yuqi-zheng
· also available in 中文

Reading LevelDB: The Read Path — Get from Entry to Disk

c++low-latency

The Flush & SSTable piece ended with the file sitting on disk and a promise: “read path next”. This article is that path — what happens when you call db->Get, the moment the request leaves the foreground thread and walks from the in-memory memtables down through the SSTable files, and how it can even trigger a compaction on the way back out.

This is the downstream half of the LSM line you have been reading:

→ Reading LevelDB: The Arena Region Allocator → Reading LevelDB: The SkipList Index → Reading LevelDB: The MemTable → Reading LevelDB: Flushing MemTables and the SSTable Format

The read path is the mirror of the write path. The write side turns a Put into a versioned, skip-list-ordered record, then flushes it to disk. The read side has to find the visible version of a key — which may be in the active memtable, the frozen one, or any of dozens of SSTable files across levels — and do so without blocking the background compactor.

1. Overview: what one Get actually does

The read entry is DBImpl::Get. A single read has four phases:

  1. Fix the visibility boundary: compute the snapshot — the “point in time” this read can see.
  2. Pin the objects: before releasing the lock, Ref() mem_ / imm_ / current once each, so a background compaction cannot delete them mid-read.
  3. Unlock and read slowly: under no lock, probe memtable → immutable memtable → SSTable (Version::Get); the background compactor may run concurrently during this window.
  4. Feed back from the read: if an SSTable was actually consulted, record seek_file statistics that can trigger a read-amplification-driven compaction.

Files involved: db/db_impl.cc, db/version_set.cc, db/version_set.h, db/table_cache.cc, db/table_cache.h, table/table.cc.

2. Step 1 — pin the visibility boundary: the snapshot (MVCC)

db/db_impl.cc:1125-1131

SequenceNumber snapshot;
if (options.snapshot != nullptr) {
  snapshot =
      static_cast<const SnapshotImpl*>(options.snapshot)->sequence_number();
} else {
  snapshot = versions_->LastSequence();
}

Two facts drive the whole read path:

  • LevelDB is multi-version (MVCC): every written record carries a globally increasing SequenceNumber.
  • A read does not fetch “the latest record”; it fetches the latest record with seq <= snapshot.

Two cases:

  • The caller passes options.snapshot → use that snapshot’s sequence number (the read “time-travels” and cannot see later writes).
  • No snapshot passed → use versions_->LastSequence(), i.e. “read the latest committed data”.

This snapshot is immediately used to build the lookup key LookupKey(key, snapshot) (§4), and every subsequent comparison only matches versions ≤ snapshot. The effect: ① read-committed consistent data; ② snapshot isolation; ③ deleted/overwritten old versions are naturally invisible.

Cross-reference: GetSnapshot() (db_impl.cc:1187) returns snapshots_.New(LastSequence()) — that is exactly where the options.snapshot you pass in comes from.

3. Step 2 — pin the objects: Ref() before unlocking

db/db_impl.cc:1133-1138

MemTable* mem = mem_;
MemTable* imm = imm_;
Version* current = versions_->current();
mem->Ref();
if (imm != nullptr) imm->Ref();
current->Ref();

Get calls mutex_.Unlock() at db/db_impl.cc:1145 to read — which may be slow because it reads SSTable files. During that unlocked window the background compaction thread may:

  • freeze mem_ into a new imm_ (MakeRoomForWrite);
  • flush imm_ then delete it (CompactMemTable sets imm_ = nullptr);
  • switch current to a new Version (LogAndApply).

If Get only held a bare pointer and the background deleted it during the window, the read would touch freed memory and crash. Ref() bumps an internal atomic reference count so these objects cannot be destroyed until the read is done; after re-acquiring the lock (db/db_impl.cc:1162-1164) each is Unref()d once, and only when the count hits zero is the object freed.

This is the canonical LevelDB pattern: concurrent reads = do the slow work unlocked + use reference counting to protect the lifetime of the objects you touch. Ref/Unref are themselves atomic, so the background’s Unref and this one cooperate safely.

