H5W3
当前位置:H5W3 > 其他技术问题 > 正文

大数据ETL技术中对数据进行局部哈希对比优化速度对比

这篇文章是对上一篇文章《大数据ETL技术中的数据抽取方法》的补充,如果还没看过上一篇文章建议先看上一篇文章,本文在上一篇文章的基础上讨论解决数据量在非常大的情况下如何快速对比数据。

在上一篇文章中我们通过对每条数据的所有字段进行了哈希摘要,将几十个字段摘要成了一串哈希值,加快的我们的对比速度,但这只是将字段进行了压缩,数据的数量还是没有被压缩,如果有几十亿条数据,我们还是不能快速的找到变化的数据。

局部哈希

假如我们两边数据各有一万亿条数据,按照上一篇文章提出的对比思路,我们将扫描对比多少次呢?是一万亿乘以一万亿,因为要遍历两边的数据,这种扫描的效率肯定是不行的,所以我们可以将数据分片打包计算哈希摘要。

在字段做完哈希以后,我们先按id字段排个序,然后按照每一万分个组,例如id在1~10000,10001~20000,20001~30000这样,每个组的哈希值连起来再做一次哈希,就得到了这个组的哈希值,也就是全部数据的局部哈希值,一万亿的数据被我们切分压缩成了一亿个局部哈希,我们对比每个局部哈希值,遇到不一样的,再去对比这个组里每条数据的哈希,就可以找到不一致的数据。

举个例子

为了方便演示,我们以20条数据为例,分别有数据源A、数据源B:

id 字段 字段 字段 字段
1 内容 内容 内容 内容
2 内容 内容 内容 内容
3 内容 内容 内容 内容
4 内容 内容 内容 内容
5 内容 内容 内容 内容
6 内容 内容 内容 内容
7 内容 内容 内容 内容
8 内容 内容 内容 内容
9 内容 内容 内容 内容
10 内容 内容 内容 内容
11 内容 内容 内容 内容
12 内容 内容 内容 内容
13 内容 内容 内容 内容
14 内容 内容 内容 内容
15 内容 内容 内容 内容
16 内容 内容 内容 内容
17 内容 内容 内容 内容
18 内容 内容 内容 内容
19 内容 内容 内容 内容
id 字段 字段 字段 字段
1 内容 内容 内容 内容
2 内容 内容 内容 内容
3 内容 内容 内容 内容
4 内容 内容 内容 内容
5 内容 内容 内容 内容
6 内容 内容 内容 内容
7 内容 内容 内容 内容
8 内容 内容 内容 内容
9 内容 内容 内容 内容
10 内容 内容 内容 内容
11 内容 内容 内容 内容
12 内容 内容 内容 内容
13 内容 内容 内容 内容
14 内容 内容 内容 内容
15 内容 内容 内容 内容
16 内容 内容 内容 内容
17 内容 内容 内容 内容
18 内容 内容 内容 内容
19 内容 内容 内容 内容
20 内容 内容 内容 内容

我们先对每条数据的字段内容进行哈希摘要,得到如下内容:

id 哈希
1 3dc57f9c5592436c88a2524c20c0286e3dc57f9c
2 9c14be621dd8440b9af1904d14bfc3869c14be62
3 5e4e864908ab4bf184fca290d65637c35e4e8649
4 a86f9409404b4ad4add119b010d48acda86f9409
5 7d60b2fff0884bc196342fc02cf917d67d60b2ff
6 4956454889694d129e73c717afc4bb4c49564548
7 e1a6c8d8895a49528d2a26429cd3f541e1a6c8d8
8 80b1d5d92257414ebe6b3861bf7e978980b1d5d9
9 3969f7b63507472aacae2b377ecc75453969f7b6
10 9d6e4f78fc424d58ba1464da308ee6d59d6e4f78
11 aa75a53d3ec1442d994c477cb4761608aa75a53d
12 72be42e2b2c943c0a46ea2d6ba73746972be42e2
13 219ed8d179e24ba88cd34779c8022384219ed8d1
14 e1b6b02367ed49e7b1c01cdf60b0dffce1b6b023
15 d41fd4ec5efe44779d5970592a6b2bacd41fd4ec
16 906d965b7a114608bb170f4504df0aba906d965b
17 294753f98c564bf7a58e0fc1ace67aff294753f9
18 148bcb667f9d412187176d346f6bcbc0148bcb66
19 927d8354109a420bb8a0434d6aba7a69927d8354
id 哈希
1 3dc57f9c5592436c88a2524c20c0286e3dc57f9c
2 9c14be621dd8440b9af1904d14bfc3869c14be62
3 5e4e864908ab4bf184fca290d65637c35e4e8649
4 a86f9409404b4ad4add119b010d48acda86f9409
5 7d60b2fff0884bc196342fc02cf917d67d60b2ff
6 4956454889694d129e73c717afc4bb4c49564548
7 e1a6c8d8895a49528d2a26429cd3f541e1a6c8d8
8 80b1d5d92257414ebe6b3861bf7e978980b1d5d9
9 3969f7b63507472aacae2b377ecc75453969f7b6
10 9d6e4f78fc424d58ba1464da308ee6d59d6e4f78
11 aa75a53d3ec1442d994c477cb4761608aa75a53d
12 72be42e2b2c943c0a46ea2d6ba73746972be42e2
13 219ed8d179e24ba88cd34779c8022384219ed8d1
14 e1b6b02367ed49e7b1c01cdf60b0dffce1b6b023
15 d41fd4ec5efe44779d5970592a6b2bacd41fd4ec
16 906d965b7a114608bb170f4504df0aba906d965b
17 294753f98c564bf7a58e0fc1ace67aff294753f9
18 148bcb667f9d412187176d346f6bcbc0148bcb66
19 927d8354109a420bb8a0434d6aba7a69927d8354
20 49f952179c10465bb1f76961384a404949f95217

