holt

Where things stand

holt is a single-node, Unix-only ART-over-blobs metadata engine. The algorithm core, persistent backend, WAL + replay, sharded buffer manager, 3-thread background checkpointer, and the curated public API are all in place. The release test surface is unit, property, crash/replay, failpoint, and integration coverage; the public benchmark surface is the RocksDB/SQLite metadata comparator in benches/main.rs.

See ARCHITECTURE.md for the design and CHANGELOG.md for what changed when. The fine- grained shipping log lives in git log; this file tracks milestones, not individual features.

v0.1 — Usable embedded library (shipped, 2026-05-19)

Goal: build the engine end-to-end so a path-shaped-metadata workload can use it on a single node.

Delivered: 9-NodeType ART layout pinned at compile time, recursive walker (insert / lookup / erase / rename), cross-blob splitBlob / mergeBlob / compactBlob, FileBlobStore (O_DIRECT Linux + F_NOCACHE macOS), logical WAL with replay, Tree::range iterator with prefix + start-after + S3-style delimiter rollup, Tree::atomic atomic batches under one WAL record, four examples (basic_kv / filesystem_meta / session_store / s3_metadata), property-based tests against a HashMap oracle, criterion benches vs RocksDB + SQLite.

v0.2 — Performance + concurrency upgrades (shipped)

Goal: scope the metadata-engine core for production-shaped workloads — no new public API surface, the bench numbers from v0.1 are the success criteria.

