Build an LSM-tree storage engine (LevelDB / RocksDB style) (11 scenes)
Scene 02

Sort in RAM, log to disk

A put writes to two places at once — an in-RAM sorted structure (the MEMTABLE — the new term this scene; think 'an in-memory sorted table of recent writes') that absorbs random keys at memory speed, and an append-only log on disk (the WAL — short for write-ahead log; literally a file we append every write to before acknowledging it) whose only job is to rebuild the memtable if the process dies.

Previously

The third panel had a question mark in it. The first piece of the answer is to write to two structures at once: one in RAM that sorts cheap, one on disk that survives a crash.

Scene 02

Sort in RAM, log to disk

  1. Watch
  2. Try it
  3. Predict
  4. Capture
RAMmemtable (sorted)emptyDISKWAL — append-onlyemptySSTable shelf — disk (empty for now; an SSTable is a sorted file of key…shelf is emptyOPERATIONidle — no operation in flightEmpty memtable, empty WAL. Watch one PUT touch both.
What to watch for

Two new structures get introduced: the MEMTABLE (an in-RAM sorted table) and the WAL (write-ahead log — an append-only file on disk). Three PUTs come in: m=1, then a=2, then z=3. Watch where each one lands — memtable rows arrive in SORTED positions; WAL records arrive in PUT-arrival order.

Continue unlocks when the animation finishes.
Implementation

Highlighted lines are the ones running in the diagram right now.

lsm.put
fan out: sorted insert into memtable, sequential append to WAL
def put(key, value):
    record = encode(tstamp, key, value)
    wal.append(record)               # sequential write — cheap
    fsync_if_policy(wal)             # durability knob
    memtable.insert_sorted(key, value)  # in-RAM sort — cheap
    return ok
    # ack means: WAL has the record AND memtable shows it
lsm.recover (on restart)
the WAL's only job: rebuild the memtable
def recover():
    memtable = empty_sorted_structure()
    for record in wal.scan_sequentially():
        memtable.insert_sorted(record.key, record.value)
    return memtable
    # WAL goes in; fresh memtable comes out, same final shape
Sources

Where this sits in Build an LSM-tree storage engine (LevelDB / RocksDB style)

Scene 02 of 11, in the Write side act — Sort in RAM, log on disk, flush to immutable SSTables.. Every put fans out: a sorted in-RAM memtable AND an append-only WAL whose only job is to rebuild the memtable on a crash.

Up next. But RAM is finite. Sooner or later the memtable gets full — and then we have to do something with what we've collected. That's the flush, and it's where 'sorted on disk' arrives.

All 11 scenes in Build an LSM-tree storage engine (LevelDB / RocksDB style) · Every curriculum

Designs that use this

Built with Arqly
Every scene in Build an LSM-tree storage engine (LevelDB / RocksDB style) builds on the one before it.All 11 Build an LSM-tree storage engine (LevelDB / RocksDB style) scenes