Elosztott rendszerekben mi lehet a Paxos algoritmus egyszerű magyarázata?

Legjobb válasz

Ez a cikk feltűnően egyértelmű magyarázatot és igazolást nyújt: http://pdos.csail.mit.edu/6.824/papers/paxos-simple.pdf

Ide megpróbálok világos összefoglalót adni:

A A Paxos algoritmus arra szolgál, hogy bizonyos számú társ megegyezzen egy értékben. A Paxos garantálja, hogy ha az egyik társ úgy véli, hogy valamilyen értékben többség állapodott meg, a többség soha nem állapodik meg más értékben. A protokoll úgy van kialakítva, hogy minden megállapodásnak mennie kell a csomópontok többségén keresztül. Minden jövőbeni megegyezési kísérletnek, ha sikeres, át kell mennie legalább egy ilyen csomóponton is. Így: Minden olyan csomópontnak, amely a döntés meghozatala után javaslatot tesz, A protokoll garantálja, hogy megtanulja a korábban ag-t a többség értékére támaszkodva.

Így működik:

Tegyük fel, hogy 3 csomópontunk van, A, B és C. A szeretne javaslatot tenni “Foo” érték.

Az algoritmus 3 fázisban működik. Minden szakaszban el kell érni a csomópontok többségének megerősítését.

Először megvan az előkészítési szakasz. A egy előkészítési kérelmet küld A, B és C részére. Paxos sorszámokra támaszkodik garantálja. Az előkészítési kérelem egy csomópontot kér az ígérethez: “Soha nem fogadok el olyan javaslatot, amelynek sorszáma kisebb, mint az előkészítési kérelemben szereplő.” A csomópontok bármely olyan értékkel válaszolnak, amellyel korábban megállapodtak (ha van ilyen). (És ez kritikus fontosságú): Az A csomópontnak javaslatot kell tennie arra az értékre, amelyet a legmagasabb sorszámmal kap. Ez a művelet garantálja a korábban elfogadott értékek megőrzését.

Ezután megkapjuk az elfogadás fázist. A egy elfogadási kérelmet küld A, B és C részére. Az elfogadási kérelem a következőket mondja ki: ” Elfogadja a foo-t? ” Ha a kísérő sorszám nem haladja meg azt, amit a csomópont korábban megígért, vagy azt kérte, amelyet a csomópont korábban elfogadott, akkor elfogadja az új értéket és sorszámot.

Ha az A csomópont fogadja, akkor az elfogadja a csomópontok többsége, az érték eldől. A Paxos ezen fordulója soha soha nem fog elfogadni egy másik értéket.

A harmadik szakasz nem feltétlenül szükséges, de döntő fontosságú optimalizálás bármely gyártott Paxos megvalósításban. Miután A megkapja az elfogadás többségét, döntött üzeneteket küld A, B és C. Ezek az üzenetek minden társának tudtára adják, hogy értéket választottak, és felgyorsítják a döntési folyamat végét.

Ezen üzenet nélkül a többi társnak meg kell próbálnia értéket javasolni a megállapodás megismerése érdekében. Az előkészítés szakaszában megtudnák a korábban elfogadott értéket. Amint a megállapodást megkötötték, a csomópont felismeri a megállapodást.

Itt néhány kulcsfontosságú kérdést áttekintettem:

  1. Minden sorozatszámnak monoton növekvőnek kell lennie, és csomópontonként egyedinek kell lennie . Vagyis A és B nem küldhet k üzenet sorszámú üzenetet. A protokollban elküldött összes üzenet sorszámokat tartalmaz. A csomópontnak követnie kell a látott legmagasabb elfogadási kérelmet, valamint az előkészítési szakaszban ígért legmagasabb értéket.
  2. Meghibásodás feltételei. Nagyon lehetséges, hogy egy forduló Paxos kudarcot vall. Meghibásodás esetén az egyik csomópont egyszerűen megpróbálja újra javaslatot tenni nagyobb sorszámmal.
  3. Megszüntetési feltételek. A leírt Paxos verzió nem feltétlenül fejeződik be. Néhány befejezésre van szükség a megszüntetés hivatalos igazolásához.

Válasz

