Skip to content
Course contents

Build a Log-Structured Store

The two-line database, done properly — append-only log, in-memory index, tombstones, and compaction that never mutates what it has already written.

core45 min hands-onruns in this tab

You have read how a log-structured store works. Now write one.

The log is an array standing in for a file: log[i] is a record and i is its offset. Two rules make this a real log rather than a Map with extra steps, and the tests enforce both:

  • Append only. Push to this.log. Never assign to an index, never splice.
  • get must not scan. One index lookup, one log read. A test proxies the array and counts accesses.

What to implement

set / get / delete — the store’s surface. delete appends a tombstone; it cannot remove anything, because you are not allowed to.

keys() — live keys in sort order, tombstoned keys excluded.

deadRecords() — how many records are superseded values or tombstones. This is the number a real engine watches to decide when compaction is worth running.

compact() — rewrite the log with one record per live key in key order, drop tombstones entirely, rebuild the index, and return how many records were reclaimed.

LogStore.recover(log) — rebuild the index by replaying a log from offset zero, exactly as a real store does on restart. The index is derived data; this is the proof.