Тэгэхээр төсөөлөөд үз дээ. Өрөөнд 5 муур цоожтой байгаа бөгөөд эзнээ сэрээхийн тулд тэд бүгдээрээ энэ талаар тохиролцох хэрэгтэй, учир нь тэд тавыг түшин хаалгаа онгойлгох боломжтой. Хэрэв муурны нэг нь Шредингерийн муур бол бусад муур нь түүний шийдвэрийн талаар мэдэхгүй бол "Тэд яаж үүнийг хийж чадах вэ?" Гэсэн асуулт гарч ирнэ.
Энэ нийтлэлд би тархсан системүүдийн ертөнцийн онолын бүрэлдэхүүн хэсэг, тэдгээрийн үйл ажиллагааны зарчмуудын талаар энгийн үгээр хэлэх болно. Би мөн Paxos-ийн үндсэн санааг өнгөцхөн судлах болно.
Хөгжүүлэгчид үүлэн дэд бүтэц, төрөл бүрийн мэдээллийн санг ашиглаж, олон тооны зангилааны кластерт ажиллах үед өгөгдөл бүрэн, найдвартай, үргэлж бэлэн байх болно гэдэгт итгэлтэй байдаг. Гэхдээ баталгаа хаана байна вэ?
Үндсэндээ бидэнд байгаа баталгаа бол ханган нийлүүлэгчийн баталгаа юм. Тэдгээрийг баримт бичигт дараах байдлаар тайлбарласан болно: "Энэ үйлчилгээ нь маш найдвартай, өгөгдсөн SLA-тай, санаа зовох хэрэггүй, бүх зүйл таны бодож байгаагаар хуваарилагдах болно."
Том компаниудын ухаалаг залуус бүх зүйл сайхан болно гэж бидэнд итгүүлсэн тул бид хамгийн сайн зүйлд итгэх хандлагатай байдаг. Бид энэ асуултыг тавьдаггүй: яагаад үнэндээ энэ нь ажиллах боломжтой юм бэ? Ийм системийг зөв ажиллуулах албан ёсны үндэслэл бий юу?
Би саяхан очсон мөн энэ сэдвээс маш их урам зориг авсан. Сургуулийн лекцүүд нь компьютерийн системтэй холбоотой гэхээсээ илүү тооцооллын хичээлтэй төстэй байв. Гэвч бидний өдөр тутам өөрийн мэдэлгүй хэрэглэдэг хамгийн чухал алгоритмууд яг ийм байдлаар нэгэн цагт батлагдсан юм.
Ихэнх орчин үеийн тархсан системүүд нь Paxos зөвшилцлийн алгоритм болон түүний янз бүрийн өөрчлөлтүүдийг ашигладаг. Хамгийн гайхалтай нь энэ алгоритмын хүчин төгөлдөр байдал, зарчмын хувьд оршин тогтнох магадлалыг үзэг цаасаар л нотлох боломжтой юм. Практикт алгоритмыг үүлэн дэх асар олон тооны зангилаа дээр ажилладаг том системд ашигладаг.
Дараа нь юу хэлэлцэх талаар хөнгөн дүрслэл: хоёр генералын даалгаварДулаацах аргыг авч үзье .
Бид улаан, цагаан гэсэн хоёр армитай. Бүслэгдсэн хотод цагаан цэргүүд байрлаж байна. А1, А2 генералаар удирдуулсан улаан цэргүүд хотын хоёр талд байрладаг. Улаачдын даалгавар бол цагаан хот руу дайрч, ялах явдал юм. Гэсэн хэдий ч улаан жанжин бүрийн арми цагаан армиас цөөхөн байдаг.
Улаануудын ялалтын нөхцөл: цагаан арьстнуудаас тооны хувьд давуу байхын тулд генерал хоёулаа нэгэн зэрэг довтлох ёстой. Үүний тулд А1, А2 генералууд хоорондоо зөвшилцөх хэрэгтэй. Бүгд тус тусдаа дайрвал улаач нар ялагдана.
Зөвшилцөлд хүрэхийн тулд А1, А2 генералууд цагаан хотын нутаг дэвсгэрээр дамжуулан бие биедээ элч илгээж болно. Элч нь холбоотны жанжинд амжилттай хүрч, эсвэл дайсанд саад болж магадгүй юм. Асуулт: Улаан үст генералуудын хооронд ийм дараалал байдаг уу (А1-ээс А2 руу элч илгээх дараалал, эсрэгээр А2-аас А1 хүртэл), тэд X цагт халдлага хийх талаар тохиролцох баталгаатай байдаг. Энд, Энэ нь аль аль генерал хоёулаа холбоотон (өөр генерал) тогтоосон X цагт довтлох болно гэсэн хоёрдмол утгагүй баталгаатай болно гэсэн үг юм.
А1 нь А2 руу “Өнөөдөр шөнө дунд дайралт хийцгээе!” гэсэн мессеж илгээсэн гэж бодъё. Генерал А1 генерал А2-аас баталгаажуулалгүйгээр довтлох боломжгүй. Хэрэв А1-ийн элч ирсэн бол генерал А2 "Тийм ээ, өнөөдөр цагаан арьстнуудыг алцгаая" гэсэн мессежийг илгээнэ. Харин одоо генерал А2 түүний элч ирсэн эсэхийг мэдэхгүй, дайралт нэгэн зэрэг болох эсэх нь түүнд баталгаагүй байна. Одоо General A2 дахин баталгаажуулах шаардлагатай байна.
Хэрэв бид тэдний харилцаа холбоог цааш нь тайлбарлавал, хэчнээн олон мессеж солилцох цикл байсан ч гэсэн хоёр генерал хоёулаа тэдний мессежийг хүлээн авсан гэдгийг баталгаажуулах арга байхгүй (ямар ч элчийг саатуулж болно гэж үзвэл).
Хоёр генералын асуудал бол найдваргүй харилцаа холбоо бүхий хоёр зангилаа байдаг маш энгийн тархсан системийн гайхалтай жишээ юм. Энэ нь синхрончлогдсон гэсэн 100% баталгаа бидэнд байхгүй гэсэн үг. Үүнтэй төстэй асуудлуудыг зөвхөн нийтлэлд илүү өргөн хүрээнд авч үзэх болно.
Бид тархсан системийн тухай ойлголтыг танилцуулж байна
Тархсан систем гэдэг нь мессеж солилцох боломжтой компьютеруудын бүлэг (цаашид бид тэдгээрийг зангилаа гэж нэрлэх болно) юм. Тусдаа зангилаа бүр нь бие даасан байгууллага юм. Зангилаа нь даалгавруудыг бие даан боловсруулах боломжтой боловч бусад зангилаатай харилцахын тулд мессеж илгээх, хүлээн авах шаардлагатай.
Мессежүүд яг хэрхэн хэрэгжиж байгаа, ямар протокол ашигладаг вэ гэдэг нь энэ хүрээнд бидний сонирхлыг татахгүй байна. Тархсан системийн зангилаанууд мессеж илгээх замаар хоорондоо мэдээлэл солилцох нь чухал юм.
Тодорхойлолт нь өөрөө тийм ч төвөгтэй харагддаггүй ч тархсан систем нь бидний хувьд чухал ач холбогдолтой хэд хэдэн шинж чанартай байдаг гэдгийг бид анхаарч үзэх хэрэгтэй.
Тархсан системийн шинж чанарууд
- Тохирлын байдал - системд нэгэн зэрэг эсвэл зэрэгцэн тохиолдох үйл явдлуудын боломж. Түүнчлэн, эдгээр үйл явдлын тодорхой дараалал байхгүй бол бид хоёр өөр зангилаа дээр тохиолдох үйл явдлуудыг нэгэн зэрэг байж болзошгүй гэж үзэх болно. Гэхдээ дүрмээр бол бидэнд байхгүй.
- Дэлхийн цаг байхгүй. Бид дэлхийн цаг байхгүйгээс болж үйл явдлын тодорхой дараалал байхгүй. Хүмүүсийн энгийн ертөнцөд бид цаг, цаг хугацаатай байдаг гэдэгт дассан байдаг. Түгээмэл системтэй холбоотой бүх зүйл өөрчлөгддөг. Хэт нарийвчлалтай атомын цаг хүртэл зөрөх чадвартай бөгөөд хоёр үйл явдлын аль нь хамгийн түрүүнд болсныг хэлж чадахгүй нөхцөл байдал байж болно. Тиймээс бид бас цаг хугацаанд нь найдаж болохгүй.
- Системийн зангилааны бие даасан гэмтэл. Өөр нэг асуудал бий: бидний зангилаа үүрд үргэлжлэхгүй тул ямар нэг зүйл буруу болж магадгүй юм. Хатуу диск амжилтгүй болж, үүлэн доторх виртуал машин дахин ачаалж, сүлжээ анивчиж, мессеж алга болно. Түүнээс гадна, зангилаа ажиллаж байгаа нөхцөл байдал байж болох ч системийн эсрэг ажилладаг. Сүүлчийн ангиллын асуудлууд нь тусдаа нэртэй болсон: асуудал . Энэ асуудалтай тархсан системийн хамгийн алдартай жишээ бол Blockchain юм. Гэхдээ өнөөдөр бид энэ тусгай ангиллын асуудлыг авч үзэхгүй. Нэг буюу хэд хэдэн зангилаа бүтэлгүйтэж болзошгүй нөхцөл байдлыг бид сонирхох болно.
- Зангилаа хоорондын харилцааны загварууд (мессежийн загварууд).. Зангилаанууд нь мессеж солилцох замаар харилцдаг гэдгийг бид аль хэдийн тогтоосон. Мессежийн хоёр алдартай загвар байдаг: синхрон ба асинхрон.
Тархсан систем дэх зангилаа хоорондын харилцааны загварууд
Синхрон загвар - Бид нэг зангилаанаас нөгөө цэг рүү мессеж хүрэх баталгаатай тодорхой хугацааны хязгаарлагдмал дельта байдгийг баттай мэднэ. Хэрэв энэ хугацаа өнгөрч, мессеж ирээгүй бол зангилаа амжилтгүй болсон гэж бид итгэлтэйгээр хэлж чадна. Энэ загварт бид урьдчилан таамаглах боломжтой хүлээх хугацаатай.
Асинхрон загвар - асинхрон загварт бид хүлээх хугацаа нь хязгаарлагдмал гэж үздэг боловч зангилаа бүтэлгүйтсэн гэдгийг баталж чадах тийм дельта цаг байхгүй. Тэдгээр. Зангилаанаас ирсэн мессежийг хүлээх хугацаа нь дур зоргоороо урт байж болно. Энэ бол чухал тодорхойлолт бөгөөд бид энэ талаар цаашид ярих болно.
Түгээмэл систем дэх зөвшилцлийн тухай ойлголт
Зөвшилцлийн тухай ойлголтыг албан ёсоор тодорхойлохын өмнө бидэнд хэрэгтэй нөхцөл байдлын жишээг авч үзье, тухайлбал - Төрийн машины хуулбар.
Бидэнд тараасан бүртгэл байна. Бид үүнийг тууштай, тархсан системийн бүх зангилаа дээрх ижил өгөгдлийг агуулсан байхыг хүсч байна. Зангилааны аль нэг нь бүртгэлд бичих гэж буй шинэ утгыг сурах үед түүний даалгавар нь бусад бүх зангилаанд энэ утгыг санал болгох бөгөөд ингэснээр бүртгэл бүх зангилаанууд дээр шинэчлэгдэж, систем шинэ тогтвортой төлөв рүү шилждэг. Энэ тохиолдолд зангилаанууд хоорондоо тохирч байх нь чухал: бүх зангилаа санал болгож буй шинэ утгыг зөв гэж хүлээн зөвшөөрч, бүх зангилаа энэ утгыг хүлээн зөвшөөрдөг бөгөөд зөвхөн энэ тохиолдолд хүн бүр шинэ утгыг бүртгэлд бичиж болно.
Өөрөөр хэлбэл: зангилааны аль нь ч илүү хамааралтай мэдээлэлтэй гэж эсэргүүцээгүй бөгөөд санал болгож буй утга нь буруу байсан. Зангилаа хоорондын тохиролцоо ба нэг зөв хүлээн зөвшөөрөгдсөн утгын тохиролцоо нь тархсан систем дэх зөвшилцөл юм. Дараа нь бид тархсан системд баталгаатай зөвшилцөлд хүрэх боломжийг олгодог алгоритмуудын талаар ярих болно.
Илүү албан ёсоор бид зөвшилцлийн алгоритмыг (эсвэл зүгээр л зөвшилцлийн алгоритм) хуваарилсан системийг А төлөвөөс B төлөв рүү шилжүүлэх тодорхой функц гэж тодорхойлж болно. Түүнээс гадна энэ төлөвийг бүх зангилаа хүлээн зөвшөөрдөг бөгөөд бүх зангилаа үүнийг баталж чадна. Эндээс харахад энэ даалгавар нь анх харахад тийм ч энгийн зүйл биш юм.
Зөвшилцлийн алгоритмын шинж чанарууд
Системийг үргэлжлүүлэн оршин тогтнохын тулд зөвшилцлийн алгоритм нь гурван шинж чанартай байх ёстой бөгөөд төлөв байдлаас төлөв рүү шилжихэд тодорхой ахиц дэвшил гарна.
- Гэрээ – бүх зөв ажиллаж байгаа зангилаа ижил утгыг авах ёстой (нийтлэлд энэ өмчийг аюулгүй байдлын өмч гэж нэрлэдэг). Одоо ажиллаж байгаа бүх зангилаа (бусадтай холбоо тасрахгүй эсвэл бүтэлгүйтээгүй) тохиролцоонд хүрч, эцсийн нийтлэг утгыг хүлээн зөвшөөрөх ёстой.
Бидний авч үзэж буй тархсан системийн зангилаанууд зөвшилцөхийг хүсч байгааг энд ойлгох нь чухал юм. Өөрөөр хэлбэл, бид одоо ямар нэг зүйл зүгээр л бүтэлгүйтэх боломжтой системийн тухай ярьж байна (жишээлбэл, зарим зангилаа бүтэлгүйтдэг), гэхдээ энэ системд бусдын эсрэг санаатайгаар ажилладаг зангилаа байхгүй (Византийн генералуудын даалгавар). Энэ өмчийн улмаас систем тогтвортой хэвээр байна.
- Бүрэн бүтэн байдал - хэрэв бүх зөв ажиллаж байгаа зангилаа ижил утгыг санал болгодог бол v, энэ нь зөв ажиллаж байгаа зангилаа бүр энэ утгыг хүлээн зөвшөөрөх ёстой гэсэн үг юм v.
- Гэрээг дуусгавар болгох - зөв ажиллаж байгаа бүх зангилаанууд эцэст нь тодорхой утгыг (амьдралын шинж чанар) авах бөгөөд энэ нь алгоритмд системд ахиц дэвшил гаргах боломжийг олгодог. Зөв ажиллаж буй зангилаа бүр эрт орой хэзээ нэгэн цагт эцсийн утгыг хүлээн зөвшөөрч, баталгаажуулах ёстой: "Миний хувьд энэ үнэ цэнэ үнэн, би бүх системтэй санал нэг байна."
Зөвшилцлийн алгоритм хэрхэн ажилладаг тухай жишээ
Хэдийгээр алгоритмын шинж чанарууд нь бүрэн тодорхой бус байж магадгүй юм. Тиймээс бид хамгийн энгийн зөвшилцлийн алгоритм нь синхрон мессежийн загвар бүхий системд ямар үе шат дамждагийг жишээгээр харуулах болно, үүнд бүх зангилаа нь хүлээгдэж буй шиг ажилладаг, мессежүүд алга болдоггүй, юу ч тасардаггүй (энэ үнэхээр тохиолддог уу?).
- Энэ бүхэн гэрлэх саналаас эхэлдэг (Санал тавих). Үйлчлүүлэгч "Зангилаа 1" гэж нэрлэгддэг зангилаатай холбогдож, гүйлгээг эхлүүлж, зангилаа руу шинэ утгыг дамжуулсан гэж үзье - O. Одооноос эхлэн бид "Зангилаа 1" гэж нэрлэх болно. санал болгох. Санал дэвшүүлэгчийн хувьд "Зангилаа 1" одоо шинэ өгөгдөлтэй гэдгээ бүхэл бүтэн системд мэдэгдэх ёстой бөгөөд бусад бүх зангилаа руу мессеж илгээдэг: "Хараач! "O" гэсэн утга надад ирсэн бөгөөд би үүнийг бичихийг хүсч байна! Та мөн бүртгэлдээ “O”-г бичихээ баталгаажуулна уу.”
- Дараагийн шат бол санал болгож буй үнэ цэнийн төлөө санал өгөх (Санал хураалт). Энэ юунд зориулагдсан бэ? Бусад зангилаанууд сүүлийн үеийн мэдээллийг хүлээн авсан бөгөөд тэдгээр нь ижил гүйлгээний талаархи мэдээлэлтэй байж магадгүй юм.
"Зангилаа 1" саналаа илгээх үед бусад зангилаанууд энэ үйл явдлын талаарх логуудаа шалгана. Хэрэв зөрчилдөөн байхгүй бол зангилаанууд: "Тийм ээ, надад энэ үйл явдлын талаар өөр мэдээлэл алга. "O" утга нь бидний авах ёстой хамгийн сүүлийн үеийн мэдээлэл юм."Бусад тохиолдолд зангилаанууд "Зангилаа 1" -д хариулах боломжтой: "Сонс! Надад энэ гүйлгээний талаарх сүүлийн үеийн мэдээлэл байна. 'O' биш, харин илүү сайн зүйл."
Санал хураалтын шатанд зангилаанууд шийдвэрт хүрдэг: тэд бүгд ижил утгыг хүлээн зөвшөөрдөг, эсвэл тэдний нэг нь эсрэг санал өгсөн нь түүнд илүү сүүлийн үеийн мэдээлэл байгааг харуулж байна.
- Хэрэв санал хураалт амжилттай болж, бүгд дэмжсэн бол систем шинэ шатанд шилждэг - утгыг хүлээн авах (Зөвшөөрөх). "Зангилаа 1" нь бусад зангилааны бүх хариултыг цуглуулж, "Хүн бүр "O" гэсэн утгыг хүлээн зөвшөөрсөн! Одоо би "O" бол бидний шинэ утга, хүн бүрт адилхан гэдгийг албан ёсоор мэдэгдэж байна! Бяцхан номондоо бичээрэй, бүү мартаарай. Бүртгэлдээ бичээрэй!"
- Үлдсэн зангилаанууд нь "O" утгыг бичсэн гэдгээ баталгаажуулсан (Хүлээн зөвшөөрөгдсөн) илгээдэг; энэ хугацаанд шинэ зүйл ирээгүй (хоёр үе шаттай үүрэг даалгавар). Энэхүү чухал үйл явдлын дараа бид тараасан гүйлгээ дууссан гэж үзэж байна.
Тиймээс энгийн тохиолдолд зөвшилцлийн алгоритм нь санал болгох, санал өгөх (санал өгөх), хүлээн зөвшөөрөх (хүлээн зөвшөөрөх), хүлээн зөвшөөрөх (хүлээн зөвшөөрсөн) гэсэн дөрвөн алхамаас бүрдэнэ.
Хэрэв зарим алхам дээр бид тохиролцоонд хүрч чадаагүй бол санал болгож буй утгыг баталгаажуулахаас татгалзсан зангилааны өгсөн мэдээллийг харгалзан алгоритм дахин эхэлнэ.
Асинхрон систем дэх зөвшилцлийн алгоритм
Үүнээс өмнө бүх зүйл жигд байсан, учир нь бид синхрон мессежийн загварын тухай ярьж байсан. Гэхдээ орчин үеийн ертөнцөд бид бүх зүйлийг асинхрон байдлаар хийж дассан гэдгийг бид мэднэ. Үүнтэй төстэй алгоритм нь асинхрон мессежийн загвартай системд хэрхэн ажилладаг вэ, үүнд зангилааны хариуг хүлээх хугацаа нь дур зоргоороо урт байж болно (дашрамд хэлэхэд, зангилааны эвдрэлийг жишээ болгон авч үзэж болно. зангилаа нь дур зоргоороо удаан хугацаанд хариу өгөх боломжтой).
Одоо бид зөвшилцлийн алгоритм нь зарчмын хувьд хэрхэн ажилладагийг мэдэж байгаа тул өнөөг хүртэл үүнийг хийсэн сониуч уншигчдад зориулсан асуулт: асинхрон мессежийн загвар бүхий N зангилааны системийн хэдэн зангилаа бүтэлгүйтэж, систем зөвшилцөлд хүрч чадах вэ?
Зөв хариулт, үндэслэл нь спойлерын ард байна.Зөв хариулт нь: 0. Асинхрон системийн нэг зангилаа ч бүтэлгүйтвэл систем зөвшилцөлд хүрч чадахгүй. Энэ мэдэгдлийг тодорхой хүрээлэлд сайн мэддэг FLP теоремоор нотолсон (1985, Фишер, Линч, Патерсон, өгүүллийн төгсгөлд байгаа эх сурвалжтай линк): "Хэрэв дор хаяж нэг зангилаа бүтэлгүйтвэл тархсан зөвшилцөлд хүрэх боломжгүй юм. .”
Залуус аа, тэгвэл бидэнд асуудал тулгараад байна, бид бүх зүйл асинхрон байдалд дассан. Тэгээд энд байна. Хэрхэн үргэлжлүүлэн амьдрах вэ?
Бид зүгээр л онол, математикийн тухай ярьж байсан. "Зөвшилцөлд хүрч чадахгүй байна" гэдэг нь математик хэлнээс манай хэл рүү орчуулбал инженерчлэл гэж юу гэсэн үг вэ? Энэ нь "үргэлж хүрч чадахгүй" гэсэн үг юм. Зөвшилцөлд хүрэх боломжгүй тохиолдол бий. Энэ ямар хэрэг вэ?
Энэ нь дээр дурдсан liveness өмчийг яг зөрчиж байна. Бидэнд нийтлэг тохиролцоо байхгүй бөгөөд бүх зангилаанаас хариу ирээгүй тохиолдолд системд ахиц дэвшил гарахгүй (хязгаарлагдмал хугацаанд дуусгах боломжгүй). Учир нь асинхрон системд бидэнд урьдчилан таамаглах хариу өгөх хугацаа байдаггүй бөгөөд зангилаа эвдэрсэн эсвэл хариу өгөхөд удаан хугацаа шаардагдах эсэхийг бид мэдэхгүй.
Гэхдээ практик дээр бид шийдлийг олж чадна. Бидний алгоритм бүтэлгүйтсэн тохиолдолд удаан хугацаанд ажиллах боломжтой байг (энэ нь тодорхой бус хугацаагаар ажиллах боломжтой). Гэхдээ ихэнх тохиолдолд ихэнх зангилаанууд зөв ажиллаж байх үед системд ахиц дэвшил гарах болно.
Практикт бид хэсэгчилсэн синхрон холбооны загваруудтай харьцдаг. Хэсэгчилсэн синхрончлолыг дараах байдлаар ойлгодог: ерөнхий тохиолдолд бид асинхрон загвартай байдаг боловч тодорхой цаг хугацааны "дэлхийн тогтворжилтын цаг" гэсэн тодорхой ойлголтыг албан ёсоор нэвтрүүлсэн.
Энэ цаг хугацаа ямар ч урт хугацаанд ирэхгүй байж болох ч хэзээ нэгэн цагт ирэх ёстой. Виртуал сэрүүлэг дуугарах бөгөөд тэр мөчөөс эхлэн бид мессеж ирэх цагийг урьдчилан таамаглаж чадна. Энэ мөчөөс эхлэн систем асинхроноос синхрон руу шилждэг. Практикт бид яг ийм системтэй харьцдаг.
Paxos алгоритм нь зөвшилцлийн асуудлыг шийддэг
нь зарим зангилаа бүтэлгүйтэх магадлалыг харгалзан хэсэгчлэн синхрон системүүдийн зөвшилцлийн асуудлыг шийддэг алгоритмуудын гэр бүл юм. Paxos-ийн зохиогч нь . Тэрээр 1989 онд алгоритмын оршин тогтнол, зөв байдлын албан ёсны нотлох баримтыг санал болгосон.
Гэвч нотлох баримт нь өчүүхэн төдий зүйл биш болсон. Алгоритмыг тайлбарласан анхны хэвлэл нь зөвхөн 1998 онд (33 хуудас) гарсан. Үүнийг ойлгоход туйлын хэцүү байсан тул 2001 онд 14 хуудас бүхий нийтлэлийн тайлбарыг нийтлэв. Үнэн хэрэгтээ зөвшилцлийн асуудал тийм ч энгийн биш бөгөөд ийм алгоритмын ард хамгийн ухаалаг хүмүүсийн асар их ажил байдаг гэдгийг харуулахын тулд нийтлэлийн хэмжээг өгсөн болно.
Лесли Лампорт өөрөө лекцэндээ хоёр дахь тайлбар өгүүлэлд нэг мэдэгдэл, нэг мөр (тэр алийг нь зааж өгөөгүй) байгаа бөгөөд үүнийг янз бүрээр тайлбарлаж болох талаар тэмдэглэсэн нь сонирхолтой юм. Үүнээс болж орчин үеийн олон тооны Paxos програмууд бүрэн зөв ажиллахгүй байна.
Paxos-ийн ажилд нарийвчилсан дүн шинжилгээ хийхэд нэгээс олон өгүүлэл шаардагдах тул би алгоритмын гол санааг маш товчоор илэрхийлэхийг хичээх болно. Миний нийтлэлийн төгсгөлд байгаа холбоосуудаас та энэ сэдвийг цааш нь судлах материалыг олох болно.
Paxos дахь дүрүүд
Paxos алгоритм нь үүргийн тухай ойлголттой. Гурван үндсэн зүйлийг авч үзье (нэмэлт үүрэг бүхий өөрчлөлтүүд байдаг):
- Санал дэвшүүлэгчид (нэр томъёог бас ашиглаж болно: удирдагч эсвэл зохицуулагч). Эдгээр нь хэрэглэгчээс шинэ үнэ цэнийн талаар суралцаж, удирдагчийн үүргийг гүйцэтгэдэг залуус юм. Тэдний даалгавар бол шинэ үнэ цэнийн талаархи саналуудыг гаргаж, зангилааны цаашдын үйл ажиллагааг зохицуулах явдал юм. Түүнээс гадна, Paxos нь тодорхой нөхцөл байдалд хэд хэдэн удирдагчид байх боломжийг олгодог.
- Хүлээн авагчид (сонгогчид). Эдгээр нь тодорхой утгыг хүлээн зөвшөөрөх эсвэл татгалзах санал өгдөг зангилаа юм. Тэдний үүрэг маш чухал, учир нь шийдвэр нь тэднээс шалтгаална: зөвшилцлийн алгоритмын дараагийн шатны дараа систем ямар төлөвт шилжих (эсвэл орохгүй байх).
- Суралцагчид. Системийн төлөв өөрчлөгдсөн үед хүлээн зөвшөөрөгдсөн шинэ утгыг зүгээр л хүлээн авч бичдэг зангилаа. Тэд шийдвэр гаргадаггүй, зөвхөн өгөгдлийг хүлээн авч, эцсийн хэрэглэгчдэд өгөх боломжтой.
Нэг зангилаа нь янз бүрийн нөхцөлд хэд хэдэн үүргийг нэгтгэж чаддаг.
Чуулгын тухай ойлголт
гэсэн системтэй гэж бид таамаглаж байна N зангилаа Мөн тэдний хамгийн дээд тал нь F зангилаа бүтэлгүйтэж магадгүй. Хэрэв F зангилаа бүтэлгүйтвэл бид дор хаяж байх ёстой 2F+1 хүлээн авагч зангилаа.
Энэ нь хамгийн муу нөхцөл байдалд ч гэсэн зөв ажилладаг "сайн" зангилааны олонхтой байхын тулд зайлшгүй шаардлагатай. Тэр бол F+1 тохиролцсон "сайн" зангилаа, эцсийн утгыг хүлээн авна. Тэгэхгүй бол манай нутгийн янз бүрийн бүлгүүд өөр өөр утга агуулгатай болж, хоорондоо санал нийлэхгүй байх нөхцөл байдал үүсч магадгүй юм. Тиймээс санал хураахад үнэмлэхүй олонх хэрэгтэй.
Paxos зөвшилцлийн алгоритм хэрхэн ажилладаг тухай ерөнхий санаа
Paxos алгоритм нь хоёр том үе шатыг агуулдаг бөгөөд тэдгээр нь эргээд хоёр үе шат болгон хуваагддаг:
- 1а үе шат: Бэлтгэх. Бэлтгэл үе шатанд удирдагч (санал гаргагч) бүх цэгүүдэд мэдэгдэнэ: "Бид санал хураалтын шинэ үе шатыг эхлүүлж байна. Бидэнд шинэ тойрог байна. Энэ тойргийн тоо n байна. Одоо бид санал хураалтаа эхлүүлнэ." Одоогоор энэ нь зүгээр л шинэ мөчлөгийн эхлэлийг мэдээлдэг боловч шинэ утгыг мэдээлдэггүй. Энэ үе шатны даалгавар бол шинэ шатыг эхлүүлж, хүн бүрт өөрийн өвөрмөц дугаарыг мэдээлэх явдал юм. Тойргийн тоо нь чухал бөгөөд энэ нь өмнөх бүх удирдагчдын санал өгсөн бүх тооноос илүү утгатай байх ёстой. Учир нь дугуй дугаарын ачаар системийн бусад зангилаа удирдагчийн өгөгдөл хэр сүүлийн үеийн болохыг ойлгох болно. Бусад зангилаа нэлээд хожуу тойргийн санал хураалтын дүнг аль хэдийн гаргаад, удирдагчдаа цаг үеэсээ хоцорсон гэдгээ хэлэх байх.
- 1б үе шат: Амлалт. Хүлээн авагч зангилаанууд санал хураалтын шинэ шатны дугаарыг хүлээн авснаар хоёр үр дүн гарах боломжтой.
- Шинэ саналын n тоо нь хүлээн авагчийн оролцсон өмнөх саналын тооноос их байна. Дараа нь хүлээн авагч нь n-ээс бага тоогоор дахин санал өгөхөд оролцохгүй гэсэн амлалтыг удирдагч руу илгээдэг. Хэрэв хүлээн авагч нь аль хэдийн ямар нэг зүйлийн төлөө саналаа өгсөн бол (өөрөөр хэлбэл хоёр дахь үе шатанд ямар нэгэн үнэ цэнийг хүлээн зөвшөөрсөн) амлалтдаа хүлээн зөвшөөрөгдсөн үнэ цэнэ, оролцсон саналын тоог хавсаргана.
- Үгүй бол, хэрэв хүлээн авагч нь илүү олон тооны саналын талаар аль хэдийн мэдсэн бол бэлтгэлийн алхамыг үл тоомсорлож, удирдагчид хариу өгөхгүй байж болно.
- 2а үе шат: Зөвшөөрөх. Удирдагч нь чуулгын хариуг хүлээх хэрэгтэй (систем дэх зангилааны дийлэнх хэсэг) бөгөөд хэрэв шаардлагатай тооны хариу ирсэн бол түүнд үйл явдлыг хөгжүүлэх хоёр сонголт байна.
- Хүлээн авагчдын зарим нь аль хэдийн саналаа өгсөн утгыг илгээсэн. Энэ тохиолдолд удирдагч хамгийн их тоогоор санал хураалтаас утгыг сонгоно. Энэ утгыг x гэж нэрлэе, энэ нь бүх зангилаа руу "Хүлээн зөвшөөрч байна (n, x)" гэсэн мессежийг илгээдэг бөгөөд эхний утга нь өөрийн санал болгох алхамын саналын дугаар, хоёр дахь утга нь хүн бүрийн цуглуулсан, өөрөөр хэлбэл бидний санал өгөх үнэ цэнэ.
- Хэрэв хүлээн авагчдын хэн нь ч ямар нэгэн үнэ цэнийг илгээгээгүй, гэхдээ тэд зүгээр л энэ шатанд саналаа өгнө гэж амласан бол удирдагч тэднийг хамгийн түрүүнд манлайлагч болсон үнэ цэнийн төлөө санал өгөхийг урьж болно. Үүнийг y гэж нэрлэе. Энэ нь өмнөх үр дүнтэй төстэй "Зөвшөөрөх (n, y)" гэх мэт бүх зангилаа руу мессеж илгээдэг.
- Үе шат 2b: Зөвшөөрөгдсөн. Цаашилбал, хүлээн авагчийн зангилаанууд удирдагчаас "Зөвшөөрөх (...)" гэсэн мессежийг хүлээн авсны дараа зөвхөн зарим нэг (бусад) амлалт өгөөгүй тохиолдолд үүнийг хүлээн зөвшөөрнө (шинэ утгыг хүлээн зөвшөөрч буйгаа бүх зангилаа руу илгээнэ үү) ) тойрогтоо санал хураалтад оролцох удирдагч n' > n, эс бөгөөс тэд баталгаажуулах хүсэлтийг үл тоомсорлодог.
Хэрэв зангилааны дийлэнх нь удирдагчид хариу өгч, бүгд шинэ утгыг баталгаажуулсан бол шинэ утгыг хүлээн зөвшөөрсөн гэж үзнэ. Өө! Хэрэв олонхи нь хүрээгүй эсвэл шинэ утгыг хүлээн авахаас татгалзсан зангилаа байгаа бол бүх зүйл дахин эхэлнэ.
Paxos алгоритм ингэж ажилладаг. Эдгээр үе шат бүр нь олон нарийн шинж чанартай байдаг бөгөөд бид янз бүрийн алдаа, олон удирдагчдын асуудал болон бусад олон зүйлийг бараг авч үзээгүй боловч энэ нийтлэлийн зорилго нь зөвхөн уншигчдыг тархсан тооцооллын ертөнцөд өндөр түвшинд танилцуулах явдал юм.
Paxos нь энэ төрлийн цорын ганц биш гэдгийг тэмдэглэх нь зүйтэй бөгөөд бусад алгоритмууд байдаг, жишээлбэл, , гэхдээ энэ бол өөр нийтлэлийн сэдэв юм.
Цаашид судлах материалын холбоосууд
Анхан шатны түвшин:
- , Преэти Касиредди, Medium дээрх блог нийтлэл
- , Ади Канчерла, Medium дээрх блог нийтлэл
- , Ittai Abraham, блог
- , Ittai Abraham, блог нийтлэл
Лесли Лампортын түвшин:
- , Фишер, Линч, Патерсон, судалгааны бүтээл, 1985
- , Лесли Лампорт, судалгааны нийтлэл, 1998
- , Лесли Лампорт, судалгааны нийтлэл, 2001
Эх сурвалж: www.habr.com