Reading LevelDB: Flushing MemTables and the SSTable Format

The MemTable piece ended at the LSM write path: a Put/Delete becomes an arena-packed, versioned, skip-list-ordered record. This article is what happens after that record piles up — the moment the active memtable fills and LevelDB must get it onto disk as an SSTable (Sorted String Table), and what that file actually looks like once it is there.

This is the bridge between the in-memory trio you have already read and the on-disk structures that follow:

→ Reading LevelDB: The Arena Region Allocator → Reading LevelDB: The SkipList Index → Reading LevelDB: The MemTable

The main LSM line continues: MemTable → WAL (log) → SSTable (table/block) → Compaction (version_set). This article covers the MemTable → SSTable step and the SSTable shape itself.

1. Why the memtable is “immutable” — double-buffering hand-off

A memtable is not born immutable. The one the writer fills is mutable (mem_); the one being flushed is frozen into imm_ (immutable). The freeze happens in MakeRoomForWrite (db/db_impl.cc:1396-1399):

imm_ = mem_;                                       // freeze the active table
has_imm_.store(true, std::memory_order_release);
mem_ = new MemTable(internal_comparator_);          // open a fresh table for new writes
mem_->Ref();

The motivation is to keep reads and writes from blocking each other:

Flushing is slow. If you flushed directly on mem_, the write path would stall for the whole flush.
Instead you swap: mem_ is atomically handed to imm_ (a read-only snapshot), and a brand-new mem_ is allocated for the foreground to keep writing. The swap is just a pointer assignment — nearly free.
Foreground writes now go into the new mem_ (no lock contention with the flush); the background thread slowly scans the read-only imm_ to produce the SSTable.
Because imm_ is never modified during the flush, the background reader needs no lock against the foreground writer — that is precisely why it is called immutable.
When CompactMemTable finishes, imm_ = nullptr; the cycle ends. The next time mem_ fills, the dance repeats.

Analogy: you “freeze” the current stack of paper and hand it to the printer, while you keep writing on a fresh stack. The two jobs run in parallel.

2. A concurrency nuance: `background_compaction_scheduled_` is not atomic

In db/db_impl.h two neighboring flags look similar but are typed differently:

std::atomic<bool> shutting_down_ GUARDED_BY(mutex_);   // line ~175
bool background_compaction_scheduled_ GUARDED_BY(mutex_); // line ~196

background_compaction_scheduled_ is a plain bool under GUARDED_BY(mutex_). Its every read and write already happens while holding mutex_:

MaybeScheduleCompaction() is annotated EXCLUSIVE_LOCKS_REQUIRED(mutex_) and begins with mutex_.AssertHeld(); it both reads and writes the flag inside.
BackgroundCall() holds the lock for its whole body and sets background_compaction_scheduled_ = false;.
~DBImpl / TEST_CompactMemTable spin while (background_compaction_scheduled_) Wait(); only after taking the lock.

Since the mutex already serializes access (and unlock/lock carry release/acquire semantics), making it atomic would be no safer and only add cost and noise.

By contrast shutting_down_ is atomic because it is deliberately decoupled from the mutex — it is polled inside long background loops (e.g. while (input->Valid() && !shutting_down_.load(...)) in DoCompactionWork) where taking the lock every iteration would be too heavy. The general rule: use a plain GUARDED_BY variable when the mutex already covers it; upgrade to atomic only for shared state that must be read/written outside the lock.

3. The background compaction entry: `BackgroundCompaction()` (db_impl.cc:708-787)

Called by BackgroundCall() while holding the lock. It does two classes of work:

if (imm_ != nullptr) {
  CompactMemTable();   // highest priority: flush the frozen memtable
  return;
}

If imm_ exists, flush it first (otherwise the foreground write would block waiting for the immutable table to clear), then return immediately. Otherwise it picks what to compact:

Manual: versions_->CompactRange(...) triggered by a user CompactRange() / test hook.
Automatic: versions_->PickCompaction() chooses the level with the worst write-amplification score.

Both return a Compaction* c. Three outcomes:

