How write-heavy databases store data: LSM Trees

1 Why a different storage engine?

Recall from Session 9 (SQL vs NoSQL & Sharding) that we split databases into two camps. Traditional SQL databases prize structure and complex queries; many NoSQL systems are built to scale out and absorb enormous write volumes. That difference isn't just in the query language — it goes all the way down to the storage engine, the part of a database that actually decides how bytes are laid out on disk and how reads and writes touch them.

The read-optimized world: B-trees

Most classic relational databases (PostgreSQL, MySQL/InnoDB, Oracle) store their data and indexes in a structure called a B-tree (more precisely a B+ tree). Picture our alphabetised library: a B-tree keeps keys sorted in place in fixed-size blocks called pages (often 4 KB or 8 KB). To find any key, you start at the top and follow a few pointers down to the right page — only a handful of page reads even in a huge table. That makes reads wonderfully fast and predictable.

The catch is writing. A B-tree does in-place updates: to insert or change a row, it finds the exact page that key belongs in and rewrites that page right where it lives on disk. Each write therefore means: locate the page, read it, modify it, write it back — and if the page is full, split it into two and fix up the parents. Those writes land at scattered, random locations on the disk.

2 The update problem in SQL

Before we can appreciate why NoSQL engines append, we need to see how a classic SQL database handles an update — because that machinery is exactly what NoSQL gives up. Let's follow a simple UPDATE all the way down to the disk.

SQL has a strong, explicit schema

In SQL, data lives in tables and every table has a fixed schema declared up front:

CREATE TABLE users (
    id   integer PRIMARY KEY,
    name varchar(20),
    age  smallint
);

The schema tells the database four things: what tables exist, what columns each has, what type each column is, and what constraints apply. For our table:

id   -> integer
name -> varchar(20)
age  -> smallint

This is called schema-on-write: every time data is inserted or updated, the database checks the new data against the schema. For INSERT INTO users (id, name, age) VALUES (1, 'Abdur', 20); it verifies: is id an integer? is name within 20 characters? is age a valid smallint? is id unique?

So two valid rows can occupy different amounts of physical storage even though they follow the same schema:

1 | Abdur        | 20
2 | Abdur Rehman | 21

And the real physical row size is not just the sum of declared column sizes — databases also store row metadata, null markers, transaction information, alignment padding, page headers, and index references.

How an update really works

Run UPDATE users SET name = 'Abdur Rehman' WHERE id = 1; and the database must: find the row, check the new value against the schema, modify the row or create a new version, update relevant indexes, make the change durable, and stay recoverable if a crash happens. This is far more than "go to disk and overwrite the old value." Modern SQL engines combine a buffer pool, pages, indexes, a write-ahead log, transaction metadata, and background flushing.

Rows live inside pages

Databases don't usually read/write individual rows from disk — data is stored in fixed-size blocks called pages:

Page 1
  |-- row: id=1, name='Abdur',        age=20
  |-- row: id=2, name='Abdur Rehman', age=21
  |-- free space

To update a row, the database loads the whole page into memory, modifies the row in memory, then marks the page as a dirty page.

Write-Ahead Log: the key idea

Before the database safely writes the modified page back to the table/index file, it first records the change in a special append-only log called the Write-Ahead Log (WAL).

In B-tree-based storage engines, data and index pages are updated in place. If a crash happens while only some pages have been written, the structure could become inconsistent. WAL prevents this by giving the database enough information to recover safely after a crash.

Why WAL is needed

A single update may touch multiple physical structures: the table page with the row, the primary-key index page, one or more secondary-index pages, and transaction metadata. If the database overwrote these in place and crashed halfway, it could be left inconsistent — e.g. the table row updated but the index not, or a B-tree page split done without updating its parent. With WAL, the database first records enough information to redo / recover the operation; after a crash it replays WAL records and brings the table and index files back to a consistent state.

What if the new value is too large?

Run UPDATE users SET name = 'Abdur Rehman Ibne Munir Bin Abdul Aziz' WHERE id = 1;. That value violates varchar(20). The database does not overflow into the next row — it usually rejects the update because the value is too large for the declared limit. Remember: varchar(20) is a constraint on allowed values, not a promise of 20 preallocated bytes.

