Locality-Sensitive Hashing for Faster Big Data ETL Comparison

This post supplements Data Extraction Methods in Big Data ETL — read that one first if you haven’t. Building on it, this post tackles how to compare data quickly when the volume is enormous.

Last post hashed the digest of every field in each row, compressing dozens of fields into a single hash to speed up comparison. But that only compressed the fields — the row count stayed the same. With billions of rows we still can’t find the changed records fast enough.

Locality-Sensitive Hashing

Suppose both sides hold a trillion rows. Following the comparison approach from last post, how many comparisons would we make? A trillion times a trillion, because we’d traverse both sides — obviously unworkable. So instead we can batch the data into chunks and hash them.

After hashing the fields, sort by id and group every ten thousand rows: ids 1-10000, 10001-20000, 20001-30000, and so on. Concatenate the hashes within each group and hash the result again to get that group’s hash — the locality-sensitive hash over the whole dataset. A trillion rows get split and compressed into a hundred million locality hashes. Compare values group by group, and whenever one differs, compare the per-row hashes inside that group to find the inconsistent records.

An Example

For simplicity let’s use 20 rows, from data source A and data source B:

id	field	field	field	field
1	content	content	content	content
2	content	content	content	content
3	content	content	content	content
4	content	content	content	content
5	content	content	content	content
6	content	content	content	content
7	content	content	content	content
8	content	content	content	content
9	content	content	content	content
10	content	content	content	content
11	content	content	content	content
12	content	content	content	content
13	content	content	content	content
14	content	content	content	content
15	content	content	content	content
16	content	content	content	content
17	content	content	content	content
18	content	content	content	content
19	content	content	content	content

id	field	field	field	field
1	content	content	content	content
2	content	content	content	content
3	content	content	content	content
4	content	content	content	content
5	content	content	content	content
6	content	content	content	content
7	content	content	content	content
8	content	content	content	content
9	content	content	content	content
10	content	content	content	content
11	content	content	content	content
12	content	content	content	content
13	content	content	content	content
14	content	content	content	content
15	content	content	content	content
16	content	content	content	content
17	content	content	content	content
18	content	content	content	content
19	content	content	content	content
20	content	content	content	content

First hash the field contents of each row, giving:

id	hash
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	hash
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

Then we group every 10 rows and hash each group’s hashes again:

id	locality hash	hash
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	locality hash	hash
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

Originally we needed 19 × 20 = 380 comparisons. Now we compare just the two locality hashes first, spot that the id 11-20 range differs, then compare each detailed hash inside that range — 9 × 10 = 90 comparisons — plus the 2 locality-hash comparisons, so just 92 total does what used to take 380. Here’s the diagram: