DEV Community

PRAVEEN KUMAR
PRAVEEN KUMAR

Posted on

LogTreeDB: Building a Crash-Safe, Zero-Dependency Document Database from Scratch in C++17

Author: Praveen Kumar
Date: November 2026

  1. Executive Summary & The Core Question

Databases are often treated as black boxes. When application developers need a document store, they default to MongoDB; when they need an embedded engine, they grab SQLite or RocksDB. But under high-concurrency write workloads requiring strict physical durability (fsync on every acknowledged write), traditional database designs encounter severe architectural bottlenecks—most notably Write Amplification (WAF) and Random I/O Thrashing.

LogTreeDB is a crash-safe, multi-threaded document database written from absolute scratch in modern C++17 without a single third-party dependency. It combines an append-only Value Log (vLog) with a disk-backed, sibling-free Copy-on-Write (COW) B+Tree index that stores only 24-byte document location references. It exposes a full MongoDB-compatible query interface (find, $set, $inc, secondary indexes, aggregation pipelines) over a custom length-prefixed TCP wire protocol on port 7070, complemented by a zero-dependency Node.js driver, an interactive shell, and an embedded administrative web console.

text
LogTreeDB at a Glance:
┌────────────────────────────────────────────────────────────────────────────────────────┐
│ • 16-Thread WAF: 1,384 bytes/update vs. SQLite's 33,300 bytes (24.1x reduction) │
│ • 16-Thread Speed: 3,363 updates/sec vs. SQLite's 313 updates/sec (10.7x faster) │
│ • Crash Resilience: 354+ randomized kill -9 crash runs, 0 acknowledged writes lost │
│ • Zero Dependencies: Engine, server, driver, shell, and UI use ONLY stdlib & POSIX │
└────────────────────────────────────────────────────────────────────────────────────────┘
The Architectural Blueprint

LogTreeDB synthesizes four foundational systems techniques:

WiscKey Key-Value Separation: Document payloads are appended sequentially to immutable segment files (vlog_%08u.log) and never updated in place. The B+Tree index remains lightweight because it stores only slim 24-byte physical pointers (VPtr).
Bounded Delta Update Logging (kMaxDeltaChain = 4): Mutating a single field via $set or $inc appends an ~96-byte delta record rather than rewriting multi-kilobyte documents, slashing write amplification by
3.65
×
3.65× to
4.78
×
4.78× while guaranteeing point read latencies under
130
𝜇
s
130μs.
Dual-Slot Ping-Pong Superblock & COW Index: Metadata updates alternate between two 4 KiB disk slots with monotonic epoch counters and hardware-accelerated CRC32C validation. Sibling-free copy-on-write index pages ensure committed state is never mutated in place, completely eliminating write corruption and the need for a separate Write-Ahead Log (WAL).
Adaptive Leader/Follower Group Commit: Overcoming the physical disk barrier of SSD write flushes (~3.7 ms per flush) by coalescing parallel transactions into a single sequential disk write and a single flush barrier.

Across 354+ randomized kill -9 process crashes during active group commits, live checkpoints, and background garbage collection, LogTreeDB demonstrated zero data loss and zero dead-version resurrection across hundreds of thousands of verified operations.

  1. The Origin: From MERN Black Box to Storage Internals

Before building LogTreeDB, I had spent two years building full-stack applications on the MERN stack (MongoDB, Express, React, Node.js). To an application developer, the database is an abstraction: you call db.users.updateOne({ _id }, { $set: { "profile.bio": "New bio" } }), get an { acknowledged: true } promise back, and move on.

Eventually, curiosity took over: What actually happens on the physical SSD when an app calls updateOne? How does the engine ensure that if power cuts out 50 microseconds later, that modification is not lost? Why does updating a 10-byte string in a 4-kilobyte document consume so much disk I/O?

That sparked the core research question:

Can I build an ACID crash-safe document database from scratch in modern C++17, with zero external dependencies, that writes fewer bytes per update than a classic page-based engine while keeping every acknowledged write safe through process crashes?

To answer that question, every claim in this paper is measured empirically, and every trade-off—including where LogTreeDB loses to mature engines like SQLite—is documented transparently.

  1. Foundational Literature & Systems Decisions

Two foundational textbooks provided the theoretical vocabulary, and four seminal papers provided the architectural design.

