sync_engine/merkle/
mod.rs

1//! Path-based Merkle tree for efficient sync verification.
2//!
3//! # Design
4//!
5//! Uses reverse DNS object IDs to create a natural tree structure:
6//!
7//! ```text
8//! uk.nhs.patient.record.123
9//!
10//! Becomes:
11//!
12//! uk ─────────────────── hash(nhs)
13//! └── nhs ───────────── hash(patient)
14//!     └── patient ───── hash(record)
15//!         └── record ── hash(123, 456, ...)
16//!             ├── 123 ─ leaf hash
17//!             └── 456 ─ leaf hash
18//! ```
19//!
20//! # Storage Strategy
21//!
22//! Merkle nodes are stored **separately** from data in Redis:
23//!
24//! - `data:uk.nhs.patient.record.123` → SyncItem (evictable by tan curve)
25//! - `merkle:hash:uk.nhs.patient.record` → 32-byte hash (NEVER evicted)
26//! - `merkle:children:uk.nhs.patient.record` → sorted set of child:hash pairs
27//!
28//! This allows efficient sync verification even when data is evicted from cache.
29//!
30//! # Sync Protocol
31//!
32//! 1. Client sends their root hash
33//! 2. If different, server sends top-level children with hashes
34//! 3. Client identifies differing branches
35//! 4. Drill down until leaves are reached
36//! 5. Transfer only the differing items
37//!
38//! This is O(diff_size × tree_depth) instead of O(total_items).
39
40mod path_tree;
41mod redis_store;
42mod sql_store;
43
44pub use path_tree::{MerkleBatch, MerkleNode, PathMerkle};
45pub use redis_store::RedisMerkleStore;
46pub use sql_store::SqlMerkleStore;
sync_engine/merkle/mod.rs

sync_engine/merkle/
mod.rs
