Paxos sen ytimessä on hyvin yksinkertainen

Paxos-algoritmi on selkokielellä esitettynä hyvin yksinkertainen. — Leslie Lamport. 2001

aion yrittää selittää yhden asetuksen Paxos tavalla, toivottavasti, joka on helppo ymmärtää.

tähän päivään, IMO, John Ousterhout ‘ s lecture on Paxos it still the BEST out there. Tämän postauksen materiaali lainaa voimakkaasti professori Ousterhoutin luentoa. John Ousterhoutin suostumuksella käytin hänen diojaan Paxosin selittämiseen.

konsensus

Paxos yrittää protokollana ratkaista konsensusongelmaa. Selkokielellä ilmaistuna se yrittää ratkaista ongelman, että järjestelmä valitsee vain yhden arvon, kun yksi tai useampi palvelin voi ehdottaa eri arvoa.

reaalimaailman esimerkki olisi jotain vaalien kaltaista. Ihmiset voivat äänestää eri presidenttiä. Mutta vain yksi presidentti voidaan valita.

Paxos on suunniteltu käsittelemään vikaantumista / kaatumista (ei-bysanttilainen) ja viestin viivästymistä/häviämistä. Lisäksi on liveness vaatimus, että jokin ehdotettu arvo on lopulta valittu niin kauan kuin suurin osa palvelimista on käynnissä. Näin vältetään epäkiinnostavia ratkaisuja, kuten koskaan-hyväksy-mitään-arvoa. Jos et tee mitään, et tee mitään väärää. Vastaavasti ei haluta, että valitaan useampi kuin yksi presidentti ja halutaan lopulta presidentti niin kauan kuin ihmiset äänestävät.

Sivuhuomautuksena, ollakseni rehellinen, minusta on hyvin luonnollista yrittää käyttää äänestystä esimerkkinä Paxosin selittämiseksi parlamentin alkuperäisessä osa-aikaisessa asiakirjassa. Mutta jotenkin se ei toiminut kovin hyvin. Lamport sanoi myös itse haastattelussa, että se on täydellinen epäonnistuminen, mikä on valitettavaa.

yksi vastaanottaja

Screen-Shot-2018-11-13-at-11.17.43-PM
kun klusteri on 2F+1 palvelimia, mitä tapahtuu, jos teemme aina yhden tietyn laatikon hyväksyäksemme ehdotuksia. Ja minkä tahansa ehdotuksen se laatikko hyväksyy valitaan.

tämän lähestymistavan ongelmana on se, että yksi alas-ruutu voi estää Palvelun käytön. Vaatimuksen mukaan palvelun on kuitenkin oltava toiminnassa niin kauan kuin suurin osa palvelimista on toiminnassa (F+1 tässä tapauksessa).

huomaa, että kyseessä on käytännössä yksi master replikointimalli. Juuri tämän takia seisokit ovat väistämättömiä isäntä-orja-replikaatiossa.

päätösvaltainen

joten jos yhden vastaanottajan saaminen ei toimi, ehkä meidän pitäisi odottaa, kunnes useat palvelimet ovat hyväksyneet ehdotuksen, ennen kuin vaadimme arvon valintaa.

kuinka monta?

jos vastaanottimet ovat kiinteitä ja se on <=F, emme taaskaan siedä F kaatuneita palvelimia. Jos vastaanottajat voivat olla mitä tahansa palvelimia ja se on <=F, klusterissa 2F+1 palvelimia, meillä saattaa olla kaksi eri ehdotusta menee kaksi disjoint joukko hyväksyjiä aiheuttaa kaksi arvoa valitaan.

joten hyväksyjien määrän on oltava >=F+1. Koska vähemmän vastaanottajia parempi, mennään vain F+1. Ja se voi olla mikä tahansa F+1 palvelimia klusterissa.

olemme jo jonkin verran edistyneet! Jos F+1 palvelimet hyväksyvät jonkin ehdotuksen, se valitaan.

ehdotusten hyväksyminen

nyt katsotaan, miten hyväksyjien pitäisi päättää, hyväksyvätkö he ehdotuksen vai eivät.

hyväksy vain ensimmäinen ehdotus?
Screen-Shot-2018-11-13-at-11.17.27-PM

se ei toimisi, koska voimme päätyä koskaan ole mitään arvoa valittu kuten yllä olevassa tapauksessa. Tämä rikkoo eloisuusvaatimusta.

ei ole järkeä sanoa hyväksyvänsä toista kosintaa tai muuta vastaavaa, koska koskaan ei voi tietää, tuleeko toista kosintaa koskaan.

joten meidän on hyväksyttävä ensimmäinen ehdotus, mutta ei ehkä vain ensimmäinen ehdotus.

hyväksy jokainen ehdotus?
Screen-Shot-2018-11-13-at-11.31.11-PM
tämä rikkoisi turvallisuusvaatimusta, koska meillä voi lopulta olla useampi kuin yksi arvo valittuna.

ydin

tässä tulee temppu, joka on mielestäni Paxosin kiinnostavin osa.

kun arvo on valittu, tulevien ehdotusten on ehdotettava samaa arvoa.

