In phase 1, rsync compares a local modification timestamp against a remote timestamp. Although this works well for the mirroring use-case, meta-data timestamps should generally be avoided in distributed systems.

Consider the case where you first connect to an unknown server. Comparing this server's timestamps against your own doesn't provide useful information. Even if you trust its clock has always been set correctly, exactly when it saved a bit of data doesn't indicate if its saved data is older or newer than your version.

A common protocol for replication is for every server to keep a log of updates it has processed. Every time a client connects, it asks the server for data that has come in since it last checked. While this scheme doesn't depend on clocks to be correct (and in fact, sequence IDs can be used instead of timestamps), it is inefficient in open networks where a client synchronises with many different servers. This is because the same updates will be downloaded from many servers, and when adding a new server, all updates or the full state must be transferred.

In dynamic/chaotic distributed environments, timestamps can become unreliable for many other reasons. Servers can unexpectedly re-build their databases, resetting timestamp meta-data. Multiple servers can be put behind a load balancer and not present consistent timestamps. Due to bugs or operator intervention, modifications can bypass the log and directly update the DB. Servers can be restored from backups, rewinding the logs.

Take-away 1: In a distributed environment, it is preferable for synchronisation methods to use the contents of data elements (or their hashes) to determine equivalence, and not meta-data such as timestamps.

In phase 2, rsync transmits the list of checksums for each chunk in the file. This means that every time a file is synchronised, an amount of data linear in the full file-size must be transferred. To reduce this overhead rsync uses a larger chunk size as the file size increases. However, chunks should not be too large since whenever a difference is detected an entire chunk must be transferred.

In the rsync protocol, the full list of chunks is constructed and transferred in one communication round. If we are willing to relax this, and allow back-and-forth communication, then we can improve on the overhead described above.

Imagine taking the checksum of the full file and transferring that. If it matches, great, we are done. Otherwise, split the file into two chunks, and send a checksum for each. If either of those match the remote chunk, then we have confirmed that this entire half of the file is identical. Whenever there is a difference, recurse until we have an arbitrarily small chunk that can be transferred directly. (This algorithm was in fact proposed in 2001 by John Langford as Multiround rsync, but was never incorporated into the official rsync program).

The divide-and-conquer technique is well known to computer scientists as the basis of binary search, and works well in this case because the bandwidth overhead grows logarithmically (very slowly) with the total file size.

Take-away 2: Using divide-and-conquer, shared sub-sets of records can be identified early-on so that no further synchronisation work needs to be performed on them. If the databases are large, this can save substantial resources such as bandwidth, CPU, and IO.

In order to avoid transferring a potentially large list of checksums like rsync, RBSR uses back-and-forth communication rounds between the protocol participants. Each round tries to find common sub-sets of elements so that processing of these sub-sets can be halted. When one side has determined that the other needs an element, it can be sent immediately (without waiting for the sync to complete).

With RBSR, all the elements to be synchronised are sorted into a particular order. Various ordering criteria can be used, but for now let's just suppose that each element has a unique timestamp and this is what we sort by.

A contiguous (no gaps) sequence of these sorted elements is called a range. Whenever we communicate about our ranges with the outside world, we cannot use the indices of the elements in our sorted list because other protocol participants may have entirely different sets. So, ranges must be specified using lower and upper bounds, which are values that can be compared against elements using the sorting criteria (ie, timestamps).

Let's walk through an example of how RBSR works.

The initiator begins by computing a fingerprint over its full range of elements (from timestamp 0 to timestamp infinity), and sending it to the other remote side. We'll talk about fingerprints in more detail soon, but for now assume they are cryptographic hashes of all the sorted elements within a range.

In our example the two parties share most of the elements in common, except that the initiator (top) is missing one element that the remote side (bottom) has, and the remote side is missing two elements the initiator has:

Once the remote side receives the fingerprint, it computes the fingerprint for its own full range. If they match, then it immediately knows that both sides have identical sets, so it can reply to the initiator that nothing needs to be done, and the protocol can stop.

But in our example this is not the case, since the two sides have different sets. To make further progress, the remote side splits its range into two smaller sub-ranges, computes the fingerprints for each, and sends them along with corresponding bounds back to the initiator:

After receiving these fingerprints, the initiator computes its own fingerprints for each sub-range specified by the remote side. It is important that the receiver uses the exact same range bounds the other side sent rather than blindly split its own range in half (for instance).

In our example, the initiator sees that the first fingerprint matches its own for this range. This is great news, since it means that we have now determined half of the elements are identical and we no longer need to do any processing for them (illustrated by colouring these elements green). However, the second fingerprint indicates that the other sub-range has one or more differences, so we need to recurse further.

Next, the initiator splits the sub-range into two sub-sub-ranges, computes their fingerprints, and sends them to the remote side:

Similar to the previous step, the remote side computes its own fingeprints and determines that one of them is identical: nothing more needs to be done for that range.

Although not strictly required, most RBSR implementations will want to stop splitting ranges once the number of elements they contain becomes sufficiently small. In our example, the remote side decides that it doesn't want to split the 6 elements in the right-most range, so it sends those elements (or their hashes), along with the range boundaries, back to the initiator:

After receiving the set of elements in the range, the initiator immediately knows which elements in this range it has that the other side needs, and vice-versa, simply by comparing these received elements against the elements in its own corresponding range.

The initiator notices that it was missing one element, and adds it to its set (illustrated by colouring blue). It also notices that it has two elements that were not sent by the remote side, so it sends these elements and the remote side adds them to its set:

At this point, the two sets are fully reconciled and the synchronisation is complete.