4. Step 3 — unlock and read, plus the seek-statistics hook

db/db_impl.cc:1143-1161

// Unlock while reading from files and memtables
{
  mutex_.Unlock();
  // First look in the memtable, then in the immutable memtable (if any).
  LookupKey lkey(key, snapshot);
  if (mem->Get(lkey, value, &s)) {
    // Done
  } else if (imm != nullptr && imm->Get(lkey, value, &s)) {
    // Done
  } else {
    s = current->Get(options, lkey, value, &stats);
    have_stat_update = true;
  }
  mutex_.Lock();
}

if (have_stat_update && current->UpdateStats(stats)) {
  MaybeScheduleCompaction();
}
  • LookupKey(key, snapshot) encodes the user key into an internal lookup key with an 8-byte sequence number.
  • Probe order: memtable → immutable memtable → SSTable (current->Get).
  • have_stat_update = true flags that this read actually reached the SSTable. Only the current->Get branch sets it; when the memtable was hit, stats is uninitialized and must not be fed to UpdateStats.

have_stat_update is the trigger for seek compaction (read-amplification-driven compaction):

  • When an SSTable is repeatedly “read but has to skip over many overwritten/deleted old versions” (its seek count crosses a threshold), UpdateStats returns true and schedules a background compaction to cut the read amplification.
  • This is a second compaction trigger running in parallel with the write-amplification trigger — read-only traffic can drive compaction too.

5. Step 4 — Version::Get: the SSTable lookup core

db/version_set.cc:324-400

Status Version::Get(const ReadOptions& options, const LookupKey& k,
                    std::string* value, GetStats* stats) {
  stats->seek_file = nullptr;
  stats->seek_file_level = -1;
  // ...
  ForEachOverlapping(state.saver.user_key, state.ikey, &state, &State::Match);
  return state.found ? state.s : Status::NotFound(Slice());
}

This is the current->Get implementation. When neither memtable nor immutable memtable matched, the read arrives here to find the latest visible version (seq <= snapshot) among all SSTable files in the current version.

5.1 State + Match: the callback-style traversal

ForEachOverlapping enumerates every file that could contain the user key and invokes State::Match for each (version_set.cc:341-379). Match does three things:

Record the candidate file to be compacted (the seek-compaction core)

if (state->stats->seek_file == nullptr &&
    state->last_file_read != nullptr) {
  // We have had more than one seek for this read.  Charge the 1st file.
  state->stats->seek_file = state->last_file_read;
  state->stats->seek_file_level = state->last_file_read_level;
}
state->last_file_read = f;
state->last_file_read_level = level;
  • A single Get that must consult a second or later file for the same key means the first file hid a “hole” (the key there was a covered/deleted old version, so the search continues). This repeated seeking is a read-amplification signal.
  • The first file is charged as the seek_file candidate — exactly the data consumed back in §4 by have_stat_update + UpdateStats.

Actually read this SSTable file

state->s = state->vset->table_cache_->Get(*state->options, f->number,
                                          f->file_size, state->ikey,
                                          &state->saver, SaveValue);

Go through TableCache to open/fetch the file; on a hit, call back SaveValue to write the value.

Decide whether to keep scanning

switch (state->saver.state) {
  case kNotFound:  return true;   // key not in this file, keep looking
  case kFound:     state->found = true; return false;  // found value, stop
  case kDeleted:   return false;  // found a deletion marker, stop (older invisible)
  case kCorrupt:   ... return false;  // error, stop
}
  • SaveValue (version_set.cc:262-275) parses the internal key, confirms the user key matches, and classifies: kTypeValue → kFound and copies the value; kTypeDeletion → kDeleted.
  • Note kDeleted also returns false immediately: a deletion marker means the key was deleted before the snapshot, so older versions are invisible too — no need to keep scanning.

5.2 Why a key may span multiple files

The root cause is again MVCC: different versions of one user key can be scattered across different files/levels, so the reader must, “newest first”, find the first version with seq <= snapshot.

6. ForEachOverlapping: L0 scans many, L1+ binary-searches one

