Această postare rezumă algoritmul de consens Raft prezentat în lucrare În căutarea unui algoritm de consens de înțeles de Diego Ongaro și John Ousterhout. Toate citatele extrase sunt preluate din acea hârtie.

Intelegerea algoritmului de consens Raft un rezumat al articolului academic
Credit

Plută:

Raft este un algoritm consens distribuit. A fost conceput pentru a fi ușor de înțeles. Rezolvă problema obținerii mai multor servere de acord asupra unei stări partajate chiar și în fața eșecurilor. Starea partajată este de obicei o structură de date acceptată de un jurnal replicat. Avem nevoie ca sistemul să fie pe deplin operațional atât timp cât majoritatea serverelor sunt în funcțiune.

Raft funcționează prin alegerea unui lider în cluster. Liderul este responsabil pentru acceptarea cererilor clientului și gestionarea replicării jurnalului pe alte servere. Datele circulă numai într-o singură direcție: de la lider la alte servere.

Pluta descompune consensul în trei subprobleme:

  • Alegerea liderului: Un nou lider trebuie ales în caz de eșec al unuia existent.
  • Replicare jurnal: Liderul trebuie să păstreze jurnalele tuturor serverelor sincronizate cu ale sale prin replicare.
  • Siguranță: dacă unul dintre servere a comis o intrare jurnal la un anumit index, niciun alt server nu poate aplica o intrare jurnal diferită pentru acel index.
1611238030 769 Intelegerea algoritmului de consens Raft un rezumat al articolului academic
Pluta se asigură că aceste proprietăți sunt adevărate în orice moment.

Noțiuni de bază:

Fiecare server există în una dintre cele trei stări: lider, adept sau candidat.

1611238030 308 Intelegerea algoritmului de consens Raft un rezumat al articolului academic
Modificări de stare ale serverelor

În funcționarea normală există exact un lider și toate celelalte servere sunt adepți. Urmăritorii sunt pasivi: nu emit cereri pe cont propriu, ci răspund pur și simplu la solicitările liderilor și candidaților. Liderul gestionează toate cererile clientului (dacă un client contactează un adept, acesta îl redirecționează către lider). Al treilea stat, candidatul, este folosit pentru a alege un nou lider.

Pluta împarte timpul în termeni de lungime arbitrară, fiecare începând cu alegeri. Dacă un candidat câștigă alegerile, acesta rămâne lider pentru restul mandatului. Dacă votul este împărțit, atunci termenul respectiv se încheie fără un lider.

ad-banner

numărul termenului crește monoton. Fiecare server stochează fișierul numărul termenului curent care se schimbă și în fiecare comunicare.

.. dacă termenul curent al unui server este mai mic decât cel al celuilalt, atunci își actualizează termenul curent la valoarea mai mare. Dacă un candidat sau un lider descoperă că mandatul său este depășit, revine imediat la statutul de adept. Dacă un server primește o cerere cu un număr vechi de termen, acesta respinge cererea.

Raft folosește două apeluri de procedură la distanță (RPC) pentru a-și efectua operațiunea de bază.

  • RequestVotes este utilizat de candidați în timpul alegerilor
  • AppendEntries este utilizat de lideri pentru reproducerea intrărilor de jurnal și, de asemenea, ca o bătăi de inimă (un semnal pentru a verifica dacă un server este activat sau nu – nu conține nicio intrare de jurnal)

Alegerea liderului

Liderul trimite periodic un bătăi de inimă adepților săi pentru a-și menține autoritatea. O alegere pentru lider este declanșată atunci când un adept expiră după ce așteptă bătăile inimii de la lider. Acest adept trece la statul candidat și îl mărește numărul termenului. După ce s-a votat pentru sine, emite RequestVotes RPC în paralel cu alții din cluster. Sunt posibile trei rezultate:

  1. Candidatul primește voturi de la majoritatea serverelor și devine lider. Apoi trimite un mesaj de inimă celorlalți din cluster pentru a stabili autoritatea.
  2. Dacă alți candidați primesc AppendEntries RPC, aceștia verifică numărul termenului. Dacă numărul termenului este mai mare decât al lor, aceștia acceptă serverul ca lider și revin la starea de urmăritor. Dacă numărul termenului este mai mic, ei resping RPC și rămân în continuare un candidat.
  3. Candidatul nu pierde și nici nu câștigă. Dacă mai mult de un server devine candidat în același timp, votul poate fi împărțit fără majoritate clară. În acest caz, începe o nouă alegere după ce unul dintre candidați expiră.

