A Paxos a szívében nagyon egyszerű

a Paxos algoritmus egyszerű angol nyelven bemutatva nagyon egyszerű. – Leslie Lamport 2001

megpróbálom megmagyarázni az egyetlen rendeletet Paxos oly módon, remélhetőleg, ez könnyen érthető.

a mai napig, IMO, John Ousterhout előadása Paxos még mindig a legjobb odakint. Az ebben a bejegyzésben szereplő anyag nagymértékben kölcsönöz Ousterhout professzor előadásától. John Ousterhout beleegyezésével felhasználtam néhány diáját, hogy megmagyarázzam Paxost.

konszenzus

a Paxos protokollként megpróbálja megoldani a konszenzus problémáját. Egyszerű angol nyelven, megpróbálja megoldani azt a problémát, hogy a rendszer csak akkor választ egy értéket, ha egy vagy több szerver különböző értékeket javasolhat.

a valós példa valami olyan lenne, mint egy választás. Az emberek különböző elnökekre szavazhatnak. De csak egy elnököt lehet választani.

a Paxos-t úgy tervezték, hogy kezelje a fail-stop/crash (nem Bizánci) és az üzenet késleltetését/elvesztését. Szintén van egy elevenség követelmény, hogy néhány javasolt érték végül választott, amíg a legtöbb szerver fut. Ennek célja az olyan érdektelen megoldások elkerülése, mint a soha nem fogad el értéket. Ha nem teszel semmit, akkor nem teszel semmi rosszat. Hasonlóképpen, nem akarod, hogy egynél több elnököt válasszanak, és végül egy elnököt akarsz, amíg az emberek szavaznak.

mellékesen megjegyzem, hogy őszinte legyek, azt hiszem, hogy a szavazást példaként használni a Paxos magyarázatához, az eredeti részmunkaidős parlamenti dokumentumban nagyon természetes. De valahogy nem működött túl jól. Lamport maga is elmondta egy interjúban, hogy ez teljes kudarc, ami sajnálatos.

egyetlen akceptor

Screen-Shot-2018-11-13-at-11.17.43-PM
a klaszter 2F+1 szerverek, mi történik, ha mindig, hogy egy bizonyos dobozt, hogy elfogadja javaslatokat. És azt a javaslatot, amit a doboz Elfogad, kiválasztják.

ennek a megközelítésnek az a problémája, hogy egyetlen lefelé mutató doboz elérhetetlenné teheti a szolgáltatást. De a követelmény szerint a szolgáltatásnak mindaddig működnie kell, amíg a szerverek többsége fut (ebben az esetbenF+1).

figyeljük meg, hogy ez gyakorlatilag egyetlen mester replikációs modell. Pontosan ezért elkerülhetetlen a leállás a master-slave replikációval.

Quorum

tehát ha egyetlen elfogadó nem működik, akkor talán meg kellene várnunk, amíg több szerver elfogadja a javaslatot, mielőtt igényelnénk egy értéket.

hány?

ha az akceptorok fixek, és <=F, akkor ismét nem toleráljuk a F összeomlott szervereket. Ha az akceptorok bármelyik szerver lehetnek, és <=F, akkor a 2F+1 szerverek klaszterében két különböző javaslatunk lehet két diszjunkt akceptorkészlethez, ami két értéket választ.

tehát az akceptorok számának >=F+1 – nak kell lennie. Mivel minél kevesebb az akceptor, annál jobb, menjünk a F+1 – val. Ez lehet bármely F+1 szerver a fürtben.

már tettünk némi előrelépést! Ha a F+1 szerverek bármelyik javaslatot elfogadják, akkor azt választják.

javaslatok elfogadása

most nézzük meg, hogy az elfogadóknak hogyan kell eldönteniük, hogy elfogadják-e a javaslatot vagy sem.

csak az első javaslatot fogadja el?
Screen-Shot-2018-11-13-at-11.17.27-PM

nem működne, mert végül soha nem választhatunk olyan értéket, mint a fenti eset. Ez sérti az élőség követelményét.

nincs értelme azt mondani, hogy fogadja el a második javaslatot, vagy ilyesmi, mert soha nem lehet tudni, hogy lesz-e valaha második javaslat.

tehát el kell fogadnunk az első javaslatot, de talán nem csak az első javaslatot.

minden javaslatot Elfogad?
Screen-Shot-2018-11-13-at-11.31.11-PM
ez sértené a biztonsági követelményt, mivel végül egynél több értéket választhatunk.

Core

itt jön a trükk, ami szerintem a Paxos legérdekesebb része.

miután kiválasztottak egy értéket, a jövőbeli javaslatoknak ugyanazt az értéket kell javasolniuk.

ez azt jelenti, hogy kétfázisú protokollra lenne szükség. Az első szakaszban a javaslattevőknek ki kell deríteniük, hogy választottak-e már valamilyen értéket. Javaslat a második szakaszban.

