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