rs-vectorclock

A small, zero-dependency Rust implementation of vector clocks — the data structure distributed systems use to track causality between events across replicas without relying on synchronized wall-clock time.

Vector clocks are the mechanism behind conflict detection in Dynamo-style key-value stores (Amazon Dynamo, Riak) and behind causal ordering in CRDT-based systems: when two replicas accept writes independently, their vector clocks let you determine whether one write causally depends on the other, or whether the two are concurrent — meaning neither replica knew about the other's write, and the conflict needs to be resolved (e.g. by merging, by last-writer-wins, or by keeping both as sibling values).

use rs_vectorclock::{CausalOrder, VectorClock};

// Two replicas, A and B, start from a common empty state.
let mut a = VectorClock::new();
let mut b = VectorClock::new();

// A records a local write.
a.increment("A"); // A: {A:1}

// B replicates from A (e.g. via anti-entropy or reading A's value),
// then records its own local write.
b.merge(&a);       // B: {A:1}
b.increment("B");  // B: {A:1, B:1}

// B's write causally depends on A's write.
assert_eq!(a.compare(&b), CausalOrder::Before);
assert_eq!(b.compare(&a), CausalOrder::After);

// Meanwhile, if a third replica C had also written independently,
// without ever observing A or B, its clock would be concurrent with both.
let mut c = VectorClock::new();
c.increment("C"); // C: {C:1}

assert_eq!(a.compare(&c), CausalOrder::Concurrent);
assert_eq!(b.compare(&c), CausalOrder::Concurrent);

A VectorClock is a map from replica identifier (&str) to a counter (u64). Each replica owns exactly one entry and only ever increments its own counter via increment(replica_id). When a replica observes another replica's state — through replication, a read that carries the writer's clock, or anti-entropy repair — it folds that state in with merge, which takes the element-wise maximum of every counter across both clocks. A replica id present in only one of the two clocks simply keeps its existing value, which is equivalent to treating the missing side as 0 and taking the max.

This merge rule is what makes vector clocks form a join-semilattice: merging is commutative, associative, and idempotent, so it doesn't matter how many times or in what order replicas exchange and merge clocks — the result always converges to the same state. That's exactly the property CRDTs (conflict-free replicated data types) build on.

compare determines the causal relationship between two clocks by looking at every replica either clock has an entry for (treating a missing entry as 0) and checking, entry by entry, whether self's counter is less than, equal to, or greater than other's:

• If every entry is equal, the clocks are Equal — same causal history.
• If every entry in self is <= the corresponding entry in other, with at least one strictly <, then self Before other — every event self knew about, other also knew about (or later), plus other knows about something self doesn't. self happened first.
• The mirror image is After.
• Otherwise, some entry favors self and some entry favors other — neither clock's history is a subset of the other's, so they're Concurrent: the two histories evolved independently and neither causally depends on the other. This is the case that signals a real conflict in a distributed store.

Because increments only ever grow a replica's own counter and merges only ever take a maximum, counters are monotonically non-decreasing, which is what makes this comparison well-defined as a partial order.

cargo test

The test suite includes a hand-traced scenario (see src/lib.rs) that walks through the textbook three-replica case step by step in comments before asserting on it:

1. Three replicas (A, B, C) each independently increment their own clock from a common empty start, with no merges between them — every pairwise comparison is asserted to be Concurrent.
2. One replica merges another's clock in before incrementing its own, producing a real Before/After relationship.
3. Two clocks with identical entries compare Equal.
4. A clock that merges another's state and then keeps incrementing independently diverges again, proving that a merge does not make all future states comparable — the comparison correctly returns to Concurrent.

MIT. See LICENSE.