Skip to content

PRIOR-ART.md

Latest commit

 

History

History
567 lines (438 loc) · 29.8 KB

PRIOR-ART.md

File metadata and controls

567 lines (438 loc) · 29.8 KB
Raw

beastdb - prior art (Wave 9)

Study notes for engines beastdb is compared against. Not a claim that beastdb reimplements these systems in Lean, matches their throughput, or is a drop-in replacement.

Pinned source trees live under ref/ as git submodules (study only). Product Lean and Nix never import ref/ as implementation. A separate Nix-generated LMDB microbench (packages.beastdb-lmdb-bench) is also not a submodule link - see BENCHMARKS.md.

Engine In tree Role
beastdb product Sharded append-only logs + multi-level compact; Lean proofs + Nix
LMDB ref/lmdb + Nix microbench SWMR mmap B+tree baseline (G7.2 numbers)
LevelDB ref/leveldb LSM / compaction-family contrast (parent of RocksDB-class designs)
Breccia ref/breccia Peter Todd append-only blob store (mark words, mmap blobs, search)
heed family ref/heed @ v0.22.1 Meilisearch typed Rust env/db/txn ergonomics over LMDB - API inspiration for ffi/rust/beastdb/, not product engine
YCSB-C ref/ycsb-c C++ Yahoo! Cloud Serving Benchmark (workloads A-F property files, pluggable DB drivers) - workload catalog + measure-only linked client nix run .#ycsbc / beastdb-ycsbc (-db beastdb via first-party bench/ycsb driver). Lightweight approx harness remains nix run .#ycsb-bench (not full YCSB-C). Not a product Lean dependency.

RocksDB is discussed below as a design family (LevelDB-derived) but is not a submodule (repo size). Architecture lessons apply via LevelDB + public RocksDB docs.

heed / heed3 (Meilisearch monorepo) is pinned under ref/heed as a bindings API study target. First-party Rust lives under ffi/rust/beastdb/ (see AGENTS.md), never under ref/. Do not invent LMDB-shim claims from this pin.

How to study ref/

# Fresh clone:
git clone --recurse-submodules <beastdb-url>
# Existing clone:
git submodule update --init --recursive
Path Upstream Pinned SHA Study focus
ref/lmdb https://github.com/LMDB/lmdb.git 704dc7028587983ce6c2a19018d22e85f2d9b8ff libraries/liblmdb/ - env, txn, B+tree pages, freelist, copy-on-write
ref/leveldb https://github.com/google/leveldb.git 7ee830d02b623e8ffe0b95d59a74db1e58da04c5 Memtable -> L0 -> leveled SSTables, version set, compaction
ref/breccia https://github.com/petertodd/breccia.git 1845f81ea0b2f0a7cc496e9fc56af3a454bda13e DESIGN.md / Rust impl - mark words, append-only single file, mmap-verbatim blobs
ref/heed https://github.com/meilisearch/heed.git 86cd1f681953cd5f6870706f6139b851e975975e (tag v0.22.1) Whole monorepo: heed (primary API inspiration), heed3 (contrast only), codecs/traits, tests as requirements catalog

