CRDT Data Types (Rust)
High-performance Conflict-free Replicated Data Types (CRDTs) with dual-pathway optimization for Web APIs and zero-copy storage.
Philosophy: The "Two-Gear" Strategy
crdt-data-types is designed to support different performance requirements by providing two optimized integration pathways ("gears"):
- JSON-Native (Low Gear): Seamless integration with Web APIs and frontends. Uses
serde_jsonfor direct struct manipulation. - Capnp-Native (High Gear): Zero-copy, high-throughput merging for distributed systems and storage engines.
Architecture
┌─────────────────────────────────────────────────────────────┐
│ Application Layer │
│ • Web APIs (JSON) │
│ • Storage Engines (Binary) │
└─────────────────────────────────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────┐
│ SerdeCapnpBridge (The Bridge) │
│ • Validates JSON input │
│ • Normalizes snake_case / PascalCase │
└─────────────────────────────────────────────────────────────┘
│ │
▼ ▼
┌─────────────────────────────┐ ┌─────────────────────────────┐
│ Low Gear: JSON-Native │ │ High Gear: Capnp-Native. │
│ • serde_json deserialization│ │ • Zero-copy Reader access │
│ • In-memory struct merge │ │ • Linear-time merge O(N) │
│ • Best for: Web/Frontend │ │ • Best for: Storage/Network │
└─────────────────────────────┘ └─────────────────────────────┘
Features
- Dual-Pathway Merging: Choose between developer-friendly JSON or performance-critical Cap'''n Proto.
- Zero-Copy Deserialization:
merge_from_readersoperates directly on byte buffers without allocation. - Comprehensive CRDT Suite:
- Counters:
GCounter,PNCounter - Sets:
GSet,ORSet,LWWSet - Registers:
LWWRegister,FWWRegister,MVRegister - Maps:
LWWMap,ORMap
- Counters:
- Probabilistic Structures:
HyperLogLog,CountMinSketch,RoaringBitmap,TDigest,TopK(via feature flag). - Vector Clocks: Standard logical clocks for causality tracking.
- Compaction: Utilities to squash history and reduce payload size.
- Binary Deltas: Apply small, strict delta updates directly to binary states (skip JSON).
- Batch Processing: Amortize IO overhead by applying multiple deltas in one pass.
- Additive Merging: Sum values for GCounter/PNCounter (vs Max/Union) for flush operations.
Add to your
Cargo.toml:
- Additive Merging: Sum values for GCounter/PNCounter (vs Max/Union) for flush operations.
Add to your
[]
= "0.1.10"
# Optional: Enable probabilistic structures
# crdt-data-types = { version = "0.1.10", features = ["probabilistic"] }
JSON Pathway (Web API)
use ;
use json;
let json1 = json!;
let json2 = json!;
// Merges JSON directly
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;
// Merges without deserializing full structs
let merged_gc = merge_from_readers.unwrap;
High-Performance Delta API (Batching)
For maximum throughput (e.g., ingestion pipelines), use the batch delta API:
// Apply 3 binary deltas in a single pass
let final_state = apply_batch_capnp_deltas.unwrap;
State Accumulation (Additive Merge)
For counters (GCounter, PNCounter), standard merging uses MAX (greatest value seen). Use add_accumulated_state when you want to sum differences (e.g., flushing a temporary counter to a main counter):
// Standard merge: MAX(10, 5) = 10
// Additive merge: 10 + 5 = 15
let current = json!;
let flush_delta = json!;
let new_state = add_accumulated_state.unwrap;
// Result: node1 = 15
Performance Tipping Point
| Operation | JSON-Native (N=100) | Capnp-Native (N=100) | Winner |
|---|---|---|---|
| GCounter Merge | 986 µs | 374 µs | Capnp (2.6x fast) |
| ORSet Merge | 650 µs | ~270 µs | Capnp (2.4x fast) |
| ORSet Delta | 52 µs | 35 µs | Capnp (1.5x fast) |
| Batch Apply (10 ops) | ~25 µs (est) | 5.2 µs | Capnp (4.8x fast) |
Testing
Comprehensive test suite covering unit logic, bridge integration, and property-based fuzzing:
| Test Suite | Count | Description |
|---|---|---|
| Unit Tests | 3 ✅ | Core logic & compaction |
| Basic Tests | 6 ✅ | Standard CRDT operations |
| Bridge Tests | 6 ✅ | JSON <-> Capnp bridge & case-insensitivity |
| Coverage Tests | 17 ✅ | Edge cases, compaction, & vector clocks |
| Delta Tests | 11 ✅ | Binary Cap'n Proto deltas, JSON delta logic |
| Additive Merge | 3 ✅ | State accumulation & counter summation |
| Property Tests | 38 ✅ | Proptest fuzzing for commutativity/associativity & delta equivalence |
| Total | 84 ✅ | ~70% code coverage |
Run tests with:
Changelog
v0.1.4
- Usability:
SerdeCapnpBridgenow accepts case-insensitive CRDT type names (e.g., "g_counter", "gcounter", "GCounter"). This simplifies integration with external systems that use snake_case.
License
Copyright (c) 2026 Adrian Robinson. All rights reserved.