sync_engine/merkle/
mod.rs

1// Copyright (c) 2025-2026 Adrian Robinson. Licensed under the AGPL-3.0.
2// See LICENSE file in the project root for full license text.
3
4//! Path-based Merkle tree for efficient sync verification.
5//!
6//! # Design
7//!
8//! Uses reverse DNS object IDs to create a natural tree structure:
9//!
10//! ```text
11//! uk.nhs.patient.record.123
12//!
13//! Becomes:
14//!
15//! uk ─────────────────── hash(nhs)
16//! └── nhs ───────────── hash(patient)
17//!     └── patient ───── hash(record)
18//!         └── record ── hash(123, 456, ...)
19//!             ├── 123 ─ leaf hash
20//!             └── 456 ─ leaf hash
21//! ```
22//!
23//! # Storage Strategy
24//!
25//! Merkle nodes are stored **separately** from data in Redis:
26//!
27//! - `data:uk.nhs.patient.record.123` → SyncItem (evictable by tan curve)
28//! - `merkle:hash:uk.nhs.patient.record` → 32-byte hash (NEVER evicted)
29//! - `merkle:children:uk.nhs.patient.record` → sorted set of child:hash pairs
30//!
31//! This allows efficient sync verification even when data is evicted from cache.
32//!
33//! # Sync Protocol
34//!
35//! 1. Client sends their root hash
36//! 2. If different, server sends top-level children with hashes
37//! 3. Client identifies differing branches
38//! 4. Drill down until leaves are reached
39//! 5. Transfer only the differing items
40//!
41//! This is O(diff_size × tree_depth) instead of O(total_items).
42
43mod path_tree;
44mod cache_store;
45mod sql_store;
46
47// Keep redis_store for backwards compatibility during migration
48mod redis_store;
49
50pub use path_tree::{MerkleBatch, MerkleNode, PathMerkle};
51pub use cache_store::MerkleCacheStore;
52pub use sql_store::SqlMerkleStore;
53
54// Re-export old name for backwards compatibility
55#[deprecated(since = "0.2.0", note = "Use MerkleCacheStore instead")]
56pub use redis_store::RedisMerkleStore;
sync_engine/merkle/mod.rs

sync_engine/merkle/
mod.rs