Nested LevelDB deps: ref/leveldb/third_party/* (e.g. googletest, benchmark) are optional nested submodules. Default shallow git submodule update --init does not require them for prior-art reading (include/, doc/, db/). Fetch only if you build LevelDB's own tests/benches (git submodule update --init --recursive inside ref/leveldb).

Rules (full text in ref/README.md and AGENTS.md):

  • Not product source - no Lean import of ref/; flake productSrc drops the ref directory.
  • Any language OK under ref/; namecheck skips it.
  • Prefer reading headers and design docs first (lmdb.h, LevelDB doc/), then the hot paths you care about (put, get, compact, recovery).

beastdb (this product)

Architecture summary

  • Dynamic prefix sharding (binary trie routing) over the key space; splits install child leaves; data appends to the routed shard log.
  • Append-only logs per shard; latest-value semantics via fold (KV.latest / Compact.compactList).
  • Multi-level compaction (beastdb.Levels): L0 + newest-first unique runs; mergeRuns newer-wins; on-disk shard blob v2 encodes multi-run layout; load flattens for the pure engine.
  • Hybrid consistency during split: orphan logs + dual-read policy until reconcile; durable LIFECYCLE side file.
  • Persistence: whole-file snapshots (format v2 default; opt-in v3-v5 / encrypt), multi-file MANIFEST + per-shard + write-ahead log (WAL), or single-file store (beastdbI / G23; API still *Image*; explicit migrate; multi-file remains the default).

Concurrency model

  • Single-writer multi-reader (SWMR) (Wave 6): exclusive writer global LOCK for session/structural sections (per-op or session lease); readers open without exclusive lock and hold a pure snapshot.
  • Multi-writer multi-reader (MWMR) product put (G22): concurrent durable put on disjoint leaf shards (per-leaf lock + per-leaf WAL); same leaf / global LOCK fail closed. Multi-process smoke: mwmr-smoke.
  • Concurrent structural publish (Workstream J + Track 3): pure generation fence in beastdb.Structural; product multi-process generation-fenced structural with short cooperative LOCK (shipped - struct-smoke); exclusive critical section required today - not lock-free dual MANIFEST publishers (Next-4 / R3 residual; dual-publisher north-star deferred pending P1-P6 in SYSTEMS.md §4).
  • Cooperative trust (Tier C / C2): among honoring beastdb writers only - not kernel multi-writer leases (deferred; foreign/bypassers not excluded). Not linearizability of concurrent IO (C3 deferred - snapshot isolation).

Durability / crash story

  • Temp + rename publish; optional Nix beastdb-fsync on file and parent dir.
  • Format v2 FNV-1a trailer (checksum, not a MAC); WAL complete-prefix recovery; multi-file crash windows documented in LIMITS.md.
  • Opt-in keyed MAC / encrypt envelope (Wave 8) - models only; not AES/AEAD.

Compaction / space reclamation

  • Pure latest-value compact + multi-level merge; on-disk rewrite of affected shard epoch files + MANIFEST; best-effort delete of superseded shard files.
  • Workstream E + Tier B: compactShard truncates that leaf's WAL after rewrite (no reopen re-inflate of that leaf); checkpoint/sync compacts the publish base before write. The keysUnique flag is not on the wire; ofEntries / normalizeStore re-detect residual key uniqueness (Nodup) so cold open of a unique residual builds a TreeMap unique index (Next-1); multi-put residuals with duplicate keys stay on latestRev. Unique get-all ~O(N log N) for distinct-key multi-put / unique residual (R1 put-maintain; Plan Step 3 closed measured win for that path); overwrite multi-put get-all still ~O(N²) until compact (accepted residual / compact discipline); no O(1)/mmap B+tree claim.
  • Resource bounds (beastdb.Bounds) fail-closed.

Verification / assurance

  • Machine-checked pure core (routing, compact, reconcile, codec soundness); checks.no-sorry; proof inventory in PROOFS.md.
  • IO, fsync, and foreign-process locking are TCB / LIMITS, not fully proved.

Performance honesty

  • Unique residual / distinct-key multi-put (R1 put-maintain keeps TreeMap): get ~log residual; get-all ~O(N log N). Overwrite / non-unique residual: get is O(length) list scan (latestRev); get-all of N keys ~O(N²) until compact - not O(1).
  • Microbench only vs LMDB - see BENCHMARKS.md. No multi-GB parity claim.

Lessons adopted (from prior art, expressed in Lean)

  • SWMR product contract (LMDB-inspired single writer; multi-reader snapshots).
  • Append-friendly durability path (WAL + checkpoint), not rewrite-everything on every put (Wave 2).
  • Leveled / multi-run compaction idea (LSM family -> Levels), with proved latest-value and weak size bounds.
  • Fail-closed load on structure/checksum (inspired by production engines' integrity gates, implemented as pure Option/Error.corrupt).
  • Honest resource caps (map-size spirit of LMDB, fail-closed in Lean).

Lessons deliberately not adopted

Prior-art choice Why not in beastdb
mmap page cache (LMDB) No Lean-first mmap API in the product stack; pure store reload
In-place B+tree page mutate + freelist Product model is append-only logs + compact, not COW pages
C/C++ / Rust as product engine Product store semantics are Lean 4 only; foreign bindings under ffi/ are allowed and are not the engine (AGENTS.md)
Full LSM bloom filters, block cache, multi-threaded compact Complexity vs proof surface; sequential compact under SWMR
RocksDB multi-CF / optimistic txn / merge operators Out of scope for verified core bar
NIST AEAD / libzstd wire Pure models only (Wave 8); not wire-compatible with LevelDB/Rocks

Explicit non-claims

  • Not a drop-in LMDB, LevelDB, or RocksDB API or file-format replacement.
  • Not "LMDB reimplemented in Lean."
  • Not multi-GB throughput or space-amp parity.
  • Not proved OS-level crash atomicity for multi-file layouts.
  • Not an lmdb.h shim; not "full heed/heed3 suite green on beastdb."

LMDB (ref/lmdb)

Upstream: LMDB/lmdb - library under libraries/liblmdb/ (OpenLDAP MDB lineage). Study pin: 704dc7028587983ce6c2a19018d22e85f2d9b8ff.

Architecture summary

  • Memory-mapped B+tree of fixed-size pages; copy-on-write page updates.
  • Single environment file (or pair with lock file); keys sorted; values as payload or overflow pages.
  • Nested transactions; cursor API; no separate LSM memtable/SST stack.

Concurrency model

  • Classic single-writer, multi-reader (SWMR): one write txn at a time; readers use MVCC snapshots via page versions / free DB tracking.
  • Lock file coordinates multi-process access (kernel-assisted), not mere cooperative O_EXCL among one product.

Durability / crash story

  • Durable commits via page meta updates + msync/fsync policy options (MDB_NOSYNC, etc.).
  • Crash recovery is "last committed meta page wins"; freelist integrity is part of the design.
  • Checksums of the LMDB-strength kind are not the product FNV trailer story.

Compaction / space reclamation

  • Freelist of unused pages; optional copy compact (mdb_copy compact mode).
  • No leveled SST merge; space reuse is page freelist + COW.

Verification / assurance

  • Mature C codebase, extensive real-world use, tests and operational lore.
  • Not machine-checked in Lean. Assurance is review + testing + production history - different bar from beastdb's pure proofs.

Performance honesty vs beastdb

  • Local microbench (Nix beastdb-lmdb-bench): LMDB is orders of magnitude faster at small N on put/get when using one write txn vs beastdb N WAL appends + O(N) gets - BENCHMARKS.md.
  • That gap is expected (mmap B+tree vs pure list fold). Do not extrapolate to "beastdb loses at multi-GB" as a measured claim - multi-GB is not measured in-tree.

Lessons adopted

  • SWMR as the product concurrency story (Wave 6).
  • Explicit map-size / resource-style limits (Wave 7 bounds - different mechanism, same honesty).
  • Side-by-side microbench baseline (G7.2) so claims stay grounded.

Lessons deliberately not adopted

  • mmap as the primary storage substrate.
  • Page freelist / B+tree as the core data structure.
  • Linking product Lean against liblmdb (bench is Nix-generated C only).

Explicit non-claims

  • beastdb is not LMDB-compatible (env, txn, or DBI API).
  • Submodule under ref/lmdb is for reading; the product does not ship or link it.
  • Nix LMDB microbench is a separate generated C program, not built from the submodule path (both study the same engine class).

LevelDB (ref/leveldb)

Upstream: google/leveldb. Study pin: 7ee830d02b623e8ffe0b95d59a74db1e58da04c5.

Architecture summary

  • Log-structured merge-tree (LSM) style:
    • Write-ahead log + in-memory memtable
    • Flush to immutable tables (SSTables) at level 0
    • Background compaction into leveled runs (higher levels, larger size)
  • Sorted string tables with block index; optional filter policy (bloom).
  • Version set tracks live files; obsolete files deleted after unreferenced.

Concurrency model

  • Process-local locking around DB state; writers serialize critical sections; compaction can run in a background thread in the C++ implementation.
  • Not the same as LMDB multi-process mmap SWMR; multi-process use typically assumes one writer process or external coordination.

Durability / crash story

  • WAL for recent writes; recover memtable from log on open.
  • Manifest / CURRENT file for version recovery; table files are immutable once published.
  • Options for sync on write; integrity depends on filesystem + options (not a Lean-proved codec).

Compaction / space reclamation

  • Compaction is the primary space and read-amplification control: merge overlapping ranges, drop obsolete keys/tombstones, promote to lower levels.
  • Write amplification and space amplification are first-class operational concerns (unlike LMDB freelist pages).

Verification / assurance

  • Extensive tests and Google production heritage; C++ implementation.
  • No Lean formalization of compaction invariants in upstream LevelDB. beastdb's Levels / mergeRuns proofs are a small, different model inspired by the idea of multi-run newer-wins merge - not a verified LevelDB.

Performance honesty vs beastdb

  • LevelDB (and RocksDB) target high write throughput and tunable read paths with block cache and bloom filters.
  • beastdb has no in-tree LevelDB/RocksDB microbench; do not invent parity numbers. Architectural comparison only.
  • beastdb multi-level is a pure model with sequential product compact - not background multi-threaded compaction.

Lessons adopted

  • Multi-level / multi-run newer-wins merge as a mental model for compaction depth (Wave 3 Levels).
  • Immutable published artifacts + version pointer idea maps loosely to MANIFEST + epoch'd shard files (temp+rename), not SST format compatibility.
  • Tombstone / latest-value thinking via append-only + compact (product ships public tombstone delete (P6-DEL): get? clears tombs; compact may retain a latest tomb marker in the residual list - not free-page reclaim).

Lessons deliberately not adopted

LevelDB / LSM choice Why not
SSTable binary format + block compression Lean pure codec; different wire; Wave 8 framing != Snappy/zstd tables
Background compaction threads Product SWMR + sequential compact; extract reliability
Bloom filters / block cache Not in pure list engine; would expand TCB
Memtable skip-list in C++ Pure Lean lists/structures for the proved core
Full RocksDB feature surface Scope creep vs machine-checked bar

Explicit non-claims

  • beastdb is not LevelDB- or RocksDB-compatible (API or on-disk).
  • Levels is not a formal verification of LevelDB compaction.
  • No claim that beastdb write/read amplification matches LSM engines.

Breccia (Peter Todd - ref/breccia)

Source: https://github.com/petertodd/breccia @ 1845f81ea0b2f0a7cc496e9fc56af3a454bda13e Upstream language: Rust (study only). Not product source.

Architecture summary

  • Single-file append-only blob store (not a full KV engine).
  • Blobs stored verbatim (mmap-friendly); 64-bit mark words equal to file offset delimit discoverable blob boundaries; padding avoids false marks.
  • Forward/backward discovery from an arbitrary offset; ordered blobs support binary search without external indexes.
  • Design targets low overhead even for small blobs; optional chattr +a append-only file attribute in operational lore (upstream design doc).

What beastdb already took (inspiration)

  • Append-only mutation story and "immutable once written" mindset (logs, temp+rename publish of snapshots).
  • Latest-value / compaction narrative historically called "Breccia-inspired" in Compact docs - honestly: product compact is latest-value dedup + multi-level runs, not Breccia's mark-word blob format.

Lessons deliberately not adopted (yet)

Breccia idea Why not wholesale
Mark-word single-file format Product uses char/versioned codecs + multi-file MANIFEST/shards/WAL
Require mmap / 64-bit-only layout No Lean-first mmap API yet; G23 ships single-file store without mmap
Rust implementation Product is Lean + Nix only
Binary search on ordered blobs as primary index Unique residual / distinct-key multi-put: TreeMap uniqueIndex (Next-1 / R1 put-maintain; ≡ fold-latest); overwrite multi-put: latestRev until compact; G23 single-file store shipped but not mmap B+tree / LMDB page format

Study items for layout / WAL (G14)

  1. Discoverable records without rewriting earlier bytes.
  2. Verbatim payload for zero-copy / future mmap.
  3. Overhead bounds when entries are small.
  4. How mark collision padding interacts with checksum/MAC trailers if we ever adopt similar framing.

Non-claims

  • beastdb is not Breccia-compatible on disk.
  • Pinning ref/breccia does not mean product compaction equals Breccia.
  • No claim of Breccia's binary-search performance.

RocksDB (family note - not a submodule)

Why LevelDB was pinned instead: smaller study tree; RocksDB is LevelDB's industrial descendant (Facebook/Meta) with many more options (column families, blobDB, transactions, advanced compaction, compression codecs). For Wave 9, LevelDB is sufficient to contrast LSM + compaction with beastdb's append-only + multi-level pure model and with LMDB's B+tree.

If a future wave adds ref/rocksdb, pin a release tag and extend this doc - do not treat absence of a RocksDB submodule as "we ignored LSM."

RocksDB-specific lessons not adopted (same reasons as LevelDB, amplified): multi-CF, merge operators, optimistic transactions, jemalloc/arena tuning, shared backup engines.

Side-by-side matrix

Dimension beastdb LMDB LevelDB (LSM) Breccia
Primary structure Sharded append-only logs + multi-level runs mmap B+tree pages Memtable + leveled SSTables Append-only mark-word blobs
Concurrency SWMR session + MWMR put on disjoint leaves (G22); generation-fenced multi-process structural (Track 3 / J; short LOCK remains) SWMR multi-process (lock + mmap) Process-local; bg compact Single-writer append lore
Durability unit WAL + checkpoint / whole-file snapshot Meta page + dirty pages WAL + SST + manifest Append-only file (+ optional +a)
Space reclaim Compact + epoch file GC Page freelist / compact copy Compaction Application-level (blob store)
Assurance Lean proofs on pure core Tests + production history Tests + production history Design + Rust tests
Product language Lean 4 -> AOT C binary C C++ Rust
In-tree measure beastdb bench + LMDB microbench same microbench architecture only architecture only

Meilisearch heed family (ref/heed)

Upstream: meilisearch/heed - one git monorepo, multiple crates. Pinned: tag v0.22.1 @ 86cd1f681953cd5f6870706f6139b851e975975e (crates.io max stable heed / heed3 0.22.1 at pin time; Phase 1 of PLAN.md).

What lives in the monorepo

Crate / area Role for beastdb study
heed Primary API inspiration - typed Env / Database / txn ergonomics, codecs, cookbook patterns
heed3 Same monorepo family aimed at LMDB mdb.master3 (encryption-at-rest / checksum features) - contrast only; not our target
heed-types / heed-traits Codec and trait patterns to mirror (reimplement; do not link upstream crates into product)
lmdb-master*-sys Real LMDB FFI - study only; beastdb does not ship or depend on these for the product path

Accurate upstream relationship: one git repo; two crates (heed ↔ mdb.master, heed3 ↔ mdb.master3). Do not document heed3 as "a git branch of this repo."

Why study it

  • Shape the first-party Rust crate at ffi/rust/beastdb/ after heed ergonomics (open env, typed put/get, commit/sync story), mapped onto beastdb truth.
  • Use the upstream test suite as a requirements catalog + selective port (T0 smoke + frozen T1 subset as flake checks) - not "drop in and cargo test against beastdb."

Phase 2 study extract (done): full API/test triage, codec decision, C ABI growth list, batching notes, and frozen T1 (12 cases) live in HEED-MAP.md. Prefer that document for Port / Adapt / Skip detail, the published skip matrix, and the thin v0 completeness table (§8.1); this section stays the architecture/non-claims overview.

Phase 3-4 (done): first-party library at ffi/rust/beastdb/ with dual write paths + Nix checks.beastdb-rust-smoke / beastdb-rust-t0 / beastdb-rust-t1. Residual R17 closed.

Phase 5 (done - docs honesty): suite provenance (heed3 tests zero) + thin v0 completeness (not "most of heed"); Gap #3 operator cross-links. Phase 6 advanced (partial): bulk multi-put + contains + product tombstone delete (P6-DEL) + Mode B flush policy + P6-EXPORT PR2 dual-backend (export package default; CLI emergency BEASTDB_USE_CLI=1) + P6-CURSOR (C ABI v6)

  • P6-ACID (C ABI v7 multi-key atomic batch + product WriteTxn + Rust Mode B unlimited commit/abort) + P6-RANGE (C ABI v8 reverse/range/first-last/neighbors; internal-key order) + D1 done (C ABI v9 len/is_empty/clear/delete_range) + D2 done (RoTxn / read_txn; selective T2; MIGRATE-HEED.md) + D3 measure done (M2) + R7-BYTES done (export get densify + bulk memcpy; R7 still deeper partial; not mmap O(1)). Live suite: T0 8 / T1 26 / T2 8 (beastdb-rust-t0 / t1 / t2). Tier 0: P6-ACID done (beastdb multi-key atomic batch, not LMDB page-level ACID); P6-RANGE done; D1 done; D2 done; D3 measure done; R7-BYTES done; P6-WAL optional / deprioritized. Default next: G1 human. Soft reopen / measure + embed need applies to remaining optional growth / further R7 product depth (SCAN/STATIC/SNAP) only. R7 is deeper partial (not closed; atomic batch / range scan / D1 / D2 / D3 measure / R7-BYTES do not close R7). Accomplished/remaining board: PLAN.md / PLAN-REMAINING.md.

Suite provenance (heed vs heed3)

The flake suite is selective heed-inspired beastdb tests (T0 + T1 + T2), not an upstream heed or heed3 port:

Source What landed
heed (primary) Selective T0 (8 tests) + T1 (26 #[test]s) + T2 (8) under checks.beastdb-rust-t0 / beastdb-rust-t1 / beastdb-rust-t2 - beastdb semantics, heed-shaped names/intents
heed3 Zero tests pulled. Contrast only: encryption-at-rest / mdb.master3 (open_encrypted, crypto errors) - not a v0 target

See HEED-MAP.md §6.1 for the same honesty and the skip matrix.

Crate API: thin v0 (not "most of heed")

Shipped surface is enough for open -> put/get/contains/delete/iter/prefix_iter -> commit/sync -> reopen, dual write paths (Mode A immediate + Mode B batch with multi-key atomic batch on unlimited commit), Bytes / Str codecs, and fail-closed corrupt open. Product delete is a tombstone (P6-DEL; API v5 / HEED-MAP P2b) - not LMDB free-page reclaim. Ordered scan / prefix iterate shipped (P6-CURSOR; API v6). Multi-key atomic batch shipped (P6-ACID; API v7) - not LMDB page-level ACID. Reverse/range/first-last shipped (P6-RANGE; API v8). len / is_empty / clear / delete_range shipped (D1; API v9). RoTxn / read_txn + selective T2 + migration cookbook shipped (D2). R7 deeper partial (export package default = same-process export; CLI emergency BEASTDB_USE_CLI=1; not closed). Against full heed public API that is a small core slice, not "most of heed." Missing vs heed (non-exhaustive): named multi-DB, nested transactions, map_size / env flags, mut/write cursors, serde codecs, full MdbError, heed3 encryption, full upstream suite. Completeness table + Port/Adapt/Skip inventory: HEED-MAP.md §7-§8.1.

Write / "txn" mapping (locked for bindings workstream)

Do not fake LMDB ACID page transactions. Heed-shaped types with beastdb meaning:

Type (heed-shaped) beastdb meaning
Env Open multi-file store (beastdb_env / directory)
Write path / RwTxn Mode A - immediate: each put/delete hits the engine/bridge; commit() -> durable publish (sync / checkpoint). Mode B - batched: buffer puts and deletes; auto-flush chunks via product multi-key atomic batch (not abortable); unlimited commit() -> one atomic batch then durable publish; abort discards unflushed only.
RoTxn Read path after last durable publish / consistent open; document free-copy / stale-handle honesty
Database<KC, DC> Typed view over the single logical store; codecs à la heed-types patterns (no LMDB sys link)

Durability honesty (bindings local-power assumption): target is local embedded durability (uninterruptible power supply (UPS) / laptop battery assumed) - not power-fail lab claims (R10 still not claimed). Write-ahead log (WAL) is not a bindings API requirement; prefer clear durable publish on commit and high-throughput batching. Crash mid-batch without commit: unflushed buffer not durable. P6-ACID ships beastdb multi-key atomic batch (temp+rename), not LMDB page-level ACID; multi-put remains non-ACID. Do not confuse this local-power story with fitness C1 / R3 (lock-free dual MANIFEST publishers - a multi-process structure residual, not a durability class).

Explicit non-claims (heed path)

Claim Reality
Full heed / heed3 suite green on beastdb Not drop-in. heed talks to real LMDB via lmdb-master*-sys. beastdb exposes a tiny C ABI over a multi-file MANIFEST/shard store (dual-backend: export package default same-process compiled @[export]; CLI emergency fork/exec) - not lmdb.h, not mmap B+tree wire. Suite is selective T0+T1+T2 beastdb tests; heed3 tests: zero.
"LMDB replacement" via heed suite Product forbids wire/page drop-in. Keep LMDB-class embeddable KV, not "pass heed suite = LMDB."
heed3 encryption-at-rest Out of scope for the Rust crate v0; G9/G19 models only on product side.
Power-fail / kill-9 durability from bindings Not claimed (R9/R10 unchanged).
Crate under ref/ Forbidden. First-party crate is ffi/rust/beastdb/.
"Most of heed" API shipped Thin v0 only - open/put/get/contains/delete/iter/range/len/clear/commit/sync/reopen + dual write + Bytes/Str + RoTxn (tombstone delete, not free-page reclaim); see HEED-MAP §8.1.

Lessons adopted (bindings only)

  • Typed env/database surface and codec trait patterns (Bytes/Str reimplemented; no upstream heed-types link).
  • Dual write paths (Mode A immediate + Mode B batched) for flexibility and measure.
  • Selective Port / Adapt / Skip matrix + T0/T1/T2 flake gates - not full upstream suite green.

Lessons deliberately not adopted

  • Linking lmdb-master*-sys or treating beastdb as an LMDB backend.
  • Named multi-DB, mut/write cursors, map_size flags, dupsort, nested txns, LMDB free-page reclaim (product delete/clear/delete_range are tombstone-only), serde, full MdbError until product + ABI exist (and only when measure/embed need).
  • heed3 / master3 encryption product.
  • Running or claiming the full heed / heed3 cargo test matrix against beastdb.

Cross-links

  • VISION.md - product architecture and roadmap
  • LIMITS.md - IO / durability honesty vs engine class
  • BENCHMARKS.md - LMDB microbench methodology and samples
  • GAPS.md - G11.1-G11.4 prior art; residual R7 deeper partial; R17 closed (Phases 3-5); post-wave G13+
  • HEED-MAP.md - Port/Adapt/Skip; suite provenance §6.1; thin v0 §8.1
  • SYSTEMS.md - AOT product, fail closed, assumptions; MWMR put + generation-fenced structural shipped; Next-4 / R3 lock-free dual MANIFEST residual (exclusive LOCK required; dual-publisher north-star deferred pending P1-P6 §4); kernel leases / linearizability deferred
  • ref/README.md - submodule inventory
  • AGENTS.md - ref/ policy + foreign-bindings exception under ffi/
  • PLAN.md - heed pin + crate workstreams (Phases 0-5 done; Phase 6 advanced/partial; P6-ACID done; P6-WAL deprioritized; PLAN-REMAINING.md)
  • HEED-MAP.md - Phase 2 heed->beastdb API/test triage + frozen T1

Wave 9 / G11.4 scope (honest)

Wave 9 was documentation + study trees (LMDB + LevelDB). G11.4 adds Breccia the same way. None of those pins add a runtime codec, foreign binding, or drop-in API. The heed family inventory above is a bindings workstream (Phase 0 policy + Phase 1 pin at ref/heed @ v0.22.1 + Phase 2 HEED-MAP.md triage + Phase 3-4 crate/T0/T1 with residual R17 closed); it does not reopen G11 as open product work and does not claim a full heed suite gate (selective T0+T1 only; heed3 tests: zero). Runtime demo banners describe Waves 1-8 + Horizon 2 product features; prior-art study is this document and ref/.