Delta Encoding, in depth: gap entropy, zigzag and varints, block bit-packing, measured sizes and rsync-style binary deltas

Why differences are small: the gap argument

Take n sorted distinct integers from 0 to U. Stored plainly, each needs log₂ U bits. The gaps between neighbours, though, sum to at most U, so their average is U/n, and a good gap code spends about log₂(U/n) bits plus a small constant per value. Information theory says you cannot do much better: choosing n of U items carries about n log₂(U/n) + 1.44n bits of information. Delta encoding turns a cost that depends on the size of the universe into one that depends only on the density.

For a posting list with 100,000 document IDs drawn from 10 million (1% density), log₂ U is about 23.3 bits, but log₂(U/n) is about 6.6. That factor of three or more is the whole case for the technique. The same reasoning applies to any sequence whose neighbours are close: timestamps sampled at a fixed interval, sorted keys, offsets into a file.

Zigzag, varints and block bit-packing

Two building blocks turn small differences into small byte strings. A varint (LEB128) writes seven bits per byte and uses the high bit to say whether another byte follows, so values below 128 take one byte. Varints only handle non-negative numbers well: a negative difference written as a 64-bit two's complement integer takes ten bytes. Zigzag encoding fixes that by interleaving signs, mapping 0, -1, 1, -2, 2 to 0, 1, 2, 3, 4, so small magnitudes stay small whatever their sign. In the measurement, -3 written as a raw 64-bit varint took 10 bytes; zigzag turned it into 5, one byte.

def zigzag(v):    return (v << 1) ^ (v >> 63)     # for values that fit in int64
def unzigzag(u):  return (u >> 1) ^ -(u & 1)

def uvarint(u, out):
    while u >= 0x80:
        out.append((u & 0x7F) | 0x80)
        u >>= 7
    out.append(u)

def delta_varint_encode(values):
    out, prev = bytearray(), 0
    for v in values:
        uvarint(zigzag(v - prev), out)
        prev = v
    return bytes(out)

def delta_varint_decode(buf):
    vals, i, prev = [], 0, 0
    while i < len(buf):
        shift = u = 0
        while True:
            b = buf[i]; i += 1
            u |= (b & 0x7F) << shift
            shift += 7
            if b < 0x80:
                break
        prev += unzigzag(u)
        vals.append(prev)
    return vals

Varints decode one byte at a time with a branch per byte, which limits speed. Block bit-packing trades that for fixed widths: take a block of differences, subtract the block's minimum (so negative differences need no zigzag inside the block), find the bit width of the largest remainder, and pack every value in exactly that many bits. Decoding a block becomes a fixed sequence of shifts and masks that compilers and SIMD instructions handle well.

Parquet's DELTA_BINARY_PACKED encoding has exactly this shape. Its header holds the block size in values (a multiple of 128), the number of miniblocks per block (chosen so each miniblock holds a multiple of 32 values), the total value count, and the first value as a zigzag varint. Each block then stores its minimum delta as a zigzag varint, one byte of bit width per miniblock, and the bit-packed miniblocks. Per-miniblock widths mean one outlier inflates only its own miniblock. The size estimator used for the measurements below follows the same idea with one width per 128-value block:

def delta_bitpack_size(values, block=128):
    deltas = [b - a for a, b in zip(values, values[1:])]
    size = 10                                        # first value
    for s in range(0, len(deltas), block):
        blk = deltas[s:s + block]
        mn = min(blk)
        width = max(d - mn for d in blk).bit_length()
        size += 10 + 1 + (width * len(blk) + 7) // 8  # min delta, width, packed bits
    return size

Measured sizes and when deltas lose

Five data sets, 64-bit raw storage as the baseline (8 bytes per value), with zlib at level 6 for comparison:

Read the rows carefully. On sorted IDs, 1.28 bytes per value at 1% density is about 10.2 bits, about two bits above the 8.1-bit bound (6.6 + 1.44), because of block headers and the spread of gap sizes inside a block. Bit-packing beat varints everywhere, most dramatically on timestamps: every delta there is near 1,000, which needs two varint bytes but only about six bits once the block minimum is subtracted. A general-purpose compressor after delta encoding recovers more than varints alone, because zlib finds the residual redundancy; it beat bit-packing alone only on the posting lists. Compressors do far worse on the raw values because they cannot see numeric closeness in bytes.

For jitter around a constant, the values are not sorted, and the deltas span twice the range of the deviations themselves. Frame-of-reference coding, storing value minus block minimum without any delta, measured 1.34 bytes per value there, beating every delta variant. For random 40-bit values, deltas made things worse than plain 5-byte packing: the difference of two random values needs one more bit than either. Delta encoding is a bet that neighbours are close, and the data has to be checked.

Timestamps show the next step. If the interval is regular, the second difference is near zero: delta-of-delta encoding of the same 100,000 timestamps with zigzag varints took 100,010 bytes, 1.00 byte per value, half the plain delta cost. That is the first half of Facebook's Gorilla scheme, built in full in the HBase article.

Binary deltas: COPY, ADD and rsync

