Snapshot delta compression

Deep dive

How it works

Parts:

• Sent ring — per client, last N snapshots sent, each with a number.
• Ack tracker — newest snapshot number the client confirmed.
• Delta encoder — merge pass over baseline and current; removed, new, changed with field mask.
• Client ring and decoder — applies the delta on its copy of the baseline.

1. Server stores, per client, a ring of the last N snapshots it sent, each tagged with a snapshot number.
2. Client acks snapshot numbers (piggybacked on its input packets via reliable UDP acks).
3. Building snapshot S for a client: baseline B = newest acked snapshot still in the ring (none → full snapshot against an empty world). Write B's number in the header.
4. Walk entities of B ∪ S in id order: removed → id + "removed" bit; new → id + all fields; existing and changed → id + field mask + values; unchanged → nothing.
5. Client keeps the snapshots it received in a ring; decodes S on top of its copy of B, stores S. If B is no longer in its ring, it drops S and keeps acking older ones; the server will fall back.

client acks:        #40       #42
server sends:  #41(base 40) #42(base 40) #43(base 42) #44(base 42) ...
lost packets cost nothing: each delta is against something the client definitely has

Code

/// Bit-level writer/reader (LSB-first within u64 words).
pub struct BitWriter { pub out: Vec<u8>, acc: u64, n: u32 }
impl BitWriter {
    pub fn new() -> Self { BitWriter { out: Vec::new(), acc: 0, n: 0 } }
    pub fn put(&mut self, v: u32, bits: u32) {
        debug_assert!(bits <= 32 && (bits == 32 || v < 1 << bits));
        self.acc |= (v as u64) << self.n;
        self.n += bits;
        while self.n >= 8 { self.out.push(self.acc as u8); self.acc >>= 8; self.n -= 8; }
    }
    pub fn finish(mut self) -> Vec<u8> { if self.n > 0 { self.out.push(self.acc as u8); } self.out }
}
pub struct BitReader<'a> { b: &'a [u8], pos: usize }
impl<'a> BitReader<'a> {
    pub fn new(b: &'a [u8]) -> Self { BitReader { b, pos: 0 } }
    pub fn get(&mut self, bits: u32) -> Option<u32> {
        let mut v = 0u32;
        for i in 0..bits {
            let byte = *self.b.get(self.pos / 8)?;
            v |= (((byte >> (self.pos % 8)) & 1) as u32) << i;
            self.pos += 1;
        }
        Some(v)
    }
}

/// Entity state, already quantized: x, y, z (18 bits each), yaw (9 bits).
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub struct Ent { pub id: u16, pub f: [u32; 4] }
const WIDTH: [u32; 4] = [18, 18, 18, 9];
const ID_BITS: u32 = 10; // up to 1024 entities

fn zigzag(d: i32) -> u32 { ((d << 1) ^ (d >> 31)) as u32 }
fn unzigzag(z: u32) -> i32 { ((z >> 1) as i32) ^ -((z & 1) as i32) }

/// Both slices sorted by id. Unchanged entities produce zero bits.
pub fn encode(base: &[Ent], cur: &[Ent]) -> Vec<u8> {
    let mut w = BitWriter::new();
    let (mut i, mut j) = (0, 0);
    while i < base.len() || j < cur.len() {
        let (b, c) = (base.get(i), cur.get(j));
        match (b, c) {
            (Some(b), Some(c)) if b.id == c.id => {
                i += 1; j += 1;
                if b.f == c.f { continue; }
                w.put(1, 1); w.put(c.id as u32, ID_BITS); w.put(0, 1); // entry, id, not removed
                for k in 0..4 {
                    if b.f[k] == c.f[k] { w.put(0, 1); continue; }
                    w.put(1, 1);
                    let z = zigzag(c.f[k] as i32 - b.f[k] as i32);
                    if z < 256 { w.put(1, 1); w.put(z, 8); } else { w.put(0, 1); w.put(c.f[k], WIDTH[k]); }
                }
            }
            (Some(b), c) if c.map_or(true, |c| b.id < c.id) => { // removed since baseline
                i += 1;
                w.put(1, 1); w.put(b.id as u32, ID_BITS); w.put(1, 1);
            }
            (_, Some(c)) => { // new entity: full state
                j += 1;
                w.put(1, 1); w.put(c.id as u32, ID_BITS); w.put(0, 1);
                for k in 0..4 { w.put(c.f[k], WIDTH[k]); }
            }
            _ => unreachable!(),
        }
    }
    w.put(0, 1); // end of entries
    w.finish()
}

pub fn decode(base: &[Ent], data: &[u8]) -> Option<Vec<Ent>> {
    let mut r = BitReader::new(data);
    let mut out: Vec<Ent> = base.to_vec();
    while r.get(1)? == 1 {
        let id = r.get(ID_BITS)? as u16;
        let removed = r.get(1)? == 1;
        let pos = out.binary_search_by_key(&id, |e| e.id);
        match (pos, removed) {
            (Ok(p), true) => { out.remove(p); }
            (Ok(p), false) => {
                for k in 0..4 {
                    if r.get(1)? == 0 { continue; }
                    out[p].f[k] = if r.get(1)? == 1 {
                        (out[p].f[k] as i32 + unzigzag(r.get(8)?)) as u32
                    } else { r.get(WIDTH[k])? };
                }
            }
            (Err(p), false) => {
                let mut f = [0u32; 4];
                for k in 0..4 { f[k] = r.get(WIDTH[k])?; }
                out.insert(p, Ent { id, f });
            }
            (Err(_), true) => return None, // removing something we never had: wrong baseline
        }
    }
    Some(out)
}

#[test]
fn delta_roundtrip_and_size() {
    let base: Vec<Ent> = (0..200).map(|i| Ent { id: i, f: [i as u32 * 100, 5000, 7, 300] }).collect();
    let mut cur = base.clone();
    for e in cur.iter_mut().step_by(10) { e.f[0] += 3; e.f[3] = (e.f[3] + 1) % 512; } // 20 movers
    cur.remove(5);
    cur.push(Ent { id: 900, f: [1, 2, 3, 4] });
    let bytes = encode(&base, &cur);
    assert_eq!(decode(&base, &bytes).unwrap(), cur);
    assert!(bytes.len() < 100, "{} bytes vs {} for a full snapshot", bytes.len(), 200 * 9);
}

Complexity and constants

• Encode/decode: one merge pass over baseline and current, O(n) in entity count; order of 10-100 ns per entity.
• Sizes in the test: 200 entities, 20 moving, 1 removed, 1 added: 96 bytes vs 1800 bytes for the full quantized snapshot.
• Per changed entity: 1 + id bits + 1 + per-field (1 bit unchanged, 10 bits small delta, 1 + width bits otherwise).
• Server memory: clients × history × snapshot size; 100 clients × 32 × 10 KB = 32 MB. Store snapshots once globally and per-client only entity lists, or share world snapshots across clients.

Efficiency

Cost: one merge pass over baseline and current, O(n) in entities, order of 10-100 ns per entity. In the test below, 200 entities with 20 moving, 1 removed, 1 added encode to 96 B against 1800 B for the full quantized snapshot. Fiedler's 901-cube demo drops from about 17 Mbit/s raw to the order of a few hundred kbit/s. Server memory is clients × history × snapshot size: 100 × 32 × 10 KB = 32 MB. Bound: bandwidth, then encode CPU per client.

Levers:

• Quantize before diffing (state-quantization) — exact integer deltas, tiny values — always.
• Delta against baseline + velocity × dt — near-zero residuals for smooth motion — moving objects.
• Cache encoded deltas per (baseline, snapshot) pair — encode once for clients sharing a baseline — 100+ clients at 60 Hz.
• Share world snapshots across clients, per-client entity lists only — cuts the 32 MB of history — large matches.
• Static Huffman over the bitstream (Quake 3) — extra bandwidth saving at some CPU cost — when CPU allows.

Naive → standard → state of the art:

• Full snapshot every tick · 1800 B in the test case
• Delta against the last acked baseline with field masks · 96 B in the same case
• Quantized, extrapolated-baseline deltas with priority accumulators · few hundred kbit/s for hundreds of objects (Fiedler)

Implementation notes

• Ack piggybacking: clients include the newest received snapshot number in every input packet; acks are naturally redundant.
• Baseline too old (ring overflow after long loss): send a full snapshot; rate-limit full snapshots because they are large and fragment.
• Keep packets under ~1200 bytes; when a delta doesn't fit, send the highest-priority entities and carry the rest over (they stay "changed" against the baseline next time).
• Per-field predictors beat plain deltas for smooth motion: delta against baseline + velocity × dt (extrapolated baseline) gives near-zero residuals.
• Follow with a generic entropy coder only if CPU allows; Quake 3 used a static Huffman table over the bitstream bytes.
• Use the same delta machinery for the client's input stream (inputs vs previous input).

Pitfalls

• Delta against the last sent snapshot: one lost packet corrupts every following frame.
• Client and server rings out of sync about which numbers exist: always include the baseline number and drop undecodable snapshots, never guess.
• Floating-point fields delta'd as floats: not exact; quantize first, delta integers.
• Entity id reuse in the same tick window (despawn + spawn with the same id) looks like a teleporting entity; add a spawn generation counter.
• Per-client encoding cost × 100 clients × 60 Hz: cache encoded deltas per (baseline, snapshot) pair when many clients share baselines.

Variants and alternatives

In production

• Games: Quake 3 and id Tech derivatives, Valve Source (delta-encoded packet entities), Unreal Engine (per-connection shadow state, delta serialization of FFastArraySerializer), Overwatch, Halo.
• Web: RFC 3229 lets an HTTP client request a delta against a cached instance of a resource, since updates are typically much smaller than the entity.
• Offline-first apps: Replicache pull responses return a patch for the client's current state.

Implementations

Sources

• Fiedler, Snapshot Compression and State Synchronization, gafferongames.com, 2015. post · post
• Sanglard, Quake 3 Source Code Review: Network Model, fabiensanglard.net, 2012. article
• id Software, Quake III Arena source code (msg.c, sv_snapshot.c), GPL release, 2005.
• Valve Developer Community, Source Multiplayer Networking. page
• Mogul et al., Delta encoding in HTTP, RFC 3229, 2002. RFC
• Replicache, How Replicache Works. docs