docs/components/read_flow/02_multiget.md
Files: db/db_impl/db_impl.cc, db/db_impl/db_impl.h, table/multiget_context.h, db/version_set.cc, db/version_set_sync_and_async.h, table/block_based/block_based_table_reader.cc, table/block_based/block_based_table_reader_sync_and_async.h, db/table_cache_sync_and_async.h
DB::MultiGet() retrieves multiple keys in a single call, enabling optimizations impossible with individual Get() calls. Keys are pre-sorted, grouped by column family, and processed in batches to maximize block reuse, coalesce I/O operations, and leverage async prefetching. Internally, DBImpl::MultiGet() handles the public API, while DBImpl::MultiGetWithCallback() provides a variant for transactions that need custom visibility via ReadCallback.
MultiGetContext (see MultiGetContext in table/multiget_context.h) manages batched key state using 64-bit bitmasks for O(1) tracking:
| Constant/Field | Purpose |
|---|---|
MAX_BATCH_SIZE (32) | Maximum keys per batch, fits in a 64-bit Mask type |
value_mask_ | Shared bitmask marking keys whose final value is found |
skip_mask_ | Per-range: keys to skip (e.g., filtered by bloom) |
invalid_mask_ | Per-range: keys that don't belong to this range |
Each key's state is tracked in a KeyContext struct (see KeyContext in table/multiget_context.h) containing the key, column family, output value/status, merge context, and per-key metadata.
Range (see MultiGetContext::Range in table/multiget_context.h) is a view over a slice of sorted keys combined with the three bitmasks above. Its Iterator skips any key whose bit is set in value_mask_ | skip_mask_ | invalid_mask_, so each lookup layer automatically sees only unresolved keys — no copying or allocation needed.
The same Range flows through all lookup layers in MultiGetImpl(): first mem->MultiGet(), then imm->MultiGet(), then Version::MultiGet(). When a layer resolves a key, it calls MarkKeyDone() which sets that key's bit in the shared value_mask_. Subsequent layers skip it automatically. Within SST lookup, FilePickerMultiGet further narrows the Range per-file using invalid_mask_ (keys outside the file's key range) and bloom filter checks set skip_mask_ (keys definitely absent). If all keys are resolved before reaching lower levels, remaining levels are skipped entirely.
DBImpl::MultiGet() processes keys in batches of MultiGetContext::MAX_BATCH_SIZE. For each batch:
Step 1: Sort keys -- PrepareMultiGetKeys() sorts keys by (column_family_id, user_key) via CompareKeyContext. Sorted order is critical: it enables sequential index seeks and adjacent-block detection.
Step 2: Group by column family -- Keys are partitioned so each batch targets a single column family, sharing a single SuperVersion acquisition.
Step 3: MemTable lookup -- MultiGetImpl() calls mem->MultiGet() then imm->MultiGet(). Keys resolved in memtables are marked done via MarkKeyDone, and remaining keys proceed to SST lookup.
Step 4: SST file lookup -- Version::MultiGet() searches SST files level by level using FilePickerMultiGet to map sorted keys to overlapping files.
| Optimization | Mechanism | Benefit |
|---|---|---|
| Batch size limit | MAX_BATCH_SIZE = 32 with 64-bit bitmask | Fits in registers, zero-allocation tracking |
| Pre-sorted keys | PrepareMultiGetKeys() sorts by CF + user key | Sequential index seeks, adjacent block detection |
| Shared SuperVersion | Acquired once per batch | Single snapshot, reduced atomic operations |
| Batched bloom filters | FullFilterKeysMayMatch() checks all keys in one pass | Single filter block load serves multiple keys |
| Block reuse | reused_mask + NullBlockHandle detection | Skip redundant cache lookup and I/O for co-located keys |
| Adjacent block coalescing | RetrieveMultipleBlocks() merges nearby reads | Fewer I/O syscalls |
| Async cache probes | StartAsyncLookupFull() + WaitAll() | Parallel cache lookups |
| Shared cleanable | SharedCleanablePtr for reused blocks | Reduces cache refcount contention |
| Coroutine parallelism | folly::coro::collectAllRange for per-level files | Parallel SST lookups within a level |
| Stack scratch buffer | kMultiGetReadStackBufSize (8192 bytes) | Avoids heap allocation for small reads |
FullFilterKeysMayMatch() in block_based_table_reader.cc checks all remaining keys against the bloom filter in a single pass by calling filter->KeysMayMatch(range, ...). Keys that are definitely absent are removed from the range via SkipKey. This avoids per-key bloom filter overhead.
The standalone MultiGetFilter() is used in the coroutine path to perform filter checking before launching async data block reads.
Inside BlockBasedTable::MultiGet(), when the index is seeked for each key, block handle offsets are compared. If the current key's block handle offset equals the previous key's, the key maps to the same data block. A NullBlockHandle is stored and a bit in reused_mask is set, avoiding redundant cache lookups and I/O.
During data iteration, keys that reused a previous block share the existing block iterator. The SharedCleanablePtr mechanism handles reference counting -- when multiple keys pin the same block cache entry, a shared cleanable avoids redundant Ref/Unref operations on the cache.
RetrieveMultipleBlocks() in block_based_table_reader_sync_and_async.h is called for cache-miss blocks:
Step 1: When compression is enabled and blocks are physically adjacent (prev_end == handle.offset()), they are merged into a single FSReadRequest
Step 2: A scratch buffer strategy is used: if total read size fits in kMultiGetReadStackBufSize (8192 bytes), a stack buffer avoids heap allocation; otherwise a heap buffer is used
Step 3: I/O dispatch -- synchronous path uses file->MultiRead() to issue all requests at once; coroutine path uses co_await batch->context()->reader().MultiReadAsync()
Step 4: After reads complete, each block is verified (checksum), decompressed if needed, and inserted into block cache
This reduces system calls from O(keys) to O(distinct_read_regions), which is often much smaller.
When ReadOptions::async_io and ReadOptions::optimize_multiget_for_io are both true, and the filesystem supports kAsyncIO:
Within a level: Multiple SST files are processed concurrently via folly::coro::collectAllRange. MultiGetFilter is called first to filter keys, then coroutines are launched for each file. Note: the coroutine path is disabled for L0 (where files overlap and must be processed in order), and requires both coroutine and async-I/O support to be available at compile time. Also, TableCache::MultiGetFilter() returns Status::NotSupported() when row cache is enabled, so the filter-then-launch sequence is skipped in that case.
Async cache probes: For each unique block handle, block_cache.StartAsyncLookupFull() initiates an async cache lookup. All lookups are started, then WaitAll() collects results. Cache hits populate results directly; misses accumulate into the I/O phase.
Async disk I/O: AsyncFileReader (see AsyncFileReader in util/async_file_reader.h) implements the C++20 Awaitable concept. MultiReadAsyncImpl calls RandomAccessFileReader::ReadAsync, which on Linux uses io_uring via PosixFileSystem::Poll(). The ReadAwaiter stores pending I/O handles and the suspended coroutine handle.
Version::MultiGet() uses FilePickerMultiGet to determine which sorted keys overlap with which SST files, level by level:
current_file_range_ produced by FilePickerMultiGet is a MultiGetRange subset of keys overlapping the current SST fileMultiGet achieves sub-linear scaling: N keys via MultiGet is significantly faster than N individual Get calls:
DB::MultiGetEntity() retrieves multiple keys as PinnableWideColumns. Three overloads exist: single-CF, multi-CF, and attribute-group. All are fully implemented in DBImpl and route through the same batched infrastructure as MultiGet(), with GetImplOptions.columns set instead of GetImplOptions.value.
When MultiGet() spans multiple column families, MultiCFSnapshot coordinates SuperVersion acquisition. For kPersistedTier, it acquires the DB mutex to freeze SuperVersion changes across all column families, ensuring a consistent persisted view even while memtables are being sealed or flushed. This is a real cross-component behavior difference from single-CF MultiGet.