CRDTs explained: an interactive G-Counter and OR-Set against last-writer-wins

A CRDT, a conflict-free replicated data type, is a data structure that several replicas can change independently, even while disconnected, and that always merges into the same result once they exchange state. There is no coordination and no conflict to resolve by hand, because the merge is built so that the order, timing and repetition of merges do not matter. CRDTs power multi-region databases, offline-first apps and collaborative editors.

The playground keeps a like count and a shopping cart on two replicas, each stored two ways: as a last-writer-wins value and as a CRDT. Partition the network, make changes on both sides, heal it, and compare.

What last writer wins loses

The simplest way to merge replicas is to keep the value with the newest timestamp. For a counter that is wrong: three likes on A and two on B during a partition merge into 2, because B wrote last and its count replaces A’s. For a cart stored as one value, A’s eggs vanish when B’s later cart, with bread, replaces it. And when one person removes milk while another adds it, whichever change happened to be stamped later wins outright. Last writer wins is still fine for a single field such as a profile name, where keeping one of two concurrent edits is acceptable.

How CRDTs merge instead

• G-Counter. Each replica counts only its own increments; a merge takes the larger count for each replica, and the value is the sum: 3 + 2 = 5. A PN-Counter pairs two of them to allow decrements.
• OR-Set, observed-remove set. Every add gets a unique tag, and a remove deletes only the tags its replica has seen. An add the remover never saw survives the merge, so concurrent add and remove resolves to add-wins: milk stays.
• Registers. A last-writer-wins register keeps one value; a multi-value register keeps all concurrent values and lets the application or the user choose, as a shopping cart might.
• Sequences. Text CRDTs such as those in Yjs and Automerge give every character a unique, ordered position, so concurrent typing in the same document merges without operational transformation’s central server.

The merge works because it is commutative, associative and idempotent: replicas can exchange state in any order, through any path, as often as they like, for example by gossip, and still converge. The costs are metadata, such as per-replica counts and tombstones for removed tags that need coordination to garbage-collect, and semantics that are fixed in advance: a CRDT cannot enforce a rule like “stock never goes below zero”, which needs coordination.

A G-Counter and an OR-Set in code

class GCounter:
    def __init__(self, replica):
        self.replica, self.counts = replica, {}
    def increment(self, n=1):
        self.counts[self.replica] = self.counts.get(self.replica, 0) + n
    def value(self):
        return sum(self.counts.values())
    def merge(self, other):                 # order and repeats do not matter
        for r, c in other.counts.items():
            self.counts[r] = max(self.counts.get(r, 0), c)

class ORSet:
    def __init__(self, replica):
        self.replica, self.seq, self.adds, self.removed = replica, 0, {}, set()
    def add(self, x):
        self.seq += 1
        self.adds.setdefault(x, set()).add((self.replica, self.seq))  # a unique tag per add
    def remove(self, x):
        self.removed |= self.adds.get(x, set())                      # only tags seen here
    def __contains__(self, x):
        return bool(self.adds.get(x, set()) - self.removed)
    def merge(self, other):
        for x, tags in other.adds.items():
            self.adds.setdefault(x, set()).update(tags)
        self.removed |= other.removed

In a system design interview

CRDTs answer “what happens when two regions accept writes to the same thing?”: “Carts are active-active across regions. Each cart is an OR-Set, so items added in one region and removed in another merge without losing adds, and like counts are PN-Counters. Checkout, which must not oversell, goes through the item’s home region with a normal transaction.” Expect the follow-ups: how tombstones are cleaned up, how you would show a user a merge they did not expect, and which data truly needs a single leader.

Read the guide to CRDTs and operational transformation or offline-first sync, see vector clocks for detecting concurrent writes, or watch a strong candidate design a collaborative editor.

Questions people ask