mufassall

Konspekt · Ma'lumot va saqlash

Bloom filtri

13 daq · O'rta · mufassall.dtwin.uz/uz/l/bloom-filter/

← Darsni ochish

Muammo

Internet-do'konning ro'yxatdan o'tish formasi har bir tugma bosilganda 50 million akkaunt ichida "bu nom bandmi?" deb so'raydi. Yozilayotgan nomlarning ko'pi bo'sh, har biri esa bazaga bitta so'rov. 62 MB lik bit massivi bazasiz qanday qilib "aniq bo'sh" deydi, uni qanday hisoblash kerak, nega u unutolmaydi va shu usul saqlash dvigatellari ichida qayerda yashirinadi.

Nimani o'rganasiz

  • Bloom filtri qanday ishlaydi: m bit, k xesh, "aniq yo'q" yoki "balki"
  • Soxta musbat javob hisobi: kalitga 10 ga yaqin bit va 7 xesh taxminan 1% beradi
  • Nega filtr o'sishni hisobga olib o'lchanadi va to'lganda qayta quriladi
  • Nega undan o'chirib bo'lmaydi, sanovchi Bloom filtri va LSM o'qishlaridagi Bloom filtrlari
Yakuniy sahna
35%30%35%

Diagramma kod sifatida

Darsdagi yakuniy sxemani matn ko'rinishida oling va Jira, GitLab, GitHub, Notion yoki hujjatga qo'ying: Mermaid u yerlarda o'zi chiziladi. D2 va PlantUML (Confluence, IntelliJ) uchun alohida variantlar bor.

Mermaid: sxema

flowchart LR
  n_form(["Ro'yxat formasi"])
  n_api["Akkauntlar API"]
  n_db[("Foydalanuvchilar bazasi")]
  n_filter{{"Bloom filtri"}}
  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: so'rovlar ketma-ketligi

sequenceDiagram
  participant n_form as Ro'yxat formasi
  participant n_api as Akkauntlar API
  participant n_db as Foydalanuvchilar bazasi
  participant n_filter as Bloom filtri
  participant n_sst3 as SSTable 3
  Note over n_form,n_api: Har bir bosishga bazadan qidiruv
  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: Ro'yxatdan o'tish kampaniyasi tekshiruvlarni uch barobar oshiradi
  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: #34;Aniq yo'q#34; deydigan bit massivi
  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;Balki#34; bazaga boradi
  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: U qanchalik tez-tez aldaydi: soxta musbat formulasi
  n_api->>n_filter: bloom sizing, n = 50 000 000 usernames
  Note over n_api,n_filter: Xotirani aniqlikka almashtirish
  n_api->>n_filter: bits per key vs false positives, n = 50 000 000
  Note over n_db,n_filter: Foydalanuvchilar ko'paygan sari filtr to'ladi
  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: Filtr unutolmaydi
  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: Sanovchi Bloom filtri yoki qayta qurish
  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: Baza ichidagi o'sha usul
  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: "Ro'yxat formasi" {
  shape: rectangle
}
n_api: "Akkauntlar API" {
  shape: rectangle
}
n_db: "Foydalanuvchilar bazasi" {
  shape: cylinder
}
n_filter: "Bloom filtri" {
  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: so'rovlar ketma-ketligi

@startuml
participant "Ro'yxat formasi" as n_form
participant "Akkauntlar API" as n_api
database "Foydalanuvchilar bazasi" as n_db
collections "Bloom filtri" as n_filter
database "SSTable 3" as n_sst3
note over n_form, n_api : Har bir bosishga bazadan qidiruv
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 : Ro'yxatdan o'tish kampaniyasi tekshiruvlarni uch barobar oshiradi
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 : "Aniq yo'q" deydigan bit massivi
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 : "Balki" bazaga boradi
n_api -> n_filter : bloom.contains("zarina_t")
n_filter --> n_api : maybe present -> ask the DB
note over n_api, n_filter : U qanchalik tez-tez aldaydi: soxta musbat formulasi
n_api -> n_filter : bloom sizing, n = 50 000 000 usernames
note over n_api, n_filter : Xotirani aniqlikka almashtirish
n_api -> n_filter : bits per key vs false positives, n = 50 000 000
note over n_db, n_filter : Foydalanuvchilar ko'paygan sari filtr to'ladi
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 : Filtr unutolmaydi
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 : Sanovchi Bloom filtri yoki qayta qurish
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 : Baza ichidagi o'sha usul
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: komponentlar

@startuml
left to right direction
agent "Ro'yxat formasi" as n_form
component "Akkauntlar API" as n_api
database "Foydalanuvchilar bazasi" as n_db
stack "Bloom filtri" 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

Xulosa

Bloom filtri uchun besh qoida.

1) So'raladigan kalitlarning ko'pi mavjud bo'lmasa, uni qimmat qidiruv oldiga qo'ying. 2) "Yo'q" — aniq, "balki" haqiqiy omborga boradi. 3) Kalitga 10 ga yaqin bit va 7 xesh taxminan 1% soxta musbat beradi; har ~5 qo'shimcha bit buni o'n barobar kamaytiradi. 4) Kelajakdagi n ga hisoblang, to'lishni kuzating, kattaroq filtrga qayta quring. 5) Oddiy filtr o'chira olmaydi: sanovchi filtrdan foydalaning yoki jadval bo'yicha qayta quring.

