Pređi na sadržaj

Paksos (informatika)

S Vikipedije, slobodne enciklopedije

Paksos je skup protokola za rešavanje konsenzusa u mreži nepouzdanih procesora. Konsenzus predstavlja dogovor među grupom učesnika. Problem nastaje kada učesnici ili njihova komunikacija mogu doživeti neuspehe.

Protokoli konsenzusa su osnova za pristup replikacije mašine stanja za distribuirano računarstvo, kao što je predložio Lesli Lamport [1] i ispitao Fred Šnajder.[2] Replikacija mašine stanja je tehnika za pretvaranje algoritma u distribuiranu implementaciju otpornu na greške.

Paksos protokol je prvi put podnet 1989. godine i nazvan je po izmišljenom sistemu zakonodavnog konsenzusa koji se koristi na ostrvu Paksos u Grčkoj, gde je Lamport napisao da parlament mora da funkcioniše „iako su zakonodavci neprestano lutali i izlazili iz parlamentarne komore“. [3] Kasnije je objavljen kao članak u časopisu 1998.

Paksos skup protokola uključuje kompromise između broja procesora, broja kašnjenja poruka pre učenja dogovorene vrednosti, nivoa aktivnosti pojedinačnih učesnika, broja poslatih poruka i tipova grešaka. Iako nijedan deterministički protokol tolerantnog konsenzusa ne može garantovati napredak u asinhronoj mreži, Paksos garantuje doslednost i teško je izazvati uslove koji bi ga mogli sprečiti da napreduje.

Paksos se obično koristi tamo gde je potrebna izdržljivost (na primer, za repliciranje datoteke ili baze podataka ), u kojoj količina trajnog stanja može biti velika. Protokol pokušava da napreduje čak i tokom perioda kada određeni broj replika ne reaguje. Takođe postoji mehanizam za ispuštanje trajno neuspele replike ili za dodavanje nove replike.

Istorija[uredi | uredi izvor]

Godine 1988, Linč, Dvork i Stokmajer su demonstrirali [4] rešivost konsenzusa u širokoj porodici „delimično sinhronih“ sistema. Paksos ima velike sličnosti sa protokolom koji se koristi za dogovor u „replikaciji sa pečatom pogleda“, koji su prvi put objavili Oki i Liskov 1988. godine, u kontekstu distribuiranih transakcija. [5] Bez obzira na ovaj prethodni rad, Paksos je ponudio posebno elegantan formalizam i uključio jedan od najranijih dokaza bezbednosti za distribuirani konsenzus protokol otporan na greške.

Rekonfigurabilne mašine stanja imaju jake veze sa prethodnim radom na pouzdanim grupnim protokolima koji podržavaju dinamičko članstvo u grupi, na primer Birmanov rad iz 1985. i 1987. na virtuelno sinhronom protokolu grupnog emitovanja. [6] Međutim, grupno emitovanje nije uobičajeno u podršci izdržljivosti i rešavanju grešaka pri particionisanju. Većina pouzdanih grupnih protokola nemaju ova svojstva, koja su potrebna za implementaciju modela replikacije mašine stanja. Ova tačka je razrađena u radu Lamporta, Malkhija i Zhoua. [7]

Paksos protokoli pripadaju teorijskoj klasi rešenja problema formalizovanih kao jednoglasno slaganje sa padom sistema. Dereco, [8] C++ softverska biblioteka za replikaciju mašina stanja u oblaku, nudi Paksos protokol koji je integrisan sa samostalno upravljanim virtuelno sinhronim članstvom. Ovaj protokol se efikasno preslikava na savremeni hardver udaljenog DMA (RDMA) centra podataka (ali koristi TCP ako RDMA nije dostupan).

Pretpostavke[uredi | uredi izvor]

Da bi se pojednostavila prezentacija Paksosa, sledeće pretpostavke i definicije su predstavljene.

Procesori[uredi | uredi izvor]

  • Procesori rade proizvoljnom brzinom.
  • Procesori mogu doživeti kvarove.
  • Procesori sa stabilnom memorijom mogu ponovo da se pridruže protokolu nakon kvarova (prateći model neuspeha prilikom oporavka od pada).
  • Procesori se ne dogovaraju, ne lažu ili na drugi način pokušavaju da potkopaju protokol. (To jest, vizantijski neuspesi se ne dešavaju.)

Mreža[uredi | uredi izvor]

  • Procesori mogu slati poruke bilo kom drugom procesoru.
  • Poruke se šalju asinhrono i slanje poruke može trajati proizvoljno dugo.
  • Poruke se mogu izgubiti, promeniti redosled ili duplirati.
  • Poruke se isporučuju bez oštećenja. (To jest, vizantijski neuspesi se ne dešavaju.)

Broj procesora[uredi | uredi izvor]

Generalno, konsenzus algoritam može napredovati koristeći procesora, uprkos istovremenom kvaru bilo kog od procesora: drugim rečima, broj ispravnih procesa mora biti striktno veći od broja neispravnih procesa. Međutim, korišćenjem rekonfiguracije, može se koristiti protokol koji preživi bilo koji broj ukupnih kvarova sve dok ne više od F istovremeno ne uspe. Za Paksos protokole, ove rekonfiguracije se mogu rukovati kao zasebne konfiguracije . [9]

Svojstva sigurnosti i životnosti[uredi | uredi izvor]

Da bi garantovao bezbednost, Paksos definiše tri svojstva i obezbeđuje da se prva dva uvek poštuju, bez obzira na obrazac kvarova:

Valjanost (ili netrivijalnost )
Samo predložene vrednosti se mogu izabrati i naučiti.
Sporazum (ili doslednost, ili bezbednost )
Nijedna dva različita učenika ne mogu naučiti različite vrednosti (ili ne može biti više od jedne određene vrednosti)
Raskid (ili životnost)
Ako je predložena vrednost C, onda će na kraju učenik L naučiti neku vrednost (ako dovoljan broj procesora ostane bez grešaka).

Imajte na umu da Pakos ne garantuje da će se prekinuti, pa stoga nema svojstvo životnosti. Ovo je podržano rezultatom nemogućnosti Fišera Linča Patersona (FLP) koji kaže da protokol konzistentnosti može imati samo dva od sledećeg: bezbednost, životnost i otpornih na greške . Kako je poenta Paksosa da obezbedi toleranciju grešaka i garantuje bezbednost, ne može da garantuje i životnost.

Tipičan razvoj[uredi | uredi izvor]

U većini implementacija Paksosa, svaki proces koji učestvuje ima tri uloge; Predlagač, primalac i učenik.[10] Ovo značajno smanjuje složenost poruke, bez žrtvovanja ispravnosti.


Spajanjem uloga, protokol se „kolapsira“ u efikasnu primenu stila klijent-master-replika, koji je tipičan za baze podataka. Prednost Paksos protokola (uključujući implementacije sa spojenim ulogama) je garancija njegovih bezbednosnih svojstava .

Osnovni Paksos[uredi | uredi izvor]