db/version_set.cc:281-322

// L0: multiple files may all contain the same key, must scan new→old
for (uint32_t i = 0; i < files_[0].size(); i++) {
  FileMetaData* f = files_[0][i];
  if (ucmp->Compare(user_key, f->smallest.user_key()) >= 0 &&
      ucmp->Compare(user_key, f->largest.user_key()) <= 0) {
    tmp.push_back(f);
  }
}
if (!tmp.empty()) {
  std::sort(tmp.begin(), tmp.end(), NewestFirst);  // by file number, new→old
  // ...
}
// L1+: files in a level are disjoint, binary search the one
for (int level = 1; level < config::kNumLevels; level++) {
  // ...
  uint32_t index = FindFile(vset_->icmp_, files_[level], internal_key);
  // ...
}
  • L0: file key-ranges may overlap, so one key may live in several L0 files → collect all overlapping files, sort by NewestFirst (file number a->number > b->number), scan newest first.
  • L1–L6: within a level the file key-ranges are disjoint, so a key lands in at most one file → FindFile binary-searches that one.

6.1 Why L0 does not use rbegin() to traverse “newest first”

Key fact: files_[0] is not ordered by file number — it is ordered by smallest key.

  • FileSet type: typedef std::set<FileMetaData*, BySmallestKey> FileSet; (version_set.cc:586).
  • Fill order: Builder::SaveTo iterates added_files (a set sorted by BySmallestKey) and push_backs into v->files_[level] (version_set.cc:683).

So files_[0]’s in-memory order is smallest-user-key ascending, not file-number ascending. rbegin() merely reverses “smallest-key ascending” into “smallest-key descending” — which is a different thing from “file number new→old” (the array positions and file numbers of the overlapping L0 files have no correspondence). Hence the explicit sort(tmp, NewestFirst) by number is required to get true “new→old”. L0 has few files (usually ≤ a dozen), so the sort cost is negligible; correctness wins.

7. What it does to FileMetaData: range filter + pointer collection

db/version_set.cc:286-294

std::vector<FileMetaData*> tmp;
tmp.reserve(files_[0].size());
for (uint32_t i = 0; i < files_[0].size(); i++) {
  FileMetaData* f = files_[0][i];
  if (ucmp->Compare(user_key, f->smallest.user_key()) >= 0 &&
      ucmp->Compare(user_key, f->largest.user_key()) <= 0) {
    tmp.push_back(f);
  }
}

What it does to FileMetaData is a read-only “range filter + pointer gather”:

  1. Read the boundary keys: take f->smallest / f->largest (the min/max internal keys in the file) and strip to .user_key(), dropping the sequence/type suffix.
  2. Range test: use the user comparator ucmp to test whether user_key falls in the closed interval [smallest.user_key, largest.user_key].
  3. Collect pointers: on a hit, push_back the f (the pointer) — zero-copy; the structure is not modified.
  4. tmp.reserve(files_[0].size()) pre-reserves capacity to avoid reallocations in the loop.

Why compare user_key rather than internal_key: an InternalKey order is “user_key primary, sequence secondary”; a file’s internal-key [smallest, largest] range spans exactly [smallest.user_key(), largest.user_key()] in user-key terms. Any user key falling in that interval guarantees the file contains some version of it. Comparing on user_key is a safe, correct simplification.

8. TableCache: the bridge between VersionSet and Table

db/table_cache.h:22 / db/table_cache.cc

8.1 What it is

TableCache is a cache keyed by file_number → (RandomAccessFile* + Table*). It maps a logical file number to an already-open, memory-resident Table reader object and manages it with LRU (the eviction internals are out of scope here).

8.2 Where it sits in the stack

