Bloom Filter

Data

Bloom Filter

A probabilistic set that answers 'definitely not present' or 'possibly present', with no false negatives.

Why interviewers ask about it

Used to skip SSTable reads in LSM engines and to stop cache-penetration attacks. ~10 bits per key for a 1% false-positive rate.

LSM Tree

Writes buffer in a memtable and flush as immutable sorted files, merged by background compaction.

Cache Penetration

Repeated requests for keys that do not exist, so the cache never helps and every request reaches the database.

This term is part of the free System Design interview preparation module - browse the full glossary for every definition.