Data & storage / 7 / 15
Bloom filters
An online shop's sign-up form asks "is this username taken?" on every keystroke, against 50 million accounts. Most names typed are free, and each one costs a database lookup. How a 62 MB bit array answers "definitely free" without the database, how to size it, why it cannot forget, and where the same trick hides inside storage engines.
- 13 min
- Intermediate
- 11 steps
- DB reads
- 1 000 /s
- Check p95
- 18 ms
- False positives
- —
- Filter memory
- —
- request
- reply
- redelivery
- duplicate
- lost
Numbers are a model scenario, not measurements
The real request
Sign-up form → Accounts APIRequest
GET /usernames/ali_k1993x/available HTTP/1.11
Host: shop.example.com
Response
HTTP/1.1 200 OK
X-DB-Time2: 4 ms
{
"username": "ali_k1993x",
"available": true
}
available— The whole answer: one bit of information.X-DB-Time— Each check costs a database round trip, even for a name nobody has.
Build it yourselfCheat sheetCompare lessons
Course: 74 lessons
01 Foundations
02 Scaling
03 Data & storage
04 Communication
05 Reliability
06 Architecture
07 Security
08 Shipping
09 Whole systems
10 Business processes
11 Case studies