DBImpl::Get
  └─ Version::Get            // logical layer: walk files_[level], find files that may hold the key
       └─ TableCache::Get    // bridge layer: file_number ──► open Table object (LRU cached)
            └─ Table::InternalGet  // physical layer: parse one SSTable file format, read data block
  • VersionSet only knows “which files exist”: each FileMetaData in files_[level] records number / file_size / smallest / largest metadata — it holds no open file and stores no index/filter data.
  • Table only knows “how to read one SSTable file”: parse footer, index, filter, data block.
  • TableCache sits between: when Version::Get decides to consult a file (f->number + f->file_size), it calls table_cache_->Get(...) (the version_set.cc:354 line from §5.1). It fetches the object by number, then delegates the real work to Table::InternalGet.

8.3 Core implementation: FindTable

db/table_cache.cc:41-76

Status TableCache::FindTable(uint64_t file_number, uint64_t file_size,
                             Cache::Handle** handle) {
  // ...
  *handle = cache_->Lookup(key);          // 1. check the cache
  if (*handle == nullptr) {
    // ... NewRandomAccessFile(fname, &file);   // 2. miss: open the file
    Table::Open(options_, file, file_size, &table);  // 3. build the reader
    *handle = cache_->Insert(key, tf, 1, &DeleteEntry);  // 4. insert
  }
  // ...
}
  • Hit: return the existing Table*, zero file I/O.
  • Miss: build the SSTable path → env_->NewRandomAccessFile opens it → Table::Open reads footer/index/filter and builds the reader → insert into the cache.
  • Errors are not cached, so a file that is repaired can be re-read automatically.

TableCache::Get (table_cache.cc:100-112): take the Table*, delegate to t->InternalGet(...), then cache_->Release(handle).

8.4 The responsibilities it carries

  1. Avoid the huge cost of re-opening files: the same SSTable is read repeatedly by Gets, compaction, and iteration. Caching the Table (with index/filter blocks already loaded) means subsequent hits reuse it directly.
  2. Unified lifetime / fd management: TableAndFile binds file and table together, managed by the cache; on LRU eviction DeleteEntry deletes both (table_cache.cc:19-24).
  3. Decoupled from the Version lifetime: after a compaction switches versions, the old Version’s files_ change, but the file handles stay in TableCache, governed by reference counting, so the switch does not close files immediately. To truly delete a file, call Evict(file_number) (table_cache.cc:114) to scrub that number from the cache and avoid reading a deleted file.

Echo of the earlier reference counting: DBImpl::Get uses Ref() on mem/imm/current to survive being compacted away while unlocked; TableCache uses a different underlying handle reference count (Lookup holds, Release frees). Same goal — guarantee that an object “currently being read” is not freed by a concurrent compaction.

9. The read path is the mirror of the write path

Three threads of the same design reappear here:

  • The snapshot / seq-number visibility is exactly what the MemTable article packed into each internal key ((s<<8)|type). Without that tag, there would be no MVCC and no “latest visible version”.
  • The Ref()-before-unlock dance is the read-side counterpart of the double-buffered immutable memtable from the Flush & SSTable piece. Both exist so that the slow operation (flush, or disk read) runs concurrently with foreground traffic without a crash.
  • Seek compaction is the read-amplification twin of the write-amplification compaction trigger. The write side schedules compaction when levels get too full; the read side schedules it when a key keeps spanning too many files.

And the whole SSTable format from the previous article is why the read is fast: the footer anchors the index, the index’s shortest-separator keys keep binary search correct, the bloom filter skips whole data blocks, and the per-block restart array bounds the prefix-decompression scan.

10. Quick reference

PhaseLocationRole
visibility boundarydb_impl.cc:1125compute snapshot (MVCC)
pin objectsdb_impl.cc:1136Ref so compaction cannot delete them while unlocked
unlock & readdb_impl.cc:1145probe mem / imm / SSTable
seek stat hookdb_impl.cc:1154have_stat_update marks an SSTable was read
trigger read compactiondb_impl.cc:1159UpdateStats → MaybeScheduleCompaction
SSTable lookupversion_set.cc:324Version::Get: walk candidate files for latest visible version
L0 scans manyversion_set.cc:288gather overlapping files, sort(NewestFirst) by number
L1+ binary searchversion_set.cc:310FindFile locates the single file
bridge cachetable_cache.cc:41FindTable: file_number → Table*, avoid re-open