fast_rsync

文档

纯 Rust 实现的 librsync 加速版本，在可用时使用 SIMD 操作。注意，仅支持传统的 MD4 格式，不支持 BLAKE2。

SIMD 当前支持 x86、x86-64 和 aarch64 目标。

rsync 算法

此 crate 提供三个主要 API

1. Signature::calculate，它接受一块数据并返回该数据的“签名”，该签名比原始数据小得多。
2. diff，它接受某个块 A 的签名和一块数据 B，并返回块 A 和块 B 之间的差异。如果 A 和 B “相似”，则差异通常比块 B 小得多。
3. apply，它接受一个块 A 和一个差异（由 diff 构建），并（通常）返回块 B。

这些函数可以用于实现一个高效传输数据的协议。假设主机 A 和 B 有某些文件的相似版本 foo，而主机 B 想要获取 A 的副本。

1. 主机 B 计算 foo_B 的 Signature 并将其发送到 A。这很便宜，因为签名可以比 foo_B 本身小 1000 倍。（精确系数是可配置的，并创建签名大小和有用性之间的权衡。较大的签名可以创建更小、更精确的差异。）
2. 主机 A 根据 B 的签名和 foo_A 计算差异，并将其发送到 B。
3. 主机 B 尝试将差异应用到 foo_B 上。得到的数据可能等于 foo_A。（*）

(*) 注意警告。 fast_rsync 签名使用不安全的 MD4 算法。因此，您不应相信 diff 会产生正确的差异。您必须始终使用其他机制（如 SHA-256 这样的加密散列函数）来验证 apply 输出的完整性。

基准测试

这些基准测试是在一个嘈杂的笔记本电脑上进行的，该笔记本电脑配备了 Intel(R) Core(TM) i7-6820HQ CPU @ 2.70GHz。源代码位于 benches/rsync_bench.rs。

签名计算

calculate_signature/fast_rsync::Signature::calculate/4194304
                        time:   [1.0639 ms 1.0696 ms 1.0775 ms]
                        thrpt:  [3.6253 GiB/s 3.6519 GiB/s 3.6716 GiB/s]
calculate_signature/librsync::whole::signature/4194304
                        time:   [5.8013 ms 5.8521 ms 5.9235 ms]
                        thrpt:  [675.28 MiB/s 683.51 MiB/s 689.50 MiB/s]

fast_rsync 由于 SIMD 优化，在计算签名方面比 librsync 快得多。基准测试处理器具有 AVX2，速度提升了 6 倍。仅具有 SSE2（或具有较少功能的 AVX）的处理器速度提升较小，大约为 3-4 倍。

请注意，fast_rsync 将在运行时检测可用的向量扩展，并根据需要使用它们；不需要 -C target-cpu。

计算差异

diff (64KB edit)/fast_rsync::diff/4194304
                        time:   [6.8681 ms 7.0596 ms 7.1953 ms]
diff (64KB edit)/librsync::whole::delta/4194304
                        time:   [7.4044 ms 7.4649 ms 7.5222 ms]

在比较相似文件时，fast_rsync 主要受单个块 MD4 哈希速度的限制，因此它并不比 librsync 快多少。

diff (random)/fast_rsync::diff/4194304
                        time:   [37.779 ms 38.317 ms 38.607 ms]
diff (random)/librsync::whole::delta/4194304
                        time:   [41.983 ms 42.758 ms 43.259 ms]

在比较完全不同的文件时，fast_rsync 主要受 hashmap 查找速度的限制。在这里，由于 Rust 的快速内置 HashMap 实现，fast_rsync 享有轻微的优势。

diff (pathological)/fast_rsync::diff/16384
                        time:   [6.0792 ms 6.2550 ms 6.3666 ms]
diff (pathological)/librsync::whole::delta/16384
                        time:   [50.082 ms 50.185 ms 50.376 ms]
diff (pathological)/fast_rsync::diff/4194304
                        time:   [32.690 ms 32.986 ms 33.171 ms]

fast_rsync 能够检测涉及许多校验和冲突的病态情况。请注意，基准测试的 4MB 版本对于 librsync 来说速度太慢，因此其结果未列出。

应用差异

apply/fast_rsync::apply/4194304
                        time:   [276.17 us 284.20 us 293.37 us]
apply/librsync::whole::patch/4194304
                        time:   [394.21 us 400.30 us 408.79 us]

应用差异相当直接，在任何情况下都不太可能成为瓶颈，但针对内存缓冲区优化的 fast_rsync 实现仍然获得了一些速度提升。

贡献

欢迎提交拉取请求！我们要求您同意 Dropbox 的贡献者许可协议，以便合并您的更改。

许可证

本项目采用 Apache-2.0 许可证。

版权（c）2019 Dropbox，Inc。
版权（c）2016 bacher09，Artyom Pavlov（RustCrypto/hashes/MD4）。