Consistent hashing nima va qanday ishlaydi?
Assalamu Alaykum bugun System Designdagi asosiy mavzulardan biri consistent hashingni ko'rib chiqamiz. Bu maqoladan oldin Database sharding maqolasini o'qishni tavsiya qilaman.
Unda qani boshladik :).
Muammo nimada ?
Katta darajadagi distributed sistemalarda ma'lumot har doim ham bitta serverga sig'maydi, shuning uchun biz ma'lumotlarni turli serverlarga bo'lib tashlashimiz kerak hamda bu ularga teng miqdorda tushishi kerak (bitta server ko'p load sababli o'chib qolmasligi uchun).
Yechim (Mod)
Ma'lumotni tarqatishni oson usuli bu mod orqali serverni aniqlash masalan Hash(key) mod NN bu yerda serverlar soni. hash(key) bu serverning hash kodi orqali.
Ammo bu usulda bir muammo bor ya'ni u serverlar soniga to'g'ridan to'g'ri bog'liq , va uni o'zgarishi serverlardagi ma'lumotlar qayta distributsiya(ya'ni tarqatilishiga) olib kelishi mumkin.
Keling buni bir misol orqali ko'rib chiqamiz, tassavur qiling siz katta trafiklik web dastur qurmoqdasiz, tepada aytganimizdek loadni hamma serverga bir xil tushirishimiz kerak . Buni modga asoslangan balancer orqali qilishni boshladik .
Sizning 4ta server bor va requestlar(ip address yoki boshqa narsa) hashlangandan keyingi key mod orqali bo'linganda qoldiq biz so'rov yuboradigan request server raqami bo'ladi . Ushbu user requestlari har doim shu serverga yo'naltirishi sessiyani saqlab qolish yordam beradi.
Hammasi yaxshi edi ammo dasturni kengaytirish (scale) vaqti keldi.Tepadagi usul serverlar soni bir xil qolganida juda yaxshi ishlaydi ammo yangi server qo'shish kerak bo'lsa yoki biror server qulasa juda ko'p narsa o'zgarib ketadi . Keling har bir holatni ko'rib chiqamiz.
1-Holat (Serverni o'chib qolishi)
Bir data markazida to'k o'chdi va sizdagi shu markazdagi serveringiz ishlamay qoldi.
Faqatgina bitta server o'chgan bo'lsa ham, foydalanuvchilarni juda ko'p qismi boshqa serverga qayta taqsimlandi va natijada :
Sessiya Yo'qolishi:Aktiv foydalanuvchilar uzilib qoldi yoki dasturdan chiqarib yuborildi.
Cache invalidation:Cachelangan ma'lumot keraksiz bo'lib qoldi , databazada load ko'paydi .
Performance pasayishi:Load qayta teng taqsimlanmadi va sistema bir butun sifatida performance tushishi mumkin.
2- Holat (Server qo'shilishi)
Dasturga bo'lgan talab oshganligi uchun biz scale up qilamiz ya’ni yangi server qo'shamiz. Shunda hash funksiya 4 ega emas 5 ga bo'lishini boshlaydi .
Bu birgina oddiygina o'zgarish oldingi bog'lanishlarni butunlay o'zgartirib tashladi va juda ko'p foydalanuvchilar qayta taqsimlandi .
Bu esa ehtimoliy qulashni keltirib chiqarishi mumkin.
Yechim => Consistent hashing
Consistent hashing bunga scalable va samarali yechimtaklif qiladi , ya’ni qachonki server scale up yoki down bo'lsa foydlanuvchilarning faqatgina bir qismi (aynan shu serverga aloqador) qayta taqsimlanadi .
Bu ayniqsa dynamic(serverlar ko'p scale up and down bo'ladigan) holatda ishlaydigan dasturlar uchun juda yaxshi performance ko'rsatadi .
Consistent hashing qanday ishlaydi ?
Consistent hashing bu distributed hashing uslubi , ma'lumotni bir necha serverlar o'rtasida teng taqsimlashga yordam beradi .
U circular hash ring yani bir biriga to'liq ulangan oraliqlardan foydalanadi.
Hamma node(server, databaza) va key (request, ma'lumotlar)lar o'sha ringdagi pozitsiyasi topiladi (hash funksiyadan foydalangan holda).
Modulli hashingdan farqli o'laroq , consistent hashingda yangi server qo'shish yoki olib tashlash juda kam qismdagi keylar qayta taqsimlanadi, bu narsa uni samarali qiladi.
Consistent hashingda , agar nodelar soni o'zgarsa faqatgina
k/nkeylar qayta taqsimlanadi .k— umumiy keylar soni ,n— umumiy nodelar soni.
Hash Ring yaratilishi
Keylarni hash(key) mod N orqali taqsimlash o'rniga , key va serverlarni circular hash ring ichiga joylashtiramiz.
Hash space odatda ishlatilingan hash funksiya natijalari oralig'iga qarab belgilanadi ammo biz uni 0 dan 99 gacha deb hisoblaylik . Bu circular bo'lganligi uchun katta qiymatlar qaytib kelib shu hash ringga tushadi.
Serverlarni Ringga joylashtirish
Har bir server (node)
Hash(server_id)natijasiga qarab ringdagi pozitsiyasi belgilanadi.
Keylar tegishli serverni aniqlash
Keyning ringdagi pozitsiyasi
Hash(key)orqali aniqlanadi. Masalan:Hash(IP Address)Key qaysi serverga tegishli ekanligini bilish uchun soat yo'nalishi bo'ylab keyingi servergacha boramiz. Ushbu server bizga javobgar bo'ladi.
Note: Agarda key server nodening aniq pozitsiyasiga tushsa demak key ushbu nodega tegishli bo'ladi.
Yangi server qo'shish
Biz yangi S5 serverni qo'shishimiz kerak.
S5server pozitsiyasiS4vaS1pozitsiyasi orasida joylashgan75–90 orasidagi barcha requestlarga endi
S1emasS5server javob beradi
Tepadagi misol, consistent hashing yangi server qo'shganda qanchalik samarali ekanini qayta taqsimlangan keylar minimalligi bilan isbotlab berdi.
Serverni olib tashlash
Qachon server o'chib qolsa masalan S2 u sistemadan olib tashlanadi :
Oldingi
S2serverga taqsimlangan barcha keylar endiS3server bo'yniga tushadi.Faqatgina
S2serverga kelayotgan so'rovlar qayta taqsimlandi , qolganlari o'zgarmasdan qoldi.
Bu odatiy hashingdan ko'ra bizga minimal ma'lumot o'zgarishini taqdim etadi .
Virtual Nodelar
Tepadagi holatlarda ko'rganimizdek server o'chgandan so'ng uni qismi boshqa bir serverga to'liqligicha tushdi bu esa teng bo'lmagan loadni olib keladi va u ham qulasa asta sekin boshqa serverlar ham qulashni boshlaydi load ko'payganligi uchun . Bu holatlar qachon kelib chiqadi :
Serverlar soni juda kam bo'lganda.
Ba'zi serverlar o'chishi sistemada hot spot yani ko'p loadlik qismlar yaralishiga sabab bo'ladi.
Server o'chirilishi undagi load to'satdan uni yonidagi serverga to'liqligicha o'tadi.
Bu narsalarni oldini olish uchun biz virtual nodelardanfoydalanamiz. Bu uslub bizga load teng taqsimlanishi hamda kelib chiqishi mumkin bo'lgan xatoliklarni oldini olishga yordam beradi.
Virtual Node qanday ishlaydi ?
Tepada aytganimizdek bizga juda ko'p serverlar kerak ammo bizda atigi 4 ta borku nima qilamiz. Har bir serverni ringda bitta emas bir necha joyga joylashtiramiz.
Har bir server ringda bir necha joyga hashlanib joylashtiriladi.
So'rov key hashlanganda unga javobgar node doimgidek soat yo'nalishi bo'ylab aniqlanadi.
Va node topilgandan so'ng u bu virtual node qaysi serverga tegishliligi topilib u hamma so'rovlarga javobgar bo'ladi.
Example
Tepadagi rasmdan ko'rsak, keling S3 server o'chib qolsin.
Ko'rib turganingizdek qayta taqsimlangan keylar serverlar o'rtasida deyarli teng taqsimlandi.
Note: Haqiqiy dasturlarda nodelar soni juda ko'p bo'ladi.
Consistent hashing Dynamo DB orqali tanilgan va hozirda Cassandra and ScyllaDB bundan tashqari Redis va juda ko'p CDNlarda ishlatilinadi.
Xulosa
Xulosa qilib aytadigan bo'lsak consistent hashing distributed sistemalarda biror yangi server qo'shilsa yoki o'chib qolsa faqatgina u javobgar bo'lgan qism qayta taqsimlanishiga yordam bergan holda performanceni ko'tarishga sabab bo'ladi. Qayta taqsimlangan ma'lumotlar serverlar orasida teng taqsimlanishi uchun biz virtual nodelar usulidan foydalanamiz.