c == nullptr: nothing to do.
Trivial Move (IsTrivialMove() true): a single file with no key overlap in the next level — just LogAndApply a RemoveFile+AddFile into the MANIFEST and “nudge” it down a level, almost zero I/O.
Real merge: DoCompactionWork merges multiple inputs, drops overwritten/tombstoned keys, writes fresh SSTables, then CleanupCompaction / ReleaseInputs / RemoveObsoleteFiles.

Note that LogAndApply / DoCompactionWork temporarily release mutex_ so the foreground is not stalled, then re-acquire it before returning to the caller’s MutexLock.

env_->Schedule(BGWork)
  → BGWork → BackgroundCall()          // holds lock; background_compaction_scheduled_ = true
      → BackgroundCompaction()          // this section
          ├─ imm_ present → CompactMemTable()  (flush)
          └─ else PickCompaction / CompactRange
                ├─ TrivialMove → LogAndApply (move file)
                └─ else DoCompactionWork (merge & rewrite)
      → MaybeScheduleCompaction()       // schedule again if more to do
      → background_compaction_scheduled_ = false

4. `CompactMemTable()`: frozen memtable → SSTable (db_impl.cc:549-580)

Called by the background thread under the lock. It turns imm_ into an L0 (or deeper) SSTable:

assert(imm_ != nullptr); grab the current version base = versions_->current() and Ref() it.
WriteLevel0Table(imm_, &edit, base) — the core; writes imm_ to an SSTable and fills edit (which new file was added).
If shutting_down_ trips mid-flush, mark an error (the database is going away).
On success, commit metadata: edit.SetLogNumber(logfile_number_) (the old WAL can now be discarded), then versions_->LogAndApply(&edit, &mutex_) writes the MANIFEST and switches to the new Version (releasing the lock internally).
On commit success: imm_->Unref() → imm_ = nullptr → has_imm_.store(false) (the atomic the foreground polls) → RemoveObsoleteFiles(). On failure, RecordBackgroundError.

5. `WriteLevel0Table` + `BuildTable`: memtable → SSTable (db_impl.cc:505-547, builder.cc:17-72)

5.1 `WriteLevel0Table` flow

① Allocate a file number: meta.number = versions_->NewFileNumber() (the SSTable filename is this number).
② Reserve in pending_outputs_: register the “in-flight” file number so a concurrent RemoveObsoleteFiles cannot delete an unfinished file; insert on entry, remove on exit.
③ Ordered iterator: mem->NewIterator() returns a skip-list iterator. Because the skip list is ordered by InternalKeyComparator, the emitted (key, value) pairs are strictly increasing.
④⑤ Release lock and flush (the important part): mutex_.Unlock() → BuildTable(...) (actually writes disk) → mutex_.Lock(). This is why imm_ had to be frozen — the flush runs concurrently with foreground writes.
Choose level: default level 0; if meta.file_size > 0 and base != nullptr, PickLevelForMemTableOutput may sink it to L1/L2; finally edit->AddFile(level, ...) is handed to LogAndApply.

5.2 `BuildTable`: how the dump happens (builder.cc:17-72)

iter->SeekToFirst() from the smallest key.
Create the physical file TableFileName(dbname, meta->number), new TableBuilder.
meta->smallest.DecodeFrom(iter->key()) (first key); loop builder->Add(key, value) in order; meta->largest.DecodeFrom(key) (last key).
builder->Finish() writes the index/footer; file->Sync() + file->Close() persist it; the table_cache opens it to verify.
meta->smallest / meta->largest are the file’s first and last internal keys — they drive level selection later and the read path’s “which files to check”.

In one sentence: sequentially scan the (already ordered) memtable → TableBuilder writes blocks → record first/last key and size. No re-sort needed.

5.3 `PickLevelForMemTableOutput`: where the new file lands (version_set.cc:470-495)

A flushed memtable does not always go to L0. When there is no conflict it sinks to reduce L0 congestion and future compaction volume:

If the new file overlaps L0 (L0 files may overlap each other) → must stay in L0, return 0.
Otherwise probe downward (level < config::kMaxMemCompactLevel, default 2):
- level+1 overlaps → stop at current level;
- level+2 (the “grandparent”) overlap bytes exceed MaxGrandParentOverlapBytes → stop (prevents future read-amplification blow-up);
- else level++.
Returns the final level (typically 0/1/2).