tämä tarkoittaa, että tarvittaisiin kaksivaiheinen protokolla. Ensimmäisessä vaiheessa ehdottajien on selvitettävä, onko jokin arvo jo valittu. Ja ehdottaa toisessa vaiheessa.

jos olet hajautetun järjestelmän veteraani, sinun on täytynyt huomata jo yksi avainsana edellisessä lauseessa. Ja se on “tulevaisuus”. Tarkistin ajan ja järjestyksen aiemmin. Hajautetussa järjestelmässä on kyse tilaamisesta. “tulevaisuus” tarkoittaa tässä tilaamista (tapahtua-ennen suhdetta). Meidän on siis tilattava kaikki ehdotukset. Sitten alla olevassa esimerkissä voimme hylätä red, koska tiedämme, että blue on valittu ja red on vanha ehdotus.

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

äänestysnumero

helppo tapa tilata ehdotuksia on saada jokaiselle ehdotukselle yksilöllinen äänestysnumero muodossa <seq_id, server_id>. Tilauksen takaamiseksi seq_id on jatkettava cross crash / restart. Se on siis säilytettävä kestävästi paikallisesti.

Paxos

nyt kaikki on asetettu kuvaamaan todellista kaksivaiheista Paxos-protokollaa. Ensimmäistä vaihetta kutsutaan prepare – vaiheeksi ja toista vaihetta accept – vaiheeksi. prepare vaihe palvelee kahta tarkoitusta yhdellä edestakaisella matkalla.

  1. ota selvää jo valituista arvoista
  2. estä hyväksyjiä hyväksymästä vanhempia ehdotuksia (hyvin paljon kuin Varausvaihe kaksivaiheisessa toimituksessa)

Screen-Shot-2018-11-13-at-11.53.52-PM
Acceptor on kestävästi tallentaa muutamia asioita

  • minProposal
  • acceptedProposal
  • acceptedValue
    huomaa, että sen sijaan “lähettää kaikille palvelimille”, sen pitäisi olla “lähettää vähintään F+1 palvelimille”. Ja ehdottajan tulisi lähettää hyväksymisviesti samalle joukolle F + 1-palvelimia kuin valmisteluvaiheessa.

tarkastellaan jokaista askelta tarkasti.

valmisteluvaihe

tässä vaiheessa ehdottaja yrittää saada acceptorilta lupauksen olla hyväksymättä yhtään häntä vanhempaa ehdotusta. Samalla hyväksyjät ilmoittavat ehdottajille, mitkä arvot on jo tähän mennessä hyväksytty.

vaiheessa 3 ja 4 ehdottaja muuttaa ehdotuksensa viimeisimmäksi hyväksytyksi ehdotukseksi, jonka hyväksyjät ovat hänelle puhuneet. Se tuntuu olevan hyvin konservatiivinen, koska saatat saada hyväksytyn ehdotuksen, jota ei ole valittu ja ehdottaja päätyy luopumaan ehdotuksestaan. Mutta se ei haittaa, koska välitämme vain konsensuksesta. Ensimmäisessä vaiheessa ehdottajan on vaikea tietää, onko jokin arvo valittu vai ei. Hyväksyttyä arvoa ei välttämättä valita. Mutta valitun arvon on hyväksyttävä suurin osa palvelimista! Ja hyväksyjät hylkäävät vanhemmat ehdotukset (vaihe 6). Kahdesta invariantista tiedämme, että viimeisin hyväksytty ehdotus, joka palautettiin ehdotukseen ensimmäisessä vaiheessa, on joko jo valittu, tai mitään arvoa ei ole tällä hetkellä valittu. Joka tapauksessa, on turvallista ehdottaa sitä arvoa.

miksi pitää kirjaa minProposal?
valmisteluvaiheessa voi olla kaksi kisaehdotusta, kun mitään ei ole vielä hyväksytty. Tämä tarkoittaa, että molemmat siirtyvät hyväksymään vaiheen. Kaikkien ehdotusten kokonaistilauksen ja F+1 vaatimuksen ansiosta ainakin yksi hyväksyjä näkee uudemman ehdotuksen ja hylkää hävinneen/vanhemman ehdotuksen accept viestin. Invariantti tässä on, että minProposal >= acceptedProposal.

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

tämä lienee kiinnostavin tapaus, sillä toinen ehdottaja ei nähnyt aiemmin hyväksyttyä arvoa eikä arvoa valittu tuolloin valmisteluvaiheessa. Tällöin se menee eteenpäin ja lähettää accept(Y) muille palvelimille. Koska S3 on luvannut, että se hyväksyy ehdotukset vasta myöhemmin kuin 4.5, se hylkää X. Jos emme pidä kirjaa minProposal, X hyväksytään S3. Silloin sekä X että Y olisi hyväksytty kolme palvelinta ja katsottu valituiksi, mikä rikkoo turvallisuusvaatimusta.

siinä se on. Tämä on yksittäinen asetus Paxos. Paxosin toteuttaminen on osoittautunut erittäin vaikeaksi.

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

  2. osa-aikainen parlamentti 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 ↩︎

Vastaa

Sähköpostiosoitettasi ei julkaista.