共计 1392 个字符,预计需要花费 4 分钟才能阅读完成。
原帖在 这里. 具体的需求如下:
- 行数是 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,不知道具体的分区消耗多少内存以及读取性能和处理性能,无法给出具体的可行性能答案。