In the previous diagrams, each pair of fingerprints had one matching and one non-matching fingerprint. But there is a possibility that both sub-ranges will have a difference, and therefore both should be recursed into. For this reason, each message transmission may include multiple ranges and their fingerprints:

Implementations have considerable flexibility when choosing their ranges. Although the descriptions above assumed splitting into evenly sized groups of 2 (or 16), there are various reasons why implementations may choose different divisions:

• Partial syncing: If a client is only interested in syncing particular portions of the data-set, it can create ranges only for those portions. The un-sent ranges will be considered already synced by the protocol and will be ignored. For instance, if records are sorted by timestamp, clients could use this to sync just the latest week's worth of records. Conversely, clients could choose to not synchronise the most recent few seconds to avoid redundant double-downloads if records are also being streamed in real-time.

• Variable sizing: Ranges can be split into more or fewer sub-ranges as the sync progresses. This could be directed by simple heuristics, or dynamically derived according to measured network conditions in order to optimise for a particular point in the bandwidth/latency trade-off space.

• Weighted splitting: In some situations, clients may have reason to believe that certain ranges are more or less likely to be in sync than others. For example, clients who sync with each other relatively often may rely on the fact that old data ranges are likely to be in sync, and therefore that most of the differences will be with recent elements. In this case, ranges that cover recent time periods can be made smaller in order to speculatively pre-partition them and reduce latency without increasing bandwidth usage.

• In order to protect against some attacks on fingerprints, implementations may choose to randomise their range boundaries.

• In order to keep messages acceptably small, ranges can be abbreviated to stay within a frame size limit, postponing their resolution until a later round of the protocol.

Suppose you have the elements A, B, and C and you computed a cryptographic hash (ie SHA-256) of the concatentation of these elements:

h = sha256(A + B + C)

Now you receive a new element D and you'd like to update h to include it. Unfortunately, the only way to do this is to re-compute the hash from scratch using the entire new set:

h' = sha256(A + B + C + D)

With incremental hashing, we can compute the new hash value without having to start again from scratch. A simple incremental hash can be implemented by hashing each individual element and then combining them with bit-wise XOR (⊕):

h = sha256(A) ⊕ sha256(B) ⊕ sha256(C)

Since XOR is associative, we can incrementally add in the new value:

h' = h ⊕ sha256(D)

Most incremental hashes allow you to subtract elements out of the hash too. With XOR, every element is its own inverse so it is as simple as:

h' ⊕ -sha256(D) = h' ⊕ sha256(D) = h

The advantage of using incremental hash functions is that we can use them to reduce the amount of work needed to compute fingerprints by storing elements in a tree data-structure. If an incremental hash function has the properties that make this possible, it is called "tree-friendly" (see Meyer's paper for the exact algebraic requirements).

The most obvious type of tree to use is the B-tree. These trees have large branching factors (many children) because this encourages related data to be stored together, exploiting the locality of reference benefits inherent to most types of storage.

As well as pointers to its children, each node of the tree contains the incremental hash of all elements below it in the tree:

To find an item in the tree, we start at the root node, and traverse down through the levels until we get to a leaf node (path indicated in red below).

If we wanted to compute the hash of all nodes preceding the item we have found (indicated in blue), we could iterate over all the leaf nodes and incrementally hash the elements. However, this would involve loading and processing an amount of elements linear in the DB size, which could be very large:

Fortunately, because nodes store the incremental hashes of all their sub-elements, this is unnecessary. Instead, as we traverse the tree, we can accumulate the tree nodes to the left of the path we traversed, and the elements in the leaf node that precede the element we found:

The result is that only a logarithmic number of hashes need to be incrementally combined.

This operation (computing the incremental hash of preceding elements) can be used to find the incremental hash of any range of elements. Suppose we have the elements 1 through 10, and we want to find the incremental hash of elements in the range [3,5) (in computer science, ranges always include the begin index and exclude the end index). To do so, use the operation two times -- one for each end of the range -- and subtract the results:

(1 + 2 + 3 + 4) - (1 + 2) = (3 + 4)

Two parties synchronising must necessarily trust one another to some degree: At the very least enough to download data from each other. Regardless of the sync protocol, if one side wants to it could always pretend that it doesn't have some data, or insert some bogus data into its data-set. The validity of the data, and the rules about its acceptance, are outside the scope of a sync protocol.

However, with RBSR there is another threat model to worry about: If a malicious third-party is able to insert specially-crafted data elements into one of the data-sets, it could choose elements that cause a range to have an equal fingerprint as some different range. During the sync, if the two parties compared the fingerprints of these two sets, they would incorrectly consider them equivalent and would stop trying to sync them.

If the specially-crafted malicious data elements themselves are not synced, nobody is likely to care. However, if the malicious elements prevent innocent victim elements from syncing, an attacker could use this to censor users by preventing their events from propagating throughout the network.

In the case of XOR, consider what would happen if you found a set of malicious elements that when hashed and XORed together were equivalent to the hash of a victim element. When computing the fingerprint of a range that includes the malicious elements and the victim element, they would "cancel out" and the two ranges would incorrectly have the same fingerprint.

Note that there are many obstacles to actually performing this censorship attack:

• The two fingerprints actually need to be compared in a sync. If one side of the sync is mostly empty, then the recursion may terminate early, and the elements will be transferred.

• The malicious elements need to be adjacent to or at least close-by the victim element. If a range boundary ever lands in the middle of these malicious elements, the attack will fail.

• If the ranges being compared also differ in any other elements, the ranges will be synced.

• If any future elements are added to the range, they may correctly sync up at that point.

rsync is theoretically vulnerable to the same problem because it uses known problematic hash functions such as MD4/MD5/xxhash and to our knowledge this has never been a problem (the analogy here is two trusted servers rsyncing a tarball containing attacker-created files).