text
Foundational Literature Matrix:
┌──────────────────────────────────────┬────────────────────────────────────┬───────────────────────────────────────┐
│ Literature Source │ Core Concept Borrowed │ Manifestation in LogTreeDB │
├──────────────────────────────────────┼────────────────────────────────────┼───────────────────────────────────────┤
│ Alex Petrov, │ Slotted page layouts, cell offsets,│ Slotted 4 KiB disk index pages, │
│ Database Internals (Ch. 3–5) │ buffer pool steal/no-force, WAL │ frame cache, epoch checkpoints │
├──────────────────────────────────────┼────────────────────────────────────┼───────────────────────────────────────┤
│ Alex Petrov, │ Copy-on-Write B-Trees, │ Sibling-free COW index pages; isolates│
│ Database Internals (Ch. 6) │ eliminating split cascades │ cloning strictly to root-to-leaf path │
├──────────────────────────────────────┼────────────────────────────────────┼───────────────────────────────────────┤
│ Martin Kleppmann, │ Bitcask append-only logs, │ Log-structured append, │
│ Designing Data-Intensive Apps (Ch. 3)│ B-tree vs. LSM write amplification │ measuring bytes written per update │
├──────────────────────────────────────┼────────────────────────────────────┼───────────────────────────────────────┤
│ WiscKey (FAST '16, Lu et al.) │ Key-value separation on SSDs, │ The core engine: immutable vLog + │
│ │ small index pointers, vLog GC │ 24-byte B+Tree pointers │
├──────────────────────────────────────┼────────────────────────────────────┼───────────────────────────────────────┤
│ The RUM Conjecture (EDBT 2016) │ Cannot minimize Read, Update, and │ Chose minimal Update cost; paid in │
│ │ Memory overhead simultaneously │ range-scan throughput and space │
├──────────────────────────────────────┼────────────────────────────────────┼───────────────────────────────────────┤
│ The Bw-Tree (ICDE 2013, Levandoski) │ Delta records prepended to base │ Delta chains for $set/$inc, cap=4 │
├──────────────────────────────────────┼────────────────────────────────────┼───────────────────────────────────────┤
│ LeanStore (ICDE 2018, Leis et al.) │ Pointer swizzling, buffer pools │ Evaluated and discarded (see below) │
└──────────────────────────────────────┴────────────────────────────────────┴───────────────────────────────────────┘
What I Profiled and Chose NOT to Build

Early in the project, I planned to build a latch-free index using pointer swizzling (LeanStore) and thread-per-core execution (ScyllaDB). A 10-second CPU profiler trace under a 16-thread mixed workload (~52,800 stack samples) abruptly killed that plan:

93.2% of worker time was spent blocked waiting for the group commit's F_FULLFSYNC system call.
5.8% of worker time was spent waiting inside the sequencer condition variable.
The read path took only 180 samples (<0.4%), and JSON parsing took under 70 samples (<0.15%).

Building a latch-free in-memory index would have produced zero measurable throughput gains because the physical disk write barrier was the entire bottleneck. As a result, the index retained a clean, maintainable reader-writer lock per tree, and engineering effort was directed where it mattered: batching physical flushes and moving checkpoint I/O out of write locks.

  1. Version 1: The Failure of MongoLite (The Slotted-Page & WAL Trap)

To understand why LogTreeDB is designed the way it is, one must understand how its predecessor failed.

My first engine, MongoLite, followed textbook database implementation to the letter:

Slotted Pages: Fixed 4096-byte pages with an array of line pointers at the front growing forward and variable-length document cells growing backward.
BufferPoolManager & LRUReplacer: A frame pool with an
𝑂
(
1
)
O(1) LRU replacer using a textbook steal/no-force policy.
WALManager: Monotonic Log Sequence Numbers (LSNs), redo log records, and checkpoint truncation.
Primary Index: Documents addressed by RecordId(page_id, slot_id) with an in-memory index.

Initial synthetic benchmarks appeared astonishing: 183,383 inserts/second and 1.52 million reads/second on 4 threads. But those numbers were an illusion: the WAL had never called fsync. It was measuring RAM bandwidth, not a durable database.

The Crash Post-Mortem

When MongoLite was subjected to true durability testing—triggering F_FULLFSYNC after every transaction and injecting kill -9 process crashes during writes—the engine collapsed:

text
MongoLite vs. LogTreeDB Durability & Write Amplification:
┌───────────────────────────────────────────────┬──────────────┬──────────────┐
│ Metric (1 KB Documents) │ MongoLite │ LogTreeDB │
├───────────────────────────────────────────────┼──────────────┼──────────────┤
│ 1-Thread Updates / sec │ 274 │ 257 │
│ 16-Thread Updates / sec │ 287 │ 3,363 │
│ 16-Thread Bytes Written / Update (Physical) │ 21,852 B │ 1,384 B │
│ 8 KB Document Support │ Unsupported │ Full Support │
│ Acked Updates Lost under kill -9 (3 runs/2500)│ 863, 852, 859│ 0, 0, 0 │
│ In-Memory Point Gets / sec │ 283,476 │ 123,646 │
└───────────────────────────────────────────────┴──────────────┴──────────────┘

MongoLite lost over 34% of its acknowledged transactions across every crash run. Furthermore, it suffered from three fundamental architectural flaws:

The Slotted-Page WAF Penalty: If a user updates a 10-byte integer in a 2 KiB document, the engine dirties the entire 4 KiB page. When the buffer pool flushes that page to disk along with its WAL record:

WAF

4096
B (Page)
+
128
B (WAL)
10
B (Payload)
≈
422
×
WAF=
10B (Payload)
4096B (Page)+128B (WAL)
​

≈422×
Document Relocation Fragmentation: In a document database, documents frequently grow when fields are added or strings expand. In a slotted page, if a document expands beyond available slot space, it must move to another page. This breaks its physical RecordId(page_id, slot_id), requiring complex forwarding pointers or updating every secondary index.
Hard Document Size Limits: A document could never exceed 4096 bytes minus page header overhead. Handling 100 KB or 1 MB documents required building complex overflow page chains.
Deep Dive: B+ Tree Advantages vs. Write Bottlenecks

Understanding this failure requires analyzing why classic B+ Trees dominate reads but struggle on writes:

text
B+ Tree Fundamental Trade-Offs:
┌──────────────────────────────────────┬──────────────────────────────────────┐
│ Why B+ Trees Excel at READS │ Why B+ Trees Struggle on WRITES │
├──────────────────────────────────────┼──────────────────────────────────────┤
│ 1. Low Tree Height (High Fanout): │ 1. Random Disk I/O: │
│ With a 4KB page and 32-byte keys, │ Inserting non-sequential keys forces │
│ fanout B ≈ 128. A tree holding │ the engine to read a random page from│
│ 1,000,000 keys has a height of only │ disk, dirty it in RAM, and write it │
│ 3 to 4 levels. Lookups take ≤ 4 I/Os.│ back, thrashing SSD flash memory. │
├──────────────────────────────────────┼──────────────────────────────────────┤
│ 2. Sequential Linked Leaf Nodes: │ 2. Cascading Page Splits: │
│ All data entries live in leaf pages. │ When an insert hits a full page, it │
│ Range queries (e.g., age 20 to 30) │ splits into two, requiring parent │
│ scan horizontally across leaf links │ updates and rebalancing, which cause │
│ without traversing back up the tree. │ severe latency spikes during writes. │
└──────────────────────────────────────┴──────────────────────────────────────┘

The Core Lesson: A throughput benchmark without fsync is a benchmark of memory, not a database. To handle high-concurrency document workloads without catastrophic write amplification, the storage layer had to decouple document storage from the indexing tree.

  1. Storage Engine Architecture (IndexedStore)

LogTreeDB solves the slotted-page bottleneck by combining WiscKey key-value separation, an append-only Value Log, a sibling-free COW B+Tree, and a dual-slot ping-pong superblock.

5.1 The Value Log (vLog)

The value log is organized as a sequence of immutable disk segments: /vlog/vlog_%08u.log.

text
Byte-Level vLog Entry Layout (8-Byte Aligned):
+--------------------+--------------------+--------------------+--------------------+
| CRC32C (4 Bytes) | TotalLen (4 Bytes)| Sequence (8 Bytes)| KeyLen (2 Bytes) |
+--------------------+--------------------+--------------------+--------------------+
| ValLen (4 Bytes) | EntryType (1 Byte)| Flags (1 Byte) | Reserved (8 Bytes)|
+--------------------+--------------------+--------------------+--------------------+
| Key String (KeyLen Bytes) | Payload Bytes (ValLen Bytes) |
+-----------------------------------------+-----------------------------------------+
| Alignment Padding (0 to 7 Bytes) |
+-----------------------------------------------------------------------------------+
Structural Invariants of the vLog:
4 KiB Segment Header: Every segment begins with a 4096-byte header containing a magic byte sequence (0x564C4F47), format version, segment sequence ID, and nanosecond creation timestamp.
8-Byte Record Alignment: Every entry is strictly padded to an 8-byte boundary, guaranteeing aligned direct memory access during pread().
Hardware Bit-Rot Protection: The entry header begins with an ARMv8 / SSE4.2 hardware-accelerated CRC32C checksum computed over the remaining TotalLen - 4 bytes. Any physical bit decay on disk aborts the read immediately rather than returning corrupted state.
Crash Truncation Rules: Segments are opened with O_CREAT | O_EXCL and never appended to after a crash. During startup recovery, a torn write is truncated only in the final active segment. Damaged bytes anywhere else fail the recovery loudly, preventing silent data loss.
Descriptor Cache (64 File Descriptors): An internal LRU cache maintains open file descriptors for active segments, transforming reads into a single pread() system call without recurring open(), fstat(), and close() overhead.
5.2 The Group Commit Pipeline: Overcoming the Physical Flush Barrier

On macOS with internal Apple Silicon SSDs, issuing an fcntl(fd, F_FULLFSYNC) forces the SSD controller cache to flush to non-volatile NAND flash. This hardware operation takes ~3.7 milliseconds, imposing a hard physical ceiling of ~270 sync operations per second for a single thread.

LogTreeDB bypasses this barrier through an Adaptive Leader/Follower Group Commit Pipeline:

text
Empirical Group Commit Scaling (Apple M5 SSD):
┌────────────────┬───────────────────┬───────────────────────┬─────────────────┐
│ Writer Threads │ Writes / Second │ F_FULLFSYNC / Second │ Average Batch │
├────────────────┼───────────────────┼───────────────────────┼─────────────────┤
│ 1 thread │ 260 ops/sec │ 261 flushes/sec │ 1.0 writes │
│ 4 threads │ 544 ops/sec │ 273 flushes/sec │ 2.0 writes │
│ 16 threads │ 2,155 ops/sec │ 270 flushes/sec │ 8.0 writes │
│ 64 threads │ 8,692 ops/sec │ 272 flushes/sec │ 31.9 writes │
└────────────────┴───────────────────┴───────────────────────┴─────────────────┘

The hardware flush rate remains clamped at ~270 flushes/second regardless of thread count. Throughput scales by
33.4
×
33.4× purely because each physical flush carries dozens of amortized transactions.

5.3 Sibling-Free Copy-on-Write (COW) B+Tree

LogTreeDB's primary index (index.db) stores 4 KiB slotted pages, but deviates completely from textbook B+Trees:

Lightweight Pointers: Leaf cells store only the document key and a 24-byte VPtr (sequence, segment ID, offset, length). For 100,000 documents, the entire B+Tree is 10.5 to 13.7 MiB, fitting entirely within the OS page cache (compared to >130 MiB if documents were stored in leaves).
Why Sibling Pointers Were Eliminated: In a classic B+Tree, leaf nodes maintain bidirectional horizontal pointers (prev / next) for range scans. In a Copy-on-Write tree, modifying a page allocates a new page ID. If leaves had sibling pointers, updating a leaf would require modifying its neighbors' pointers, which would trigger COW cloning of their ancestor paths—cascading across the entire tree! Eliminating sibling pointers isolates path cloning strictly to the single modified leaf's ancestors (
𝑂
(
height
)
O(height)).
In-Memory Parent-Stack Traversal: Range scans (store_->scan()) traverse ordered keys without sibling pointers by maintaining a lightweight traversal stack of parent node IDs and slot offsets in memory, achieving
𝑂
(
log
⁡
𝑁
+
𝐾
)
O(logN+K) scan complexity.
The
𝐸
+
2
E+2 Delayed Page Reuse Rule: When a page is superseded during checkpoint epoch
𝐸
E, it cannot be recycled immediately. If the system crashes, recovery must roll back to checkpoint
𝐸
−
1
E−1. A freed page is returned to the allocator's free list only after checkpoint epoch
𝐸
+
2
E+2 commits, ensuring both superblock slots reference structurally intact trees.
5.4 Dual-Slot Ping-Pong Superblock & Crash Recovery

LogTreeDB eliminates the need for a separate Write-Ahead Log by treating the append-only vLog as the source of truth, synchronized via an 8 KiB dual-slot ping-pong file (superblock.db).

text
Superblock Ping-Pong Layout (8192 Bytes):
+-------------------------------------------+-------------------------------------------+
| Slot 0 (Bytes 0 to 4095) | Slot 1 (Bytes 4096 to 8191) |
| Epoch: E | Root Page: #42 | Epoch: E+1 (Active Committed State) |
| Replay VPtr: Seg 3, Off 1024 | Replay VPtr: Seg 4, Off 512 |
| Hardware CRC32C Checksum | Hardware CRC32C Checksum |
+-------------------------------------------+-------------------------------------------+
The Two-Phase Checkpoint Flush Protocol:
Hold Locks Briefly: The engine acquires index locks only long enough to capture: the last applied sequence number, the current vLog file position, the root page ID, and in-memory clones of dirty index pages. Locks are released immediately.
Phase 1 (Index Flush): The dirty index pages are written to index.db and flushed via F_FULLFSYNC.
Phase 2 (Superblock Commit): The alternate superblock slot is updated with epoch
𝐸
+
1
E+1, the new root page, the vLog replay pointer, and its CRC32C, followed by a second F_FULLFSYNC.

If a crash or power cut occurs during Phase 1, the superblock still points to epoch
𝐸
E. On reboot, the engine opens epoch
𝐸
E and replays any newer vLog records. If a crash occurs during Phase 2, the CRC32C of the uncommitted slot fails, and the engine safely reverts to epoch
𝐸
E.

text
Crash Recovery Sequence:

  1. Validate format version, random nonce, and CRC32C on both superblock slots.
  2. Select the valid slot with the highest monotonic epoch counter.
  3. Validate every page in the committed tree structure.
  4. Truncate index.db to the committed page count recorded in the winning slot.
  5. Rebuild the free list by walking the active tree.
  6. Replay vLog sequentially starting from the slot's Replay VPtr. -> Higher sequence numbers overwrite older pointers; tombstones erase entries.

In automated crash testing, recovering a database with 6,000 operations across 30 segments with 200 uncheckpointed writes completed in 11.3 milliseconds.

5.5 Bounded Delta Update Logging (kMaxDeltaChain = 4)

When an application calls updateOne with update operators like {$inc: {"profile.views": 1}}, rewriting a multi-kilobyte document creates massive write amplification. LogTreeDB solves this with Delta Chains:

text
Delta Chain Traversal (Bounded to kMaxDeltaChain = 4):
+---------------+ +---------------+ +---------------+ +------------------+
| Index Head | ----> | Delta 2 | ----> | Delta 1 | ----> | Base Document |
| (Points to D2)| | ($set status) | | ($inc views) | | (Full JSON Copy) |
+---------------+ +---------------+ +---------------+ +------------------+
Hop 1 Hop 2 Hop 3
Strict Invariants of Delta Chains:
The 4-Hop Cap: A chain is strictly capped at 4 deltas. If an update would push chain_depth > 4, or if accumulated delta operations exceed 50% of the document's total size, the engine consolidates: it resolves the document in memory and writes an unchained Full Document Entry flagged kFlagConsolidated.
1024 Key Stripe Locks: Every write operation computes

stripe

std::hash
(
key
)
(
m
o
d
1024
)
stripe=std::hash(key)(mod1024). The writer holds stripe_mutex[stripe] from reading the current version until the new vLog entry is applied to the index, preventing concurrent updates from creating branched or orphaned delta chains.
Global Sequencer (applyInOrder): While group commit batches writes across different keys out of order to saturate disk throughput, index updates must be applied in strict log sequence. Each writer thread waits on a condition variable until next_apply_seq == my_assigned_seq, applies its modification to the B+Tree, advances next_apply_seq, and signals waiting threads.
text
Measured Byte Savings: 10,000 $inc Updates on Single Key:
┌───────────────┬────────────────────────────┬────────────────────────────┬─────────────┐
│ Document Size │ Full Rewrite (put) / Op │ Delta (cap 4) / Op │ WAF Savings │
├───────────────┼────────────────────────────┼────────────────────────────┼─────────────┤
│ 1 KB Doc │ 1,074 bytes │ 293 bytes │ 3.67x lower │
│ 2 KB Doc │ 2,100 bytes │ 498 bytes │ 4.22x lower │
│ 8 KB Doc │ 8,257 bytes │ 1,729 bytes │ 4.78x lower │
└───────────────┴────────────────────────────┴────────────────────────────┴─────────────┘

A delta record consumes ~96 bytes. The average byte volume is dominated by the fifth update that writes a full consolidated copy: out of 10,000 updates, 8,000 wrote tiny deltas and 2,000 wrote consolidated baselines.

5.6 Online Garbage Collection

Because the vLog is append-only, superseded deltas and deleted documents accumulate dead space.

text
Segment Lifecycle State Machine:
[Active Segment]
│ (Fills to 4 MiB)
▼
[Sealed Segment]
│ (Overwrites / Deletes drop Live Ratio < 0.5)
▼
[Victim Selection]
│ (Sort sealed segments by lowest live_bytes / total_bytes)
▼
[Striped Batch Relocation]
│ (Acquire stripe locks in ascending order -> appendRelocated() -> update index)
▼
[Epoch Quarantine (E + 2)]
│ (Wait until two successive checkpoint epochs commit & active readers unpin)
▼
[Superblock Condemned List]
│ (Segment ID written to superblock condemned list -> F_FULLFSYNC)
▼
[Physical Unlink & Directory Fsync]
In-Memory Space Accounting: A concurrent tracker maintains total_bytes and live_bytes per segment. A full document overwrite or tombstone deducts the previous chain's bytes from the respective segment's live counter.
Deadlock-Free Relocation: When evacuating a candidate segment, live documents are read and their stripe locks acquired in strict ascending numerical order, eliminating lock inversion deadlocks with incoming client writes.
Idempotent Relocation: Relocated entries retain their original seq sequence number. If a crash interrupts GC, recovery replay remains strictly idempotent.
Crash-Safe Segment Unlinking: A segment file is only physically unlinked after its segment ID is recorded in the superblock's condemned array and fsynced across two checkpoint epochs.

  1. Query Engine, Indexes & Client Ecosystem

LogTreeDB implements a complete MongoDB-compatible query pipeline and client architecture.

6.1 Key Scheme & Unified Key Space

LogTreeDB isolates collections, indexes, and catalogs inside a single unified B+Tree key space using null-byte (\0) delimiters:

text
Unified Key Space Partitioning:
┌───────────────────────┬──────────────────────────────────────────┬─────────────────────────────┐
│ Key Purpose │ Binary Key Format │ Value Content │
├───────────────────────┼──────────────────────────────────────────┼─────────────────────────────┤
│ Document Key │ \0\0 │ 24-byte VPtr to vLog │
│ Database Metadata │ \0cat\0db\0 │ JSON metadata object │
│ Collection Metadata │ \0cat\0coll\0\0 │ JSON metadata object │
│ Index Catalog │ \0cat\0idx\0\0\0 │ Index schema definition │
│ Secondary Index Entry │ \0idx\0\0\0<_id> │ Empty (Index key holds data)│
└───────────────────────┴──────────────────────────────────────────┴─────────────────────────────┘

The prefix distinguishes between string IDs ('s') and binary ObjectIds ('o'), preventing collision between "_id": "6737..." and "_id": ObjectId("6737...").

6.2 Secondary Indexes & Order-Preserving Encodings

Secondary index values are encoded into sortable binary byte strings (encodeIndexValue):

Type Precedence: Null (0) < Numbers (1) < Strings (2) < Objects (3) < Arrays (4) < Booleans (5) < ObjectId (6).
IEEE 754 Floating-Point Normalization: Converts 64-bit doubles to order-preserving unsigned integers with sign-bit inversion, allowing floating-point values to sort correctly under standard lexicographical byte comparison.
Array Invalidation (hasArrays): If an application inserts an array into an indexed scalar field, the catalog permanently flags hasArrays = true, safely falling back to collection scans to preserve correct multi-key query semantics.
6.3 Aggregation Pipeline Engine

LogTreeDB implements a pull-based memory-bounded generator supporting:

Stages: $match, $project, $addFields, $group, $sort, $skip, $limit, $count, $unwind.
Accumulators: $sum, $avg, $min, $max, $count, $push.
Optimizer Pushdown: Leading $match stages are detected by Pipeline::leadingMatch() and pushed down to the storage engine as index range scans.
Strict Memory Caps: Intermediate state in $group and $sort is bounded to 64 MiB. Exceeding this limit aborts with MemoryLimitError, preventing out-of-memory kernel panics.
6.4 Client Ecosystem (Node.js Driver, Shell, Web UI)

The client ecosystem was built with zero external dependencies using only Node.js standard modules (node:net, node:crypto):

Pipelined Driver (logtreedb-driver): Multiplexes concurrent asynchronous requests across a single persistent TCP connection with auto-reconnection and Extended JSON 64-bit integer handling ($numberLong).
Interactive REPL (logtreedb-shell): Terminal interface mimicking mongosh with multi-line editing and query helpers.
Web Admin Console (logtreedb-ui): A zero-dependency embedded dashboard (vanilla JavaScript and CSS) featuring connection management, visual document querying, schema statistics, index creation, and aggregation debugging.
sh

Pull and start official Docker container

docker run -d --name logtreedb -p 127.0.0.1:7070:7070 -v logtreedb-data:/data pravi2005/logtreedb:latest

Connect via interactive CLI shell

npx -p logtreedb-driver logtreedb-shell logtreedb://localhost:7070/myapp

Launch web administration dashboard

npx -p logtreedb-driver logtreedb-ui --db 127.0.0.1:7070 --port 8080

  1. Empirical Benchmarks & Systems Comparison

All benchmarks were executed on an Apple M5 machine (10 CPU cores, 16 GB unified RAM, Apple internal APFS SSD, macOS 27.0).

Benchmark Invariants & Methodology:
Strict Durability: Every acknowledged write across all three engines enforced physical non-volatile disk flushes (fcntl(F_FULLFSYNC) on macOS).
VFS Shim for SQLite: macOS's default SQLite implementation quietly translates PRAGMA fullfsync = ON into F_BARRIERFSYNC, which only flushes to volatile drive cache (0.34 ms vs. 3.8 ms). To ensure absolute fairness, SQLite 3.54 was run with a custom VFS shim forcing true F_FULLFSYNC on every transaction commit.
MongoLite Synchronization: MongoLite's WAL was modified to call F_FULLFSYNC after every operation.
Dataset: 25,000 documents pre-populated, followed by 10,000 single-field update operations (profile.score + 1). All numbers reflect the median of 3 independent runs.
7.1 Headline Results: Write Amplification & Throughput
text
Benchmark Comparison: 10,000 Updates on 25,000 Pre-Loaded Documents:
┌────────────────────────────────────────┬─────────────┬─────────────┬─────────────┬───────────────────────────┐
│ Workload Configuration │ LogTreeDB │ SQLite 3.54 │ MongoLite │ Performance Advantage │
├────────────────────────────────────────┼─────────────┼─────────────┼─────────────┼───────────────────────────┤
│ Bytes Written / Op (1 KB, 16 threads) │ 1,384 B │ 33,300 B │ 21,852 B │ 24.1x lower write volume │
│ Bytes Written / Op (2 KB, 16 threads) │ 1,382 B │ 35,405 B │ 26,003 B │ 25.6x lower write volume │
│ Bytes Written / Op (8 KB, 16 threads) │ 2,044 B │ 34,287 B │ Unsupported │ 16.7x lower write volume │
├────────────────────────────────────────┼─────────────┼─────────────┼─────────────┼───────────────────────────┤
│ Throughput (1 KB, 16 threads) │ 3,363 ops/s │ 313 ops/s │ 287 ops/s │ 10.7x higher throughput │
│ Throughput (2 KB, 16 threads) │ 3,402 ops/s │ 309 ops/s │ 240 ops/s │ 11.0x higher throughput │
│ Throughput (8 KB, 16 threads) │ 2,216 ops/s │ 284 ops/s │ Unsupported │ 7.8x higher throughput │
├────────────────────────────────────────┼─────────────┼─────────────┼─────────────┼───────────────────────────┤
│ Flushes per Update (1 KB, 16 threads) │ 0.067 │ 1.01 │ 1.00 │ 15x fewer physical flushes│
│ Post-GC Space Amplification │ 1.04x–1.32x │ 1.36x–2.01x │ 2.40x–3.60x │ Significantly denser │
└────────────────────────────────────────┴─────────────┴─────────────┴─────────────┴───────────────────────────┘
Why SQLite and MongoLite Stall under Concurrency

At 16 threads, SQLite in WAL mode and MongoLite still issue ~1.0 physical flushes per transaction. Adding writer threads creates lock contention without amortizing physical I/O. In contrast, LogTreeDB's group commit achieves 0.067 flushes per update, packing up to 32 parallel updates into a single sequential disk flush.

7.2 Latency Percentiles under 16-Thread Concurrency

Measured across 100,000 mixed operations (35% put, 45% update, 10% erase, 10% get):

text
16-Thread Latency Percentile Distribution:
┌───────────────────────────────────┬──────────────┬──────────┬──────────┬──────────┬───────────┐
│ Operation Type │ Sample Size │ p50 │ p90 │ p99 │ p99.9 │
├───────────────────────────────────┼──────────────┼──────────┼──────────┼──────────┼───────────┤
│ put (New Document) │ 35,145 ops │ 4.77 ms │ 8.08 ms │ 9.83 ms │ 16.0 ms │
│ update (Delta Record) │ 42,971 ops │ 4.83 ms │ 8.22 ms │ 9.94 ms │ 13.5 ms │
│ erase (Tombstone) │ 10,078 ops │ 4.81 ms │ 8.16 ms │ 9.91 ms │ 14.1 ms │
│ get (Depth 0 - Full Document) │ ~7,846 ops │ 36 µs │ 216 µs │ 262 µs │ 350 µs │
│ get (Depth 1 to 4 - Delta Chain) │ ~1,594 ops │ 64 µs │ 279 µs │ 457 µs │ 722 µs │
└───────────────────────────────────┴──────────────┴──────────┴──────────┴──────────┴───────────┘

Point reads at depth 0 return in
36
𝜇
s
36μs, while traversing a 4-hop delta chain and deserializing JSON in memory completes in
64
𝜇
s
64μs (p50).

7.3 Optimization Impact: Before vs. After

During engine profiling, four targeted architectural changes transformed system throughput:

Segment Rollover Re-Check: Fixed a race condition where 16 threads encountering segment rollover simultaneously created 240 nearly-empty segment files.
Open Descriptor Pool: Cached 64 file descriptors for active vLog segments.
Adaptive 500 µs Commit Window: Doubled group commit batch size without penalizing isolated writers.
Out-of-Lock Checkpoint Flushing: Writing and syncing dirty index pages outside reader-writer locks dropped checkpoint lock hold times by 89%.
text
Impact of Optimization Profiling (100,000-Key Stress Workload, 16 Threads):
┌────────────────────────────────────────┬─────────────┬─────────────┬─────────────┐
│ Architectural Metric │ Before │ After │ Improvement │
├────────────────────────────────────────┼─────────────┼─────────────┼─────────────┤
│ Mixed Ops / sec (GC Enabled) │ 2,407 ops/s │ 3,711 ops/s │ +54.2% │
│ put Latency p99.9 (GC Enabled) │ 111.1 ms │ 14.6 ms │ -86.8% │
│ get Latency p50 │ 100 µs │ 36 µs │ -64.0% │
│ Checkpoint Lock Hold (Median / Max) │ 7.7 / 22 ms │ 0.8 / 3.4 ms│ -89% / -85% │
│ Average Group Commit Batch Size │ 7.7 writes │ 15.1 writes │ ~2x batching│
└────────────────────────────────────────┴─────────────┴─────────────┴─────────────┘
7.4 Transparent Systems Honesty: Where SQLite & MongoLite Win

Engineering integrity demands acknowledging where alternative architectures outperform LogTreeDB:

text
Workload Trade-Off Matrix:
┌─────────────────────────────────────┬──────────────┬──────────────┬──────────────┐
│ Workload Metric │ LogTreeDB │ SQLite 3.54 │ MongoLite │
├─────────────────────────────────────┼──────────────┼──────────────┼──────────────┤
│ 1-Thread Updates / sec │ 257 ops/s │ 340 ops/s │ 274 ops/s │
│ 100-Key Sequential Range Scans / sec│ 1,423 scans/s│ 9,166 scans/s│ 2,110 scans/s│
│ Immediate File Growth on Disk │ 449 B / op │ 0 B (In-Place│ 0 B (In-Place│
│ In-Memory Point Gets / sec │ 123,646 ops/s│ 114,737 ops/s│ 283,476 ops/s│
└─────────────────────────────────────┴──────────────┴──────────────┴──────────────┘
Single-Threaded Updates: When concurrency is 1, SQLite's localized rollback journal or WAL commits faster (340 vs. 257 ops/sec) because LogTreeDB incurs mutex staging and condition variable overhead.
Range Scans: SQLite delivers
6.4
×
6.4× faster 100-key range scans. Because SQLite clusters row data directly inside B-tree leaf pages, scanning 100 rows traverses contiguous disk blocks. LogTreeDB's WiscKey separation stores only pointers in leaves, requiring 100 separate pread() calls across vLog segments.
Immediate Disk Growth: SQLite updates data in place (0 bytes immediate file growth). LogTreeDB appends to the log, expanding disk usage until the background Garbage Collector runs.
In-Memory Reads: MongoLite's raw in-memory slotted pages achieve 283,476 gets/sec vs. LogTreeDB's 123,646 gets/sec, because LogTreeDB traverses delta chains and validates CRC32C checksums.

  1. Extreme Crash Testing & Formal Verification

Storage systems cannot be validated solely through happy-path unit tests. LogTreeDB underwent extensive fault injection, sanitizer runs, and randomized kill -9 crash campaigns.

text
Fault Injection & Process Crash Summary:
┌──────────────┬────────────────────────────────────────────┬────────┬─────────────────────────────┐
│ Suite ID │ Injected Fault / Process Kill Point │ Runs │ Verification Result │
├──────────────┼────────────────────────────────────────────┼────────┼─────────────────────────────┤
│ V9 │ kill -9 vLog writer during group commit │ 50 │ 21,926 recovered, 0 lost │
│ B5.2 │ kill -9 Store during active concurrent ops │ 50 │ 17,073 acked ops verified │
│ CP11 │ kill -9 between index fsync & superblock │ 50 │ 12,507 acked ops verified │
│ P4.G1 │ kill -9 during stream of single-key $inc │ 20 │ 1,994 acked ops verified │
│ P4.G2 │ kill -9 during random multi-key deltas │ 20 │ 2,240 acked ops verified │
│ P5.H1–H5 │ kill -9 across 5 distinct GC phases │ 5 │ Zero corruption, 0 lost │
│ P6.C3 │ kill -9 inside checkpoint with 16 writers │ 9 │ Index equals full replay │
│ Chaos Soak │ 16 threads + background GC killed randomly │ 150 │ 112,305 acked ops verified │
├──────────────┼────────────────────────────────────────────┼────────┼─────────────────────────────┤
│ Total │ Process Crash Injections (kill -9) │ 354 │ 168,045+ Operations Verified│
└──────────────┴────────────────────────────────────────────┴────────┴─────────────────────────────┘
The Chaos Verification Protocol

In the 150 chaos iterations:

16 worker threads hammered the engine with random put, update, erase, and get operations while background GC evacuated segments.
The harness sent kill -9 to the process at randomized intervals (between 400 and 4,399 acknowledged writes).
Upon restart, the engine reopened and every key was compared against the client's acknowledged log.
Next, superblock.db was deliberately deleted, forcing a cold index rebuild directly from the raw vLog segments. In 50 out of 50 recorded runs (204,800 key comparisons), the recovered index matched the cold-rebuilt index bit-for-bit.
Hardware Bit-Rot Simulation (B1.1)

To verify resilience against physical media degradation, every single one of the 32,768 possible single-bit flips across a 4096-byte page was systematically simulated. In 100% of cases, the hardware-accelerated CRC32C routine rejected the corrupt page and aborted the read, preventing corrupted memory state from propagating.

Reality Check on Fanless Hardware

To verify stability under resource constraints, the engine was stressed on a fanless MacBook Air under strict safety limits:

9.1 Million Documents: A 64-thread load inserted 9,095,650 documents before halting cleanly at a 40 GB write budget. Reopening took 53.9 seconds, with zero key holes across any thread.
30-Minute Chaos Soak: 8 writers and 4 readers with continuous GC, checkpoints, and a kill -9 every 5 minutes: 179,480 acknowledged writes, 61.8 million reads, zero corruptions.
Disk Full Recovery (ENOSPC): Inside a 512 MB disk image, writes halted cleanly upon receiving ENOSPC. Reopening in read-only mode functioned without corruption; once space was freed, writes resumed normally.
16 MB Large Documents: Documents up to the 16,777,168-byte limit succeeded through put, get, delta update, scan, checkpoint, GC, and crash recovery. Exceeding the limit by 1 byte failed with a clean error.

  1. Hard-Earned Systems Engineering Lessons

Many of the deepest insights came from code that failed during real-world testing:

fsync() Does Not Guarantee Durability on macOS: On macOS, standard fsync() only flushes dirty blocks to the drive's volatile cache. True durability requires fcntl(fd, F_FULLFSYNC). SQLite on macOS falls back to F_BARRIERFSYNC unless custom VFS shims are provided.
POSIX write() Is Never Guaranteed to Be Complete: Under heavy disk load, write() frequently writes fewer bytes than requested or returns EINTR. Storage engines must wrap every I/O call in a strict writeAll() loop.
The Segment Rollover Concurrency Race: When 16 threads filled an active segment simultaneously, each thread attempted to roll over the segment, creating ~240 nearly-empty segments instead of 36. The fix: threads must re-check segment size under the lock after waiting on an in-flight flush.
Catastrophic Regex Backtracking: Standard std::regex in libstdc++ uses exponential backtracking. A malicious regex like (a+)+$ against a repetitive payload hangs worker threads indefinitely. On Linux, nested repeating groups are now rejected at parse time.
The Missing Databases Mystery: During testing, two test databases (myapp and test) vanished from a local server instance. Investigation revealed that demo/run.sh was silently attaching to an existing background instance on port 7070. Test harnesses must strictly enforce isolated ports and ephemeral directories.
Laptop Sleep Stalls Benchmarks: Two benchmark runs recorded unexplained 17-minute write pauses: the MacBook had gone to sleep while running unattended! All subsequent benchmark suites ran under caffeinate.
Client Driver Reconnection Semantics: In the Node.js driver, if a connection drops, operations already sent across the wire are never silently retried, because the write may have already committed on disk. Silent retries would violate non-idempotent operation semantics ($inc).

  1. Known Limitations & Architectural Roadmap

LogTreeDB is a single-node engine designed for embedded and local workloads. Engineering honesty requires highlighting where it is not yet complete:

Current Limitations:
Single-Node Architecture: No clustering, consensus protocols (Raft/Paxos), sharding, or multi-node replication.
No Multi-Document Transactions: ACID durability is guaranteed per document; there are no cross-document multi-statement transactions.
Range Scan Penalty: Because keys are separated from values (WiscKey), full collection range scans incur random pread() calls across vLog segments.
Local Interface Binding: The server listens on 127.0.0.1 only. It lacks TLS encryption and role-based authentication, making it unsuitable for direct exposure to untrusted public networks.
Startup Reopen Scaling: Rebuilding GC tracking counters on startup requires reading one entry per key, taking 15.5 seconds at 2.5 million keys and 53.9 seconds at 9.1 million keys.
Next Engineering Iterations:
Persistent GC Metadata: Persisting segment live-byte counters in the superblock to drop startup reopen times from 53 seconds to under 50 milliseconds.
Clustered GC Relocation: Grouping logically adjacent documents into identical physical segments during GC to accelerate range scan performance.
Server Audit Trail: Logging all collection drops and bulk deletes with timestamps and client metadata.
Rust Native Desktop GUI: Developing a high-performance native desktop application to complement the web admin console.

  1. Academic & Literature References Alex Petrov. Database Internals: A Deep Dive into How Distributed Data Systems Work. O'Reilly Media, 2019. Chapters 1–7. Martin Kleppmann. Designing Data-Intensive Applications. O'Reilly Media, 2017. Chapter 3: Storage and Retrieval. Lanyue Lu, Thanumalayan Sankaranarayana Pillai, Hariharan Gopalakrishnan, Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau. WiscKey: Separating Keys from Values in SSD-Conscious Storage. USENIX FAST 2016. Manos Athanassoulis, Michael S. Kester, Lukas M. Maas, Radu Stoica, Stratos Idreos, Anastasia Ailamaki, Mark Callaghan. Designing Access Methods: The RUM Conjecture. EDBT 2016. Justin J. Levandoski, David B. Lomet, Sudipta Sengupta. The Bw-Tree: A B-tree for New Hardware Platforms. IEEE ICDE 2013, pp. 302–313. Viktor Leis, Michael Haubenschild, Alfons Kemper, Thomas Neumann. LeanStore: In-Memory Data Management beyond Main Memory. IEEE ICDE 2018, pp. 185–196.

LogTreeDB is distributed as an open software package on npm (logtreedb-driver)
and Docker Hub (pravi2005/logtreedb)
.

Top comments (0)