Taqsimlangan algoritmlar va tizimlar

4-laboratoriya ishi
Taqsimlangan tizimlarda konsensus: Raft algoritmi
Nega Paxos emas
Paxos algoritmi 1990-yilda Lesli Lambert (LaTeX-dagi “La”, hozir Microsoft Research-da) tomonidan taklif qilingan xabarga asoslangan izchillik algoritmidir. Algoritmni tushunish qiyin va dastlab odamlarning e'tiborini tortmaganligi sababli, Lamport sakkiz yil o'tgach, 1998 yilda ACM Transactions on Computer Systems tomonidan qayta nashr etildi (The Part-TimeParliament). Biroq, paxos algoritmi hali ham jiddiy qabul qilinmagan. 2001 yilda Lamport hamkasblari uning hazil tuyg'usini qabul qila olmasligini his qildi, shuning uchun u buni oson qabul qilinadigan shaklda qayta ishlab chiqdi (Paxos MadeSimple). Lamportning Paxos algoritmi uchun zaif tomoni borligini ko'rish mumkin. So'nggi yillarda Paxos algoritmining keng qo'llanilishi ham taqsimlangan konsensus algoritmlarida muhim o'rnini isbotladi. 2006 yilda uchta Google maqolasida "bulut" belgilari topilgan. Chubby Lock xizmati Paxos-dan Chubby Cell konsensus algoritmi sifatida foydalangan va o'shandan beri Paxos mashhurligi keskin oshdi. Lamportning o'zi, uning blogi, 9 yil davomida ushbu algoritmni nashr qilishning barcha nozik tomonlarini tasvirlab beradi.

"Faqat bitta konsensus protokoli mavjud va bu Paxos - boshqa barcha yondashuvlar Paxosning buzilgan versiyalari." - mualliflar

"NSDI hamjamiyatining nopok siri shundaki, ko'pi bilan besh kishi Paxosning har bir qismini haqiqatan ham tushunadi ;-)." -NSDI sharhlovchisi

Ushbu maqolaning qahramoni Raftga nazar tashlaydigan bo'lsak, "InSearch of an Consensus Algoritm tushunarli" o'z rivojlanishining boshidanoq muallif tushunarlilikni eng yuqori mezon sifatida ko'rib chiqdi, bu qaror qabul qilishning ko'plab variantlarida o'z aksini topdi.

muammoning tavsifi
Tarqalgan tizimlarda tugunlarning o'zaro ta'sirining ikkita modeli mavjud: umumiy xotira va xabar uzatish. Xabarni uzatish modelining taqsimlangan tizimiga asoslanib, quyidagi xatolar muqarrar ravishda yuzaga keladi: jarayon sekin bo'lishi, qulashi va qayta ishga tushishi mumkin, xabar kechiktirilishi, yo'qolishi va takrorlanishi mumkin.

Oddiy stsenariy: taqsimlangan ma'lumotlar bazasi tizimida, agar har bir tugunning boshlang'ich holati bir xil bo'lsa va har bir tugun bir xil operatsiyalar ketma-ketligini bajarsa, ular nihoyat izchil holatni olishlari mumkin. Har bir tugun ko'rsatmalarning bir xil ketma-ketligini bajarishini ta'minlash uchun har bir tugun tomonidan ko'rilgan ko'rsatmalar izchil bo'lishini ta'minlash uchun har bir ko'rsatma uchun "mustahkamlik algoritmi" ishga tushirilishi kerak. Umumiy konsensus algoritmi ko'plab stsenariylarda qo'llanilishi mumkin va taqsimlangan hisoblashda muhim masaladir. 1980-yillardan beri konsensus algoritmlari bo'yicha tadqiqotlar to'xtamadi.

5-rasm. Replikatsiya qilingan davlat mashinasining arxitekturasi

Raft algoritmi yuqoridagi rasmda ko'rsatilganidek, ushbu turdagi muammolarni "Replikatsiya qilingan holat mashinasi" ga aylantiradi.Har bir server mahalliy davlat mashinasi tomonidan ketma-ket bajarish uchun foydalanuvchi buyruqlari jurnalini yuritadi. Shubhasiz, "Replicated State Machine" ning izchilligini ta'minlash uchun biz faqat "ReplicatedLog" ning izchilligini ta'minlashimiz kerak.

