2021-02-06 13:16:13

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


大数据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哈希
13dc57f9c5592436c88a2524c20c0286e3dc57f9c
29c14be621dd8440b9af1904d14bfc3869c14be62
35e4e864908ab4bf184fca290d65637c35e4e8649
4a86f9409404b4ad4add119b010d48acda86f9409
57d60b2fff0884bc196342fc02cf917d67d60b2ff
64956454889694d129e73c717afc4bb4c49564548
7e1a6c8d8895a49528d2a26429cd3f541e1a6c8d8
880b1d5d92257414ebe6b3861bf7e978980b1d5d9
93969f7b63507472aacae2b377ecc75453969f7b6
109d6e4f78fc424d58ba1464da308ee6d59d6e4f78
11aa75a53d3ec1442d994c477cb4761608aa75a53d
1272be42e2b2c943c0a46ea2d6ba73746972be42e2
13219ed8d179e24ba88cd34779c8022384219ed8d1
14e1b6b02367ed49e7b1c01cdf60b0dffce1b6b023
15d41fd4ec5efe44779d5970592a6b2bacd41fd4ec
16906d965b7a114608bb170f4504df0aba906d965b
17294753f98c564bf7a58e0fc1ace67aff294753f9
18148bcb667f9d412187176d346f6bcbc0148bcb66
19927d8354109a420bb8a0434d6aba7a69927d8354
id哈希
13dc57f9c5592436c88a2524c20c0286e3dc57f9c
29c14be621dd8440b9af1904d14bfc3869c14be62
35e4e864908ab4bf184fca290d65637c35e4e8649
4a86f9409404b4ad4add119b010d48acda86f9409
57d60b2fff0884bc196342fc02cf917d67d60b2ff
64956454889694d129e73c717afc4bb4c49564548
7e1a6c8d8895a49528d2a26429cd3f541e1a6c8d8
880b1d5d92257414ebe6b3861bf7e978980b1d5d9
93969f7b63507472aacae2b377ecc75453969f7b6
109d6e4f78fc424d58ba1464da308ee6d59d6e4f78
11aa75a53d3ec1442d994c477cb4761608aa75a53d
1272be42e2b2c943c0a46ea2d6ba73746972be42e2
13219ed8d179e24ba88cd34779c8022384219ed8d1
14e1b6b02367ed49e7b1c01cdf60b0dffce1b6b023
15d41fd4ec5efe44779d5970592a6b2bacd41fd4ec
16906d965b7a114608bb170f4504df0aba906d965b
17294753f98c564bf7a58e0fc1ace67aff294753f9
18148bcb667f9d412187176d346f6bcbc0148bcb66
19927d8354109a420bb8a0434d6aba7a69927d8354
2049f952179c10465bb1f76961384a404949f95217

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

id局部哈希哈希
175d65498d9c861fa464c1607fe7c60b5e1f8a9de3dc57f9c5592436c88a2524c20c0286e3dc57f9c
29c14be621dd8440b9af1904d14bfc3869c14be62
35e4e864908ab4bf184fca290d65637c35e4e8649
4a86f9409404b4ad4add119b010d48acda86f9409
57d60b2fff0884bc196342fc02cf917d67d60b2ff
64956454889694d129e73c717afc4bb4c49564548
7e1a6c8d8895a49528d2a26429cd3f541e1a6c8d8
880b1d5d92257414ebe6b3861bf7e978980b1d5d9
93969f7b63507472aacae2b377ecc75453969f7b6
109d6e4f78fc424d58ba1464da308ee6d59d6e4f78
1177b540f49a595afbb1c3f9209de23e8d00688c02aa75a53d3ec1442d994c477cb4761608aa75a53d
1272be42e2b2c943c0a46ea2d6ba73746972be42e2
13219ed8d179e24ba88cd34779c8022384219ed8d1
14e1b6b02367ed49e7b1c01cdf60b0dffce1b6b023
15d41fd4ec5efe44779d5970592a6b2bacd41fd4ec
16906d965b7a114608bb170f4504df0aba906d965b
17294753f98c564bf7a58e0fc1ace67aff294753f9
18148bcb667f9d412187176d346f6bcbc0148bcb66
19927d8354109a420bb8a0434d6aba7a69927d8354
id局部哈希哈希
175d65498d9c861fa464c1607fe7c60b5e1f8a9de3dc57f9c5592436c88a2524c20c0286e3dc57f9c
29c14be621dd8440b9af1904d14bfc3869c14be62
35e4e864908ab4bf184fca290d65637c35e4e8649
4a86f9409404b4ad4add119b010d48acda86f9409
57d60b2fff0884bc196342fc02cf917d67d60b2ff
64956454889694d129e73c717afc4bb4c49564548
7e1a6c8d8895a49528d2a26429cd3f541e1a6c8d8
880b1d5d92257414ebe6b3861bf7e978980b1d5d9
93969f7b63507472aacae2b377ecc75453969f7b6
109d6e4f78fc424d58ba1464da308ee6d59d6e4f78
1191244c3037f6b6c308ead098c2ed48584c4eefadaa75a53d3ec1442d994c477cb4761608aa75a53d
1272be42e2b2c943c0a46ea2d6ba73746972be42e2
13219ed8d179e24ba88cd34779c8022384219ed8d1
14e1b6b02367ed49e7b1c01cdf60b0dffce1b6b023
15d41fd4ec5efe44779d5970592a6b2bacd41fd4ec
16906d965b7a114608bb170f4504df0aba906d965b
17294753f98c564bf7a58e0fc1ace67aff294753f9
18148bcb667f9d412187176d346f6bcbc0148bcb66
19927d8354109a420bb8a0434d6aba7a69927d8354
2049f952179c10465bb1f76961384a404949f95217

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

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

商业用途请联系作者获得授权。
版权声明:本文为博主「任霏」原创文章,遵循 CC BY-NC-SA 4.0 版权协议,转载请附上原文出处链接及本声明。
原文链接:https://www.renfei.net/posts/1003450
评论与留言
以下内容均由网友提交发布,版权与真实性无法查证,请自行辨别。

本站有缓存策略,时间约2小时后能看到您的评论。本站使用自动审核机制,如果您的内容包含广告/谩骂/恐怖/暴力/涉政等不和谐内容将无法展示!


本站有缓存策略,时间约2小时后能看到您的评论。本站使用自动审核机制,如果您的内容包含广告/谩骂/恐怖/暴力/涉政等不和谐内容将无法展示!