mrdt — Mergeable Replicated Data Types#

Replicated data types with three-way merges. Two concurrent versions of a value reconcile against their lowest common ancestor, exactly as Git merges branches: merge ~ancestor a b. Values carry no replication metadata — no vector clocks, dots, or tombstones in the data — because all merge context comes from the ancestor that the version history provides.

This is the complement of crdt: CRDTs join two states with a semilattice merge and pay for it with metadata inside the values; MRDTs keep values plain and pay with a version DAG outside them. The DAG also buys a garbage collection story CRDTs lack (see below).

Installation#

Install with opam:

$ opam install mrdt

If opam cannot find the package, it may not yet be released in the public opam-repository. Add the overlay repository, then install it:

$ opam repo add samoht https://tangled.org/gazagnaire.org/opam-overlay.git
$ opam update
$ opam install mrdt

Types#

Derived from the relational merge specifications of Kaki et al. (OOPSLA 2019):

• Counter — merge ~ancestor:l a b = l + (a − l) + (b − l); add, sub and mult all converge.
• Make_pair (A) (B) — componentwise merge of mergeable components.
• Make_set (E) — membership merges as (l ∩ a ∩ b) ∪ (a − l) ∪ (b − l): fresh additions survive, an observed removal wins over a concurrent retain.
• Make_queue (E) — at-least-once FIFO queue: an element popped in either branch never reappears, pushes in either branch survive, relative order is preserved, and concurrent pushes are ordered by the arbitration order E.compare.
• Make_map (K) (V) — keys merge set-like (remove wins over concurrent update), surviving values merge with V.merge against the ancestor value, or V.zero where the key is absent.

Replicas and garbage collection#

Make_replica (S) turns a mergeable type into a distributed object with a fixed, known number of replicas. Each replica keeps a version DAG; update commits, pull syncs with a peer (no-op / fast-forward / LCA merge, with criss-cross histories resolved by recursive LCA merging as in Git).

History is compacted using the known replica count: versions carry version vectors, replicas exchange acknowledgement vectors on every sync, and a version acknowledged by all replicas can never again be an LCA, so everything below the acknowledged frontier collapses into one snapshot. This is the observation of Soundarapandian et al. (PLDI 2022): a commit merged into every replica's public branch frees its ancestors. Steady-state memory is proportional to the work since the frontier, not to the full history — the cost model that makes long-lived collaborative documents deployable. The flip side is liveness: one unreachable replica pins the frontier until it syncs again.

Status#

The test suite is the specification: test/test_mrdt.ml encodes the paper's worked examples verbatim (counter Fig. 2, queue Figs. 5–6 and 8, pair Sec. 4.1, map Rel-Merge), the replica/GC contract, and hostile-input cases (non-ancestor merges, mismatched replica groups, overflow, deep criss-cross); fuzz/fuzz_mrdt.ml checks the merge laws and exact-value convergence with compaction over randomized schedules for counters, queues and maps. All implemented and green.

bench/bench.ml exercises large merge and replica scenarios and reports throughput and words/op (MEMTRACE=… dune exec ocaml-mrdt/bench/bench.exe profiles it); merges are written to keep structural sharing and avoid materializing relations, so steady-state allocation stays low.

Roadmap, in order:

1. Text: lift the merge3 line-level 3-way merge as a mergeable type; move the typed merges shared with irmin's Merge module into one home.
2. Sync protocol: an I/O-free wire machine for pull over a transport (patch exchange instead of whole-replica access), plus an Eio adapter.
3. JavaScript middleware: js_of_ocaml/wasm_of_ocaml build published to npm with TypeScript definitions, and a demo collaborative app.

Related work#

• Gowtham Kaki, Swarn Priya, KC Sivaramakrishnan, Suresh Jagannathan, "Mergeable Replicated Data Types", OOPSLA 2019 — the relational merge specifications implemented here. The paper's OCaml/Irmin artifact lives in gowthamk/ocaml-irmin.
• Vimala Soundarapandian, Adharsh Kamath, Kartik Nagar, KC Sivaramakrishnan, "Certified Mergeable Replicated Data Types", PLDI 2022 (prismlab/peepul) — F* verified MRDTs; source of the all-replicas-acknowledged GC condition.
• irmin — block-level two-phase 3-way merge over a content-addressed store; this package is the typed, store-free layer.
• crdt — state-based CRDTs with two-way semilattice merges, for when no shared version history is available.

License#

ISC.