Raft folosește expirări aleatorii ale alegerilor pentru a se asigura că voturile împărțite sunt rare și că acestea sunt rezolvate rapid. Pentru a preveni voturile împărțite, în primul rând, expirarea alegerilor este aleasă aleatoriu dintr-un interval fix (de exemplu, 150-300ms). Acest lucru răspândește serverele, astfel încât, în majoritatea cazurilor, un singur server va expira; câștigă alegerile și trimite bătăi de inimă înainte ca orice alte servere să expire. Același mecanism este utilizat pentru a gestiona voturile împărțite. Fiecare candidat își reluează timpul aleatoriu aleatoriu la începutul alegerilor și așteaptă să treacă acel timeout înainte de a începe următoarele alegeri; acest lucru reduce probabilitatea unui alt vot divizat în noile alegeri.

Replicare jurnal:

Se presupune că solicitările clientului sunt deocamdată numai în scriere. Fiecare cerere constă dintr-o comandă care trebuie executată în mod ideal de către mașinile de stare replicate ale tuturor serverelor. Atunci când un lider primește o cerere de client, aceasta o adaugă la propriul jurnal ca o intrare nouă. Fiecare intrare într-un jurnal:

  • Conține comanda specificată de client
  • Are un index pentru a identifica poziția intrării în jurnal (indexul începe de la 1)
  • Are o numărul termenului pentru a identifica logic când a fost scrisă intrarea

Trebuie să replice intrarea în toate nodurile adepților pentru a menține jurnalele coerente. Liderul emite RPC-uri AppendEntries către toate celelalte servere în paralel. Liderul reîncearcă acest lucru până când toți adepții reproduc în siguranță noua intrare.

Când intrarea este replicată pe majoritatea serverelor de către liderul care a creat-o, aceasta este considerată comisă. Toate intrările anterioare, inclusiv cele create de liderii anteriori, sunt, de asemenea, considerate angajate. Liderul execută intrarea după ce este angajată și returnează rezultatul clientului.

Liderul păstrează cel mai mare index pe care știe că este angajat în jurnalul său și îl trimite împreună cu RPC-urile AppendEntries către adepții săi. Odată ce adepții află că intrarea a fost comisă, aplică intrarea în mașina de stat în ordine.

Pluta menține următoarele proprietăți, care împreună constituie proprietatea de potrivire a jurnalului

• Dacă două intrări în jurnale diferite au același index și termen, atunci ele stochează aceeași comandă.

• Dacă două intrări în jurnale diferite au același index și termen, atunci jurnalele sunt identice în toate intrările precedente.

La trimiterea unui RPC AppendEntries, liderul include numărul termenului și indexul intrării care precede imediat noua intrare. Dacă urmăritorul nu poate găsi o potrivire pentru această intrare în propriul jurnal, respinge cererea de a adăuga noua intrare.

Această verificare a consistenței îi permite liderului să concluzioneze că ori de câte ori AppendEntries revine cu succes de la un adept, acestea au jurnale identice până la indexul inclus în RPC.

Dar jurnalele liderilor și ale adepților pot deveni inconsistente în fața prăbușirilor liderilor.

În Raft, liderul gestionează neconcordanțele forțând jurnalele adepților să își dubleze propriile. Aceasta înseamnă că intrările conflictuale din jurnalele de urmăritori vor fi suprascrise cu intrări din jurnalul liderului.

Liderul încearcă să găsească ultimul index în care jurnalul său se potrivește cu cel al adeptului, șterge intrări suplimentare dacă există și adaugă cele noi.

Liderul menține un nextIndex pentru fiecare adept, care este indicele următoarei înregistrări pe care liderul îl va trimite acelui adept. Când un lider ajunge la putere, acesta inițializează toate valorile nextIndex la index imediat după ultimul din jurnalul său.

