{"id":37335,"date":"2019-10-31T22:17:01","date_gmt":"2019-10-31T19:17:01","guid":{"rendered":"https:\/\/prohoster.info\/blog\/kot-shryodingera-bez-korobki-problema-konsensusa-v-raspredelyonnyh-sistemah\/"},"modified":"2019-10-31T22:17:01","modified_gmt":"2019-10-31T19:17:01","slug":"kot-shryodingera-bez-korobki-problema-konsensusa-v-raspredelyonnyh-sistemah","status":"publish","type":"post","link":"https:\/\/prohoster.info\/sv\/blog\/administrirovanie\/kot-shryodingera-bez-korobki-problema-konsensusa-v-raspredelyonnyh-sistemah","title":{"rendered":"Schr\u00f6dingers katt utan l\u00e5da: konsensusproblemet i distribuerade system","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

S\u00e5, l\u00e5t oss f\u00f6rest\u00e4lla oss. I rummet \u00e4r 5 katter inst\u00e4ngda, och f\u00f6r att kunna g\u00e5 och v\u00e4cka sin \u00e4gare m\u00e5ste de f\u00f6rst komma \u00f6verens st\u00e4rker de tillsammans, eftersom de endast kan \u00f6ppna d\u00f6rren genom att trycka sig p\u00e5 den fem och fem. Om en av katterna \u00e4r Schr\u00f6dingers katt, och de andra katterna inte k\u00e4nner till hans beslut, uppst\u00e5r fr\u00e5gan: \"Hur kan de g\u00f6ra det?\" <\/p>\n

I den h\u00e4r artikeln kommer jag p\u00e5 ett enkelt s\u00e4tt att f\u00f6rklara den teoretiska aspekten av distribuerade system och principerna bakom deras funktion. Jag kommer ocks\u00e5 att kortfattat g\u00e5 igenom den huvudsakliga id\u00e9n som ligger till grund f\u00f6r Paxos. <\/p>\n

\"Schr\u00f6dingers
\n<\/a><\/noindex>
\nN\u00e4r utvecklare anv\u00e4nder molninfrastrukturer, olika databaser och arbetar i kluster med ett stort antal noder, \u00e4r de s\u00e4kra p\u00e5 att data kommer att vara intakta, s\u00e4kra och alltid tillg\u00e4ngliga. Men var kommer garantierna ifr\u00e5n?<\/p>\n

I grunden \u00e4r de garantier vi har \u2013 garantier fr\u00e5n leverant\u00f6ren. De beskrivs i dokumentationen ungef\u00e4r s\u00e5 h\u00e4r: \"Denna tj\u00e4nst \u00e4r tillr\u00e4ckligt p\u00e5litlig, den har en angiven SLA, oroa dig inte, allt kommer att fungera distribuerat som du f\u00f6rv\u00e4ntar dig.\" <\/p>\n

Vi tenderar att tro p\u00e5 det b\u00e4sta, eftersom kloka m\u00e4n fr\u00e5n stora f\u00f6retag har f\u00f6rs\u00e4krat oss om att allt kommer att g\u00e5 bra. Vi st\u00e4ller oss inte fr\u00e5gan: varf\u00f6r kan detta \u00f6verhuvudtaget fungera? Finns det n\u00e5gon formell motivering till korrektheten i s\u00e5dana system?<\/p>\n

Nyligen bes\u00f6kte jag skolan f\u00f6r distribuerad databehandling<\/a><\/noindex> och blev v\u00e4ldigt inspirerad av detta \u00e4mne. F\u00f6rel\u00e4sningarna i skolan liknade mer lektioner i matematisk analys \u00e4n n\u00e5got som var relaterat till datorsystem. Men just s\u00e5 bevisades i sin tid de viktiga algoritmer som vi anv\u00e4nder varje dag utan att vi ens \u00e4r medvetna om det. <\/p>\n

I de flesta moderna distribuerade system anv\u00e4nds konsensusalgoritmen Paxos och dess olika variationer. Det mest fantastiska \u00e4r att bevisbarheten och i princip sj\u00e4lva m\u00f6jligheten av existensen av denna algoritm kan bevisas helt enkelt med hj\u00e4lp av en penna och papper. Samtidigt till\u00e4mpas algoritmen i praktiken i stora system som arbetar p\u00e5 ett enormt antal noder i molnets milj\u00f6. <\/p>\n

En l\u00e4ttfattlig illustration av vad som kommer att diskuteras h\u00e4rn\u00e4st: tv\u00e5 generalers problem<\/b>L\u00e5t oss f\u00f6r uppv\u00e4rmning analysera tv\u00e5 generalers problem<\/a><\/noindex>. <\/p>\n

Vi har tv\u00e5 arm\u00e9er \u2013 den r\u00f6da och den vita. De vita trupperna \u00e4r baserade i den bel\u00e4grade staden. De r\u00f6da trupperna, ledda av generalerna A1 och A2, \u00e4r placerade p\u00e5 tv\u00e5 sidor av staden. M\u00e5let f\u00f6r de r\u00f6da \u00e4r att attackera den vita staden och segra. Men varje r\u00f6d generals arm\u00e9 \u00e4r mindre \u00e4n de vita.<\/p>\n

\"Schr\u00f6dingers
\n
\nVillkoren f\u00f6r seger f\u00f6r de r\u00f6da: b\u00e5da generalerna m\u00e5ste attackera samtidigt f\u00f6r att ha ett numer\u00e4rt \u00f6verl\u00e4ge \u00f6ver de vita. F\u00f6r detta m\u00e5ste generalerna A1 och A2 enas med varandra. Om de attackerar var f\u00f6r sig, kommer de r\u00f6da att f\u00f6rlora. <\/p>\n

F\u00f6r att enas kan generalerna A1 och A2 skicka budb\u00e4rare till varandra \u00f6ver den vita stadens territorium. Budb\u00e4raren kan n\u00e5 sin allierade general eller bli f\u00e5ngad av fienden. Fr\u00e5gan \u00e4r: finns det en s\u00e5dan sekvens av kommunikation mellan de r\u00f6da generalerna (sekvens av s\u00e4ndning av budb\u00e4rare fr\u00e5n A1 till A2 och vice versa fr\u00e5n A2 till A1), d\u00e4r de garanterat kommer \u00f6verens om att attackera klockan X. H\u00e4r under garantier f\u00f6rst\u00e5s att b\u00e5da generalerna kommer att ha entydig bekr\u00e4ftelse p\u00e5 att den allierade (den andra generalen) verkligen attackerar p\u00e5 den best\u00e4mda tiden X.<\/p>\n

Anta att A1 skickar en budb\u00e4rare till A2 med meddelandet: \"L\u00e5t oss attackera idag vid midnatt!\" Generalen A1 kan inte attackera utan bekr\u00e4ftelse fr\u00e5n general A2. Om budb\u00e4raren fr\u00e5n A1 har n\u00e5tt fram, skickar general A2 en bekr\u00e4ftelse med meddelandet: \"Ja, l\u00e5t oss \u00f6vermannar de vita idag.\" Men nu vet general A2 inte om hans budb\u00e4rare har kommit fram eller inte, han har ingen garanti f\u00f6r att attacken blir simultan. Nu m\u00e5ste general A2 \u00e5terigen f\u00e5 en bekr\u00e4ftelse.<\/p>\n

Om vi forts\u00e4tter att beskriva deras kommunikation kommer vi att inse f\u00f6ljande: hur m\u00e5nga cykler av meddelandeutbyte som helst finns det inget s\u00e4tt att garantera att b\u00e5da generalerna f\u00e5r veta att deras meddelanden har mottagits (under f\u00f6ruts\u00e4ttning att n\u00e5gon av budb\u00e4rarna kan f\u00e5ngas).<\/p>\n

Problemet med de tv\u00e5 generalerna \u00e4r en utm\u00e4rkt illustration av ett mycket enkelt distribuerat system, d\u00e4r det finns tv\u00e5 noder med os\u00e4ker kommunikation. Det inneb\u00e4r att vi inte har 100 % garanti f\u00f6r att de synkroniseras. Om liknande problem p\u00e5 en st\u00f6rre skala forts\u00e4tter i artikeln.<\/p>\n

Vi introducerar begreppet distribuerade system.<\/h2>\n

\nEtt distribuerat system \u00e4r en grupp datorer (som vi kommer att kalla noder) som kan utbyta meddelanden. Varje enskild nod \u00e4r en viss autonom enhet. En nod kan sj\u00e4lvst\u00e4ndigt hantera uppgifter, men f\u00f6r att interagera med andra noder m\u00e5ste den skicka och ta emot meddelanden. <\/p>\n

Hur meddelanden konkret implementeras, vilka protokoll som anv\u00e4nds \u2014 det \u00e4r inte det som intresserar oss i detta sammanhang. Det viktiga \u00e4r att noder i det distribuerade systemet kan utbyta data med varandra genom att skicka meddelanden.<\/p>\n

Sj\u00e4lva definitionen verkar inte s\u00e4rskilt komplicerad, men man m\u00e5ste beakta att ett distribuerat system har en rad attribut som kommer att vara viktiga f\u00f6r oss.<\/p>\n

Attribut f\u00f6r distribuerade system<\/h4>\n

<\/p>\n

    \n
  1. Samtidighet<\/b> \u2013 m\u00f6jligheten till samtidiga eller konkurrerande h\u00e4ndelser i systemet. Dessutom kommer vi att anta att h\u00e4ndelser som intr\u00e4ffar p\u00e5 tv\u00e5 olika noder potentiellt \u00e4r konkurrerande s\u00e5 l\u00e4nge vi inte har n\u00e5gon tydlig ordning p\u00e5 h\u00e4ndelserna. Och vanligtvis har vi ingen s\u00e5dan ordning.<\/li>\n
  2. Avsaknad av globala klockor<\/b>. Vi har ingen tydlig ordning p\u00e5 h\u00e4ndelserna p\u00e5 grund av avsaknaden av globala klockor. I den vanliga m\u00e4nniskov\u00e4rlden \u00e4r vi vana vid att ha klockor och en absolut tid. Allt f\u00f6r\u00e4ndras n\u00e4r det handlar om distribuerade system. \u00c4ven de mest precisa atomklockorna har en driftskiftning, och det \u00e4r m\u00f6jligt att vi inte kan s\u00e4ga vilket av de tv\u00e5 h\u00e4ndelserna som intr\u00e4ffade f\u00f6rst. D\u00e4rf\u00f6r kan vi inte heller lita p\u00e5 tid.<\/li>\n
  3. Oberoende fel i nodernas system<\/b>. Det finns \u00e4nnu ett problem: n\u00e5got kan g\u00e5 fel helt enkelt eftersom v\u00e5ra noder inte \u00e4r eviga. En h\u00e5rddisk kan g\u00e5 s\u00f6nder, en virtuell maskin i molnet kan starta om, n\u00e4tverket kan blinkar och meddelanden g\u00e5r f\u00f6rlorade. Dessutom \u00e4r det m\u00f6jligt att noderna fungerar, men samtidigt arbetar mot systemet. Den sista klassen av problem har till och med f\u00e5tt ett eget namn: problemet med byzantinska generaler<\/a><\/noindex>. Det mest k\u00e4nda exemplet p\u00e5 ett distribuerat system som har detta problem \u00e4r Blockchain. Men idag kommer vi inte att g\u00e5 in p\u00e5 denna specifika klass av problem. Vi kommer att fokusera p\u00e5 situationer d\u00e4r en eller flera noder helt enkelt kan g\u00e5 ner.<\/li>\n
  4. Kommunikationsmodeller (meddelandeutbytesmodeller) mellan noder<\/b>. Vi har redan konstaterat att noder kommunicerar genom att utbyta meddelanden. Det finns tv\u00e5 k\u00e4nda modeller f\u00f6r meddelandeutbyte: synkront och asynkront.<\/li>\n<\/ol>\n

    <\/p>\n

    Kommunikationsmodeller mellan noder i distribuerade system<\/h4>\n

    \nSynkron modell<\/b> \u2013 vi vet med s\u00e4kerhet att det finns en slutlig k\u00e4nd tidsdelta, inom vilken ett meddelande garanterat n\u00e5r fr\u00e5n en nod till en annan. Om denna tid har g\u00e5tt och meddelandet inte har kommit, kan vi utan tvekan s\u00e4ga att noden har slutat fungera. I en s\u00e5dan modell har vi en f\u00f6ruts\u00e4gbar v\u00e4ntetid. <\/p>\n

    Asynkron modell<\/b> \u2013 i asynkrona modeller anser vi att v\u00e4ntetiden \u00e4r \u00e4ndlig, men det finns ingen tidsdelta efter vilken vi kan garantera att noden har slutat fungera. Det vill s\u00e4ga, v\u00e4ntetiden f\u00f6r ett meddelande fr\u00e5n en nod kan vara hur l\u00e5ng som helst. Detta \u00e4r en viktig definition och vi kommer att diskutera det vidare. <\/p>\n

    Begreppet konsensus i distribuerade system<\/h2>\n

    \nInnan vi formellt definierar begreppet konsensus, l\u00e5t oss \u00f6verv\u00e4ga ett exempel p\u00e5 en situation d\u00e4r vi beh\u00f6ver det, n\u00e4mligen \u2013 State Machine Replication<\/b>. <\/p>\n

    Vi har en viss distribuerad logg. Vi skulle vilja att den \u00e4r konsekvent och inneh\u00e5ller identiska data p\u00e5 alla noder i det distribuerade systemet. N\u00e4r n\u00e5gon av noderna f\u00e5r veta ett nytt v\u00e4rde som de t\u00e4nker skriva till loggen, blir det deras uppgift att f\u00f6resl\u00e5 detta v\u00e4rde f\u00f6r alla andra noder, s\u00e5 att loggen uppdateras p\u00e5 alla noder, och systemet g\u00e5r in i ett nytt konsekvent tillst\u00e5nd. Det \u00e4r viktigt att noderna kommer \u00f6verens med varandra: alla noder har enats om att det f\u00f6reslagna nya v\u00e4rdet \u00e4r korrekt, alla noder har accepterat detta v\u00e4rde, och f\u00f6rst d\u00e5 kan alla skriva det nya v\u00e4rdet till loggen. <\/p>\n

    Med andra ord: ingen av noderna har inv\u00e4nt att de har mer aktuell information och att det f\u00f6reslagna v\u00e4rdet \u00e4r felaktigt. \u00d6verenskommelsen mellan noderna och enigheten om det enhetliga godtagna v\u00e4rdet \u00e4r vad konsensus inneb\u00e4r i ett distribuerat system. Fram\u00f6ver kommer vi att diskutera algoritmer som g\u00f6r det m\u00f6jligt f\u00f6r det distribuerade systemet att garantera att konsensus n\u00e5s.
    \n\"Schr\u00f6dingers
    \nMer formellt kan vi definiera algoritmen f\u00f6r att uppn\u00e5 konsensus (eller helt enkelt konsensusalgoritm) som en viss funktion som f\u00f6rvandlar ett distribuerat system fr\u00e5n tillst\u00e5nd A till tillst\u00e5nd B. Detta tillst\u00e5nd m\u00e5ste accepteras av alla noder, och alla noder m\u00e5ste kunna bekr\u00e4fta det. Som det visar sig \u00e4r denna uppgift inte s\u00e5 trivial som den kan verka vid f\u00f6rsta anblick.<\/p>\n

    Egenskaper hos konsensusalgoritmen<\/h4>\n

    \nKonsensusalgoritmen m\u00e5ste ha tre egenskaper f\u00f6r att systemet ska forts\u00e4tta existera och ha n\u00e5got framsteg i \u00f6verg\u00e5ngen mellan tillst\u00e5nd:<\/p>\n

      \n
    1. \u00d6verenskommelse <\/b> \u2013 alla korrekt fungerande noder m\u00e5ste acceptera samma v\u00e4rde (i artiklar kallas denna egenskap ocks\u00e5 f\u00f6r safety property). Alla noder som f\u00f6r n\u00e4rvarande fungerar (inte har kraschat eller tappat kontakten med de andra) m\u00e5ste n\u00e5 en \u00f6verenskommelse och acceptera ett slutgiltigt gemensamt v\u00e4rde.\n

      H\u00e4r \u00e4r det viktigt att f\u00f6rst\u00e5 att noderna i det distribuerade systemet vi diskuterar str\u00e4var efter att komma \u00f6verens. Det vill s\u00e4ga, vi pratar nu om system d\u00e4r n\u00e5got kan fungera fel (till exempel att en nod kraschar), men i detta system finns det absolut inga noder som avsiktligt arbetar emot andra (den byzantinska generalens problem). Tack vare denna egenskap f\u00f6rblir systemet konsistent.<\/li>\n

    2. Integritet <\/b> \u2013 om alla korrekt fungerande noder erbjuder samma v\u00e4rde v<\/b>, m\u00e5ste varje korrekt fungerande nod acceptera detta v\u00e4rde v<\/b>. <\/li>\n
    3. Avslutning <\/b>\u2013 alla korrekt fungerande noder kommer till slut att acceptera ett visst v\u00e4rde (liveness property), vilket g\u00f6r det m\u00f6jligt f\u00f6r algoritmen att ha framsteg i systemet. Varje enskild korrekt fungerande nod m\u00e5ste f\u00f6rr eller senare acceptera det slutgiltiga v\u00e4rdet och bekr\u00e4fta detta: \"F\u00f6r mig \u00e4r detta v\u00e4rde sant, jag h\u00e5ller med hela systemet.\"<\/li>\n<\/ol>\n

      <\/p>\n

      Exempel p\u00e5 konsensusalgoritmens funktion<\/h4>\n

      \nTills dessa egenskaper hos algoritmen \u00e4r helt f\u00f6rst\u00e5eliga, l\u00e5t oss illustrera med ett exempel hur de enklaste konsensusalgoritmerna i ett system med en synkron modell f\u00f6r meddelandeutbyte fungerar, d\u00e4r alla noder fungerar som de ska, meddelanden inte g\u00e5r f\u00f6rlorade och inget g\u00e5r s\u00f6nder (kan detta verkligen h\u00e4nda?).<\/p>\n

        \n
      1. Allt b\u00f6rjar med ett f\u00f6rslag om hand och hj\u00e4rta (Propose). Anta att en klient har anslutit sig till noden kallad \"Nod 1\" och startat en transaktion genom att skicka ett nytt v\u00e4rde - O. Fr\u00e5n och med nu kommer vi att kalla \"Nod 1\" proposer<\/b>. Som proposer m\u00e5ste \"Nod 1\" nu meddela hela systemet att den har nya data, och den skickar meddelanden till alla andra noder: \"Titta! Jag har f\u00e5tt v\u00e4rdet 'O', och jag vill att ni ocks\u00e5 ska bekr\u00e4fta att ni kommer att skriva 'O' i er logg.\"\n

        \"Schr\u00f6dingers<\/li>\n

      2. N\u00e4sta steg \u00e4r omr\u00f6stning om det f\u00f6reslagna v\u00e4rdet (Voting). Varf\u00f6r beh\u00f6vs det? Det kan h\u00e4nda att andra noder har f\u00e5tt mer aktuella uppgifter, och de kan ha information om samma transaktion.\n

        \"Schr\u00f6dingers
        \n
        \nN\u00e4r noden \"Nod 1\" skickar sitt f\u00f6rslag, kontrollerar de andra noderna sina loggar f\u00f6r uppgifter om denna h\u00e4ndelse. Om det inte finns n\u00e5gra mots\u00e4gelser, f\u00f6rklarar noderna: \"Ja, jag har ingen annan information om denna h\u00e4ndelse. V\u00e4rdet 'O' \u00e4r den senaste information vi har f\u00e5tt.\" <\/p>\n

        I annat fall kan noderna svara \"Nod 1\": \"Lyssna! Jag har mer aktuell information om denna transaktion. Inte 'O', utan n\u00e5got b\u00e4ttre.\"<\/p>\n

        Under omr\u00f6stningen kommer noderna fram till en l\u00f6sning: antingen accepterar alla ett v\u00e4rde eller s\u00e5 r\u00f6star n\u00e5gon emot, och anger att de har mer aktuell information. <\/li>\n

      3. Om omr\u00f6stningen har genomf\u00f6rts framg\u00e5ngsrikt och alla var \"f\u00f6r\", g\u00e5r systemet vidare till ett nytt steg - acceptans av v\u00e4rdet (Accept). \"Nod 1\" samlar alla svar fr\u00e5n andra noder och meddelar: \"Alla har kommit \u00f6verens om v\u00e4rdet 'O'! Nu f\u00f6rklarar jag officiellt att 'O' \u00e4r v\u00e5rt nya v\u00e4rde som g\u00e4ller f\u00f6r alla! Skriv ner det i er bok, gl\u00f6m inte. Skriv i er logg!\"\n

        \"Schr\u00f6dingers<\/li>\n

      4. \u00d6vriga noder skickar en bekr\u00e4ftelse (Accepted) p\u00e5 att de har skrivit ner v\u00e4rdet 'O', inget nytt har kommit in under den tiden (en slags tv\u00e5fasesbekr\u00e4ftelse). Efter denna betydelsefulla h\u00e4ndelse anser vi att den distribuerade transaktionen har genomf\u00f6rts.
        \n \"Schr\u00f6dingers <\/li>\n<\/ol>\n

        \nS\u00e5ledes best\u00e5r konsensusalgoritmen i enkla fall av fyra steg: f\u00f6resl\u00e5, omr\u00f6stning (voting), acceptans (accept), bekr\u00e4ftelse av acceptans (accepted).<\/p>\n

        Om vi inte kan n\u00e5 en \u00f6verenskommelse i n\u00e5got steg, startar algoritmen om, med h\u00e4nsyn till den information som noderna som v\u00e4grar att bekr\u00e4fta det f\u00f6reslagna v\u00e4rdet kommer att tillhandah\u00e5lla.<\/p>\n

        Konsensusalgoritm i ett asynkront system<\/h2>\n

        \nTidigare har allt varit enkelt, eftersom vi har talat om en synkron kommunikationsmodell. Men vi vet ju att vi i den moderna v\u00e4rlden \u00e4r vana vid att g\u00f6ra allt asynkront. Hur fungerar d\u00e5 en liknande algoritm i ett system med en asynkron meddelandemodell, d\u00e4r vi anser att v\u00e4ntetiden f\u00f6r ett svar fr\u00e5n en nod kan vara hur l\u00e5ng som helst (f\u00f6r att n\u00e4mna ett exempel, en nod som g\u00e5r ner kan ocks\u00e5 ses som ett fall d\u00e4r noden kan svara hur l\u00e4nge som helst). <\/p>\n

        Nu n\u00e4r vi vet hur konsensusalgoritmen fungerar i princip, en fr\u00e5ga till de nyfikna l\u00e4sarna som har kommit hit: hur m\u00e5nga noder i ett system med N noder som har en asynkron meddelandemodell kan g\u00e5 ner, s\u00e5 att systemet fortfarande kan n\u00e5 konsensus?<\/p><\/blockquote>\n

        \nDet r\u00e4tta svaret och motiveringen finns under spoilern.<\/b>Det r\u00e4tta svaret: 0<\/b>. Om \u00e4ven en nod i ett asynkront system g\u00e5r ner, kan systemet inte n\u00e5 konsensus. Detta p\u00e5st\u00e5ende bevisades i en v\u00e4lk\u00e4nd sats inom vissa kretsar, FLP-teoremet (1985, Fischer, Lynch, Paterson, referens till originalet i slutet av artikeln): \"Om\u00f6jligheten att n\u00e5 distribuerad konsensus vid nedg\u00e5ng av minst en nod.\"
        \n\"Schr\u00f6dingers
        \nGrabbar, d\u00e5 har vi ett problem, vi \u00e4r ju vana vid att allt \u00e4r asynkront. Och h\u00e4r \u00e4r det s\u00e5. Hur ska vi g\u00e5 vidare? <\/p>\n

        Vi har just pratat om teori, om matematik. Vad betyder \"konsensus kan inte n\u00e5s\" n\u00e4r vi \u00f6vers\u00e4tter fr\u00e5n matematiskt spr\u00e5k till v\u00e5rt \u2013 ingenj\u00f6rsspr\u00e5k? Det betyder att \"det alltid kan finnas fall d\u00e4r konsensus inte kan n\u00e5s\". Vad \u00e4r detta fall? <\/p>\n

        Det handlar just om brott mot liveness property som n\u00e4mndes tidigare. Vi har ingen gemensam \u00f6verenskommelse, och systemet kan inte g\u00f6ra framsteg (kan inte avslutas inom en begr\u00e4nsad tid) n\u00e4r vi inte har svar fr\u00e5n alla noder. Eftersom vi i ett asynkront system inte har f\u00f6ruts\u00e4gbart svarstid, kan vi inte veta om en nod har g\u00e5tt ner eller bara svarar l\u00e5ngsamt.<\/p>\n

        Men i praktiken kan vi hitta en l\u00f6sning. L\u00e5t v\u00e5r algoritm kunna fungera l\u00e4nge vid fel (potentiellt kan den fungera o\u00e4ndligt). Men i de flesta situationer, n\u00e4r de flesta noder fungerar korrekt, kommer vi att ha framsteg i systemet. <\/p>\n

        I praktiken hanterar vi delvis synkrona kommunikationsmodeller. Delvis synkronitet f\u00f6rst\u00e5s s\u00e5 att vi i allm\u00e4nhet har en asynkron modell, men formellt introduceras en viss term \"global stabilization time\" f\u00f6r en viss tidpunkt. <\/p>\n

        Denna tidpunkt beh\u00f6ver inte infalla under en obest\u00e4md tid, men en dag m\u00e5ste den intr\u00e4ffa. En virtuell v\u00e4ckarklocka kommer att ringa, och fr\u00e5n det \u00f6gonblicket kan vi f\u00f6ruts\u00e4ga tidsdifferensen f\u00f6r att meddelandena ska n\u00e5 fram. Fr\u00e5n det \u00f6gonblicket omvandlas systemet fr\u00e5n asynkront till synkront. I praktiken hanterar vi just s\u00e5dana system. <\/p>\n

        Paxos-algoritmen l\u00f6ser konsensusproblem<\/h2>\n

        \nPaxos <\/a><\/noindex> \u2013 \u00e4r en familj av algoritmer som l\u00f6ser konsensusproblemet f\u00f6r delvis synkrona system, under f\u00f6ruts\u00e4ttning att vissa noder kan fallera. F\u00f6rfattaren av Paxos \u00e4r Leslie Lamport<\/a><\/noindex>. Han f\u00f6reslog ett formellt bevis p\u00e5 existensen och korrektheten av algoritmen 1989. <\/p>\n

        Men beviset visade sig vara l\u00e5ngt ifr\u00e5n trivialt. Den f\u00f6rsta publikationen sl\u00e4pptes f\u00f6rst 1998 (33 sidor) med en beskrivning av algoritmen. Det visade sig att den var oerh\u00f6rt sv\u00e5r att f\u00f6rst\u00e5, och 2001 publicerades en f\u00f6rklaring till artikeln som tog 14 sidor. Omf\u00e5nget av publikationerna anges f\u00f6r att visa att konsensusproblemet faktiskt \u00e4r ganska komplicerat, och bakom s\u00e5dana algoritmer ligger ett enormt arbete av de smartaste m\u00e4nniskorna.<\/p>\n

        Intressant nog p\u00e5pekade Leslie Lamport sj\u00e4lv i sin f\u00f6rel\u00e4sning att det i den andra f\u00f6rklarande artikeln finns ett p\u00e5st\u00e5ende, en rad (han specificerade inte vilken), som kan tolkas p\u00e5 olika s\u00e4tt. Och p\u00e5 grund av detta fungerar m\u00e5nga moderna implementationer av Paxos inte helt korrekt. <\/p><\/blockquote>\n

        \nEn detaljerad genomg\u00e5ng av hur Paxos fungerar skulle ta flera artiklar, s\u00e5 jag ska f\u00f6rs\u00f6ka f\u00f6rmedla huvudid\u00e9n med algoritmen p\u00e5 ett mycket kort s\u00e4tt. I slutet av min artikel kommer ni att hitta material f\u00f6r vidare f\u00f6rdjupning i detta \u00e4mne.<\/p>\n

        Roller i Paxos<\/h4>\n

        \nI Paxos-algoritmen finns begreppet roller. Vi ska titta p\u00e5 tre huvudroller (det finns modifieringar med ytterligare roller):<\/p>\n

          \n
        1. Proposers (termer som ledare eller samordnare kan ocks\u00e5 f\u00f6rekomma)<\/b>. Dessa \u00e4r killarna som f\u00e5r veta om ett nytt v\u00e4rde fr\u00e5n anv\u00e4ndaren och tar p\u00e5 sig rollen som ledare. Deras uppgift \u00e4r att starta en runda av erbjudanden om det nya v\u00e4rdet och koordinera de vidare \u00e5tg\u00e4rderna av noderna. Paxos till\u00e5ter att det finns flera ledare i vissa situationer.<\/li>\n
        2. Acceptorer (R\u00f6stare)<\/b>. Dessa \u00e4r noder som r\u00f6star f\u00f6r att anta eller avvisa ett visst v\u00e4rde. Deras roll \u00e4r mycket viktig, eftersom det \u00e4r upp till dem att avg\u00f6ra: vilket tillst\u00e5nd systemet kommer att g\u00e5 \u00f6ver till (eller inte g\u00e5 \u00f6ver till) efter n\u00e4sta steg av konsensusalgoritmen.<\/li>\n
        3. L\u00e4rande noder<\/b>. Noder som bara tar emot och registrerar det nya antagna v\u00e4rdet n\u00e4r systemets tillst\u00e5nd har \u00e4ndrats. De fattar inga beslut, utan f\u00e5r bara data och kan ge dem till slutanv\u00e4ndaren. <\/li>\n<\/ol>\n

          \nEn nod kan kombinera flera roller i olika situationer. <\/p>\n

          Begreppet kvorum<\/h4>\n

          \nVi antar att vi har ett system av N<\/b> noder. Och av dem kan h\u00f6gst F<\/b> noder g\u00e5 ner. Om F noder g\u00e5r ner, betyder det att vi i klustret m\u00e5ste ha minst 2F + 1<\/b> acceptor-noder. <\/p>\n

          Detta \u00e4r n\u00f6dv\u00e4ndigt s\u00e5 att vi alltid, \u00e4ven i den s\u00e4msta situationen, har en majoritet av 'goda', korrekt fungerande noder. Det vill s\u00e4ga F + 1<\/b> goda noder som har enats, och det slutliga v\u00e4rdet kommer att antas. Annars kan det uppst\u00e5 en situation d\u00e4r olika lokala grupper antagit olika v\u00e4rden och inte kan enas. D\u00e4rf\u00f6r beh\u00f6ver vi en absolut majoritet f\u00f6r att vinna omr\u00f6stningen.<\/p>\n

          Den allm\u00e4nna id\u00e9n bakom Paxos konsensusalgoritm<\/h4>\n

          \nPaxos-algoritmen omfattar tv\u00e5 stora faser, som i sin tur delas upp i tv\u00e5 steg vardera:<\/p>\n

            \n
          1. Fas 1a: F\u00f6rbered<\/b>. I f\u00f6rberedelseskedet meddelar ledaren (proposer) alla noder: \"Vi inleder ett nytt r\u00f6stningsskede. Vi har en ny omg\u00e5ng. Nummer p\u00e5 denna omg\u00e5ng \u00e4r n. Nu b\u00f6rjar vi r\u00f6sta.\" Just nu meddelar han bara b\u00f6rjan av en ny cykel, men han informerar inte om n\u00e5got nytt v\u00e4rde. M\u00e5let med detta steg \u00e4r att initiera en ny omg\u00e5ng och att informera alla om dess unika nummer. Omg\u00e5ngsnumret \u00e4r viktigt, det m\u00e5ste vara ett v\u00e4rde som \u00e4r st\u00f6rre \u00e4n alla tidigare r\u00f6stningsnummer fr\u00e5n alla tidigare ledare. Eftersom det \u00e4r tack vare omg\u00e5ngsnumret som andra noder i systemet kommer att f\u00f6rst\u00e5 hur aktuella ledarens data \u00e4r. Det \u00e4r m\u00f6jligt att andra noder redan har r\u00f6stningsresultat fr\u00e5n mycket senare omg\u00e5ngar och de kommer helt enkelt att ber\u00e4tta f\u00f6r ledaren att han har halkat efter.<\/li>\n
          2. Fas 1b: L\u00f6fte<\/b>. N\u00e4r acceptor-noderna har f\u00e5tt numret p\u00e5 den nya r\u00f6stningsrundan kan det finnas tv\u00e5 utfall: \n