Ko'rsatkichlar: boshida va oxirida

Ko'rsatkichBoshidaOxirida
Baza o'qishlari1 000/s620/s
Tekshiruv p9518 ms6 ms
Soxta musbat0,8%0,8%
Filtr xotirasi62,5 MB600 MB

Qadamlar

  1. Holat Har bir bosishga bazadan qidiruv

    Yangi xaridor nom yozayotganda, forma har to'xtashdan keyin API'dan so'raydi: ali_k1993x bo'shmi?

  2. Muammo Ro'yxatdan o'tish kampaniyasi tekshiruvlarni uch barobar oshiradi

    Marketing kampaniyasi ro'yxatdan o'tish to'lqinini olib keladi: soniyasiga 3000 tekshiruv.

  3. Yechim "Aniq yo'q" deydigan bit massivi

    API xotirada Bloom filtri saqlaydi: m bitli massiv, boshida hammasi nol.

  4. Holat "Balki" bazaga boradi

    Band nomda barcha k bit 1, va API buni bazada tasdiqlaydi.

  5. Holat U qanchalik tez-tez aldaydi: soxta musbat formulasi

    n ta nom, m bit va k xeshda bo'sh nomning barcha bitlari 1 chiqish ehtimoli taxminan p = (1 - e^(-kn/m))^k.

  6. Yechim Xotirani aniqlikka almashtirish

    Ulush umumiy o'lchamga emas, faqat kalitga to'g'ri keladigan bitga bog'liq.

  7. Muammo Foydalanuvchilar ko'paygan sari filtr to'ladi

    Ikki yildan keyin do'konda 120 million akkaunt bor, filtrda esa hamon 500 million bit.

  8. Muammo Filtr unutolmaydi

    Xaridor ali_k akkauntini yopadi va nom bo'shashi kerak.

  9. Yechim Sanovchi Bloom filtri yoki qayta qurish

    Sanovchi Bloom filtri har katakda bit o'rniga kichik hisoblagich saqlaydi.

  10. Holat Baza ichidagi o'sha usul

    LSM daraxtiga qurilgan saqlash dvigatellari ma'lumotni diskdagi ko'p saralangan fayllarda — SSTable'larda saqlaydi.

  11. Xulosa Xulosa

    Bloom filtri uchun besh qoida.

Atamalar

Bloom filtr
Bit massivi va bir nechta hash: "bu kalit to'plamda yo'q" deganida doim to'g'ri, "bor bo'lishi mumkin" deganida esa ba'zan xato qiladi. Kalitiga 10 bit va 7 hash bilan xato taxminan 1% bo'ladi, oddiy filtrdan kalitni o'chirib bo'lmaydi.