Module merkle 

Path-based Merkle tree for efficient sync verification.

Design

Uses reverse DNS object IDs to create a natural tree structure:

uk.nhs.patient.record.123

Becomes:

uk ─────────────────── hash(nhs)
└── nhs ───────────── hash(patient)
    └── patient ───── hash(record)
        └── record ── hash(123, 456, ...)
            ├── 123 ─ leaf hash
            └── 456 ─ leaf hash

Storage Strategy

Merkle nodes are stored separately from data in Redis:

• data:uk.nhs.patient.record.123 → SyncItem (evictable by tan curve)
• merkle:hash:uk.nhs.patient.record → 32-byte hash (NEVER evicted)
• merkle:children:uk.nhs.patient.record → sorted set of child:hash pairs

This allows efficient sync verification even when data is evicted from cache.

Sync Protocol

1. Client sends their root hash
2. If different, server sends top-level children with hashes
3. Client identifies differing branches
4. Drill down until leaves are reached
5. Transfer only the differing items

This is O(diff_size × tree_depth) instead of O(total_items).

Structs

MerkleBatch

Batch of Merkle updates to apply atomically.

MerkleCacheStore

Redis cache for SQL Merkle tree.

MerkleNode

A node in the path-based Merkle tree.

PathMerkle

Manages path-based Merkle tree operations.

RedisMerkleStore

Redis-backed Merkle tree storage.

SqlMerkleStore

SQL-backed Merkle tree storage (ground truth).