CRDTs — How They Work

This page is the implementation-level companion to Collections and State, Projection & the Root Hash. The former tells you which collection to reach for; this one explains how the merge actually happens in the storage layer — and why the design choices are what they are.

The one big idea

Calimero never asks two nodes to agree on an order of operations. Instead, every piece of your state is shaped so that merge is a pure function — commutative, idempotent, and associative — and then it leans on one structural trick:

Give the same logical value the same storage id on every node, and most “merging” stops being a conflict and becomes a coincidence: both nodes already point at the same entity.

Everything below is a consequence of that. Where genuine concurrency does collide on one entity, a small set of per-type rules (last-writer-wins, max-per-writer, add-wins union, …) resolves it the same way on every replica.

The storage substrate: one entity per value

The unit of storage is not your app struct — it is the individual entry. Each logical entry (Entry<T>) is its own content-addressed storage entity with its own id, its own metadata, and its own sync path. A Map with 1,000 keys is 1,000 independent entities plus a thin container; it is not one blob.

The ids are derived, not random. An entry’s id is a domain-separated SHA-256 of its parent’s id and its key bytes (crates/storage/src/collections/collections.rs:189):

// compute_id(parent, key) — the same logical key → the same id on every node.
pub(crate) fn compute_id(parent: Id, key: &[u8]) -> Id {
    let mut hasher = Sha256::new();
    hasher.update(parent.as_bytes());
    hasher.update(b"__calimero_entry__"); // domain separator
    hasher.update(key);
    Id::new(hasher.finalize().into())
}

A nested collection uses the same construction with a different domain separator (__calimero_collection__ ‖ field_name), so a map entry keyed "X" can never collide with a child collection named X in the same parent.

The payoff: when node A writes users["alice"] and node B writes users["alice"] concurrently, both writes land on the same entity id — there is nothing to “match up” at sync time. Convergence is by id. The merge rule only has to settle the value of that one entity, never reconcile two independently-named things.

Note

Random ids would force every sync to discover “your alice == my alice” by content comparison. Deriving the id from the key sidesteps that entire problem: identity is a function of position, computed identically and offline on every node.

Blob vs Structured: why container merge is a no-op

Each CRDT type declares a StorageStrategy (crdt_impls.rs):

• Blob — the value lives inline as one serialized unit. The leaf CRDTs (LwwRegister, Counter, RGA) are blobs.
• Structured — the value decomposes into separate entities. The containers (UnorderedMap, SortedMap, UnorderedSet, SortedSet, Vector) are structured: each entry is its own Blob entity with its own derived id.

This split explains a line of code that looks like a bug but isn’t. The container-level merge for a structured collection literally throws away the existing side and keeps incoming (crates/storage/src/merge.rs):

fn merge_unordered_map(_existing: &[u8], incoming: &[u8]) -> Result<Vec<u8>, MergeError> {
    // Entries are separate entities synced on their own paths.
    // The container holds only structure; real accumulation is per-entry.
    Ok(incoming.to_vec())
}

That is correct precisely because the container holds no values — only structure. The actual keys and values are independent entities that each sync and merge on their own. The “map merge” you care about (union of keys, recursive merge of shared values) happens per entry, by id, not in this function. A structured container is a directory, and you do not merge two directories by merging the word “directory” — you merge their files.

Caution

There is a second, in-WASM map merge (UnorderedMap::merge in crdt_impls.rs) that does walk entries and recurse into values. It runs only for the rare root-entity conflict, where the whole app struct is compared as one unit. The hot path — a remote delta touching one key — never calls it; that key’s entity merges directly.

Per-type merge rules

Every leaf type resolves a same-id collision with a fixed, node-independent rule:

Type	Representation	Merge rule
LwwRegister<T>	inline { value, ts: HybridTimestamp, node_id }	newer HLC wins; exact tie → higher node_id
Counter (G / PN)	two UnorderedMap<hex(executor), u64> (positive / negative)	max per executor; value = Σpos − Σneg
UnorderedMap / Set (+ Sorted variants)	entries as separate entities	add-wins union; shared keys recurse into the value’s own CRDT merge
Vector<T>	indexed entries, each Id::random() at push	element-wise by index, then append the longer tail
RGA (text)	UnorderedMap<CharId, { content, left }>	union of immutable chars; delete = tombstone
Frozen	UnorderedMap keyed by SHA-256(value)	first-write-wins (keep existing)
Shared / SharedMember	LWW per writer	per-writer LWW; rotation-log children union regardless of timestamp

A little more on each:

LwwRegister<T> carries its own HLC timestamp and the writing node’s id inline. Merge keeps whichever side has the greater (timestamp, node_id). It is the right wrapper for any plain field — a bare String or u64 is deliberately not Mergeable, because *self = other is not commutative and would let two nodes diverge permanently.