Ovaj protokol je najosnovniji u porodici Paksos. Svaka „instanca“ (ili „izvršenje“) osnovnog Paksos protokola odlučuje o jednoj izlaznoj vrednosti. Protokol se odvija u nekoliko rundi. Uspešna runda ima 2 faze: fazu 1 (koja je podeljena na delove a i b) i fazu 2 (koja je podeljena na delove a i b). Pretpostavljamo asinhroni model, tako da npr. procesor može biti u jednoj fazi, dok drugi procesor može biti u drugoj.

Faza 1[uredi | uredi izvor]

Faza 1a: Priprema[uredi | uredi izvor]

Predlagač kreira poruku, koju zovemo "Priprema", označenu brojem n, koji predstavlja samo broj koji jedinstveno identifikuje ovu početnu poruku predlagača (koja se šalje primaocima). Broj n mora biti veći od bilo kog broja koji je ovaj predlagač koristio u bilo kojoj od prethodnih poruka. Zatim šalje poruku Priprema koja sadrži najmanje n kvorum primalaca. Imajte na umu da poruka Priprema sadrži samo broj n (to jest, ne mora da sadrži npr. predloženu vrednost, često označenu sa v). Predlagač odlučuje ko je u Kvorumu. Predlagač ne bi trebalo da pokrene Paksos ako ne može da komunicira sa najmanje Kvorumom primalaca.

Faza 1b: Obećanje[uredi | uredi izvor]

Bilo koji od Primalaca čeka poruku Pripremi od bilo kog Predlagača . Ako primalac primi poruku pripreme, mora da pogleda identifikacioni broj n upravo primljene poruke pripreme . Postoje dva slučaja.
Ako je n veći od svakog prethodnog broja koji je primalac primio od bilo kog predlagača, onda on mora da vrati poruku (koju nazivamo „obećanje“) predlagaču, da ignoriše sve buduće predloge koji imaju manji broj. nego n . Ako je primalac prihvatio predlog u nekom trenutku u prošlosti, on mora uključiti prethodni broj predloga, recimo m, i odgovarajuću prihvaćenu vrednost, recimo v, u svom odgovoru predlagaču.
U suprotnom (to jest, n je manje ili jednako bilo kom prethodnom predlogu koji je primalac primio od bilo kog predlagača), primalac može da ignoriše primljeni predlog. U ovom slučaju ne mora da odgovari da bi Paksos radio. Međutim, radi optimizacije, slanje odgovora o odbijanju bi reklo predlagaču da može zaustaviti svoj pokušaj da stvori konsenzus sa predlogom n .

Faza 2[uredi | uredi izvor]

Faza 2a: Prihvatanje[uredi | uredi izvor]

Ako predlagač primi obećanja od kvoruma primalaca, on treba da postavi vrednost v svom predlogu. Ako je bilo koji primalac prethodno prihvatio bilo koji predlog, onda će svoje vrednosti poslati predlagaču, koji sada mora da postavi vrednost svog predloga, v, na vrednost povezanu sa najvećim brojem predloga koji su prijavili primaoci , nazovimo to z. Ako nijedan od primalaca nije prihvatio predlog do ove tačke, onda predlagač može izabrati vrednost koju je prvobitno želeo da predloži, recimo k .
Predlagač šalje poruku prihvatanja, (n, v), kvorumu primalaca sa izabranom vrednošću za njegov predlog, v, i brojem predloga n (koji je isti kao broj sadržan u poruci priprema koja je prethodno poslata primaocima). Dakle, poruka prihvatanja je ili (n, v=z) ili, u slučaju da nijedan od primalaca prethodno nije prihvatio vrednost, (n, v=k) .

Faza 2b: Prihvaćeno[uredi | uredi izvor]

Ako Primalac primi poruku o prihvatanju (n, v) od predlagača, mora je prihvatiti ako i samo ako već nije obećao (u fazi 1b) da će razmatrati samo predloge koji imaju identifikator veći od n .
Ako primalac već nije obećao (u Fazi 1b) da će razmatrati samo predloge koji imaju identifikator veći od n, trebalo bi da registruje vrednost v (upravo primljene poruke o prihvatanju ) kao prihvaćenu vrednost (protokola) i pošalje Prihvaćena poruka predlagaču i svakom učeniku. Učenici će saznati određenu vrednost samo nakon primanja prihvaćenih poruka od većine onih koji ih prihvataju, što znači, ne nakon što dobiju samo prvu poruku o prihvatanju.
U suprotnom, može da ignoriše poruku ili zahtev Prihvati.

Imajte na umu da se konsenzus postiže kada većina primalaca prihvati isti identifikacioni broj (umesto iste vrednosti). Pošto je svaki identifikator jedinstven za predlagača i samo jedna vrednost može biti predložena po identifikatoru, svi primaoci koji prihvataju isti identifikator na taj način prihvataju istu vrednost. Paksos protokol garantuje da je konsenzus trajan i da je izabrana vrednost nepromenljiva.

Kada runde ne uspeju[uredi | uredi izvor]

Runde ne uspevaju kada više predlagača pošalje konfliktne poruke pripreme ili kada predlagač ne primi kvorum odgovora ( obećanje ili prihvaćeno ). U ovim slučajevima, mora se započeti drugi krug sa većim brojem predloga.

Paksos se može koristiti za odabir vođe[uredi | uredi izvor]

Obratite pažnju da bi predlagač u Paksosu mogao da predloži „Ja sam vođa“ (ili, na primer, „Predlagač K je lider“). [11] Zbog dogovora i garancija valjanosti Paksosa, ako ih kvorum prihvati, onda je poznato da je predlagač lider u svim ostalim čvorovima. Ovo zadovoljava potrebe izbora lidera [12] jer postoji jedan čvor koji veruje da je lider i jedan čvor za koji se zna da je lider u svakom trenutku.

Grafički prikaz toka poruka u osnovnom Paksosu[uredi | uredi izvor]

Sledeći dijagrami predstavljaju nekoliko slučajeva/situacija primene osnovnog Paksos protokola. Neki slučajevi pokazuju kako se osnovni Paksos protokol nosi sa otkazom određenih (redundantnih) komponenti distribuiranog sistema.

Imajte na umu da su vrednosti vraćene u poruci obećanja nulte vrednosti kada se prvi put napravi predlog (pošto nijedan primalac nije prihvatio vrednost ranije u ovoj rundi).

Osnovni Paksos bez grešaka[uredi | uredi izvor]

Na dijagramu ispod, postoji 1 klijent, 1 predlagač, 3 primaoca (tj. veličina kvoruma je 3) i 2 učenika (predstavljeno sa 2 vertikalne linije). Ovaj dijagram predstavlja slučaj prve runde, koja je uspešna.

Slučajevi greške u osnovnom Paksosu[uredi | uredi izvor]

Najjednostavniji slučajevi greške su neuspeh primaoca (kada dovoljan broj primaoca ostaje živ) i neuspeh suvišnog učenika. U ovim slučajevima, protokol ne zahteva nikakav „oporavak“ (tj. i dalje uspeva): nisu potrebne dodatne runde ili poruke, kao što je prikazano ispod (u sledeća dva dijagrama/slučaja).

