How does a read find a key in a log-structured engine that holds several sorted files, and how do bloom filters and file indexes limit the work?

middleshould knowfreq 50%

answer

newest first, then merge
memory, then files
may contain vs cannot contain
index jumps to the block
point reads, not ranges

basics

~20 s

A read checks the memory buffer and then every sorted file that could hold the key, merging entries so the newest version wins. Per-file bloom filters skip files that certainly lack the key, and per-file indexes jump straight to the right block.

solid answer

~50 s

Because updates are new entries in new files, a key's data may be spread over the memory buffer and several sorted files. A point read therefore consults the buffer and each candidate file, then merges what it finds, keeping the entry with the newest timestamp and honouring delete markers. Three things keep this cheap. Key ranges: each file records its smallest and largest key, so files that cannot contain the key are skipped. Bloom filters: each file carries a compact filter that answers "definitely not here" or "maybe here", so most files without the key are skipped without disk I/O. File indexes: for files that may hold it, a sparse index points to the block to read, usually one disk read. Caches for blocks or rows avoid even that. Bloom filters help lookups of a specific key; a range scan must still merge every file overlapping the range.

Because updates are new entries in new files, a key's data may be spread over the **memory buffer** and several **sorted files**. A point read therefore consults the buffer and each candidate file, then **merges** what it finds, keeping the entry with the newest timestamp and honouring delete markers. Three things keep this cheap. **Key ranges**: each file records its smallest and largest key, so files that cannot contain the key are skipped. **Bloom filters**: each file carries a compact filter that answers "definitely not here" or "maybe here", so most files without the key are skipped without disk I/O. **File indexes**: for files that may hold it, a sparse index points to the block to read, usually one disk read. Caches for blocks or rows avoid even that. Bloom filters help lookups of a specific key; a range scan must still merge every file overlapping the range.

code

pseudocode · 11 lines

pseudocode

function get(key):
    candidates = [memtable] + [f for f in filesNewestFirst if f.minKey <= key <= f.maxKey]
    entries = []
    for source in candidates:
        if source is a file and not source.bloom.mightContain(key):
            continue                      # definitely absent: skip without disk I/O
        entries += source.lookup(key)     # file index locates the block
    newest = maxByTimestamp(entries)
    if newest is none or newest.isTombstone:
        return NOT_FOUND
    return newest.value

go deeper

for a junior

Know that a read checks the memory buffer and possibly several files, and that the newest version wins.

for a middle

Explain the read steps with key ranges, bloom filters and file indexes, and why filters give no false negatives.

for a senior

Diagnose slow reads from overlapping files, delete markers or evicted filters, and relate them to compaction health.

for a principal

Be ready to weigh memory for filters and caches against read latency targets for a workload.

Why reads have more to do

In a log-structured engine, writes never modify existing files. After a while, one key may have:

its latest value in the memory buffer;
an older value in a recently flushed file;
an even older value, or a delete marker, in older files.

A read must find all relevant entries and decide which one is current. The number of places it has to look is the engine's read amplification.

The steps of a point read

Check the memory buffer(s) — the active one and any being flushed.
Pick candidate files. Skip every file whose recorded key range excludes the key.
Consult each candidate's bloom filter. If it says the key is definitely absent, skip the file.
Use the file's index. For the remaining files, a sparse index (one entry per block) locates the block that would contain the key.
Read the block, from a cache if possible, else from disk, and extract the entries for the key.
Merge. Combine entries from all sources; for each cell the newest timestamp wins, and a delete marker hides older data.

Bloom filters, briefly

A bloom filter is a small bit array per file that answers membership questions with no false negatives and a tunable rate of false positives. In the read path that means:

"not here" is always right, so the file is safely skipped;
"maybe here" occasionally costs a wasted block read.

Filters are kept in memory; memory spent on them buys fewer wasted reads. How the filter works internally, and how it is sized for a target error rate, is a data-structure subject of its own.

Where filters do not help

read	filter useful?	why
point read of one key	yes	"is this key in the file?" is exactly the filter's question
range or prefix scan	no	a range cannot be tested against a set of hashed keys, so every overlapping file is merged
read of a key that exists everywhere	little	every file really does contain it

Range scans therefore depend on having fewer overlapping files, which is compaction's job.

Other helpers

Block cache: recently read blocks stay in memory.
Row or key caches: some engines cache hot rows or the position of hot keys.
Per-file metadata: minimum and maximum timestamps let a read of recent data skip old files.

What makes reads slow

Many overlapping files, because compaction has fallen behind.
Many versions or delete markers for the same key, all read and merged.
Filters evicted or disabled to save memory.
Large rows or partitions read in full.

Interview angle

Describe the read as "check memory, check candidate files newest first, merge by timestamp", explain what bloom filters and indexes each save, and note that range scans cannot use the filters.

