mufassall

Konspekt · Ma'lumot va saqlash

Consistent hashing

12 daq · O'rta · mufassall.dtwin.uz/uz/l/consistent-hashing/

← Darsni ochish

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 % N da 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
Yakuniy sahna
66%44%67%66%

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 down

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

D2

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_d

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

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

Xulosa

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'rsatkichBoshidaOxirida
Keshdan topildi (hit)95%72%
Bazadan o'qish250/s1 400/s
Ko'chgan kalitlar0%25%

Qadamlar

  1. Holat Uchta kesh, bitta qoida: hash % 3

    API soniyasiga 5 000 ga yaqin profil o'qiydi.

  2. Muammo To'rtinchi kesh qolgan uchtasini bo'shatadi

    Xotira yetmayapti, to'rtinchi kesh qo'shildi va qoida hash % 4 bo'ldi.

  3. Muammo Har bir miss bazaga tushadi

    Hit rate 95% dan 24% ga tushdi.

  4. Yechim Kalitlarni ham, node'larni ham bitta halqaga qo'yamiz

    Uchta keshga qaytamiz va qoidani o'zgartiramiz.

  5. Yechim Endi yangi node faqat bitta yoyni oladi

    D kesh 0x4CC00000 nuqtaga qo'shildi.

  6. Muammo To'rtta nuqta halqani teng bo'lmagan yoylarga bo'ladi

    Har bir keshda bitta nuqta bo'lsa, yoylar hash'lar kabi tasodifiy chiqadi.

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

  8. Holat Kesh o'lsa, uning kalitlari tarqaladi

    B kesh javob bermay qo'ydi va API uni halqadan olib tashladi.

  9. Xulosa Xulosa

    hash % N N 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.