A Raft konszenzus algoritmusának megértése: tudományos cikk összefoglaló

Ez a bejegyzés összefoglalja a Raft-konszenzus-algoritmust, amelyet Diego Ongaro és John Ousterhout Az érthető konszenzus-algoritmus keresése című cikkben mutattak be. Az összes húzó idézet abból a papírból származik.

Tutaj:

A Raft egy elosztott konszenzusos algoritmus. Úgy tervezték, hogy könnyen érthető legyen. Megoldja azt a problémát, hogy több szerver is megegyezzen egy megosztott állapotban, még a hibák ellenére is. A megosztott állapot általában egy adatszerkezet, amelyet egy replikált napló támogat. Szükségünk van a rendszer teljes működőképességére, amíg a szerverek többsége fent van.

A Raft úgy működik, hogy megválasztja a vezetőt a klaszterben. A vezető felelős az ügyfélkérések elfogadásáért és a napló más szerverekre történő replikációjának kezeléséért. Az adatok csak egy irányban áramlanak: vezetőről más szerverekre.

A tutaj három részproblémára bontja a konszenzust:

  • Vezetői választás: Új vezetőt kell választani a meglévő kudarca esetén.
  • Napló replikáció: A vezetőnek replikáció útján szinkronban kell tartania az összes szerver naplóit a sajátjaival.
  • Biztonság: Ha az egyik kiszolgáló naplóbejegyzést követett el egy adott indexnél, akkor egyetlen másik szerver sem alkalmazhat más naplóbejegyzést az adott indexhez.

Alapok:

Minden szerver a három állam egyikében létezik: vezető, követő vagy jelölt.

Normál üzemben pontosan egy vezető van, és az összes többi szerver követő. A követők passzívak: önállóan nem adnak ki kéréseket, hanem egyszerűen válaszolnak a vezetők és a jelöltek kéréseire. A vezető kezeli az összes ügyfélkérést (ha egy ügyfél kapcsolatba lép egy követővel, a követő átirányítja a vezetőhöz). A harmadik államot, a jelöltet új vezető megválasztására használják.

A tutaj kifejezésekre osztja az időtönkényes hosszúságú, mindegyik választással kezdődik. Ha egy jelölt megnyeri a választásokat, akkor a ciklus hátralévő részében vezető marad. Ha a szavazás megoszlik, akkor ez a ciklus vezető nélkül ér véget.

A szám kifejezés monoton növekszik. Minden szerver tárolja az aktuális kifejezés számátamelyet minden kommunikáció során cserélnek is.

.. ha az egyik szerver jelenlegi futamideje kisebb, mint a másiké, akkor az aktuális kifejezését nagyobb értékre frissíti. Ha egy jelölt vagy vezető felfedezi, hogy mandátuma elavult, azonnal visszatér a követői állapotra. Ha egy szerver elavult kifejezésszámú kérést kap, elutasítja a kérést.

A Raft két távoli eljáráshívást (RPC) használ az alapművelet végrehajtásához.

  • A RequestVotes-t a jelöltek a választások során használják
  • Az AppendEntries alkalmazást a vezetők használják a naplóbejegyzések replikálásához, valamint szívdobbanásként (egy jel annak ellenőrzésére, hogy a szerver fenn van-e vagy sem - nem tartalmaz naplóbejegyzéseket)

Vezetőválasztás

A vezető rendszeresen szívdobbanást küld követőinek, hogy fenntartsák a tekintélyt. A vezetőválasztást akkor indítják el, amikor egy követő elévül, miután megvárja a vezető szívdobbanását. Ez a követő áttér a tagjelölt államra, és növeli a tagok számát . Miután megszavazta magát, a RequestVotes RPC-t párhuzamosan adja ki a fürt többi tagjával. Három eredmény lehetséges:

  1. A jelölt a szerverek többségétől megkapja a szavazatokat, és vezetővé válik. Ezután szívverésüzenetet küld a fürt többi tagjának a tekintély megalapozása érdekében.
  2. Ha más jelöltek megkapják az AppendEntries RPC-t, akkor ellenőrzik akifejezés száma. Ha a kifejezés száma nagyobb, mint a sajátjuk, akkor elfogadják a kiszolgálót vezetőként, és visszatérnek követői állapotba. Ha a kifejezés száma kisebb, elutasítják az RPC-t, és továbbra is jelöltek maradnak.
  3. A jelölt sem veszít, sem nem nyer. Ha egyszerre több szerver válik jelöltté, akkor a szavazat egyértelmű többség nélkül felosztható. Ebben az esetben új választások kezdődnek, miután az egyik jelölt időtúllépést mutat.