Osnovni Paksos kada primalac zakaže[uredi | uredi izvor]

Na sledećem dijagramu, jedan od primaoca zakaže, tako da veličina kvoruma postaje 2. U ovom slučaju, osnovni Paksos protokol i dalje uspeva.

Клијент  Предлагач     Прималац      Ученик
   |         |          |  |  |       |  |
   X-------->|          |  |  |       |  |  Захтев
   |         X--------->|->|->|       |  |  Припрема(1)
   |         |          |  |  !       |  |  !! Неуспех !!
   |         |<---------X--X          |  |  Обећање(1,{Va, Vb, null})
   |         X--------->|->|          |  |  Прихвати!(1,V)
   |         |<---------X--X--------->|->|  Прихваћено(1,V)
   |<---------------------------------X--X  Одговор
   |         |          |  |          |  |


Osnovni Paksos kada suvišni učenik zakaže[uredi | uredi izvor]

U sledećem slučaju, jedan od (suvišnih) učenika ne uspeva, ali osnovni Paksos protokol i dalje uspeva. 

Клијент  Предлагач     Прималац      Ученик
   |         |          |  |  |       |  |
   X-------->|          |  |  |       |  |  Захтев
   |         X--------->|->|->|       |  |  Припрема(1)
   |         |<---------X--X--X       |  |  Обећање(1,{Va,Vb,Vc})
   |         X--------->|->|->|       |  |  Прихвати!(1,V)
   |         |<---------X--X--X------>|->|  Прихваћено(1,V)
   |         |          |  |  |       |  !  !! Неуспех !!
   |<---------------------------------X     Одговор
   |         |          |  |  |       |

Osnovni Paksos kada predlagač ne uspe[uredi | uredi izvor]

U ovom slučaju, predlagač zakaže nakon što je predložio vrednost, ali pre nego što je postignut dogovor. Konkretno, zakaže u sredini poruke o prihvatanju, tako da samo jedan primalac kvoruma prima vrednost. U međuvremenu se bira novi lider, to jest predlagač. Imajte na umu da u ovom slučaju postoje 2 kruga (krugovi idu vertikalno, od vrha do dna).



Клијент Предлагач      Прималац      Ученик
   |      |             |  |  |       |  |
   X----->|             |  |  |       |  |  Захтев
   |      X------------>|->|->|       |  |  Припрема(1)
   |      |<------------X--X--X       |  |  Обећање(1,{Va, Vb, Vc})
   |      |             |  |  |       |  |
   |      |             |  |  |       |  |  !! Лидер не успева током преноса !!
   |      X------------>|  |  |       |  |  Прихвати!(1,V)
   |      !             |  |  |       |  |
   |         |          |  |  |       |  |  !! Нови лидер !!
   |         X--------->|->|->|       |  |  Припрема(2)
   |         |<---------X--X--X       |  |  Обећање(2,{V, null, null})
   |         X--------->|->|->|       |  |  Прихвати!(2,V)
   |         |<---------X--X--X------>|->|  Прихваћено(2,V)
   |<---------------------------------X--X  Одговор
   |         |          |  |  |       |  |

Osnovni Paksos kada se sukobi više predlagača[uredi | uredi izvor]

Najsloženiji slučaj je kada više predlagača smatra sebe liderom. Na primer, trenutni lider može da zakaže i kasnije se oporavi, ali su drugi predlagači već ponovo izabrali novog lidera. Oporavljeni lider to još nije naučio i pokušava da započne jednu rundu u sukobu sa aktuelnim liderom. Na donjem dijagramu su prikazane 4 neuspešne runde, ali ih može biti više (kao što je sugerisano na dnu dijagrama).

Клијент Предлагач   Прималац         Ученик
   |      |             |  |  |       |  |
   X----->|             |  |  |       |  |  Захтев
   |      X------------>|->|->|       |  |  Припрема(1)
   |      |<------------X--X--X       |  |  Обећање(1,{null,null,null})
   |      !             |  |  |       |  |  !! Лидер заказује
   |         |          |  |  |       |  |  !! Нови лидер (зна да је последњи број био 1)
   |         X--------->|->|->|       |  |  Припрема(2)
   |         |<---------X--X--X       |  |  Обећање(2,{null,null,null})
   |      |  |          |  |  |       |  |  !! Стари лидер се опоравља
   |      |  |          |  |  |       |  |  !! Стари лидер покушава са 2, одбијено
   |      X------------>|->|->|       |  |  Припрема(2)
   |      |<------------X--X--X       |  |  Одбијање(2)
   |      |  |          |  |  |       |  |  !! Стари лидер покушава са 3
   |      X------------>|->|->|       |  |  Припрема(3)
   |      |<------------X--X--X       |  |  Обећање(3,{null,null,null})
   |      |  |          |  |  |       |  |  !! Нови лидер предлаже, одбијено
   |      |  X--------->|->|->|       |  |  Прихбати!(2,Va)
   |      |  |<---------X--X--X       |  |  Одбијање(3)
   |      |  |          |  |  |       |  |  !! Нови лидер покушава са 4
   |      |  X--------->|->|->|       |  |  Припрема(4)
   |      |  |<---------X--X--X       |  |  Обећање(4,{null,null,null})
   |      |  |          |  |  |       |  |  !! Стари лидер предлаже, одбијено
   |      X------------>|->|->|       |  |  Прихвати!(3,Vb)
   |      |<------------X--X--X       |  |  Одбијено(4)
   |      |  |          |  |  |       |  |  ... и тако даље ...

Osnovni Paksos gde primalac prihvata dve različite vrednosti[uredi | uredi izvor]

U sledećem slučaju, jedan predlagač postiže prihvatanje vrednosti V1 od strane jednog primaoca pre nego što zakaže. Novi predlagač priprema primaoce koji nikada nisu prihvatili V1, dozvoljavajući mu da predloži V2. Tada V2 prihvataju svi primaoci, uključujući i onaj koji je prvobitno prihvatio V1. 

Предлагач   Прималац     Ученик
 |  |       |  |  |       |  |
 X--------->|->|->|       |  |  Припрема(1)
 |<---------X--X--X       |  |  Обећање(1,{null,null,null})
 x--------->|  |  |       |  |  Прихвати!(1,V1)
 |  |       X------------>|->|  Прихваћено(1,V1)
 !  |       |  |  |       |  |  !! Неуспех !!
    |       |  |  |       |  |
    X--------->|->|       |  |  Припрема(2)
    |<---------X--X       |  |  Обећање(2,{null,null})
    X------>|->|->|       |  |  Прихвати!(2,V2)
    |<------X--X--X------>|->|  Прихваћено(2,V2)
    |       |  |  |       |  |

Osnovni Paksos u kom višestruka identifikacija većine nije dovoljna[uredi | uredi izvor]

