A storage engine is a log and an index

The problem: what is a database actually doing?

Snip leans on three stores: Postgres for links, Redis for the cache, and a Cassandra-style cluster for click history (08.04 Replication and quorums). They behave very differently: Postgres updates rows in place, the click store never does, and both have a background process that "compacts" or "vacuums". To choose between storage engines, and to understand their odd behaviour under load, it helps to build the simplest one yourself.

The simplest database: append to a file

Store each write as one line at the end of a file. To read a key, scan the file and take the last value written for it. Writes are as fast as a disk can be, because appending is sequential: no seeking, and nothing existing is touched. A delete is just another append: a special tombstone value meaning "gone".

But reads are terrible: finding one key scans the whole file, and the file grows for ever.

Add an index

Keep a hash map in memory from each key to the byte offset of its latest record in the file. A write appends a line and updates the map; a read looks up the offset and reads exactly that record: one seek, one read. This is the design of Bitcask, the storage engine Riak used:

type Pos = { offset: number; length: number };

export class LogStore {
  private index = new Map<string, Pos>(); // key -> where its latest value is in the file
  private size = 0; // bytes in the file so far

  constructor(private readonly path: string) {
    if (!existsSync(path)) writeFileSync(path, "");
    this.rebuild();
  }

  /** Each record is one line: JSON [key, value], or [key, null] for a delete (a tombstone). */
  set(key: string, value: string | null) {
    const line = Buffer.from(JSON.stringify([key, value]) + "\n");
    const offset = this.size;
    appendFileSync(this.path, line); // the only write: an append at the end
    this.size += line.length;
    if (value === null) this.index.delete(key);
    else this.index.set(key, { offset, length: line.length });
  }

  get(key: string): string | null {
    const pos = this.index.get(key);
    if (!pos) return null;
    const fd = openSync(this.path, "r");
    const buf = Buffer.alloc(pos.length);
    readSync(fd, buf, 0, pos.length, pos.offset); // one seek, one read
    closeSync(fd);
    return JSON.parse(buf.toString())[1];
  }

  /** After a restart, the index is gone: scan the whole log to rebuild it. */
  private rebuild() {
    this.index.clear();
    let offset = 0;
    for (const line of readFileSync(this.path).toString().split("\n")) {
      if (!line) continue;
      const length = Buffer.byteLength(line) + 1;
      const [key, value] = JSON.parse(line);
      if (value === null) this.index.delete(key);
      else this.index.set(key, { offset, length });
      offset += length;
    }
    this.size = offset;
  }

  /** Compaction: rewrite only the latest value of each live key, then swap files. */
  compact() {
    const tmp = this.path + ".compact";
    writeFileSync(tmp, "");
    for (const key of this.index.keys()) appendFileSync(tmp, JSON.stringify([key, this.get(key)]) + "\n");
    renameSync(tmp, this.path);
    this.rebuild();
  }
}

(Imports from node:fs omitted.) Tested: after setting x7Kp twice and deleting b2Qe, reads returned the newer destination and nothing for the deleted key, both before and after a simulated restart that rebuilt the index from the file.

Three problems, three ideas

The file grows with every overwrite. Snip's link x7Kp edited twice leaves three records, two of them dead. Compaction rewrites only the live records into a new file and swaps it in. In the test, 1,000 writes to 10 keys made a 13,929-byte log; compacting it left 179 bytes. Real engines split the log into segments and compact old segments in the background while new writes go to the newest one.

A restart loses the index. Rebuilding it means reading the whole log. Bitcask also writes a small "hint" file alongside each segment so the index can be rebuilt without reading every value.

Every key must fit in memory, and ranges are impossible. A hash map has no order, so "all codes between x7A and x7Z" means checking everything. Fixing both needs the index to be sorted, and that's the fork in the road: keep a sorted tree on disk and update it in place (a B-tree), or keep sorted files that are written once and merged later (an LSM-tree). 09.02 B-trees vs LSM-trees compares them.

Recap

Interview questions