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

[lsk569937453]

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

• 行数是 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 集群就行了。由于是单线程读文件然后处理，因此也不需要重排序。

分治法

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

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

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

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

Spark

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

[sampeng]

分治法反而是成本最低的。并没限制时间一定要用最快时间。要加快磁盘吞吐也有很多办法。

[kneo]

布隆过滤器就不要再提了吧。以丢失两亿/两千万条数据的代价去重？

[tool2dx]

精确去重，最后还是要建立 hash 。

而根据生日悖论计算，你必须要一个足够大的 hash function 结果值，才能把 203 亿的冲突概率，控制在一定范围内。

[drymonfidelia]

原帖是我发的，尝试过的方案有 sort | uniq 会卡死不出结果
布隆过滤器会丢失数据，肯定是不行的
其它的方案我们都没操作经验，目前打算用 76 楼的加行号方案，看起来最靠谱。

[james122333]

为何要另外发?...

[james122333]

@drymonfidelia

76 楼...

[dapang1221]

Clickhouse 的位图？不知道每行数据是不是规律，能不能映射过去，哎呀 6.2T ，我这辈子都没接触过这么大的……

[ignor]

这么大的数据量，hash 冲突也是个不小的麻烦吧？

[psyer]

上 PySpark 试试？

[james122333]

@ignor

所以可以试试我讲的消秏最小资源解

[leonhao]

典型的 Spark 应用场景，几行 SQL 的事情，搞这么复杂

[realpg]

这种东西 一般不需要考虑性能 只需要操作简单 结果不要二次操作就好

[almas1992]

@leonhao 你实操过？

[me1onsoda]

这么大文件怎么读取？

[Vegetable]

你对时间的评估与我的认知有一些偏差。
因为我做过手机号全量 md5 排序，这也是 40 多亿的数据，我印象中跑一遍 md5 再排序，用时应该在小时级别。在此基础上去重回写到原文件可能涉及到再次排序，整个时间可能是我那套逻辑的 10(多一次排序×5 倍数量级)倍左右。我肯定没花到 7 小时。

[lsk569937453]

@Vegetable 单线程流式读文件、多线程 seek 读文件、mmap 。这三种读法的性能不一样。写也是一样。我上文的读文件都是单线程流式读，写的话也是单线程写。

[leonhao]

@almas1992 不需要实操，这个问题本质就是排序，先按照去重值排序，再按照行号排序输出结果。大数据领域很多性能测试就是按照排序来测得。https://spark.apache.org/news/spark-wins-daytona-gray-sort-100tb-benchmark

[jsjscool]

Merge sort + 多线程 就是专门解决这个问题的，几行代码的事情，别绕进去了。

[ignor]

几行代码就能搞定的，能否写两行出来秀一下？不是信不过你啊，就是想让大家开开眼界

[kneo]

有些人真是张口就来啊。一台机器 256G 内存，排序 6T 数据，spark ？还“不需要实操”，真敢“云”。

[securityCoding]

@kneo #20 你跑 spark 只有一台机器么...

[kneo]

@securityCoding 兄弟，你回去看看原 OP 的需求。需求是有限资源下对数据去重，不是无限资源跑 spark 。说几行 sql 跑个 spark 就能解决的那个是来搞笑的。

[securityCoding]

@kneo #22 从工程角度来看确实得用 spark 跑

[kneo]

@securityCoding 实事求是才能谈工程的角度。

[noparking188]

@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

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

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

[NoobPhper]

啊 看上去这个 需求相对简单, 可以自己撸一个简单的 mapreduce. 来控制资源, 没必要引一堆东西

[buster]

1. 先给一行加个行号
2. 数据太多其实可以根据每一行的前缀先做一次数据拆分，例如取前 5 个字符
3. 较小数据集并行处理，bitmap ，md5+hashset ，再或者直接内存排序好了。
4. 去除完重复，最后归并

[wxf666]

@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

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

[tool2dx]

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

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

可以多层 hash ，比如 sha1 冲突后，再计算一次 sha256 。如果再冲突一次，就只能两两比较了，不过估计这种情况不多。

[securityCoding]

@kneo #24 也不是，我工作中倒是经常用 spark 洗推荐系统的样本数据，有时候上百 T