U sledećem slučaju, jedan predlagač postiže prihvatanje vrednosti V1 jednog primaoca pre nego što zakaže. Novi predlagač priprema primaoce koji nikada nisu prihvatili V1, dozvoljavajući mu da predloži V2. Ovaj predlagač može da natera jednog primaoca da prihvati V2 pre nego što ne uspe. Novi predlagač pronalazi većinu koja uključuje primaoca koji je prihvatio V1 i mora ga predložiti. Predlagač uspeva da natera dva primaoca da ga prihvate pre nego što zakaže. U ovom trenutku, tri primaoca su prihvatila V1, ali ne za isti identifikator. Konačno, novi predlagač priprema većinu koja nije videla najveći prihvaćeni identifikator. Vrednost povezana sa najvećim identifikatorom u toj većini je V2, tako da ga mora predložiti. Ovaj Predlagač onda tera sve primaoce da prihvate V2, postižući konsenzus.

  Предлагач         Прималац           Ученик
 |  |  |  |       |  |  |  |  |       |  |
 X--------------->|->|->|->|->|       |  |  Припрема(1)
 |<---------------X--X--X--X--X       |  |  Обећање(1,{null,null,null,null,null})
 x--------------->|  |  |  |  |       |  |  Прихвати!(1,V1)
 |  |  |  |       X------------------>|->|  Прихваћено(1,V1)
 !  |  |  |       |  |  |  |  |       |  |  !! Неуспех !!
    |  |  |       |  |  |  |  |       |  |
    X--------------->|->|->|->|       |  |  Припрема(2)
    |<---------------X--X--X--X       |  |  Обећање(2,{null,null,null,null})
    X--------------->|  |  |  |       |  |  Прихвати!(2,V2)
    |  |  |       |  X--------------->|->|  Прихваћено(2,V2)
    !  |  |       |  |  |  |  |       |  |  !! Неуспех !!
       |  |       |  |  |  |  |       |  | 
       X--------->|---->|->|->|       |  |  Припрема(3)
       |<---------X-----X--X--X       |  |  Обећање(3,{V1,null,null,null})
       X--------------->|->|  |       |  |  Прихвати!(3,V1)
       |  |       |  |  X--X--------->|->|  Прихваћено(3,V1)
       !  |       |  |  |  |  |       |  |  !! Неуспех !!
          |       |  |  |  |  |       |  |
          X------>|->|------->|       |  |  Припрема(4)
          |<------X--X--|--|--X       |  |  Обећање(4,{V1(1),V2(2),null})
          X------>|->|->|->|->|       |  |  Прихвати!(4,V2)
          |       X--X--X--X--X------>|->|  Прихваћено(4,V2)

Osnovni Paksos gde novi predlagači ne mogu da promene postojeći konsenzus[uredi | uredi izvor]

U sledećem slučaju, jedan predlagač postiže prihvatanje vrednosti V1 od dva primaoca pre nego što on zakaže. Novi predlagač može započeti još jedan krug, ali sada je nemoguće da taj predlagač pripremi većinu koja ne uključuje najmanje jednog primaoca koji je prihvatio V1. Kao takav, iako predlagač ne vidi postojeći konsenzus, jedina opcija predlagača je da predloži već dogovorenu vrednost. Novi predlagači mogu stalno da povećavaju identifikator da bi ponovo pokrenuli proces, ali konsenzus se nikada ne može promeniti.

Предлагач    Прималац     Ученик
 |  |       |  |  |       |  |
 X--------->|->|->|       |  |  Припрема(1)
 |<---------X--X--X       |  |  Обећање(1,{null,null,null})
 x--------->|->|  |       |  |  Прихвати!(1,V1)
 |  |       X--X--------->|->|  Прихваћено(1,V1)
 !  |       |  |  |       |  |  !! Неуспех !!
    |       |  |  |       |  |
    X--------->|->|       |  |  Припрема(2)
    |<---------X--X       |  |  Обећање(2,{V1,null})
    X------>|->|->|       |  |  Прихвати!(2,V1)
    |<------X--X--X------>|->|  Прихваћено(2,V1)
    |       |  |  |       |  |

Višestruki Paksos[uredi | uredi izvor]

Tipična primena Paksosa zahteva neprekidan tok dogovorenih vrednosti koje deluju kao komande distribuiranoj mašini stanja. Ako je svaka komanda rezultat jedne instance protokola Standardnog Paksosa, rezultiraće značajnim troškovima.

Ako je vođa relativno stabilan, faza 1 postaje nepotrebna. Stoga, moguće je preskočiti fazu 1 za buduće slučajeve protokola sa istim vođom.

Grafički prikaz toka poruka u Višestrukom Paksosu[uredi | uredi izvor]

Višestruki Paksos bez kvarova[uredi | uredi izvor]

U sledećem dijagramu je prikazana samo jedna instanca (ili „izvršenje“) osnovnog Paksos protokola, sa početnim vođom (predlagačem). Višestruki Paksos sastoji od nekoliko instanci osnovnog Paksos protokola.

Клијент  Предлагач   Прималац        Ученик
   |         |          |  |  |       |  | --- Први захтев ---
   X-------->|          |  |  |       |  |  Захтев
   |         X--------->|->|->|       |  |  Припрема(N)
   |         |<---------X--X--X       |  |  Обећање(N,I,{Va,Vb,Vc})
   |         X--------->|->|->|       |  |  Прихвати!(N,I,V)
   |         |<---------X--X--X------>|->|  Примљено(N,I,V)
   |<---------------------------------X--X  Одговор
   |         |          |  |  |       |  |

Multi-Pakos kada se faza 1 može preskočiti[uredi | uredi izvor]

U ovom slučaju, sledeće instance osnovnog Paksos protokola (predstavljenog sa I+1 ) koriste istog lidera, tako da faza 1 (od ovih narednih instanci osnovnog Paksos protokola), koja se sastoji od podfaza Priprema i Obećanje, se preskače. Imajte na umu da Lider treba da bude stabilan, tj. ne bi trebalo da se ruši ili menja.

Клијент Предлагач    Прималац     Ученик
   |         |          |  |  |       |  |  --- Престојећи захтеви ---
   X-------->|          |  |  |       |  |  Захтев
   |         X--------->|->|->|       |  |  Прихвати!(N,I+1,W)
   |         |<---------X--X--X------>|->|  Прихваћено(N,I+1,W)
   |<---------------------------------X--X  Одговор
   |         |          |  |  |       |  |

Višestruki Paksos kada su uloge skupljene[uredi | uredi izvor]

Uobičajena primena Višestrukog Pakosa se sastoji u uklanjanju uloge predlagača, primaoca i učenika na „servere“. Dakle, na kraju postoje samo „Klijenti“ i „Serveri“.

Sledeći dijagram predstavlja prvu „instancu“ osnovnog Paksos protokola, kada se uloge predlagača, primoaca i učenika skupljaju u jednu ulogu, nazvanu „server“. 

Клијент      Сервери
   |         |  |  | --- Први захтев ---
   X-------->|  |  |  Захтев
   |         X->|->|  Припремни(N)
   |         |<-X--X  Обећање(N, I, {Va, Vb})
   |         X->|->|  Прихвати!(N, I, Vn)
   |         X<>X<>X  Прихваћено(N, I)
   |<--------X  |  |  Одговор
   |         |  |  |

