Forstå Raft-konsensusalgoritmen: et akademisk artikelsammendrag

Dette indlæg opsummerer Raft-konsensusalgoritmen, der er præsenteret i papiret på jagt efter en forståelig konsensusalgoritme af Diego Ongaro og John Ousterhout. Alle tilbud på træk er taget fra papiret.

Tømmerflåde:

Raft er en distribueret konsensusalgoritme. Det var designet til let at forstå. Det løser problemet med at få flere servere til at blive enige om en delt tilstand, selv i tilfælde af fejl. Den delte status er normalt en datastruktur understøttet af en replikeret log. Vi har brug for, at systemet er fuldt operationelt, så længe et flertal af serverne er op.

Raft fungerer ved at vælge en leder i klyngen. Lederen er ansvarlig for at acceptere klientanmodninger og administrere replikering af loggen til andre servere. Dataene flyder kun i en retning: fra leder til andre servere.

Raft nedbryder konsensus i tre underproblemer:

  • Valg af leder: En ny leder skal vælges i tilfælde af en eksisterende fiasko.
  • Logreplikering: Lederen skal holde logget på alle servere synkroniseret med sine egne gennem replikering.
  • Sikkerhed: Hvis en af ​​serverne har begået en logindgang ved et bestemt indeks, kan ingen anden server anvende en anden logindgang for det indeks.

Grundlæggende:

Hver server findes i en af ​​de tre stater: leder, tilhænger eller kandidat.

I normal drift er der nøjagtigt en leder, og alle de andre servere er tilhængere. Følgere er passive: de udsender ingen anmodninger alene, men besvarer blot anmodninger fra ledere og kandidater. Lederen håndterer alle klientanmodninger (hvis en klient kontakter en tilhænger, dirigerer tilhængeren det til lederen). Den tredje stat, kandidat, bruges til at vælge en ny leder.

Raft opdeler tiden i vilkåraf vilkårlig længde, der hver begynder med et valg. Hvis en kandidat vinder valget, forbliver det lederen resten af ​​valgperioden. Hvis afstemningen deles, ender denne periode uden en leder.

Den Udtrykket nummer stiger monotont. Hver server gemmer det aktuelle termnummersom også udveksles i enhver kommunikation.

.. hvis den ene servers aktuelle periode er mindre end den anden, opdaterer den den aktuelle periode til den større værdi. Hvis en kandidat eller leder opdager, at dets periode er forældet, vender det straks tilbage til tilhængerstatus. Hvis en server modtager en anmodning med et forældet termnummer, afviser den anmodningen.

