/crdt-deflation

CRDTs (Conflict-free Replicated Data Types) with with a "deflating" approach

Primary LanguageKotlinMIT LicenseMIT

CRDT Deflation

Lightweight Kotlin implementations of CRDTs (Conflict-free Replicated Data Types) together with a "deflating" approach: buffer local operations and flush them to the underlying CRDT to reduce state growth. The repo also contains microbenchmarks (JMH), a memory benchmark, and a small web app that visualizes buffering effects for text CRDTs.

Modules

  • Root library:
    • Counters: GrowOnlyCounter, Counter (PN-Counter style), DeflatingCounter (buffered writes)
    • Sets: GrowOnlySet, ORSetAddWins (add-wins), DeflatingORSetAddWins (buffered adds/removes)
  • benchmark-jmh: JMH microbenchmarks comparing baseline vs deflating variants
  • benchmark-memory: Measures retained heap size using com.volkhart.memory javaagent
  • crdt-buffer-bench: Vite/React app to explore buffering message sizes for Yjs and Automerge

Build and Test

  • Build everything: ./gradlew build

Using the Library (examples)

Counter (PN-Counter with deflating wrapper):

val d = crdt.deflation.counter.DeflatingCounter(crdt.deflation.core.ReplicaId("A"))
d.inc(5)
d.dec(3)
println(d.value())        // 2 (includes pending)
println(d.stableValue())  // 0 (base only)
d.flush()
println(d.value())        // 2 (now stable)

Add-Wins OR-Set (deflating variant):

val defl = crdt.deflation.sets.DeflatingORSetAddWins<String>(crdt.deflation.core.ReplicaId("A"))
defl.add("x")
defl.remove("x")
println(defl.elements())   // reflects pending

defl.flush()               // publish pending adds/removes to base

JMH Microbenchmarks

  • Run all benchmarks:
    • ./gradlew :benchmark-jmh:jmh
  • The benchmark ORSetAddWinsJmh supports params (set via JMH runtime):
    • impl: baseline | deflating
    • ops: e.g., 10000
    • keySpace: e.g., 100000
    • removeProb: e.g., 0.2
    • flushEvery: e.g., 0, 64, 256
    • seed: RNG seed

Memory Benchmark

Measures retained size using a javaagent.

  • Run:
    • ./gradlew :benchmark-memory:run
  • The Gradle task automatically locates and attaches the com.volkhart.memory:measurer javaagent.
  • Entry points:
    • crdt.deflation.benchmem.MemoryBenchmarkKt (OR-Set)
    • crdt.deflation.benchmem.MemoryBenchmarkCounterKt (Counters)

Web App: CRDT Buffering Bench

A simple Vite/React app comparing message sizes for buffered vs immediate strategies in Yjs and Automerge.

  • Development server:
  • Build static site: npm run build

License

MIT (See LICENSE)