WriteLevel0Table(imm_, edit, base)
 ├ allocate file number, reserve in pending_outputs_
 ├ take the memtable's ordered iterator
 ├ Unlock → BuildTable: scan → TableBuilder writes SSTable (record smallest/largest, Sync) → Lock
 ├ PickLevelForMemTableOutput: if no L0 overlap, sink toward L1/L2
 └ edit->AddFile(level, ...) → handed to LogAndApply to commit the MANIFEST

6. SSTable on-disk format (TableBuilder / BlockBuilder)

┌─────────────────────────────────────────────┐
│  data block 0  (block_data + type + crc)     │  ← the real K/V data
│  data block 1  (block_data + type + crc)     │
│  ...                                          │
│  filter block   (bloom filter data, optional) │
│  metaindex block (points at the filter block) │
│  index block    (shortest separator + offset) │  ← locates data blocks
│  footer         (metaindex_handle, index_handle, magic) │ ← fixed size, read first
└─────────────────────────────────────────────┘

On read you first read the fixed-size footer to get two handles, then walk the index down to the specific data block.

6.2 Data block internals: prefix compression (block_builder.cc)

A single entry:

shared_bytes   : varint32   // length of prefix shared with the previous key
unshared_bytes : varint32   // length of this key's unique suffix
value_length   : varint32
key_delta      : char[unshared_bytes]   // store only the non-shared suffix
value          : char[value_length]

BlockBuilder::Add compares the new key with the previous one, finds the common prefix shared, and stores only the suffix key[shared..]; the value is stored whole. shared is always relative to the immediately preceding key, so decoding must scan sequentially to reassemble.

Worked example (large restart interval, 5 ordered keys):

#	(shared, non_shared)	bytes stored	reconstructed
①	(0, 9)	`"the apple"`	first key, stored whole
②	(8, 5)	`"ication"`	`"the apple"` + `"ication"` = `"the application"`
③	(8, 1)	`"y"`	`"the application"` + `"y"` = `"the apply"`
④	(4, 6)	`"banana"`	`"the apply"` + `"banana"` = `"the banana"`
⑤	(7, 2)	`"nd"`	`"the banana"` + `"nd"` = `"the band"`

50 bytes of keys → 23 bytes after compression (keys only; values untouched).

Restart point: every block_restart_interval (default 16) keys the compression is force-reset (shared = 0, the whole key stored) and the offset is recorded in restarts_[]. The effect:

A block is cut into segments, each at most 16 keys.
A lookup first binary-searches restarts_[] to find the segment, then scans sequentially from the segment start (at most 16 steps).
Finish() appends restarts_[] and its count to the block tail.

6.3 Block cutting and the index: delayed write + shortest separator (table_builder.cc)

Add appends each K/V to data_block; when it reaches block_size (default ~4KB) it Flushes. After flushing, a delayed index trick fires (pending_index_entry, comments ~50-59):

if (r->pending_index_entry) {
  r->options.comparator->FindShortestSeparator(&r->last_key, key); // compute separator
  r->pending_handle.EncodeTo(&handle_encoding);
  r->index_block.Add(r->last_key, Slice(handle_encoding));          // (separator, block handle)
  r->pending_index_entry = false;
}

The N-th block’s index entry is not written when block N is flushed. It waits until the first key of block N+1 arrives, then uses FindShortestSeparator to compute the shortest key that is ≥ every key in block N and < every key in block N+1.
This makes the index key shorter than the real key → a smaller index, yet binary search stays correct.
pending_handle is the just-flushed block’s BlockHandle (offset + size).

6.4 Per-block compression and trailer (WriteBlock / WriteRawBlock)

Before writing, optional Snappy/Zstd compression is applied — but only if it saves more than 12.5% (otherwise stored raw). Each block’s physical format:

[block_data][type:1B][crc:4B]

trailer[0] = type; the CRC covers data + type (crc32c::Mask) and is checked on read to catch corruption. BlockHandle records offset (position in file) + size (block_data only, excluding the trailer), varint-encoded — the universal handle for locating any block internally.

6.5 `Finish()`: filter / metaindex / index / footer (213-268)

Flush() writes the final block.
filter block: each Add feeds the key into a bloom filter; on read, a “definitely absent” answer skips the data block entirely.
metaindex block: a small index recording "filter.<policy>" -> filter block location.
index block: the last pending index entry is closed out with FindShortSuccessor, then written.
footer: fixed length (with a magic number), the entry point for reading an SSTable; stores metaindex_handle and index_handle.