Ori de câte ori AppendRPC revine cu un eșec pentru un adept, liderul scade nextIndex și emite un alt RPC AppendEntries. În cele din urmă, nextIndex va ajunge la o valoare în care converg jurnalele. AppendEntries va reuși atunci când se întâmplă acest lucru și poate elimina intrări străine (dacă există) și adăuga altele noi din jurnalul liderilor (dacă există). Prin urmare, o anexă de succes de la un adept garantează că jurnalul liderului este în concordanță cu acesta.

Cu acest mecanism, un lider nu trebuie să întreprindă acțiuni speciale pentru a restabili consistența jurnalului atunci când vine vorba de putere. Începe doar funcționarea normală, iar jurnalele converg în mod automat ca răspuns la eșecurile verificării de consistență a Anexării-intrări. Un lider nu suprascrie sau șterge niciodată intrările din propriul jurnal.

Siguranță:

Raft se asigură că liderul pentru un termen a angajat intrări din toți termenii anteriori din jurnalul său. Acest lucru este necesar pentru a vă asigura că toate jurnalele sunt coerente și că mașinile de stare execută același set de comenzi.

În timpul alegerilor pentru lider, RPC RequestVote include informații despre jurnalul candidatului. Dacă alegătorul constată că jurnalul este mai actualizat decât cel al candidatului, acesta nu votează pentru el.

Pluta determină care dintre cele două jurnale este mai actualizată comparând indexul și termenul ultimelor intrări din jurnale. Dacă jurnalele au ultimele intrări cu termeni diferiți, atunci jurnalul cu termenul ulterior este mai actualizat. Dacă jurnalele se termină cu același termen, oricare dintre jurnale mai lungi este mai actualizat.

Calitatea de membru al clusterului:

Pentru ca mecanismul de schimbare a configurației să fie sigur, nu trebuie să existe un punct în timpul tranziției în care este posibil ca doi lideri să fie aleși pentru același mandat. Din păcate, orice abordare în care serverele trec direct de la vechea configurație la noua configurație este nesigură.

Raft utilizează o abordare în două faze pentru modificarea apartenenței la cluster. În primul rând, trece la o configurație intermediară numită consens comun. Apoi, odată ce acest lucru este comis, acesta trece la noua configurație.

Consensul comun permite serverelor individuale să treacă între configurații în momente diferite, fără a compromite siguranța. Mai mult, consensul comun permite clusterului să continue să deservească solicitările clienților pe tot parcursul modificării configurației.

Consensul comun combină configurațiile noi și vechi după cum urmează:

  • Intrările de jurnal sunt replicate pe toate serverele din ambele configurații
  • Orice server vechi sau nou poate deveni lider
  • Acordul necesită majorități separate atât de configurațiile vechi, cât și de cele noi

Atunci când un lider primește un mesaj de modificare a configurației, acesta stochează și reproduce intrarea pentru consensul aderării C ew>. Un server folosește întotdeauna cea mai recentă configurație din jurnalul său pentru a lua decizii chiar dacă nu este angajat. Când se angajează un consens comun, numai serverele cu C <vechi, nou> în jurnalele lor pot deveni lideri.

Acum este sigur pentru lider să creeze o intrare jurnal care să descrie C și să o replice în cluster. Din nou, această configurație va intra în vigoare pe fiecare server de îndată ce va fi văzută. Când noua configurație a fost angajată în conformitate cu regulile C , vechea configurație este irelevantă și serverele care nu se află în noua configurație pot fi închise.

O vizualizare fantastică a modului în care funcționează Raft poate fi găsită aici.

Mai multe materiale, cum ar fi discuții, prezentări, lucrări conexe și implementări open-source pot fi găsite aici.

Am căutat doar în detaliile algoritmului de bază care alcătuiesc Raft și în garanțiile de siguranță pe care le oferă. Lucrarea conține mult mai multe detalii și este foarte accesibilă, deoarece obiectivul principal al autorilor a fost înțelegerea. Vă recomand cu siguranță să o citiți chiar dacă nu ați mai citit niciodată nicio altă lucrare.

Dacă v-a plăcut acest articol, vă rugăm să apăsați butonul de batere de mai jos pentru ca mai mulți oameni să-l vadă Mulțumesc.

PS – Dacă ați ajuns până aici și doriți să primiți un e-mail ori de câte ori public una dintre aceste postări, înscrieți-vă aici.