Konspekt · Ma'lumot va saqlash
Bloom filtri
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
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_sst3Mermaid: 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 readsD2
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
@endumlPlantUML: 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
@endumlXulosa
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'rsatkich | Boshida | Oxirida |
|---|---|---|
| Baza o'qishlari | 1 000/s | 620/s |
| Tekshiruv p95 | 18 ms | 6 ms |
| Soxta musbat | 0,8% | 0,8% |
| Filtr xotirasi | 62,5 MB | 600 MB |
Qadamlar
- Holat Har bir bosishga bazadan qidiruv
Yangi xaridor nom yozayotganda, forma har to'xtashdan keyin API'dan so'raydi:
ali_k1993xbo'shmi? - Muammo Ro'yxatdan o'tish kampaniyasi tekshiruvlarni uch barobar oshiradi
Marketing kampaniyasi ro'yxatdan o'tish to'lqinini olib keladi: soniyasiga 3000 tekshiruv.
- Yechim "Aniq yo'q" deydigan bit massivi
API xotirada Bloom filtri saqlaydi: m bitli massiv, boshida hammasi nol.
- Holat "Balki" bazaga boradi
Band nomda barcha k bit 1, va API buni bazada tasdiqlaydi.
- 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.
- Yechim Xotirani aniqlikka almashtirish
Ulush umumiy o'lchamga emas, faqat kalitga to'g'ri keladigan bitga bog'liq.
- Muammo Foydalanuvchilar ko'paygan sari filtr to'ladi
Ikki yildan keyin do'konda 120 million akkaunt bor, filtrda esa hamon 500 million bit.
- Muammo Filtr unutolmaydi
Xaridor
ali_kakkauntini yopadi va nom bo'shashi kerak. - Yechim Sanovchi Bloom filtri yoki qayta qurish
Sanovchi Bloom filtri har katakda bit o'rniga kichik hisoblagich saqlaydi.
- Holat Baza ichidagi o'sha usul
LSM daraxtiga qurilgan saqlash dvigatellari ma'lumotni diskdagi ko'p saralangan fayllarda — SSTable'larda saqlaydi.
- 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.