Topic 10.4
Distributed Object Existence and an LSM Storage Engine
In one line
For 10B stored objects, fast existence checks use per-shard filters (co-located with storage nodes), local filters for hot namespaces, and a shared filter only where query rates allow; deletes push toward cuckoo filters or rebuilds. In an LSM engine, the same idea appears as one filter per SSTable, built at flush time.
Think of it like this
A warehouse network where each warehouse keeps a quick list of what it holds, and head office routes each request only to warehouses that might have the item.
Key ideas
- 01
Object stores: keys map to shards by hash (routing is deterministic), so the filter's job is to avoid disk or index lookups on the owning shard for nonexistent keys (404s), not routing.
- 02
Per-shard filters: each storage node keeps a filter for its objects (for example 100M objects × 14.4 bits ≈ 180 MB at 0.1%); built at write time and rebuilt during compaction.
- 03
Deletes: object deletion is common; options are counting/cuckoo filters, or LSM-style immutable segments each with its own filter where compaction rebuilds filters without deleted keys.
- 04
LSM engine design: MemTable → flush to SSTable with index + Bloom filter; reads check MemTable, then filters from newest to oldest; compaction merges SSTables and rebuilds filters (naturally purging deleted keys).
- 05
Tune bits per key per level: many filters for small upper levels (cheap), fewer bits on the largest level if most lookups hit existing keys.
Code & diagrams
Interview problem
The problem
Existence checks for 10 billion objects
Design fast existence checking for an object store with 10 billion objects. Discuss local, shared and per-shard filters, false positives and object deletion.
Explain it without notes
Why does an LSM design handle deletes well for Bloom filters?
Practice
Estimate filter memory per storage node for 10B objects on 250 nodes at 1%.
Trade-offs
- ↔
Per-shard filters scale with data and avoid global bottlenecks, at the cost of per-node memory and rebuilds.
Done when you can
I can design existence checks for large object stores and explain filters in LSM engines.