Vector clocks

Deep dive

How it works

In: vectors V and W (one counter per node), the local node id · Out: the updated vector, or Equal / Before / After / Concurrent · State: one vector per node, replica or stored item · Cost: O(N) per compare and merge, N = nodes that wrote

1. Local event at node i: V[i] += 1.
2. Send: attach V. Receive W: V = max(V, W) pointwise, then V[i] += 1.
3. Compare: V ≤ W iff every entry ≤. Equal / Before / After / Concurrent.

Storing siblings (version vectors). A client reads a key and gets the values plus a context (the merged clock). On write it sends the context back. The server drops every sibling the context has seen and keeps the rest. Plain version vectors break here: if the server stamps the new value with ctx plus its own incremented entry, that stamp can falsely dominate a concurrent sibling written through the same server. Dotted version vectors record the new event's dot (server, n) separately from its causal past ctx; a sibling is obsolete exactly when the incoming context contains its dot.

siblings: v1 dot(A,1) ctx{}        client X read {} → writes v2 with ctx{}
          v2 dot(A,2) ctx{}        both kept: neither ctx contains the other's dot
client Y reads {A:2}, writes v3 → v1, v2 obsolete (dots (A,1),(A,2) ≤ {A:2})

Code

use std::cmp::Ordering;
use std::collections::BTreeMap;

pub type Node = u32;

#[derive(Clone, Default, Debug, PartialEq, Eq)]
pub struct VClock(BTreeMap<Node, u64>); // absent entry = 0

#[derive(Debug, PartialEq, Eq)]
pub enum Causality { Equal, Before, After, Concurrent }

impl VClock {
    pub fn get(&self, n: Node) -> u64 { self.0.get(&n).copied().unwrap_or(0) }
    pub fn tick(&mut self, n: Node) -> u64 { let c = self.0.entry(n).or_default(); *c += 1; *c }
    pub fn merge(&mut self, o: &VClock) {
        for (&n, &c) in &o.0 { let e = self.0.entry(n).or_default(); *e = (*e).max(c); }
    }
    pub fn contains(&self, (n, c): (Node, u64)) -> bool { self.get(n) >= c }

    pub fn compare(&self, o: &VClock) -> Causality {
        let (mut less, mut greater) = (false, false);
        for n in self.0.keys().chain(o.0.keys()) {
            match self.get(*n).cmp(&o.get(*n)) {
                Ordering::Less => less = true,
                Ordering::Greater => greater = true,
                Ordering::Equal => {}
            }
        }
        match (less, greater) {
            (false, false) => Causality::Equal,
            (true, false) => Causality::Before,
            (false, true) => Causality::After,
            (true, true) => Causality::Concurrent,
        }
    }
}

/// Dotted version vector sibling: the write's own event plus what it had seen.
#[derive(Clone, Debug)]
pub struct Sibling { pub dot: (Node, u64), pub past: VClock, pub value: Vec<u8> }

#[derive(Default)]
pub struct Key { pub siblings: Vec<Sibling> }

impl Key {
    /// Read: all live values plus the context the client must echo on its next write.
    pub fn read(&self) -> (Vec<Vec<u8>>, VClock) {
        let mut ctx = VClock::default();
        for s in &self.siblings {
            ctx.merge(&s.past);
            let e = ctx.0.entry(s.dot.0).or_default();
            *e = (*e).max(s.dot.1);
        }
        (self.siblings.iter().map(|s| s.value.clone()).collect(), ctx)
    }

    /// Write coordinated by `server` with the client's context.
    pub fn write(&mut self, server: Node, ctx: VClock, value: Vec<u8>) {
        // Next dot must exceed every dot this server issued for the key: those live on
        // as sibling dots or inside the causal past of whoever overwrote them.
        let n = self.siblings.iter()
            .map(|s| s.past.get(server).max(if s.dot.0 == server { s.dot.1 } else { 0 }))
            .chain(std::iter::once(ctx.get(server))).max().unwrap_or(0) + 1;
        self.siblings.retain(|s| !ctx.contains(s.dot)); // drop what the client has seen
        self.siblings.push(Sibling { dot: (server, n), past: ctx, value });
    }
}