Raft benytter sig af to fjernprocedurkald (RPC'er) til at udføre sin grundlæggende drift.

  • RequestVotes bruges af kandidater under valg
  • AppendEntries bruges af ledere til at replikere logindgange og også som et hjerteslag (et signal til at kontrollere, om en server er oppe eller ej - den indeholder ikke nogen logindgange)

Ledervalg

Lederen sender med jævne mellemrum et hjerterytme til sine tilhængere for at opretholde autoritet. Et ledervalg udløses, når en tilhænger afvikler tid efter at have ventet på et hjerteslag fra lederen. Denne tilhænger overgår til kandidatstaten og øger dens terminsnummer . Efter at have stemt for sig selv udsteder den RequestVotes RPC parallelt med andre i klyngen. Tre resultater er mulige:

  1. Kandidaten modtager stemmer fra flertallet af serverne og bliver leder. Derefter sender det en hjerteslagsbesked til andre i klyngen for at etablere autoritet.
  2. Hvis andre kandidater modtager AppendEntries RPC, kontrollerer de fortermnummer. Hvis udtrykket er større end deres eget, accepterer de serveren som leder og vender tilbage til tilhængertilstand. Hvis betegnelsen er mindre, afviser de RPC og forbliver stadig kandidat.
  3. Kandidaten hverken mister eller vinder. Hvis mere end en server bliver kandidat på samme tid, kan afstemningen deles uden klart flertal. I dette tilfælde begynder et nyt valg, når en af ​​kandidaterne har afbrudt.
Raft bruger randomiserede timeouts til valg for at sikre, at opdelte stemmer er sjældne, og at de løses hurtigt. For at forhindre splittede stemmer i første omgang vælges timeouts til valget tilfældigt fra et fast interval (f.eks. 150–300 ms). Dette spreder serverne ud, så kun en enkelt server i de fleste tilfælde vil timeout; det vinder valget og sender hjerteslag inden andre servere tager timeout. Den samme mekanisme bruges til at håndtere split stemmer. Hver kandidat genstarter sin randomiserede timeout til valget i starten af ​​et valg, og de venter på, at timeoutet forløber, inden det næste valg starter; dette reducerer sandsynligheden for endnu en delt afstemning ved det nye valg.

Log replikering:

Klientanmodningerne antages at være skrivebeskrivede indtil videre. Hver anmodning består af en kommando, der ideelt skal udføres af de replikerede tilstandsmaskiner på alle serverne. Når en leder får en klientanmodning, føjer den den til sin egen log som en ny post. Hver post i en log:

  • Indeholder den klient specificerede kommando
  • Har et indeks til at identificere indtastningspositionen i loggen (indekset starter fra 1)
  • Har et termnummer, der logisk kan identificere, hvornår posten blev skrevet

Det er nødvendigt at replikere posten til alle tilhørende knudepunkter for at holde logfilerne konsistente. Lederen udsteder parallelt RPC'er til AppendEntries til alle andre servere. Lederen prøver igen, indtil alle tilhængere sikkert replikerer den nye post.

Når posten replikeres til et flertal af servere af den leder, der oprettede den, betragtes den som begået. Alle tidligere poster, inklusive dem oprettet af tidligere ledere, betragtes også som engagerede. Lederen udfører posten, når den først er begået, og returnerer resultatet til klienten.

Lederen opretholder det højeste indeks, den ved, der er forpligtet i sin log, og sender det ud med AppendEntries RPC'erne til sine tilhængere. Når tilhængerne finder ud af, at posten er begået, anvender den posten på dens statsmaskine i rækkefølge.

Raft opretholder følgende egenskaber, som tilsammen udgør den logmatchende egenskab • Hvis to poster i forskellige logfiler har det samme indeks og udtryk, gemmer de den samme kommando. • Hvis to poster i forskellige logfiler har det samme indeks og udtryk, så logfiler er identiske i alle foregående poster.

Når du sender en AppendEntries RPC, lederen omfatter udtrykket nummer og indeks for posten, der umiddelbart forud for ny post. Hvis følgeren ikke kan finde et match for denne post i sin egen log, afviser den anmodningen om at tilføje den nye post.

Denne sammenhængskontrol lader lederen konkludere, at når AppendEntries vender tilbage med succes fra en tilhænger, har de identiske logfiler, indtil indekset er inkluderet i RPC.

Men lederne og tilhængernes logfiler kan blive inkonsekvente i lyset af ledernedbrud.

I Raft håndterer lederen uoverensstemmelser ved at tvinge tilhængernes logfiler til at duplikere sine egne. Dette betyder, at modstridende poster i tilhængerlogfiler overskrives med poster fra lederens log.

Lederen forsøger at finde det sidste indeks, hvor dets log matcher med tilhængeren, sletter eventuelt ekstra poster og tilføjer de nye.

Lederen opretholder en nextIndex for hver tilhænger, som er indekset for den næste logindgang, som lederen sender til den tilhænger. Når en leder først kommer til magten, initialiserer den alle nextIndex-værdier til indekset lige efter den sidste i sin log.

Hver gang AppendRPC vender tilbage med en fejl for en tilhænger, reducerer lederen nextIndexog udsteder en anden RPC for AppendEntries. Til sidst nextIndexnår en værdi, hvor logfilerne konvergerer. AppendEntries vil lykkes, når dette sker, og det kan fjerne fremmede poster (hvis nogen) og tilføje nye fra lederloggen (hvis nogen). Derfor garanterer en vellykket AppendEntries fra en tilhænger, at lederens log er i overensstemmelse med den.

Med denne mekanisme behøver en leder ikke tage nogen specielle handlinger for at gendanne logkonsistens, når det kommer til magt. Det begynder bare normal drift, og logfilerne konvergerer automatisk som reaktion på fejl i Append-Entries-konsistenskontrollen. En leder overskriver eller sletter aldrig poster i sin egen log.

Sikkerhed:

Raft sørger for, at lederen for en periode har begået poster fra alle tidligere vilkår i sin log. Dette er nødvendigt for at sikre, at alle logfiler er konsistente, og tilstandsmaskinerne udfører det samme sæt kommandoer.

Under et ledervalg inkluderer RequestVote RPC oplysninger om kandidatens log. Hvis vælgeren finder ud af, at den logger den mere opdateret, som kandidaten, stemmer den ikke for den.

Raft bestemmer, hvilken af ​​to logs der er mere opdateret ved at sammenligne indekset og udtrykket for de sidste poster i loggene. Hvis logfilerne har sidste poster med forskellige udtryk, er loggen med den senere periode mere opdateret. Hvis logfiler slutter med samme udtryk, er den log, der er længere, mere opdateret.

Klyngemedlemskab:

For at konfigurationsændringsmekanismen skal være sikker, må der ikke være noget punkt under overgangen, hvor det er muligt for to ledere at blive valgt for samme periode. Desværre er enhver tilgang, hvor servere skifter direkte fra den gamle konfiguration til den nye konfiguration, usikker.

Raft bruger en tofasetilgang til at ændre klyngemedlemskab. For det første skifter den til en mellemkonfiguration kaldet fælles konsensus. Så når det er begået, skifter det til den nye konfiguration.

Den fælles konsensus giver individuelle servere mulighed for at skifte mellem konfigurationer på forskellige tidspunkter uden at gå på kompromis med sikkerheden. Desuden giver fælles konsensus klyngen mulighed for at fortsætte med at servicere klientanmodninger gennem hele konfigurationsændringen.

Fælles konsensus kombinerer de nye og gamle konfigurationer som følger:

  • Logposter replikeres til alle servere i begge konfigurationer
  • Enhver server fra gammel eller ny kan blive førende
  • Aftalen kræver separate flertal fra både gamle og nye konfigurationer

Når en leder modtager en konfigurationsændringsmeddelelse, gemmer og replikerer den posten for deltagelse i konsensus C ew>. En server bruger altid den nyeste konfiguration i sin log til at træffe beslutninger, selvom den ikke er forpligtet. Når der er opnået fælles konsensus, kan kun servere med C < gamle, nye> i deres logfiler blive ledere.

Det er nu sikkert for lederen at oprette en logindgang, der beskriver C og replikere den til klyngen. Igen vil denne konfiguration træde i kraft på hver server, så snart den ses. Når den nye konfiguration er begået i henhold til reglerne i C, er den gamle konfiguration irrelevant, og servere, der ikke er i den nye konfiguration, kan lukkes ned.

En fantastisk visualisering af, hvordan Raft fungerer, kan findes her.

Mere materiale som foredrag, præsentationer, relaterede artikler og open source-implementeringer kan findes her.

Jeg har kun gravet ind i detaljerne i den grundlæggende algoritme, der udgør Raft og de sikkerhedsgarantier, den giver. Papiret indeholder mange flere detaljer, og det er super tilgængeligt, da forfatternes primære mål var forståelighed. Jeg anbefaler bestemt, at du læser det, selvom du aldrig har læst noget andet papir før.

Hvis du kunne lide denne artikel, skal du trykke på klappeknappen nedenfor, så flere mennesker ser den. Tak skal du have.

PS - Hvis du er kommet så langt og gerne vil modtage en mail, når jeg udgiver et af disse indlæg, kan du tilmelde dig her.