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

[drymonfidelia]

[NXzCH8fP20468ML5]

1. hash
2. 加序号
3. 按照 hash 分区
4. 逐个处理分区
5. 分区内排序
6. 分区外归并排序

只有单机的话，可以考虑用 duckdb ，多机就用 spark 吧。

[yangxin0]

分治：
1 、用空间换时间（计算）
2 、用时间（计算）换空间

针对（ 1 ）有 spark 集群很快的，如果预算有限那么方法（ 2 ）：
1 、把数据分成 N 块，并针对 N 块内进行去重
2 、从 n 块中取一块，和剩下的 n-1 块去重，取这一块建立 hash or map 都可以，n-1 按照顺序读取
3 、从剩下的 n-1 块中又进行步骤（ 2 ）， 直到 n=0
4 、经过上述思路处理的 csv 就包含重复

[caola]

直接存入 kvrocks (硬盘版 redis)

[dacapoday]

单文件这么大，文件系统压力也不小吧。多数文件系统单文件也不支持这么大吧

[james122333]

sed 有往下查找一样内容行并删除的工具都可以 其它的都要内存或硬盘空间 vim 就差在它开启文件要暂存 不然也可以

[YTMartian]

磁盘够用的话，先外部排序，然后直接读取，忽略与上一条相同的数据就行了吧，随机读取文件指定位置，也不用加载进内存

[dode]

按顺序处理，依据一个合适长度的前缀做分区，逐行文本进行处理，写入到对应分区下面。

检索特定行文本，是否在对应分区内存在，不存在则写入，存在就返回已存在。

[chen7897499]

emeditor

[chen7897499]

https://www.emeditor.com/text-editor-features/large-file-support/files-up-to-248gb/

[NotLongNil]

上面有人提到的 Bloom Filter 应该是相对最优的解法了，实现简单，占用内存低，速度也快。唯一的问题就是要选择合适的长度，将错误率降低，这需要一定的算法知识，不过现在可以问 AI 了，让 AI 给出公式

[ClericPy]

有点像 map reduce 场景，归并加快排

问 AI 是好办法

[msg7086]

我能想到的两种不同的做法。
第一种，在内存不足的情况下，放弃掉内存，直接用 SSD 读写。
在 SSD 上开一个数据库（比如 MySQL 或者 Postgres ），把已经存在的 hash 写到数据库里。
然后流式扫描每一行，取 hash 比对数据库，如果存在 hash 就跳过，不存在就写到结果集里并添加到数据库。
要快速稳妥可以用两种不同的 hash ，比如 xxHash 做一次过滤，SHA1 做二次检验。

第二种，在内存不足的情况下，分批处理。
多次流式扫描每一行，取 hash ，每次只处理 hash 第一个 hex 字符相同的那些数据。
第一次只索引和处理 sha1hash[0] == '0'，第二次只索引和处理'1'，这样可以把内存需求降到 1/16 ，缺点是 hash 计算也会是 16 倍。
稍微优化一下的话，可以在第一次遍历的时候在数据上追加 sha1hash[0]作为分区标记，这样后面 15 次就不会重复计算，缺点是会每行多一两个字节，而且要多写入一次磁盘。

[esee]

什么叫保级顺序？比如在一百万的位置和 200 万的位置有重复项，则删除后面重复的那个是么。然后能提供多大的内存和硬盘，

[wxf666]

想到个方法，预计耗时：10 小时，准确率：100% 剔除重复行。


## 简单流程

1. 分块排序。
2. 同时循环每块，删掉非首次出现的重复行。
3. 分别循环每块，按行号顺序，输出未被删掉的行。


## 详细流程

1. 分块 240GB 文件，每块排序后，写入固态。同时保存每行长度+原始偏移量（约 (240 << 30) / 335 * 8 / 1024 ^ 3 = 5.7 GB ）。
2. 利用小根堆，流式排序（按 <string, offset> 排）所有分块每一行。非首次出现行，保存该行偏移量，到相应块的删除名单里。
3. 循环每块，排序原始偏移量、删除名单，按序输出（未被删除的）相应行，至最终文件。


## 耗时计算

1. 顺序读写：9 小时（ 3 次顺序读，2 次顺序写，假设都为 1GB/s ）。
2. 内存字符串排序：< 1 小时（实测轻薄本 i5-8250U ，每秒归并排序 200W 次 335 长度的随机字符串，约 6900W 次比较）。
- 多线程快排/归并：`(每块行数 = (240 << 30) / 335) * log2(每块行数) * 块数 = 6017 亿` 次比较，我的轻薄本 8 线程需 0.3 小时。
- 单线程小根堆：`202e8 * log2(块数 = 6.2 * 1024 / 240 = 26.5) * 2 = 1910 亿` 次比较，需 0.7 小时。

[wxf666]

34 楼纠正下数据，实测轻薄本 i5-8250U ，1.5 秒归并排序 320W 个 336 长度的随机字符串，约 6500W 次比较。

- 多线程快排/归并：总计 6017 亿次比较，我的轻薄本 8 线程需 0.5 小时。
- 单线程小根堆：总计 1910 亿次比较，单线程需 1.2 小时。

差不太远。。

[wxf666]

@dcsuibian #2 ，@opengps #3 ，@msg7086 #32：
如果数据库，每秒写入 10W 条，总计要 203e8 / 1e5 / 3600 = 56 小时？

@YTMartian #26 ，@dode #27：
就算固态 4K 随机读写有 10W IOPS ，算下来也要 56 小时吧？

[wxf666]

@cndenis #14 ，@hbcolorful #17 ，@NotLongNil #30：

用布隆过滤，几十 GB 好像不够。
在线算了下，50 GB + 15 函数，都会有 1 / 25000 概率出错。。
250 GB + 11 函数，算完 203 亿行，才能有 83.8% 的概率，一个不出错？


@phrack #15：

压缩内存，来存 hash ？好像真的可行。。
平均而言，写入 (372 << 30) / 4096 = 1 亿次，就会占满 372 GB 内存页。即，几乎一开始就会启用 zram ？
我在别处看了看，lz4 每秒能有 200W 次 IO ，算下来要 2.8 小时即可？
话说，这个和 Bloom Filter 相比，哪个出错概率小呢？

[dingwen07]

@wxf666
Bloom filter 的假阳性率是要看哈希函数的数量的吧

[hobochen]

大概想了一下，一定深度的前缀树，叶子节点是哈希表或者平衡树存原来的行号应该是一个可行的方案。

[hobochen]

更正：叶子节点应当是一个哈希表/平衡树； k 是哈希值，v 是行号