V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
lsk569937453
V2EX  ›  程序员

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

  •  
  •   lsk569937453 · 153 天前 · 2813 次点击
    这是一个创建于 153 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    • 行数是 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 ,不知道具体的分区消耗多少内存以及读取性能和处理性能,无法给出具体的可行性能答案。

    30 条回复    2024-06-07 20:57:43 +08:00
    sampeng
        1
    sampeng  
       153 天前   ❤️ 1
    分治法反而是成本最低的。并没限制时间一定要用最快时间。要加快磁盘吞吐也有很多办法。
    kneo
        2
    kneo  
       153 天前 via Android   ❤️ 4
    布隆过滤器就不要再提了吧。以丢失两亿/两千万条数据的代价去重?
    tool2dx
        3
    tool2dx  
       153 天前
    精确去重,最后还是要建立 hash 。

    而根据生日悖论计算,你必须要一个足够大的 hash function 结果值,才能把 203 亿的冲突概率,控制在一定范围内。
    drymonfidelia
        4
    drymonfidelia  
       153 天前
    原帖是我发的,尝试过的方案有 sort | uniq 会卡死不出结果
    布隆过滤器会丢失数据,肯定是不行的
    其它的方案我们都没操作经验,目前打算用 76 楼的加行号方案,看起来最靠谱。
    james122333
        5
    james122333  
       153 天前 via Android
    为何要另外发?...
    james122333
        6
    james122333  
       153 天前 via Android
    @drymonfidelia

    76 楼...
    dapang1221
        7
    dapang1221  
       153 天前
    Clickhouse 的位图?不知道每行数据是不是规律,能不能映射过去,哎呀 6.2T ,我这辈子都没接触过这么大的……
    ignor
        8
    ignor  
       153 天前 via Android
    这么大的数据量,hash 冲突也是个不小的麻烦吧?
    psyer
        9
    psyer  
       153 天前 via Android
    上 PySpark 试试?
    james122333
        10
    james122333  
       153 天前 via Android
    @ignor

    所以可以试试我讲的消秏最小资源解
    leonhao
        11
    leonhao  
       153 天前
    典型的 Spark 应用场景,几行 SQL 的事情,搞这么复杂
    realpg
        12
    realpg  
       153 天前
    这种东西 一般不需要考虑性能 只需要操作简单 结果不要二次操作就好
    almas1992
        13
    almas1992  
       153 天前
    @leonhao 你实操过?
    me1onsoda
        14
    me1onsoda  
       153 天前
    这么大文件怎么读取?
    Vegetable
        15
    Vegetable  
       153 天前
    你对时间的评估与我的认知有一些偏差。
    因为我做过手机号全量 md5 排序,这也是 40 多亿的数据,我印象中跑一遍 md5 再排序,用时应该在小时级别。在此基础上去重回写到原文件可能涉及到再次排序,整个时间可能是我那套逻辑的 10(多一次排序×5 倍数量级)倍左右。我肯定没花到 7 小时。
    lsk569937453
        16
    lsk569937453  
    OP
       153 天前
    @Vegetable 单线程流式读文件、多线程 seek 读文件、mmap 。这三种读法的性能不一样。写也是一样。我上文的读文件都是单线程流式读,写的话也是单线程写。
    leonhao
        17
    leonhao  
       153 天前
    @almas1992 不需要实操,这个问题本质就是排序,先按照去重值排序,再按照行号排序输出结果。大数据领域很多性能测试就是按照排序来测得。https://spark.apache.org/news/spark-wins-daytona-gray-sort-100tb-benchmark
    jsjscool
        18
    jsjscool  
       153 天前
    Merge sort + 多线程 就是专门解决这个问题的,几行代码的事情,别绕进去了。
    ignor
        19
    ignor  
       153 天前 via Android
    几行代码就能搞定的,能否写两行出来秀一下?不是信不过你啊,就是想让大家开开眼界
    kneo
        20
    kneo  
       153 天前
    有些人真是张口就来啊。一台机器 256G 内存,排序 6T 数据,spark ?还“不需要实操”,真敢“云”。
    securityCoding
        21
    securityCoding  
       152 天前
    @kneo #20 你跑 spark 只有一台机器么...
    kneo
        22
    kneo  
       152 天前
    @securityCoding 兄弟,你回去看看原 OP 的需求。需求是有限资源下对数据去重,不是无限资源跑 spark 。说几行 sql 跑个 spark 就能解决的那个是来搞笑的。
    securityCoding
        23
    securityCoding  
       152 天前
    @kneo #22 从工程角度来看确实得用 spark 跑
    kneo
        24
    kneo  
       152 天前 via Android
    @securityCoding 实事求是才能谈工程的角度。
    noparking188
        25
    noparking188  
       152 天前
    @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
        26
    NoobPhper  
       152 天前
    啊 看上去这个 需求相对简单, 可以自己撸一个简单的 mapreduce. 来控制资源, 没必要引一堆东西
    buster
        27
    buster  
       152 天前
    1. 先给一行加个行号
    2. 数据太多其实可以根据每一行的前缀先做一次数据拆分,例如取前 5 个字符
    3. 较小数据集并行处理,bitmap ,md5+hashset ,再或者直接内存排序好了。
    4. 去除完重复,最后归并
    wxf666
        28
    wxf666  
       150 天前
    @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
        29
    tool2dx  
       150 天前
    @wxf666 "精确去重,不应该是每行两两比较吗?

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

    可以多层 hash ,比如 sha1 冲突后,再计算一次 sha256 。如果再冲突一次,就只能两两比较了,不过估计这种情况不多。
    securityCoding
        30
    securityCoding  
       150 天前
    @kneo #24 也不是,我工作中倒是经常用 spark 洗推荐系统的样本数据,有时候上百 T
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1233 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 18:17 · PVG 02:17 · LAX 10:17 · JFK 13:17
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.