# v2.0 — Page-based disk-backed storage engine > Date: 2026-05-15 > Author: design draft > Status: Proposed > Supersedes: nothing yet — v1.x in-memory-everything model still in production ## Why v2.0 v1.x is a memory database with WAL/snapshot persistence. It assumes the entire working set fits in RAM. v1.9.x patched the symptoms (jemalloc to bound allocator retention, history on disk to stop tracker inflation) but the architecture still requires RAM proportional to dataset size. For ShadowMan-Zoe today: 2.1 M docs / 1.6 GB tracker / 3-4 GB RSS — fits comfortably in 11 GB host. For ShadowMan-at-Battery scale (target: 20 M+ docs, files, telemetry rollups), we'll be back at the same wall. **The constraint we're hitting:** RAM is the cap. Eviction is a fallback, not a design feature. WAL fallback for evicted docs is O(WAL size) per read — works for tens of evictions, falls over at thousands. **MySQL/InnoDB's design choice:** RAM is a configured budget (the buffer pool). Disk is the canonical store. The buffer pool caches hot pages. A 100 GB database on a 4 GB pool just means more cache misses, not OOM. v2.0 adopts the buffer-pool model. ## High-level architecture ``` ┌─────────────────────────────────────────────────────────────────┐ │ gRPC handlers │ │ (Insert / Get / Update / Find / Subscribe etc.) │ │ unchanged wire API │ └──────────────────────────────┬──────────────────────────────────┘ │ ┌──────────────────────────────▼──────────────────────────────────┐ │ Document API layer │ │ - parses JSON wire bytes once with yyjson (replaces nlohmann) │ │ - converts to compact binary doc record on write │ │ - converts binary back to JSON on read │ └──────────────────────────────┬──────────────────────────────────┘ │ ┌──────────────────────────────▼──────────────────────────────────┐ │ Storage engine (NEW in v2.0) │ │ ┌─────────────────────────────────────────────────────────────┐ │ │ │ BufferPool (bounded LRU page cache) │ │ │ │ buffer_pool_size_mb (default 1024) — hard RAM cap │ │ │ └─────────────────────────────────────────────────────────────┘ │ │ ┌─────────────────────────────────────────────────────────────┐ │ │ │ B+ tree indexes (one per collection) │ │ │ │ key: doc_id → value: page_offset │ │ │ └─────────────────────────────────────────────────────────────┘ │ │ ┌─────────────────────────────────────────────────────────────┐ │ │ │ Page files: {data_dir}/pages/{collection}.dat │ │ │ │ 16 KB pages, slotted-page format │ │ │ └─────────────────────────────────────────────────────────────┘ │ │ ┌─────────────────────────────────────────────────────────────┐ │ │ │ WAL (mostly unchanged) │ │ │ │ now records page-level redo records │ │ │ └─────────────────────────────────────────────────────────────┘ │ └─────────────────────────────────────────────────────────────────┘ ``` ## Phasing This is a multi-release effort. Three phases that each ship value without depending on the next one. ### Phase A — `yyjson` swap (option 1) - Replace `nlohmann::json` with `yyjson` on the parse hot path (gRPC request body parsing, WAL deserialize, snapshot deserialize) - Keep `nlohmann::json` in the API for now (it's used everywhere) - Expected gain: 3-5× faster parse, ~20% reduction in tree-node overhead from `yyjson`'s flatter representation **Ship target:** v1.10.0 **Effort:** 1-2 weeks **Risk:** low — drop-in API change in a few hot files; tests cover regressions ### Phase B — Lazy / binary doc representation (option 2) - New `Document` storage: `std::vector binary` (BSON or custom packed format) instead of `nlohmann::json data` - `Document::data()` is a lazy accessor that parses the binary on demand, used only by paths that need a JSON view (gRPC response serialization, projection in views, etc.) - Write path: deserialize wire JSON once with `yyjson`, convert to binary, store - Read path: stay binary as long as possible; convert to JSON only when crossing the gRPC boundary **Ship target:** v1.11.0 or v2.0-alpha **Effort:** 3-5 weeks **Risk:** medium — touches `Document`, every read-write path, snapshot format. Snapshot format v6 needed (read v3-v5 on the way in, migrate). **Expected memory drop on Zoe-shape workload:** - Tracker: 1.6 GB → ~500-700 MB (close to raw JSON wire size + Document metadata) - VmRSS (with v1.9.4 jemalloc): 3-4 GB → ~1-1.5 GB ### Phase C — Page-based storage + buffer pool (option 3) The big rewrite. The Document API stays binary (from Phase B); we swap out the storage layer underneath. **Ship target:** v2.0 **Effort:** 2-3 months **Risk:** high — new on-disk format, B+ tree implementation, recovery semantics, migration tooling Subphases inside Phase C: #### C.1 Storage primitives - `Page` struct: 16 KB, fixed header + slotted-page body - `PageFile`: one file per collection, mmap'd or read via positional pread - `BufferPool`: bounded LRU map, page_id → in-memory page buffer, configurable `buffer_pool_size_mb`, dirty-page write-back on eviction #### C.2 B+ tree index - `BPlusTree` parameterized on key type (string for doc_id) - Index pages live in the same page file as data pages - Index pages also cached in BufferPool — index reads cost is bounded by the same pool #### C.3 Storage API replacement - `MemoryStore::insert/update/get/find` route to the new engine - The wire API is identical - `coll->documents` hash map goes away - `coll->vectors` may stay in RAM for vector search (hot, small) or move to page-stored vectors per doc #### C.4 Recovery and crash safety - WAL records become page-level redo logs: `(page_id, offset, before, after)` - Recovery: load checkpoint LSN, replay WAL forward, redo each page modification - Snapshots become "checkpoints": flush all dirty pages and record an LSN. The lz4 .dat snapshot format goes away. #### C.5 Eviction-pressure machinery - Most of v1.7.0's eviction logic goes away — the BufferPool's own page-LRU is the eviction - `max_memory_mb` becomes `buffer_pool_size_mb` - "evicted stubs" / WAL fallback / docWalSeq_ tracking all disappear - Eviction is now O(1) page replacement instead of O(N) doc scanning ## Format details ### Slotted page layout (16 KB) ``` +--------------------------------------------------------------+ | Page header (32 B): | | magic(4) + page_id(8) + lsn(8) + slot_count(2) + | | free_space_offset(2) + checksum(8) | +--------------------------------------------------------------+ | Slot directory (4 B per slot): | | [offset(2) + length(2)] × slot_count | +--------------------------------------------------------------+ | ... free space grows down from free_space_offset ... | | | | | | | | ... record data grows up from end ... | | [record N data: doc_id_len + doc_id + bin_doc_len + bin_doc] | | [record N-1 data: ...] | +--------------------------------------------------------------+ ``` Slotted pages are battle-tested (PostgreSQL, InnoDB, SQLite use variants). Records inside a page can be variable length. Slot directory at the top is sorted by slot_id so a doc_id lookup costs one binary search within the page. ### Doc-record binary format (per slot) ``` +----------------------------------------------------+ | Header (24 B): | | version(8) + createdAt(8) + updatedAt(8) | +----------------------------------------------------+ | Metadata: encrypted(1) + node_id_len(2) + node_id | +----------------------------------------------------+ | Data: bin_doc_len(4) + bin_doc | +----------------------------------------------------+ ``` `bin_doc` is either BSON or a packed-JSON we define. BSON is well-known but heavyweight in places; let's spec a small custom format that's a 1:1 mapping of JSON values to length-tagged bytes (close to "what yyjson outputs as a binary tape"). Decoding back to JSON is just a serializer. ### Vector storage Vectors are dense `float[dim]`. They get their own page section attached to the doc record or, for `vector_dimension > 4096`, a separate "vector page" referenced by the doc's vector_offset field. ### History storage (.hlog) **Unchanged from v1.9.0.** The HistoryStore design we just shipped is already disk-backed and page-friendly. v2.0 keeps it as-is. ## Migration v1.x → v2.0 needs a one-time data migration: 1. Boot v2.0 with `--migrate-from-v1` flag 2. Reads latest v1 snapshot + WAL into memory (last time we'll do this) 3. Writes pages out to the new format 4. Renames the data dir so subsequent boots use the v2 format 5. v1 data is preserved alongside for rollback Rollback path: rename data dir back, downgrade deb, restart. We pin v1.11.x and v2.0 in apt so operators can choose; we don't auto-migrate. ShadowMan-cpp gets a migration runbook. ## What we lose - **Snapshot files go away** — replaced by checkpoints + page files. Backup tooling needs an update (now it's a `cp -r` of the page files + WAL). - **`getAllDocuments`** scans the B+ tree, no longer returns a vector of fully-loaded Documents. Becomes an iterator-style API. Most callers want pagination anyway. - **WAL replay for evicted docs (loadEvictedDocument)** disappears. The whole eviction-stub concept goes away — eviction is page-level. - **Some flexibility**: page sizes, B+ tree node sizes are fixed. To store a single 10 MB doc you need overflow pages. Not common in our use case but a constraint to be aware of. ## What we gain | Property | v1.9.x | v2.0 | |------------------------------------|-------------------------|---------------------------------------| | Dataset size limit | bounded by RAM | bounded by disk | | RAM usage | grows with dataset | bounded by `buffer_pool_size_mb` | | Read latency (cache hit) | hash map lookup, µs | B+ tree lookup, low µs | | Read latency (cache miss) | WAL fallback, ms-s | page read, sub-ms | | Recovery time | parse all snapshot data | replay WAL forward | | Memory predictability | rough | exact | | Document tree heap overhead | 4-5× | ~1.1× (binary record) | | Eviction work under pressure | O(N docs) scan + stub | O(1) page replacement | | Compatible with current API | yes | yes | | Compatible with current data | yes (in-place) | one-time migration | ## Open design questions 1. **B+ tree vs hash index per collection** — B+ tree gives ordered scans for `find` with sort, hash gives faster point lookups. Default to B+ tree (sortable); add hash as opt-in via collection option (`index_type: hash`). 2. **Bypass for very small collections** — `_views`, `_collection_meta`, `_migrations` are small (<100 docs); keeping them in RAM is fine. Add a `cache_all: true` option per collection that pins everything in pool. 3. **Replication payload format** — currently sends `Document` JSON in ReplicationEntry. v2.0 could send the binary record (smaller, faster on both sides). Wire compatibility matters; need to version-tag the payload. 4. **Vector search** — currently `SimilaritySearch` brute-force scans the entire `coll->vectors` map. For v2.0 we either keep vectors pinned in RAM (works for current scale) or build a proper ANN index (HNSW, IVF). Decision deferred — keep RAM-pinned vectors in v2.0, add ANN in v2.1+. 5. **Should we just use RocksDB / LMDB / SQLite underneath?** RocksDB gives us LSM tree + buffer pool + WAL + compaction for free. Argument for: huge engineering savings, battle-tested. Argument against: lose control of the on-disk format, harder to reason about exact memory shape, more deps. Worth a 1-week spike to prototype before committing to a homegrown B+ tree. ## Acceptance criteria (v2.0) - ShadowMan-Zoe runs for 30 days with **RSS bounded at `buffer_pool_size_mb × 1.1`** under sustained load. No SIGUSR2 intervention. No OOM kills. - 100 M doc dataset feasible on a 4 GB pool: cold reads from unpinned pages stay under 50 ms p99. - gRPC API surface is **identical** to v1.x; no client-side changes. - v1.x → v2.0 migration completes within 2× the original snapshot load time on the same hardware. - All existing `tests/test_*` pass against v2.0 (some need updates for removed APIs, but no test logic should change). ## Timeline (rough) | Phase | Releases | Calendar | Engineer-weeks | |---------|--------------|----------|----------------| | Phase A | v1.10.0 | week 1-2 | 1.5 | | Phase B | v1.11.0 | week 3-7 | 4 | | C.1-C.2 | v2.0-alpha1 | week 8-14 | 6 | | C.3-C.4 | v2.0-alpha2 | week 15-20 | 5 | | C.5 | v2.0-beta | week 21-22 | 1.5 | | Bake | v2.0 | week 23-24 | 1.5 | | **Total** | — | **~6 mo** | **~19 wks** | Aggressive but each phase is independently shippable. If C is paused at any point, we still have the (1)+(2) gains from A+B. ## Decision points before starting 1. **Confirm phase A+B are worth shipping ahead of C.** They're real wins (~70% memory cut for the doc store layer), shippable in ~5 weeks, and don't commit us to the full rewrite. If we go straight to C we keep nlohmann + parsed trees in heap during the transition. 2. **Spike: RocksDB-backed prototype vs homegrown B+ tree.** Worth 1 week of effort to compare; might collapse the C estimate significantly. 3. **Migration window on Zoe.** v1 → v2 migration is offline on first boot. For a 2 M doc dataset that's ~5 minutes of downtime. Probably acceptable; confirm with operators. ## Out of scope for v2.0 - Distributed storage (sharding across nodes). v1.x replication stays. - Compaction strategies beyond basic LRU + dirty-page flush. - A query planner. We stay at the find-by-filter-and-sort level. - SQL surface. We're a document store, not a relational DB.