Delivered: io_uring persistent-backend fast path (Linux, feature-gated), crc32fast SIMD CRC32, sharded BufferManager (DashMap replacing the v0.1 Mutex<HashMap> + VecDeque LRU), cached Tree.root_pin, range-iter fast-forward in delimiter mode, 3-thread background checkpointer (planner + I/O worker + eviction) under a W2D-strict protocol, adaptive tick-based eviction, observability (Tree::stats, structured tracing, Prometheus text-format renderer behind the metrics feature, silent-pin reads so scrapes don't pollute cache counters), diagnostics (Tree::scan, range-iter tombstone fix, structured Error::NodeCorrupt), PGO docs, cargo deny check in CI, scale-curve + p95/p99 contention benches.

Concurrency primitives: per-blob HybridLatch (LeanStore 3-mode, wait-free optimistic reads) inside one WAL-writer critical section per write. Slot-versioned cross-blob lock-coupling was considered for v0.2 but deferred to v0.3 — it needs structural changes the v0.2 scope didn't budget for, and the per-slot version array is best designed alongside the cross-blob descent flattening rather than retro-fitted.

Public API surface closed before crates.io publication: the v0.1 pub mod layout / journal / store exposure shipped the on-disk layout, WAL codec, and buffer-manager guards as part of SemVer; v0.2 tightened those to pub(crate) so the engine is free to evolve internally without minor-version breaks. See CHANGELOG.md for the supported user surface.

v0.3 — Extreme metadata-engine performance (shipped, 2026-05-21)

v0.3 shipped as the performance ceiling milestone for an embedded metadata engine. Feature work waits. The goal is to push the Fractal-ART-inspired kernel as far as practical on modern Linux/macOS: cache-resident reads, path-shaped writes, prefix/list walks, WAL durability, checkpoint I/O, and large-tree behavior.

The target design borrows the strongest parts of Fractal ART, LeanStore, and modern NVMe engines while keeping holt's product boundary narrow: one embedded library, opaque byte values, no RPC server, no replication, no distributed object-store layer.

P0 — Remove the write-path serial choke points (done)

v0.3's concurrency cut is implemented in the codebase:

• Cross-blob lock coupling. The old parent-held fallback is gone. insert_multi / erase_multi read the parent BlobNode, pin the child, release the parent guard, and continue in the child. The child blob's own header.root_slot is the authoritative entry, so child-local splits, collapses, and compaction do not require parent rewrites.
• No slot-version sidecar. The earlier per-slot version plan would have added ~80 KB of out-of-line state per cached blob. The shipped shape avoids that memory tax by removing BlobNode.child_entry_ptr and making the child header the only cross-blob root token.
• Scoped walker instead of unsafe state machine. The mutation walker still uses recursive Rust scopes, but it no longer retains ancestor guards across child mutation. That gives the same latch lifetime as the flattened state-machine design without self-referential guard plumbing.
• Maintenance is separated. Foreground writers enter only the shared side of a narrow atomic maintenance_gate while they may cross BlobNode boundaries. Deletes and leaf-slot churn enqueue blob-local compaction candidates; spillovers enqueue parent-merge candidates. compact() cold-seeds only when no hints exist, drains bounded candidate batches, skips clean stale candidates after a shared-latch header check, and compact() plus the background merge pass enter the exclusive side only around the parent edge currently being folded/deleted. Point reads also take the shared side, but blob-local access remains optimistic; ordinary readers and writers still run concurrently with each other.
• Large-tree puts avoid root write-latch traffic. Cross-blob puts route through the root under a shared latch, acquire the child write latch while the edge is stable, then mutate only from the child down. Child-only writes also return a precise root_dirty = false, so the caller does not mark the root dirty or take the dirty-map mutex for a blob it did not change.
• Shape counters are exposed. Tree::stats() now reports mutation walker ops, total/average/max blob hops, max cross-blob boundary depth, spillovers, merges, and optimistic read restarts. Prometheus export includes the same counters.
• Checkpoint/eviction interlock is closed. Dirty entries drained by a checkpoint round stay protected as in-flight flushing entries until their snapshotted bytes complete write_through, so eviction cannot drop the cache image in the gap between snapshot_dirty() and the planner's byte copy. Dirty / flushing / pending-delete bookkeeping is sharded by BlobGuid, and fresh spillover blobs keep a local Arc pin alive until their dirty entry is visible, so background eviction cannot observe a new child blob as clean before checkpoint can flush it.

Still intentionally not in P0: per-op latch wait histograms. The current HybridLatch API has no timed acquisition boundary, and adding timing to every latch acquire should be driven by a contention benchmark rather than added speculatively.

P1 — Journal group commit (done, with one explicit boundary)

Durable group commit is implemented:

• Persistent trees own a dedicated journal worker instead of an exposed Arc<Mutex<WalWriter>>.
• Writers encode complete WAL records into owned buffers, submit them to the worker, and wait outside the commit-publish critical section.
• Durability::Wal { sync: true } writers share one sync_data when they arrive inside the short group window. Tree::stats() and Prometheus export journal appends, append batches, and sync counts so the batching ratio is observable.
• The old global commit_lock is replaced with CommitGate: foreground writers enter the shared side while they mutate blobs, publish dirty state, and submit journal records; checkpoint takes the exclusive side only while draining dirty/pending sets, flushing the journal, and cloning dirty blob bytes.
• This keeps the W2D proof intact while removing writer-vs-writer serialization from the persistent write hot path. Writers on disjoint child blobs now contend on per-blob latches and the mutation-bookkeeping shard they actually touch, not a global commit mutex or global dirty mutex.

P2 — NVMe-grade checkpoint I/O (done)

The background checkpointer already has planner / I/O / eviction threads. v0.3 makes the I/O side worth that structure:

• Submit dirty blobs as batches, not one synchronous write at a time: BlobStore::write_blobs is the checkpoint write-through primitive.
• The default Unix backend sorts and coalesces slot-contiguous 512 KB blob writes with pwritev; Linux io_uring keeps ring-depth batched SQE submission with fixed-file and fixed-buffer registration.
• Experimental SQPOLL / IOPOLL / linked-fsync modes are not part of the v0.3 path: on Holt's short checkpoint batches they did not improve throughput, and keeping them would make the I/O completion path harder to audit. The next real Linux step is a dedicated async I/O scheduler, not more ring flags.
• Manifest persistence now uses a base snapshot plus append-only manifest.log set/delete deltas. Checkpoint rounds append and fsync only the current delta batch; full manifest.bin rewrites happen only as log compaction. Deleted slots become reusable only after the manifest delta is durable, and reopen reconstructs reusable slots from final manifest holes using compact ranges rather than expanding sparse high-water files into one u64 per free slot.
• Backends expose a conservative needs_flush hint. Clean manual checkpoints and background idle rounds skip the data-file Sync only when the backend has no outstanding data or manifest work, so a previous failed Sync still forces the next retry.
• The WAL worker tracks whether the current log has uncheckpointed records, including records found when reopening a nonempty WAL. Clean checkpoints now skip empty WAL flush/truncate work instead of paying a sync_data or temp-file rename on every idle round. It also tracks the durable WAL frontier, so checkpoint does not re-fsync records that already passed through durable group commit. A nonempty WAL discovered on reopen is treated as replayable but not proven fsync-durable, so the first checkpoint after replay still forces a WAL flush before backend durability. Background checkpoint rounds also handle WAL-only truncate work without paying an unrelated backend Sync. WAL truncate itself is an in-place ftruncate + sync_data, avoiding the older temp-file write, rename, and fd reopen after every checkpoint. Release benchmark coverage stays focused on the public RocksDB/SQLite metadata comparison. Checkpoint-specific probes should be reintroduced only when they are promoted to either a public comparator or a correctness integration test.

P3 — CPU hot-path work

Most of the structural CPU hot path is already in place:

• SearchKey uses a virtual terminator, so point lookups and mutations no longer allocate a padded key per operation.
• Same-key insert/delete comparison borrows the stored leaf key directly. The API allocates only when it must return the old value or materialise split-prefix bytes.
• SIMD is already used for Node16 byte search, longest-common prefix, Node48 child scans, and Node256 child scans. CRC32 uses crc32fast.
• Node bodies stay packed in 512 KB blob frames; the hot path does not allocate heap node objects or chase per-node boxes.

Remaining P3 work should be profile-driven only: simplify branches that show up in the flamegraph, then consider targeted SIMD/copy-repack kernels where profiles prove the scalar path is still material.

P4 — Large-tree shape control

• Recursive occupancy-aware spillover is implemented. The picker skips existing BlobNode crossings, descends inside overfull path branches, and chooses a victim near the target child fill band instead of blindly peeling off the largest direct child.
• BlobNode inline-prefix divergence split is implemented: a bad blob boundary now recovers locally into Prefix? -> Node4 -> {old BlobNode, new Leaf} instead of failing the insert.
• Make merge/rebalance incremental. compact() and background merge are now candidate-driven and online with respect to foreground writers through the atomic maintenance_gate; the remaining large-tree work is policy quality (when to split/merge/rebalance), not basic safety.
• Large-tree release coverage is the public {20 k, 100 k, 500 k, 2 M} scale curve in benches/main.rs. Additional shape probes should be profile-driven and promoted only if they become part of the release comparison surface.

v0.4 — Scale-stable metadata performance

Goal: keep the v0.3 cache-resident read/list advantages while making large-tree writes and negative metadata probes stay flat as the namespace grows from millions to tens or hundreds of millions of records. v0.4 should be judged by scale curves, not by small-tree microbench wins.

The main risk at this point is not one more syscall on the durable path. It is shape drift: overfull hot prefixes, too many cross-blob hops, negative lookups walking full descents, checkpoint bursts competing with writers, and bulk creates paying one full ART descent per key. The v0.4 work is therefore workload-shaped rather than generic KV tuning.

P0 — Prefix shape policy and write-stability guardrails

• Add explicit shape-control metrics to release benches: blob fill distribution, blob-hop histogram, spillover/merge rate, checkpoint dirty backlog, and WAL sync batching ratio at each scale point.
• Promote prefix/subtree boundaries deliberately. The generic API should be a shape hint such as promote_prefix(prefix), not an S3-specific "bucket" concept. Object-store users can map one bucket or tenant to a promoted prefix; filesystem users can map hot directories or mount roots.
• Make spill/merge policy backlog-aware. When writers are flooding a hot prefix, the engine should prefer bounded child splits and defer cosmetic merges instead of oscillating between split/compact/merge.
• Add write-stability benches that model untar/rsync/S3-sync bursts: sorted path creates, random creates under one hot prefix, mixed create/delete churn, and large-prefix list while writes continue.

Success criteria:

• put and atomic throughput should degrade smoothly with scale: no cliff when moving from 2M to larger trees.
• Average blob hops should stay low and p99 blob hops should be explainable by explicit promoted boundaries, not accidental shape drift.
• Checkpoint backlog should drain without forcing foreground writers through long global waits.

Closed investigations (so they are not re-opened):

• Resident route-cache sizing — exonerated by measurement. A 2M→20M scale curve showed the route cache uses <14% of capacity at 87–99% hit rate; it is not the scale bottleneck. The real signal is blob fill efficiency (83–87% of blobs below the 35% fill floor at scale), i.e. a disk-space cost.
• Two blob-fill fixes — designed and adversarially refuted, closed. Tighter spillover packing cannot balance a path-shaped tree (no single ~50% edge) and does nothing for the existing corpus; a sibling-merge primitive double-consumes the branching byte (silent wrong-read) and the eligible population is tiny. Fill is a space cost that the page-granular routing region already mitigates for read latency; revisit only if disk space itself becomes the constraint, diagnostic-first.

P1 — Negative lookup filter (DONE via per-blob bloom)

Metadata workloads are unusually negative-heavy: open/stat/head often ask for keys that do not exist. Shipped (unreleased branch) as a per-blob bloom filter, which went further than the original in-memory-first plan:

• Built from stored keys at compaction and embedded at the tail of the routing region (bloom_off / bloom_len in the blob header), so it is read for free with the routing region on a cold read.
• A cold negative lookup answers NotFound without the leaf-page read. The bloom never false-negatives (it only ever skips a leaf read), so it cannot change get() semantics; a structural mutation de-routes the blob and clears the bloom until the next compaction rebuilds it.
• On disk it is additive (bloom_len == 0 = no bloom = legacy behavior).

P2 — Explicit bulk-load path

Bulk create is a metadata-specific write pattern. Treating an archive restore as N unrelated puts leaves performance on the table.

• Add an explicit sorted bulk-load API or builder rather than hidden timing heuristics. Callers that know they are loading a directory, bucket prefix, image layer, or archive can opt in.
• Build final ART shapes directly for sorted keys: avoid repeated Node4 -> Node16 -> Node48 -> Node256 promotion and repeated descent through the same prefix.
• Commit each bulk batch as one atomic WAL envelope with bounded byte and key-count limits, so crash replay and memory use stay simple.

Success criteria:

• Mass-create workloads improve by multiples, not percentages.
• Point-write latency for ordinary single-key writes is unchanged.

P3 — Async checkpoint scheduler, not more io_uring flags

The v0.3 Linux backend already has the useful fixed-file / fixed-buffer / batched-ring foundation. The next I/O gain is not SQPOLL or linked-fsync by default; those did not help Holt's short checkpoint batches enough to justify the complexity.

An io_uring WAL/checkpoint rewrite was investigated and rejected: the WAL is already user-space group-committed (one write + one fdatasync per barrier, no fan-out for a ring to parallelize), the cost is the device flush not syscall entry, and io_uring Write ignoring O_APPEND would force error-prone explicit-offset bookkeeping on the durability hot path for a sub-microsecond win. All fsync-device-bound metadata paths (WAL, manifest.log, manifest.bin) are non-candidates under the synchronous-flusher architecture. The read-side batched ring (pread_many) did land, for cold-scan read-ahead.

The next gain is execution-model work:

• Keep dirty-byte and dirty-age watermarks so checkpoint starts before the dirty set becomes a foreground-write problem.
• Let the I/O worker keep multiple write batches in flight when the backend can absorb queue depth, while preserving the WAL-before-data and data-before-manifest ordering boundaries.
• Add foreground write throttling only as a last resort, driven by dirty backlog and checkpoint lag, not by raw operation count.
• Keep the default Unix pwritev path simple and auditable; Linux io_uring should remain an internal backend optimization with the same correctness contract.

Success criteria:

• Under sustained writes, p99 put latency should remain bounded while checkpoint makes progress.
• Idle and lightly loaded trees should not pay extra scheduler cost.

v0.5 — Stronger metadata semantics without MVCC tax

Goal: add the missing semantics that real metadata servers need while preserving Holt's core design: path-shaped keys, opaque byte values, single-node embedded library, no always-on MVCC version chains.

Completed — Scoped snapshot view

• Tree::view(prefix, |view| ...) performs one root-frame copy, shares descendants, and serves stable point reads/scans while first writes fork snapshot-visible frames after validating their parent edges. Cloned views, range builders, and owned cursors extend the process-local epoch lease beyond the callback until their final handle drops; retirement then makes detached frames eligible for checkpoint/GC reclamation.
• Ordinary range() / range_keys() remain the hot restart-on-conflict iterators; View is the explicit stable-read path for list/readdir.

P1 — WAL tail / change feed with explicit retention

• Holt 0.9 exposes a local checkpoint-bounded recovery suffix through DB::journal_envelopes_after. This is a crash-recovery primitive for one file store, not a live subscription or shared change feed.
• Expose a change-feed API only after WAL retention is designed. Today's checkpoint path truncates WAL, so subscribe(from_seq) cannot pretend old history is always available.
• The first version should support live-tail subscription and bounded retained segments for cache invalidation, audit, and follower-style experiments.
• Follower mode or replication should remain outside the core release until the single-node durability contract has a crisp tail-retention story.

P2 — Sealed immutable subtree

• Add an optional seal_prefix(prefix) mode for image layers, archives, and package indexes that become read-only after build.
• Start with semantic enforcement and latch elision. Huge pages, mmap tiers, and TLB-focused placement are later profile-driven optimizations.

v0.6+ — Optional adapters and research-grade hardware work

These are useful, but they should not pollute the core engine or the 0.4/0.5 scale-stability work.

• POSIX dirent/inode separation belongs in an adapter/example layer: e.g. d/<path> for dirents and i/<inode> for inode metadata.
• ACL inheritance, S3 bucket semantics, lifecycle policy, and object versioning are schema conventions above Holt's opaque byte values.
• Value compression should be an optional codec layer, not a core schema-aware dictionary unless benchmarks prove opaque values are the limiting factor.
• Prefix interning changes node layout and adds read indirection; do it only after path-memory profiles show it beats the existing ART prefix compression.
• NUMA, CXL.mem, ZNS, and lockless rename are server-appliance or research tracks. They are valid experiments, but not release blockers for an embedded metadata engine.

Non-goals for the core engine

• Do not bake S3 object schemas, inode structs, ACL formats, JSON, protobuf, chunk lists, or lifecycle rules into the storage core. Holt stores opaque values; higher layers own schema.
• Do not add full MVCC until a concrete workload proves copy-on-list and atomic CAS batches are insufficient.
• Do not chase io_uring flags that make the backend harder to audit without moving a measured bottleneck.
• Do not add compatibility aliases for renamed public APIs. The crate is still young enough that clean API shape matters more than transition glue.

v1.0 — Production-ready

• Post-v0.5 public surface and persistence format stabilized.
• Multi-platform stability across Linux + macOS (optional BSDs if anyone needs them).
• Real production deployments + case studies.
• Long-term API stability commitment — holt::* surface frozen, #[non_exhaustive] markers in place so additive changes stay non-breaking.

Not on the roadmap

The library is a metadata engine, period. Single-node, embed-in-your-process, Unix-only. Out of scope:

• Windows support — O_DIRECT (Linux) and F_NOCACHE (macOS) have no Windows analog this project wants to maintain. The crate compile_error!s on Windows targets.
• Object-storage frontend / S3 layer — the upstream that inspired holt's algorithm core wrapped its ART in an S3-style RPC server (PUT/GET/LIST inode handlers, multi-tenant bucket registry, RPC worker pool). holt does not reproduce any of that. The alignment is bounded to the metadata engine: ART core, blob layout, WAL, latching, range iterator. WalOp variants holt journals share wire shape with the upstream so a future RPC layer could re-use the format, but holt itself ships no multi-root registry, no bucket namespace, no RPC dispatcher.
• Replication / consensus — build it above this. Future hooks can support it, but holt itself does not implement Raft.
• Network server — this is a library. Wrap it in your gRPC / HTTP / whatever.
• SQL — not the right abstraction for this data shape.
• Vector search — combine with a dedicated vector DB.
• Full-text search — combine with Tantivy / Lucene-rs.

Contributing

Early-stage project; design feedback most welcome. PRs welcome too, but please open an issue first for non-trivial changes — the architecture is still being shaped and we want to avoid churn.