Convergent Data Types

The previous chapter left you with a choice on every concurrent write: keep siblings and resolve them yourself, or let last-write-wins silently drop one. Convergent data types -- CRDTs -- give you a third option that is almost always the right one for structured values. A CRDT merges concurrent writes automatically and correctly, with no sibling handling and no lost write, because the merge is defined by the data type's algebra rather than by a timestamp race or a human callback.

This chapter explains why CRDTs work, walks the six types Dyniak ships, and shows the API for each.

Why CRDTs

A CRDT is a data type whose merge operation is associative, commutative, and idempotent. Those three laws are what make it safe in an eventually-consistent, masterless store:

Commutative

merge(a, b) == merge(b, a). The order in which two replicas exchange state does not matter.

Associative

merge(merge(a, b), c) == merge(a, merge(b, c)). The order in which three or more replicas' states combine does not matter.

Idempotent

merge(a, a) == a. Receiving the same state twice -- a retransmit, a re-read during anti-entropy -- changes nothing.

Together these give strong eventual consistency: any two replicas that have received the same set of updates, in any order, with any duplicates, converge to exactly the same value. No coordination, no locks, no consensus round. A replica can accept a write while partitioned from the rest of the cluster, and when the partition heals, the merge reconciles the divergence deterministically.

Every type below satisfies all three laws; property tests in the crate (crates/dyniak/tests/datatypes_properties.rs) exercise associativity, commutativity, and idempotence on randomly generated states.

Actors

CRDTs track who made each change so the merge can tell concurrent edits apart. Riak keyed this by an Erlang vnode_id tuple; Dyniak uses an ActorId, the (datacenter, peer) pair the Dynomite substrate already publishes through gossip. The pair is stable across gossip rounds and totally ordered, which is exactly what an OR-Set tag generator and a register tiebreaker need.

#![allow(unused)]
fn main() {
use dyniak::datatypes::ActorId;

let a = ActorId::new("dc1", "peer-a");
let b = ActorId::new("dc1", "peer-b");
assert!(a < b);   // lexicographic on (dc, peer)
}

The six types

Dyniak ships the same six data types Riak did. Four are primitive; the map composes them; the HyperLogLog is a cardinality estimator.

flowchart TB
  Counter[Counter<br/>PN-counter]
  Set[Set<br/>observed-remove]
  Register[Register<br/>last-write-wins]
  Flag[Flag<br/>enable-wins]
  Map[Map<br/>observed-remove, recursive]
  HLL[HyperLogLog<br/>cardinality estimate]
  Map --> Counter
  Map --> Set
  Map --> Register
  Map --> Flag
  Map --> Map

The six Dyniak CRDTs. A Map field may hold any primitive type or, recursively, another Map -- the same composition Riak's riak_dt_map offers.

Counter

A positive-negative counter (PnCounter). Internally it is a pair of per-actor grow-only counts; the value is sum(positive) - sum(negative), and merge is the element-wise maximum of each actor's count. That maximum is what makes concurrent increments on different replicas both survive.

#![allow(unused)]
fn main() {
use dyniak::datatypes::{ActorId, Crdt, PnCounter};

let a = ActorId::new("dc1", "a");
let b = ActorId::new("dc2", "b");

// Two replicas increment independently while partitioned.
let mut left = PnCounter::new();
left.increment(&a, 5);

let mut right = PnCounter::new();
right.increment(&b, 3);
right.decrement(&b, 1);

// Partition heals; the two states merge.
left.merge(&right);
assert_eq!(left.value(), 5 + 3 - 1);   // 7 -- neither increment lost
}

Over the wire this is a DtUpdateReq carrying a counter op. A common use is a page-view or like counter that many nodes bump concurrently.

Set

An observed-remove set (OrSet) of arbitrary byte-string elements. Each add mints a fresh per-actor tag; a remove tombstones only the tags it has observed. The rule is "add wins": a concurrent add and remove of the same element resolves to present, because the add carries a tag the remove never saw.

