[单个 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 的思路去重的.

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

[CodeAllen]

如果要减少内存使用，可以考虑使用布隆过滤器，缺点就是有误判率。
203 亿数据规模，按照误判率 0.1%计算，布隆过滤器大约需要 22.83 GB 的内存------GPT4o 。
如果能容忍更大的误判率内存需求可以继续减少。

[jurassic2long]

添加一个行号，直接大数据那一套，group by 就行了

[picone]

1. 可以给出一点大概的思路和手段吗，不然这像是炫耀贴没有任何实质意义
2. 能有证明内存和处理行数是线性关系吗，不然不能直接得出 203 亿行就是 272GB 内存
3. 处理时间也是重要的指标，有相关的 benchmark 吗？

[tool2dx]

hash 去重不难，我估计 gpt4 也能把代码写出来，就是看怎么特定优化内存占用。

[0o0O0o0O0o]

V2EX 自己的 1brc

[ShuWei]

磁盘、内存、时间的平衡游戏而已，提出用一堆中间件的人，我表示很费解，搞得谁不知道有那些中间件一样的，提出问题的人，应该是希望不借助外部工具来解决这个问题吧

分块、哈希、归并去重，过程中使用一些小技巧，应该是最通用的解决方案了，像 op 这样，中间控制一下参数，从而控制资源的使用，就已经能达到目标了，如果需要更精确更优的解决方案，恐怕还得依赖于更精确的基础条件设置

[heguangyu5]

@picone

1. 思路就是基于 hash 去重的.
2/3. 可执行程序在那里,你可以自己 down 回来试一下.我给的内存用量和处理时间(20 亿以内)是实测数据,不是拍脑袋粗估的.

[stiangao]

看情况分词生成倒排索引文件，递归生成索引文件直到能加载进内存处理，然后顺序的加载所有索引文件去比较

[heguangyu5]

@ShuWei 是的,简单的 hashtable 就能解决,前提是仔细思考问题本身和操控计算资源.

[wxf666]

有点感兴趣，问一下楼主：

1. 楼主硬盘读写速度多少？

2. 可以指定限制多少内存完成吗？

3. 有不同的两行，恰好 hash 相同，会出问题吗？

4. 除顺序读一次原文件外，还需要额外读写多少文件吗？

5. 能轻而易举改造成，针对 CSV 文件（可能有字符串跨多行），且现有成绩影响不大，是吗？

[Keuin]

一行 shell 的事被你搞得这么复杂，6TB 可以存内存里，6PB 呢？
看不下去了，这个源码也不愿意给，我直接给出结论：
```shell
awk '{print $0","NR}' input.csv | sort | sed -E 's/,[0-9]+$//' | uniq
```
其中 input.csv 替换成你的输入文件，结果将出现在 stdout ，如果要存到文件，自己重定向一下即可。
运行实例：
```
$ cat input
1,2,3,4
2,3,4,5
3,4,5,6
4,5,6,7
2,3,4,5
1,2,3,4
5,6,7,8
$ awk '{print $0","NR}' input
1,2,3,4,1
2,3,4,5,2
3,4,5,6,3
4,5,6,7,4
2,3,4,5,5
1,2,3,4,6
5,6,7,8,7
$ awk '{print $0","NR}' input | sort
1,2,3,4,1
1,2,3,4,6
2,3,4,5,2
2,3,4,5,5
3,4,5,6,3
4,5,6,7,4
5,6,7,8,7
$ awk '{print $0","NR}' input | sort | sed -E 's/,[0-9]+$//'
1,2,3,4
1,2,3,4
2,3,4,5
2,3,4,5
3,4,5,6
4,5,6,7
5,6,7,8
$ awk '{print $0","NR}' input | sort | sed -E 's/,[0-9]+$//' | uniq
1,2,3,4
2,3,4,5
3,4,5,6
4,5,6,7
5,6,7,8
```

不管你的电脑内存是 1T 还是 1G ，都可以正确运行并得到相同输出，因为 sort 命令用的是归并排序，是外存算法。如果你要限制用到的内存大小，把 sort 改成 sort --buffer-size=100M ，即可限制只用 100M 内存，其他命令都是行缓存算法，只会保存当前行在内存里，也就是说，最大内存用量是 max(100M, max_line_size_bytes)

[wxf666]

@Keuin #11 原帖还要求，保持文本原有顺序诶。。

分块归并排序确实好用，我在原帖也手撸了一个，i5-8250U 每分钟能排序 25 GB 。但读写量还是太大了。。

换成只写入 MD5/SHA-1 值的话，读写量能减少 95%。代价就是有极小概率会哈希冲突。。

但也能通过回原文件比较两行解决。代价就是可能会有不少的随机读，和重复行数量成正比。。

[heguangyu5]

@wxf666

1. 楼主硬盘读写速度多少？

4 块 4TB 西数机械硬盘做 RAID 0,读写速度可能在 200~400M/s?不太确定.
gen-20.3B-lines.sh 生成 6.8TB 数据用了 7 个多小时.

2. 可以指定限制多少内存完成吗？

dedup-use-more-mem 每 1 亿行数据需要 1.34GB 内存,N 亿就是 N*1.34,当然还需要留出几个 G 的内存给操作系统正常运行.
dedup-use-less-mem 每 1 亿行数据需要 0.67GB 内存.203 亿 136GB 就够了,所以完成 6.2TB-203 亿去重 150G 内存足够了.


3. 有不同的两行，恰好 hash 相同，会出问题吗？

hashtable 就是普通意义的那个,比例 php 的 array,其它语言里的 map, dict 什么的,hash 当然会冲突,这时要解决冲突,常见的解决冲突办法是单链表.所以结果是精确的,不会有误判率什么的.


4. 除顺序读一次原文件外，还需要额外读写多少文件吗？

dedup-use-more-mem 始终都在读原文件.

dedup-use-less-mem 需要额外借助其它文件的帮助.


5. 能轻而易举改造成，针对 CSV 文件（可能有字符串跨多行），且现有成绩影响不大，是吗？

可以的.现在是按\n 取一行的,可以换成其它逻辑.

[heguangyu5]

@Keuin 请仔细看下原贴,原 OP 已经说了 "尝试过的方案有 sort | uniq 会卡死不出结果"

[heguangyu5]

@wxf666

2. 可以指定限制多少内存完成吗?

需要的内存是和要处理的数据量成正比的,如果内存不够,那就无法完成.

当然要在内存不够的情况下完成,那就是另一个解法了,耗时可能会很长,我一开始尝试了一个方案,因为无法较准确的预估处理完所需要的时间,所以就放弃了.

现在的这两个方案处理时间是可靠的,可等的,dedup-use-less-mem 可在约 10 小时左右的时间处理完 203 亿,一个晚上就能得出结论.

[heguangyu5]

@Keuin 原 OP 也说了要尝试一下你的加行号方案,期待结果

[harmless]

不提供实现思路，鉴定炫耀帖

[Keuin]

@wxf666 昨天写的马虎，忘记顺序这个要求了，我其实又回复了一次来 update ，不过看起来楼被 v 站吞了。保序的方案是用 sort -u -k1,4 来只按原内容排序并去重，最后 sed 去掉行号，最最后的 uniq 去掉即可

[wxf666]

@Keuin #18 你是说，类似这样吗？

awk '{print NR" "$0}' in.txt | sort -u -k2 | sort -n | cut -d' ' -f 2-

感觉写入量翻倍。。而且很难扩展到（可能跨多行的） csv ？


@heguangyu5 #13

1. 平均下来，每行花费 14.4 字节内存，肯定没存原字符串。

hash 冲突时，你要回源文件，具体比较两行吗？那随机读会不会很多。。

换句话说，随机生成 1E 行，又把这 1E 行打乱，追加到原文件。dedup-use-more-mem 会随机读 1E 次吗？

2. dedup-use-less-mem 需要额外写多大文件呢？有多少次随机读写呢？这个支持流式读源文件吗？

[Keuin]

@wxf666 自己研究一下吧，昨天的楼被删了，我懒得再写一遍了，只需要假定 csv 列数固定，不需要用到 cut 。如果假定不了，简便起见，需要找一个输入里面没有的分隔符。
写入量的话，我在原 po 主帖子里分析过，不过那里把加行号的中间结果也全部存下来了，所以当时给的磁盘用量是 3*6TB 。如果都用流式传递中间结果的话，两个 sort 需要有 2*6TB 的临时空间。

[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 即可？

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