Counter is a state-based counter: each executor owns one entry in a map and only ever grows its own count. Merge takes the max per executor — order-independent by construction — and the reported value sums the positive map and subtracts the negative map (a PN-counter; a G-counter omits the negative side).

Maps and sets are add-wins. Merge is a union of keys; when both sides hold the same key, the values are merged by their own CRDT rule (this is where nesting like Map<String, Counter> recurses). The Sorted variants store and merge identically to the unordered ones — ordering is a read-time concern derived from K: Ord, not a merge concern.

Vector merges element-wise by index, then appends whichever tail is longer. Note the id discipline: appended elements get Id::random() so two nodes appending concurrently cannot collide on the same entity. This is not a positional CRDT — concurrent inserts in the middle can interleave awkwardly. For collaborative text, use RGA.

RGA stores each character as an immutable node keyed by a CharId (HLC + sequence) with a pointer to its left neighbour. Deletes are tombstones (physically removed once resolved); merge is just the union of immutable characters. Read order is a pre-order DFS over the left-edge tree, and within a sibling group the highest CharId is emitted first — so a later concurrent insert at the same position sorts ahead deterministically on every node.

Frozen is for write-once data (identity keys, genesis state). It is a map keyed by SHA-256(value), so the same value always lands on the same key. Merge keeps the existing side — first-write-wins. Two nodes that independently write different first values will each keep their own and not converge; that is by design for immutable data, and is exactly why you should not use it for anything that must reconcile.

The algorithms

Everything above is prose; the two blocks here are the executable summary — enough to reimplement the merge layer from scratch. The unifying shape is the same for every type: combine the two sides commutatively, then resolve each element by a deterministic, node-independent rule. Because the rule reads only the data and never the arrival order, merge is commutative, idempotent, and associative — so order never matters.

Per-type merge

// LwwRegister<T> — entity resolved by `lww_pick` (interface.rs).
//   winner = max over (hlc, SHA-256(value_bytes)): newer HLC wins; on an exact HLC
//   tie the higher content hash wins — a property of the data, not of who arrived last.
fn merge(existing, incoming) -> bytes {
    match incoming.hlc.cmp(&existing.hlc) {
        Greater => incoming,
        Less    => existing,
        Equal   => if Sha256(incoming) >= Sha256(existing) { incoming } else { existing },
    }
}

// Counter<ALLOW_DECREMENT> — state-based G/PN counter (crdt_impls.rs).
//   Each executor owns one slot of grow-only counts; merge = per-executor MAX
//   (NOT a sum of deltas). `max` is commutative + idempotent, so two replicas
//   converge with zero coordination regardless of apply order.
fn merge(&mut self, other) {
    for (executor, n) in other.positive { self.positive[executor] = max(self.positive[executor], n) }
    if ALLOW_DECREMENT {
        for (executor, n) in other.negative { self.negative[executor] = max(self.negative[executor], n) }
    }
}
// value = Σ positive  (− Σ negative for the PN variant).

// UnorderedMap / UnorderedSet (+ Sorted variants) — add-wins (crdt_impls.rs + interface.rs).
//   Container merge = union of keys/elements; a shared map key recurses into V::merge.
//   Presence is LWW per entry ENTITY, decided in the storage layer, where a remove
//   is a tombstone carrying its own stamp:
fn present(entry) -> bool {
    entry.add_hlc > entry.delete_hlc   // newest stamp wins; an add outliving its tombstone ⇒ present
    // cf. apply_delete_ref_action: `deleted_at < updated_at` ⇒ deletion loses ⇒ entry kept
}

// Rga (text) — union of immutable char nodes (rga.rs).
//   A char is immutable, keyed by CharId = (hlc, seq); merge is a plain SET UNION;
//   a delete is a tombstone (the char drops out of the live set).
fn merge(&mut self, other) {
    for (id, ch) in other.chars { self.chars.entry(id).or_insert(ch) } // identical chars are a no-op
}
// Read order = pre-order DFS over the tree induced by each char's `left` edge.
// Within one sibling group (chars sharing a `left` origin) the HIGHEST CharId is
// emitted FIRST — so two concurrent inserts at the same position sort by (hlc, seq)
// the same way on every node, and a later insert lands ahead of the earlier one.

How an entity is hashed and addressed

own_hash(entity)  = SHA-256( borsh(value) )            // value bytes ONLY — metadata and
                                                       // schema_version are excluded, and in merge
                                                       // mode timestamps zero out, so two replicas
                                                       // that computed the same value hash identically