A Raft randomizált választási időkorlátokat használ annak biztosítására, hogy az osztott szavazatok ritkák legyenek és gyorsan megoldódjanak. A megosztott szavazások elkerülése érdekében a választások időkorlátjait véletlenszerűen, rögzített időközönként választják meg (pl. 150–300 ms). Ez elosztja a szervereket, így a legtöbb esetben csak egyetlen szerver fog időtúllépni; megnyeri a választást, és szívveréseket küld, mielőtt bármilyen más szerver időtúllépést jelentene. Ugyanezt a mechanizmust használják a megosztott szavazatok kezelésére. Minden jelölt a választások kezdetekor újraindítja a véletlenszerű választások időkorlátját, és a következő választások megkezdése előtt megvárja, amíg ez az időkorlát letelik; ez csökkenti az új választásokon az újabb részenkénti szavazások valószínűségét.

Napló replikáció:

Feltételezzük, hogy az ügyfélkérések egyelőre csak írási jellegűek. Minden kérés egy parancsból áll, amelyet ideális esetben az összes szerver replikált állapotgépei hajtanak végre. Amikor a vezető ügyfélkérést kap, új bejegyzésként hozzáadja a saját naplójához. Minden naplóbejegyzés:

  • Az ügyfél által megadott parancsot tartalmazza
  • Van indexe a naplóba történő bejegyzés helyének azonosításához (az index 1-től kezdődik)
  • Van egy terminusszáma, amely logikusan azonosítja a bejegyzés írásának időpontját

A naplók következetességének megőrzése érdekében meg kell replikálnia a bejegyzést az összes követő csomóponton. A vezető párhuzamosan adja ki az összes többi kiszolgálónak az AppendEntries RPC-ket. A vezető ezt addig próbálja újra, amíg az összes követő biztonságosan megismétli az új bejegyzést.

Amikor a bejegyzést a szerver többségéhez replikálja a vezető, aki létrehozta, akkor elkötelezettnek tekintik. Az összes korábbi bejegyzést, beleértve a korábbi vezetők által készítetteket is, elkötelezettnek tekintjük. A vezető végrehajtja a bejegyzést, miután elkötelezte magát, és visszaadja az eredményt az ügyfélnek.

A vezető a naplóban tartja a legmagasabb indexet, amelyet tud elkötelezni, és az AppendEntries RPC-kkel küldi el követőinek. Miután a követők megtudták, hogy a bejegyzés megtörtént, a bejegyzést rendben alkalmazza az államgépére.

A Raft a következő tulajdonságokat tartja fenn, amelyek együttesen alkotják a Naplóillesztési tulajdonságot. • Ha a különböző naplókban szereplő két bejegyzésnek ugyanaz az indexe és a terminusa, akkor ugyanazt a parancsot tárolja: • Ha a különböző naplók két bejegyzésének ugyanaz az indexe és a kifejezés, akkor a naplók minden előző bejegyzésben megegyeznek.

Az AppendEntries RPC küldésekor a vezető tartalmazza az új bejegyzést közvetlenül megelőző bejegyzés kifejezés számát és indexét. Ha a követő nem talál egyezést ehhez a bejegyzéshez a saját naplójában, elutasítja az új bejegyzés hozzáfűzésére vonatkozó kérelmet.

Ez a konzisztencia-ellenőrzés lehetővé teszi a vezető számára a következtetést, hogy valahányszor az AppendEntries sikeresen visszatér egy követőtől, azonos naplóikkal rendelkeznek, amíg az index nem szerepel az RPC-ben.

De a vezetők és követők naplói következetlenné válhatnak a vezető összeomlása esetén.

A Raft-ban a vezető az inkonzisztenciákat úgy kezeli, hogy a követők naplóit a sajátjainak másolására kényszeríti. Ez azt jelenti, hogy az ütköző naplókba ütköző bejegyzéseket felülírják a vezető naplójának bejegyzéseivel.

A vezető megpróbálja megtalálni az utolsó indexet, ahol a naplója megegyezik a követőével, törli az esetleges további bejegyzéseket, és hozzáadja az újakat.

A vezető minden egyes követő számára fenntart egy nextIndex-et, amely a következő naplóbejegyzés indexe, amelyet a vezető elküld az adott követőinek. Amikor egy vezető először hatalomra kerül, az összes nextIndex-értéket inicializálja az indexhez, közvetlenül a napló utolsó értéke után.