Variable-length updates

What about changing Abdur → Abdur Rehman? It's larger but still fits varchar(20). Since varchar is variable-length, the new value may need more physical storage, and the engine has several tactics:

• use free space on the same page;
• create a new row version elsewhere;
• move large values out-of-line;
• update pointers or indexes;
• leave old row versions for later cleanup;
• split or reorganize pages.

So updates aren't manageable because space was fully preallocated — they're manageable because the storage engine knows how to modify pages safely, maintain indexes, and recover using WAL.

Schema changes (ALTER TABLE)

Adding a column changes the table conceptually from id | name | age to id | name | age | gender:

ALTER TABLE users ADD COLUMN gender smallint;

Physically, the database may not rewrite every row. Adding a nullable column can be fast: existing rows are treated as if the new column is NULL, recorded in metadata. Same idea with a default value:

ALTER TABLE users ADD COLUMN country text DEFAULT 'India';

Older systems might rewrite every row; modern databases may store the default in metadata and return it when old rows are read. But some changes do require rewriting many or all rows, e.g.:

ALTER TABLE users ALTER COLUMN age TYPE bigint;
ALTER TABLE users ADD COLUMN created_at timestamp DEFAULT clock_timestamp();

3 Why NoSQL is forced to append

Most NoSQL databases are schemaless (or semi-structured / loose-schema). The crucial consequence: we don't know the size of any particular entry.

No preallocation — and no way to preallocate

NoSQL databases do not pre-allocate max-space for an entry. More than that, they cannot: the possible maximum is just too large. In Redis, the size limit for a single string is 500 MB — preallocating that for every key would be a massive waste of space.

The overflow problem on update

When you update an entry in NoSQL, its size can change. So what happens if the new value is larger than the space it currently occupies? It would overflow and overwrite the adjacent entry. The two naive "fixes" are both terrible:

• Truncate — enforce that you can't update a value to a larger size. A useless database; bad design.
• Shift — push all subsequent entries to the right to make room. Ridiculously slow.

4 Designing a write-optimized store

So how do we make writes fast? Flip the B-tree's rule on its head with one core principle:

This style is called an append-only design, and the simplest form is a log — literally a file you keep tacking records onto. Because every write lands at the end of one file, the disk writes are sequential: one smooth stream, the pattern disks are fastest at. No seeking, no page splits, no read-modify-write. The write essentially becomes "remember where the end is, write the record there, move the end pointer forward."

# command stream            # what gets appended to the file (end →)
SET user:42 = "Ann"          →  [ user:42 | "Ann"   ]
SET user:42 = "Annie"        →  [ user:42 | "Ann"   ][ user:42 | "Annie" ]
DELETE user:42               →  [ user:42 | "Ann"   ][ user:42 | "Annie" ][ user:42 | <tombstone> ]

Why this is the right trade for write-heavy systems

5 The LSM tree write path

An LSM tree (Log-Structured Merge tree) is the storage engine that turns the append-only idea into something practical. It keeps the cheap sequential writes but adds a layered structure so reads stay manageable and old data gets cleaned. It has a few moving parts — let's meet each one.

The moving parts

• MemTable — an in-memory, sorted structure (typically a balanced tree or skip list) holding the most recent writes. Because it's in RAM and self-sorting, inserting a key in order is fast. This is the "sorting table by the door."
• Write-Ahead Log (WAL) — an append-only file on disk. RAM is volatile: if the server crashes, everything in the MemTable vanishes. So before a write goes into the MemTable, it's first appended to the WAL on disk. That's the durability insurance — after a crash we replay the WAL to rebuild the lost MemTable.
• SSTable (Sorted String Table) — when the MemTable gets big enough, its contents are written out to disk as an immutable, sorted file. "Immutable" means once written it is never modified — only read, or eventually thrown away. These are the "sealed shelves."
• Compaction — a background process that merges several SSTables into fewer, larger ones, discarding overwritten values and applying tombstones. This is the "quiet-hours tidy-up."

What a single write does, step by step

The beautiful part: from the client's point of view a write is just steps 1–3, and both are sequential/in-memory operations — no random disk seeks. Steps 4 and 5 happen later, in the background, off the critical path.