Višestruki Paksos kada su uloge srušene i lider je stabilan[uredi | uredi izvor]

U sledećim instancama osnovnog Paksos protokola, sa istim vođom kao u prethodnim instancama osnovnog Pakos protokola, faza 1 se može preskočiti.

Клијент      Сервери
   X-------->|  |  |  Захтев
   |         X->|->|  Прихвати!(N,I+1,W)
   |         X<>X<>X  Прихваћено(N,I+1)
   |<--------X  |  |  Одговор
   |         |  |  |

Optimizacije[uredi | uredi izvor]

Da bi se smanjio broj razmenjenih poruka, poboljšao učinak protokola, itd. mogu se izvršiti brojne optimizacije. Neke od ovih optimizacija su navedene u nastavku.

„Možemo da sačuvamo poruke po cenu dodatnog kašnjenja poruke tako što imamo jednog istaknutog učenika koji obaveštava druge učenike kada sazna da je vrednost izabrana. Primaoci tada šalju prihvaćene poruke samo istaknutom učeniku. U većini aplikacija, uloge lidera i istaknutog učenika obavlja isti procesor."
„Lider može poslati svoju Pripremi i prihvati! poruku samo kvorumu primalaca. Sve dok svi primaoci u tom kvorumu rade i mogu da komuniciraju sa vođom i učenicima, nema potrebe da oni koji prihvataju koji nisu u kvorumu bilo šta rade."
„Primaocima nije važno koja će vrednost biti izabrana. Oni jednostavno odgovaraju na Pripremi i prihvati! poruke kako bi se osiguralo da se, uprkos neuspesima, može izabrati samo jedna vrednost. Međutim, ako primalac sazna koja je vrednost izabrana, može da sačuva vrednost u stabilnom skladištu i da izbriše sve druge informacije koje je tamo sačuvao. Ako primalac kasnije dobije Pripremi ili Prihvati! poruku, umesto da izvrši svoju akciju faza1b ili faza2b, može jednostavno obavestiti vođu o izabranoj vrednosti." [13]
„Umesto slanja vrednosti v, lider može da pošalje heš od v nekim primaocima u svojim porukama Prihvati!. Učenik će naučiti da je v izabran ako primi prihvaćene poruke ili za v ili svoj heš od kvoruma prihvatača, i najmanje jedna od tih poruka sadrži v, a ne svoj heš. Međutim, lider bi mogao da primi poruke obećanja koje mu govore heš vrednosti v koju mora da koristi u svojoj akciji Faze 2a, a da mu ne kaže stvarnu vrednost v. Ako se to dogodi, vođa ne može da izvrši svoju akciju Faze 2a dok ne komunicira sa nekim procesom koji zna v."
„Predlagač može da pošalje svoj predlog samo lideru, a ne svim koordinatorima. Međutim, ovo zahteva da se rezultat algoritma za izbor lidera emituje predlagačima, što bi moglo biti skupo. Dakle, možda bi bilo bolje da predlagač pošalje svoj predlog svim koordinatorima. (U tom slučaju samo koordinatori sami treba da znaju ko je vođa.)[14]
„Umesto da svaki primalac šalje prihvaćene poruke svakom učeniku, oni koji prihvataju mogu da pošalju svoje prihvaćene poruke vođi, a on može da obavesti učenike kada je vrednost izabrana. Međutim, ovo dodaje dodatno kašnjenje poruke.
„Konačno, primetite da je faza 1 nepotrebna za prvu rundu. Vođa prve runde može započeti rundu slanjem poruke Prihvati! sa bilo kojom predloženom vrednošću.“

Jeftini Paksos[uredi | uredi izvor]

Jeftini Pakos proširuje Standardni Paksos tako da toleriše F kvarova sa F+1 glavnim procesorima i F pomoćnim procesorima dinamičkim rekonfigurisanjem nakon svakog kvara.

Ovo smanjenje zahteva za procesore dolazi na štetu životnosti; ako previše glavnih procesora otkaže u kratkom vremenu, sistem se mora zaustaviti dok pomoćni procesori ne mogu ponovo da konfigurišu sistem. Tokom stabilnih perioda, pomoćni procesori ne učestvuju u protokolu.

"Sa samo dva procesora p i k, jedan procesor ne može da razlikuje kvar drugog procesora od otkaza komunikacionog medijuma. Potreban je treći procesor. Međutim, taj treći procesor ne mora da učestvuje u izboru redosleda komandi. Mora da preduzme akciju samo u slučaju da p ili k ne uspe, nakon čega ništa ne radi dok p ili k nastavljaju da sami upravljaju sistemom. Treći procesor može biti mali/spor/jeftin ili procesor koji je prvenstveno posvećen drugim zadacima. ."[15]

Tok poruka: Jeftini Višestruki Paksos[uredi | uredi izvor]

Primer koji uključuje tri glavna primaoca, jednog pomoćnog primaoca i veličinu kvoruma od tri, koji pokazuje otkaz jednog glavnog procesora i naknadnu rekonfiguraciju: 

             {  Примаоци }
Предлагач     Main       Aux    Ученик
|            |  |  |     |       |  -- Фаза2 --
X----------->|->|->|     |       |  Прихвати!(N,I,V)
|            |  |  !     |       |  --- Неуспех! ---
|<-----------X--X--------------->|  Прихваћено(N,I,V)
|            |  |        |       |  -- Неуспех детектован (само 2 су прихваћена) --
X----------->|->|------->|       |  Прихвати!(N,I,V)  (ретрансмитуј, include Aux)
|<-----------X--X--------X------>|  Прихваћено(N,I,V)
|            |  |        |       |  -- Реконфигуриши : Кворум = 2 --
X----------->|->|        |       |  Прихвати!(N,I+1,W) (Aux не учествује)
|<-----------X--X--------------->|  Прихваћено(N,I+1,W)
|            |  |        |       |

Brzi Paksos[uredi | uredi izvor]

Brzi Paksos generalizuje standardni Paksos tako što smanjuje kašnjenja poruka od kraja do kraja. U standardnom Paksosu, kašnjenje poruke od zahteva klijenta do učenja je 3. Brzi Paksos dozvoljava 2 kašnjenja poruka, ali zahteva da (1) sistem bude sastavljen od 3f+ 1 primaoca da toleriše do f grešaka (umesto klasičnog 2f+1), i (2) da klijent pošalje svoj zahtev na više destinacija .

Intuitivno, ako lider nema vrednost da predloži, onda bi klijent mogao da pošalje poruku Prihvatanje direktno primaocima. Primaoci bi odgovorili kao u osnovnom Paksosu, šaljući prihvaćene poruke vođi i svaki učenik bi postigao dva kašnjenja poruke od klijenta do učenika.

Ako vođa otkrije koliziju, on ga rešava slanjem poruke o prihvatanju za novu rundu koje se prihvataju kao i obično. Ova koordinirana tehnika oporavka zahteva četiri kašnjenja poruke od klijenta do učenika.