Contexts must come from read, so a context that contains a dot also contains that sibling's past.

Complexity and constants

• Space: N entries × (node id + counter) ≈ 12-16 bytes each in a compact encoding; a BTreeMap costs several times more in RAM.
• Compare/merge: O(N) with sorted vectors (merge-join), a few ns per entry.
• DVV per sibling: one dot + one vector; sibling count is bounded by the number of truly concurrent writers.
• Dynamo truncated clocks beyond about 10 entries (dropping the oldest by timestamp), trading rare false conflicts for bounded size.

Efficiency

• Cost: space N entries x (node id + counter), about 12-16 bytes each in a compact encoding; a BTreeMap costs several times more RAM. Compare and merge are O(N) with sorted vectors (merge-join), order of a few ns per entry. A dotted version vector adds one dot per sibling, and siblings are bounded by truly concurrent writers. Bound: memory and bytes on the wire, grows with distinct writers.
• Levers:
  • sorted Vec<(u32, u64)> or fixed array by replica number — merge-join, no hashing — small, known membership
  • key entries by replica, not client — vector size bounded by the replica count — client-facing stores
  • varint encoding (varint-leb128) — counters are usually small, so entries shrink — vectors sent per message or stored per key
  • truncate or prune old entries (Dynamo truncated beyond about 10) — bounded size at the price of rare false conflicts — many writers per item
  • interval tree clocks (Almeida et al.) — vector size follows the live participants, not all that ever existed — dynamic membership
• Naive → standard → state of the art:
  • one vector per client in a BTreeMap · grows without bound, several times the RAM
  • sorted replica-keyed vector with varints · about 12-16 bytes per entry, O(N) merge-join
  • dotted version vectors, or interval tree clocks for churn · siblings bounded by real concurrency

Implementation notes

• Use a sorted Vec<(u32, u64)> or a fixed array indexed by replica number when membership is small and known; avoid hash maps on the hot path.
• Key entries by replica/vnode, not client: Riak originally used client IDs, which grew vectors without bound.
• Encode with varints (varint-leb128): counters are usually small.
• Prune entries for decommissioned nodes only when every replica has merged past them.

Pitfalls

• Plain server-side version vectors with "ctx + increment own entry": falsely overwrites concurrent writes through the same coordinator. Use dots.
• Clients writing without the read context (blind writes): every write becomes a new sibling forever.
• Treating "Concurrent" as an error: it is the normal outcome of partitions; resolve with app logic or CRDT merge.
• Unbounded siblings when many clients write blindly to a hot key.

Variants and alternatives

In production

Key-value stores: Riak KV (dotted version vectors since 2.0), Amazon Dynamo (vector clocks with truncation), Project Voldemort. Collaborative editing: Yjs and Yrs encode a state vector per document. File sync: Syncthing's protocol carries a version vector per file. ShiViz visualizes vector-timestamped logs to debug distributed systems.

Implementations

Sources

• Colin Fidge, Timestamps in Message-Passing Systems That Preserve the Partial Ordering, 1988.
• Friedemann Mattern, Virtual Time and Global States of Distributed Systems, 1989.
• Nuno Preguiça, Carlos Baquero, Paulo Sérgio Almeida, Victor Fonte, Ricardo Gonçalves, Dotted Version Vectors: Logical Clocks for Optimistic Replication, arXiv 1011.5808, 2010. paper
• Paulo Sérgio Almeida, Carlos Baquero, Victor Fonte, Interval Tree Clocks, OPODIS 2008. paper
• Bernadette Charron-Bost, Concerning the Size of Logical Clocks in Distributed Systems, IPL 1991. paper
• Giuseppe DeCandia et al., Dynamo: Amazon's Highly Available Key-value Store, SOSP 2007. paper
• Syncthing, Block Exchange Protocol v1 (Vector, per-file version). spec
• Yjs documentation, Document Updates (state vectors). docs