Mivel a Paxos konszenzusra jut, emellett az elosztott adatbázisban lévő írások lemásolására is használható. garantálni tudja az események következetes sorrendjét a csoport összes csomópontja között. A Chubby by Google a Paxost használja az erősen konzisztens fájlok kiszolgálására. Innen ered a zavar. Milyen kapcsolat van ekkor a nézet szinkron és a paxos között, ha mindkettő használható replikációra?

Kis előzmények: A Lamport a 80-as évek elején vezette be az államgép-replikáció fogalmát. Az állapotgépi replikáció azt jelenti, hogy egy rendszer az eseményeket ugyanabban a sorrendben juttatja el az összes csomóponthoz, és ezeket feldolgozzuk determinisztikusan, garantálva a csoport összes csomópontjának következetes állapotát. Ennek a koncepciónak a bevezetésekor azonban mindenféle feltételezést felvetett, beleértve a hálózat szinkron működését is.Az állami gépi replikáció tehát csupán elméleti eszköz maradt, gyakorlati felhasználás nélkül. A nézet szinkronit ezen a ponton vezették be, és célja a következetesség elérése volt, ilyen feltételezések nélkül. A cél az volt, hogy legyen egy gyakorlati rendszer, amely ilyen garanciákat nyújt.

A Paxos közzététele akkor történt, amikor a nézet szinkronizálása folyamatban volt. A Paxos elérheti az állapotgép replikációt, mivel a replikák ezzel a konszenzusos algoritmussal megállapodhatnak az ügyfélkérelmek végrehajtási sorrendjében. A Paxos nem feltételezett szinkron hálózatot vagy hibákat. A Paxos egy csoporttagsági protokollt is nyújtott. A nézetszinkron és a Paxos között most megmaradt különbségek csak az absztrakciók megfogalmazásának módjában voltak. Mindkettő dinamikus tagságot biztosít, és hasonlóan kezeli a kudarcokat. A különbségek valójában csak a modellben vannak. Néhány kiemelhető különbség a következő:

  • A Virtual Synchronynak egyszerű csoporttagsági protokollja van a Paxoshoz képest. A Virtuális szinkronizálás külön szolgáltatásként futtatja a csoporttagságot.
  • A Paxos előreléphet a partíció bizonyos eseteiben, ahol a virtuális szinkron blokkol.
  • A virtuális szinkron gyorsabb, mint a kortárs Paxos.

Mindkét rendszer fejlődött és konvergált . A jelenlegi helyzetben nagyon nehéz szignifikáns különbségeket levonni a kettő között.

Lalith világosan elmagyarázza a Virtual Synchrony protokollt, és helyesen rámutat, hogy a Paxos vagy bármely más konszenzusváltozat használható a nézet szinkronban. A Paxos a konszenzustól eltekintve csoporttagságot és egyéb szolgáltatásokat nyújt, amelyeket a virtuális szinkron már biztosít. Mivel mind a virtuális szinkron, mind a Paxos ugyanazokat a garanciákat nyújtja, és ugyanabban az időben lettek kifejlesztve, a virtuális szinkron szekvencia specifikációja nem használja a Paxos-t konszenzusra. A virtuális szinkronmodell azonban a teljesen rendezett küldési protokollt (más néven ABCAST) használja az atomi sugárzáshoz, és egy másik protokollt a csoportnézetek frissítéséhez, és ezek a konszenzusvariánsként használja.

Érdekes lehet megjegyezni, hogy az ISIS-2 futásidejű modell a Paxos modellt a virtuális szinkron modellel ötvözi, nem konszenzus érdekében, hanem azért, hogy a csoporttagságot külön szolgáltatásként vegye figyelembe a Paxosban. Ez gyorsabbá teszi a Paxost azokban az esetekben, amikor a tagság nem változik dinamikusan. A virtuális szinkron és a Paxos kombinálásával az ISIS2 képes kihagyni bizonyos lépéseket, amelyeket a tipikus Paxos-nak végre kell hajtania. Lényegében a Paxos és a Virtual Synchrony különböző modellek ugyanazon funkcionalitás elérése érdekében, és kombinálhatók egymással változatok vagy optimalizációk elérése érdekében.

Vélemény, hozzászólás?

Az email címet nem tesszük közzé. A kötelező mezőket * karakterrel jelöltük