v2.0 — Page-based disk-backed storage engine

STATUS: partly superseded. Read this before the rest of the document.

Phases A and B shipped as described (v1.10.0, v1.11.0). Phase C did not. The "Phase C" section below specifies a homegrown engine - 16 KB slotted pages, BPlusTree, BufferPool, page-level WAL redo. None of it was built. The build-vs-buy spike chose LMDB instead, which shipped as v2.0.0 and provides those internally. There is no Page, BufferPool or BPlusTree type in this codebase, and buffer_pool_size_mb does not exist.

Kept because the problem analysis and the phase reasoning are still sound. For current status see docs/ROADMAP.md.

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<uint8_t> 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<Key, Value> 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:

Boot v2.0 with --migrate-from-v1 flag
Reads latest v1 snapshot + WAL into memory (last time we'll do this)
Writes pages out to the new format
Renames the data dir so subsequent boots use the v2 format
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

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).
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.
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.
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+.
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

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.
Spike: RocksDB-backed prototype vs homegrown B+ tree. Worth 1 week of effort to compare; might collapse the C estimate significantly.
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.

2026-05-15-v2.0-storage-engine-design.md 17 KB 文件歷史 原始文件