mufassall

Шпаргалка · Данные и хранение

Фильтр Блума

13 мин · Средний · mufassall.dtwin.uz/ru/l/bloom-filter/

← Открыть урок

Проблема

Форма регистрации интернет-магазина на каждое нажатие спрашивает «занято ли это имя?» среди 50 миллионов аккаунтов. Большинство набираемых имён свободны, и каждое стоит запроса в базу. Как битовый массив на 62 МБ отвечает «точно свободно» без базы, как его рассчитать, почему он не умеет забывать и где тот же приём прячется внутри движков хранения.

Чему вы научитесь

  • Как работает фильтр Блума: m бит, k хешей, «точно нет» или «возможно»
  • Математика ложных срабатываний: около 10 бит на ключ и 7 хешей дают около 1%
  • Почему фильтр рассчитывают с запасом на рост и перестраивают, когда он заполняется
  • Почему из него нельзя удалять, считающий фильтр Блума и фильтры Блума при чтении в LSM
Итоговая сцена
35%30%35%

Диаграмма как код

Итоговая схема урока в виде текста: вставьте её в Jira, GitLab, GitHub, Notion или документацию, там Mermaid рисуется сам. Есть варианты для D2 и PlantUML (Confluence, IntelliJ).

Mermaid: схема

flowchart LR
  n_form(["Форма регистрации"])
  n_api["API аккаунтов"]
  n_db[("БД пользователей")]
  n_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: последовательность запросов

sequenceDiagram
  participant n_form as Форма регистрации
  participant n_api as API аккаунтов
  participant n_db as БД пользователей
  participant n_filter as Фильтр Блума
  participant n_sst3 as SSTable 3
  Note over n_form,n_api: Запрос в базу на каждое нажатие
  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: Кампания регистраций утраивает проверки
  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: Битовый массив, который говорит «точно нет»
  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: «Возможно» идёт в базу
  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: Как часто он врёт: формула ложных срабатываний
  n_api->>n_filter: bloom sizing, n = 50 000 000 usernames
  Note over n_api,n_filter: Меняем память на точность
  n_api->>n_filter: bits per key vs false positives, n = 50 000 000
  Note over n_db,n_filter: Фильтр заполняется по мере роста пользователей
  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: Фильтр не умеет забывать
  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: Считающий фильтр Блума или перестройка
  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: Тот же приём внутри базы
  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: "Форма регистрации" {
  shape: rectangle
}
n_api: "API аккаунтов" {
  shape: rectangle
}
n_db: "БД пользователей" {
  shape: cylinder
}
n_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: последовательность запросов

@startuml
participant "Форма регистрации" as n_form
participant "API аккаунтов" as n_api
database "БД пользователей" as n_db
collections "Фильтр Блума" as n_filter
database "SSTable 3" as n_sst3
note over n_form, n_api : Запрос в базу на каждое нажатие
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 : Кампания регистраций утраивает проверки
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 : Битовый массив, который говорит «точно нет»
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 : «Возможно» идёт в базу
n_api -> n_filter : bloom.contains("zarina_t")
n_filter --> n_api : maybe present -> ask the DB
note over n_api, n_filter : Как часто он врёт: формула ложных срабатываний
n_api -> n_filter : bloom sizing, n = 50 000 000 usernames
note over n_api, n_filter : Меняем память на точность
n_api -> n_filter : bits per key vs false positives, n = 50 000 000
note over n_db, n_filter : Фильтр заполняется по мере роста пользователей
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 : Фильтр не умеет забывать
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 : Считающий фильтр Блума или перестройка
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 : Тот же приём внутри базы
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: компоненты

@startuml
left to right direction
agent "Форма регистрации" as n_form
component "API аккаунтов" as n_api
database "БД пользователей" as n_db
stack "Фильтр Блума" 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

Итог

Пять правил для фильтра Блума.

1) Ставьте его перед дорогим поиском, когда большинства запрашиваемых ключей нет. 2) «Нет» — наверняка, «возможно» идёт в настоящее хранилище. 3) Около 10 бит на ключ и 7 хешей дают около 1% ложных срабатываний; каждые ~5 бит сверху уменьшают это в десять раз. 4) Рассчитывайте на будущее n, следите за заполнением, перестраивайте в больший фильтр. 5) Обычный фильтр не умеет удалять: берите считающий или перестраивайте по расписанию.

Показатели: в начале и в конце

ПоказательВ началеВ конце
Чтения БД1 000/с620/с
p95 проверки18 мс6 мс
Ложные срабатывания0,8%0,8%
Память фильтра62,5 МБ600 МБ

Шаги

  1. Кейс Запрос в базу на каждое нажатие

    Пока новый покупатель набирает имя, форма после каждой паузы спрашивает API: свободно ли ali_k1993x?

  2. Проблема Кампания регистраций утраивает проверки

    Маркетинговая кампания приводит волну регистраций: 3000 проверок в секунду.

  3. Решение Битовый массив, который говорит «точно нет»

    API держит в памяти фильтр Блума: массив из m бит, сначала все нули.

  4. Кейс «Возможно» идёт в базу

    У занятого имени все k бит равны 1, и API подтверждает это в базе.

  5. Кейс Как часто он врёт: формула ложных срабатываний

    При n именах, m битах и k хешах вероятность, что у свободного имени все биты окажутся единицами, примерно p = (1 - e^(-kn/m))^k.

  6. Решение Меняем память на точность

    Доля зависит только от бит на ключ, а не от общего размера.

  7. Проблема Фильтр заполняется по мере роста пользователей

    Через два года в магазине 120 миллионов аккаунтов, а в фильтре всё те же 500 миллионов бит.

  8. Проблема Фильтр не умеет забывать

    Покупатель закрывает аккаунт ali_k, и имя должно освободиться.

  9. Решение Считающий фильтр Блума или перестройка

    Считающий фильтр Блума хранит в каждой ячейке маленький счётчик вместо бита.

  10. Кейс Тот же приём внутри базы

    Движки хранения на LSM-дереве держат данные во многих отсортированных файлах на диске — SSTable.

  11. Итоги Итог

    Пять правил для фильтра Блума.

Термины

Фильтр Блума
Битовый массив и несколько хешей: ответ «ключа точно нет» всегда верен, а «возможно, есть» иногда ошибочен. При 10 битах на ключ и 7 хешах ошибка около 1%, удалить ключ из обычного фильтра нельзя.