AlexMelanFromRingo/dedup-giant-files

# Giant Dedup **快速、内存受限的海量文本文件和词表去重。** `dedup_giant_files` 可以移除*任何*大小的文本文件中的重复行——包括远大于 RAM 的文件——它通过使用磁盘哈希分区、内存映射桶以及流式 k 路合并来实现。无论输入包含多少唯一行，峰值内存都保持平稳，因此它既不会在庞大的唯一集合上发生 OOM，也不会在病态的重度重复输入上发生 OOM。 ## 为什么需要另一个去重工具？ 简单的 `sort -u` 需要对整个文件进行排序；哈希集合工具会将每个唯一的行保留在 RAM 中。这两者在处理数百 GB 的词表时都会崩溃。Giant Dedup 的设计使得**峰值内存仅受限于单个分区的工作集**，而不是输入大小或唯一行的数量： - **不会因为高唯一性而 OOM** —— 唯一行被流式传输到输出，永远不会收集到一个巨大的内存向量中。 - **不会因为重度/倾斜的重复而 OOM** —— 分区使用内存映射（基于文件、可回收）而不是读取到堆上，并且去重哈希表是容量受限的，因此重复繁重的桶无法预留巨大的空表。 - **跨核心扩展** —— 分区和每个桶的去重完全并行（Rayon），无共享。 ## 功能 - 在单次处理中**合并多个文件并去重**。 - **`--keep-order`** —— 保留首次出现的顺序（输入文件顺序，然后是行位置）。通过流式 k 路合并实现，因此保持内存受限。 - **`--sort-length`** —— 输出按从短到长排序的唯一行（适用于破解字典），同样通过受限的合并实现。 - **`--buckets N`** —— 调整分区数量（内存/并行度权衡）。 - **跨平台** —— 纯 Rust 编写；使用 `memmap2` 实现可移植的内存映射。 ## 安装 需要最新的 [Rust 工具链](https://rustup.rs/)。 ``` git clone https://github.com/AlexMelanFromRingo/dedup-giant-files cd dedup-giant-files cargo build --release # 位于 ./target/release/dedup_giant_files 的 binary ``` ## 用法 ``` # 基础 deduplication ./target/release/dedup_giant_files wordlist.txt -o cleaned.txt # 合并 + dedup 多个字典 ./target/release/dedup_giant_files dict1.txt dict2.txt dict3.txt -o mega.txt # 保留首次出现顺序（文件顺序，然后是位置） ./target/release/dedup_giant_files priority.txt common.txt -o merged.txt --keep-order # 按长度对 unique 行进行排序（短 → 长） ./target/release/dedup_giant_files massive.txt -o sorted.txt --sort-length # 调整 partition 数量（更多 buckets = 每个 bucket 更小的 working set） ./target/release/dedup_giant_files huge.txt -o out.txt --buckets 1024 ``` | 标志 | 默认值 | 描述 | | :-- | :-- | :-- | | `-o, --output ` | `dedup_out.txt` | 输出路径。 | | `--keep-order` | 关闭 | 保持首次出现的顺序。 | | `--sort-length` | 关闭 | 将唯一行按从短到长排序（平局：按字节顺序）。 | | `--buckets ` | `256` | 磁盘哈希分区的数量。 | ## 工作原理 1. **分区** —— 输入以 64 MB 为块进行流式传输；每一行都被哈希（XXH3）并路由到 *N* 个磁盘桶之一。顺序元数据（`file_idx`, `offset`）**仅**在设置了 `--keep-order` 时写入，否则会将短行的临时磁盘使用量减半。 2. **按桶去重** —— 每个桶都进行内存映射，并使用容量受限的哈希集合（`AHashSet<&[u8]>`）进行去重。桶以并行方式处理。 3. **输出** —— - *默认：* 每个桶将其唯一行直接流式传输到输出； - *有序：* 每个桶写入一个排序后的结果文件，然后**流式 k 路合并**使用每个桶一个缓冲行来生成全局排序的输出。 完整的说明，包括对两种 OOM 失败模式的根本原因分析及修复方法，请参见 [`docs/METHODOLOGY.md`](docs/METHODOLOGY.md)。 ## 内存行为（实测） 在流式重写前后，AMD Ryzen 5 5500 (6C/12T)、WSL2 环境下的峰值**匿名堆**（实际导致 OOM-kill 的内存）： | 场景 | 模式 | 重写前 | 重写后 | | :-- | :-- | --: | --: | | 4000 万唯一行（约 920 MB） | 默认 | 3163 MB | **427 MB** | | 4000 万唯一行（约 920 MB） | `--keep-order` | 4681 MB | **421 MB** | | 1 个热点行 × 3000 万 + 200 万唯一行 | 默认 | （易发生 OOM） | **182 MB** | 重写后，峰值堆内存大致**恒定** —— 它取决于每个桶的工作集和合并缓冲区，而不是唯一行的数量。重写前的设计随着唯一性的增加呈线性增长（在数十亿唯一行时约为 100 GB+）。 ## 生成测试数据 一个辅助二进制程序可以生成用于实验的大型低熵文件： ``` cargo run --release --bin generate_data # writes large_test_file.txt ``` ## 许可证 根据您的选择，采用 [MIT](LICENSE-MIT) 或 [Apache-2.0](LICENSE-APACHE) 双重许可。

标签：Rust, SOC Prime, 内存映射, 可视化界面, 开发工具, 文本去重, 网络流量审计, 通知系统