def put(key, value):
    # 1. Durability first: append to the write-ahead log on disk.
    #    This is a sequential append — cheap and fast.
    wal.append(record(key, value))      # survives a crash
    wal.fsync()                         # force it to actually hit disk

    # 2. Update the in-memory sorted structure (skip list / balanced tree).
    memtable.insert(key, value)         # O(log n), all in RAM

    # 3. We can now safely tell the client the write succeeded.
    return OK

    # --- background, NOT on the write's critical path ---

def maybe_flush():
    if memtable.size_bytes >= FLUSH_THRESHOLD:    # e.g. 64 MB
        sstable = write_sorted_to_disk(memtable)   # one sequential write
        sstables.add_newest(sstable)               # immutable from now on
        wal.truncate()                             # those writes are now safe on disk
        memtable = new_empty_memtable()            # start fresh

def delete(key):
    put(key, TOMBSTONE)                 # a delete is just a special append

The WAL file in detail — quick persistence

Any operation (insert / update / delete) must be durable — persisted on disk. The WAL is an append-only file on the hard disk: every new write is simply appended as a new entry at the end. Because it's append-only, the writes are sequential, so write throughput is high. The WAL acts as temporary storage: data there is committed and durable, but it has not yet been fully absorbed into the database's internal bookkeeping.

The WAL file has a max size (typically 100 MB). Once it reaches that size, we must dump it into an SSTable.

The MemTable in detail — the read cache

The MemTable is essentially a hashmap in RAM (often also implemented as a balanced BST / sorted linked list). Writes must mandatorily go to disk (for durability), but reads can be served from RAM for ultra-high throughput. The MemTable acts as an in-memory cache over the data we just wrote.

• Invalidation: it's a write-through cache, but super simple — no 2PC needed, because the entire LSM tree lives within a single server. (If the DB is sharded, each shard builds its own LSM tree.)
• Eviction: Least Recently Used (LRU).
• Size: bounded by the DB server's RAM — more RAM means a larger db-internal cache. Typically the MemTable is kept larger than the WAL's max size, which simplifies eviction and read queries.

Inside an SSTable, and why "sorted" matters

An SSTable stores its key→value entries sorted by key. Sorting buys two things. First, merging two sorted files is easy and sequential (like the merge step of merge sort — walk both with two pointers). Second, you can build a small sparse index — "key m starts at byte offset 50,000" — so a read can jump near the right spot instead of scanning the whole file. (We go deep on these read-side indexes, plus bloom filters, in Session 11.)

Some hard rules about SSTables (long-term persistence). When the WAL fills up, we dump it into a new SSTable. SSTables are immutable: once created they are never updated. They can be deleted (during compaction) and new ones created, but a table is never "edited". Inside a single SSTable, entries are sorted by key and have no duplicates — we deduplicate the WAL data before dumping it.

Levels / tiers — organising the sealed shelves

Flushing produces a stream of SSTables over time. Left alone they'd pile up, so LSM trees organise them into levels (sometimes called tiers): Level 0 holds the freshest, smallest SSTables straight from flushes; deeper levels (L1, L2, …) hold larger SSTables that result from merging. Each level down is typically ~10× bigger than the one above. Newer data lives shallow; older, consolidated data sinks deeper.

Compaction — the background tidy-up

Compaction takes several overlapping SSTables and merges them into new, larger SSTables, throwing away garbage along the way. Because the inputs are each sorted, the merge is a clean sequential pass. During the merge it resolves duplicates and deletes:

• If a key appears in multiple input SSTables, keep only the newest version and drop the older copies (reclaiming the space wasted by updates).
• If the newest version is a tombstone, drop the key entirely (this is when a delete finally frees space).
• Write the survivors out as fresh, immutable SSTables; once readers move over, delete the old inputs.

# OLDER sstable (sorted)        # NEWER sstable (sorted)
  a → 1                           a → 9            # a was updated
  b → 2                           c → <tombstone>  # c was deleted
  c → 3                           d → 4            # brand-new key

