[单个 6.2TB 203 亿行 的超大 csv 文件保持顺序的情况下去重]的两个解决方案

[heguangyu5]

详细需求及讨论见 帖 1 和 帖 2.

这是个很有意思的问题,我认真思考和尝试了两三天,找到了两个解决方案.

可执行程序及简单说明见 github 6.2TB-20.3B-dedup.

由于没有合适的硬件条件,因此没有做全量 203 亿数据的测试,仅测试了 20 亿行.

测试步骤:

1. ./gen-20.3B-lines.sh > 20.3B.txt

   生成测试数据, 可修改脚本第 3 行 B=203 为你想要的数据量

2. ./dedup-use-more-mem /path/to/20.3B.txt lines

   lines 的单位是亿行,比如要测试 20 亿行,那就是 ./dedup-use-more-mem 20.3B.txt 20

   这个解决方案处理 203 亿行数据需要内存约 272GB,超出了但是很接近原帖的要求.

3. ./dedup-use-less-mem /path/to/20.3B.txt lines

   用法同上,但是这个解决方案用的内存要少一半,所以如果有 256GB 内存,那么处理 203 亿行数据是没问题的.

给出的两个可执行程序都是基于 hash 的思路去重的.

为避免被白嫖,所以只给出了可执行程序,不提供源码,见谅.

[heguangyu5]

@wxf666 这两个解决方案都是基于 hashtable 去重的,就是那个普通意义的 hashtable,没有什么花招,所以你的猜想都对.

hash 冲突了,就是要回源文件比较原始行,随机读有可能会很多.

但是如果能提前知晓数据的大致分布情况,可能会有更恰当的解决办法.

在不知道的情况下,这两个方案可以快速试错,然后找到正确的方向.

[wxf666]

@Keuin #20 写入量还是太大了。我手撸，只写一遍，都觉得大。。

换成算 SHA-1 ，最差情况，只需要写 203e8 * (20 + 6 该行偏移量) / 2 ^ 30 = 492 GB 即可。

当然，自己写肯定不如久经考验的工具成熟稳定，第一次花的时间精力也多。。



@heguangyu5 #21 C/C++ 新人，看了下排行前三的 HashTable ，感觉每行只需 11 字节即可？

6 字节原始文件偏移量 + 5 字节与原始位置的距离（ unordered_dense ）或下一节点数组下标（ emhash ）？

狠一点儿，ceil(log2(6.20 * 2^40)) - 1 + ceil(log2(203e8)) = 77 bits / 行？总共需 182 GB 即可？

剩下几字节，你用来存啥了呢。。