fast_rsync
A faster implementation of librsync in pure Rust, using SIMD operations where available. Note that only the legacy MD4 format is supported, not BLAKE2.
SIMD is currently supported on x86, x86-64, and aarch64 targets.
The rsync algorithm
This crate offers three major APIs:
Signature::calculate
, which takes a block of data and returns a "signature" of that data which is much smaller than the original data.diff
, which takes a signature for some block A, and a block of data B, and returns a delta between block A and block B. If A and B are "similar", then the delta is usually much smaller than block B.apply
, which takes a block A and a delta (as constructed bydiff
), and (usually) returns the block B.
These functions can be used to implement an protocol for efficiently
transferring data over a network. Suppose hosts A and B have similar versions
of some file foo
, and host B would like to acquire A's copy.
- Host B calculates the
Signature
offoo_B
and sends it to A. This is cheap because the signature can be 1000X smaller thanfoo_B
itself. (The precise factor is configurable and creates a tradeoff between signature size and usefulness. A larger signature enables the creation of smaller and more precise deltas.) - Host A calculates a
diff
from B's signature andfoo_A
, and sends it toB
. - Host B attempts to
apply
the delta tofoo_B
. The resulting data is probably (*) equal tofoo_A
.
(*) Note the caveat. fast_rsync
signatures use the insecure MD4 algorithm.
Therefore, you should not trust that diff
will produce a correct delta. You
must always verify the integrity of the output of apply
using some other
mechanism, such as a cryptographic hash function like SHA-256.
Benchmarks
These were taken on a noisy laptop with a Intel(R) Core(TM) i7-6820HQ CPU @ 2.70GHz
. The source code is available in benches/rsync_bench.rs
.
Signature computation
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
is substantially faster than librsync
at calculating signatures,
thanks to SIMD optimizations. The benchmark processor has AVX2 and sees a 6X
speedup. Processors with only SSE2 (or with less fully-featured AVX) see a
smaller speedup, about 3-4X.
Note that fast_rsync
will detect available vector extensions at runtime and
use them as appropriate; -C target-cpu
is not required.
Computing deltas
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]
When comparing similar files, fast_rsync
is mostly bound by the speed of
single-block MD4 hashing, so it is not much faster than 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]
When comparing completely different files, fast_rsync
is mostly bound by the
speed of hashmap lookups. Here, fast_rsync
enjoys a slight advantage because
of Rust's fast built-in HashMap
implementation.
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
is able to detect pathological cases that involve many checksum
collisions. Note that the 4MB version of the benchmark is prohibitively slow
for librsync
and so its result is not listed.
Applying deltas
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]
Applying deltas is quite straightforward and in any case is unlikely to be a
bottleneck, but fast_rsync
's implementation, which is specialized for
in-memory buffers, enjoys a mild speedup.
Contributing
Pull requests are welcome! We ask that you agree to Dropbox's Contributor License Agreement for your changes to be merged.
License
This project is licensed under the Apache-2.0 license.
Copyright (c) 2019 Dropbox, Inc.
Copyright (c) 2016 bacher09, Artyom Pavlov (RustCrypto/hashes/MD4).