full_hash(node)   = SHA-256( own_hash ‖ for c in children.sorted_by(c.id): c.merkle_hash )
                                                       // c.merkle_hash IS the child's own full_hash → a
                                                       // recursive roll-up. Children are sorted by id
                                                       // ALONE (not by created_at) so the hash is purely
                                                       // content-derived and ignores each peer's local
                                                       // creation clock.

id(parent, key)   = SHA-256( parent ‖ "__calimero_entry__"        ‖ key )    // map / set entry
id(parent, field) = SHA-256( [parent ‖] "__calimero_collection__" ‖ field )  // nested collection
                                                       // (parent is omitted for a top-level field)

Consequences:

• Content-derived ids ⇒ the same logical key or field computes to the same id on every node, offline. Convergence is by id; there is nothing to match up at sync time.
• Recursive roll-up ⇒ editing one leaf rehashes only that leaf and its ancestor chain — O(depth), not O(tree). Untouched siblings keep their hashes.
• The root entity’s full_hash is the storage root_hash — the single value two replicas compare to detect (and then localise) divergence; see Projection.

A concrete merge: two writes to one field

Say a profile struct holds name: LwwRegister<String>. The field is one inline Blob entity at a derived id — the same id on every node, because it is a function of position, not content. Two users edit it concurrently:

entity id (both nodes): compute_id(profile_id, "name") = 0x5b2e…c4