Konačna optimizacija se dešava kada vođa unapred specificira tehniku oporavka, dozvoljavajući primaocima da sami izvrše oporavak od kolizije. Dakle, nekoordinisani oporavak od kolizije može se desiti u tri kašnjenja poruke (i samo dva kašnjenja poruke ako su svi učenici takođe primaoci).

Tok poruka: Brz Pakos, nekonfliktan[uredi | uredi izvor]

Клијент    Лидер         Прималац      Ученик
   |         |          |  |  |  |       |  |
   |         X--------->|->|->|->|       |  |  Било који(N,I,Опоравак)
   |         |          |  |  |  |       |  |
   X------------------->|->|->|->|       |  |  Прихвати!(N,I,W)
   |         |<---------X--X--X--X------>|->|  Прихваћено(N,I,W)
   |<------------------------------------X--X  Одговор(W)
   |         |          |  |  |  |       |  |

Tok poruka: Brzi Paksosi, konfliktni predlozi[uredi | uredi izvor]

Sukobni predlozi sa koordinisanim oporavkom. Napomena: protokol ne navodi kako se postupa sa odbačenim zahtevom klijenta.

Клијент  Лидер      Прималац       Ученик
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Конкурентни конфликтне понуде
 |  |      |        |  |  |  |      |  |  !!   добијене другачијим редоследом 
 |  |      |        |  |  |  |      |  |  !!   од стране прималаца
 |  X--------------?|-?|-?|-?|      |  |  Прихвати!(N,I,V)
 X-----------------?|-?|-?|-?|      |  |  Прихвати!(N,I,W)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Примоаци се не слажу око вредности
 |  |      |<-------X--X->|->|----->|->|  Прихваћено(N,I,V)
 |  |      |<-------|<-|<-X--X----->|->|  Прихваћено(N,I,W)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Детектована колизија и опоравак
 |  |      X------->|->|->|->|      |  |  Прихвати!(N+1,I,W)
 |  |      |<-------X--X--X--X----->|->|  Прихваћено(N+1,I,W)
 |<---------------------------------X--X  Одговор(W)
 |  |      |        |  |  |  |      |  |

Sukobni predlozi sa nekoordiniranim oporavkom.

Клијент   Лидер     Прималац       Ученик



|  |      |        |  |  |  |      |  |
|  |      X------->|->|->|->|      |  |  Било који(N,I,Опоравак)
|  |      |        |  |  |  |      |  |
|  |      |        |  |  |  |      |  |  !! Конкурентне конфликтне понуде
|  |      |        |  |  |  |      |  |  !!   добијене другачијим редоследом
|  |      |        |  |  |  |      |  |  !!   од стране Прималаца
|  X--------------?|-?|-?|-?|      |  |  Прихвати!(N,I,V)
X-----------------?|-?|-?|-?|      |  |  Прихвати!(N,I,W)
|  |      |        |  |  |  |      |  |
|  |      |        |  |  |  |      |  |  !! Примаоци се не слажу око вредности
|  |      |<-------X--X->|->|----->|->|  Прихваћено(N,I,V)
|  |      |<-------|<-|<-X--X----->|->|  Прихваћено(N,I,W)
|  |      |        |  |  |  |      |  |
|  |      |        |  |  |  |      |  |  !! Детектована колизија и опоравак
|  |      |<-------X--X--X--X----->|->|  Прихваћено(N+1,I,W)
|<---------------------------------X--X  Одговор(W)
|  |      |        |  |  |  |      |  |

Tok poruka: Brz Pakos sa nekoordinisanim oporavkom, srušene uloge[uredi | uredi izvor]

Клијент        Сервери
 |  |         |  |  |  |
 |  |         X->|->|->|  Било који(N,I,Опоравак)
 |  |         |  |  |  |
 |  |         |  |  |  |  !! Конкурентне конфликтне понуде
 |  |         |  |  |  |  !!   добијене различитим редоследом
 |  |         |  |  |  |  !!   од стране Сервера
 |  X--------?|-?|-?|-?|  Прихвати!(N,I,V)
 X-----------?|-?|-?|-?|  Прихвати!(N,I,W)
 |  |         |  |  |  |
 |  |         |  |  |  |  !! Сервери се не слажу око вредности
 |  |         X<>X->|->|  Прихваћено(N,I,V)
 |  |         |<-|<-X<>X  Прихваћено(N,I,W)
 |  |         |  |  |  |
 |  |         |  |  |  |  !! Детектована колизија и опоравак
 |  |         X<>X<>X<>X  Прихваћено(N+1,I,W)
 |<-----------X--X--X--X  Одговор(W)
 |  |         |  |  |  |

Generalizovani Paksos[uredi | uredi izvor]

Generalizovani konsenzus istražuje odnos između operacija repliciranog stanja mašine i protokola konsenzusa koji ga implementira. Glavno otkriće uključuje optimizacije Paksosa kada se konfliktni predlozi mogu primeniti bilo kojim redosledom. tj. kada su predložene operacije komutativne operacije za državni stroj. U takvim slučajevima, konfliktne operacije mogu biti prihvaćene, izbegavajući odlaganja koja su potrebna za rešavanje sukoba i ponovno predlaganje odbijenih operacija.

Ovaj koncept se dalje generalizuje u stalno rastuće sekvence komutativnih operacija, od kojih se zna da su neke stabilne (i stoga se mogu izvršiti). Protokol prati ove sekvence obezbeđujući da su sve predložene operacije jedne sekvence stabilizovane pre nego što dozvoli da bilo koja operacija koja ne putuje sa njima postane stabilna.

Primer[uredi | uredi izvor]

Da bi se ilustrovao generalizovani Paksos, donji primer prikazuje tok poruka između dva klijenta koji se istovremeno izvršavaju i repliciranog državnog stroja koji implementira operacije čitanja/pisanja preko dva različita registra A i B.

Tabela komutativnosti
Pročitaj(A) Napiši(A) Pročitaj(B) Napiši (B)
Pročitaj(A) Ne
Napiši(A) Ne Ne
Pročitaj (B) Ne
napiši (B) Ne Ne

Gde u ovoj tabeli označava operacije koje nisu komutativne.

Mogući redosled operacija :|

1:Прочитај(А),2:Прочитај(Б),3:Напиши(Б),4:Прочитај(Б)5:Прочитај(А),6:Напиши(А)

Pošto 5:Прочитај(А) menja i sa 3:Напиши(Б) i 4:Read(B), jedna moguća permutacija ekvivalentna prethodnom redosledu je sledeća:

1:Прочитај(А),2:Прочитај(Б),5:Прочитај(А)3:Напиши(Б),4:Прочитај(Б),6:Напиши(А)

U praksi, premeštanje se dešava samo kada se operacije predlažu istovremeno.

Tok poruke: Generalizovani Paksos (primer)[uredi | uredi izvor]