## Why reads have more to do In a log-structured engine, writes never modify existing files. After a while, one key may have: - its latest value in the **memory buffer**; - an older value in a recently flushed file; - an even older value, or a delete marker, in older files. A read must find **all** relevant entries and decide which one is current. The number of places it has to look is the engine's **read amplification**. ## The steps of a point read 1. **Check the memory buffer(s)** — the active one and any being flushed. 2. **Pick candidate files.** Skip every file whose recorded key range excludes the key. 3. **Consult each candidate's bloom filter.** If it says the key is definitely absent, skip the file. 4. **Use the file's index.** For the remaining files, a sparse index (one entry per block) locates the block that would contain the key. 5. **Read the block**, from a cache if possible, else from disk, and extract the entries for the key. 6. **Merge.** Combine entries from all sources; for each cell the **newest timestamp** wins, and a **delete marker** hides older data. ## Bloom filters, briefly A bloom filter is a small bit array per file that answers membership questions with **no false negatives** and a tunable rate of **false positives**. In the read path that means: - "not here" is always right, so the file is safely skipped; - "maybe here" occasionally costs a wasted block read. Filters are kept in memory; memory spent on them buys fewer wasted reads. How the filter works internally, and how it is sized for a target error rate, is a data-structure subject of its own. ## Where filters do not help | read | filter useful? | why | |---|---|---| | point read of one key | yes | "is this key in the file?" is exactly the filter's question | | range or prefix scan | no | a range cannot be tested against a set of hashed keys, so every overlapping file is merged | | read of a key that exists everywhere | little | every file really does contain it | Range scans therefore depend on having **fewer overlapping files**, which is compaction's job. ## Other helpers - **Block cache**: recently read blocks stay in memory. - **Row or key caches**: some engines cache hot rows or the position of hot keys. - **Per-file metadata**: minimum and maximum timestamps let a read of recent data skip old files. ## What makes reads slow - Many overlapping files, because compaction has fallen behind. - Many versions or delete markers for the same key, all read and merged. - Filters evicted or disabled to save memory. - Large rows or partitions read in full. ## Interview angle Describe the read as "check memory, check candidate files newest first, merge by timestamp", explain what bloom filters and indexes each save, and note that range scans cannot use the filters.

Why can't a bloom filter speed up a range scan?
The filter tests membership of exact keys through hashing, which destroys order. A range covers keys you do not know in advance, so there is nothing to test; every file overlapping the range must be read and merged.
A read of a key that was deleted long ago is slow. Why might that be?
Until compaction purges it, the delete marker and the old data still sit in files, so the read must find and merge them to conclude the key is gone. Many such markers on a path make "empty" reads expensive.

saying these in an interview costs you the question

Believing a read checks only the newest file
Saying bloom filters can return false negatives
Expecting bloom filters to speed up range scans
Thinking reads use the commit log to find recent writes

Why reads have more to do

In a log-structured engine, writes never modify existing files. After a while, one key may have:

its latest value in the memory buffer;

an older value in a recently flushed file;

an even older value, or a delete marker, in older files.

A read must find all relevant entries and decide which one is current. The number of places it has to look is the engine's read amplification.

The steps of a point read

Check the memory buffer(s) — the active one and any being flushed.

Pick candidate files. Skip every file whose recorded key range excludes the key.

Consult each candidate's bloom filter. If it says the key is definitely absent, skip the file.

Use the file's index. For the remaining files, a sparse index (one entry per block) locates the block that would contain the key.

Read the block, from a cache if possible, else from disk, and extract the entries for the key.

Merge. Combine entries from all sources; for each cell the newest timestamp wins, and a delete marker hides older data.

Bloom filters, briefly

A bloom filter is a small bit array per file that answers membership questions with no false negatives and a tunable rate of false positives. In the read path that means:

"not here" is always right, so the file is safely skipped;

"maybe here" occasionally costs a wasted block read.

Filters are kept in memory; memory spent on them buys fewer wasted reads. How the filter works internally, and how it is sized for a target error rate, is a data-structure subject of its own.

Where filters do not help

read	filter useful?	why
point read of one key	yes	"is this key in the file?" is exactly the filter's question
range or prefix scan	no	a range cannot be tested against a set of hashed keys, so every overlapping file is merged
read of a key that exists everywhere	little	every file really does contain it

Range scans therefore depend on having fewer overlapping files, which is compaction's job.

How does a read find a key in a log-structured engine that holds several sorted files, and how do bloom filters and file indexes limit the work?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~3 min

Why reads have more to do

The steps of a point read

Bloom filters, briefly

Where filters do not help

Other helpers

What makes reads slow

Interview angle

▾common follow-ups2 questions

▾red flags4 flags

Why reads have more to do

The steps of a point read

Bloom filters, briefly

Where filters do not help

Other helpers

What makes reads slow

Interview angle

answer

go deeper