The rsync algorithm

The chapter of the basic course “The parliament of Paxos” (in its Russian version) was edited five times over two days: a style pass, non-breaking spaces, a fact check, one word, a shorter description. Each time the new version, about 97 KB, had to reach the server where the previous one lay. How many bytes need to be sent for that? Below are all five edits as rsync would send them, and one more for comparison: a picture that was simply saved again.

Choose “a shorter description”. At the very start of the chapter the description became 102 bytes shorter, and everything after it shifted. If blocks are compared only at their old places (“a block only in its place”), one block in 140 matches, and more than the whole file has to be sent: the block sums are added to the new bytes. rsync finds 139 blocks out of 140, at new places, 102 bytes to the left, and sends 4 KB, of which 598 bytes are new. And the picture, almost unchanged to the eye, goes in full: of the old version nothing was found in the new one except one block in the file header.

The idea

The receiver cuts its old version into blocks of B bytes and sends two checksums for each: a weak one, 4 bytes, and a strong one, 16 bytes. The sender rolls a window of length B along the new version, shifting it a byte at a time, and at each place asks: is there a block with this weak sum? The window’s weak sum is recomputed in O(1) on a shift, so checking all offsets costs O(n), not O(n·B). If the weak sum matches, compare the strong one. If that matches too, send the block number and jump B bytes; otherwise the byte goes as it is and the window shifts by one.

The problem rsync solves differs from the one diff solves. To find the difference between two files, both files are needed on one machine. Here the files are on different machines, and the link between them is the most expensive part: sending the old version to the new one for comparison means sending the whole file, exactly what we wanted to avoid. The block sums are a compressed description of the old version: 20 bytes per 700, 35 times smaller than the file itself.

Why not compare blocks at their places, the first with the first, the second with the second? Because edits shift the text. Insert a word at the start, and every byte after it is at a different offset, although the content is the same. The old version’s blocks must be searched for in the new one at any place, and that is exactly what the rolling sum does.

A sum that rolls

rsync’s weak sum is a pair of 16-bit numbers. For a window of bytes x_k, …, x_l:

a is just the sum of the bytes, b a weighted sum: the window’s first byte counts L times, the last once, where L = l − k + 1 is the window length. When the window shifts by a byte, x_k leaves and x_l+1 arrives:

The second formula becomes clear if you write out the weights. The departing byte weighed L, so it is subtracted. The other bytes of the window lose one unit of weight each (they are one position “older”), which is the same as subtracting their sum once more; and adding the new a, in which the new byte is already counted with weight 1, gives each byte back one unit of weight. In the end the old bytes keep their previous weights relative to the end of the window, and the new one gets weight 1. Check it on the chapter’s title: an eight-byte window rolls along the line, and after each shift both sums computed by the formulas match those computed afresh.

The report in which rsync was first described says that this sum was modelled on Mark Adler’s Adler-32 checksum, which also adds up bytes and sums of sums. Why a second sum? a alone does not see the order of bytes: “dog” and “god” give the same value. In the chapter’s text the bytes are distributed similarly from window to window, and the sums of 700 bytes fall into a narrow range. The listing counts: if rsync checked only a, the weak sum would have fooled it 88 times on the fact-check edit. The pair (a, b) did not fool it once.

The weak sum is only a filter. It is cheap and easy to forge on purpose, so a match is confirmed by the strong one: MD4 in the first version of rsync, MD5 and xxHash in the current one. It is computed only when the weak sum has matched, and on real files these are almost always real matches. The search in the 1996 paper has three stages: a 16-bit hash of the weak sum points to a row of a table of 2¹⁶ rows, an exact match of the 32-bit weak sum is sought in it, and only then is the strong sum compared.

The rolling sum was not invented by rsync. The polynomial hash, which also shifts in O(1), underlies Rabin–Karp substring search, and such hashes are covered in detail in the article on the polynomial hash. rsync’s sum has another merit: it is simpler and faster, and the strong sum makes up the reliability.

Code

The listing repeats the scene’s experiment: for each of the five edits it builds the block sums of the old version, rolls the window along the new one, assembles the new version from the old one and the pieces sent, and checks that it matches byte for byte. The accounting is honest: one way, 20 bytes of sums per block; the other, 4 bytes per block number and per length of each piece of new bytes, plus the bytes themselves.

The table of edits from the listing:

The last column is how many blocks would be found if they were compared only at their old places. In the “one word” edit «тысячи» (thousands) became «сто тысяч» (a hundred thousand) near the end of the chapter: everything before that place stayed where it was, 135 blocks, and only the last ones shifted. In all the other edits the length of the text changes right at the start of the chapter, and almost everything after that place shifts.

