mufassall

Cheat sheet · Data & storage

Bloom filters

13 min · Intermediate · mufassall.dtwin.uz/en/l/bloom-filter/

← Open the lesson

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
Final scene
35%30%35%

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_sst3

Mermaid: 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 reads

D2

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
@enduml

PlantUML: 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
@enduml

Recap

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

MetricStartEnd
DB reads1 000/s620/s
Check p9518 ms6 ms
False positives0.8%0.8%
Filter memory62.5 MB600 MB

Steps

  1. Case A database lookup for every keystroke

    While a new customer types a username, the form asks the API after every pause: is ali_k1993x free?

  2. Problem A sign-up campaign triples the checks

    A marketing campaign brings a wave of sign-ups: 3000 checks a second.

  3. 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.

  4. Case "Maybe" goes to the database

    For a taken name all k bits are 1, and the API confirms in the database.

  5. 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.

  6. Fix Trading memory for accuracy

    The rate depends only on bits per key, not on the total size.

  7. 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.

  8. Problem A filter cannot forget

    A customer closes the account ali_k, and the name should become free.

  9. Fix Counting Bloom filter, or rebuild

    A counting Bloom filter keeps a small counter in each slot instead of a bit.

  10. Case The same trick inside the database

    Storage engines built on an LSM tree keep data in many sorted files on disk, SSTables.

  11. 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.