crdt-data-types 0.1.4

High-performance CRDT library with dual pathways: JSON-native for web APIs and Cap'n Proto zero-copy for binary transport
Documentation

CRDT Data Types (Rust)

A high-performance library of Conflict-free Replicated Data Types (CRDTs) built on Cap'n Proto for zero-copy deserialization, with a native JSON-first gear for seamless Web API integration.

Includes a demo-server with a rogue-like game to demonstrate CRDT merge ops. See how long you can survive! ⚔️

Installation

Add this to your Cargo.toml:

[dependencies]
crdt-data-types = "0.1.4"

To enable Probabilistic Data Structures (HyperLogLog, CountMinSketch, etc.), add the probabilistic feature:

[dependencies]
crdt-data-types = { version = "0.1.4", features = ["probabilistic"] }

The "Two-Gear" Strategy

This library is designed to support different performance requirements by providing two optimized integration pathways ("gears").

🏎️ Low Gear: JSON-Native

Best for: Web APIs, Frontend synchronization, and developer simplicity.

  • How it works: Uses serde_json to deserialize directly into Rust structs, performs in-memory merging, and serializes back to JSON.
  • Performance: Fastest for JSON-locked environments (avoids the ~1ms "translation tax" between JSON and binary formats).
  • Complexity: $O(N \log N)$ or $O(N)$ depending on the data type.

🚀 High Gear: Capnp-Native

Best for: High-throughput distributed systems, persistent storage, and massive state synchronization.

  • How it works: Operates directly on Cap'n Proto byte buffers using specialized Reader and merge_from_readers logic. Uses Sorted Vector Layouts to enable $O(N)$ linear-time merging, bypassing full struct allocations and expensive hash calculations.
  • Performance: 2.5x - 3x faster than JSON for both flat and nested data types.
  • Trade-off: Requires binary transport (gRPC, P2P) or scale large enough to justify the translation overhead. Alternatively, use a reverse proxy which pre-converts to capnp.

Performance Tipping Point

CRDT Type JSON-Native (N=1000) Capnp-Native (N=1000) Winner
GCounter 986 µs 374 µs Capnp (2.6x fast)
ORSet 650 µs ~270 µs Capnp (2.4x fast)

[!NOTE] With the Sorted Vector Layout optimization, Cap'n Proto zero-copy merging now dominates across both flat and complex nested types.


Supported CRDTs

  • Counters: GCounter, PNCounter
  • Sets: GSet, ORSet, LWWSet
  • Registers: LWWRegister, FWWRegister, MVRegister
  • Maps: LWWMap, ORMap
  • Probabilistic (Optional, requires features = ["probabilistic"]): HyperLogLog, CountMinSketch, RoaringBitmap, TDigest, TopK
  • Utilities: VectorClock

Algorithm References

Type Algorithm Citation
GCounter Grow-only Counter Shapiro et al., 2011
PNCounter Positive-Negative Counter Shapiro et al., 2011
GSet Grow-only Set Shapiro et al., 2011
ORSet Observed-Remove Set Bieniusa et al., 2012
)
LWWSet Last-Writer-Wins Set Shapiro et al., 2011
LWWRegister Last-Writer-Wins Register Shapiro et al., 2011
FWWRegister First-Writer-Wins Register Shapiro et al., 2011
MVRegister Multi-Value Register Shapiro et al., 2011
LWWMap LWW-Element Map Composition of LWWRegister per key
ORMap OR-Element Map Composition of ORSet semantics
VectorClock Vector Clock Fidge, 1988; Mattern, 1989
HyperLogLog Cardinality Estimation Flajolet et al., 2007
CountMinSketch Frequency Estimation Cormode & Muthukrishnan, 2005
TDigest Quantile Estimation Dunning & Ertl, 2019
RoaringBitmap Compressed Bitmap Lemire et al., 2016
TopK Heavy Hitters CMS + Min-Heap composition

Usage

JSON Pathway (Web API)

use crdt_data_types::SerdeCapnpBridge;
use serde_json::json;

let json1 = json!({ "counters": { "node1": 10 } });
let json2 = json!({ "counters": { "node2": 20 } });

let merged = SerdeCapnpBridge::merge_json_values("GCounter", &[json1, json2]).unwrap();

Zero-Copy Pathway (Binary/Storage)

use crdt_data_types::{GCounter, GCounterReader, Crdt};

let gc1_bytes = gc1.to_capnp_bytes();
let gc2_bytes = gc2.to_capnp_bytes();

let reader1 = GCounterReader::new(&gc1_bytes);
let reader2 = GCounterReader::new(&gc2_bytes);

let merged_gc = GCounter::merge_from_readers(&[reader1, reader2]).unwrap();

Compaction

use crdt_data_types::compaction::{compact_json_values, compact_capnp_bytes};
use serde_json::json;

// JSON pathway
let values = vec![json1, json2, json3];
let compacted = compact_json_values("GCounter", &values).unwrap();

// Cap'n Proto pathway (faster, no JSON overhead)
let compacted_bytes = compact_capnp_bytes("GCounter", &[&bytes1, &bytes2]).unwrap();

Changelog

v0.1.4

  • Usability: SerdeCapnpBridge now accepts case-insensitive CRDT type names (e.g., "g_counter", "gcounter", "GCounter"). This simplifies integration with external systems that use snake_case.

License

MIT