Implementing RSYNC Protocol: From Theory to Practice

Understanding the RSYNC Protocol

What Is RSYNC?

RSYNC is a file synchronization protocol designed to efficiently update files over a network. Its core innovation is the delta-transfer algorithm, which minimises the amount of data that must be sent between a source and a destination. Instead of transmitting entire files, RSYNC compares a new version of a file (the source) with an older version that already exists at the destination (the receiver). The receiver sends compact block signatures (a weak rolling checksum and a strong hash for each block) to the sender. The sender then computes a delta — a set of instructions that describe how to rebuild the new file using the old file as a base. Only the parts that differ (literal data) and references to matching blocks are sent across the wire.

This approach turns a slow full-file copy into a lightweight exchange of checksums and patch commands. RSYNC is the engine behind the ubiquitous rsync command-line tool, but the protocol itself is a standalone concept that can be embedded in backup systems, software update mechanisms, and cloud storage synchronisation.

Why It Matters

Bandwidth efficiency: When only a small fraction of a large file changes, RSYNC sends just the changed bytes plus a handful of control tokens — often reducing transfer size by 90% or more.
Incremental backups: Backup tools like rsnapshot and rdiff-backup rely on the RSYNC algorithm to store only differences between snapshots.
Software updates: Over-the-air update systems can distribute delta patches instead of full binaries, saving mobile data and storage I/O.
Distributed storage: Cloud sync engines (Dropbox, Syncthing) use similar block-level differencing to keep folders in sync with minimal traffic.
Understanding the fundamentals: Implementing the protocol yourself gives you a deep intuition for checksums, rolling hashes, and delta encoding that transfers directly to other domains like log replication or data deduplication.

The Algorithm Deep Dive

🚀 Deploy your AI agent in 10 minutes

Managed Hermes hosting. Zero DevOps. 100M tokens/mo included.

Try it free →

Fixed-Size Block Splitting

Both the receiver and the sender divide files into fixed-size blocks (except the last block which may be shorter). The block size is crucial: too small and you generate many signatures, hurting lookup performance; too large and you lose granularity, increasing literal data. RSYNC typically selects a block size based on the file length. For example, the rsync tool uses roughly:

block_size = max(512, min(2048, file_size / 10000))

In our implementation we will use a fixed block size for simplicity, but the algorithm works identically with variable block sizes.

Weak Rolling Checksum

The weak checksum must be cheap to compute and must support a rolling window — i.e., when the window slides forward by one byte, the new checksum can be derived from the previous checksum in O(1) time. RSYNC uses a checksum inspired by Adler-32, consisting of two 16-bit components:

a = sum of all bytes in the block modulo 2¹⁶
b = sum of (i+1) * byte_i modulo 2¹⁶, where i is the position index (0‑based)

The combined 32-bit weak checksum is (b << 16) | a. This hash is not cryptographically strong, but it serves as a fast first-level filter. Because it is cheap and rolling, the sender can slide a window across the entire new file and test every position against the receiver’s signature table.

Rolling update derivation:
Let a block of size n have bytes B₀ … B_n-1. When we remove B₀ and append a new byte new, the new sums become:

a_new = a_old - B0 + new
b_new = b_old - a_old + n * new   (then mask to 16 bits)

This formula avoids recalculating the entire block sum from scratch, enabling the sender to scan huge files efficiently.

Strong Hash

Because the weak checksum can collide (different blocks may produce the same 32-bit value), every block signature also includes a strong, cryptographic hash — traditionally MD5, but MD4 or SHA-1 can be used. When the weak checksum matches, the sender computes the strong hash of its local window and compares it against the receiver’s stored hash. Only if both match does the protocol treat the block as identical. This two-stage filter provides both speed and reliability.

Delta Transfer Workflow

The whole exchange follows these steps:

Receiver: Splits its version of the file into blocks. For each block, computes weak checksum and strong hash. Sends this signature list to the sender.
Sender: Loads the new file. Slides a window of block size across it, computing the rolling weak checksum at every position. For each position, looks up the weak checksum in the receiver’s table. On a hit, it verifies with the strong hash. If verification succeeds, the sender emits a match token (pointing to the receiver’s block index) and advances the window by a full block. Otherwise, it emits the current byte as literal data and advances by one byte.
Receiver: Receives the delta instructions (mix of literal bytes and match tokens) and reconstructs the new file by copying matched blocks from its old file and writing out the literal chunks.

Implementing RSYNC in Python

Let’s build a complete, runnable implementation of the RSYNC algorithm. We’ll create four core components: block signatures, a rolling checksum class, delta computation, and reconstruction.

Step 1: Block Signatures

Given the receiver’s file data and a block size, we split the file into blocks, compute weak and strong checksums, and store them in a list. The last block may be shorter; we still compute its checksum normally.

import hashlib

def weak_checksum(data):
    """Compute the rsync-style 32-bit weak checksum."""
    a = 0
    b = 0
    for i, byte in enumerate(data):
        a += byte
        b += (i + 1) * byte
    a &= 0xFFFF
    b &= 0xFFFF
    return (b << 16) | a

def block_signatures(data, block_size):
    """Return list of (weak_checksum, strong_hash) for each block."""
    sigs = []
    for i in range(0, len(data), block_size):
        block = data[i:i+block_size]
        wk = weak_checksum(block)
        strong = hashlib.md5(block).digest()
        sigs.append((wk, strong))
    return sigs

Note: In production the strong hash should be chosen according to security needs; MD5 is used here for speed and compatibility with the traditional rsync algorithm.

Step 2: Rolling Checksum Class