Algoritmning tavsifi
Umuman olganda, taqsimlangan muhitda kelishuvga ikki yo'l bilan erishish mumkin:
1. Simmetrik, yetakchisiz
Barcha serverlar teng va mijoz istalgan server bilan o'zaro aloqada bo'lishi mumkin
2. Asimmetrik, yetakchiga asoslangan
Istalgan vaqtda bitta va bitta server qaror qabul qilish huquqiga ega va mijoz faqat rahbar bilan muloqot qiladi.
Raftning "Aniqlik uchun dizayn" algoritmi ikkinchisini quyidagi fikrlarga asoslanib qabul qiladi:
1. Muammoning buzilishi: Oddiy ishlash va rahbar o'zgarishi
2. Soddalashtirilgan operatsiya: Oddiy ishlashda nizolar yo'q
3. Lidersiz yondashuvlarga qaraganda samaraliroq
asosiy tushuncha
Server davlatlari
Raft algoritmi serverni uchta rolga ajratadi:
1. Rahbar
Mijoz bilan muloqot qilish va jurnalni takrorlash uchun mas'ul, bir vaqtning o'zida tizimda 1 tadan ko'p bo'lmagan
2.Izdosh
RPC so'roviga passiv javob bering, hech qachon RPC so'rovini faol ravishda boshlamang
3. nomzod
Kuzatuvchidan Liderga oraliq o'tish holati

2-rasm Server holati
Shartlar
Hammamizga ma'lumki, taqsimlangan muhitda "vaqt sinxronizatsiyasi"ning o'zi katta muammo, ammo "muddati o'tgan ma'lumot" ni aniqlash uchun vaqt haqidagi ma'lumot muhim ahamiyatga ega. Ushbu muammoni hal qilish uchun Raft vaqtni alohida qismlarga ajratadi, bu esa o'ziga xos "mantiqiy vaqt" sifatida qaralishi mumkin. Quyida ko'rsatilganidek:
1. Bir muddatda 1 nafardan ortiq menejer bo'lishi mumkin emas.
2. Saylovning muvaffaqiyatsizligi sababli ma’lum muddat davomida yetakchining yo‘qligi.
3. Har bir Server joriyTermni mahalliy darajada saqlaydi

3-rasm Shartlar
Heartbeats va Timeout
1. Barcha serverlar qul sifatida ishga tushadi va saylov taymerini ishga tushiradi.
2. Izdoshi rahbar yoki nomzoddan RPC olishni kutadi.
3. Rahbar izdoshlarni saylov taymerini qayta o'rnatish uchun Heartbeat-ni efirga uzatishi kerak.
4. Agar kuzatuvchini tanlash taymerining muddati tugasa, yetakchi halokatga uchradi deb faraz qiling va saylovni boshlang.
Leader election
Joriy muddatni o'z-o'zidan oshiring, Obunachidan Nomzodga aylantiring, ovoz berilgan For o'zini o'rnating, RequestVote RPC-ni parallel ravishda ishga tushiring va quyidagi shartlardan biri bajarilmaguncha urinib ko'ring:
1. Server ovozlarining yarmidan ko‘pini oling, yetakchi bo‘ling va “Heartbeat”ni efirga uzating
2. Yuridik rahbardan RPC AppendEntries-ni oling va uni Followerga aylantiring
3. Saylov muddati tugadi, server saylovi muvaffaqiyatli o'tmadi, joriy muddat o'z-o'zidan ko'tariladi va qayta saylanadi
Qo'shimcha tafsilotlar:

1. Nomzod ovoz berish natijalarini kutayotganda, u boshqa yetakchilardan RPC AppendEntries olishi mumkin. Agar Rahbarning Muddati mahalliy amaldagi Muddatdan kam bo'lmasa, u holda Rahbarning shaxsi tan olinadi va tashabbus Kuzatuvchiga tushadi; aks holda, nomzodning shaxsi saqlanib qoladi va ovoz berish natijasi davom etadi.

2. Nomzod saylovlarda yaxshi natija ko‘rsatmaydi va boshqa yetakchilardan RPC ni olmaydi.Bu holat odatda bir vaqtning o‘zida bir nechta tugunlar bir vaqtning o‘zida saylovlarni boshlaganida (bo‘lingan ovoz berishda ko‘rsatilgandek) va oxir-oqibat har bir nomzodning vaqti tugashi bilan yuzaga keladi. Mojarolarni kamaytirish uchun bu yerda “tasodifiy chiqish” strategiyasi qabul qilinadi: har bir nomzod saylov taymerini (tasodifiy qiymat) qayta ishga tushiradi, bu esa mojarolar ehtimolini sezilarli darajada kamaytiradi.

4-rasm Jurnalning tuzilishi