ha Ön elosztott rendszer veterán, akkor az előző nyilatkozatban már észrevett egy kulcsszót. És ez a “jövő”. Korábban átnéztem az időt és a rendet. Az elosztott rendszer a megrendelésről szól. a “jövő” itt azt jelenti, hogy a megrendelés (történik-a kapcsolat előtt). Tehát minden javaslatot meg kell rendelnünk. Ezután az alábbi példában elutasíthatjuk a red – et, mert tudjuk, hogy a blue van kiválasztva, a red pedig egy régi javaslat.

Screen-Shot-2018-11-13-at-11.39.37-PM

szavazólap száma

a javaslatok megrendelésének egyszerű módja az, hogy minden javaslathoz egyedi szavazólapszám legyen <seq_id, server_id>formában. Annak érdekében, hogy garantálja a rendelés, seq_id fenn kell tartani cross crash/restart. Tehát tartósan helyben kell tárolni.

Paxos

most mindannyian fel vagyunk állítva a valódi kétfázisú Paxos protokoll leírására. Az első fázist prepare fázisnak, a második fázist accept fázisnak nevezzük. prepare a fázis két célt szolgál egy oda-vissza út során.

  1. Ismerje meg a már kiválasztott értékeket
  2. megakadályozza, hogy az elfogadók elfogadják a régebbi javaslatokat (nagyon hasonlóan a tartalék lépéshez két fázisban)

Screen-Shot-2018-11-13-at-11.53.52-PM
az Elfogadónak tartósan tárolnia kell néhány dolgot

  • minProposal
  • acceptedProposal
  • acceptedValue
    vegye figyelembe, hogy a “broadcast to all servers” helyett “legalább F+1 szerverekre kell sugározni”. A javaslattevőnek az accept üzenetet ugyanannak az F+1 kiszolgálónak kell elküldenie, mint az előkészítési szakaszban.

nézzük meg alaposan az egyes lépéseket.

előkészítési szakasz

ebben a szakaszban a javaslattevő megpróbál ígéretet kapni az Elfogadótól, hogy nem fogad el nála régebbi javaslatokat. Ugyanakkor az elfogadók tájékoztatják a javaslattevőket arról, hogy milyen értékeket fogadtak el eddig.

a 3 és 4 lépésben a javaslattevő megváltoztatja javaslatát a legutóbbi elfogadott javaslatra az elfogadóktól, akikkel beszélt. Nagyon konzervatívnak tűnik, mert előfordulhat, hogy egy elfogadott javaslatot kap, amelyet nem választottak meg, és a javaslattevő végül feladja a javaslatát. De ez rendben van, mivel csak a konszenzus érdekel. Az első szakaszban a javaslattevő számára nehéz tudni, hogy értéket választanak-e vagy sem. Az elfogadott érték nem választható. De a választott értéket a szerverek többségének el kell fogadnia! Az elfogadók elutasítják a régebbi javaslatokat (6 lépés). Két invariánssal tudjuk, hogy az első fázisban a javaslathoz visszatért legújabb elfogadott javaslatot vagy már kiválasztották, vagy jelenleg nem választottak értéket. Akárhogy is, biztonságos ezt az értéket javasolni.

miért kell nyomon követni a minProposal – et?
két versenyzői javaslat is lehet a felkészülési szakaszban, de még semmit sem fogadtak el. Ez azt jelenti, hogy mindketten az elfogadás fázisába lépnek. Az összes javaslat teljes megrendelésének és a F+1 követelménynek köszönhetően legalább egy elfogadó látja az újabb javaslatot, és elutasítja a vesztes/régebbi javaslat accept üzenetét. Az invariáns itt az, hogy minProposal >= acceptedProposal.

Screen-Shot-2018-11-14-at-12.28.11-AM

valószínűleg ez a legérdekesebb eset, mivel a második javaslattevő nem látta a korábban elfogadott értéket, és az előkészítési szakaszban nem választottak értéket. Ebben az esetben továbbküldi a accept(Y) – t más szerverekre. Mivel a S3 megígérte, hogy csak a 4.5 – nél később fogadja el a javaslatokat, elutasítja a X – et. Ha nem követjük nyomon a minProposal – et, az X – et S3fogadja el. Akkor mind az X, mind a Y három szerver elfogadta volna, és kiválasztottnak tekintették volna, ami sérti a biztonsági követelményt.

itt van. Ez az egyetlen rendelet Paxos. Ezt mondják, a Paxos végrehajtása nagyon-nagyon nehéznek bizonyult.

  1. Paxos egyszerű https://lamport.azurewebsites.net/pubs/paxos-simple.pdf ↩︎

  2. a részmunkaidős Parlament https://lamport.azurewebsites.net/pubs/lamport-paxos.pdf ↩︎

  3. Paxos made live https://www.cs.utexas.edu/users/lorenzo/corsi/cs380d/papers/paper2-1.pdf ↩︎

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

Az e-mail-címet nem tesszük közzé.