然后我们按照10条为一组,对每组的哈希再摘要哈希值,得到如下情况:

id 局部哈希 哈希
1 75d65498d9c861fa464c1607fe7c60b5e1f8a9de 3dc57f9c5592436c88a2524c20c0286e3dc57f9c
2 9c14be621dd8440b9af1904d14bfc3869c14be62
3 5e4e864908ab4bf184fca290d65637c35e4e8649
4 a86f9409404b4ad4add119b010d48acda86f9409
5 7d60b2fff0884bc196342fc02cf917d67d60b2ff
6 4956454889694d129e73c717afc4bb4c49564548
7 e1a6c8d8895a49528d2a26429cd3f541e1a6c8d8
8 80b1d5d92257414ebe6b3861bf7e978980b1d5d9
9 3969f7b63507472aacae2b377ecc75453969f7b6
10 9d6e4f78fc424d58ba1464da308ee6d59d6e4f78
11 77b540f49a595afbb1c3f9209de23e8d00688c02 aa75a53d3ec1442d994c477cb4761608aa75a53d
12 72be42e2b2c943c0a46ea2d6ba73746972be42e2
13 219ed8d179e24ba88cd34779c8022384219ed8d1
14 e1b6b02367ed49e7b1c01cdf60b0dffce1b6b023
15 d41fd4ec5efe44779d5970592a6b2bacd41fd4ec
16 906d965b7a114608bb170f4504df0aba906d965b
17 294753f98c564bf7a58e0fc1ace67aff294753f9
18 148bcb667f9d412187176d346f6bcbc0148bcb66
19 927d8354109a420bb8a0434d6aba7a69927d8354
id 局部哈希 哈希
1 75d65498d9c861fa464c1607fe7c60b5e1f8a9de 3dc57f9c5592436c88a2524c20c0286e3dc57f9c
2 9c14be621dd8440b9af1904d14bfc3869c14be62
3 5e4e864908ab4bf184fca290d65637c35e4e8649
4 a86f9409404b4ad4add119b010d48acda86f9409
5 7d60b2fff0884bc196342fc02cf917d67d60b2ff
6 4956454889694d129e73c717afc4bb4c49564548
7 e1a6c8d8895a49528d2a26429cd3f541e1a6c8d8
8 80b1d5d92257414ebe6b3861bf7e978980b1d5d9
9 3969f7b63507472aacae2b377ecc75453969f7b6
10 9d6e4f78fc424d58ba1464da308ee6d59d6e4f78
11 91244c3037f6b6c308ead098c2ed48584c4eefad aa75a53d3ec1442d994c477cb4761608aa75a53d
12 72be42e2b2c943c0a46ea2d6ba73746972be42e2
13 219ed8d179e24ba88cd34779c8022384219ed8d1
14 e1b6b02367ed49e7b1c01cdf60b0dffce1b6b023
15 d41fd4ec5efe44779d5970592a6b2bacd41fd4ec
16 906d965b7a114608bb170f4504df0aba906d965b
17 294753f98c564bf7a58e0fc1ace67aff294753f9
18 148bcb667f9d412187176d346f6bcbc0148bcb66
19 927d8354109a420bb8a0434d6aba7a69927d8354
20 49f952179c10465bb1f76961384a404949f95217

原本需要对比19X20=380次,现在我们只需要先对比两个局部哈希,发现id在11~20的这个区域不一致,那么我们再对比11~20的这个区域中每个详细的哈希值,对比9X10=90次,再加上我们对比局部哈希的两次,我们只对比了92次就把原先需要380次的对比完成了。以下是示意图:

大数据ETL技术中对数据进行局部哈希对比优化对比速度

本文地址:H5W3 » 大数据ETL技术中对数据进行局部哈希对比优化速度对比