We encapsulate the rolling window logic in a class. You feed bytes one at a time. Once the window fills to the block size, every subsequent byte produces a new checksum in O(1) using the derived update formulas.

class RollingChecksum:
    def __init__(self, block_size):
        self.block_size = block_size
        self.a = 0
        self.b = 0
        self.window = []   # stores the current block bytes
        self.count = 0
        self.checksum = None

    def add_byte(self, byte):
        """Feed one byte, return the current window's checksum (or None if not full)."""
        if self.count < self.block_size:
            self.window.append(byte)
            self.count += 1
            self.a += byte
            self.b += self.count * byte   # count is 1-indexed position
            if self.count == self.block_size:
                self.a &= 0xFFFF
                self.b &= 0xFFFF
                self.checksum = (self.b << 16) | self.a
            return self.checksum
        else:
            # Slide window forward
            old = self.window.pop(0)
            self.window.append(byte)
            a_old = self.a
            self.a = a_old - old + byte
            self.b = self.b - a_old + self.block_size * byte
            self.a &= 0xFFFF
            self.b &= 0xFFFF
            self.checksum = (self.b << 16) | self.a
            return self.checksum

    def current_window_bytes(self):
        """Return the bytes currently in the window (only valid when full)."""
        if len(self.window) == self.block_size:
            return bytes(self.window)
        return None

The current_window_bytes() helper lets us retrieve the window content when we need to compute the strong hash for verification. In a real high-performance implementation you would avoid copying bytes and instead keep a pointer into the original buffer, but for clarity we keep a small deque.

Step 3: Delta Computation Using Rolling Checksum

The sender loads the new file, builds a lookup table from the receiver’s signatures (mapping weak checksum to a list of (block_index, strong_hash) tuples), then runs the rolling checksum over the new file. At each full window, it checks the weak checksum table. On a hit, it verifies the strong hash and, if matched, emits a 'match' token. Otherwise, it emits a literal byte and advances by one position.

def compute_delta(signatures, new_data, block_size):
    """
    Compute delta instructions from receiver signatures and sender's new file.
    Returns list of tuples: ('literal', bytes) or ('match', block_index)
    """
    # Build lookup: weak_checksum -> list of (index, strong_hash)
    lookup = {}
    for idx, (wk, strong) in enumerate(signatures):
        lookup.setdefault(wk, []).append((idx, strong))

    delta = []
    literal_buffer = []
    roller = RollingChecksum(block_size)
    i = 0

    # Feed bytes into roller up to first full window
    while i < len(new_data) and roller.checksum is None:
        roller.add_byte(new_data[i])
        i += 1

    # Now slide window across remaining data
    while i <= len(new_data):
        window = roller.current_window_bytes()
        if window is None:
            break
        wk = roller.checksum
        if wk in lookup:
            # Weak match found, verify strong hash
            strong = hashlib.md5(window).digest()
            match_idx = None
            for blk_idx, stored_strong in lookup[wk]:
                if stored_strong == strong:
                    match_idx = blk_idx
                    break
            if match_idx is not None:
                # Flush any accumulated literal bytes
                if literal_buffer:
                    delta.append(('literal', bytes(literal_buffer)))
                    literal_buffer = []
                delta.append(('match', match_idx))
                # Advance window by full block
                for _ in range(block_size):
                    if i < len(new_data):
                        roller.add_byte(new_data[i])
                        i += 1
                    else:
                        break
                continue
        # No match or strong verification failed -> emit one literal byte
        literal_buffer.append(window[0])   # oldest byte in window
        # Slide window by one byte
        if i < len(new_data):
            roller.add_byte(new_data[i])
            i += 1
        else:
            break

    # Process any remaining bytes that never formed a full window
    while i < len(new_data):
        literal_buffer.append(new_data[i])
        i += 1

    if literal_buffer:
        delta.append(('literal', bytes(literal_buffer)))

    return delta

This algorithm produces a compact delta: long runs of matching blocks become single 'match' tokens, while changed areas become literal bytes. Note that we advance the window by a full block after a successful match; this is exactly what the real rsync does, because the matched block is now “consumed”.

Step 4: Reconstructing the File

The receiver holds the original file blocks (split identically to how signatures were generated) and applies the delta instructions sequentially. A match token copies the block from the original file; literal bytes are appended directly.

def reconstruct(original_data, delta, block_size):
    """Rebuild the new file from original data and delta instructions."""
    # Pre-split original into blocks for easy copy
    blocks = []
    for i in range(0, len(original_data), block_size):
        blocks.append(original_data[i:i+block_size])

    output = bytearray()
    for op, payload in delta:
        if op == 'literal':
            output.extend(payload)
        elif op == 'match':
            block_idx = payload
            output.extend(blocks[block_idx])
    return bytes(output)

Step 5: Putting It All Together

Here is a complete demonstration that simulates the RSYNC workflow on two versions of a file. It generates signatures from the old version, computes a delta from the new version, reconstructs the new version, and verifies correctness.

def main():
    # Simulate an old and a new version of a file
    old_data = b"The quick brown fox jumps over the lazy dog" * 20
    new_data = b"The quick brown fox leaps over the lazy cat" * 20

    block_size = 32  # small for demonstration

    # Receiver side: create signatures
    sigs = block_signatures(old_data, block_size)

    # Sender side: compute delta
    delta = compute_delta(sigs, new_data, block_size)

    # Receiver reconstructs
    reconstructed = reconstruct(old_data, delta, block_size)

    # Verify
    if reconstructed == new_data:
        print("Success! Reconstruction matches new file exactly.")
        print(f"Delta instructions count: {len(delta)}")