So kom ons verbeel ons. 5 katte word in die kamer toegesluit, en om die eienaar te gaan wakker maak, moet hulle almal saam hieroor saamstem, want hulle kan die deur net oopmaak deur saam met vyf van hulle daarop te leun. As een van die katte Schrödinger se kat is en die ander katte is onbewus van sy besluit, ontstaan die vraag: "Hoe kan hulle dit doen?"
In hierdie artikel sal ek jou in eenvoudige terme vertel van die teoretiese komponent van die wêreld van verspreide stelsels en die beginsels van hul werk. En oorweeg ook oppervlakkig die hoofgedagte onderliggend aan Paxos'a.
Wanneer ontwikkelaars wolkinfrastruktuur, verskeie databasisse gebruik, in groepe van 'n groot aantal nodusse werk, is hulle vol vertroue dat die data konsekwent, veilig en altyd beskikbaar sal wees. Maar waar is die waarborge?
Trouens, die waarborge wat ons het, is verskafferswaarborge. Hulle word soos volg in die dokumentasie beskryf: "Hierdie diens is redelik betroubaar, dit het 'n gegewe SLA, moenie bekommerd wees nie, alles sal versprei werk soos jy verwag."
Ons is geneig om in die beste te glo, want slim ooms van groot maatskappye het ons verseker dat alles reg sal wees. Ons vra onsself nie af: hoekom kan dit eintlik enigsins werk nie? Is daar enige formele regverdiging vir die korrekte werking van sulke stelsels?
Ek het onlangs na en was baie geïnspireer deur hierdie tema. Lesings op skool was meer soos klasse in wiskundige analise as enigiets wat met rekenaarstelsels verband hou. Maar dit is presies hoe die belangrikste algoritmes wat ons elke dag gebruik, sonder om dit te vermoed, op een slag bewys is.
Die meeste moderne verspreide stelsels gebruik die Paxos-konsensusalgoritme en sy verskillende wysigings. Die coolste ding is dat die geldigheid en, in beginsel, die moontlikheid van die bestaan van hierdie algoritme eenvoudig met 'n pen en papier bewys kan word. Terselfdertyd, in die praktyk, word die algoritme gebruik in groot stelsels wat op 'n groot aantal nodusse in die wolke werk.
Ligte illustrasie van wat volgende bespreek sal word: die probleem van twee generaalsKom ons kyk na die opwarming .
Ons het twee leërs – rooi en wit. Wit troepe is in die beleërde stad gebaseer. Rooi troepe onder leiding van generaals A1 en A2 is aan twee kante van die stad geleë. Die taak van die rooikoppe is om die wit stad aan te val en te wen. Die leër van elke rooi generaal afsonderlik is egter kleiner as die leër van blankes.
Oorwinningsvoorwaardes vir die rooikoppe: beide generaals moet gelyktydig aanval om 'n numeriese voordeel bo die blankes te hê. Om dit te doen, moet generaals A1 en A2 met mekaar saamstem. As almal afsonderlik aanval, sal die rooikoppe verloor.
Om te onderhandel, kan generaals A1 en A2 boodskappers na mekaar stuur deur die gebied van die wit stad. Die boodskapper kan 'n geallieerde generaal suksesvol bereik of kan deur die vyand onderskep word. Vraag: is daar so 'n volgorde van kommunikasie tussen die rooiharige generaals (die volgorde van stuur van boodskappers van A1 na A2 en omgekeerd van A2 na A1), waarin hulle gewaarborg word om oor 'n aanval op uur X ooreen te kom. Hier, by waarborge word verstaan dat beide generaals ondubbelsinnige bevestiging sal hê dat 'n bondgenoot ('n ander generaal) presies op die vasgestelde tyd X sal aanval.
Gestel A1 stuur 'n boodskapper na A2 met die boodskap: "Kom ons val vandag om middernag aan!". Generaal A1 kan nie aanval sonder bevestiging van Generaal A2 nie. As die boodskapper van A1 bereik het, dan stuur generaal A2 'n bevestiging met die boodskap: "Ja, kom ons maak vandag die blankes vol." Maar nou weet generaal A2 nie of sy boodskapper bereik het of nie, hy het geen waarborge of die aanval gelyktydig sal wees nie. Nou kort generaal A2 weer bevestiging.
As ons hul kommunikasie verder beskryf, blyk dit die volgende: maak nie saak hoeveel boodskapuitruilsiklusse daar is nie, daar is geen manier om beide generaals te waarborg dat hul boodskappe ontvang is nie (met die veronderstelling dat enige van die boodskappers onderskep kan word).
Die twee generaals probleem is 'n goeie illustrasie van 'n baie eenvoudige verspreide stelsel waar daar twee nodusse met onbetroubare kommunikasie is. Ons het dus nie 'n 100% waarborg dat hulle gesinchroniseer is nie. Oor soortgelyke probleme eers op groter skaal later in die artikel.
Bekendstelling van die konsep van verspreide stelsels
'n Verspreide stelsel is 'n groep rekenaars (hierna na verwys as nodusse) wat boodskappe kan uitruil. Elke individuele nodus is een of ander outonome entiteit. 'n Nodus kan take op sy eie verwerk, maar om met ander nodusse te kan kommunikeer, moet dit boodskappe stuur en ontvang.
Hoe boodskappe spesifiek geïmplementeer word, watter protokolle gebruik word - dit interesseer ons nie in hierdie konteks nie. Dit is belangrik dat die nodusse van 'n verspreide stelsel data met mekaar kan uitruil deur boodskappe te stuur.
Die definisie self lyk nie baie ingewikkeld nie, maar hou in gedagte dat 'n verspreide stelsel 'n aantal eienskappe het wat vir ons belangrik sal wees.
Eienskappe van verspreide stelsels
- concurrency – die moontlikheid van voorkoms van gelyktydige of mededingende gebeurtenisse in die stelsel. Verder sal ons oorweeg dat gebeure wat op twee verskillende nodusse plaasgevind het, potensieel gelyktydig is totdat ons 'n duidelike volgorde het waarin hierdie gebeure plaasvind. En gewoonlik doen ons dit nie.
- Geen globale horlosie nie. Ons het nie 'n duidelike volgorde van gebeure nie as gevolg van die gebrek aan 'n globale horlosie. In die gewone wêreld van mense is ons gewoond daaraan dat ons absoluut ure en tyd het. Alles verander wanneer dit kom by verspreide stelsels. Selfs ultra-presiese atoomhorlosies het dryfkrag, en daar is situasies waar ons nie kan sê watter van twee gebeurtenisse eerste gebeur het nie. Daarom kan ons ook nie op tyd staatmaak nie.
- Onafhanklike mislukking van stelsel nodusse. Daar is nog 'n probleem: iets kan verkeerd loop bloot omdat ons nodusse nie ewig is nie. Die hardeskyf kan misluk, die virtuele masjien in die wolk kan herselflaai, die netwerk kan flikker en boodskappe sal verlore gaan. Boonop is daar situasies wanneer die nodusse werk, maar terselfdertyd werk hulle teen die stelsel. Die laaste klas probleme het selfs 'n aparte naam gekry: die probleem . Die gewildste voorbeeld van 'n verspreide stelsel met so 'n probleem is Blockchain. Maar vandag sal ons nie hierdie spesiale klas probleme oorweeg nie. Ons sal belangstel in situasies waarin net een of meer nodusse kan misluk.
- Kommunikasiemodelle (boodskapmodelle) tussen nodusse. Ons het reeds uitgevind dat nodusse kommunikeer deur boodskappe uit te ruil. Daar is twee bekende boodskapmodelle: sinchrone en asinchrone.
Modelle van kommunikasie tussen nodusse in verspreide stelsels
Sinchroniese model - ons weet vir seker dat daar 'n eindige bekende delta van tyd is waarvoor die boodskap gewaarborg is om van een nodus na 'n ander te bereik. As hierdie tyd verby is en die boodskap nie opgedaag het nie, kan ons met veiligheid sê dat die nodus misluk het. In so 'n model het ons 'n voorspelbare wagtyd.
Asinchroniese model – in asinchrone modelle neem ons aan dat die wagtyd eindig is, maar daar is geen tyddelta waarna gewaarborg kan word dat die nodus misluk het nie. Dié. die wagtyd vir 'n boodskap vanaf 'n nodus kan arbitrêr lank wees. Dit is 'n belangrike definisie, en ons sal verder daaroor praat.
Die konsep van konsensus in verspreide sisteme
Voordat u die konsep van konsensus formeel definieer, oorweeg 'n voorbeeld van 'n situasie waar ons dit nodig het, naamlik − Staatsmasjienreplikasie.
Ons het 'n paar verspreide log. Ons wil graag hê dit moet konsekwent wees en identiese data bevat op alle nodusse van 'n verspreide stelsel. Wanneer een van die nodusse 'n nuwe waarde leer wat dit na die log gaan skryf, is sy taak om hierdie waarde aan alle ander nodusse te bied sodat die log op alle nodusse opgedateer word, en die stelsel oorskakel na 'n nuwe konsekwente toestand. Terselfdertyd is dit belangrik dat die nodusse onder mekaar ooreenkom: alle nodusse stem saam dat die voorgestelde nuwe waarde korrek is, alle nodusse aanvaar hierdie waarde, en slegs in hierdie geval kan almal 'n nuwe waarde aanteken.
Met ander woorde: nie een van die nodusse het beswaar gemaak dat hulle meer bygewerkte inligting het nie, en die voorgestelde waarde was verkeerd. 'n Ooreenkoms tussen nodusse en ooreenkoms oor 'n enkele korrekte aanvaarde waarde is die konsensus in 'n verspreide stelsel. Vervolgens sal ons praat oor algoritmes wat 'n verspreide stelsel toelaat om 'n konsensus te bereik met 'n waarborg.
Meer formeel kan ons 'n konsensusalgoritme (of bloot 'n konsensusalgoritme) definieer as een of ander funksie wat 'n verspreide stelsel van toestand A na toestand B neem. Boonop word hierdie toestand deur alle nodusse aanvaar, en alle nodusse kan dit bevestig. Soos dit blyk, is hierdie taak glad nie so onbenullig soos dit met die eerste oogopslag lyk nie.
Eienskappe van die konsensusalgoritme
Die konsensus-algoritme moet drie eienskappe hê sodat die stelsel kan voortbestaan en 'n mate van vordering in die oorgang van staat tot staat kan hê:
- Ooreenkoms – alle korrek werkende nodusse moet dieselfde waarde aanneem (in artikels word hierdie eienskap ook as 'n veiligheidseienskap gevind). Alle nodusse wat nou funksioneer (nie buite werking nie en nie kontak met die res verloor het nie) moet tot 'n ooreenkoms kom en een of ander finale gemeenskaplike waarde aanvaar.
Dit is belangrik om hier te verstaan dat die nodusse in die verspreide stelsel wat ons oorweeg wil saamstem. Dit wil sê, ons praat nou van stelsels waarin iets eenvoudig kan misluk (byvoorbeeld, sommige nodus faal), maar in hierdie stelsel is daar beslis geen nodusse wat doelbewus teen ander werk nie (die taak van die Bisantynse generaals). As gevolg van hierdie eiendom bly die stelsel konsekwent.
- integriteit - as alle korrek werkende nodusse dieselfde waarde bied v, so elke korrek werkende nodus moet hierdie waarde aanvaar v.
- beëindiging - alle korrek werkende nodusse sal uiteindelik 'n waarde aanneem (lewenskrag-eienskap), wat die algoritme in staat stel om vordering in die stelsel te hê. Elke individuele nodus wat reg werk, moet vroeër of later die finale waarde aanvaar en dit bevestig: "Vir my is hierdie waarde waar, ek stem saam met die hele stelsel."
'n Voorbeeld van hoe die konsensusalgoritme werk
Terwyl die eienskappe van die algoritme dalk nie heeltemal duidelik is nie. Daarom sal ons met 'n voorbeeld illustreer deur watter stadiums die eenvoudigste konsensusalgoritme gaan in 'n stelsel met 'n sinchrone boodskapmodel, waarin alle nodusse funksioneer soos verwag, boodskappe nie verlore gaan nie en niks breek nie (gebeur dit regtig?).
- Dit begin alles met 'n huweliksaansoek (Propose). Gestel 'n kliënt koppel aan 'n nodus genaamd "Node 1" en begin 'n transaksie, en gee 'n nuwe waarde aan die node - O. Van nou af sal ons "Node 1" noem aanbod. Hoe moet die voorsteller "Node 1" nou die hele stelsel in kennis stel dat hy vars data het, en hy stuur boodskappe na alle ander nodusse: "Kyk! Ek het die waarde "O" ontvang en ek wil dit neerskryf! Bevestig asseblief dat jy ook "O" in jou log sal aanteken."
- Die volgende fase is om vir die voorgestelde waarde te stem (Stem). Waarvoor is dit? Dit kan gebeur dat ander nodusse meer onlangse inligting ontvang het, en hulle het data oor dieselfde transaksie.
Wanneer die nodus "Node 1" sy propuse stuur, gaan die ander nodusse hul logs na vir data oor hierdie gebeurtenis. As daar geen konflik is nie, kondig die nodusse aan: “Ja, ek het geen ander data vir hierdie gebeurtenis nie. Die 'O'-waarde is die mees onlangse inligting wat ons verdien."In enige ander geval kan die nodusse reageer op "Node 1": "Luister! Ek het meer onlangse data oor hierdie transaksie. Nie "O" nie, maar iets beters."
In die stemstadium kom die nodusse tot 'n besluit: óf hulle aanvaar almal dieselfde waarde, óf een van hulle stem daarteen, wat aandui dat hy meer onlangse data het.
- As die stemronde suksesvol was, en almal was ten gunste, dan beweeg die stelsel na 'n nuwe stadium - aanvaarding van die waarde (Aanvaar). "Node 1" versamel al die antwoorde van ander nodusse en rapporteer: "Almal het saamgestem oor die waarde 'O'! Nou verklaar ek amptelik dat "O" ons nuwe betekenis is, dieselfde vir almal! Skryf dit in jou notaboek neer, moenie vergeet nie. Skryf na jou logboek!"
- Die res van die nodusse stuur bevestiging (Aanvaar) dat hulle die waarde "O" vir hulself neergeskryf het, niks nuuts is gedurende hierdie tyd ontvang nie ('n soort twee-fase commit). Na hierdie belangrike gebeurtenis, is ons van mening dat die verspreide transaksie voltooi is.
Dus bestaan die konsensusalgoritme in 'n eenvoudige geval uit vier stappe: voorstel, stem (stem), aanvaarding (aanvaar), bevestiging van aanvaarding (aanvaar).
As ons op 'n stadium nie 'n ooreenkoms kon bereik nie, word die algoritme weer begin, met inagneming van die inligting wat verskaf is deur die nodusse wat geweier het om die voorgestelde waarde te bevestig.
Konsensusalgoritme in asinchrone stelsel
Voor dit was alles glad, want dit het oor die sinchrone boodskapmodel gegaan. Maar ons weet dat ons in die moderne wêreld gewoond is daaraan om alles asynchronies te doen. Hoe werk 'n soortgelyke algoritme in 'n stelsel met 'n asynchrone boodskapmodel, waar ons glo dat die wagtyd vir 'n reaksie van 'n nodus arbitrêr lank kan wees (terloops, 'n nodusfout kan ook as 'n voorbeeld beskou word wanneer 'n nodus kan arbitrêr lank reageer ).
Noudat ons weet hoe die konsensusalgoritme in beginsel werk, is die vraag vir daardie nuuskierige lesers wat hierdie punt bereik het: hoeveel nodusse in 'n stelsel van N nodusse met 'n asinchroniese boodskapmodel kan daal sodat die stelsel steeds konsensus kan bereik ?
Die korrekte antwoord en rasionaal agter die bederf.Die korrekte antwoord is: 0. As selfs een nodus in 'n asynchrone stelsel afgaan, sal die stelsel nie konsensus kan bereik nie. Hierdie stelling word bewys in die bekende FLP-stelling (1985, Fischer, Lynch, Paterson, skakel na die oorspronklike aan die einde van die artikel): "Die onmoontlikheid om 'n verspreide konsensus te bereik as ten minste een nodus misluk."
Ouens, dan het ons 'n probleem, ons is gewoond daaraan dat alles asynchronies is met ons. En hier is dit. Hoe om voort te gaan om te lewe?
Ons het sopas gepraat oor teorie, oor wiskunde. Wat beteken "konsensus kan nie bereik word nie", vertaal van wiskundige taal na ons s'n - ingenieurswese? Dit beteken dat "nie altyd bereik kan word nie", m.a.w. daar is 'n geval waarin konsensus nie bereikbaar is nie. En wat is hierdie geval?
Dit is presies die skending van die lewendheidseienskap wat hierbo beskryf word. Ons het nie 'n gemeenskaplike ooreenkoms nie, en die stelsel kan nie vorder nie (kan nie in 'n eindige tyd eindig nie) in die geval waar ons nie 'n reaksie van alle nodusse het nie. Want in 'n asinchrone stelsel het ons nie 'n voorspelbare reaksietyd nie en ons kan nie weet of 'n nodus af is of net lank neem om te reageer nie.
Maar in die praktyk kan ons 'n oplossing vind. Laat ons algoritme vir 'n lang tyd kan loop in geval van mislukkings (dit kan moontlik onbepaald loop). Maar in die meeste situasies, wanneer die meeste van die nodusse reg funksioneer, sal ons vordering in die stelsel hê.
In die praktyk het ons te doen met gedeeltelik sinchrone kommunikasiemodelle. Gedeeltelike sinchronisasie word soos volg verstaan: in die algemene geval het ons 'n asinchrone model, maar 'n sekere konsep van "globale stabiliseringstyd" van 'n sekere tydstip word formeel bekendgestel.
Hierdie oomblik in tyd kom dalk nie vir 'n arbitrêre lang tyd nie, maar eendag moet dit kom. Die virtuele wekker sal lui, en van daardie oomblik af kan ons die tyddelta voorspel waarin die boodskappe sal bereik. Van hierdie punt af verander die stelsel van asinchronies na sinchronies. In die praktyk hanteer ons sulke stelsels.
Paxos-algoritme los konsensusprobleme op
is 'n familie van algoritmes wat die konsensusprobleem vir gedeeltelik sinchrone stelsels oplos, mits sommige nodusse kan misluk. Die skrywer van Paxos is . Hy het in 1989 'n formele bewys van die bestaan en korrektheid van die algoritme voorgestel.
Maar die bewys het geblyk geensins triviaal te wees nie. Die eerste publikasie is eers in 1998 vrygestel (33 bladsye) wat die algoritme beskryf. Soos dit geblyk het, was dit uiters moeilik om te verstaan, en in 2001 is 'n verduideliking vir die artikel gepubliseer, wat 14 bladsye beslaan het. Die volumes publikasies word gegee om te wys dat die probleem van konsensus eintlik glad nie eenvoudig is nie, en agter sulke algoritmes is daar 'n groot werk van die slimste mense.
Dit is interessant dat Leslie Lampor self in sy lesing opgemerk het dat daar in die tweede artikel-verduideliking een stelling is, een reël (hy het nie gespesifiseer watter een nie), wat op verskillende maniere geïnterpreteer kan word. En as gevolg hiervan werk 'n groot aantal moderne Paxos-implementerings nie heeltemal korrek nie.
'N Gedetailleerde ontleding van die werk van Paxos sal meer as een artikel neem, so ek sal probeer om die hoofgedagte van die algoritme baie kortliks oor te dra. In die skakels aan die einde van my artikel sal jy materiaal vind om verder in hierdie onderwerp te duik.
Rolle by Paxos
Die Paxos-algoritme het 'n konsep van rolle. Oorweeg drie hoofs (daar is wysigings met bykomende rolle):
- Voorstellers (daar kan ook terme wees: leiers of koördineerders). Dit is die ouens wat die een of ander nuwe betekenis by die gebruiker leer en die rol van leier aanneem. Hulle taak is om 'n rondte voorstelle vir 'n nuwe waarde te loods en verdere aksies van die nodusse te koördineer. Boonop laat Paxos die teenwoordigheid van verskeie leiers in sekere situasies toe.
- Aanvaarders (kiesers). Dit is die nodusse wat stem om 'n bepaalde waarde te aanvaar of te verwerp. Hul rol is baie belangrik, want die besluit hang van hulle af: na watter toestand die stelsel gaan (of nie gaan nie) na die volgende fase van die konsensusalgoritme.
- leerders. Nodusse wat eenvoudig die nuwe aanvaarde waarde aanvaar en skryf wanneer die toestand van die stelsel verander het. Hulle neem nie besluite nie, hulle ontvang net data en kan dit aan die eindgebruiker gee.
Een nodus kan verskeie rolle in verskillende situasies kombineer.
Die konsep van kworum
Ons neem aan dat ons 'n stelsel van N nodusse. En die meeste van hulle F nodusse kan misluk. As F nodusse misluk, moet ons ten minste hê 2F+1 aanvaarder nodusse.
Dit is nodig sodat ons altyd, selfs in die ergste situasie, "goed", korrek werkende nodusse 'n meerderheid het. Dit is F+1 "goeie" nodusse wat ooreengekom het, en die finale waarde sal aanvaar word. Andersins kan daar 'n situasie wees waar verskillende plaaslike groepe verskillende betekenisse sal aanneem en nie onder mekaar sal kan ooreenkom nie. Ons het dus 'n volstrekte meerderheid nodig om die stemming te wen.
Algemene idee van die Paxos-konsensusalgoritme
Die Paxos-algoritme neem twee groot fases aan, wat op hul beurt in twee stappe elk verdeel word:
- Fase 1a: Berei voor. Tydens die voorbereidingsfase lig die leier (voorsteller) alle nodusse in: “Ons begin 'n nuwe stemfase. Ons het 'n nuwe rondte. Die getal van hierdie rondte is n. Ons sal nou begin stem.” Tot dusver rapporteer dit net die begin van 'n nuwe siklus, maar rapporteer nie die nuwe waarde nie. Die taak van hierdie stadium is om 'n nuwe rondte te begin en elkeen van sy unieke nommer in te lig. Die ronde getal is belangrik, dit moet groter wees as alle vorige stemgetalle van alle vorige leiers. Aangesien dit te danke is aan die ronde getal dat ander nodusse in die stelsel sal verstaan hoe vars die leier se data is. Ander nodusse het waarskynlik reeds stemuitslae van heelwat latere rondtes en sal bloot vir die leier sê dat hy agter die tyd is.
- Fase 1b: Belofte. Wanneer die aanvaarder nodusse die nommer van die nuwe stemfase ontvang het, is twee uitkomste moontlik:
- Die getal n van die nuwe stem is groter as die getal van enige van die vorige stemme waaraan die aanvaarder deelgeneem het. Dan stuur die aanvaarder 'n belofte aan die leier dat hy nie meer aan enige stemme met 'n getal minder as n sal deelneem nie. As die aanvaarder reeds vir iets gestem het (dit wil sê, hy het reeds 'n mate van waarde in die tweede fase aanvaar), dan voeg dit die aanvaarde waarde en die nommer van die stemming waaraan hy deelgeneem het by sy belofte.
- Andersins, as die aanvaarder reeds van die hooggetalde stem weet, kan hy eenvoudig die voorbereidingstap ignoreer en nie op die leier reageer nie.
- Fase 2a: Aanvaar. Die leier moet wag vir 'n reaksie van die kworum (die meeste van die nodusse in die stelsel) en as die vereiste aantal antwoorde ontvang word, het hy twee opsies vir die ontwikkeling van gebeure:
- Sommige van die aanvaarders het waardes ingedien waarvoor hulle reeds gestem het. In hierdie geval kies die leier die waarde uit die stem met die hoogste getal. Kom ons noem hierdie waarde x, en stuur 'n boodskap soos hierdie aan alle nodusse: "Aanvaar (n, x)", waar die eerste waarde die stemnommer van sy eie Stel stap is, en die tweede waarde is waarvoor almal bymekaar gekom het, m.a.w. waarde waarvoor ons eintlik stem.
- As nie een van die aanvaarders enige waardes gestuur het nie, maar hulle het bloot belowe om in hierdie rondte te stem, kan die leier hulle nooi om te stem vir hul waarde, die waarde waarvoor hy hoegenaamd 'n leier geword het. Kom ons noem dit y. Dit stuur aan alle nodusse 'n boodskap van die vorm: "Aanvaar (n, y)", in analogie met die vorige uitkoms.
- Fase 2b: Aanvaar. Verder, die aanvaarder nodusse, by ontvangs van die boodskap "Aanvaar (...)", van die leier stem daarmee saam (stuur bevestiging aan alle nodusse dat hulle saamstem met die nuwe waarde) slegs as hulle nie een of ander (ander) die leier om deel te neem aan die stemming met die nommer van die rondte n' > nanders ignoreer hulle die bevestigingsboodskap.
As die meerderheid nodusse die leier geantwoord het, en hulle het almal die nuwe waarde bevestig, dan word die nuwe waarde as aanvaar beskou. Hoera! As die meerderheid nie getik is nie of daar nodusse is wat geweier het om die nuwe waarde te aanvaar, dan begin alles oor.
Dit is hoe die Paxos-algoritme werk. Elkeen van hierdie stadiums het baie subtiliteite, ons het feitlik nie verskillende tipes mislukkings, probleme van veelvuldige leiers en nog baie meer oorweeg nie, maar die doel van hierdie artikel is slegs om die leser bekend te stel aan die wêreld van verspreide rekenaars op die hoogste vlak.
Dit is ook opmerklik dat Paxos nie die enigste in sy soort is nie, daar is ander algoritmes, byvoorbeeld, , maar dit is 'n onderwerp vir 'n ander artikel.
Skakels na materiaal vir verdere studie
Beginner vlak:
- , Preethi Kasireddy, blogartikel oor Medium
- , Adi Kancherla, blogartikel oor Medium
- Ittai Abraham blog
- , Ittai Abraham, blogartikel
Leslie Lamport Vlak:
- Fischer, Lynch en Paterson, navorsingsartikel, 1985
- , Leslie Lamport, navorsingsartikel, 1998
- , Leslie Lamport, navorsingsartikel, 2001
Bron: will.com