wxf666

@phrack #15

突然想起来，zram 可能行不通。。

sha1 的结果，是不是相当于随机数据？随机数据，压缩不了啥吧。。

即，256 GB 内存，当不了 512 GB 用？全都用来存压缩比 100% 后的数据了？


@cabbage #57

需要保留 27 行原始 string ，在小根堆里。

第二步目的：检查出各块中，偏移量非最小的重复行，记录进删除名单中。

第二步时，已经有 26.5 个 240GB 的、排序好的块。

参考多路归并，可以流式构造出有序的 (string, offset, chunk_index)。

当 string 与上一个不同时，说明碰到偏移量最小的新行了（即，全文首次出现）。

当 string 与上一个相同时，说明重复行了，此时往 "to_del_${chunk_index}.txt" 里记录 offset 。

（可以攒多点再写，反正只用了 27 个字符串 + 27 * 1GB 缓冲区，还剩 200+GB 内存呢。。）

以前写过类似的，10+ MB 内存去重 13 GB 文件，里面也有用到多路归并：/t/1031275#reply15

36 37 楼，好像没 @ 成功。。再试一下。。


@opengps #3
@msg7086 #32

如果数据库，每秒写入 10W 条，总计要 203e8 / 1e5 / 3600 = 56 小时？


@hbcolorful #17
@NotLongNil #30

用布隆过滤，几十 GB 好像不够。
在线算了下，50 GiB + 15 函数，都会有 1 / 26000 概率出错，大约丢失 80W 行数据？
250 GiB + 11 函数，算完 203 亿行，才能有 83.8% 的概率，不丢失任何数据，也不保留任何重复行？

@dingwen07 #38 是的。37 楼有提及到，用多少哈希函数。


@dode #42

《写入到对应分区下面》这个是缓存尽可能多的文本（如 1GB ），再写入，是吗？
《检索特定行文本，是否在对应分区内存在》这个是如何做到，顺序读的呢？


@tonywangcn #44

平均每十亿条，就误认为一次，某行是重复行，导致丢失该行？
那你要问 @drymonfidelia 愿不愿意丢失几十行数据了。。

@cndenis #14 ，@hbcolorful #17 ，@NotLongNil #30：

用布隆过滤，几十 GB 好像不够。
在线算了下，50 GB + 15 函数，都会有 1 / 25000 概率出错。。
250 GB + 11 函数，算完 203 亿行，才能有 83.8% 的概率，一个不出错？


@phrack #15：

压缩内存，来存 hash ？好像真的可行。。
平均而言，写入 (372 << 30) / 4096 = 1 亿次，就会占满 372 GB 内存页。即，几乎一开始就会启用 zram ？
我在别处看了看，lz4 每秒能有 200W 次 IO ，算下来要 2.8 小时即可？
话说，这个和 Bloom Filter 相比，哪个出错概率小呢？

@dcsuibian #2 ，@opengps #3 ，@msg7086 #32：
如果数据库，每秒写入 10W 条，总计要 203e8 / 1e5 / 3600 = 56 小时？

@YTMartian #26 ，@dode #27：
就算固态 4K 随机读写有 10W IOPS ，算下来也要 56 小时吧？

34 楼纠正下数据，实测轻薄本 i5-8250U ，1.5 秒归并排序 320W 个 336 长度的随机字符串，约 6500W 次比较。

- 多线程快排/归并：总计 6017 亿次比较，我的轻薄本 8 线程需 0.5 小时。
- 单线程小根堆：总计 1910 亿次比较，单线程需 1.2 小时。

差不太远。。

想到个方法，预计耗时：10 小时，准确率：100% 剔除重复行。


## 简单流程

1. 分块排序。
2. 同时循环每块，删掉非首次出现的重复行。
3. 分别循环每块，按行号顺序，输出未被删掉的行。


## 详细流程

1. 分块 240GB 文件，每块排序后，写入固态。同时保存每行长度+原始偏移量（约 (240 << 30) / 335 * 8 / 1024 ^ 3 = 5.7 GB ）。
2. 利用小根堆，流式排序（按 <string, offset> 排）所有分块每一行。非首次出现行，保存该行偏移量，到相应块的删除名单里。
3. 循环每块，排序原始偏移量、删除名单，按序输出（未被删除的）相应行，至最终文件。


## 耗时计算

1. 顺序读写：9 小时（ 3 次顺序读，2 次顺序写，假设都为 1GB/s ）。
2. 内存字符串排序：< 1 小时（实测轻薄本 i5-8250U ，每秒归并排序 200W 次 335 长度的随机字符串，约 6900W 次比较）。
- 多线程快排/归并：`(每块行数 = (240 << 30) / 335) * log2(每块行数) * 块数 = 6017 亿` 次比较，我的轻薄本 8 线程需 0.3 小时。
- 单线程小根堆：`202e8 * log2(块数 = 6.2 * 1024 / 240 = 26.5) * 2 = 1910 亿` 次比较，需 0.7 小时。

@wanghr64 #5 老板：帮我统计该员工认真工作时长？