Vector Clocks & CRDTs
ReliabilityTechniques for detecting or entirely avoiding conflicts when multiple replicas accept writes independently and must later reconcile.
In an AP (available-under-partition) system, multiple replicas can accept writes to the 'same' logical data independently while partitioned, and later need to reconcile. A vector clock is a per-replica counter vector attached to each write, letting the system later determine whether two versions are causally ordered (one clearly happened after the other) or truly concurrent/conflicting (neither happened-before the other) — it detects conflicts but doesn't resolve them for you (the app must decide, e.g. merge or ask the user). A CRDT (Conflict-free Replicated Data Type) takes a stronger approach: it's a data structure specifically designed so that concurrent updates from different replicas can always be merged automatically into a single, mathematically well-defined result, with no conflict left for the application to resolve at all (e.g. a counter that only ever increments, or a set that merges via union).
How it connects
Vector Clocks & CRDTs as the source, with the components it typically interacts with.
- → CAP Theorem & PACELC: Vector clocks/CRDTs are the mechanism AP systems use to reconcile concurrent, conflicting writes accepted during a network partition.
- → Database Types (SQL, NoSQL & Beyond): Leaderless, multi-master databases (Dynamo, Riak, Cassandra) attach vector clocks to versions so they can detect and resolve write conflicts.
- → Gossip Protocol & Anti-Entropy: State is often propagated between replicas via gossip, and CRDTs guarantee that merging that gossiped state in any order still converges.