What a real database does that we didn't

Step 12 of 12, and nothing here compiles — nothing here changes code. The store is finished: eleven steps produced a tinylsm with forty-six passing tests and a benchmark table that says plainly where it stands against sled and RocksDB. A closing step owes one more thing, and it is not a feature. It is the honest list of what a real database does that this one doesn’t — the gap between a store that teaches you the shape of an LSM engine and one you could run a service on.

What the store actually guarantees

The guarantees are real, and worth stating precisely before listing the gaps.

Every record in the log carries a checksum. A record that fails it is rejected, not interpreted — step 4 would rather refuse a corrupt byte range than guess at what it meant. A process killed mid-write costs at most the record in flight: on the next open, replay walks the log and cuts the torn tail. Every put calls sync_all before it returns, so when put hands control back, the bytes are on the device — step 11 measured what that costs. Compaction writes a temp file, fsyncs it, and renames it over the old one, so a crash mid-compaction leaves the old table intact. And tombstones survive every merge, because the directory listing is the only record of which files exist — a leftover file from a crashed merge cannot resurrect a deleted key.

One key at a time, a put is atomic. It is one record, written with one write_all, guarded by a checksum. A reader sees the old value or the new one, never a mixture.

That is the inventory. Everything below is what is missing from it.

Transactions

The store has no “both or neither”. Two puts are two operations:

store.put(b"account_a", &balance_a)?;
store.put(b"account_b", &balance_b)?;   // crash here: a is written, b is not

Move money between two accounts and die between the two puts, and the money is gone — or duplicated, depending on the order. Nothing in the API even says these two puts belong together, so the caller cannot be warned, and the store cannot help.

A real database makes a group of writes into one operation with a commit boundary. The writes go to the log first, and a commit record after them marks the point where the group becomes real. Recovery replays the log up to the last commit record and stops: everything before it applies, everything after it vanishes. That is also what makes step 4’s torn-tail truncation safe here and unsafe in general. This store truncates the incomplete tail because it has no way to know better — with no commit record, a torn tail is indistinguishable from a half-written committed write. A database with commit records knows exactly which one it is holding.

There is a second half to transactions: isolation between concurrent ones. That needs the next piece first.

MVCC

tinylsm assumes one owner. put and delete take &mut self, get takes &self — put a store behind a Mutex and you get serialised access, not concurrency. A reader waiting on the lock behind a slow compaction is the polite case; two threads fighting over the mutex is just queueing with extra steps.

Multi-version concurrency control keeps several versions of each key. Every reader gets a snapshot: a fixed view of the store as it was at one instant, while writers keep appending new versions underneath. Readers never block writers, writers never block readers, and no reader sees a half-finished group of writes — which is where transactions and MVCC meet. The implementations differ in where the versions live. PostgreSQL keeps old row versions in the table itself, tags each row with the transaction that created it, and a transaction sees the rows its snapshot permits; vacuum reclaims the versions nobody can see any more. RocksDB gives every write a monotonically increasing sequence number, and a snapshot is just a number — a get against a snapshot skips versions above it.

Compaction is where it all connects. Old versions are garbage, and reclaiming garbage is compaction’s whole job — but a version can only be dropped once no live snapshot can still read it. The step 7 tombstone rule gets sharper: a tombstone may not be discarded while some snapshot can still see the value it hides. The store skips all of this by assuming a single owner, which is honest, and unscalable, which is why it is a toy.

Recovery

What the store does today, on open: replay the log — the not-yet-flushed tail of the writes — rebuild the memtable, load every table’s index, and cut the torn tail. A leftover temp file from a crashed compaction is truncated and reused. That is crash tolerance: the store opens, and loses nothing that was acknowledged.

Recovery in a real database is three things this store does not have. Replay is bounded: old log segments are dropped once their contents are checkpointed into tables, so startup replays minutes of log, not the store’s entire history. (This store is halfway there already — step 8 made the log hold only the un-flushed memtable — but it never reclaims the log file, it just reuses it.) Replay is commit-accurate: it stops at the last commit record, not the last intact byte. And the file set is crash-consistent: a manifest names exactly which files are live, so a leftover table from a crashed merge is identified and deleted at startup instead of being tolerated forever. Step 7 could only make leftovers harmless; a manifest makes them gone.

Beyond one machine there is replication — the log shipped to a standby, which is why the append-only design keeps winning: a log is already the perfect thing to replicate. That is a bigger track than this one, and it starts from everything above.

The three debts the benchmark left

Step 11’s numbers earn their own list, because these are engineering gaps with known fixes, not research problems:

• Group commit. An fsync costs about 1.8 ms on this machine, so a put pays 1.49 ms. Let concurrent writes share one fsync and the per-write cost collapses — that is the gap between tinylsm’s 149 ms and sled’s 8.6 ms for the same hundred writes.
• Cached handles. Every table lookup opens the file, seeks, reads one block, and closes. That open was ninety-three percent of the whole get benchmark. Keeping the handle warm is the single biggest read fix available.
• The footer. load rebuilds each table’s index by scanning the file end to end. Real formats write the index at the foot of the file, so opening a table is one read, not a scan.

None of them changes the guarantees above; all of them change the numbers.

Where to read next

The shortlist, in the order that pays off:

• SQLite’s write-ahead log — one document, one design, and the clearest explanation anywhere of readers not blocking writers.
• PostgreSQL’s MVCC chapter — what multi-version storage looks like when the versions live in the table.
• The RocksDB wiki — this track’s steps 6 through 9, industrialised: SSTables, compaction, manifests, block caches.
• Designing Data-Intensive Applications (Martin Kleppmann) — the storage-engine chapter and the transactions chapter cover almost everything this track skipped, with the trade-offs spelled out.

The track ends here

From the toy-database directory of a checkout at lsm-ch11:

cargo test

Forty-six tests, all offline, all standard library until the benchmark step. The full step list lives on the track overview, and each step’s state is a tag — lsm-ch02 through lsm-ch11 — in the examples repository, so any point in the build can be checked out and run.

The store is done. What it taught is the part of a database nobody sees: writes are appends, deletes are tombstones, and everything else — the indexes, the merges, the filters — is bookkeeping to keep the appends cheap to read back. The machinery this step described is the same ideas again, one level of seriousness up.