原帖在这里.具体的需求如下:
本文只讨论几种可行性的方案。
通过中间件来处理是可行的,无论你是 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 的限制是内存,我们通过这个网站来计算一下所需要的内存。
看样子内存是符合要求了。我们再计算一下所用时间。
单机 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 算法重新分散到不同的文件中,对于文中的需求按照文件顺序,则需要添加行号来用于最后的排序。第 1 ,2 ,3 步都是用单线程进行操作。在我本机 SSD 上测试了一下,处理 1000 万条数据的时间为 2 分钟,大量的时间都花在写文件上。以同样的性能评估 203 亿行的数据执行 1,2,3 的步骤,则所花费的时间为2.9 天。
后续的处理不在赘述,因为 hash 分区重新写文件的时间太久已经明显的不如其他的方案。
答主没有用过 Spark ,不知道具体的分区消耗多少内存以及读取性能和处理性能,无法给出具体的可行性能答案。
1
sampeng 171 天前 1
分治法反而是成本最低的。并没限制时间一定要用最快时间。要加快磁盘吞吐也有很多办法。
|
2
kneo 171 天前 via Android 4
布隆过滤器就不要再提了吧。以丢失两亿/两千万条数据的代价去重?
|
3
tool2dx 171 天前
精确去重,最后还是要建立 hash 。
而根据生日悖论计算,你必须要一个足够大的 hash function 结果值,才能把 203 亿的冲突概率,控制在一定范围内。 |
4
drymonfidelia 171 天前
原帖是我发的,尝试过的方案有 sort | uniq 会卡死不出结果
布隆过滤器会丢失数据,肯定是不行的 其它的方案我们都没操作经验,目前打算用 76 楼的加行号方案,看起来最靠谱。 |
5
james122333 171 天前 via Android
为何要另外发?...
|
6
james122333 171 天前 via Android
|
7
dapang1221 171 天前
Clickhouse 的位图?不知道每行数据是不是规律,能不能映射过去,哎呀 6.2T ,我这辈子都没接触过这么大的……
|
8
ignor 171 天前 via Android
这么大的数据量,hash 冲突也是个不小的麻烦吧?
|
9
psyer 171 天前 via Android
上 PySpark 试试?
|
10
james122333 171 天前 via Android
|
11
leonhao 171 天前
典型的 Spark 应用场景,几行 SQL 的事情,搞这么复杂
|
12
realpg 171 天前
这种东西 一般不需要考虑性能 只需要操作简单 结果不要二次操作就好
|
14
me1onsoda 171 天前
这么大文件怎么读取?
|
15
Vegetable 171 天前
你对时间的评估与我的认知有一些偏差。
因为我做过手机号全量 md5 排序,这也是 40 多亿的数据,我印象中跑一遍 md5 再排序,用时应该在小时级别。在此基础上去重回写到原文件可能涉及到再次排序,整个时间可能是我那套逻辑的 10(多一次排序×5 倍数量级)倍左右。我肯定没花到 7 小时。 |
16
lsk569937453 OP @Vegetable 单线程流式读文件、多线程 seek 读文件、mmap 。这三种读法的性能不一样。写也是一样。我上文的读文件都是单线程流式读,写的话也是单线程写。
|
17
leonhao 171 天前
@almas1992 不需要实操,这个问题本质就是排序,先按照去重值排序,再按照行号排序输出结果。大数据领域很多性能测试就是按照排序来测得。https://spark.apache.org/news/spark-wins-daytona-gray-sort-100tb-benchmark
|
18
jsjscool 171 天前
Merge sort + 多线程 就是专门解决这个问题的,几行代码的事情,别绕进去了。
|
19
ignor 171 天前 via Android
几行代码就能搞定的,能否写两行出来秀一下?不是信不过你啊,就是想让大家开开眼界
|
20
kneo 170 天前
有些人真是张口就来啊。一台机器 256G 内存,排序 6T 数据,spark ?还“不需要实操”,真敢“云”。
|
21
securityCoding 170 天前
@kneo #20 你跑 spark 只有一台机器么...
|
22
kneo 170 天前
@securityCoding 兄弟,你回去看看原 OP 的需求。需求是有限资源下对数据去重,不是无限资源跑 spark 。说几行 sql 跑个 spark 就能解决的那个是来搞笑的。
|
23
securityCoding 170 天前
@kneo #22 从工程角度来看确实得用 spark 跑
|
24
kneo 170 天前 via Android
@securityCoding 实事求是才能谈工程的角度。
|
25
noparking188 170 天前
@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 感觉这是一个工程问题,重在如何优化。 非常希望你能分享下后续,是否解决了,解决方案,感觉很有意思。 |
26
NoobPhper 170 天前
啊 看上去这个 需求相对简单, 可以自己撸一个简单的 mapreduce. 来控制资源, 没必要引一堆东西
|
27
buster 170 天前
1. 先给一行加个行号
2. 数据太多其实可以根据每一行的前缀先做一次数据拆分,例如取前 5 个字符 3. 较小数据集并行处理,bitmap ,md5+hashset ,再或者直接内存排序好了。 4. 去除完重复,最后归并 |
28
wxf666 168 天前
@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 手撸了一个,不知对你有帮助吗? |
29
tool2dx 168 天前
@wxf666 "精确去重,不应该是每行两两比较吗?
但如果能承受极小概率冲突,用哈希应该会快很多。" 可以多层 hash ,比如 sha1 冲突后,再计算一次 sha256 。如果再冲突一次,就只能两两比较了,不过估计这种情况不多。 |
30
securityCoding 167 天前
@kneo #24 也不是,我工作中倒是经常用 spark 洗推荐系统的样本数据,有时候上百 T
|