rs-crdt

Real, from-scratch implementations of four widely used Conflict-free Replicated Data Types (CRDTs) in zero-dependency Rust:

• GCounter — grow-only counter
• PNCounter — increment/decrement counter
• LwwRegister<T> — last-write-wins register
• OrSet<T> — observed-remove set (add-wins)

CRDTs are the data-structure trick behind real-time collaborative software like Figma, Google Docs-style multiplayer editing, and offline-first sync engines (e.g. local-first apps that keep working without a network and reconcile changes later). The core idea: let independent replicas mutate their own copy of some state concurrently, with zero coordination, and guarantee that no matter what order those replicas later exchange and merge state in, they all converge on the exact same result — no conflicts, no central lock, no "last save wins and silently discards someone's work" surprise (except where that's explicitly the documented semantics, as in LwwRegister).

This crate is a library-level, in-memory implementation. It does not provide network transport, persistence, or wire-format serialization — deciding how replicas actually exchange state (HTTP, WebSockets, a gossip protocol, a message queue, disk storage, whatever) is entirely up to the caller. What this crate guarantees is the math: given two CRDT states, merge always produces the mathematically correct, conflict-free combination of both.

Usage

use rs_crdt::GCounter;

fn main() {
    // Two replicas (e.g. two servers, two offline devices) start empty.
    let mut replica_a = GCounter::new();
    let mut replica_b = GCounter::new();

    // Each replica increments its own count independently, with no
    // coordination between them.
    replica_a.increment("replica-a");
    replica_a.increment("replica-a");
    replica_b.increment("replica-b");

    assert_eq!(replica_a.value(), 2);
    assert_eq!(replica_b.value(), 1);

    // Later, the replicas sync by exchanging and merging state. It doesn't
    // matter which replica initiates the merge, or how many times it
    // happens - the result always converges.
    let merged = replica_a.merge(&replica_b);
    assert_eq!(merged.value(), 3);
    assert_eq!(merged, replica_b.merge(&replica_a));
}

See the crate's doc comments (cargo doc --open) for a runnable example of every public method, including PNCounter, LwwRegister<T>, and OrSet<T>.

How it works

Every type in this crate is a state-based CRDT (a CvRDT): each replica holds a full local copy of the data structure's state, and two replicas reconcile by calling merge(&self, other: &Self) -> Self. For a data type to be a valid CRDT, its merge operation must be:

• Commutative — merge(a, b) == merge(b, a). The order two replicas sync in doesn't matter.
• Associative — merge(merge(a, b), c) == merge(a, merge(b, c)). It doesn't matter how merges are grouped/batched.
• Idempotent — merge(a, a) == a. Merging the same state twice (e.g. from a re-delivered network message) is harmless.

Together these three properties mean every replica converges to the same state regardless of network delays, message reordering, or duplicate delivery. Every one of these properties is empirically proven in this crate's test suite for all four types, using real constructed instances — not just asserted against the implementation's own output.

GCounter

Each replica owns a private slot in a map from replica id to count, and only ever increments its own slot. merge takes the element-wise maximum of every replica's slot, and value() sums all slots. Because integer max is commutative, associative, and idempotent, so is the whole counter.

PNCounter

A plain grow-only counter can't represent "decrement" — there's no safe way to subtract without breaking the merge lattice (a real decrement would make merge no longer monotonic). PNCounter sidesteps this by holding two internal GCounters: one that only accumulates increments, one that only accumulates decrements. value() is increments.value() - decrements.value(), and merge just merges the two internal counters independently. Since each side is a valid G-Counter lattice, the whole thing is too.

LwwRegister

Holds one value, tagged with a logical timestamp and a replica id. merge keeps whichever write has the higher timestamp; ties are broken deterministically by comparing replica ids (higher wins). This is exactly max over the totally-ordered key (timestamp, replica_id) — max over a total order is commutative, associative, and idempotent by construction, so is merge. Be aware this is a genuine trade-off: the losing write is discarded entirely. If you need to preserve both sides of a real concurrent write, LwwRegister is the wrong tool — reach for something like OrSet instead.

OrSet (add-wins observed-remove set)

The hard case. A naive "set of elements" can't represent "replica A removed X while replica B concurrently re-added X" — there's no way to know, after the fact, which happened "later," and any fixed tie-breaking rule (always prefer remove, always prefer add) throws away real intent in the other case.

OrSet solves this by never deleting anything. Every add(replica_id, elem) generates a globally unique tag — (replica_id, sequence_number) — for that specific add event, and the set stores, per element, every tag that has ever added it. remove(elem) does not touch element identity at all: it only tombstones the tags currently observed by that replica at the moment of the call. An element is considered present iff it has at least one add-tag that is not in the tombstone set.

This is what produces add-wins semantics for real, not by convention: if replica B's re-add of X happens concurrently with (or causally after) replica A's remove of X, B's new tag was never observed by A, so A's tombstone set physically cannot contain it. Once A and B exchange state, merge takes the union of both replicas' add-tags and the union of both tombstone sets — B's fresh, untombstoned tag survives the union, so X is present in the merged result. The test suite proves this directly: two replicas start from a shared observed state of x, one removes it, the other concurrently re-adds it, and the merged result is asserted to contain x.

Testing

cargo test

The test suite includes, for every one of the four types:

1. An empirical commutativity check — real, non-trivial instances merged in both orders, assert equal results.
2. An empirical associativity check — three real instances merged in different groupings, assert equal results.
3. An empirical idempotence check — a real instance merged with itself, assert it's unchanged.
4. A scenario-specific convergence test, most notably OrSet's concurrent_add_wins_over_remove test, which builds two replicas from a shared starting state, has one remove an element while the other concurrently re-adds it, merges both directions, and asserts the element survives — proving add-wins semantics against a real divergent history, not a trivial no-op.

License

MIT