[单个 6.2TB 203 亿行 的超大 csv 文件保持顺序的情况下去重]的两个解决方案

查看 80|回复 9
作者:heguangyu5   
详细需求及讨论见 帖 1 和 帖 2.
这是个很有意思的问题,我认真思考和尝试了两三天,找到了两个解决方案.
可执行程序及简单说明见 github 6.2TB-20.3B-dedup.
由于没有合适的硬件条件,因此没有做全量 203 亿数据的测试,仅测试了 20 亿行.
测试步骤:
[ol]

  • ./gen-20.3B-lines.sh > 20.3B.txt
    生成测试数据, 可修改脚本第 3 行 B=203 为你想要的数据量

  • ./dedup-use-more-mem /path/to/20.3B.txt lines
    lines 的单位是亿行,比如要测试 20 亿行,那就是 ./dedup-use-more-mem 20.3B.txt 20
    这个解决方案处理 203 亿行数据需要内存约 272GB,超出了但是很接近原帖的要求.

  • ./dedup-use-less-mem /path/to/20.3B.txt lines
    用法同上,但是这个解决方案用的内存要少一半,所以如果有 256GB 内存,那么处理 203 亿行数据是没问题的.
    [/ol]
    给出的两个可执行程序都是基于 hash 的思路去重的.
    为避免被白嫖,所以只给出了可执行程序,不提供源码,见谅.
  • CodeAllen   
    如果要减少内存使用,可以考虑使用布隆过滤器,缺点就是有误判率。
    203 亿数据规模,按照误判率 0.1%计算,布隆过滤器大约需要 22.83 GB 的内存------GPT4o 。
    如果能容忍更大的误判率内存需求可以继续减少。
    jurassic2long   
    添加一个行号,直接大数据那一套,group by 就行了
    picone   
    1. 可以给出一点大概的思路和手段吗,不然这像是炫耀贴没有任何实质意义
    2. 能有证明内存和处理行数是线性关系吗,不然不能直接得出 203 亿行就是 272GB 内存
    3. 处理时间也是重要的指标,有相关的 benchmark 吗?
    tool2dx   
    hash 去重不难,我估计 gpt4 也能把代码写出来,就是看怎么特定优化内存占用。
    0o0O0o0O0o   
    V2EX 自己的 1brc
    ShuWei   
    磁盘、内存、时间的平衡游戏而已,提出用一堆中间件的人,我表示很费解,搞得谁不知道有那些中间件一样的,提出问题的人,应该是希望不借助外部工具来解决这个问题吧
    分块、哈希、归并去重,过程中使用一些小技巧,应该是最通用的解决方案了,像 op 这样,中间控制一下参数,从而控制资源的使用,就已经能达到目标了,如果需要更精确更优的解决方案,恐怕还得依赖于更精确的基础条件设置
    heguangyu5
    OP
      
    @picone
    1. 思路就是基于 hash 去重的.
    2/3. 可执行程序在那里,你可以自己 down 回来试一下.我给的内存用量和处理时间(20 亿以内)是实测数据,不是拍脑袋粗估的.
    stiangao   
    看情况分词生成倒排索引文件,递归生成索引文件直到能加载进内存处理,然后顺序的加载所有索引文件去比较
    heguangyu5
    OP
      
    @ShuWei 是的,简单的 hashtable 就能解决,前提是仔细思考问题本身和操控计算资源.
    您需要登录后才可以回帖 登录 | 立即注册

    返回顶部