For files, the decoder holds an old version and needs a new one. A binary delta is a program of two instructions: COPY offset, length from the old version, and ADD literal bytes. VCDIFF (RFC 3284) standardises this format with a third instruction, RUN, for repeated bytes. Git packfiles store many objects as deltas against another object using the same copy and insert idea, and binary patch tools such as bsdiff refine it for executables, where inserting code shifts many addresses by the same amount.

When both versions are on one machine, the encoder can index the old version however it likes. The harder case is rsync's: the receiver has the old file, the sender has the new one, and neither wants to send a whole file. The receiver cuts its file into fixed-size blocks and sends a signature per block: a cheap weak checksum and a strong hash. The sender slides a window over the new file one byte at a time, updating the weak checksum in constant time, and checks the strong hash only on weak matches. The rolling update is the same trick as in Rabin-Karp search:

M = 1 << 16
def weak(block):                                  # rsync-style two-part checksum
    a = sum(block) % M
    b = sum((len(block) - i) * x for i, x in enumerate(block)) % M
    return a, b

# slide the window [i, i + bs) one byte to the right in O(1):
out_byte, in_byte = target[i], target[i + bs]
a = (a - out_byte + in_byte) % M
b = (b - bs * out_byte + a) % M

The full matcher (about 40 lines: index the signatures, roll, emit COPY on a strong-hash match and merge adjacent copies, otherwise append to a pending ADD) was tested on a 259,716-byte text file edited three ways: 99 bytes inserted, 50 deleted, 10 overwritten. Applying every delta reproduced the new file exactly. The interesting part is the traffic. Assuming 20 bytes of signature per block (a 4-byte weak checksum plus a 16-byte MD5) and estimating the delta at 8 bytes per COPY and 1 byte plus the literals per ADD, with zlib of the whole new file (109,817 bytes) as the alternative:

Small blocks give the tightest delta but the signatures cost more than sending the compressed file. Large blocks resend more literal bytes around each edit but cut signature traffic. The total is minimised where the two terms balance, which is why rsync does not use a fixed block size: since version 2.6.0 it picks roughly the square root of the file length, with a 700-byte minimum, and it also shortens the strong checksum it sends according to block and file size. In this sweep the minimum fell at 1,400-byte blocks (8,693 bytes in total); the rule gives 700 bytes for this file, which cost 9,621, within 11% of the minimum and twelve times smaller than resending the compressed file.

Failure modes

Failure modes that show up in production:

• No random access. Each value depends on all earlier ones, so reading value one million means decoding a million deltas. Restart from an absolute value every block and keep a small index of block starts; posting lists add skip pointers for the same reason.
• Error propagation. One corrupted delta shifts every later value, and nothing looks wrong. Checksum each block, and verify the reconstructed file against a whole-file hash after applying a binary delta.
• Wrong base. A binary delta is meaningless against any version other than the one it was made from. Carry the base's hash in the delta header and refuse to apply on mismatch.
• Overflow. The difference of two int64 values can exceed int64. Compute deltas with wrapping arithmetic and undo it the same way, or restrict the input range.
• Unsorted or noisy input. As measured, deltas of unrelated values are wider than the values. Choose the encoding per block from the data: plain bit-packing, frame of reference, delta or delta-of-delta.
• Long delta chains. Version stores that delta each object against the previous one make reads walk the chain. Git limits chain depth when repacking for this reason; any store should cap chains and keep periodic full snapshots.

Operational guidance and trade-offs

Choose by access pattern. Sequential scans of sorted or regular data, such as posting lists, timestamps and offsets, suit delta with block bit-packing. Point lookups need block restarts and an index. Data written once and read often deserves the encoder time to choose the best scheme per block. Data written constantly and rarely read needs cheap encoding, which favours plain varints.

Measure bytes per value and decode throughput together. The table shows varints losing on size, and in practice they also lose on decode speed against fixed-width blocks, though SIMD-friendly byte-oriented formats such as Stream VByte narrow that gap. Layer a general-purpose compressor on top only when the measurement shows a gain worth its CPU cost: here zlib on top of varints came to 0.65 bytes per value on the 10% posting list against 0.85 for bit-packing alone, but 0.89 against 0.84 on the timestamps.

For binary deltas, decide where the expensive work happens. Generating deltas on a server once and shipping them to many clients (software updates, package mirrors) justifies slow, thorough matching. Interactive sync between two peers needs rsync's cheap rolling search and adaptive block size. Fall back to a full transfer when the delta would exceed a large fraction of the compressed file, which happens with encrypted or already compressed inputs, where a one-byte change scrambles everything after it.

What to do next

1. Run the encoder and decoder above on a real column or posting list from your system and assert a round trip on every block.
2. Compute the bound, n log₂(U/n) + 1.44n bits, and compare your bytes per value with it to see how much room is left.
3. Implement the 128-value block bit-packer, then compare it with varints on size and decode speed using your data, not random data.
4. Add per-block checksums and restart points, and test that decoding the middle of a stream works.
5. For file sync, build the rolling matcher, sweep the block size, and plot delta plus signature bytes against the compressed file size, as in the table above.
6. Read the Huffman coding article to see how an entropy coder can follow a delta transform when gap sizes are skewed.