Node A:  set name = "Alice"   →  LwwRegister { value: "Alice",  ts: 1750.000100:#0, node_id: A }
Node B:  set name = "Alicia"  →  LwwRegister { value: "Alicia", ts: 1750.000140:#0, node_id: B }

Both writes land on entity 0x5b2e…c4 — there is nothing to match up at sync time. When the deltas cross, each node runs the identical LwwRegister merge on that one entity: compare (ts, node_id), keep the greater. Here ts alone decides it — …140 > …100 — so both nodes converge on "Alicia", regardless of which delta arrived first:

Node	Applies	Compare	Result
A	local "Alice", then remote "Alicia"	…140 > …100 ⇒ incoming wins	"Alicia"
B	local "Alicia", then remote "Alice"	…100 < …140 ⇒ existing wins	"Alicia"

node_id never enters into it because the timestamps differ — it is only consulted on an exact ts tie, which is the next section. The losing write ("Alice") is simply dropped on merge; LWW keeps one value, it does not concatenate.

The equal-HLC tiebreak

Last-writer-wins needs a winner even when two writes carry the exact same HLC. This is not exotic: after a writer-set rotation, two distinct writers in a Shared set can stamp the same HLC nanosecond. The resolution lives in lww_pick (crates/storage/src/interface.rs:3358):

// Newer HLC wins; older loses; an exact tie is broken by content hash.
match incoming_timestamp.cmp(&existing_timestamp) {
    Ordering::Greater => incoming.to_vec(),
    Ordering::Less    => existing.to_vec(),
    Ordering::Equal   => {
        let inc = Sha256::digest(incoming);
        let exi = Sha256::digest(existing);
        if inc >= exi { incoming.to_vec() } else { existing.to_vec() }
    }
}

Why a content hash and not the obvious “incoming wins”? Because “incoming wins” is not order-independent. If node A applies B’s write last it keeps B; if B applies A’s write last it keeps A — and the two replicas are now permanently split-brained on the same DAG heads, with neither ever moving. Breaking the tie by SHA-256(value) makes the choice a property of the data, not of arrival order: both nodes compute the same winner, so they converge. Equal data is a true no-op.

Note

The same reasoning drives the rotation-log merge, which is an order-invariant union by delta_id with a deterministic byte-tiebreak on collision — so two nodes that apply each other’s logs in opposite orders produce byte-identical results and the same hash.

Two nodes write the same entity concurrently, gossip their deltas, and each runs the identical lww_pick — equal HLC, broken by SHA-256(value) — so both pick the same winner regardless of arrival order:

▶ Replay

Deterministic merge: with_merge_mode

Convergent values are not enough. Calimero compares replicas by hashing their state into a Merkle root (see Projection), so two nodes that computed the same merge must produce byte-identical entities — same timestamps, same node ids, everything.

That is a problem, because an LwwRegister normally stamps a fresh HLC and the local executor id whenever it is constructed or set. If a merge constructed new registers, each node would bake in its own clock and id, and the bytes — hence the hashes — would diverge even though the logical value matched.

The fix is a thread-local flag. Merges run inside env::with_merge_mode(...), and while it is set, every timestamp-stamping path zeroes itself out instead of reading the clock:

// LwwRegister::new / set, inside merge mode:
if env::in_merge_mode() {
    Self { value, timestamp: HybridTimestamp::zero(), node_id: [0; 32] }
} else {
    Self { value, timestamp: env::hlc_timestamp(), node_id: env::executor_id() }
}

So any value materialised as part of a merge is deterministic across nodes: two replicas computing the same merge serialize identical bytes and therefore hash to an identical Merkle root. A genuine post-merge write later supersedes it with a real timestamp. The flag is re-entrancy-safe — a nested storage op opening its own with_merge_mode will not clear the outer scope.

HybridTimestamp, briefly

The ordering currency is a Hybrid Logical Clock. A HybridTimestamp is an NTP64 value — 32 bits of seconds over 32 bits of fraction, with the low 16 bits reserved as a logical counter — paired with a u128 instance id:

┌──────────────────────┬──────────────────────┐
│   Seconds (32 bits)  │  Fraction (32 bits)  │
└──────────────────────┴──────────────────────┘
                                  └─ low 16 bits = logical counter

Ordering is (time, id): physical time first (so timestamps track wall-clock for TTLs and debugging), the logical counter breaking same-tick ties (so causality survives clock skew), and the unique instance id guaranteeing global uniqueness with no coordination. When a node observes a remote timestamp it advances its own clock past it, so a locally issued timestamp always sorts strictly after any event it causally follows.

Three subtler mechanisms

The rules above cover the common path. Three further mechanisms close gaps that only surface under writer rotation, runtime nesting, and schema migration — each one a small reuse of machinery you have already seen.

The rotation log is just add-wins children

A Shared set tracks who may write it through a per-entity writer-rotation log. Rather than invent a side channel, the log is materialised as an ordinary UnorderedMap<delta_id, RotationLogEntry> child of the Shared anchor entity, keyed by delta_id (crates/storage/src/rotation_log.rs:17-22, crates/storage/src/interface.rs:388-416). Each rotation is therefore one more hashed Merkle child — a content-addressed leaf — and converges through the very same add-wins entity-tree comparison that reconciles any other map.

A single blob holding the whole log would not converge: its custom merge re-runs every sync round and never settles. Per-delta_id leaves reconcile individually via the proven structural path, and insertion order does not matter — causal precedence between concurrent rotations is resolved at read time, not baked into storage order.

Runtime id rekey and the DeleteRef tombstone

A collection created on the fly — for example a Counter inserted as a map value — is born with a random id (Collection::new(None)). The moment it is inserted as a value of another collection it must take a parent-derived deterministic id so every node mints the same id and the children converge (crates/storage/src/collections.rs:490-537): the runtime computes compute_collection_id(parent, field_name), removes the old random-id entry, and re-adds the entity under the new id. rekey_nested_value recurses this through any nested collections the value itself carries (crates/storage/src/collections/rekey.rs:145-197).

There is a subtlety for nested collections (parent_id.is_some()). Such a collection’s Add action, under its random id, may already have been pushed to the outgoing delta. Re-keying locally removes the random-id entry, but a receiver that already applied the random-id Add would keep it as an orphan and diverge its parent’s hash. So the rekey also pushes a DeleteRef tombstone for the old random id, cancelling the shipped Add. Top-level rekeys (parent_id == None) run before any state is broadcast, so the old id was never shipped and no tombstone is needed.

schema_version is Merkle-invisible

Each entity’s Metadata carries a schema_version: Option<u32> (crates/storage/src/entities.rs:603-611). Crucially it is never folded into own_hash: a leaf’s own_hash is Sha256 of its data bytes only, not its metadata (crates/storage/src/interface.rs), so stamping or bumping the version never changes the entity’s Merkle leaf.

That is precisely what makes identity-gated migration possible. An owner re-stamps its identity-gated entries at a new version on its next ordinary signed write (with_schema_version, crates/storage/src/entities.rs:689-705) without diverging peers’ hashes and without a coordinated flag-day upgrade. A None tag reads as a legacy/v0 entry.

Summary

Mechanism	What it buys
Derived entity ids (SHA-256(parent ‖ sep ‖ key))	same logical value → same id on every node; convergence by id, no matching
Entity-per-value (Structured containers)	container merge is a no-op; accumulation is per-entry on independent sync paths
Per-type merge rules	each leaf collision resolves identically on every replica (LWW / max / union / FWW)
Content-hash tiebreak (lww_pick)	exact-HLC ties resolved by data, not arrival order → no split-brain
with_merge_mode timestamp zeroing	merged values are byte-identical across nodes → identical Merkle hashes
HybridTimestamp (time, id)	causal ordering immune to clock skew, globally unique without coordination

For the user-facing view of these types, see Collections; for how the merged entities fold into one comparable root hash, see Projection; and for the clock that stamps every write and breaks last-writer-wins ties, see the Hybrid Logical Clock.