#![allow(unused)]
fn main() {
use dyniak::datatypes::{ActorId, Crdt, OrSet};

let a = ActorId::new("dc1", "a");
let b = ActorId::new("dc2", "b");

let mut left = OrSet::new();
left.add(&a, "red");
left.add(&a, "green");

// Concurrently, replica b adds "blue" and removes "green"
// (b had observed green before removing it).
let mut right = left.clone();
right.add(&b, "blue");
right.remove(b"green");

left.add(&a, "green");   // a re-adds green concurrently -> add wins
left.merge(&right);

assert!(left.contains(b"red"));
assert!(left.contains(b"blue"));
assert!(left.contains(b"green"));   // survived: the re-add's tag was unseen
}

Use a Set for tag lists, group memberships, or any collection where concurrent add and remove must both be respected.

Register

A last-write-wins register (LwwRegister). State is (value, timestamp, actor); merge picks the higher timestamp, breaking ties by the higher actor id. Unlike bucket-level last-write-wins, a register is a deliberate, typed choice: you are saying "for this field, newest wins" and you get a deterministic tiebreak instead of a silent sibling. Registers are most useful as fields inside a Map.

Flag

An enable-wins boolean (EwFlag) -- an OR-Set restricted to a singleton domain. Concurrent enable and disable resolves to enabled. Use it for a feature toggle or a "seen" bit where turning it on should not be lost to a concurrent turn-off.

Map

An observed-remove map (Map), ORSWOT-style. It is keyed by a FieldKey -- a (name, type) pair -- and each value is one of the four primitives or, recursively, another Map. Two fields with the same name but different types are distinct, which is how a map namespaces its fields. Field presence follows the same add-wins rule as the Set:

#![allow(unused)]
fn main() {
use dyniak::datatypes::map::FieldType;
}

The field types a map may carry are Counter, OrSet, LwwRegister, EwFlag, and NestedMap. A worked example: a user profile as a map with a visits counter, an interests set, and a name register, all merging independently.

HyperLogLog

A probabilistic cardinality estimator (HyperLogLog). It answers "how many distinct elements have been added?" with a small, fixed-size state and a bounded error, and it merges by taking the per-register maximum -- the same lattice join pattern as the counter. Use it to count unique visitors or unique keys touched without storing every element.

How convergence plays out on the ring

The laws are abstract; here is what they buy you operationally. Two replicas of the same CRDT key diverge under a partition, then reconcile:

sequenceDiagram
  participant R1 as replica 1
  participant R2 as replica 2
  Note over R1,R2: network partition
  R1->>R1: increment counter (+5)
  R2->>R2: increment counter (+3)
  Note over R1,R2: partition heals; anti-entropy runs
  R1->>R2: ship state {r1: +5}
  R2->>R1: ship state {r2: +3}
  Note over R1: merge -> {r1:+5, r2:+3} = 8
  Note over R2: merge -> {r1:+5, r2:+3} = 8

Both replicas accepted a write during the partition; the anti-entropy exchange ships state both ways; the merge is order-independent and idempotent, so both converge to 8. No write was lost and no coordination was needed.

The exchange that carries CRDT state between replicas is the same anti-entropy machinery described in Anti-Entropy and Repair; read repair on a quorum read also merges divergent replicas before answering.

Choosing a type

A running total

Counter. Increments and decrements from any replica all count.

A collection with add and remove

Set. Concurrent add wins over remove.

A single "newest wins" value

Register, usually as a Map field.

A boolean where "on" should stick

Flag (enable-wins).

A structured record

Map, composing the above; nest maps for sub-records.

An approximate distinct count

HyperLogLog.

An arbitrary opaque blob with a custom merge

Not a CRDT -- use a plain object with siblings and resolve in the application. See siblings.

Where to next

• Distributed Transactions -- when you need atomic updates across several keys at once, which no single CRDT gives you.
• Anti-Entropy and Repair -- how CRDT state actually flows between replicas.
• Buckets, Keys, and Objects -- the plain-object model CRDTs sit alongside.