What it costs

Time. The block sums of the old version are one pass, O(n). The sender does O(1) work and one hash-table lookup at each offset, and computes the strong sum only on a weak match; each real match consumes B bytes, so all the strong sums cost O(m) for a new version of length m. Memory is a table of ⌈n/B⌉ sums.

The network is what matters. The sums weigh s bytes per block, and there are ⌈n/B⌉ of them. Each edit site spoils the block it falls into, and that piece goes as it is, about B bytes. The larger the block, the fewer the sums and the more bytes each edit drags along. The scene below shows this on all five edits.

Let us check on the fact check. The listing counted k = 15 edit sites, the file is 97,323 bytes, s = 20. The formula gives B ≈ 360, and the search in the scene gives a best block of 400 bytes and 12.1 KB over the wire; in the listing, among sizes 100, 200, 300, 500, 700, the best is 300. The estimate 2√(nsk) ≈ 10.8 KB is below the real 12.1 KB: the model ignores the length of the edits themselves, and here some of them are longer than a block. For the style pass there are many edit sites, and the best block is smaller, 200 bytes, while for edits in one or two places it is 1500. An exact search over all sizes is the article’s second problem; it shows that edits coming in clusters push the answer far from the formula.

The real rsync does not search: for files up to 490 KB the block is 700 bytes, for larger ones about √n, a multiple of eight but at most 128 KB. The square root of n is the same estimate with a constant ratio s/k. And its sums are shorter. The strong sum is not sent in full, only as many bytes as are needed for an accidental match to be unlikely for a file of that size: 2 bytes for a 97 KB chapter. With the 4 bytes of the weak sum that is 6 bytes per block instead of 20. If a false match does happen, it is caught by the checksum of the whole file, which the sender sends at the end; then the file is transferred again, this time with full sums.

What else real life needs

• Leaving alone what has not changed. Before computing sums, rsync compares the file’s size and modification time. If they match, the file is skipped altogether. On a directory of thousands of files of which three changed, this is the main saving.
• Not waiting for each other. While the sender searches for the blocks of one file, the receiver is already computing the sums of the next. Both sides work at the same time, and the network latency is paid once rather than per file.
• Compressed files. Compression destroys what rsync relies on. A compressed stream depends on everything before it, and an edit at the start changes all the bytes after it. That is what happened with the picture: JPEG stores not pixels but compressed coefficients (how this works is told in the course chapter on compression). For archives gzip has had the --rsyncable option since version 1.7: it resets the compression state from time to time at places that depend only on the content, and a small edit changes only the piece of the archive near it.
• Compressing what is sent. The new bytes and block numbers can be compressed on the way like an ordinary stream. On text this further cuts the transfer several times.

Where it works

rsync is the standard way to copy a directory to another machine so that a repeated copy sends only the difference: backups, mirrors, deploying sites.

librsync splits the algorithm’s three steps into separate actions: take the signature of the old file, build a delta from the signature and the new file, apply the delta to the old file. The signature and delta can be stored. This is how incremental backups work in the Duplicity program: only deltas go into the archive.

zsync swaps the roles. The block sums of the new version lie in advance on an ordinary web server in a .zsync file, and the client rolls the window, over its own old version, and downloads only the missing pieces over HTTP. The server needs no special program.

Content-defined chunking. Fixed-length blocks are good when one side knows the old version. If common pieces must be found among many files and versions, chunk boundaries are set by the content itself: where the rolling window’s fingerprint satisfies a condition, for example ends in the right number of zero bits. An inserted byte then shifts only the nearest boundary, and the other chunks stay the same. The LBFS network file system (2001) started with this, hashing the window with Rabin fingerprints.

History

Andrew Tridgell and Paul Mackerras described the algorithm in the technical report “The rsync algorithm” in 1996; the rsync program came out at the same time. The report has measurements too: two archives of Linux kernel sources, versions 1.99.10 and 2.0.0, 24 MB each, were synchronised with a 500-byte block by sending about a million bytes of new data, and there were 64 false weak-sum matches for 47 thousand blocks found. A detailed analysis of the algorithm and its improvements went into Tridgell’s 1999 dissertation, “Efficient Algorithms for Sorting and Synchronization”.

Problems

The first problem is the search itself: find the old version’s blocks in the new one at any offset, without huge blocks turning the check of each offset into copying. In the second you must choose the block size exactly rather than by the formula.