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:
[]
= "0.1.3"
To enable Probabilistic Data Structures (HyperLogLog, CountMinSketch, etc.), add the probabilistic feature:
[]
= { = "0.1.3", = ["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_jsonto 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
Readerandmerge_from_readerslogic. 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
Usage
JSON Pathway (Web API)
use SerdeCapnpBridge;
use json;
let json1 = json!;
let json2 = json!;
let merged = merge_json_values.unwrap;
Zero-Copy Pathway (Binary/Storage)
use ;
let gc1_bytes = gc1.to_capnp_bytes;
let gc2_bytes = gc2.to_capnp_bytes;
let reader1 = new;
let reader2 = new;
let merged_gc = merge_from_readers.unwrap;
Compaction
use ;
use json;
// JSON pathway
let values = vec!;
let compacted = compact_json_values.unwrap;
// Cap'n Proto pathway (faster, no JSON overhead)
let compacted_bytes = compact_capnp_bytes.unwrap;
License
MIT