Felly gadewch i ni ddychmygu. Mae 5 cath yn cael eu cloi yn yr ystafell, ac er mwyn deffro'r perchennog, mae angen iddynt i gyd gytuno ar hyn, oherwydd dim ond trwy bwyso arno gyda phump ohonynt y gallant agor y drws. Os yw un o'r cathod yn gath Schrödinger ac nad yw'r cathod eraill yn ymwybodol o'i benderfyniad, mae'r cwestiwn yn codi: "Sut allan nhw wneud hyn?"
Yn yr erthygl hon, byddaf yn dweud wrthych mewn termau syml am gydran ddamcaniaethol byd systemau gwasgaredig ac egwyddorion eu gwaith. A hefyd yn arwynebol ystyried y prif syniad sy'n sail i Paxos'a.
Pan fydd datblygwyr yn defnyddio seilweithiau cwmwl, cronfeydd data amrywiol, yn gweithio mewn clystyrau o nifer fawr o nodau, maent yn hyderus y bydd y data yn gyson, yn ddiogel ac ar gael bob amser. Ond ble mae'r gwarantau?
Mewn gwirionedd, gwarantau cyflenwyr yw'r gwarantau sydd gennym. Fe'u disgrifir yn y ddogfennaeth fel a ganlyn: "Mae'r gwasanaeth hwn yn eithaf dibynadwy, mae ganddo CLG penodol, peidiwch â phoeni, bydd popeth yn gweithio wedi'i ddosbarthu fel y disgwyliwch."
Rydyn ni'n tueddu i gredu yn y gorau, oherwydd fe wnaeth ewythrod craff o gwmnïau mawr ein sicrhau y bydd popeth yn iawn. Nid ydym yn gofyn i ni ein hunain: pam, mewn gwirionedd, y gall hyn weithio o gwbl? A oes unrhyw gyfiawnhad ffurfiol dros weithredu systemau o'r fath yn gywir?
Es i yn ddiweddar i a chafodd ei ysbrydoli'n fawr gan y thema hon. Roedd darlithoedd yn yr ysgol yn debycach i ddosbarthiadau dadansoddi mathemategol nag unrhyw beth yn ymwneud â systemau cyfrifiadurol. Ond dyma'n union sut y profwyd yr algorithmau pwysicaf a ddefnyddiwn bob dydd, heb amau hynny, ar un adeg.
Mae'r rhan fwyaf o systemau dosbarthedig modern yn defnyddio algorithm consensws Paxos a'i amrywiol addasiadau. Y peth cŵl yw y gellir profi dilysrwydd ac, mewn egwyddor, y posibilrwydd o fodolaeth yr algorithm hwn yn syml gyda beiro a phapur. Ar yr un pryd, yn ymarferol, defnyddir yr algorithm mewn systemau mawr sy'n gweithredu ar nifer fawr o nodau yn y cymylau.
Darlun ysgafn o'r hyn a drafodir nesaf: problem dau gadfridogGadewch i ni edrych ar y cynhesu .
Mae gennym ddwy fyddin - coch a gwyn. Mae milwyr gwyn wedi'u lleoli yn y ddinas dan warchae. Mae milwyr coch dan arweiniad cadfridogion A1 ac A2 wedi'u lleoli ar ddwy ochr y ddinas. Tasg y pennau coch yw ymosod ar y ddinas wen ac ennill. Fodd bynnag, mae byddin pob cadfridog coch yn unigol yn llai na byddin y gwyn.
Amodau buddugoliaeth i'r pengochiaid: rhaid i'r ddau gadfridog ymosod ar yr un pryd er mwyn cael mantais rifiadol dros y gwyn. I wneud hyn, mae angen i gadfridogion A1 ac A2 gytuno â'i gilydd. Os bydd pawb yn ymosod ar wahân, bydd y pennau coch yn colli.
I drafod, gall cadfridogion A1 ac A2 anfon negeswyr at ei gilydd trwy diriogaeth y ddinas wen. Gall y negesydd gyrraedd cadfridog cynghreiriol yn llwyddiannus neu gall y gelyn gael ei ryng-gipio. Cwestiwn: a oes dilyniant o'r fath o gyfathrebu rhwng y cadfridogion gwallt coch (y dilyniant o anfon negeswyr o A1 i A2 ac i'r gwrthwyneb o A2 i A1), lle maent yn sicr o gytuno ar ymosodiad ar awr X. Yma, trwy warantau deellir y bydd gan y ddau gadfridog gadarnhad diamwys y bydd cynghreiriad (cadfridog arall) yn ymosod yn union ar yr amser penodedig X.
Tybiwch fod A1 yn anfon negesydd i A2 gyda'r neges: "Gadewch i ni ymosod heddiw am hanner nos!". Ni all Cyffredinol A1 ymosod heb gadarnhad gan General A2. Os yw'r negesydd o A1 wedi cyrraedd, yna mae cyffredinol A2 yn anfon cadarnhad gyda'r neges: "Ie, gadewch i ni lenwi'r gwyn heddiw." Ond nawr nid yw'r Cadfridog A2 yn gwybod a yw ei negesydd wedi cyrraedd ai peidio, nid oes ganddo unrhyw sicrwydd a fydd yr ymosodiad ar yr un pryd. Nawr mae angen cadarnhad eto ar General A2.
Os byddwn yn disgrifio eu cyfathrebu ymhellach, mae'n troi allan fel a ganlyn: ni waeth faint o gylchoedd cyfnewid negeseuon sydd, nid oes unrhyw ffordd i warantu'r ddau gadfridog bod eu negeseuon wedi'u derbyn (gan dybio y gellir rhyng-gipio'r naill neges neu'r llall).
Mae problem y ddau gadfridog yn enghraifft wych o system ddosbarthedig syml iawn lle mae dau nod gyda chyfathrebu annibynadwy. Felly nid oes gennym warant 100% eu bod yn cael eu cydamseru. Ynglŷn â phroblemau tebyg yn unig ar raddfa fwy yn ddiweddarach yn yr erthygl.
Cyflwyno'r cysyniad o systemau gwasgaredig
Mae system ddosbarthedig yn grŵp o gyfrifiaduron (y cyfeirir atynt o hyn ymlaen fel nodau) sy'n gallu cyfnewid negeseuon. Mae pob nod unigol yn rhyw endid ymreolaethol. Gall nod brosesu tasgau ar ei ben ei hun, ond er mwyn cyfathrebu â nodau eraill, mae angen iddo anfon a derbyn negeseuon.
Sut mae negeseuon yn cael eu gweithredu'n benodol, pa brotocolau a ddefnyddir - nid yw hyn o ddiddordeb i ni yn y cyd-destun hwn. Mae'n bwysig bod nodau system ddosbarthedig yn gallu cyfnewid data â'i gilydd trwy anfon negeseuon.
Nid yw'r diffiniad ei hun yn edrych yn gymhleth iawn, ond cofiwch fod gan system ddosbarthedig nifer o nodweddion a fydd yn bwysig i ni.
Nodweddion systemau gwasgaredig
- Cydlyniant – y posibilrwydd o ddigwyddiadau cydamserol neu gystadleuol yn y system. At hynny, byddwn yn ystyried y gallai digwyddiadau a ddigwyddodd ar ddau nod gwahanol fod yn gydamserol nes bod gennym drefn glir ar gyfer y digwyddiadau hyn. Ac fel arfer nid ydym yn gwneud hynny.
- Dim cloc byd-eang. Nid oes gennym drefn glir o ddigwyddiadau oherwydd diffyg cloc byd-eang. Ym myd cyffredin pobl, rydyn ni wedi arfer â'r ffaith bod gennym ni oriau ac amser o gwbl. Mae popeth yn newid o ran systemau gwasgaredig. Mae gan hyd yn oed glociau atomig tra-fanwl drifft, ac mae sefyllfaoedd lle na allwn ddweud pa un o ddau ddigwyddiad a ddigwyddodd gyntaf. Felly, ni allwn ddibynnu ar amser ychwaith.
- Methiant annibynnol nodau system. Mae problem arall: gall rhywbeth fynd o'i le yn syml oherwydd nad yw ein nodau yn dragwyddol. Efallai y bydd y gyriant caled yn methu, efallai y bydd y peiriant rhithwir yn y cwmwl yn ailgychwyn, efallai y bydd y rhwydwaith yn blincio a bydd negeseuon yn cael eu colli. Ar ben hynny, mae yna sefyllfaoedd pan fydd y nodau'n gweithio, ond ar yr un pryd maen nhw'n gweithio yn erbyn y system. Derbyniodd y dosbarth olaf o broblemau enw ar wahân hyd yn oed: y broblem . Yr enghraifft fwyaf poblogaidd o system ddosbarthedig gyda phroblem o'r fath yw Blockchain. Ond heddiw ni fyddwn yn ystyried y dosbarth arbennig hwn o broblemau. Bydd gennym ddiddordeb mewn sefyllfaoedd lle gall un nod neu fwy fethu.
- Modelau cyfathrebu (modelau negeseuon) rhwng nodau. Rydym eisoes wedi darganfod bod nodau'n cyfathrebu trwy gyfnewid negeseuon. Mae dau fodel negeseuon adnabyddus: cydamserol ac asyncronig.
Modelau cyfathrebu rhwng nodau mewn systemau gwasgaredig
Model cydamserol — gwyddom yn sicr fod delta amser hysbys meidrol y mae'r neges yn sicr o'i chyrraedd o'r naill nod i'r llall. Os yw'r amser hwn ar ben ac nad yw'r neges wedi cyrraedd, gallwn ddweud yn ddiogel bod y nod wedi methu. Mewn model o'r fath, mae gennym amser aros rhagweladwy.
Model asyncronig – mewn modelau asyncronaidd, tybiwn fod yr amser aros yn gyfyngedig, ond nid oes amser delta ar ôl hynny gellir gwarantu bod y nod wedi methu. Y rhai. gall yr amser aros am neges o nod fod yn fympwyol o hir. Mae hwn yn ddiffiniad pwysig, a byddwn yn siarad amdano ymhellach.
Y cysyniad o gonsensws mewn systemau gwasgaredig
Cyn diffinio’r cysyniad o gonsensws yn ffurfiol, ystyriwch enghraifft o sefyllfa lle mae ei angen arnom, sef − Dyblygiad Peiriant Gwladol.
Mae gennym rywfaint o log wedi'i ddosbarthu. Hoffem iddo fod yn gyson ac yn cynnwys data union yr un fath ar holl nodau system ddosbarthedig. Pan fydd un o'r nodau'n dysgu gwerth newydd y mae'n mynd i'w ysgrifennu at y log, ei dasg yw cynnig y gwerth hwn i bob nod arall fel bod y log yn cael ei ddiweddaru ar bob nod, a bod y system yn newid i gyflwr cyson newydd. Ar yr un pryd, mae'n bwysig bod y nodau'n cytuno ymhlith ei gilydd: mae pob nod yn cytuno bod y gwerth newydd arfaethedig yn gywir, mae pob nod yn derbyn y gwerth hwn, a dim ond yn yr achos hwn y gall pawb logio gwerth newydd.
Mewn geiriau eraill: nid oedd yr un o'r nodau yn gwrthwynebu bod ganddynt wybodaeth fwy diweddar, a bod y gwerth arfaethedig yn anghywir. Cytundeb rhwng nodau a chytundeb ar un gwerth derbyniol cywir yw'r consensws mewn system ddosbarthedig. Nesaf, byddwn yn siarad am algorithmau sy'n caniatáu i system ddosbarthedig gyrraedd consensws gyda gwarant.
Yn fwy ffurfiol, gallwn ddiffinio algorithm consensws (neu algorithm consensws yn unig) fel rhyw swyddogaeth sy'n cymryd system ddosbarthedig o gyflwr A i gyflwr B. Ar ben hynny, mae'r cyflwr hwn yn cael ei dderbyn gan bob nod, a gall pob nod ei gadarnhau. Fel y digwyddodd, nid yw'r dasg hon mor ddibwys o gwbl ag y mae'n ymddangos ar yr olwg gyntaf.
Priodweddau'r algorithm consensws
Rhaid i'r algorithm consensws fod â thri phriodwedd er mwyn i'r system barhau i fodoli a chael rhywfaint o gynnydd yn y trawsnewid o'r wladwriaeth i'r wladwriaeth:
- Cytundeb – rhaid i bob nod sy'n gweithio'n gywir gymryd yr un gwerth (mewn erthyglau mae'r eiddo hwn hefyd yn eiddo diogelwch). Rhaid i bob nod sydd bellach yn gweithredu (ddim allan o drefn a heb golli cysylltiad â'r gweddill) ddod i gytundeb a derbyn rhywfaint o werth cyffredin terfynol.
Mae'n bwysig deall yma bod y nodau yn y system ddosbarthedig yr ydym yn ei hystyried eisiau cytuno. Hynny yw, rydym nawr yn sôn am systemau lle gall rhywbeth fethu'n syml (er enghraifft, mae rhai nod yn methu), ond yn y system hon yn bendant nid oes nodau sy'n gweithio'n fwriadol yn erbyn eraill (tasg y cadfridogion Bysantaidd). Oherwydd yr eiddo hwn, mae'r system yn parhau'n gyson.
- Uniondeb - os yw'r holl nodau sy'n gweithio'n gywir yn cynnig yr un gwerth v, felly mae'n rhaid i bob nod sy'n gweithio'n gywir dderbyn y gwerth hwn v.
- Terfynu - Bydd yr holl nodau sy'n gweithio'n gywir yn y pen draw yn cymryd rhywfaint o werth (eiddo bywiogrwydd), sy'n caniatáu i'r algorithm gael cynnydd yn y system. Rhaid i bob nod unigol sy'n gweithio'n gywir dderbyn y gwerth terfynol yn hwyr neu'n hwyrach a'i gadarnhau: "I mi, mae'r gwerth hwn yn wir, rwy'n cytuno â'r system gyfan."
Enghraifft o sut mae'r algorithm consensws yn gweithio
Er efallai na fydd priodweddau'r algorithm yn gwbl glir. Felly, byddwn yn dangos gydag enghraifft pa gamau y mae'r algorithm consensws symlaf yn mynd drwyddynt mewn system gyda model negeseuon cydamserol, lle mae pob nod yn gweithredu yn ôl y disgwyl, nid yw negeseuon yn cael eu colli a dim byd yn torri (a yw hyn yn digwydd mewn gwirionedd?).
- Mae'r cyfan yn dechrau gyda chynnig priodas (Cynnig). Tybiwch fod cleient yn cysylltu â nod o'r enw "Nôd 1" ac yn dechrau trafodiad, gan drosglwyddo gwerth newydd i'r nod - O. O hyn ymlaen, byddwn yn galw "Nôd 1" i gynnig. Gan fod yn rhaid i'r cynigydd "Nôd 1" bellach hysbysu'r system gyfan bod ganddo ddata ffres, ac mae'n anfon negeseuon i bob nod arall: "Edrychwch! Derbyniais y gwerth "O", ac rwyf am ei ysgrifennu i lawr! Cadarnhewch y byddwch hefyd yn cofnodi "O" yn eich log."
- Y cam nesaf yw pleidleisio dros y gwerth arfaethedig (Pleidleisio). Beth yw ei ddiben? Gall ddigwydd bod nodau eraill wedi derbyn gwybodaeth fwy diweddar, ac mae ganddynt ddata ar yr un trafodiad.
Pan fydd y nod "Nôd 1" yn anfon ei brop, mae'r nodau eraill yn gwirio eu logiau am ddata ar y digwyddiad hwn. Os nad oes gwrthdaro, mae'r nodau'n cyhoeddi: “Oes, nid oes gennyf unrhyw ddata arall ar gyfer y digwyddiad hwn. Y gwerth 'O' yw'r wybodaeth fwyaf diweddar yr ydym yn ei haeddu."Mewn unrhyw achos arall, gall y nodau ymateb i "Nôd 1": "Gwrandewch! Mae gennyf ddata mwy diweddar ar y trafodiad hwn. Nid "O", ond rhywbeth gwell."
Yn y cyfnod pleidleisio, daw’r nodau i benderfyniad: naill ai maent i gyd yn derbyn yr un gwerth, neu mae un ohonynt yn pleidleisio yn erbyn, gan ddynodi bod ganddo ddata mwy diweddar.
- Os oedd y rownd bleidleisio yn llwyddiannus, a phawb o blaid, yna mae'r system yn symud i gyfnod newydd - derbyn y gwerth (Derbyn). Mae "Node 1" yn casglu'r holl ymatebion o nodau ac adroddiadau eraill: "Roedd pawb yn cytuno ar y gwerth 'O'! Nawr rwy'n datgan yn swyddogol mai "O" yw ein hystyr newydd, yr un peth i bawb! Ysgrifennwch ef yn eich llyfr nodiadau, peidiwch ag anghofio. Ysgrifennwch at eich log!"
- Mae gweddill y nodau yn anfon cadarnhad (Derbyniwyd) eu bod wedi ysgrifennu'r gwerth “O” drostynt eu hunain, nid oes dim byd newydd wedi'i dderbyn yn ystod y cyfnod hwn (math o ymrwymiad dau gam). Ar ôl y digwyddiad pwysig hwn, rydym o'r farn bod y trafodiad a ddosbarthwyd wedi'i gwblhau.
Felly, mae'r algorithm consensws mewn achos syml yn cynnwys pedwar cam: cynnig, pleidleisio (pleidleisio), derbyn (derbyn), cadarnhad o dderbyn (derbyniwyd).
Os na allem ddod i gytundeb ar ryw gam, yna caiff yr algorithm ei ailgychwyn, gan ystyried y wybodaeth a ddarparwyd gan y nodau a wrthododd gadarnhau'r gwerth arfaethedig.
Algorithm consensws yn y system asyncronig
Cyn hynny, roedd popeth yn llyfn, oherwydd roedd yn ymwneud â'r model negeseuon cydamserol. Ond rydyn ni'n gwybod ein bod ni'n gyfarwydd â gwneud popeth yn anghydamserol yn y byd modern. Sut mae algorithm tebyg yn gweithio mewn system gyda model negeseuon asyncronaidd, lle credwn y gall yr amser aros am ymateb gan nod fod yn fympwyol o hir (gyda llaw, gellir ystyried methiant nod hefyd fel enghraifft pan fydd nod yn gallu ymateb yn fympwyol o hir).
Nawr ein bod ni'n gwybod sut mae'r algorithm consensws yn gweithio mewn egwyddor, mae'r cwestiwn ar gyfer y darllenwyr chwilfrydig hynny sydd wedi cyrraedd y pwynt hwn: faint o nodau mewn system o nodau N gyda model neges asyncronig all fynd i lawr fel bod y system yn gallu cyrraedd consensws o hyd ?
Yr ateb cywir a'r rhesymeg y tu ôl i'r sbwyliwr.Yr ateb cywir yw: 0. Os bydd hyd yn oed un nod mewn system asyncronig yn mynd i lawr, ni fydd y system yn gallu cyrraedd consensws. Mae’r datganiad hwn wedi’i brofi yn y theorem FLP adnabyddus (1985, Fischer, Lynch, Paterson, dolen i’r gwreiddiol ar ddiwedd yr erthygl): “Amhosibilrwydd cyrraedd consensws gwasgaredig os bydd o leiaf un nod yn methu.”
Guys, yna mae gennym broblem, rydym wedi arfer â'r ffaith bod popeth yn asyncronaidd â ni. A dyma fe. Sut i barhau i fyw?
Rydym newydd siarad am theori, am fathemateg. Beth mae “na ellir cyrraedd consensws” yn ei olygu, wrth gyfieithu o iaith fathemategol i'n un ni - peirianneg? Mae hyn yn golygu "na ellir ei gyflawni bob amser", h.y. mae achos lle nad yw consensws yn gyraeddadwy. A beth yw'r achos hwn?
Mae hyn yn union y groes i'r eiddo bywiogrwydd a ddisgrifir uchod. Nid oes gennym gytundeb cyffredin, ac ni all y system symud ymlaen (ni all ddod i ben mewn amser cyfyngedig) yn yr achos lle nad oes gennym ymateb gan bob nod. Oherwydd mewn system asyncronaidd nid oes gennym amser ymateb rhagweladwy ac ni allwn wybod a yw nod i lawr neu dim ond yn cymryd amser hir i ymateb.
Ond yn ymarferol, gallwn ddod o hyd i ateb. Gadewch i'n algorithm allu rhedeg am amser hir rhag ofn y bydd methiannau (mae'n bosibl y gall redeg am gyfnod amhenodol). Ond yn y rhan fwyaf o sefyllfaoedd, pan fydd y rhan fwyaf o'r nodau'n gweithio'n gywir, bydd gennym ni gynnydd yn y system.
Yn ymarferol, rydym yn delio â modelau cyfathrebu rhannol gydamserol. Deellir synchronism rhannol fel a ganlyn: yn yr achos cyffredinol, mae gennym fodel asyncronaidd, ond mae cysyniad penodol o "amser sefydlogi byd-eang" o gyfnod penodol mewn amser yn cael ei gyflwyno'n ffurfiol.
Efallai na fydd y foment hon mewn amser yn dod am amser mympwyol o hir, ond un diwrnod mae'n rhaid iddo ddod. Bydd y cloc larwm rhithwir yn canu, ac o'r eiliad honno ymlaen gallwn ragweld yr amser delta y bydd y negeseuon yn cyrraedd. O'r pwynt hwn ymlaen, mae'r system yn troi o asyncronig i gydamserol. Yn ymarferol, rydym yn delio â systemau o'r fath.
Mae algorithm Paxos yn datrys problemau consensws
yn deulu o algorithmau sy'n datrys y broblem consensws ar gyfer systemau rhannol gydamserol, ar yr amod y gall rhai nodau fethu. Awdwr Paxos yw . Cynigiodd brawf ffurfiol o fodolaeth a chywirdeb yr algorithm yn 1989.
Ond nid oedd y prawf yn ddibwys o bell ffordd. Dim ond yn 1998 y rhyddhawyd y cyhoeddiad cyntaf (33 tudalen) yn disgrifio'r algorithm. Fel y digwyddodd, roedd yn hynod anodd ei ddeall, ac yn 2001 cyhoeddwyd esboniad am yr erthygl, a gymerodd 14 tudalen. Rhoddir y cyfrolau o gyhoeddiadau er mwyn dangos nad yw'r broblem o gonsensws yn syml o gwbl mewn gwirionedd, a thu ôl i algorithmau o'r fath mae yna waith enfawr gan y bobl fwyaf craff.
Mae'n ddiddorol bod Leslie Lampor ei hun yn ei ddarlith wedi nodi bod yn yr ail erthygl-esboniad un datganiad, un llinell (ni nododd pa un), y gellir ei ddehongli mewn gwahanol ffyrdd. Ac oherwydd hyn, nid yw nifer fawr o weithrediadau Paxos modern yn gweithio'n hollol gywir.
Bydd dadansoddiad manwl o waith Paxos yn cymryd mwy nag un erthygl, felly byddaf yn ceisio cyfleu prif syniad yr algorithm yn fyr iawn. Yn y dolenni ar ddiwedd fy erthygl fe welwch ddeunyddiau ar gyfer plymio ymhellach i'r pwnc hwn.
Rolau yn Paxos
Mae gan algorithm Paxos gysyniad o rolau. Ystyriwch dri phrif rai (mae yna addasiadau gyda rolau ychwanegol):
- Cynigwyr (efallai y bydd termau hefyd: arweinwyr neu gydlynwyr). Dyma'r dynion sy'n dysgu am ryw ystyr newydd gan y defnyddiwr ac yn cymryd rôl yr arweinydd. Eu tasg yw lansio rownd o gynigion ar gyfer gwerth newydd a chydlynu camau gweithredu pellach y nodau. Ar ben hynny, mae Paxos yn caniatáu presenoldeb sawl arweinydd mewn rhai sefyllfaoedd.
- Derbynwyr (Pleidleiswyr). Dyma'r nodau sy'n pleidleisio i dderbyn neu wrthod gwerth penodol. Mae eu rôl yn bwysig iawn, oherwydd mae'r penderfyniad yn dibynnu arnynt: i ba gyflwr y bydd y system yn mynd (neu beidio) ar ôl cam nesaf yr algorithm consensws.
- Dysgwyr. Nodau sy'n derbyn ac yn ysgrifennu'r gwerth derbyniol newydd pan fydd cyflwr y system wedi newid. Nid ydynt yn gwneud penderfyniadau, maent yn derbyn data a gallant ei roi i'r defnyddiwr terfynol.
Gall un nod gyfuno sawl rôl mewn gwahanol sefyllfaoedd.
Y cysyniad o gworwm
Tybiwn fod gennym system o N nodau. A'r rhan fwyaf ohonyn nhw F gall nodau fethu. Os bydd nodau F yn methu, yna dylem gael o leiaf 2F+1 nodau derbynnydd.
Mae hyn yn angenrheidiol fel ein bod bob amser, hyd yn oed yn y sefyllfa waethaf, nodau “da”, sy'n gweithio'n gywir, â mwyafrif. Hynny yw F+1 nodau "da" a gytunwyd, a bydd y gwerth terfynol yn cael ei dderbyn. Fel arall, efallai y bydd sefyllfa lle bydd gwahanol grwpiau lleol yn cymryd gwahanol ystyron ac na fyddant yn gallu cytuno ymhlith ei gilydd. Felly mae angen mwyafrif llwyr i ennill y bleidlais.
Syniad cyffredinol o algorithm consensws Paxos
Mae algorithm Paxos yn rhagdybio dau gam mawr, sydd yn eu tro yn cael eu rhannu'n ddau gam yr un:
- Cam 1a: Paratoi. Yn ystod y cyfnod paratoi, mae'r arweinydd (cynigydd) yn hysbysu pob nod: “Rydym yn dechrau cyfnod pleidleisio newydd. Mae gennym rownd newydd. Rhif y rownd hon yw n. Byddwn yn dechrau pleidleisio nawr." Hyd yn hyn, dim ond dechrau cylch newydd y mae'n ei adrodd, ond nid yw'n adrodd ar y gwerth newydd. Tasg y cam hwn yw cychwyn rownd newydd a hysbysu pawb o'i rif unigryw. Mae'r rhif crwn yn bwysig, rhaid iddo fod yn fwy na'r holl rifau pleidleisio blaenorol gan yr holl arweinwyr blaenorol. Gan mai diolch i'r rhif crwn y bydd nodau eraill yn y system yn deall pa mor ffres yw data'r arweinydd. Mae'n debyg bod gan nodau eraill ganlyniadau pleidleisio o rowndiau llawer diweddarach eisoes a byddant yn dweud wrth yr arweinydd ei fod ar ei hôl hi.
- Cam 1b: Addewid. Pan fydd y nodau derbyn wedi derbyn rhif y cam pleidleisio newydd, mae dau ganlyniad yn bosibl:
- Mae rhif n y bleidlais newydd yn fwy na nifer unrhyw un o'r pleidleisiau blaenorol y cymerodd y derbynnydd ran ynddynt. Yna mae'r derbynnydd yn anfon addewid i'r arweinydd na fydd bellach yn cymryd rhan mewn unrhyw bleidleisiau gyda nifer llai nag n. Os yw'r derbynnydd eisoes wedi pleidleisio dros rywbeth (hynny yw, ei fod eisoes wedi derbyn rhywfaint o werth yn yr ail gam), yna mae'n atodi'r gwerth derbyniol a rhif y bleidlais y cymerodd ran ynddi i'w addewid.
- Fel arall, os yw'r derbynnydd eisoes yn gwybod am y bleidlais â nifer uchel, gall anwybyddu'r cam paratoi a pheidio ag ymateb i'r arweinydd.
- Cam 2a: Derbyn. Mae angen i'r arweinydd aros am ymateb gan y cworwm (y rhan fwyaf o'r nodau yn y system) ac, os derbynnir y nifer gofynnol o ymatebion, yna mae ganddo ddau opsiwn ar gyfer datblygu digwyddiadau:
- Mae rhai o'r derbynwyr wedi cyflwyno gwerthoedd y maent eisoes wedi pleidleisio drostynt. Yn yr achos hwn, mae'r arweinydd yn dewis y gwerth o'r bleidlais gyda'r nifer uchaf. Gadewch i ni alw'r gwerth hwn yn x, ac anfon neges fel hon i bob nod: "Derbyn (n, x)", lle mai'r gwerth cyntaf yw'r rhif pleidleisio o'i gam Cynnig ei hun, a'r ail werth yw'r hyn y casglodd pawb amdano, h.y. gwerth yr ydym, mewn gwirionedd, yn pleidleisio amdano.
- Os na anfonodd unrhyw un o'r derbynwyr unrhyw werthoedd, ond eu bod yn syml wedi addo pleidleisio yn y rownd hon, gall yr arweinydd eu gwahodd i bleidleisio dros eu gwerth, y gwerth y daeth yn arweinydd o gwbl. Gadewch i ni ei alw y. Mae'n anfon neges o'r ffurflen i bob nod: "Derbyn (n, y)", trwy gyfatebiaeth â'r canlyniad blaenorol.
- Cam 2b: Derbyniwyd. Ymhellach, mae'r nodau derbynnydd, ar ôl derbyn y neges "Derbyn (...)", gan yr arweinydd yn cytuno ag ef (anfonwch gadarnhad i bob nod eu bod yn cytuno â'r gwerth newydd) dim ond os nad ydynt wedi addo rhai (eraill) y arweinydd i gymryd rhan mewn pleidleisio gyda rhif y rownd n' > nfel arall maent yn anwybyddu'r anogwr cadarnhau.
Os atebodd y mwyafrif o nodau yr arweinydd, a'u bod i gyd yn cadarnhau'r gwerth newydd, yna ystyrir bod y gwerth newydd yn dderbyniol. Hwre! Os nad yw'r mwyafrif wedi'i deipio neu os oes nodau a wrthododd dderbyn y gwerth newydd, yna mae popeth yn dechrau drosodd.
Dyma sut mae algorithm Paxos yn gweithio. Mae gan bob un o'r camau hyn lawer o gynildeb, yn ymarferol ni wnaethom ystyried gwahanol fathau o fethiannau, problemau arweinwyr lluosog, a llawer mwy, ond pwrpas yr erthygl hon yw cyflwyno'r darllenydd i fyd cyfrifiadura gwasgaredig ar y lefel uchaf yn unig.
Mae'n werth nodi hefyd nad Paxos yw'r unig un o'i fath, mae yna algorithmau eraill, er enghraifft, , ond mae hwn yn bwnc ar gyfer erthygl arall.
Dolenni i ddeunyddiau ar gyfer astudiaeth bellach
Lefel dechreuwyr:
- , Preethi Kasireddy, erthygl blog ar Ganolig
- , Adi Kancherla, erthygl blog ar Ganolig
- Ittai Abraham blog
- , Ittai Abraham, erthygl blog
Lefel Leslie Lamport:
- Fischer, Lynch a Paterson, papur ymchwil, 1985
- , Leslie Lamport, papur ymchwil, 1998
- , Leslie Lamport, papur ymchwil, 2001
Ffynhonnell: hab.com