Designing a CRDT from Scratch

Designing a CRDT is not a syntax problem. It is a correctness-modeling problem. You move correctness from coordination into the data type itself.

If CRDTs Explained is the conceptual foundation, this is the implementation mindset.

The Real Shift

Traditional distributed systems try to prevent write conflicts through ordering, locking, or quorum rules.

CRDTs assume concurrency is normal. Replicas diverge, messages reorder, retries duplicate, partitions happen. The data type still converges.

That changes where you put rigor. Correctness no longer lives in "did these writes coordinate." Correctness lives in the state model and merge semantics.

Design starts with invariants, not syntax.

Step 0: Define the Invariant

You do not start with a struct or class. You start with what must be true after replicas converge.

Counter: total should equal all increments minus all decrements.
Set membership: an element should be present or absent according to explicit add/remove semantics.
Document ordering: all replicas should agree on the same relative order of inserted elements.

If you cannot state the invariant clearly, you are not ready to design the CRDT.

Step 1: Make State Monotonic

CRDT state must move forward in a partial order. Overwrite-in-place is the wrong mental model.

State should represent accumulated evidence, not one mutable slot.

Naive mutable counter failure:

Initial value = 0

Replica A: value = value + 1  => 1
Replica B: value = value + 1  => 1

If last-writer-wins merge picks one value, final = 1 (lost update).
Correct converged result should be 2.

Monotonic decomposition avoids this by storing per-replica progress that can only advance.

Step 2: Design the Merge Function First

In real networks, delivery order is unstable, retries happen, and duplicate delivery is expected.

So merge must be:

Commutative (order does not matter)
Associative (merge tree shape does not matter)
Idempotent (duplicates are safe)

You are not designing writes. You are designing merge behavior.

This guarantees that replicas converge to the same state regardless of message ordering, batching, or duplicate delivery.

CRDTs are one approach to eventual consistency, but unlike retry-based or queue-driven reconciliation, they encode conflict resolution directly into the data model.

Step 3: Choose the Model

State-based (CvRDT)

Replicas exchange state and merge with join semantics. Operationally simple. Payloads can get large.

Operation-based (CmRDT)

Replicas exchange operations instead of full state. Payloads stay smaller, but correctness now depends more heavily on the sync layer preserving the assumptions of the data type, typically causal delivery. The tradeoff is efficiency in exchange for tighter network and protocol requirements.

Delta CRDT

Replicas exchange compact state deltas while preserving join-based convergence. Good balance when full-state sync is too expensive.

Step 4: Encode Intent, Not Just Value

The PN-counter is a clean example. You do not store one integer. You store two grow-only maps indexed by replica: increments and decrements.

state:
  P[replica_id] = increments seen from that replica
  N[replica_id] = decrements seen from that replica

operations:
  increment(k): P[self] += k
  decrement(k): N[self] += k

merge(other):
  for each replica r:
    P[r] = max(P[r], other.P[r])
    N[r] = max(N[r], other.N[r])

value = sum(P[*]) - sum(N[*])

Merge takes the per-replica maximum for each component, making the system resilient to duplication, reordering, and delayed delivery.

Step 5: Handle Deletes Explicitly

Deletes are where many first CRDT designs break. Another replica may not even have seen the add you are trying to remove.

Use identity-tracked adds (OR-Set style), then remove observed identities.

Add(x) on replica A -> tag tA1
Add(x) on replica B -> tag tB9

state for x = {tA1, tB9}

Remove(x) at A removes identities A has observed.
If A has only seen tA1, remove records {tA1}.
After merge, tB9 can remain until it is explicitly observed and removed.

Remove operations only affect identities that are causally observed, which prevents deleting concurrent additions that have not yet been seen.

You do not delete values. You delete observed history.

Step 6: Define Concurrency Semantics

CRDT design always encodes meaning for concurrent actions. You must choose that meaning explicitly.

For registers, a common choice is:

LWW register: simple, compact, but can discard legitimate concurrent intent.
Multi-value register: preserves concurrent values and pushes final resolution to the application layer.

This is a product decision as much as a data-structure decision.

Step 7: Ordered Data Is Hard

Counters and sets are comparatively easy. Lists are not.

Index-based reasoning fails under concurrency: two replicas can both insert at index 3, but "index 3" is not a stable distributed identity. Ordered CRDTs like RGA, Logoot, and LSEQ therefore solve identity under concurrency, not fixed position in a mutable array.

Replica A inserts "X" after node id=7
Replica B inserts "Y" after node id=7 concurrently

Both operations are valid.
Order is resolved by deterministic identifier ordering, not wall-clock timing.

Memorable rule: lists are not "arrays with retries." They are identity graphs with ordering semantics.

Step 8: Validate the Design

Before implementation, run a strict checklist:

Merge is commutative, associative, idempotent.
State transitions are monotonic in the chosen partial order.
All replicas eventually converge under repeated anti-entropy.
Validate whether the business invariant is preserved after convergence.

CRDTs guarantee convergence—not correctness.

Step 9: Know When Not to Use One

Do not force CRDTs into domains that require hard global invariants:

Financial ledgers requiring strict serial ordering
Inventory with hard global limits
Uniqueness constraints across replicas
Cross-object invariants that require atomic multi-entity checks

Inventory oversell example: two partitions both see stock=1 and both sell. Later convergence may agree on state, but the business rule "never sell below zero" is already violated.

Stock = 1

Replica A sells → 0
Replica B sells → 0

Merge → -1

Converged. Still wrong.

This is the core limitation: convergence does not guarantee that business invariants survive concurrent writes.

Step 10: Map It to a Real System

A practical deployment model looks like this:

Client (local replica)
        ↓
Sync layer (anti-entropy / gossip / pubsub)
        ↓
Merge function (deterministic)
        ↓
Eventually consistent shared state

This is where anti-entropy, gossip, and read repair choices meet data-model guarantees.

Your causality model still matters. If you need a refresher on ordering metadata, review vector clocks vs timestamps.

Anti-entropy and causality metadata keep synchronization correct. And if your sync path can amplify retries under stress, apply reliability controls from backpressure and stability patterns to avoid turning replication into a self-inflicted incident.

Mental Models

Append-only history disguised as state.
Every write must be replayable in any order.
State is a monotonic lattice, not a mutable slot.

Conclusion

CRDTs remove coordination from the write path. They do not remove complexity.

The complexity moves into data modeling, merge semantics, and explicit concurrency meaning. Designing one well means defining what must stay true, then proving your merge rules preserve that truth under the worst network behavior you can expect.