CRDTs

Deep dive

How it works

Parts:

• replica state — counter slots, dotted sets or sequence IDs, one copy per replica
• merge function — commutative, associative, idempotent join of two states
• version vector / dots — records which updates a replica has seen
• delivery layer — gossip or sync that moves states (or deltas) between replicas

Operations: (1) apply a write locally, update the dots; (2) send state or a delta to a peer in any order; (3) merge on receipt; (4) read the value from the merged state.

• G-Counter: map actor → count; increment your own slot; merge = pointwise max; value = sum.
• PN-Counter: two G-Counters (increments, decrements); value = P − N.
• LWW-Register: (timestamp, actor, value); merge keeps the largest (timestamp, actor). Loses concurrent writes.
• MV-Register: keeps all concurrent values, tagged with vector clocks; the app resolves.
• OR-Set (add-wins), optimized "ORSWOT": a version vector clock of all dots seen plus, per element, the dots of its live adds. Add creates a fresh dot (actor, ++clock[actor]). Remove deletes the element's dots locally, and the clock remembers they existed. On merge, a dot present on one side only survives if the other side's clock has not seen it (it's new) and is dropped if it has (it was removed). No tombstones.
• Sequences (text): each character gets a unique, ordered ID (RGA, YATA in Yjs, Fugue); deletes leave tombstones or are compacted.

A: add(x) dot a1          B: (has seen a1) remove(x)
merge(A, B): dot a1 only on A, B.clock[a] >= 1 → B removed it → x gone
concurrent add(x) on A as a2: B.clock[a] = 1 < 2 → survives → add wins

Code

use std::collections::{BTreeSet, HashMap};
use std::hash::Hash;

pub type Actor = u32;
pub type Dot = (Actor, u64);

#[derive(Clone, Default, Debug, PartialEq)]
pub struct GCounter { slots: HashMap<Actor, u64> }

impl GCounter {
    pub fn inc(&mut self, me: Actor, n: u64) { *self.slots.entry(me).or_default() += n; }
    pub fn value(&self) -> u64 { self.slots.values().sum() }
    pub fn merge(&mut self, o: &GCounter) {
        for (a, &c) in &o.slots { let s = self.slots.entry(*a).or_default(); *s = (*s).max(c); }
    }
}

#[derive(Clone, Default, Debug, PartialEq)]
pub struct PNCounter { p: GCounter, n: GCounter }

impl PNCounter {
    pub fn add(&mut self, me: Actor, d: i64) {
        if d >= 0 { self.p.inc(me, d as u64) } else { self.n.inc(me, d.unsigned_abs()) }
    }
    pub fn value(&self) -> i64 { self.p.value() as i64 - self.n.value() as i64 }
    pub fn merge(&mut self, o: &PNCounter) { self.p.merge(&o.p); self.n.merge(&o.n); }
}

/// Add-wins observed-remove set without tombstones (ORSWOT).
#[derive(Clone, Debug, PartialEq)]
pub struct OrSet<E: Eq + Hash + Clone> {
    clock: HashMap<Actor, u64>,            // every dot this replica has seen
    entries: HashMap<E, BTreeSet<Dot>>,    // live add-dots per element
}

impl<E: Eq + Hash + Clone> OrSet<E> {
    pub fn new() -> Self { OrSet { clock: HashMap::new(), entries: HashMap::new() } }
    fn seen(clock: &HashMap<Actor, u64>, (a, c): Dot) -> bool { clock.get(&a).map_or(false, |&m| c <= m) }

    pub fn add(&mut self, me: Actor, e: E) {
        let c = self.clock.entry(me).or_default();
        *c += 1;
        // The new dot supersedes every add of e this replica has observed.
        self.entries.insert(e, BTreeSet::from([(me, *c)]));
    }
    pub fn remove(&mut self, e: &E) { self.entries.remove(e); } // clock keeps the evidence
    pub fn contains(&self, e: &E) -> bool { self.entries.contains_key(e) }

    pub fn merge(&mut self, o: &OrSet<E>) {
        let mut out: HashMap<E, BTreeSet<Dot>> = HashMap::new();
        let keys: Vec<E> = self.entries.keys().chain(o.entries.keys()).cloned().collect();
        let empty = BTreeSet::new();
        for e in keys {
            if out.contains_key(&e) { continue; }
            let mine = self.entries.get(&e).unwrap_or(&empty);
            let theirs = o.entries.get(&e).unwrap_or(&empty);
            let mut keep: BTreeSet<Dot> = mine.intersection(theirs).copied().collect();
            keep.extend(mine.difference(theirs).filter(|d| !Self::seen(&o.clock, **d)));
            keep.extend(theirs.difference(mine).filter(|d| !Self::seen(&self.clock, **d)));
            if !keep.is_empty() { out.insert(e, keep); }
        }
        for (a, &c) in &o.clock { let s = self.clock.entry(*a).or_default(); *s = (*s).max(c); }
        self.entries = out;
    }
}

Dots per actor are contiguous because every replica generates its own dots in sequence and merges whole state; that is what lets a plain version vector stand in for the set of seen dots.

Complexity and constants

• G/PN-Counter: 8-16 bytes per actor; merge O(actors).
• ORSWOT: O(actors) clock + one dot (~12 bytes) per live element, typically one per element after merges settle; merge O(elements + actors).
• Text CRDTs: per-character IDs and tombstones; modern implementations (Yjs, Automerge 2, diamond-types) run-length encode consecutive inserts by one actor, so the saved format of real editing traces costs order of bytes, not tens of bytes, per character.
• Delta-state: send only the join-irreducible changes since the last ack: bandwidth proportional to updates, not to object size.

Efficiency

• Cost: counters take 8-16 bytes per actor and merge in O(actors); an ORSWOT set takes one dot (about 12 bytes) per live element and merges in O(elements + actors). Text CRDTs run-length encode consecutive inserts by one actor, so saved real editing traces cost order of bytes per character (see above). Bound: metadata size and merge bandwidth, not CPU.
• Levers:
  • delta-state shipping — bandwidth proportional to the update, not the object (Almeida et al., JPDC 2018) — large sets and maps
  • run-length encoded text IDs — order of bytes per character instead of tens — editors
  • few stable actor IDs — clocks stay O(actors) — long-lived replicas
  • ORSWOT instead of tombstoned OR-Set — no tombstones for removed elements (Bieniusa et al. 2012) — churning sets
  • compact tombstones after all replicas have seen a delete — bounded text metadata — sequence types
• Naive → standard → state of the art:
  • ship full state every time · O(object size) per sync
  • op-based with causal delivery · O(1) per op, needs exactly-once causal delivery
  • delta-state with run-length encoded IDs · O(update) per sync, order of bytes per character

Implementation notes

• Actor IDs: a replica that loses its state and restarts with the same actor ID reissues old dots, which merges then silently drop. Persist the counter or take a fresh actor ID on recovery.
• Keep the actor set small: route client writes through a few server-side actors, or prune actors after a causal-stability point (all replicas have seen their dots).
• Ship deltas with anti-entropy via gossip; state-based merge makes duplicate and out-of-order delivery harmless.
• Compose: a map of CRDTs is a CRDT (Riak maps, Automerge documents). Removing a map key while another replica updates the nested value needs explicit "reset-remove" or "add-wins" semantics.
• Use hybrid logical clocks for LWW timestamps to bound skew effects.

Pitfalls

• Using LWW everywhere: concurrent updates silently vanish; fine for "last profile edit", wrong for carts.
• Expecting a counter to support set(0): concurrent increments make reset ill-defined without a reset-aware design.
• Op-based CRDTs over a transport without causal delivery: a remove can arrive before its add.
• Unbounded tombstones in sequence CRDTs for long-lived docs; plan compaction or snapshots.
• Interleaving anomalies in text: two users typing at the same spot can interleave characters with some algorithms (RGA); Fugue was designed to avoid this.

Variants and alternatives

In production

Databases: Riak KV data types (riak_dt), Redis Enterprise Active-Active, SoundCloud Roshi (LWW-element-set on Redis). Real-time presence: Phoenix Presence (Elixir, delta-CRDT). Collaborative editing: Automerge, Yjs, Loro.

Implementations

Sources

• Marc Shapiro, Nuno Preguiça, Carlos Baquero, Marek Zawirski, Conflict-free Replicated Data Types, SSS 2011. paper
• Marc Shapiro et al., A Comprehensive Study of Convergent and Commutative Replicated Data Types, INRIA RR-7506, 2011. report
• Annette Bieniusa et al., An Optimized Conflict-free Replicated Set, arXiv 1210.3368, 2012. paper
• Paulo Sérgio Almeida, Ali Shoker, Carlos Baquero, Delta State Replicated Data Types, JPDC 2018. paper · arXiv
• Matthew Weidner, Martin Kleppmann, The Art of the Fugue: Minimizing Interleaving in Collaborative Text Editing, arXiv 2023. paper