Cheat sheet · Data & storage
Bloom filters
The problem
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.
What you learn
- How a Bloom filter works: m bits, k hashes, "definitely not" or "maybe"
- False-positive math: about 10 bits per key and 7 hashes give about 1%
- Why a filter must be sized for its growth and rebuilt when it fills up
- Why you cannot delete from it, counting Bloom filters, and Bloom filters in LSM reads
Diagram as code
The lesson's final design as text: paste it into Jira, GitLab, GitHub, Notion or your docs, where Mermaid renders by itself. There are D2 and PlantUML (Confluence, IntelliJ) versions too.
Mermaid: flowchart
flowchart LR
n_form(["Sign-up form"])
n_api["Accounts API"]
n_db[("Users DB")]
n_filter{{"Bloom filter"}}
n_sst1[("SSTable 1")]
n_sst2[("SSTable 2")]
n_sst3[("SSTable 3")]
n_form --> n_api
n_api --> n_db
n_api --> n_filter
n_db -.-> n_sst1
n_db -.-> n_sst2
n_db -.-> n_sst3Mermaid: request sequence
sequenceDiagram
participant n_form as Sign-up form
participant n_api as Accounts API
participant n_db as Users DB
participant n_filter as Bloom filter
participant n_sst3 as SSTable 3
Note over n_form,n_api: A database lookup for every keystroke
n_form->>n_api: GET /usernames/ali_k1993x/available HTTP/1.1
n_api-->>n_form: HTTP/1.1 200 OK
Note over n_api,n_db: A sign-up campaign triples the checks
n_api->>n_db: SELECT 1 FROM users WHERE username = 'ali_k1993x' LIMIT 1#59;
n_db-->>n_api: 0 rows, 4 ms
Note over n_api,n_filter: A bit array that says #34;definitely not#34;
n_api->>n_filter: bloom.contains(#34;ali_k1993x#34;)
n_filter-->>n_api: definitely not present -#62; available, no DB call
Note over n_api,n_filter: #34;Maybe#34; goes to the database
n_api->>n_filter: bloom.contains(#34;zarina_t#34;)
n_filter-->>n_api: maybe present -#62; ask the DB
Note over n_api,n_filter: How often it lies: the false-positive formula
n_api->>n_filter: bloom sizing, n = 50 000 000 usernames
Note over n_api,n_filter: Trading memory for accuracy
n_api->>n_filter: bits per key vs false positives, n = 50 000 000
Note over n_db,n_filter: The filter fills up as users grow
n_db->>n_filter: filter built for n = 50 000 000, now n = 120 000 000
n_filter-->>n_db: rebuild: scan 120 000 000 names into a 150 MB filter, then swap
Note over n_api,n_filter: A filter cannot forget
n_api->>n_filter: account ali_k closed, its name must become free
n_filter-->>n_api: bloom.contains(#34;zarina_t#34;) = false
Note over n_api,n_filter: Counting Bloom filter, or rebuild
n_api->>n_filter: counting bloom: 4-bit counters instead of bits
n_filter-->>n_api: memory: 4 x 150 MB = 600 MB
Note over n_db,n_sst3: The same trick inside the database
n_db->>n_sst3: GET user:ali_k1993x (LSM tree, 3 SSTables on disk)
n_sst3-->>n_db: not found, 0 disk readsD2
direction: right
n_form: "Sign-up form" {
shape: rectangle
}
n_api: "Accounts API" {
shape: rectangle
}
n_db: "Users DB" {
shape: cylinder
}
n_filter: "Bloom filter" {
shape: hexagon
}
n_sst1: "SSTable 1" {
shape: stored_data
}
n_sst2: "SSTable 2" {
shape: stored_data
}
n_sst3: "SSTable 3" {
shape: stored_data
}
n_form -> n_api
n_api -> n_db
n_api -> n_filter
n_db -> n_sst1 {
style.stroke-dash: 3
}
n_db -> n_sst2 {
style.stroke-dash: 3
}
n_db -> n_sst3 {
style.stroke-dash: 3
}PlantUML: request sequence
@startuml
participant "Sign-up form" as n_form
participant "Accounts API" as n_api
database "Users DB" as n_db
collections "Bloom filter" as n_filter
database "SSTable 3" as n_sst3
note over n_form, n_api : A database lookup for every keystroke
n_form -> n_api : GET /usernames/ali_k1993x/available HTTP/1.1
n_api --> n_form : HTTP/1.1 200 OK
note over n_api, n_db : A sign-up campaign triples the checks
n_api -> n_db : SELECT 1 FROM users WHERE username = 'ali_k1993x' LIMIT 1;
n_db --> n_api : 0 rows, 4 ms
note over n_api, n_filter : A bit array that says "definitely not"
n_api -> n_filter : bloom.contains("ali_k1993x")
n_filter --> n_api : definitely not present -> available, no DB call
note over n_api, n_filter : "Maybe" goes to the database
n_api -> n_filter : bloom.contains("zarina_t")
n_filter --> n_api : maybe present -> ask the DB
note over n_api, n_filter : How often it lies: the false-positive formula
n_api -> n_filter : bloom sizing, n = 50 000 000 usernames
note over n_api, n_filter : Trading memory for accuracy
n_api -> n_filter : bits per key vs false positives, n = 50 000 000
note over n_db, n_filter : The filter fills up as users grow
n_db -> n_filter : filter built for n = 50 000 000, now n = 120 000 000
n_filter --> n_db : rebuild: scan 120 000 000 names into a 150 MB filter, then swap
note over n_api, n_filter : A filter cannot forget
n_api -> n_filter : account ali_k closed, its name must become free
n_filter --> n_api : bloom.contains("zarina_t") = false
note over n_api, n_filter : Counting Bloom filter, or rebuild
n_api -> n_filter : counting bloom: 4-bit counters instead of bits
n_filter --> n_api : memory: 4 x 150 MB = 600 MB
note over n_db, n_sst3 : The same trick inside the database
n_db -> n_sst3 : GET user:ali_k1993x (LSM tree, 3 SSTables on disk)
n_sst3 --> n_db : not found, 0 disk reads
@endumlPlantUML: components
@startuml
left to right direction
agent "Sign-up form" as n_form
component "Accounts API" as n_api
database "Users DB" as n_db
stack "Bloom filter" as n_filter
storage "SSTable 1" as n_sst1
storage "SSTable 2" as n_sst2
storage "SSTable 3" as n_sst3
n_form --> n_api
n_api --> n_db
n_api --> n_filter
n_db ..> n_sst1
n_db ..> n_sst2
n_db ..> n_sst3
@endumlRecap
Five rules for Bloom filters.
1) Use one in front of an expensive lookup when most keys asked for do not exist. 2) "No" is certain, "maybe" goes to the real store. 3) About 10 bits per key with 7 hashes gives about 1% false positives; every ~5 more bits cut it tenfold. 4) Size for future n, watch the fill ratio, rebuild into a bigger filter. 5) A plain filter cannot delete: use a counting filter or rebuild on a schedule.
Numbers: at the start and at the end
| Metric | Start | End |
|---|---|---|
| DB reads | 1 000/s | 620/s |
| Check p95 | 18 ms | 6 ms |
| False positives | 0.8% | 0.8% |
| Filter memory | 62.5 MB | 600 MB |
Steps
- Case A database lookup for every keystroke
While a new customer types a username, the form asks the API after every pause: is
ali_k1993xfree? - Problem A sign-up campaign triples the checks
A marketing campaign brings a wave of sign-ups: 3000 checks a second.
- Fix A bit array that says "definitely not"
The API keeps a Bloom filter in memory: an array of m bits, all zero at first.
- Case "Maybe" goes to the database
For a taken name all k bits are 1, and the API confirms in the database.
- Case How often it lies: the false-positive formula
With n names, m bits and k hashes, the chance that a free name finds all its bits set is about p = (1 - e^(-kn/m))^k.
- Fix Trading memory for accuracy
The rate depends only on bits per key, not on the total size.
- Problem The filter fills up as users grow
Two years later the shop has 120 million accounts, but the filter still has 500 million bits.
- Problem A filter cannot forget
A customer closes the account
ali_k, and the name should become free. - Fix Counting Bloom filter, or rebuild
A counting Bloom filter keeps a small counter in each slot instead of a bit.
- Case The same trick inside the database
Storage engines built on an LSM tree keep data in many sorted files on disk, SSTables.
- Recap Recap
Five rules for Bloom filters.
Terms
- Bloom filter
- A bit array plus several hashes: "this key is definitely not here" is always right, "it might be here" is sometimes wrong. With 10 bits per key and 7 hashes the error is about 1%, and a plain filter cannot delete a key.