Så låt oss föreställa oss. Det finns 5 katter inlåsta i rummet, och för att väcka ägaren måste de alla komma överens om detta sinsemellan, eftersom de bara kan öppna dörren när fem av dem lutar sig mot den. Om en av katterna är Schrödingers katt, och de andra katterna inte vet om hans beslut, uppstår frågan: "Hur kan de göra det?"
I den här artikeln kommer jag att berätta i enkla termer om den teoretiska komponenten i världen av distribuerade system och principerna för deras funktion. Jag kommer också ytligt att undersöka huvudidén bakom Paxos.
När utvecklare använder molninfrastruktur, olika databaser och arbetar i kluster av ett stort antal noder, är de säkra på att data kommer att vara komplett, säker och alltid tillgänglig. Men var finns garantierna?
De garantier vi har är i huvudsak leverantörsgarantier. De beskrivs i dokumentationen enligt följande: "Denna tjänst är ganska pålitlig, den har en given SLA, oroa dig inte, allt kommer att fungera distribuerat som du förväntar dig."
Vi tenderar att tro på det bästa, eftersom smarta killar från stora företag försäkrade oss att allt kommer att bli bra. Vi ställer inte frågan: varför kan det här fungera alls? Finns det någon formell motivering för att sådana system fungerar korrekt?
Jag gick nyligen till och blev väldigt inspirerad av detta ämne. Föreläsningar i skolan var mer som kalkylkurser än något relaterat till datorsystem. Men det är precis så de viktigaste algoritmerna som vi använder varje dag, utan att ens veta om det, bevisades på en gång.
De flesta moderna distribuerade system använder Paxos konsensusalgoritm och dess olika modifieringar. Det coolaste är att giltigheten och, i princip, själva möjligheten till existensen av denna algoritm kan bevisas helt enkelt med penna och papper. I praktiken används algoritmen i stora system som körs på ett stort antal noder i molnen.
En lätt illustration av vad som kommer att diskuteras härnäst: två generalers uppgiftLåt oss ta en titt efter en uppvärmning .
Vi har två arméer - röda och vita. Vita trupper är baserade i den belägrade staden. Röda trupper ledda av generalerna A1 och A2 finns på två sidor av staden. De rödhårigas uppgift är att attackera den vita staden och vinna. Emellertid är armén för varje röd general individuellt mindre än den vita armén.
Segervillkor för de röda: båda generalerna måste attackera samtidigt för att ha ett numerärt övertag gentemot de vita. För att göra detta måste generalerna A1 och A2 komma överens med varandra. Om alla attackerar var för sig kommer de rödhåriga att förlora.
För att nå en överenskommelse kan generalerna A1 och A2 skicka budbärare till varandra genom den vita stadens territorium. Budbäraren kan framgångsrikt nå en allierad general eller kan fångas upp av fienden. Fråga: finns det en sådan sekvens av kommunikation mellan de rödhåriga generalerna (sekvensen att skicka budbärare från A1 till A2 och vice versa från A2 till A1), där de garanterat kommer överens om en attack vid timme X. Här, garantier innebär att båda generalerna kommer att få entydig bekräftelse på att en allierad (en annan general) definitivt kommer att attackera vid utsatt tid X.
Anta att A1 skickar en budbärare till A2 med meddelandet: "Låt oss attackera idag vid midnatt!" General A1 kan inte attackera utan bekräftelse från General A2. Om budbäraren från A1 har anlänt, skickar general A2 en bekräftelse med meddelandet: "Ja, låt oss döda de vita i dag." Men nu vet inte general A2 om hans budbärare har anlänt eller inte, han har ingen garanti för om attacken kommer att ske samtidigt. Nu behöver General A2 återigen bekräftelse.
Att beskriva deras kommunikation ytterligare avslöjar följande: oavsett hur många meddelandecykler det finns, finns det inget sätt att garantera att båda generalerna har meddelats att deras meddelanden har tagits emot (förutsatt att båda budbärarna kan avlyssnas).
The Two Generals Problem är en bra illustration av ett mycket enkelt distribuerat system där det finns två noder med opålitlig kommunikation. Det betyder att vi inte har 100% garanti för att de är synkroniserade. Liknande problem diskuteras först i större skala längre fram i artikeln.
Vi introducerar begreppet distribuerade system
Ett distribuerat system är en grupp datorer (nedan kallar vi dem noder) som kan utbyta meddelanden. Varje enskild nod är någon form av autonom enhet. En nod kan bearbeta uppgifter på egen hand, men för att kunna kommunicera med andra noder behöver den skicka och ta emot meddelanden.
Hur exakt meddelanden implementeras, vilka protokoll som används - detta är inte av intresse för oss i detta sammanhang. Det är viktigt att noderna i ett distribuerat system kan utbyta data med varandra genom att skicka meddelanden.
Definitionen i sig ser inte särskilt komplicerad ut, men vi måste ta hänsyn till att ett distribuerat system har ett antal attribut som kommer att vara viktiga för oss.
Attribut för distribuerade system
- samtidighet – möjligheten att samtidiga eller samtidiga händelser inträffar i systemet. Dessutom kommer vi att betrakta händelser som inträffar på två olika noder som potentiellt samtidiga så länge vi inte har en tydlig ordning för förekomsten av dessa händelser. Men som regel har vi det inte.
- Ingen global klocka. Vi har ingen tydlig händelseordning på grund av avsaknaden av en global klocka. I den vanliga människors värld är vi vana vid att vi absolut har klockor och tid. Allt förändras när det kommer till distribuerade system. Även ultraexakta atomklockor har drift, och det kan finnas situationer där vi inte kan säga vilken av två händelser som hände först. Därför kan vi inte heller lita på tiden.
- Oberoende fel på systemnoder. Det finns ett annat problem: något kan gå fel helt enkelt för att våra noder inte varar för evigt. Hårddisken kan misslyckas, den virtuella maskinen i molnet kan starta om, nätverket kan blinka och meddelanden går förlorade. Dessutom kan det finnas situationer där noder fungerar, men samtidigt motverkar systemet. Den sista klassen av problem fick till och med ett separat namn: problem . Det mest populära exemplet på ett distribuerat system med detta problem är Blockchain. Men idag kommer vi inte att överväga denna speciella klass av problem. Vi kommer att vara intresserade av situationer där bara en eller flera noder kan misslyckas.
- Kommunikationsmodeller (meddelandemodeller) mellan noder. Vi har redan konstaterat att noder kommunicerar genom att utbyta meddelanden. Det finns två välkända meddelandemodeller: synkron och asynkron.
Modeller för kommunikation mellan noder i distribuerade system
Synkron modell – vi vet med säkerhet att det finns ett ändligt känt tidsdelta under vilket ett meddelande garanterat når från en nod till en annan. Om denna tid har gått och meddelandet inte har kommit fram kan vi lugnt säga att noden har misslyckats. I denna modell har vi förutsägbara väntetider.
Asynkron modell – i asynkrona modeller anser vi att väntetiden är ändlig, men det finns inget sådant tidsdelta efter vilket vi kan garantera att noden har misslyckats. De där. Väntetiden för ett meddelande från en nod kan vara godtyckligt lång. Detta är en viktig definition, och vi kommer att prata om den ytterligare.
Konsensusbegreppet i distribuerade system
Innan vi formellt definierar begreppet konsensus, låt oss överväga ett exempel på en situation där vi behöver det, nämligen - Tillståndsmaskinreplikering.
Vi har en del distribuerad stock. Vi vill att det ska vara konsekvent och innehålla identisk data på alla noder i det distribuerade systemet. När en av noderna lär sig ett nytt värde som den ska skriva till loggen blir dess uppgift att erbjuda detta värde till alla andra noder så att loggen uppdateras på alla noder och systemet flyttar till ett nytt konsekvent tillstånd. I det här fallet är det viktigt att noderna kommer överens sinsemellan: alla noder är överens om att det föreslagna nya värdet är korrekt, alla noder accepterar detta värde, och endast i detta fall kan alla skriva det nya värdet till loggen.
Med andra ord: ingen av noderna invände att den hade mer relevant information, och det föreslagna värdet var felaktigt. Överenskommelse mellan noder och överenskommelse om ett enda korrekt accepterat värde är konsensus i ett distribuerat system. Därefter kommer vi att prata om algoritmer som gör att ett distribuerat system kan garanteras nå konsensus.
Mer formellt kan vi definiera en konsensusalgoritm (eller helt enkelt en konsensusalgoritm) som en viss funktion som överför ett distribuerat system från tillstånd A till tillstånd B. Dessutom accepteras detta tillstånd av alla noder, och alla noder kan bekräfta det. Som det visar sig är denna uppgift inte alls så trivial som den verkar vid första anblicken.
Egenskaper för konsensusalgoritmen
Konsensusalgoritmen måste ha tre egenskaper för att systemet ska fortsätta att existera och ha några framsteg när det gäller att flytta från stat till stat:
- Avtal – alla korrekt fungerande noder måste ha samma värde (i artiklar kallas denna egenskap även för säkerhetsegenskap). Alla noder som för närvarande fungerar (inte har misslyckats eller tappat kontakten med de andra) måste komma överens och acceptera något slutgiltigt gemensamt värde.
Det är viktigt att förstå här att noderna i det distribuerade systemet vi överväger vill komma överens. Det vill säga, vi pratar nu om system där något helt enkelt kan misslyckas (till exempel någon nod misslyckas), men i detta system finns det definitivt inga noder som medvetet motarbetar andra (bysantinska generalers uppgift). På grund av denna egenskap förblir systemet konsekvent.
- Integritet — om alla korrekt fungerande noder erbjuder samma värde v, vilket innebär att varje korrekt fungerande nod måste acceptera detta värde v.
- Uppsägning – alla korrekt fungerande noder kommer så småningom att anta ett visst värde (liveness-egenskap), vilket gör att algoritmen kan göra framsteg i systemet. Varje enskild korrekt fungerande nod måste förr eller senare acceptera det slutliga värdet och bekräfta det: "För mig är detta värde sant, jag håller med hela systemet."
Ett exempel på hur konsensusalgoritmen fungerar
Medan egenskaperna hos algoritmen kanske inte är helt klara. Därför kommer vi att illustrera med ett exempel vilka stadier den enklaste konsensusalgoritmen går igenom i ett system med en synkron meddelandemodell, där alla noder fungerar som förväntat, meddelanden inte går förlorade och ingenting går sönder (händer detta verkligen?).
- Det hela börjar med ett äktenskapsförslag (Propose). Låt oss anta att en klient kopplade till en nod som heter "Nod 1" och startade en transaktion och skickade ett nytt värde till noden - O. Från och med nu kommer vi att anropa "Nod 1" erbjudande. Som förslagsställare måste "Nod 1" nu meddela hela systemet att det har färska data, och det skickar meddelanden till alla andra noder: "Titta! Betydelsen "O" kom till mig och jag vill skriva ner det! Vänligen bekräfta att du också kommer att anteckna "O" i din logg."
- Nästa steg är att rösta för det föreslagna värdet (omröstning). Vad är det för? Det kan hända att andra noder har fått nyare information, och de har data om samma transaktion.
När nod "Nod 1" skickar sitt förslag, kontrollerar de andra noderna sina loggar för data om denna händelse. Om det inte finns några motsägelser meddelar noderna: "Ja, jag har inga andra data för denna händelse. "O"-värdet är den senaste informationen vi förtjänar."I alla andra fall kan noder svara på "Nod 1": "Lyssna! Jag har nyare uppgifter om denna transaktion. Inte "O", utan något bättre."
Vid omröstningsstadiet kommer noderna till ett beslut: antingen accepterar de alla samma värde, eller så röstar en av dem emot, vilket indikerar att han har nyare data.
- Om omröstningen var framgångsrik och alla var för, så går systemet till ett nytt stadium - Acceptera värdet. "Nod 1" samlar alla svar från andra noder och rapporterar: "Alla var överens om värdet "O"! Nu förklarar jag officiellt att "O" är vår nya betydelse, samma för alla! Skriv ner det i din lilla bok, glöm inte. Skriv ner det i din logg!”
- De återstående noderna skickar en bekräftelse (Accepterad) att de har skrivit ner värdet "O", inget nytt har kommit under denna tid (en sorts tvåfas commit). Efter denna betydande händelse anser vi att den distribuerade transaktionen har slutförts.
Sålunda består konsensusalgoritmen i ett enkelt fall av fyra steg: föreslå, rösta (rösta), acceptera (acceptera), bekräfta acceptans (accepterat).
Om vi vid något steg inte kunde komma överens, startar algoritmen igen, med hänsyn till informationen från noderna som vägrade att bekräfta det föreslagna värdet.
Konsensusalgoritm i ett asynkront system
Innan detta var allt smidigt, eftersom vi pratade om en synkron meddelandemodell. Men vi vet att vi i den moderna världen är vana vid att göra allt asynkront. Hur fungerar en liknande algoritm i ett system med en asynkron meddelandemodell, där vi tror att väntetiden för ett svar från en nod kan vara godtyckligt lång (förresten, ett misslyckande i en nod kan också betraktas som ett exempel när en nod kan svara under en godtyckligt lång tid ).
Nu när vi vet hur konsensusalgoritmen fungerar i princip, en fråga för de nyfikna läsare som har kommit så här långt: hur många noder i ett system av N noder med en asynkron meddelandemodell kan misslyckas så att systemet fortfarande kan nå konsensus?
Rätt svar och motivering ligger bakom spoilern.Rätt svar: 0. Om ens en nod i ett asynkront system misslyckas, kommer systemet inte att kunna nå konsensus. Detta påstående bevisas i FLP-satsen, välkänd i vissa kretsar (1985, Fischer, Lynch, Paterson, länk till originalet i slutet av artikeln): ”Omöjligheten att uppnå en distribuerad konsensus om åtminstone en nod misslyckas .”
Killar, då har vi ett problem, vi är vana vid att allt är asynkront. Och här är den. Hur ska man fortsätta leva?
Vi pratade bara om teori, om matematik. Vad betyder "konsensus kan inte uppnås", att översätta från matematiskt språk till vårt - ingenjörskonst? Detta innebär att ”inte alltid kan uppnås”, d.v.s. Det finns ett fall där konsensus inte kan uppnås. Vad är det här för fall?
Detta är exakt den kränkning av livlighetsegenskapen som beskrivs ovan. Vi har inte en gemensam överenskommelse, och systemet kan inte ha framsteg (kan inte slutföras på en begränsad tid) i det fall vi inte har ett svar från alla noder. För i ett asynkront system har vi ingen förutsägbar svarstid och vi kan inte veta om en nod har kraschat eller bara tar lång tid att svara.
Men i praktiken kan vi hitta en lösning. Låt vår algoritm kunna fungera länge vid misslyckanden (potentiellt kan den fungera oändligt). Men i de flesta situationer, när de flesta noder fungerar korrekt, kommer vi att ha framsteg i systemet.
I praktiken sysslar vi med delvis synkrona kommunikationsmodeller. Partiell synkroni förstås enligt följande: i det allmänna fallet har vi en asynkron modell, men ett visst begrepp om "global stabiliseringstid" för en viss tidpunkt introduceras formellt.
Det här ögonblicket i tiden kanske inte kommer hur länge som helst, men det måste komma en dag. Den virtuella väckarklockan ringer, och från det ögonblicket kan vi förutsäga tidsdeltat för vilket meddelandena kommer att anlända. Från och med detta ögonblick övergår systemet från asynkront till synkront. I praktiken sysslar vi med just sådana system.
Paxos-algoritmen löser konsensusproblem
är en familj av algoritmer som löser konsensusproblemet för delvis synkrona system, med förbehåll för möjligheten att vissa noder kan misslyckas. Författaren till Paxos är . Han föreslog ett formellt bevis på algoritmens existens och riktighet 1989.
Men beviset visade sig vara långt ifrån trivialt. Den första publikationen släpptes först 1998 (33 sidor) som beskriver algoritmen. Som det visade sig var det extremt svårt att förstå, och 2001 publicerades en förklaring av artikeln, som tog 14 sidor. Volymen av publikationer ges för att visa att problemet med konsensus inte alls är enkelt, och bakom sådana algoritmer ligger en enorm mängd arbete av de smartaste människorna.
Det är intressant att Leslie Lamport själv noterade i sin föreläsning att det i den andra förklarande artikeln finns ett påstående, en rad (han angav inte vilken), som kan tolkas på olika sätt. Och på grund av detta fungerar ett stort antal moderna Paxos-implementationer inte helt korrekt.
En detaljerad analys av Paxos arbete skulle kräva mer än en artikel, så jag ska försöka att mycket kortfattat förmedla huvudidén med algoritmen. I länkarna i slutet av min artikel hittar du material för ytterligare dykning i detta ämne.
Roller på Paxos
Paxos-algoritmen har ett rollbegrepp. Låt oss överväga tre huvudsakliga (det finns ändringar med ytterligare roller):
- Förslagsställare (termerna kan också användas: ledare eller samordnare). Det här är killarna som lär sig om något nytt värde från användaren och tar på sig rollen som ledare. Deras uppgift är att lansera en förslagsrunda för ett nytt värde och samordna ytterligare åtgärder för noderna. Dessutom tillåter Paxos närvaron av flera ledare i vissa situationer.
- Acceptanter (väljare). Dessa är noder som röstar för att acceptera eller förkasta ett visst värde. Deras roll är mycket viktig, eftersom beslutet beror på dem: vilket tillstånd systemet kommer (eller inte kommer) att gå till efter nästa steg av konsensusalgoritmen.
- Eleverna. Noder som helt enkelt accepterar och skriver det nya accepterade värdet när systemets tillstånd har ändrats. De fattar inga beslut, de tar bara emot data och kan ge dem till slutanvändaren.
En nod kan kombinera flera roller i olika situationer.
Begreppet kvorum
Vi antar att vi har ett system med N knutpunkter Och av dem maximalt F noder kan misslyckas. Om F-noder misslyckas måste vi ha åtminstone 2F+1 acceptornoder.
Detta är nödvändigt för att vi alltid ska ha majoriteten, även i den värsta situationen, av "bra" noder som fungerar korrekt. Det är F+1 "bra" noder som överensstämde, och det slutliga värdet kommer att accepteras. Annars kan det uppstå en situation där våra olika lokalgrupper får olika innebörd och inte kan komma överens sinsemellan. Därför behöver vi absolut majoritet för att vinna omröstningen.
Den allmänna idén om hur Paxos konsensusalgoritm fungerar
Paxos-algoritmen involverar två stora faser, som i sin tur är uppdelade i två steg vardera:
- Fas 1a: Förbered. Under förberedelsefasen informerar ledaren (förslagsställaren) alla noder: ”Vi startar en ny omröstningsfas. Vi har en ny omgång. Antalet för denna omgång är n. Nu börjar vi rösta." För närvarande rapporterar den helt enkelt början av en ny cykel, men rapporterar inte ett nytt värde. Uppgiften för denna etapp är att initiera en ny omgång och informera alla om dess unika nummer. Det runda numret är viktigt, det måste vara ett värde större än alla tidigare röstsiffror från alla tidigare ledare. För det är tack vare det runda numret som andra noder i systemet kommer att förstå hur färska ledarens data är. Det är troligt att andra noder redan har röstningsresultat från mycket senare omgångar och helt enkelt kommer att berätta för ledaren att han ligger efter tiden.
- Fas 1b: Löfte. När acceptornoderna fick numret för det nya röstningssteget är två utfall möjliga:
- Antalet n av den nya rösten är större än numret av någon tidigare omröstning som accepteraren deltog i. Sedan skickar accepteraren ett löfte till ledaren att den inte kommer att delta i fler röster med ett lägre antal än n. Om accepteraren redan har röstat för något (det vill säga den har redan accepterat ett visst värde i den andra fasen), så fäster den det accepterade värdet och numret på rösten som den deltog i sitt löfte.
- Annars, om accepteraren redan känner till den högre rösten, kan den helt enkelt ignorera förberedelsesteget och inte svara ledaren.
- Fas 2a: Acceptera. Ledaren måste vänta på ett svar från kvorumet (de flesta noder i systemet) och om det erforderliga antalet svar tas emot, har han två alternativ för utveckling av händelser:
- Några av accepterarna skickade värden som de redan hade röstat på. I detta fall väljer ledaren värdet från omröstningen med det maximala antalet. Låt oss kalla det här värdet x, och det skickar ut ett meddelande till alla noder som: "Acceptera (n, x)", där det första värdet är röstnumret från sitt eget förslagssteg, och det andra värdet är vad alla samlades för, dvs. värdet som vi faktiskt röstar för.
- Om ingen av accepterarna skickade några värderingar, utan de helt enkelt lovade att rösta i den här omgången, kan ledaren bjuda in dem att rösta för deras värde, det värde som han blev ledare för i första hand. Låt oss kalla det y. Den skickar ett meddelande till alla noder som: "Acceptera (n, y)", liknande det tidigare resultatet.
- Fas 2b: Godkänd. Vidare instämmer acceptornoderna, när de får meddelandet "Acceptera(...)" från ledaren (skicka bekräftelse till alla noder att de håller med det nya värdet) endast om de inte har lovat något (annat) ) ledare att delta i omröstningen med runda nummer n' > n, annars ignorerar de begäran om bekräftelse.
Om majoriteten av noderna svarade på ledaren, och alla bekräftade det nya värdet, anses det nya värdet vara accepterat. Hurra! Om majoriteten inte nås eller det finns noder som vägrat acceptera det nya värdet, så börjar allt om.
Så här fungerar Paxos-algoritmen. Var och en av dessa stadier har många finesser, vi övervägde praktiskt taget inte olika typer av misslyckanden, problem med flera ledare och mycket mer, men syftet med den här artikeln är bara att introducera läsaren till världen av distribuerad datoranvändning på hög nivå.
Det är också värt att notera att Paxos inte är den enda i sitt slag, det finns andra algoritmer, till exempel, , men det här är ett ämne för en annan artikel.
Länkar till material för vidare studier
Nybörjarnivå:
- , Preethi Kasireddy, bloggartikel på Medium
- , Adi Kancherla, bloggartikel om Medium
- , Ittai Abraham, blogg
- , Ittai Abraham, bloggartikel
Leslie Lamport nivå:
- , Fischer, Lynch och Paterson, forskningsartikel, 1985
- , Leslie Lamport, forskningsartikel, 1998
- , Leslie Lamport, forskningsartikel, 2001
Källa: will.com