V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
• 请不要在回答技术问题时复制粘贴 AI 生成的内容
heguangyu5
V2EX  ›  程序员

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

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

    详细需求及讨论见 帖 1帖 2.

    这是个很有意思的问题,我认真思考和尝试了两三天,找到了两个解决方案.

    可执行程序及简单说明见 github 6.2TB-20.3B-dedup.

    由于没有合适的硬件条件,因此没有做全量 203 亿数据的测试,仅测试了 20 亿行.

    测试步骤:

    1. ./gen-20.3B-lines.sh > 20.3B.txt

      生成测试数据, 可修改脚本第 3 行 B=203 为你想要的数据量

    2. ./dedup-use-more-mem /path/to/20.3B.txt lines

      lines 的单位是亿行,比如要测试 20 亿行,那就是 ./dedup-use-more-mem 20.3B.txt 20

      这个解决方案处理 203 亿行数据需要内存约 272GB,超出了但是很接近原帖的要求.

    3. ./dedup-use-less-mem /path/to/20.3B.txt lines

      用法同上,但是这个解决方案用的内存要少一半,所以如果有 256GB 内存,那么处理 203 亿行数据是没问题的.

    给出的两个可执行程序都是基于 hash 的思路去重的.

    为避免被白嫖,所以只给出了可执行程序,不提供源码,见谅.

    22 条回复    2024-06-09 00:18:30 +08:00
    CodeAllen
        1
    CodeAllen  
       200 天前
    如果要减少内存使用,可以考虑使用布隆过滤器,缺点就是有误判率。
    203 亿数据规模,按照误判率 0.1%计算,布隆过滤器大约需要 22.83 GB 的内存------GPT4o 。
    如果能容忍更大的误判率内存需求可以继续减少。
    jurassic2long
        2
    jurassic2long  
       200 天前   ❤️ 1
    添加一个行号,直接大数据那一套,group by 就行了
    picone
        3
    picone  
       200 天前
    1. 可以给出一点大概的思路和手段吗,不然这像是炫耀贴没有任何实质意义
    2. 能有证明内存和处理行数是线性关系吗,不然不能直接得出 203 亿行就是 272GB 内存
    3. 处理时间也是重要的指标,有相关的 benchmark 吗?
    tool2dx
        4
    tool2dx  
       200 天前
    hash 去重不难,我估计 gpt4 也能把代码写出来,就是看怎么特定优化内存占用。
    0o0O0o0O0o
        5
    0o0O0o0O0o  
       200 天前 via iPhone
    V2EX 自己的 1brc
    ShuWei
        6
    ShuWei  
       200 天前
    磁盘、内存、时间的平衡游戏而已,提出用一堆中间件的人,我表示很费解,搞得谁不知道有那些中间件一样的,提出问题的人,应该是希望不借助外部工具来解决这个问题吧

    分块、哈希、归并去重,过程中使用一些小技巧,应该是最通用的解决方案了,像 op 这样,中间控制一下参数,从而控制资源的使用,就已经能达到目标了,如果需要更精确更优的解决方案,恐怕还得依赖于更精确的基础条件设置
    heguangyu5
        7
    heguangyu5  
    OP
       200 天前
    @picone

    1. 思路就是基于 hash 去重的.
    2/3. 可执行程序在那里,你可以自己 down 回来试一下.我给的内存用量和处理时间(20 亿以内)是实测数据,不是拍脑袋粗估的.
    stiangao
        8
    stiangao  
       200 天前
    看情况分词生成倒排索引文件,递归生成索引文件直到能加载进内存处理,然后顺序的加载所有索引文件去比较
    heguangyu5
        9
    heguangyu5  
    OP
       200 天前
    @ShuWei 是的,简单的 hashtable 就能解决,前提是仔细思考问题本身和操控计算资源.
    wxf666
        10
    wxf666  
       200 天前
    有点感兴趣,问一下楼主:

    1. 楼主硬盘读写速度多少?

    2. 可以指定限制多少内存完成吗?

    3. 有不同的两行,恰好 hash 相同,会出问题吗?

    4. 除顺序读一次原文件外,还需要额外读写多少文件吗?

    5. 能轻而易举改造成,针对 CSV 文件(可能有字符串跨多行),且现有成绩影响不大,是吗?
    Keuin
        11
    Keuin  
       200 天前   ❤️ 3
    一行 shell 的事被你搞得这么复杂,6TB 可以存内存里,6PB 呢?
    看不下去了,这个源码也不愿意给,我直接给出结论:
    ```shell
    awk '{print $0","NR}' input.csv | sort | sed -E 's/,[0-9]+$//' | uniq
    ```
    其中 input.csv 替换成你的输入文件,结果将出现在 stdout ,如果要存到文件,自己重定向一下即可。
    运行实例:
    ```
    $ cat input
    1,2,3,4
    2,3,4,5
    3,4,5,6
    4,5,6,7
    2,3,4,5
    1,2,3,4
    5,6,7,8
    $ awk '{print $0","NR}' input
    1,2,3,4,1
    2,3,4,5,2
    3,4,5,6,3
    4,5,6,7,4
    2,3,4,5,5
    1,2,3,4,6
    5,6,7,8,7
    $ awk '{print $0","NR}' input | sort
    1,2,3,4,1
    1,2,3,4,6
    2,3,4,5,2
    2,3,4,5,5
    3,4,5,6,3
    4,5,6,7,4
    5,6,7,8,7
    $ awk '{print $0","NR}' input | sort | sed -E 's/,[0-9]+$//'
    1,2,3,4
    1,2,3,4
    2,3,4,5
    2,3,4,5
    3,4,5,6
    4,5,6,7
    5,6,7,8
    $ awk '{print $0","NR}' input | sort | sed -E 's/,[0-9]+$//' | uniq
    1,2,3,4
    2,3,4,5
    3,4,5,6
    4,5,6,7
    5,6,7,8
    ```

    不管你的电脑内存是 1T 还是 1G ,都可以正确运行并得到相同输出,因为 sort 命令用的是归并排序,是外存算法。如果你要限制用到的内存大小,把 sort 改成 sort --buffer-size=100M ,即可限制只用 100M 内存,其他命令都是行缓存算法,只会保存当前行在内存里,也就是说,最大内存用量是 max(100M, max_line_size_bytes)
    wxf666
        12
    wxf666  
       200 天前
    @Keuin #11 原帖还要求,保持文本原有顺序诶。。

    分块归并排序确实好用,我在原帖也手撸了一个,i5-8250U 每分钟能排序 25 GB 。但读写量还是太大了。。

    换成只写入 MD5/SHA-1 值的话,读写量能减少 95%。代价就是有极小概率会哈希冲突。。

    但也能通过回原文件比较两行解决。代价就是可能会有不少的随机读,和重复行数量成正比。。
    heguangyu5
        13
    heguangyu5  
    OP
       200 天前
    @wxf666

    1. 楼主硬盘读写速度多少?

    4 块 4TB 西数机械硬盘做 RAID 0,读写速度可能在 200~400M/s?不太确定.
    gen-20.3B-lines.sh 生成 6.8TB 数据用了 7 个多小时.

    2. 可以指定限制多少内存完成吗?

    dedup-use-more-mem 每 1 亿行数据需要 1.34GB 内存,N 亿就是 N*1.34,当然还需要留出几个 G 的内存给操作系统正常运行.
    dedup-use-less-mem 每 1 亿行数据需要 0.67GB 内存.203 亿 136GB 就够了,所以完成 6.2TB-203 亿去重 150G 内存足够了.


    3. 有不同的两行,恰好 hash 相同,会出问题吗?

    hashtable 就是普通意义的那个,比例 php 的 array,其它语言里的 map, dict 什么的,hash 当然会冲突,这时要解决冲突,常见的解决冲突办法是单链表.所以结果是精确的,不会有误判率什么的.


    4. 除顺序读一次原文件外,还需要额外读写多少文件吗?

    dedup-use-more-mem 始终都在读原文件.

    dedup-use-less-mem 需要额外借助其它文件的帮助.


    5. 能轻而易举改造成,针对 CSV 文件(可能有字符串跨多行),且现有成绩影响不大,是吗?

    可以的.现在是按\n 取一行的,可以换成其它逻辑.
    heguangyu5
        14
    heguangyu5  
    OP
       200 天前
    @Keuin 请仔细看下原贴,原 OP 已经说了 "尝试过的方案有 sort | uniq 会卡死不出结果"
    heguangyu5
        15
    heguangyu5  
    OP
       200 天前
    @wxf666

    2. 可以指定限制多少内存完成吗?

    需要的内存是和要处理的数据量成正比的,如果内存不够,那就无法完成.

    当然要在内存不够的情况下完成,那就是另一个解法了,耗时可能会很长,我一开始尝试了一个方案,因为无法较准确的预估处理完所需要的时间,所以就放弃了.

    现在的这两个方案处理时间是可靠的,可等的,dedup-use-less-mem 可在约 10 小时左右的时间处理完 203 亿,一个晚上就能得出结论.
    heguangyu5
        16
    heguangyu5  
    OP
       200 天前
    @Keuin 原 OP 也说了要尝试一下你的加行号方案,期待结果
    harmless
        17
    harmless  
       199 天前 via iPhone
    不提供实现思路,鉴定炫耀帖
    Keuin
        18
    Keuin  
       199 天前
    @wxf666 昨天写的马虎,忘记顺序这个要求了,我其实又回复了一次来 update ,不过看起来楼被 v 站吞了。保序的方案是用 sort -u -k1,4 来只按原内容排序并去重,最后 sed 去掉行号,最最后的 uniq 去掉即可
    wxf666
        19
    wxf666  
       199 天前
    @Keuin #18 你是说,类似这样吗?

    awk '{print NR" "$0}' in.txt | sort -u -k2 | sort -n | cut -d' ' -f 2-

    感觉写入量翻倍。。而且很难扩展到(可能跨多行的) csv ?


    @heguangyu5 #13

    1. 平均下来,每行花费 14.4 字节内存,肯定没存原字符串。

    hash 冲突时,你要回源文件,具体比较两行吗?那随机读会不会很多。。

    换句话说,随机生成 1E 行,又把这 1E 行打乱,追加到原文件。dedup-use-more-mem 会随机读 1E 次吗?

    2. dedup-use-less-mem 需要额外写多大文件呢?有多少次随机读写呢?这个支持流式读源文件吗?
    Keuin
        20
    Keuin  
       199 天前
    @wxf666 自己研究一下吧,昨天的楼被删了,我懒得再写一遍了,只需要假定 csv 列数固定,不需要用到 cut 。如果假定不了,简便起见,需要找一个输入里面没有的分隔符。
    写入量的话,我在原 po 主帖子里分析过,不过那里把加行号的中间结果也全部存下来了,所以当时给的磁盘用量是 3*6TB 。如果都用流式传递中间结果的话,两个 sort 需要有 2*6TB 的临时空间。
    heguangyu5
        21
    heguangyu5  
    OP
       199 天前
    @wxf666 这两个解决方案都是基于 hashtable 去重的,就是那个普通意义的 hashtable,没有什么花招,所以你的猜想都对.

    hash 冲突了,就是要回源文件比较原始行,随机读有可能会很多.

    但是如果能提前知晓数据的大致分布情况,可能会有更恰当的解决办法.

    在不知道的情况下,这两个方案可以快速试错,然后找到正确的方向.
    wxf666
        22
    wxf666  
       199 天前
    @Keuin #20 写入量还是太大了。我手撸,只写一遍,都觉得大。。

    换成算 SHA-1 ,最差情况,只需要写 203e8 * (20 + 6 该行偏移量) / 2 ^ 30 = 492 GB 即可。

    当然,自己写肯定不如久经考验的工具成熟稳定,第一次花的时间精力也多。。



    @heguangyu5 #21 C/C++ 新人,看了下排行前三的 HashTable ,感觉每行只需 11 字节即可?

    6 字节原始文件偏移量 + 5 字节与原始位置的距离( unordered_dense )或下一节点数组下标( emhash )?

    狠一点儿,ceil(log2(6.20 * 2^40)) - 1 + ceil(log2(203e8)) = 77 bits / 行?总共需 182 GB 即可?

    剩下几字节,你用来存啥了呢。。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5374 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 06:47 · PVG 14:47 · LAX 22:47 · JFK 01:47
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.