# two-pointer merge, newest-wins, tombstones drop the key:
  a → 9        # newer value beats older 1
  b → 2        # only in older, kept
               # c → deleted: newest version is a tombstone, so dropped
  d → 4        # only in newer, kept

# RESULT sstable (still sorted, smaller, garbage removed):
  a → 9
  b → 2
  d → 4

Why compaction, mechanically

Two motivations. (1) Multiple SSTables can hold duplicate (redundant) entries for the same key, wasting space — we want to remove the duplicates. (2) Reads must scan SSTables one by one, so we don't want the count to grow large — compaction reduces the number of SSTables. The mechanism: take 2 consecutive SSTables and merge them into a single SSTable. Since each SSTable is individually sorted by key, we use the merge step of merge sort; for duplicate keys we keep only the latest entry (not both). After compaction the original SSTables are deleted.

Most common compaction strategies

• Levelling — the moment you get 2 SSTables on a level, you trigger compaction: tableCountThreshold = 2.
• Tiering — you allow more than 2 SSTables on a level, keeping a higher tableCountThreshold > 2 before compacting.

The compaction strategy is decided differently for each level. Poorly tuned compaction can make or break database performance, so the choice must be careful.

Typical WAL size                 = 100 MB
size of SSTable on Level 1  <= 100 MB   # compacted from the WAL file
size of SSTable on Level 2  <= 200 MB   # compacted from 2 Level-1 SSTables
size of SSTable on Level 3  <= 400 MB   # compacted from 2 Level-2 SSTables
...

6 Trade-offs & the real systems that use LSM

LSM trees buy fast writes, but every engineering choice has a bill. There are three classic costs to know, usually called the three "amplifications" plus the read penalty.

The trade-offs

def get(key):
    if key in memtable:                 # 1. check RAM first (newest)
        return resolve(memtable[key])    # could be a tombstone → "not found"

    for sstable in newest_to_oldest(sstables):   # 2. then disk files
        if sstable.maybe_contains(key):          # (Session 11: bloom filter!)
            v = sstable.lookup(key)               # binary search via sparse index
            if v is not None:
                return resolve(v)               # first (newest) hit wins

    return NOT_FOUND                # worst case: checked everything

Compared to the B-tree we started with

Real systems built on LSM trees

• LevelDB — Google's compact embedded key-value library; the original popular open-source LSM implementation (and the source of the SSTable terminology we've used).
• RocksDB — Facebook/Meta's fork of LevelDB, heavily tuned; embedded inside countless systems (it's a storage engine, not a server). Uses leveled compaction by default.
• Apache Cassandra — a distributed wide-column NoSQL database (recall sharding from Session 9); its on-disk format is MemTable + commit log (WAL) + SSTables with size-tiered or leveled compaction.
• ScyllaDB — a C++ rewrite of Cassandra focused on raw performance; same LSM design, different implementation.
• Also common: HBase, Bigtable (the original inspiration), and time-series stores — all lean on LSM-style storage for write throughput.

★ Putting it all together

You just learned how write-heavy databases actually store data. Here's the one-paragraph story that connects all four topics:

Quick self-check

📚 References & Further Reading

Class material

• 📄 Original class notes / handout (Google Doc) — open the shared class material for this session.
• Class handout: "[SST-2028] NoSQL Internals - LSM Tree".

Papers, docs & deep dives

• 📄 O'Neil et al. — "The Log-Structured Merge-Tree (LSM-Tree)" (1996) — the original paper that introduced the LSM tree.
• 📄 RocksDB Wiki (Meta) — a production LSM storage engine: MemTables, SSTables, flush and compaction explained.
• 📄 Apache Cassandra — Storage Engine docs — commit log (WAL), MemTables, and SSTables in a real wide-column database.
• 📘 Designing Data-Intensive Applications (Kleppmann), Ch. 3 — B-trees vs LSM-trees and storage-engine trade-offs.

Optional resources (from the handout)

• 🎬 LSM-Tree Compaction Visualization — watch compaction across levels animate.
• 📄 An In-depth Discussion on the LSM Compaction Mechanism — Alibaba Cloud Community.
• 📄 Raphael Carvalho — Building state-of-art LSM-tree compaction in ScyllaDB.