Amikor az AppendRPC hibával tér vissza egy követőhöz, a vezető csökkenti a következőIndex értéketés kiad egy másik AppendEntries RPC-t. Végül a nextIndexértéket ér el, ahol a naplók összefutnak. Az AppendEntries sikeres lesz, ha ez megtörténik, és eltávolíthatja az idegen bejegyzéseket (ha vannak ilyenek), és újakat adhat hozzá a vezetők naplójába (ha vannak ilyenek). Ezért a követői sikeres AppendEntries garantálja, hogy a vezető naplója összhangban legyen vele.

Ezzel a mechanizmussal a vezetőnek nem kell külön intézkedéseket tennie a naplóállomány konzisztenciájának helyreállítása érdekében, amikor hatalomra kerül. Most kezdődik a normál működés, és a naplók automatikusan összefognak az Append-Entries konzisztencia-ellenőrzés hibáira reagálva. A vezető soha nem írja felül vagy törli a bejegyzéseket a saját naplójában.

Biztonság:

A Raft megbizonyosodik arról, hogy egy ciklus vezetője a naplójában az összes korábbi kifejezés bejegyzéseit elvégezte. Erre azért van szükség, hogy minden napló következetes legyen, és az állapotgépek ugyanazt a parancskészletet hajtsák végre.

A vezetőválasztás során a RequestVote RPC információkat tartalmaz a jelölt naplójáról. Ha a szavazó úgy találja, hogy naprakészebbé teszi, mint a jelölt, akkor nem szavaz rá.

A Raft megállapítja, hogy a két napló közül melyik naprakészebb, összehasonlítva a naplók utolsó bejegyzéseinek indexét és kifejezését. Ha a naplókban utoljára különböző kifejezések szerepelnek, akkor a későbbi kifejezéssel ellátott napló naprakészebb. Ha a naplók ugyanazzal a kifejezéssel végződnek, akkor amelyik napló hosszabb, az naprakészebb.

Klaszter tagság:

Ahhoz, hogy a konfigurációváltási mechanizmus biztonságos legyen, az átmenet során nem lehet olyan, hogy két vezetőt ugyanarra a ciklusra lehessen megválasztani. Sajnos nem biztonságos minden olyan megközelítés, ahol a szerverek közvetlenül a régi konfigurációról az új konfigurációra váltanak.

A Raft kétfázisú megközelítést alkalmaz a klasztertagság megváltoztatására. Először egy közbenső konfigurációra vált, amelyet közös konszenzusnak hívnak . Ezután, ha ez megtörtént, átáll az új konfigurációra.

A közös konszenzus lehetővé teszi az egyes szerverek számára a konfigurációk közötti váltást különböző időpontokban, a biztonság veszélyeztetése nélkül. Ezenkívül a közös konszenzus lehetővé teszi a fürt számára, hogy továbbra is kiszolgálja az ügyfélkérelmeket a konfiguráció módosítása során.

A közös konszenzus az alábbiak szerint ötvözi az új és a régi konfigurációt:

  • A naplóbejegyzéseket az összes kiszolgálóra replikálják mindkét konfigurációban
  • Bármely régi vagy új szerver válhat vezetővé
  • A megállapodás külön többséget igényel mind a régi, mind az új konfigurációktól

Amikor egy vezető konfiguráció-módosító üzenetet kap, tárolja és megismétli a C csatlakozási konszenzus bejegyzését ew>. A szerver mindig a legfrissebb konfigurációt használja a naplójában a döntések meghozatalához, még akkor is, ha nincs elkötelezve. Ha közös konszenzus születik, csak azok a szerverek válhatnak vezetővé, akiknek naplójában szerepel a C < old, new>.

Most már biztonságos a vezető számára, hogy naplóbejegyzést készítsen, amely leírja a C-t, és megismétli azt a fürtön. Ez a konfiguráció ismét minden kiszolgálón érvénybe lép, amint meglátja. Amikor az új konfigurációt a C szabályai szerint végezték el, a régi konfiguráció lényegtelen, és az új konfigurációban nem szereplő kiszolgálókat le lehet állítani.

A Raft működésének fantasztikus látványa itt található.

További anyagokat, például beszélgetéseket, előadásokat, kapcsolódó cikkeket és nyílt forráskódú megvalósításokat itt talál.

Csak a Raftot alkotó algoritmus részleteibe és az általa nyújtott biztonsági garanciákba vetettem bele. A cikk sokkal több részletet tartalmaz, és szuper megközelíthető, mivel a szerzők elsődleges célja az érthetőség volt. Mindenképpen ajánlom, hogy olvassa el, akkor is, ha még soha nem olvasott más cikket.

Ha tetszett ez a cikk, kérjük, nyomja meg az alábbi taps gombot, hogy minél többen lássák. Köszönöm.

PS - Ha eddig eljutott, és szeretne levelet kapni, valahányszor közzéteszem a bejegyzések egyikét, regisztráljon itt.