要对单个 6.20TB 的超大 csv 文件保持顺序的情况下进行去除重复行，有什么好思路？显然不可能加载进内存

noqwerty

29 天前

可以试试 polars streaming + file sink ？ https://www.rhosignal.com/posts/streaming-in-polars/

dode

29 天前

@wxf666 这个是连续 IO 的读写很快，文件在 Linux 系统中读写也可以开启内存缓存

dode

29 天前

@wxf666 固态硬盘随机读写 10 IOPS ，服务器也可以搞几块 U3 固态，存这个计算缓存加速呀

tonywangcn

29 天前

@wxf666

你的计算好像不对吧

n = 20300000000
p = 0.000000001 (1 in 999925223)
m = 875595082773 (101.93GiB)
k = 30

https://hur.st/bloomfilter/?n=20300000000&p=1.0E-9&m=&k=

acapla

29 天前

不限时间的话:

for (i = 1; i < N; i++)
for (j = 0; j < i; j++)
if line[i] == line[j]:
skip line[i]

HanashirodotETH

29 天前

分块 - 用 96 位哈希编号，去重，排序 - 多路归并
但是也要大概 240G 内存。

wxf666

29 天前

@dingwen07 #38 是的。37 楼有提及到，用多少哈希函数。

@dode #42

《写入到对应分区下面》这个是缓存尽可能多的文本（如 1GB ），再写入，是吗？
《检索特定行文本，是否在对应分区内存在》这个是如何做到，顺序读的呢？

@tonywangcn #44

平均每十亿条，就误认为一次，某行是重复行，导致丢失该行？
那你要问 @drymonfidelia 愿不愿意丢失几十行数据了。。

sunnysab

29 天前

@phrack sha1sum 本身如何存储或索引呢？使用 BTree （或类似的树）吗，还是多级 hash 索引？

wxf666

29 天前

36 37 楼，好像没 @ 成功。。再试一下。。

@opengps #3
@msg7086 #32

如果数据库，每秒写入 10W 条，总计要 203e8 / 1e5 / 3600 = 56 小时？

@hbcolorful #17
@NotLongNil #30

用布隆过滤，几十 GB 好像不够。
在线算了下，50 GiB + 15 函数，都会有 1 / 26000 概率出错，大约丢失 80W 行数据？
250 GiB + 11 函数，算完 203 亿行，才能有 83.8% 的概率，不丢失任何数据，也不保留任何重复行？

hguangzhen

29 天前

惊了~ 竟然没人提到 RocksDB 吗？本地的文件型 KV 存储库，内置 bloomfilter ，磁盘空间够用，应该很简单的

mayli

29 天前

如果你只是想最简单的解法（不考虑最高效率或者多机并发）可以试试 sort+uniq

sort 是可以排序比内存大的文件的: https://vkundeti.blogspot.com/2008/03/tech-algorithmic-details-of-unix-sort.html
然后排序后的 uniq 是不怎么吃内存

不过我看有个需求是要保持文件顺序的话，你可以用 uniq --repeated 来找到重复行，如果你重复行不多，那搞个脚本直接过滤一遍源文件就好，也是线性的。

Kaiv2

29 天前

