Shunday qilib, tasavvur qilaylik. Xonada 5 ta mushuk qulflangan va egasini uyg'otish uchun ularning barchasi o'zaro kelishib olishlari kerak, chunki ular faqat beshtasi unga suyanib eshikni ochishlari mumkin. Agar mushuklardan biri Shredingerning mushuki bo'lsa va boshqa mushuklar uning qarori haqida bilmasa, savol tug'iladi: "Ular buni qanday qilishlari mumkin?"
Ushbu maqolada men sizga oddiy so'zlar bilan taqsimlangan tizimlar dunyosining nazariy komponenti va ularning ishlash tamoyillari haqida gapirib beraman. Men Paxosning asosiy g'oyasini ham yuzaki ko'rib chiqaman.
Ishlab chiquvchilar bulutli infratuzilmalardan, turli ma'lumotlar bazalaridan foydalanganda va ko'p sonli tugunlardan iborat klasterlarda ishlaganda, ular ma'lumotlar to'liq, xavfsiz va har doim mavjud bo'lishiga ishonch hosil qiladi. Ammo kafolatlar qayerda?
Aslida, bizda mavjud bo'lgan kafolatlar yetkazib beruvchi kafolatlaridir. Hujjatlarda ular quyidagicha tasvirlangan: "Ushbu xizmat juda ishonchli, u berilgan SLAga ega, xavotir olmang, hamma narsa siz kutganingizdek taqsimlangan holda ishlaydi."
Biz eng yaxshisiga ishonishga moyilmiz, chunki yirik kompaniyalarning aqlli yigitlari bizni hamma narsa yaxshi bo'lishiga ishontirishdi. Biz savol bermaymiz: nima uchun, aslida, bu umuman ishlay oladimi? Bunday tizimlarning to'g'ri ishlashi uchun biron bir rasmiy asos bormi?
Yaqinda bordim va bu mavzudan juda ilhomlangan. Maktabdagi ma'ruzalar kompyuter tizimlari bilan bog'liq bo'lgan narsadan ko'ra ko'proq hisob-kitob darslariga o'xshardi. Lekin biz bilmay har kuni ishlatadigan eng muhim algoritmlar aynan shunday isbotlangan edi.
Aksariyat zamonaviy taqsimlangan tizimlar Paxos konsensus algoritmi va uning turli modifikatsiyalaridan foydalanadi. Eng zo'r narsa shundaki, ushbu algoritmning haqiqiyligi va printsipial jihatdan mavjudligini shunchaki qalam va qog'oz bilan isbotlash mumkin. Amalda, algoritm bulutlardagi juda ko'p sonli tugunlarda ishlaydigan yirik tizimlarda qo'llaniladi.
Keyinchalik muhokama qilinadigan narsalarning engil tasviri: ikkita generalning vazifasiKeling, isinishni ko'rib chiqaylik .
Bizning ikkita armiyamiz bor - qizil va oq. Qamaldagi shaharda oq qo'shinlar joylashgan. A1 va A2 generallari boshchiligidagi qizil qo'shinlar shaharning ikki tomonida joylashgan. Qizillarning vazifasi oq shaharga hujum qilish va g'alaba qozonishdir. Biroq, har bir qizil generalning armiyasi alohida oq armiyadan kichikroq.
Qizillar uchun g'alaba shartlari: oqlar ustidan son jihatdan ustunlikka ega bo'lish uchun ikkala general ham bir vaqtning o'zida hujum qilishlari kerak. Buning uchun A1 va A2 generallari bir-biri bilan kelishib olishlari kerak. Agar hamma alohida hujum qilsa, qizillar mag'lub bo'lishadi.
Kelishuvga erishish uchun A1 va A2 generallari oq shahar hududi orqali bir-birlariga xabarchilar yuborishlari mumkin. Xabarchi ittifoqchi generalga muvaffaqiyatli etib borishi yoki dushman tomonidan tutib olinishi mumkin. Savol: qizil sochli generallar o'rtasida shunday aloqalar ketma-ketligi bormi (messenjerlarni A1 dan A2 ga va aksincha A2 dan A1 ga yuborish ketma-ketligi), bunda ular X soatda hujum qilish to'g'risida kelishib olishlari kafolatlanadi. kafolatlar shuni anglatadiki, ikkala general ham ittifoqchi (boshqa bir general) belgilangan X vaqtida albatta hujum qilishini aniq tasdiqlaydi.
Aytaylik, A1 A2 ga “Bugun yarim tunda hujum qilaylik!” degan xabar bilan xabarchi yubordi. General A1 General A2 tomonidan tasdiqlanmasdan hujum qila olmaydi. Agar A1 dan xabarchi kelgan bo'lsa, General A2 "Ha, bugun oqlarni o'ldiramiz" degan xabarni tasdiqlaydi. Ammo endi general A2 o'z messenjeri kelgan-kelmaganini bilmaydi, hujum bir vaqtning o'zida bo'ladimi-yo'qmi, hech qanday kafolati yo'q. Endi General A2 yana tasdiqlashga muhtoj.
Agar biz ularning muloqotini batafsil tavsiflab beradigan bo'lsak, ma'lum bo'ladiki, qancha xabar almashish sikllari bo'lishidan qat'i nazar, ikkala general ham o'z xabarlarini olganligiga kafolat berishning hech qanday usuli yo'q (agar ikkala messenjer ham ushlanishi mumkin).
Ikki general muammosi ishonchsiz aloqaga ega ikkita tugun mavjud bo'lgan juda oddiy taqsimlangan tizimning ajoyib tasviridir. Bu ularning sinxronlashtirilganligiga 100% kafolatimiz yo'qligini anglatadi. Shunga o'xshash muammolar faqat keyinchalik maqolada kengroq miqyosda muhokama qilinadi.
Biz taqsimlangan tizimlar tushunchasini kiritamiz
Taqsimlangan tizim - bu xabar almashishi mumkin bo'lgan kompyuterlar guruhi (bundan keyin ularni tugunlar deb ataymiz). Har bir alohida tugun qandaydir avtonom ob'ektdir. Tugun vazifalarni mustaqil ravishda bajarishi mumkin, ammo boshqa tugunlar bilan aloqa qilish uchun u xabarlarni yuborishi va qabul qilishi kerak.
Xabarlar qanday aniq amalga oshiriladi, qanday protokollardan foydalaniladi - bu kontekstda bizni qiziqtirmaydi. Taqsimlangan tizimning tugunlari xabarlarni yuborish orqali bir-biri bilan ma'lumot almashishi muhim ahamiyatga ega.
Ta'rifning o'zi unchalik murakkab ko'rinmaydi, lekin biz taqsimlangan tizim biz uchun muhim bo'lgan bir qator atributlarga ega ekanligini hisobga olishimiz kerak.
Tarqalgan tizimlarning atributlari
- Birgalikda - tizimda bir vaqtning o'zida yoki bir vaqtning o'zida sodir bo'ladigan hodisalar ehtimoli. Bundan tashqari, biz ikkita turli tugunlarda sodir bo'ladigan hodisalarni, agar bizda bu hodisalarning aniq tartibiga ega bo'lmasak, bir vaqtning o'zida potentsial deb hisoblaymiz. Lekin, qoida tariqasida, bizda yo'q.
- Global soat yo'q. Global soat yo'qligi sababli bizda voqealarning aniq tartibi yo'q. Oddiy odamlar dunyosida bizda soatlar va vaqt mutlaqo borligiga o'rganib qolganmiz. Taqsimlangan tizimlar haqida gap ketganda hamma narsa o'zgaradi. Hatto o'ta aniq atom soatlari ham driftga ega va ikkita voqeadan qaysi biri birinchi bo'lib sodir bo'lganini ayta olmaydigan vaziyatlar bo'lishi mumkin. Shuning uchun biz ham vaqtga tayanolmaymiz.
- Tizim tugunlarining mustaqil ishlamay qolishi. Yana bir muammo bor: bir narsa noto'g'ri ketishi mumkin, chunki bizning tugunlarimiz abadiy davom etmaydi. Qattiq disk ishlamay qolishi, bulutdagi virtual mashina qayta ishga tushishi, tarmoq miltillashi va xabarlar yo'qolishi mumkin. Bundan tashqari, tugunlar ishlaydigan vaziyatlar bo'lishi mumkin, lekin ayni paytda tizimga qarshi ishlaydi. Muammolarning oxirgi sinfi hatto alohida nom oldi: muammo . Ushbu muammo bilan taqsimlangan tizimning eng mashhur namunasi Blockchain hisoblanadi. Ammo bugun biz ushbu maxsus muammolar sinfini ko'rib chiqmaymiz. Bizni oddiygina bir yoki bir nechta tugun ishlamay qolishi mumkin bo'lgan holatlar qiziqtiradi.
- Tugunlar orasidagi aloqa modellari (xabar almashish modellari).. Biz allaqachon tugunlar xabar almashish orqali aloqa qilishini aniqladik. Ikkita mashhur xabar almashish modeli mavjud: sinxron va asinxron.
Tarqalgan tizimlardagi tugunlar orasidagi aloqa modellari
Sinxron model - biz aniq bilamizki, ma'lum vaqt deltasi mavjud bo'lib, uning davomida xabar bir tugundan boshqasiga yetib borishi kafolatlanadi. Agar bu vaqt o'tgan bo'lsa va xabar kelmagan bo'lsa, biz tugun ishlamay qolgan deb ishonch bilan aytishimiz mumkin. Ushbu modelda bizda taxminiy kutish vaqtlari mavjud.
Asinxron model - asinxron modellarda biz kutish vaqti cheklangan deb hisoblaymiz, ammo bunday vaqt deltasi yo'q, shundan so'ng biz tugun ishlamay qolganiga kafolat bera olamiz. Bular. Tugundan xabarni kutish vaqti o'zboshimchalik bilan uzoq bo'lishi mumkin. Bu muhim ta'rif va biz bu haqda batafsilroq gaplashamiz.
Tarqalgan tizimlarda konsensus tushunchasi
Konsensus tushunchasini rasman aniqlashdan oldin, keling, bizga kerak bo'lgan vaziyatning misolini ko'rib chiqaylik, xususan - Shtat mashinasi replikatsiyasi.
Bizda tarqatilgan jurnal bor. Biz uning izchil bo'lishini va taqsimlangan tizimning barcha tugunlarida bir xil ma'lumotlarni o'z ichiga olishini xohlaymiz. Tugunlardan biri jurnalga yozmoqchi bo'lgan yangi qiymatni o'rganganda, uning vazifasi barcha tugunlarda jurnal yangilanishi va tizim yangi izchil holatga o'tishi uchun ushbu qiymatni boshqa barcha tugunlarga taklif qilishdan iborat. Bunday holda, tugunlar o'zaro kelishib olishlari muhim: barcha tugunlar taklif qilingan yangi qiymat to'g'ri ekanligiga rozi bo'ladi, barcha tugunlar bu qiymatni qabul qiladi va faqat shu holatda har bir kishi yangi qiymatni jurnalga yozishi mumkin.
Boshqacha qilib aytadigan bo'lsak: tugunlarning hech biri tegishli ma'lumotlarga ega ekanligiga e'tiroz bildirmadi va taklif qilingan qiymat noto'g'ri. Tugunlar o'rtasidagi kelishuv va yagona to'g'ri qabul qilingan qiymat bo'yicha kelishuv taqsimlangan tizimda konsensusdir. Keyinchalik, taqsimlangan tizimni konsensusga erishish kafolatlanishiga imkon beruvchi algoritmlar haqida gapiramiz.
Rasmiyroq qilib aytganda, konsensus algoritmini (yoki oddiygina konsensus algoritmini) taqsimlangan tizimni A holatdan B holatga o‘tkazuvchi ma’lum funksiya sifatida belgilashimiz mumkin. Bundan tashqari, bu holat barcha tugunlar tomonidan qabul qilinadi va barcha tugunlar buni tasdiqlashi mumkin. Ma'lum bo'lishicha, bu vazifa birinchi qarashda ko'rinadigan darajada ahamiyatsiz emas.
Konsensus algoritmining xossalari
Konsensus algoritmi tizim mavjudligini davom ettirishi va davlatdan holatga o'tishda bir oz oldinga siljishi uchun uchta xususiyatga ega bo'lishi kerak:
- Shartnoma - barcha to'g'ri ishlaydigan tugunlar bir xil qiymatga ega bo'lishi kerak (maqolalarda bu xususiyat xavfsizlik xususiyati deb ham ataladi). Hozirda ishlayotgan barcha tugunlar (boshqalari bilan aloqani yo'qotmagan yoki yo'qotmagan) kelishuvga kelishi va yakuniy umumiy qiymatni qabul qilishi kerak.
Bu erda biz ko'rib chiqayotgan taqsimlangan tizimdagi tugunlar rozi bo'lishni xohlashini tushunish muhimdir. Ya'ni, biz hozir biror narsa shunchaki muvaffaqiyatsiz bo'lishi mumkin bo'lgan tizimlar haqida gapiramiz (masalan, ba'zi tugunlar muvaffaqiyatsiz tugadi), ammo bu tizimda boshqalarga qarshi ataylab ishlaydigan tugunlar yo'q (Vizantiya generallarining vazifasi). Ushbu xususiyat tufayli tizim izchil bo'lib qoladi.
- Butunlik - agar barcha to'g'ri ishlaydigan tugunlar bir xil qiymatni taklif qilsa v, ya'ni har bir to'g'ri ishlaydigan tugun ushbu qiymatni qabul qilishi kerak v.
- Bekor qilish - barcha to'g'ri ishlaydigan tugunlar oxir-oqibat ma'lum bir qiymatga ega bo'ladi (jonlilik xususiyati), bu algoritmga tizimda muvaffaqiyatga erishish imkonini beradi. To'g'ri ishlaydigan har bir tugun ertami-kechmi yakuniy qiymatni qabul qilishi va uni tasdiqlashi kerak: "Men uchun bu qiymat to'g'ri, men butun tizim bilan roziman."
Konsensus algoritmi qanday ishlashiga misol
Algoritmning xususiyatlari to'liq aniq bo'lmasligi mumkin. Shuning uchun biz eng oddiy konsensus algoritmi sinxron xabar almashish modeliga ega tizimda qanday bosqichlardan o'tishini misol bilan ko'rsatamiz, unda barcha tugunlar kutilganidek ishlaydi, xabarlar yo'qolmaydi va hech narsa buzilmaydi (bu haqiqatan ham sodir bo'ladimi?).
- Hammasi turmush qurish taklifi bilan boshlanadi (Taklif qilish). Faraz qilaylik, mijoz “1-tugun” deb nomlangan tugunga ulanib, tranzaktsiyani boshladi, tugunga yangi qiymat o'tkazdi - O. Bundan buyon biz “1-tugun”ni chaqiramiz. taklif qilmoq. Taklifchi sifatida "1-tugun" endi butun tizimni yangi ma'lumotlarga ega ekanligi haqida xabardor qilishi kerak va u boshqa barcha tugunlarga xabarlar yuboradi: "Mana! "O" ma'nosi menga keldi va men uni yozmoqchiman! Iltimos, jurnalingizga "O" ni ham yozib qo'yishingizni tasdiqlang."
- Keyingi bosqich - taklif qilingan qiymat uchun ovoz berish (Ovoz berish). Bu nima uchun? Boshqa tugunlar so'nggi ma'lumotlarni olgan bo'lishi mumkin va ular xuddi shu tranzaksiya bo'yicha ma'lumotlarga ega.
"1-tugun" o'z taklifini yuborganda, boshqa tugunlar o'zlarining jurnallarida ushbu hodisa bo'yicha ma'lumotlarni tekshiradilar. Agar qarama-qarshiliklar bo'lmasa, tugunlar e'lon qiladi: "Ha, menda bu voqea uchun boshqa ma'lumotlar yo'q. "O" qiymati biz loyiq bo'lgan eng so'nggi ma'lumotdir."Boshqa har qanday holatda, tugunlar "1-tugun" ga javob berishi mumkin: "Eshiting! Menda ushbu tranzaksiya bo'yicha so'nggi ma'lumotlar bor. "O" emas, balki yaxshiroq narsa."
Ovoz berish bosqichida tugunlar bir qarorga kelishadi: yoki ularning barchasi bir xil qiymatni qabul qiladi yoki ulardan biri qarshi ovoz beradi, bu uning so'nggi ma'lumotlarga ega ekanligini ko'rsatadi.
- Agar ovoz berish bosqichi muvaffaqiyatli o'tgan va hamma yoqlagan bo'lsa, tizim yangi bosqichga o'tadi - Qiymatni qabul qilish. "1-tugun" boshqa tugunlardan barcha javoblarni to'playdi va hisobot beradi: "Hamma "O" qiymatiga rozi bo'ldi! Endi men rasman e'lon qilamanki, "O" bizning yangi ma'nomiz, hamma uchun bir xil! Buni kichik kitobingizga yozing, unutmang. Buni jurnalingizga yozing!”
- Qolgan tugunlar "O" qiymatini yozib olganliklarini tasdiqlaydi (Qabul qilingan); bu vaqt ichida hech qanday yangi narsa kelmadi (ikki fazali majburiyatning bir turi). Ushbu muhim voqeadan so'ng, biz taqsimlangan tranzaksiya yakunlandi deb hisoblaymiz.
Shunday qilib, oddiy holatda konsensus algoritmi to'rt bosqichdan iborat: taklif qilish, ovoz berish (ovoz berish), qabul qilish (qabul qilish), qabul qilishni tasdiqlash (qabul qilingan).
Agar biron bir qadamda biz kelishuvga erisha olmasak, algoritm taklif qilingan qiymatni tasdiqlashdan bosh tortgan tugunlar tomonidan taqdim etilgan ma'lumotlarni hisobga olgan holda qayta boshlanadi.
Asinxron tizimda konsensus algoritmi
Bungacha hamma narsa silliq edi, chunki biz sinxron xabar almashish modeli haqida gapirgan edik. Ammo biz bilamizki, zamonaviy dunyoda biz hamma narsani asinxron qilishga odatlanganmiz. Shunga o'xshash algoritm asinxron xabar almashish modeliga ega tizimda qanday ishlaydi, bu erda tugunning javobini kutish vaqti o'zboshimchalik bilan uzoq bo'lishi mumkin deb hisoblaymiz (Aytgancha, tugunning ishlamay qolishi ham misol sifatida ko'rib chiqilishi mumkin. tugun o'zboshimchalik bilan uzoq vaqt davomida javob berishi mumkin).
Endi biz konsensus algoritmi printsipial jihatdan qanday ishlashini bilganimizdan so'ng, hozirgacha buni amalga oshirgan qiziquvchan o'quvchilar uchun savol: asinxron xabar modeliga ega N tugunlar tizimidagi qancha tugunlar muvaffaqiyatsiz bo'lishi mumkin, shunda tizim konsensusga erisha oladi?
To'g'ri javob va asos spoyler ortida.To'g'ri javob: 0. Agar asinxron tizimdagi bitta tugun ham ishlamay qolsa, tizim konsensusga erisha olmaydi. Ushbu bayonot FLP teoremasida isbotlangan, ma'lum doiralarda yaxshi ma'lum (1985, Fisher, Linch, Paterson, maqolaning oxiridagi asl nusxaga havola): "Hech bo'lmaganda bitta tugun ishlamay qolsa, taqsimlangan konsensusga erishishning mumkin emasligi. ”.
Bolalar, bizda muammo bor, biz hamma narsa asinxron bo'lishiga o'rganib qolganmiz. Va bu erda. Qanday qilib yashashni davom ettirish kerak?
Biz faqat nazariya, matematika haqida gapirgan edik. Matematik tildan bizning tilimizga – muhandislik tiliga tarjima qilinganda “konsensusga erishib bo‘lmaydi” degani nimani anglatadi? Bu shuni anglatadiki, "har doim ham erishib bo'lmaydi", ya'ni. Konsensusga erishib bo'lmaydigan holat mavjud. Bu qanday holat?
Bu yuqorida tavsiflangan jonlilik xususiyatining buzilishidir. Bizda umumiy kelishuv yo'q va agar biz barcha tugunlardan javob olmasak, tizim taraqqiyotga erisha olmaydi (cheklangan vaqt ichida yakunlay olmaydi). Chunki asinxron tizimda bizda oldindan aytib bo'ladigan javob vaqtimiz yo'q va biz tugunning ishdan chiqqanligini yoki javob berish uchun uzoq vaqt ketayotganini bila olmaymiz.
Lekin amalda biz yechim topa olamiz. Bizning algoritmimiz muvaffaqiyatsizlikka uchragan taqdirda uzoq vaqt ishlashiga imkon bering (potentsial u cheksiz ishlashi mumkin). Ammo aksariyat hollarda, ko'pchilik tugunlar to'g'ri ishlayotgan bo'lsa, biz tizimda muvaffaqiyatga erishamiz.
Amalda biz qisman sinxron aloqa modellari bilan shug'ullanamiz. Qisman sinxroniya quyidagicha tushuniladi: umumiy holatda bizda asinxron model mavjud, ammo ma'lum bir vaqtning "global barqarorlashuv vaqti" ning ma'lum bir kontseptsiyasi rasmiy ravishda kiritilgan.
Vaqtning bu lahzasi uzoq vaqt davomida kelmasligi mumkin, lekin bir kun kelishi kerak. Virtual uyg'otuvchi soat jiringlaydi va shu paytdan boshlab biz xabarlar keladigan vaqt deltasini taxmin qilishimiz mumkin. Shu paytdan boshlab tizim asinxrondan sinxronga o'tadi. Amalda biz aynan shunday tizimlar bilan shug'ullanamiz.
Paxos algoritmi konsensus masalalarini hal qiladi
qisman sinxron tizimlar uchun konsensus muammosini hal qiluvchi algoritmlar oilasi boʻlib, baʼzi tugunlarning ishlamay qolishi ehtimolini hisobga olgan holda. Paxos muallifi . U 1989 yilda algoritmning mavjudligi va to'g'riligini rasmiy isbotlashni taklif qildi.
Ammo dalil ahamiyatsiz bo'lib chiqdi. Algoritmni tavsiflovchi birinchi nashr faqat 1998 yilda chiqarilgan (33 bet). Ma'lum bo'lishicha, buni tushunish juda qiyin edi va 2001 yilda 14 sahifadan iborat maqolaning izohi nashr etildi. Nashrlar hajmi konsensus muammosi umuman oddiy emasligini va bunday algoritmlar ortida eng aqlli odamlarning katta hajmdagi ishi yotganligini ko'rsatish uchun berilgan.
Qizig'i shundaki, Lesli Lemportning o'zi o'z ma'ruzasida ta'kidlaganidek, ikkinchi tushuntirish maqolasida bitta bayonot, bitta satr (u qaysi birini aniqlamadi), uni turli yo'llar bilan izohlash mumkin. Va shuning uchun ko'p sonli zamonaviy Paxos ilovalari to'liq ishlamaydi.
Paxos ishini batafsil tahlil qilish uchun bir nechta maqola kerak bo'ladi, shuning uchun men algoritmning asosiy g'oyasini juda qisqacha etkazishga harakat qilaman. Mening maqolamning oxiridagi havolalarda siz ushbu mavzuni yanada chuqurroq o'rganish uchun materiallarni topasiz.
Paxosdagi rollar
Paxos algoritmida rollar tushunchasi mavjud. Keling, uchta asosiy narsani ko'rib chiqaylik (qo'shimcha rollar bilan o'zgartirishlar mavjud):
- Taklifchilar (shuningdek, atamalar ishlatilishi mumkin: rahbarlar yoki koordinatorlar). Bular foydalanuvchidan qandaydir yangi qiymatni o'rganadigan va etakchi rolini o'z zimmasiga oladigan bolalardir. Ularning vazifasi yangi qiymat bo'yicha takliflar raundini ishga tushirish va tugunlarning keyingi harakatlarini muvofiqlashtirishdir. Bundan tashqari, Paxos ma'lum vaziyatlarda bir nechta etakchilarning mavjudligiga imkon beradi.
- Qabul qiluvchilar (saylovchilar). Bu ma'lum bir qiymatni qabul qilish yoki rad etish uchun ovoz beradigan tugunlar. Ularning roli juda muhim, chunki qaror ularga bog'liq: konsensus algoritmining keyingi bosqichidan keyin tizim qanday holatga o'tadi (yoki yo'q).
- O'quvchilar. Tizim holati o'zgarganda yangi qabul qilingan qiymatni oddiygina qabul qiladigan va yozadigan tugunlar. Ular qaror qabul qilmaydi, faqat ma'lumotlarni oladi va oxirgi foydalanuvchiga berishi mumkin.
Bitta tugun turli vaziyatlarda bir nechta rollarni birlashtirishi mumkin.
Kvorum tushunchasi
Bizda tizim mavjud deb taxmin qilamiz N tugunlar Va ulardan maksimal F tugunlar muvaffaqiyatsiz bo'lishi mumkin. Agar F tugunlari muvaffaqiyatsiz bo'lsa, bizda hech bo'lmaganda bo'lishi kerak 2F+1 qabul qiluvchi tugunlar.
Bu biz doimo, hatto eng yomon holatda ham, to'g'ri ishlaydigan "yaxshi" tugunlarning ko'pchiligiga ega bo'lishimiz uchun kerak. Ya'ni F+1 kelishilgan "yaxshi" tugunlar va yakuniy qiymat qabul qilinadi. Aks holda, bizning turli mahalliy guruhlarimiz turli xil ma'nolarga ega bo'lib, o'zaro kelisha olmaydigan holat bo'lishi mumkin. Shunday ekan, ovoz berish uchun bizga mutlaq ko‘pchilik kerak.
Paxos konsensus algoritmi qanday ishlashi haqida umumiy fikr
Paxos algoritmi ikkita katta bosqichni o'z ichiga oladi, ular o'z navbatida har biri ikki bosqichga bo'lingan:
- 1a bosqich: tayyorlang. Tayyorgarlik bosqichida yetakchi (taklifchi) barcha tugunlarni xabardor qiladi: “Biz yangi ovoz berish bosqichini boshlaymiz. Bizda yangi tur. Ushbu turning soni n. Endi ovoz berishni boshlaymiz”. Hozircha u shunchaki yangi tsikl boshlanishi haqida xabar beradi, lekin yangi qiymat haqida xabar bermaydi. Ushbu bosqichning vazifasi yangi turni boshlash va uning noyob raqamini hammaga etkazishdir. Davra raqami muhim, u barcha oldingi rahbarlarning oldingi ovoz berish raqamlaridan kattaroq qiymat bo'lishi kerak. Aynan dumaloq raqam tufayli tizimdagi boshqa tugunlar rahbar ma'lumotlari qanchalik yaqinda ekanligini tushunishadi. Ehtimol, boshqa tugunlar ancha keyingi turlardagi ovoz berish natijalariga ega bo'lib, rahbarga u zamondan orqada qolganini aytishadi.
- 1b-bosqich: Va'da. Qachon qabul qiluvchi tugunlar yangi ovoz berish bosqichining raqamini olgan bo'lsa, ikkita natija bo'lishi mumkin:
- Yangi ovozning n soni qabul qiluvchi ishtirok etgan oldingi ovozlar sonidan kattaroqdir. Keyin qabul qiluvchi yetakchiga n dan past raqam bilan boshqa ovoz berishda qatnashmasligi haqida va'da yuboradi. Agar qabul qiluvchi biror narsa uchun ovoz bergan bo'lsa (ya'ni, u ikkinchi bosqichda qandaydir qiymatni qabul qilgan bo'lsa), u o'z va'dasiga qabul qilingan qiymatni va ishtirok etgan ovozlar sonini qo'shadi.
- Aks holda, agar qabul qiluvchi ko'proq ovoz berish haqida allaqachon bilsa, u tayyorgarlik bosqichini e'tiborsiz qoldirishi va etakchiga javob bermasligi mumkin.
- 2a bosqich: Qabul qiling. Rahbar kvorumdan javob kutishi kerak (tizimdagi ko'pchilik tugunlar) va agar kerakli miqdordagi javoblar olinsa, unda voqealarni rivojlantirish uchun ikkita variant mavjud:
- Ba'zi qabul qiluvchilar allaqachon ovoz bergan qiymatlarni yuborishdi. Bunday holda, etakchi maksimal raqam bilan ovoz berishdan qiymatni tanlaydi. Keling, bu qiymatni x deb nomlaymiz va u barcha tugunlarga quyidagi xabarni yuboradi: “Qabul qilaman (n, x)”, bu erda birinchi qiymat o'zining Taklif qilish bosqichidagi ovoz berish raqami, ikkinchi qiymat esa hamma to'plagan narsa, ya'ni biz aslida ovoz beradigan qiymat.
- Agar qabul qiluvchilarning hech biri biron bir qiymatni yubormagan bo'lsa, lekin ular shunchaki ushbu turda ovoz berishga va'da berishgan bo'lsa, etakchi ularni o'z qiymati uchun ovoz berishga taklif qilishi mumkin, u birinchi navbatda etakchi bo'lgan qiymat uchun. Keling, uni y deb ataymiz. U barcha tugunlarga xabar yuboradi: "Qabul qiling (n, y)", oldingi natijaga o'xshash.
- 2b-bosqich: Qabul qilingan. Bundan tashqari, qabul qiluvchi tugunlar rahbardan "Qabul qilaman (...)" xabarini olgandan so'ng, u bilan rozi bo'lishadi (barcha tugunlarga yangi qiymatga rozi ekanligi to'g'risida tasdiqlashni yuboring), agar ular ba'zi (boshqa) va'da qilmagan bo'lsalar ) ) Rahbari tur raqami bilan ovoz berishda ishtirok etadi n' > n, aks holda ular tasdiqlash so'roviga e'tibor bermaydilar.
Agar tugunlarning aksariyati etakchiga javob bergan bo'lsa va ularning barchasi yangi qiymatni tasdiqlagan bo'lsa, unda yangi qiymat qabul qilingan hisoblanadi. Xayr! Agar ko'pchilikka erishilmasa yoki yangi qiymatni qabul qilishdan bosh tortgan tugunlar bo'lsa, unda hamma narsa qaytadan boshlanadi.
Paxos algoritmi shunday ishlaydi. Ushbu bosqichlarning har biri juda ko'p nozikliklarga ega, biz deyarli har xil turdagi nosozliklarni, bir nechta rahbarlarning muammolarini va boshqa ko'p narsalarni ko'rib chiqmadik, ammo ushbu maqolaning maqsadi o'quvchini yuqori darajada taqsimlangan hisoblash dunyosi bilan tanishtirishdir.
Shuni ham ta'kidlash kerakki, Paxos bu turdagi yagona emas, boshqa algoritmlar ham mavjud, masalan, , lekin bu boshqa maqola uchun mavzu.
Qo'shimcha o'rganish uchun materiallarga havolalar
Boshlang'ich darajasi:
- , Preethi Kasireddy, Medium-dagi blog maqolasi
- , Adi Kancherla, Medium-dagi blog maqolasi
- , Ittai Abraham, blog
- , Ittai Abraham, blog maqolasi
Lesli Lamport darajasi:
- , Fisher, Linch va Paterson, tadqiqot maqolasi, 1985 yil
- , Leslie Lamport, tadqiqot maqolasi, 1998 yil
- , Leslie Lamport, tadqiqot maqolasi, 2001 yil
Manba: www.habr.com