Disk-backed Mmr
- Lingua principale
- Rust
- Stelle
- 104
- Fork
- 138
- Merge medio
- 1g 13h
- PR unite (30g)
- 56
Descrizione
# Support a partially on-disk `Mmr`
## Motivation
`Mmr` currently holds its entire postorder node buffer in memory. Growth is ~64 bytes per leaf (`2n − popcount(n)` nodes × 32-byte `Word`). For the block-hash MMR at a 3s block time:
| Horizon | Size |
|---|---|
| 6 months | ~335 MB |
| 1 year | ~670 MB |
| 10 years | ~6.7 GB |
Not urgent for RAM at one leaf per block, but worth designing the seam early. Full-buffer scans (serialization, startup deserialization, `PartialEq`) go linear in the multi-GB range first; per-transaction/per-note MMRs would make the disk tier a hard requirement (~670 GB/year at 1k leaves/block).
## Key properties
Based on the chunked storage refactor from: https://github.com/0xMiden/miden-vm/pull/3562:
- The node buffer is strictly append-only: every full 32 KiB `NodeStore` chunk is immutable forever — no cache invalidation, lock-free reads of frozen chunks, chunk index is a natural storage key.
- `add` only reads the current peaks (≤64 words), so with peaks cached in memory, appends require zero historical reads.
- Required resident set: `forest` (one `usize`), peaks (≤2 KiB), partial tail chunk (≤32 KiB), plus a cache of full chunks for `open()`/`peaks_at`/`get_delta`.
## Options
### A. Make `Mmr` generic over a chunk-granular storage trait
Existing `NodeStore` becomes the default in-memory impl (no downstream breakage, keeps miden-crypto no_std); a RocksDB backend lives in the node crate, e.g. key = chunk index, value = 32 KiB chunk, full chunks + `forest` committed in the same `WriteBatch` as the block.
```rust
pub trait ChunkStore {
type Error;
fn num_chunks(&self) -> usize;
fn get_chunk(&self, idx: usize) -> Result>, Self::Error>;
fn append_chunk(&mut self, idx: usize, chunk: &[Word]) -> Result<(), Self::Error>;
}
```
Cost is the API ripple in miden-crypto: `Index` → fallible `get_node`, a storage error variant on `open`/`peaks_at`/`get_delta`, and `MmrNodeIter` streaming owned `Arc` chunks instead of borrowed slices.
### B. `PartialMmr` + external archive
Leave `Mmr` untouched. The node keeps a `PartialMmr` (peaks + tracked paths) in memory and streams the full buffer to its own storage via the existing `nodes_from(start)` sync API, serving historical `open()` from that storage. Least invasive to miden-crypto, but duplicates `collect_merkle_path_and_value`'s postorder walk downstream (or requires extracting it over an abstract reader).
### C. mmap'd flat append-only file
Fixed 32-byte records at `index * 32`; the OS page cache provides partial residency for free. Operationally the simplest, but can't live in a no_std crate, involves unsafe mmap handling, and loses atomic batching of MMR state with the rest of the node's RocksDB state.
## Open questions
- Which operations must be served from the cold tier (historical `open()`? `get_delta`?), since that determines how much of the read path needs to be storage-aware.
- Tail-chunk durability: write-through per block vs. rebuilding the last ≤1023 nodes from the leaf source on restart.
Guida per i contributori
Apri la guida per i contributori
Valutazione
Questa issue non è ancora stata valutata.