1. 先计原始文件 a.txt 算每一行 hash 保存到 hash.txt 文件
2. 复制一份 hash.txt -> hash-2.txt 用于去重计算
3. 取 hash-2.txt 文件中 10000(这个数根据内存大小预估) 个 hash 前 8 位不重复 hash_array_8
4. 重复的的写入 hash-4.txt, 剩于的写入 hash-2.1.txt -> hash-2.txt ，循环处理直到 hash-2.txt 没有记录
```txt
let limit = 10000; // 控制内存使用
let hash_array_8 = [];
let cache_line = []
for(let h_line: read_line(hash_2.txt)) {
if(hash_array_8.size < limit) {
if(!hash_array_8.has(h_line.sub(8))) {
hash_array_8.add(h_line.sub(8))
}
}
if(hash_array_8.has(h_line.sub(8))) {
if(cache_line.has(h_line)) {
write(hash-4.txt);
} else {
cache_line.add(h_line);
}
} else {
write(hash-2.1.txt);
}
}
mv(hash-2.1.txt, hash-2.txt)
```
5. 得到 hash.txt 跟文件一一对应，hash-4.txt 是重复的记录
6. hash-4.txt (如果重复的不多）直接读取到内存，对应读取 a.txt, hash.txt 每一行，比较 hash 重复跳过，不重复写入 b.txt
没有考虑过计算量，内存不够可以考虑试试这个办法

Kaiv2

29 天前

@Kaiv2 写着写着写成了单机的，这么做多此一举，太蠢了。。。应该是分 hash-3.1 .. n.txt 多个机器同时处理，然后合并重复数据 hash-4.1..n.txt

drymonfidelia

29 天前

@wxf666 不能丢失数据
@esee 是的。最大可以提供 256GB 内存，硬盘没有限制

msg7086

29 天前

@wxf666 #35 上 TB 的数据怎么处理都是会很慢的。（一秒 10w 条数据可能到不了）

我建议用第三方数据库纯粹是因为这样对实现的要求最低，不需要你搞大内存服务器，不需要自己开发复杂的算法，全部用已知的成熟的方案，你只要插上一堆 SSD 然后干别的事就行了，等个几天数据就都跑完了。算法简单所以要根据需求修改起来也简单，可维护性也好。（用人话说就是，工程师不需要加班，让服务器加班就行。）

现实当中从 SSD 读取数据到内存也是要花时间的，这么大的量级还要跑前后依赖的操作，我是觉得快不起来。

（如果能并行 map reduce 倒是能快不少，但这里不太行。）

lmshl

29 天前

版本答案：RocksDB （与其他 leveldb family 产品）

解析：203 亿个 bloomfilter 在 p=0.01 下所需的内存空间约为 23.75GB 。实际上，去重所需的空间会少于 203 亿，所以在这个内存空间下，实际 p 值将进一步降低。

大部分人可能对 bloomfilter 的使用存在误解，他们只考虑在只有 bloomfilter 单一算法存在的前提下来解决需求，这显然是错误的。现代数据库对 bloomfilter 的应用主要是用来降低 miss key 对磁盘 IO 的影响。如果 bloomfilter 认为这个 key 没有出现过，那么这个 key 确实没有出现过。当 bloomfilter 认为它可能出现过，那么出现的概率为 1-p ，此时需要回表二次确认（磁盘 IO ）。

假设一个典型的重复度为 10 倍的 200 亿数据表文件，在这个空间下，p 值会低至 1e-20 。

那么对这个文件去重，总共会发生 200 亿次内存 bloomfilter 读取，20 亿次 bloomfilter 写入+磁盘顺序写入，以及 180 亿次磁盘随机读取。（考虑到数据库对磁盘的批量写入优化，sstable/memtable 这个数值将会被巨幅降低）

假设一个重复度为 0.1 倍的 200 亿数据表文件，在这个空间下，p 值变化不大。

那么对这个文件去重，总共发生 200 亿次内存 bloomfilter 读取，180 亿次 bloomfilter 写入+磁盘顺序写入，以及 20 亿次磁盘随机读取。（同上）

根据网上其他人做的吞吐量测试，rocksdb 在现代硬件条件下可以稳定达到 10k*rows/s 以上的写入性能，或>1GB/s 的写入吞吐量。乐观地估计，6.2TB 的文件应该能在 2 小时到 2 天左右完成去重。

cabbage

29 天前

@wxf666 布隆过滤器单独用确实不行，免不了假阳性，即便事后检查那也逃不了随机读，不是稳定的方法。但如果纯粹作为首次顺序读的过滤器来用，应该还不错，可以降低一些输入数据量。

to 34 楼：其实没看懂第二步的堆排序怎么回事，是说在一次排序中对所有行进行排序并去重吗？如果这样的话，那比较的时候是不是还需要在内存里保留所有原始 string ？来讨教下，乐意的话可否点明一二？

harmless

29 天前

203 亿行全部计算成 hash ，再加上行号，大概 700 多 G
1. 遍历每行，计算出 hash ，按 hash 第一位将 hash 和行号写入不同的文件，例如 hash 第一位为 0 ，则写入 hash_0.txt ，这样一共会有 16 个文件，每个文件大概 40 多 G
2. 分别对每个文件按 hash 排序，找出重复的需要删除的行号，记录到文件中
3. 遍历原始文件，删除需要删除的行

lrjia

29 天前

先 hash ，按照 hash 前缀分块成多个文件，使分块后单块的大小可以放入内存。再对每块使用 hash 表去重。最后合并多个文件，用归并排序的做法。这中间应该都是文件的顺序读写。

cloudzhou

29 天前

布隆过滤器，申请硬盘 db 空间作为布隆过滤器存储，按位标记，只要空间足够大，冲突就很小
在布隆过滤器冲突情况下，将冲突部分，存入到其他人提到的某种 kv db ，然后排除重复处理