Клијент    Лидер     Примлац       Ученик
 |  |         |      |  |  |         |  |  !! Нови лидер започиње рунду
 |  |         X----->|->|->|         |  |  Припрема(N)
 |  |         |<-----X- X- X         |  |  Обећање(N,null)
 |  |         X----->|->|->|         |  |  Фаза2(N,null)
 |  |         |      |  |  |         |  | 
 |  |         |      |  |  |         |  |  !! Конкурентни предлози
 |  X------- ?|-----?|-?|-?|         |  |  Предложи(Прочитај A)
 X-----------?|-----?|-?|-?|         |  |  Предложи(Прочитај B)
 |  |         X------X-------------->|->|  Прихваћено(N,<Прочитај A,Прочитај B>)
 |  |         |<--------X--X-------->|->|  Прихваћено(N,<Прочитај B,Прочитај A>)
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  |  !! Нема конфликта, оба прихваћена
 |  |         |      |  |  |         |  |  Стабилно = <Прочитај A, Прочитај B>
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  |  !! КОнкурентни предлози
 X-----------?|-----?|-?|-?|         |  |  Предложи(<Напиши B,Напиши A>)
 |  X--------?|-----?|-?|-?|         |  |  Предложи(Прочитај B)
 |  |         |      |  |  |         |  |
 |  |         X------X-------------->|->|  Прихваћено(N,<Напиши B,Прочитај A> . <Прочитај B>)
 |  |         |<--------X--X-------->|->|  Прихваћено(N,<Прочитај B> . <Напиши B,Прочитај A>)
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  |  !! Конфликт детектован, лидер бира редослед
 |  |         |      |  |  |         |  |  
 |  |         |      |  |  |         |  |  V = <Прочитај A, Напиши B, Прочитај B>
 |  |         |      |  |  |         |  |
 |  |         X----->|->|->|         |  |  Фаза2(N+1,V)
 |  |         |<-----X- X- X-------->|->|  Прихваћено(N+1,V)
 |  |         |      |  |  |         |  |  Стабилно = <Прочитај A, Прочитај B> .
 |  |         |      |  |  |         |  |           <Прочитај A, Напиши B, Прочитај B>
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  | !! Више конфликтних предлога
 X-----------?|-----?|-?|-?|         |  |  Предложи(Напиши A)
 |  X--------?|-----?|-?|-?|         |  |  Предложи(Прочитај A)
 |  |         |      |  |  |         |  |
 |  |         X------X-------------->|->|  Прихваћено(N+1,<Напиши A> . <Прочитај A>)
 |  |         |<--------X- X-------->|->|  Прихваћено(N+1,<Прочитај A> . <Напиши A>)
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  |  !! Лидер бира распоред:
 |  |         |      |  |  |         |  |  W = <Напиши A, Прочитај A>
 |  |         |      |  |  |         |  |
 |  |         X----->|->|->|         |  |  Фаза2(N+2,W)
 |  |         |<-----X- X- X-------->|->|  Прихваћено(N+2,W)
 |  |         |      |  |  |         |  |  Стабилно = <Прочитај A, Прочитај B> .
 |  |         |      |  |  |         |  |           <Прочитај A, Напиши B, Прочитај B> .
 |  |         |      |  |  |         |  |           <Напиши A, Прочитај A>
 |  |         |      |  |  |         |  |

Performanse[uredi | uredi izvor]

Gornji tok poruka pokazuje da generalizovani Paksos može da iskoristi semantiku operacije da izbegne kolizije kada spontano uređenje mreže ne uspe. Ovo omogućava da protokol bude u praksi brži od Brzog Pakosa. Međutim, kada dođe do sudara, Generalizovanom Paksosu su potrebna dva dodatna povratna putovanja da bi se oporavio. Ova situacija je ilustrovana operacijama NapišiB i PročitajB u gornjoj šemi.

U opštem slučaju, takva kružna putovanja su neizbežna i proizilaze iz činjenice da se više komandi može prihvatiti tokom jedne runde. Ovo čini protokol skupljim od Paksosa kada su sukobi česti.

  • Prvo, ako je koordinator deo svakog kvoruma primalaca (krug N se naziva centriranim), onda da bi se oporavio u krugu N+1 od kolizije u krugu N, koordinator preskače fazu 1 i u fazi 2 predlaže sekvencu koju je poslednji prihvatio tokom runde N. Ovo smanjuje troškove oporavka na jedno povratno putovanje.
  • Drugo, ako oba kruga N i N+1 koriste jedinstven i identičan centrirani kvorum, kada primalac otkrije koliziju u krugu N, on spontano predlaže u krugu N+1 sekvencu sa sufiksom oba (i) sekvencu prihvaćenu u krugu N od strane koordinatora i najveći nekonfliktni prefiks koji je prihvatio u rundi N. Na primer, ako su koordinator i primalac prihvatili respektivno u rundi N <NapišiB, PročitajB> i <PročitajB, PročitajA>, primalac će spontano prihvatiti < NapišiB, PročitajB, PročitajA> u rundi N+1. Sa ovom varijacijom, cena oporavka je kašnjenje jedne poruke, što je očigledno optimalno. Primetite ovde da upotreba jedinstvenog kvoruma na rundi ne šteti životnosti. Ovo dolazi iz činjenice da svaki proces u ovom kvorumu je kvorum za čitanje za fazu pripreme narednih rundi. [16]

Vizantijski Paksos[uredi | uredi izvor]

Paksos se takođe može proširiti da podrži proizvoljne neuspehe učesnika, uključujući laganje, izmišljanje poruka, dosluh sa drugim učesnicima, selektivno neučestvovanje, itd. Ove vrste neuspeha se nazivaju vizantijskim neuspesima, prema rešenju koje je popularizovao Lamport.

Vizantijski Paksos [17] koji su predstavili Kastro i Liskov dodaje dodatnu poruku (Potvrdu) koja služi za distribuciju znanja i proveru akcija drugih procesora:

Tok poruka: Vizantijski Multi-Paksos, stabilno stanje[uredi | uredi izvor]



Клијент   Предагач     Прималац    Ученик
   |         |          |  |  |       |  |
   X-------->|          |  |  |       |  |  Захтев
   |         X--------->|->|->|       |  |  Прихвати!(N,I,V)
   |         |          X<>X<>X       |  |  Верификуј(N,I,V) - BROADCAST
   |         |<---------X--X--X------>|->|  Прихваћено(N,V)
   |<---------------------------------X--X  Одговор(V)
   |         |          |  |  |       |  |

Brzi vizantijski Paksos [18] koji su uveli Martin i Alvisi uklanja ovo dodatno kašnjenje, pošto klijent šalje komande direktno primaocima.

Imajte na umu da se prihvaćena poruka u Brzom Vizantijskom Paksosu šalje svim primaocima i svim učenicima, dok Brzi Pakos šalje prihvaćene poruke samo učenicima.

Tok poruka: Brzi vizantijski Višestruki Paksos, stabilno stanje[uredi | uredi izvor]




Клијент   Прималац    Ученик
   |      |  |  |       |  |
   X----->|->|->|       |  |  Пријвати!(N,I,V)
   |      X<>X<>X------>|->|  Прихваћено(N,I,V) - BROADCAST
   |<-------------------X--X  Одговор(V)
   |      |  |  |       |  |


Scenario neuspeha je isti za oba protokola; Svaki učenik čeka da dobije F+1 identične poruke od različitih primalaca. Ako se to ne dogodi, sami primaoci će takođe biti svesni toga (pošto su razmenili poruke jedni drugima u rundi emitovanja), a ispravni primalac će ponovo emitovati dogovorenu vrednost:

Tok poruka: Brzi vizantijski višestruki Paksos, neuspeh[uredi | uredi izvor]

Клијент   Прималац    Ученик
   |      |  |  !       |  |  !! Један Прималац греши
   X----->|->|->!       |  |  Прихвати!(N,I,V)
   |      X<>X<>X------>|->|  Прихваћено(N,I,{V,W}) - BROADCAST
   |      |  |  !       |  |  !! Ученик добија 2 команде
   |      |  |  !       |  |  !! Правилан Прималац примећује грешку
   |      X<>X<>X------>|->|  Пеихваћено(N,I,V) - BROADCAST
   |<-------------------X--X  Одоговор(V)
   |      |  |  !       |  |

Prilagođavanje Paksosa za RDMA mreže[uredi | uredi izvor]

Sa pojavom veoma brzih i pouzdanih mreža centara podataka koje podržavaju udaljeni DMA (RDMA), postojao je značajan interes za optimizaciju Paksosa kako bi se iskoristio rasterećenje hardvera, u kojem kartica mrežnog interfejsa i mrežni ruteri obezbeđuju pouzdanost i kontrolu zagušenja na nivou mreže, oslobađajući centralni procesor domaćina za druge zadatke. Dereco C++ Paksos biblioteka je Paksos implementacija otvorenog koda koja istražuje ovu opciju.

Dereco nudi i klasični Paksos, sa izdržljivošću podataka kroz sekvence potpunog isključivanja/restarta, i vertikalni Paksos (atomsko višestruko emitovanje), za replikaciju u memoriji i sinhronizaciju sa stanjem mašine. Paksos protokoli koje koristi Dereco morali su da budu prilagođeni da maksimiziraju asinhroni protok podataka i uklone druge izvore kašnjenja na kritičnom putu lidera. Ovo omogućava Derecu da održi punu dvosmernu brzinu RDMA podataka. Nasuprot tome, iako tradicionalni Paksos protokoli mogu da se migriraju na RDMA mrežu jednostavnim mapiranjem operacija slanja poruke u matične RDMA operacije, to ostavlja povratna kašnjenja na kritičnom putu. U RDMA mrežama velike brzine, čak i mala kašnjenja mogu biti dovoljno velika da spreče korišćenje punog potencijalnog propusnog opsega.

Reference[uredi | uredi izvor]

  1. ^ Lamport, Leslie (1978). „Time, clocks, and the ordering of events in a distributed system”. Communications of the ACM. 21 (7): 558—565. S2CID 215822405. doi:10.1145/359545.359563. 
  2. ^ Schneider, Fred B. (1990). „Implementing fault-tolerant services using the state machine approach: A tutorial”. ACM Computing Surveys. 22 (4): 299—319. CiteSeerX 10.1.1.69.1536 Slobodan pristup. S2CID 678818. doi:10.1145/98163.98167. 
  3. ^ Leslie Lamport's history of the paper
  4. ^ Dwork, Cynthia; Lynch, Nancy; Stockmeyer, Larry (1988). „Consensus in the presence of partial synchrony”. Journal of the ACM. 35 (2): 288—323. CiteSeerX 10.1.1.13.3423 Slobodan pristup. doi:10.1145/42282.42283. 
  5. ^ Oki, Brian M.; Liskov, Barbara H. (1988). „Viewstamped replication: A general primary copy”. Proceedings of the seventh annual ACM Symposium on Principles of distributed computing - PODC '88. str. 8—17. ISBN 0-89791-277-2. doi:10.1145/62546.62549. 
  6. ^ Birman, Kenneth P.; Joseph, Thomas A. (1987). „Reliable communication in the presence of failures”. ACM Transactions on Computer Systems. 5: 47—76. S2CID 11224827. doi:10.1145/7351.7478. hdl:1813/6534. 
  7. ^ Lamport, Leslie; Malkhi, Dahlia; Zhou, Lidong (2010). „Reconfiguring a state machine”. ACM Sigact News. 41: 63—73. CiteSeerX 10.1.1.212.2168 Slobodan pristup. S2CID 15189602. doi:10.1145/1753171.1753191. 
  8. ^ Jha, Sagar; Behrens, Jonathan; Gkountouvas, Theo; Milano, Mae; Song, Weijia; Tremel, Edward; Renesse, Robbert Van; Zink, Sydney; Birman, Kenneth P. (2018). „Derecho: Fast State Machine Replication for Cloud Services”. ACM Transactions on Computer Systems. 36 (2): 1—49. S2CID 218482757. doi:10.1145/3302258. 
  9. ^ Van Renesse, Robbert; Altinbuken, Deniz (2015-02-17). „Paxos Made Moderately Complex”. ACM Computing Surveys. 47 (3): 42:1—42:36. ISSN 0360-0300. doi:10.1145/2673577. 
  10. ^ Chandra, Tushar D.; Griesemer, Robert; Redstone, Joshua (2007). „Paxos made live: An engineering perspective”. Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing. str. 398—407. ISBN 978-1-59593-616-5. S2CID 207164635. doi:10.1145/1281100.1281103. 
  11. ^ „Leader Election, Why Should I Care?”. Elastic Blog. 13. 9. 2013. Pristupljeno 27. 2. 2021. 
  12. ^ I. Gupta, R. van Renesse, and K. P. Birman, 2000, A Probabilistically Correct Leader Election Protocol for Large Groups, Technical Report, Cornell University
  13. ^ Lamport, Leslie; Massa, Mike (2004). "Cheap Paxos". Proceedings of the International Conference on Dependable Systems and Networks (DSN 2004).
  14. ^ Lamport, Leslie (2005). "Fast Paxos".
  15. ^ Lamport, Leslie; Massa, Mike (2004). "Cheap Paxos". Proceedings of the International Conference on Dependable Systems and Networks (DSN 2004).
  16. ^ Lamport, Leslie; Malkhi, Dahlia; Zhou, Lidong (2009). „Vertical paxos and primary-backup replication”. Proceedings of the 28th ACM symposium on Principles of distributed computing. PODC '09. New York, NY, USA: ACM. str. 312—313. CiteSeerX 10.1.1.150.1791 Slobodan pristup. ISBN 9781605583969. doi:10.1145/1582716.1582783. 
  17. ^ Castro, Miguel; Liskov, Barbara (februar 1999). „Practical Byzantine Fault Tolerance” (PDF). Proceedings of the Third Symposium on Operating Systems Design and Implementation: 173—186. Pristupljeno 5. 3. 2018. 
  18. ^ Martin, Jean-Philippe; Alvisi, Lorenzo (jul 2006). „Fast Byzantine Consensus” (PDF). IEEE Transactions on Dependable and Secure Computing. 3 (3): 202—215. doi:10.1109/TDSC.2006.35. Pristupljeno 5. 3. 2018. 
Preuzeto iz „https://sr.wikipedia.org/w/index.php?title=Паксос_(информатика)&oldid=27865047”