Konspekt · Ma'lumot va saqlash
Consistent hashing
Muammo
Profil API tez-tez so'raladigan ma'lumotni uchta kesh serverda saqlaydi. To'rtinchisini qo'shish yordam berishi kerak edi, lekin `hash % N` bilan u deyarli butun keshni bo'shatadi. Hash ring qanday qilib kalitlarning faqat choragini ko'chiradi va unga nega virtual node'lar kerak.
Nimani o'rganasiz
- Nega
hash % Nda N o'zgarsa deyarli har bir kalit boshqa joyga ketadi - Hash ring node'ni qanday tanlaydi: soat strelkasi bo'yicha keyingi nuqta
- Nega node qo'shilganda yoki chiqqanda kalitlarning faqat ~1/N qismi ko'chadi
- Virtual node'lar nimani tuzatadi: notekis yoylar va o'lgan node yuki
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_client(["Ilova"])
n_api["Profil API"]
n_cache_a{{"Kesh A"}}
n_cache_b{{"Kesh B"}}
n_cache_c{{"Kesh C"}}
n_db[("Foydalanuvchilar bazasi")]
n_cache_d{{"Kesh D"}}
n_client --> n_api
n_api --> n_cache_a
n_api --x|"yo'qoldi"| n_cache_b
n_api --> n_cache_c
n_api --> n_db
n_api --> n_cache_d
classDef down fill:#fde2e2,stroke:#c62828,color:#4a0d0d,stroke-dasharray:4 3
class n_cache_b downMermaid: so'rovlar ketma-ketligi
sequenceDiagram
participant n_api as Profil API
participant n_cache_b as Kesh B
participant n_cache_d as Kesh D
participant n_db as Foydalanuvchilar bazasi
participant n_cache_c as Kesh C
Note over n_api,n_cache_b: Uchta kesh, bitta qoida: hash % 3
n_api->>n_cache_b: GET user:u_42
n_cache_b-->>n_api: #34;plan=pro#59;lang=uz#34;
Note over n_api,n_cache_d: To'rtinchi kesh qolgan uchtasini bo'shatadi
n_api->>n_cache_d: GET user:u_42
n_cache_d-->>n_api: (nil)
Note over n_api,n_db: Har bir miss bazaga tushadi
n_api->>n_db: SELECT plan, lang FROM users
n_db-->>n_api: pro #124; uz (1 row, 410 ms)
Note over n_api,n_cache_b: Kalitlarni ham, node'larni ham bitta halqaga qo'yamiz
n_api->>n_cache_b: DEBUG ring lookup user:u_42
n_cache_b-->>n_api: #34;plan=pro#59;lang=uz#34;
Note over n_api,n_cache_d: Endi yangi node faqat bitta yoyni oladi
n_api->>n_cache_d: INFO ring add cache-d at 0x4CC00000
Note over n_api,n_cache_c: To'rtta nuqta halqani teng bo'lmagan yoylarga bo'ladi
n_api->>n_cache_c: INFO keyspace
n_cache_c-->>n_api: #35; Keyspace
Note over n_api,n_cache_c: Virtual node'lar: har bir keshga ko'p kichik nuqta
n_api->>n_cache_c: INFO ring rebuilt: 4 nodes x 128 vnodes
Note over n_api,n_cache_b: Kesh o'lsa, uning kalitlari tarqaladi
n_api-xn_cache_b: PINGD2
direction: right
n_client: "Ilova" {
shape: rectangle
}
n_api: "Profil API" {
shape: rectangle
}
n_cache_a: "Kesh A" {
shape: hexagon
}
n_cache_b: "Kesh B" {
shape: hexagon
style.fill: "#fde2e2"
style.stroke: "#c62828"
style.stroke-dash: 3
}
n_cache_c: "Kesh C" {
shape: hexagon
}
n_db: "Foydalanuvchilar bazasi" {
shape: cylinder
}
n_cache_d: "Kesh D" {
shape: hexagon
}
n_client -> n_api
n_api -> n_cache_a
n_api -> n_cache_b: "yo'qoldi" {
target-arrowhead.shape: cross
}
n_api -> n_cache_c
n_api -> n_db
n_api -> n_cache_dPlantUML: so'rovlar ketma-ketligi
@startuml
participant "Profil API" as n_api
collections "Kesh B" as n_cache_b
collections "Kesh D" as n_cache_d
database "Foydalanuvchilar bazasi" as n_db
collections "Kesh C" as n_cache_c
note over n_api, n_cache_b : Uchta kesh, bitta qoida: hash % 3
n_api -> n_cache_b : GET user:u_42
n_cache_b --> n_api : "plan=pro;lang=uz"
note over n_api, n_cache_d : To'rtinchi kesh qolgan uchtasini bo'shatadi
n_api -> n_cache_d : GET user:u_42
n_cache_d --> n_api : (nil)
note over n_api, n_db : Har bir miss bazaga tushadi
n_api -> n_db : SELECT plan, lang FROM users
n_db --> n_api : pro | uz (1 row, 410 ms)
note over n_api, n_cache_b : Kalitlarni ham, node'larni ham bitta halqaga qo'yamiz
n_api -> n_cache_b : DEBUG ring lookup user:u_42
n_cache_b --> n_api : "plan=pro;lang=uz"
note over n_api, n_cache_d : Endi yangi node faqat bitta yoyni oladi
n_api -> n_cache_d : INFO ring add cache-d at 0x4CC00000
note over n_api, n_cache_c : To'rtta nuqta halqani teng bo'lmagan yoylarga bo'ladi
n_api -> n_cache_c : INFO keyspace
n_cache_c --> n_api : # Keyspace
note over n_api, n_cache_c : Virtual node'lar: har bir keshga ko'p kichik nuqta
n_api -> n_cache_c : INFO ring rebuilt: 4 nodes x 128 vnodes
note over n_api, n_cache_b : Kesh o'lsa, uning kalitlari tarqaladi
n_api ->x n_cache_b : [yo'qoldi] PING
@endumlPlantUML: komponentlar
@startuml
left to right direction
agent "Ilova" as n_client
component "Profil API" as n_api
stack "Kesh A" as n_cache_a
stack "Kesh B" as n_cache_b #fde2e2;line:c62828;line.dashed
stack "Kesh C" as n_cache_c
database "Foydalanuvchilar bazasi" as n_db
stack "Kesh D" as n_cache_d
n_client --> n_api
n_api --> n_cache_a
n_api -[#c62828,dashed]-> n_cache_b : yo'qoldi
n_api --> n_cache_c
n_api --> n_db
n_api --> n_cache_d
@endumlXulosa
hash % N N hech qachon o'zgarmaguncha yaxshi. N o'zgarsa, deyarli har bir kalit ko'chadi.
1) Node'lar va kalitlarni bitta halqaga qo'ying; kalit soat strelkasi bo'yicha keyingi node'ga tegishli. 2) Node qo'shilsa yoki chiqsa, kalitlarning faqat ~1/N qismi ko'chadi. 3) Har bir node'ga ko'p virtual nuqta bering, shunda yoylar va yuk tenglashadi. 4) Barcha klientlar bir xil node ro'yxatini ishlatishi kerak.
Ko'rsatkichlar: boshida va oxirida
| Ko'rsatkich | Boshida | Oxirida |
|---|---|---|
| Keshdan topildi (hit) | 95% | 72% |
| Bazadan o'qish | 250/s | 1 400/s |
| Ko'chgan kalitlar | 0% | 25% |
Qadamlar
- Holat Uchta kesh, bitta qoida:
hash % 3API soniyasiga 5 000 ga yaqin profil o'qiydi.
- Muammo To'rtinchi kesh qolgan uchtasini bo'shatadi
Xotira yetmayapti, to'rtinchi kesh qo'shildi va qoida
hash % 4bo'ldi. - Muammo Har bir miss bazaga tushadi
Hit rate 95% dan 24% ga tushdi.
- Yechim Kalitlarni ham, node'larni ham bitta halqaga qo'yamiz
Uchta keshga qaytamiz va qoidani o'zgartiramiz.
- Yechim Endi yangi node faqat bitta yoyni oladi
D kesh
0x4CC00000nuqtaga qo'shildi. - Muammo To'rtta nuqta halqani teng bo'lmagan yoylarga bo'ladi
Har bir keshda bitta nuqta bo'lsa, yoylar hash'lar kabi tasodifiy chiqadi.
- Yechim Virtual node'lar: har bir keshga ko'p kichik nuqta
Endi har bir keshga halqada 128 ta nuqta beriladi (
cache-a#0…cache-a#127), har biri o'z hash'idan. - Holat Kesh o'lsa, uning kalitlari tarqaladi
B kesh javob bermay qo'ydi va API uni halqadan olib tashladi.
- Xulosa Xulosa
hash % NN hech qachon o'zgarmaguncha yaxshi.
Atamalar
- Consistent hashing
- Node'lar va kalitlar bitta halqaga qo'yiladi, kalit soat strelkasi bo'yicha keyingi node'ga tegishli. Node qo'shilsa yoki chiqsa kalitlarning faqat ~1/N qismi ko'chadi; virtual node'lar yukni tenglashtiradi.