Read path (next): Reading LevelDB: The Read Path walks how Get actually descends these structures from the top down — snapshot visibility, the Ref()-before-unlock dance, Version::Get across L0/L1+, and the TableCache bridge.

6.6 How `FindShortestSeparator` works

Default implementation: find the first differing byte between start and limit, increment that byte of start by one, and truncate at that position, yielding sep such that start < sep < limit.

Comment example: block N’s last key start = "the quick brown fox", block N+1’s first key limit = "the who":

Byte 4 differs: 'q'(0x71) vs 'w'(0x77); 'q' + 1 = 'r', truncate after position 5 → "the r".
Verify: "the r" > "the quick brown fox" (byte 4 'r' > 'q') ✓; "the r" < "the who" (byte 4 'r' < 'w') ✓.
Block N’s index entry becomes ("the r", handle_N) — a key far shorter than any real key.

Why binary search still lands correctly: the separator sep_N satisfies last_N < sep_N < first_{N+1}. Binary-searching for the first index key ≥ target:

target is inside block N ⇔ first_N ≤ target ≤ last_N; since sep_N ≥ last_N ≥ target and sep_{N-1} < first_N ≤ target, the first ≥ target entry is exactly sep_N → go to block N ✓.
Example: look up "the queen" (which is < "the quick brown fox", inside block N) → "the r" > "the queen" → block N ✓.
Example: look up "the rabbit" (falls in a gap, in neither block) → "the r" is its prefix so < "the rabbit", it is skipped; go to block N+1, whose minimum "the who" > "the rabbit" → not found ✓.

Payoff: the index block is read constantly and ideally stays in memory; the shorter it is the better. When many keys share a long prefix (same user_key, different versions; same business prefix), the index shrinks dramatically.

7. Connecting to the in-memory trio

The ordered iterator that BuildTable scans is the skip list from the MemTable — that is why no re-sort is needed; the data is already in InternalKeyComparator order.
The frozen imm_ is exactly the double-buffered, immutable snapshot from §1 — made possible by the Arena/SkipList “never free a node individually” design.
The version/seq numbers packed into each internal key (see the MemTable piece) are what let compaction later drop overwritten values and tombstones.

8. Quick reference

Topic	Key point
immutable memtable	double-buffer swap: `imm_ = mem_; new mem_`; frozen = read-only, flush runs lock-free vs foreground
`background_compaction_scheduled_`	always under lock → plain `bool` + `GUARDED_BY`; `shutting_down_` polled outside lock → `atomic`
`BackgroundCompaction`	under lock; flush `imm_` first, else PickCompaction / TrivialMove / real merge
`CompactMemTable`	`imm_` → SSTable via `WriteLevel0Table` → `LogAndApply` commits MANIFEST → clear `imm_`
`WriteLevel0Table`	release lock to flush (the concurrency trick); `pending_outputs_` prevents accidental delete; smart level L0/L1/L2
`BuildTable`	sequential scan of ordered memtable → `TableBuilder` writes SSTable, records smallest/largest
prefix compression	each key stores only the suffix differing from the previous; restart every 16 keys
delayed index	block N’s index entry waits for block N+1’s first key, uses shortest separator → shorter, still correct
block trailer	`[data][type:1B][crc:4B]`; CRC covers data + type
SSTable layout	data blocks + filter + metaindex + index + footer (fixed, read first)

Reading LevelDB: Flushing MemTables and the SSTable Format

1. Why the memtable is “immutable” — double-buffering hand-off

2. A concurrency nuance: background_compaction_scheduled_ is not atomic

3. The background compaction entry: BackgroundCompaction() (db_impl.cc:708-787)

4. CompactMemTable(): frozen memtable → SSTable (db_impl.cc:549-580)

5. WriteLevel0Table + BuildTable: memtable → SSTable (db_impl.cc:505-547, builder.cc:17-72)

5.1 WriteLevel0Table flow

5.2 BuildTable: how the dump happens (builder.cc:17-72)

5.3 PickLevelForMemTableOutput: where the new file lands (version_set.cc:470-495)