4.2 Log-Structured Storage

Compaction

segments written6

state

beforeafter

6

seeks/miss

12

stale entries

seg 0

bc

seg 1

abd

seg 2

acd

seg 3

bc

seg 4

abd

seg 5

acd

Problem

6 seeks to prove a key is absent, and 12 of 16 stored entries are already shadowed. This is why reads degrade as writes accumulate, and why a Bloom filter is added in front — and why compaction falling behind under sustained write load is the LSM failure mode to alert on.

2.1 Step 1: hash index in memory

Keep an in-memory hash map: key → byte offset of its most recent value in the log.

Write = append to log and update the map. Read = look up offset, seek, read. If that part of the file is already in the filesystem cache, a read requires no disk I/O at all.

Four problems, and each one motivates the next design step:

In practice, hash tables are not used very often for database indexes. It is much more common to keep data sorted by key.

2.2 SSTables — Sorted String Tables

Same key-value pairs, but sorted by key, and each key appears only once in the file.

How the sparse index works: group pairs into blocks of a few kilobytes and store only the first key of each block in the index. Looking for handiwork, which isn't in the sparse index: because of the sorting you know it must lie between handbag and handsome, so seek to handbag's offset and scan forward. A block of a few kilobytes can be scanned very quickly.

The sparse index itself lives in a separate part of the SSTable — implemented as an immutable B-tree, a trie, or similar.

Consequence: you no longer need all keys in memory. That kills problem #3 above.

2.3 Constructing and merging SSTables — the LSM algorithm

The problem SSTables create: you can't just append, or the file stops being sorted. Rewriting the whole SSTable per insert would be far too expensive.

The solution — a hybrid of an append-only log and a sorted file:

The four steps:

1. Write → in-memory ordered map (the memtable): red-black tree, skip list, or trie — structures that let you insert in any order, look up efficiently, and read back in sorted order.
2. When the memtable exceeds a threshold (typically a few MB), write it out to disk in sorted order as an SSTable — the most recent segment, a separate file alongside older ones, each with its own index. While it's being written, the database keeps writing to a new memtable instance; the old memtable's memory is freed on completion.
3. Read: try the memtable, then the most recent on-disk segment, then next-older, etc. If the key is in no segment, it doesn't exist in the database.
4. Background merge & compaction combines segments and discards overwritten/deleted values.

Merging works like mergesort: read the input files side by side, look at the first key in each, copy the lowest key to the output, repeat. If the same key appears in more than one input file, keep only the more recent value. Output is sorted, one value per key, and it uses minimal memory because you iterate one key at a time.

Segment 1 (older)	Segment 2	Segment 3 (newer)	Merged output
a: 1	a: 7	c: 9	a: 7 — newest wins
b: 2	d: 8		b: 2
d: 3			c: 9
			d: 8 — newest wins

Crash safety of the memtable: a separate log on disk to which every write is immediately appended. It's not sorted by key — that doesn't matter, because its only purpose is to restore the memtable after a crash. Every time the memtable is written out, the corresponding part of the log can be discarded.

Deletion = a tombstone. Append a special deletion record. When segments are merged, the tombstone tells the merge process to discard any previous values for that key. Once the tombstone is merged into the OLDEST segment, it can be dropped.

Provenance: this is essentially what RocksDB, Cassandra, ScyllaDB, and HBase do, all inspired by Google's Bigtable paper (which introduced the terms SSTable and memtable). Published in 1996 as the Log-Structured Merge-tree (LSM-tree), building on earlier work on log-structured filesystems.

Key properties that fall out of immutability:

• A segment file is written in one pass and thereafter immutable.
• Merging happens in a background thread, and reads continue to be served from the input segments during the merge. When it completes, switch reads to the merged segment, then delete the inputs.
• Segment files needn't be on local disk — they're well suited to object storage. SlateDB and Delta Lake take this approach.
• Crash recovery is simple: crash during a memtable flush or a merge → just delete the unfinished SSTable and start afresh. The WAL may contain incomplete records (crash mid-record, or disk full) — detected via checksums and discarded.

2.4 Bloom filters

The problem: reading a key last updated long ago, or a key that doesn't exist, is slow — the engine must check several segment files.

The fix: a Bloom filter per segment — a fast, approximate check of whether a key appears in an SSTable.

Build — for every key in the SSTable, hash it to a few bit positions and set them:

hash("handbag") → (2, 9, 4)

bit index:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
bitmap:    [0][0][1][0][1][0][0][0][0][1][0][0][0][0][0][0]
                  ▲     ▲              ▲

Query "handheld" → hashes to (6, 11, 2):

• bit 6 = 0 ✗
• bit 11 = 0 ✗
• bit 2 = 1 ✓

At least one zero means the key is definitely not in this SSTable, so the segment is skipped entirely. All bits set would mean maybe present — false positives are possible, false negatives are not.

• If at least one bit is 0 → the key definitely does NOT appear. Safe to skip the SSTable.
• If all bits are 1 → the key is likely present — but possibly all those bits were set by other keys. That's a false positive.

Cost of a false positive is small: consult the sparse index, decode the block, discover it's not there, continue the search with the next-oldest segment. A bit of unnecessary work; no harm done.

Sizing rule of thumb (worth memorizing):

~10 bits of Bloom filter per key ⇒ ~1% false-positive probability, and the probability drops TENFOLD for every 5 additional bits per key.

So: 10 bits/key → 1%; 15 bits/key → 0.1%; 20 bits/key → 0.01%.

Checks use bitwise operations all CPUs support — extremely fast. The filter is small compared to the rest of the SSTable.

2.5 Compaction strategies

When to compact, and which SSTables to include — usually configurable.

Size-tiered	Leveled
Similar-sized tables are merged upward into bigger ones.	Fixed-size tables in levels, key-range partitioned, each level ~10× the last.
[256M][256M][256M][256M] → [898M] — not 1024M, because deletions, overwrites and TTL expirations are removed on the way.	L0: [ ][ ][ ] newest writes · L1: [a–m][n–z] · L2: [a–d][e–h][i–l]…. When a level exceeds its limit, one or more SSTables merge into level i+1.
Old tables get very large and merging needs a lot of temporary disk. ✔ Very high write throughput — data is rewritten only a few times, in large sequential merges.	Incremental, so it needs less spare disk. ✔ Better read performance, because fewer SSTables have to be checked.

Most LSM implementations provide a variety of strategies for different workloads.

The basic idea — keeping a cascade of SSTables merged in the background — is simple and effective.

2.6 Aside: embedded storage engines

Not all databases are network services. Embedded databases are libraries running in the same process as your application, reading/writing local files, invoked by normal function calls.

Examples: RocksDB, SQLite, LMDB, DuckDB, KùzuDB.

• Very common in mobile apps for local user data
• On the backend: appropriate if the data fits on a single machine and there aren't many concurrent transactions
• Multitenant pattern: if each tenant is small and completely separate (you never run queries combining data from multiple tenants), you can use a separate embedded database instance per tenant

---