[单个 6.20TB 的超大 csv 文件保持顺序的情况下进行去除重]各个方案的可行性分析

原帖在这里.具体的需求如下:

行数是 203 亿，平均行长 335
去重是基于整行文本
前缀重复度不高，没有 ID
内存最大 256GB
重点是文件保持顺序

本文只讨论几种可行性的方案。

中间件方案(基于硬盘)

通过中间件来处理是可行的，无论你是 mysql 、postgresql 、sqlite 、hbase 还是 kvrocks ，都可以在插入的时候判断同样的内容是否存在。而这些数据库是基于磁盘的，因此磁盘的 IO 决定了这个方案的上限。

以 kvrocks 为例(我前段时间刚好压测过 kvrocks)，kvrocks(部署在 SSD 上)单机指令的 TPS 为 10 万。那么处理 203 亿行数据的时间为2.3 天。我们可以部署 kvrocks 集群来增加 kvrocks 的吞吐量，由于本次需求只限制了内存，没有限制其他的 CPU 等，我们可以尽量多部署几个节点，让 kvrocks 集群的吞吐量高于我们读文件的性能即可。我在我本机 SSD 上测试的读取文件的性能为 1 秒钟 150 万行，那我们部署 15 个 kvrocks 节点即可。

优点

这个方案的好处在于只需要很小的内存。中间件简单，只要部署一下 kvrocks 集群就行了。受限于写文件性能，因此没有加行号重新写入文件。所以本方案还是推荐单线程读文件,最后处理完的结果就是最终的结果(不需要重新排序)。

中间件方案(基于内存)

使用 redis 的布隆过滤器能够很好的处理重复的数据。使用 redis 的限制是内存，我们通过这个网站来计算一下所需要的内存。

203 亿个 key ，允许错误率 1%时，需要 24GB 内存
203 亿个 key ，允许错误率 0.1%时,需要 35GB 内存

看样子内存是符合要求了。我们再计算一下所用时间。

单机 redis 的 TPS 为 20W,那么处理 203 亿行数据的时间为1 天。

集群 redis 所用的时间和 redis 的节点数有关系，集群节点数越多,则 TPS 越高。由于最大内存为 256GB ，CPU 没有限制,那么我们可以部署 9 个 redis 主节点，总共消耗 24GBb*9=216Gb 。则理想状态下处理 203 亿行数据所用时间为3 小时。

什么是理想状态？数据完全离散，每行数据都落到不同的分区。这个视具体的数据情况而定。

第二个问题是当我们部署 redis 集群后，redis 集群的吞吐量为 180 万每秒,而我们使用单线程读取文件，能达到这个量级吗？我试了一下流式读取 SSD 上的文件,每秒钟大概读 150 万的样子。如此看来读文件也不是瓶颈，而且我们还优化到了 3 小时。

优点

这个方案的好处在于中间件简单，只要部署一下 redis 集群就行了。由于是单线程读文件然后处理，因此也不需要重排序。

分治法

我当初看到这个需求的时候第一时间想要的也是分治法。我们就按照分治法的思路分析一下可行性。

hash
加序号
按照 hash 分区
逐个分区处理
分区内排序

由于分治法会把整个文件通过 hash 算法重新分散到不同的文件中，对于文中的需求按照文件顺序，则需要添加行号来用于最后的排序。第 1 ，2 ，3 步都是用单线程进行操作。在我本机 SSD 上测试了一下，处理 1000 万条数据的时间为 2 分钟，大量的时间都花在写文件上。以同样的性能评估 203 亿行的数据执行 1,2,3 的步骤，则所花费的时间为2.9 天。

后续的处理不在赘述，因为 hash 分区重新写文件的时间太久已经明显的不如其他的方案。

Spark

答主没有用过 Spark ，不知道具体的分区消耗多少内存以及读取性能和处理性能，无法给出具体的可行性能答案。

noparking188

197 天前

@drymonfidelia 能不能补充，对于这样的数据量，你给的已知条件不够
1. 什么类型的数据，给个 sample ，或类似的 sample?
2. 试过切块压缩后的存储占用吗，比如切 10GB 一块，再行存压缩或者列存压缩后分布占用？
3. 最高有 256G 内存，那么计算资源（ CPU 核）能有多少，SSD 读写达到多少？
4. 如果服务器为多台，带宽达到多少？
5. 结果文件是否要求为同样单个 CSV 文件？
6. 处理时间要求多少？
7. 任务为一次性的，还是后续有同样的需求，方案要能复用？

我有个想法可以讨论下：
1. Spark 或者 Hadoop 之类计算框架先做数据预处理，追加行号、数据值编码为整数，切块和压缩后存储（比如 10 GB 一块，parquet 格式 snappy 压缩）
2. 真正的计算任务就是对先前预处理后的数据进行处理，可以用 Spark ，或者 PrestoDB DB 这种 MPP 计算引擎

我想到的主要问题和瓶颈：
1. 数据量太大，还是单个文件，磁盘 IO 是主要耗时，所以要预处理做切块、编码、压缩，减轻任务计算时的 IO 压力；
2. 串行处理无法充分利用计算资源，所以要数据切块分区、利用成熟的分布式计算框架，比如 Spark

感觉这是一个工程问题，重在如何优化。

非常希望你能分享下后续，是否解决了，解决方案，感觉很有意思。

wxf666

195 天前

@lsk569937453
@drymonfidelia #4

我在原贴 99 楼回复了，用的分块排序、归并去重方法，

6 秒（保持顺序地）去重 2.50 GB 文本（ 900 万行，336 字/行），
照此速度，预计 4 小时即能去重完毕 6.20 TB 文本？

这是在七年前 i5-8250U 轻薄本上，限制 1 GB 内存，四线程跑出来的。（截图在原贴）
当然，文本存在内存盘里，读 8G/s ，写 3G/s ，1000 元 2TB 的固态都有的水平，应该不算过分。

@tool2dx #3

精确去重，不应该是每行两两比较吗？

但如果能承受极小概率冲突，用哈希应该会快很多。

@jsjscool #18

大佬是用什么写的，只需要几行就行呢？

我也是用的 merge sort + 多线程，但写了两三百行了。。

@securityCoding #23

能自己手撸一个跑吗？感觉也不算慢呀。。

@noparking188 #25

手撸了一个，不知对你有帮助吗？