|
3-laboratoriya ishi
Taqsimlangan tizimlarda konsensus: Paxos algoritmi
Nima uchun taqsimlangan konsensus kerak va u nima?
Paxos konsensus algoritmi
Paxos - bu taqsimlangan tizimlarda konsensusga erishish uchun foydalaniladigan asosiy algoritmlar oilasi.Konsensus jarayoni tugunlar guruhida kelishilgan natijaga erishishdan iborat. Tugunlar xatoga yo'l qo'yishi va aloqa xabarlari yo'qolishi mumkinligi sababli, konsensusga erishish qiyinroq jarayondir.
Paxos algoritmining taxminlari
Protsessorlar (tugunlar deb tushunish mumkin)
Protsessor har qanday tezlikda ishlaydi
Protsessor noto'g'ri bo'lishi mumkin
Protsessor ishlamay qolgandan so'ng, u qayta sozlanadi va tarmoqqa qaytariladi.
Ishlovchi yolg'on gapirmaydi yoki shartnomani buzmaydi, Vizantiya xatosi yo'q
tarmoq
Tugun boshqa istalgan tugunga xabar yuborishi mumkin
Xabarlar asinxron tarzda yuborilishi mumkin va uzatish jarayoni istalgan vaqtni olishi mumkin.
Xabarlar yo'qolishi, takrorlanishi yoki muvaffaqiyatsiz bo'lishi mumkin.
Xabar uzatish paytida o'zgartirilmaydi yoki yo'q qilinmaydi, Vizantiya xatosi yo'q
Tugunlar soni
Umuman olganda, konsensus algoritmi ff tugunlarida xatolik yuzaga kelganda tizim normal ishlashini ta'minlash uchun 2f + 12f + 1 tugunlaridan foydalanadi.
Rollar
Paxos algoritmida turli tugunlar xatti-harakatlariga ko'ra turli rollarga bo'linadi: mijoz, taklif qiluvchi, qabul qiluvchi, o'rganuvchi, etakchi. Algoritmni amalga oshirishda tugun bir yoki bir nechta rollarni bajarishi mumkin.
mijoz
Mijoz tarqatilgan tizimga so'rov yuboradi va javobni kutadi. Masalan, taqsimlangan fayl tizimida fayl yozish so'rovi ishga tushiriladi.
Qabul qiluvchi
Qabul qiluvchilar guruhlarga bo'lingan (Kvorum) va har bir guruh qabul qiluvchilarning ko'p qismini o'z ichiga oladi. Qabul qiluvchi tomonga yuborilgan har qanday xabar guruhning istalgan tuguniga yuborilishi kerak. Agar qabul qiluvchi tomon xabarni qabul qilsa, lekin xabarning nusxasi guruhdagi barcha qabul qiluvchilarga yuborilmasa, xabar e'tiborga olinmaydi.
Taklifchi
Tashabbus qiymatini ko'rsating va qabul qiluvchini ushbu qiymatga rozi bo'lishiga harakat qiling. Mojaro yuzaga kelgan taqdirda, u koordinator rolini o'z zimmasiga oladi.
O'rgangan
Kelishuvga erishilganda, harakatni bajaruvchi. Mijoz so'rovi mezbon tomonidan bir ovozdan qabul qilinganda, o'quvchi so'rovni bajaradi va qaytib keladi.
yetakchi
Konsensus jarayonini ilgari surish uchun Excellent Proposer ishlatiladi. Ko'pgina tugunlar o'zlarini etakchi deb hisoblashlari mumkin.
Kvorumlar
Guruh ostida ushbu guruh qabul qiluvchilarning ko'pchiligini (yarmidan ko'pini) o'z ichiga oladi, shuning uchun har qanday ikkita Kvorum kamida bitta umumiy tugunga ega bo'ladi. Masalan, {A, B, C, D} tugunida barcha uchta tugunlar kvorum hosil qilishi mumkin. Siz har bir tugunga vazn belgilashingiz mumkin va kvorumdagi barcha tugunlarning og'irliklari yig'indisi 50% dan katta bo'ladi.
Asosiy Paxos
Konsensus jarayoni odatda shunday ko'rinadi: mijoz taqsimlangan tizimga so'rovni boshlaydi, so'ngra taklif qiluvchi so'rovni (taklifni) qabul qiluvchi tomonga yuboradi. Konsensusga erishilganda, o'quvchi so'rovni bajaradi.
Gapning shakli: butun N uning identifikatorini ifodalaydi, har bir tugun tomonidan yuborilgan gapning identifikatori oshiriladi, so'ngra gapning qiymati qiymat bilan ifodalanadi.
Konsensus quyidagi to'rt bosqichda o'rnatiladi.
1. Tayyorlang
Da'vogar birinchi navbatda taklif identifikatorini (N bilan belgilangan) kvorumning qabul qiluvchi uchiga (ya'ni, tugunlarning ko'pchiligiga) yuboradi.
2 Va'da
Qabul qiluvchi tayyorlanish xabarini oladi. Agar xabardagi N hozirgacha olingan eng katta qiymat bo'lsa, u Va'da xabarini qaytaradi. Agar N ning kattaroq qiymati avval olingan bo'lsa, bu safar qabul qilingan Prepare xabari e'tiborga olinmaydi. Agar ushbu Akseptor ilgari taklifni qabul qilgan bo'lsa, u qaytarilgan va'da xabariga N va oldingi qabul qilingan taklifning qiymatini qo'shadi.
3. So'rovni qabul qiling
Agar taklif qiluvchi etarli va'da olsa, siz taklifning qiymatini belgilashingiz kerak. Agar qabul qilingan va'da xabarida Akseptor tomonidan qabul qilingan taklif bo'lsa, undan eng yuqori N qiymatiga ega bo'lgan taklif tanlanadi va taklifni belgilash uchun qiymat qiymatidan foydalaniladi.
Keyin taklif qiluvchi kvorum qabul qiluvchiga taklif identifikatori va qiymatini o'z ichiga olgan "So'rovni qabul qilish" xabarini yuboradi.
4 Qabul qilingan
Qabul qiluvchi "So'rovni qabul qilaman" xabarini olganida, agar va'da uchun katta identifikatorga ega bo'lgan taklif mavjud bo'lmasa, taklif QABUL QILISh KERAK. Taklifning qiymatini yozib oling va taklif qiluvchiga va har bir talabaga "Qabul qilingan" xabarini yuboring.
Shuni ta'kidlash kerakki, Akseptor takliflarni qabul qilishi mumkin va bu takliflar turli xil ma'nolarga ega bo'lishi mumkin. Biroq, Paxos protokoli oxirida faqat bitta qiymatga erishilishini kafolatlashi mumkin.
Paxos jarayonining xabarlar oqimi quyidagi rasmda ko'rsatilgan:
Do'stlaringiz bilan baham: |
