Pa hajde da zamislimo. U sobi je zaključano 5 mačaka, a da bi išle probudile vlasnika, potrebno je da se svi zajedno dogovore oko toga, jer mogu otvoriti vrata samo tako što će se osloniti na njih sa njih pet. Ako je jedna od mačaka Schrödingerova mačka, a druge mačke nisu svjesne njegove odluke, postavlja se pitanje: "Kako to mogu učiniti?"
U ovom članku ću vam jednostavno reći o teorijskoj komponenti svijeta distribuiranih sistema i principima njihovog rada. I također površno razmotriti glavnu ideju koja leži u osnovi Paxos'a.
Kada programeri koriste cloud infrastrukture, razne baze podataka, rade u klasterima velikog broja čvorova, sigurni su da će podaci biti konzistentni, sigurni i uvijek dostupni. Ali gdje su garancije?
U stvari, garancije koje imamo su garancije dobavljača. U dokumentaciji su opisani na sljedeći način: "Ovaj servis je prilično pouzdan, ima zadati SLA, ne brinite, sve će raditi distribuirano kako očekujete."
Skloni smo vjerovati u najbolje, jer su nas pametni stričevi iz velikih kompanija uvjeravali da će sve biti u redu. Ne pitamo se: zašto, zapravo, ovo uopće može funkcionirati? Postoji li formalno opravdanje za ispravan rad ovakvih sistema?
Nedavno sam bio u i bio je veoma inspirisan ovom temom. Predavanja u školi više su ličila na časove matematičke analize nego na bilo šta vezano za kompjuterske sisteme. Ali upravo tako su se svojevremeno dokazali najvažniji algoritmi koje svakodnevno koristimo, a da to ne slutimo.
Većina modernih distribuiranih sistema koristi Paxos konsenzus algoritam i njegove različite modifikacije. Najzgodnije je to što se valjanost i, u principu, sama mogućnost postojanja ovog algoritma može dokazati jednostavno olovkom i papirom. Istovremeno, u praksi se algoritam koristi u velikim sistemima koji rade na velikom broju čvorova u oblacima.
Lagana ilustracija onoga o čemu će se dalje govoriti: problem dva generalaHajde da pogledamo zagrevanje .
Imamo dvije vojske - crvenu i bijelu. Bijele trupe se nalaze u opkoljenom gradu. Crvene trupe predvođene generalima A1 i A2 nalaze se na dvije strane grada. Zadatak crvenokosih je da napadnu bijeli grad i pobijede. Međutim, vojska svakog crvenog generala pojedinačno je manja od vojske bijelih.
Uslovi pobede crvenokosih: oba generala moraju da napadnu istovremeno da bi imali brojčanu prednost nad belim. Da bi to učinili, generali A1 i A2 moraju se međusobno složiti. Ako svi napadnu zasebno, crvenokosi će izgubiti.
Da bi pregovarali, generali A1 i A2 mogu slati glasnike jedni drugima preko teritorije bijelog grada. Glasnik može uspješno doći do savezničkog generala ili ga neprijatelj može presresti. Pitanje: postoji li takav redosled komunikacije između crvenokosih generala (redosled slanja glasnika od A1 do A2 i obrnuto od A2 do A1), u kojem se garantovano dogovore o napadu u sat X. Evo, pod garancijama se podrazumijeva da će oba generala imati nedvosmislenu potvrdu da će saveznik (drugi general) napasti tačno u određeno vrijeme X.
Pretpostavimo da A1 šalje glasnika A2 sa porukom: "Napadnimo danas u ponoć!". General A1 ne može napasti bez potvrde generala A2. Ako je stigao glasnik iz A1, onda general A2 šalje potvrdu sa porukom: "Da, hajde da napunimo bele danas." Ali sada general A2 ne zna da li je njegov glasnik stigao ili ne, nema garancije da li će napad biti istovremen. Sada General A2 ponovo treba potvrdu.
Ako dalje opišemo njihovu komunikaciju, ispada sljedeće: bez obzira na to koliko ciklusa razmjene poruka ima, ne postoji način da se garantuje obojici generala da su njihove poruke primljene (pod pretpostavkom da bilo koji od glasnika može biti presretnut).
Problem dva generala je odlična ilustracija vrlo jednostavnog distribuiranog sistema u kojem postoje dva čvora sa nepouzdanom komunikacijom. Dakle, nemamo 100% garanciju da su sinhronizovani. O sličnim problemima samo u većem obimu kasnije u članku.
Upoznavanje sa konceptom distribuiranih sistema
Distribuirani sistem je grupa računara (u daljem tekstu čvorovi) koji mogu razmjenjivati poruke. Svaki pojedinačni čvor je neki autonomni entitet. Čvor može samostalno obraditi zadatke, ali da bi komunicirao s drugim čvorovima, mora slati i primati poruke.
Kako se poruke konkretno implementiraju, koji protokoli se koriste - to nas u ovom kontekstu ne zanima. Važno je da čvorovi distribuiranog sistema mogu međusobno razmjenjivati podatke slanjem poruka.
Sama definicija ne izgleda mnogo komplikovano, ali imajte na umu da distribuirani sistem ima niz atributa koji će nam biti važni.
Atributi distribuiranih sistema
- Istovremeno – mogućnost pojave istovremenih ili takmičarskih događaja u sistemu. Štaviše, smatraćemo da su događaji koji su se desili na dva različita čvora potencijalno istovremeni dok ne budemo imali jasan redosled u kome se ti događaji dešavaju. I obično ne radimo.
- Nema globalnog sata. Nemamo jasan redosled događaja zbog nedostatka globalnog sata. U običnom svijetu ljudi, navikli smo na činjenicu da imamo sate i vrijeme apsolutno. Sve se mijenja kada su u pitanju distribuirani sistemi. Čak i ultraprecizni atomski satovi imaju drift, a postoje situacije u kojima ne možemo reći koji se od dva događaja prvi dogodio. Stoga se ne možemo osloniti ni na vrijeme.
- Nezavisni kvar sistemskih čvorova. Postoji još jedan problem: nešto može poći po zlu jednostavno zato što naši čvorovi nisu vječni. Čvrsti disk može pokvariti, virtuelna mašina u oblaku se može ponovo pokrenuti, mreža može treptati i poruke će biti izgubljene. Štaviše, postoje situacije kada čvorovi rade, ali u isto vrijeme rade protiv sistema. Posljednja klasa problema je čak dobila poseban naziv: problem . Najpopularniji primjer distribuiranog sistema s takvim problemom je Blockchain. Ali danas nećemo razmatrati ovu posebnu klasu problema. Zanimaju nas situacije u kojima samo jedan ili više čvorova može otkazati.
- Komunikacijski modeli (modeli razmjene poruka) između čvorova. Već smo otkrili da čvorovi komuniciraju razmjenom poruka. Postoje dva dobro poznata modela razmjene poruka: sinhroni i asinhroni.
Modeli komunikacije između čvorova u distribuiranim sistemima
Sinhroni model - pouzdano znamo da postoji konačna poznata delta vremena za koju je zagarantovano da poruka stiže od jednog čvora do drugog. Ako je ovo vrijeme isteklo, a poruka nije stigla, možemo sa sigurnošću reći da je čvor otkazao. U takvom modelu imamo predvidljivo vrijeme čekanja.
Asinhroni model – u asinhronim modelima pretpostavljamo da je vrijeme čekanja konačno, ali ne postoji vremenska delta nakon koje se može garantovati da je čvor otkazao. One. vrijeme čekanja na poruku od čvora može biti proizvoljno dugo. Ovo je važna definicija i o njoj ćemo dalje govoriti.
Koncept konsenzusa u distribuiranim sistemima
Prije formalnog definiranja koncepta konsenzusa, razmotrimo primjer situacije u kojoj nam je potreban, naime − Replikacija državnog stroja.
Imamo neki distribuirani dnevnik. Željeli bismo da bude dosljedan i da sadrži identične podatke na svim čvorovima distribuiranog sistema. Kada jedan od čvorova nauči novu vrijednost koju će zapisati u dnevnik, njegov zadatak je da ponudi ovu vrijednost svim ostalim čvorovima tako da se dnevnik ažurira na svim čvorovima, a sistem prelazi u novo konzistentno stanje. Istovremeno, važno je da se čvorovi međusobno slažu: svi čvorovi se slažu da je predložena nova vrijednost ispravna, svi čvorovi prihvataju ovu vrijednost i samo u tom slučaju svi mogu upisati novu vrijednost.
Drugim riječima: nijedan od čvorova nije prigovorio da ima ažurnije informacije, a predložena vrijednost je netačna. Sporazum između čvorova i dogovor o jednoj ispravnoj prihvaćenoj vrijednosti je konsenzus u distribuiranom sistemu. Zatim ćemo govoriti o algoritmima koji omogućavaju distribuiranom sistemu da postigne konsenzus sa zagarantovanim.
Formalnije, možemo definisati konsenzus algoritam (ili jednostavno konsenzus algoritam) kao neku funkciju koja prenosi distribuirani sistem iz stanja A u stanje B. Štaviše, ovo stanje prihvataju svi čvorovi i svi čvorovi ga mogu potvrditi. Kako se ispostavilo, ovaj zadatak uopće nije tako trivijalan kao što se čini na prvi pogled.
Svojstva algoritma konsenzusa
Algoritam konsenzusa mora imati tri svojstva da bi sistem nastavio da postoji i imao određeni napredak u tranziciji iz stanja u stanje:
- sporazum – svi ispravno radni čvorovi moraju imati istu vrijednost (u člancima se ovo svojstvo nalazi i kao sigurnosno svojstvo). Svi čvorovi koji sada funkcionišu (nisu u kvaru i nisu izgubili kontakt sa ostalima) moraju se dogovoriti i prihvatiti neku konačnu zajedničku vrijednost.
Ovdje je važno razumjeti da čvorovi u distribuiranom sistemu koji razmatramo žele da se slože. Odnosno, sada govorimo o sistemima u kojima nešto jednostavno može pokvariti (na primjer, neki čvor otkaže), ali u ovom sistemu definitivno nema čvorova koji namjerno rade protiv drugih (zadatak vizantijskih generala). Zbog ovog svojstva, sistem ostaje dosljedan.
- integritet - ako svi ispravno radni čvorovi nude istu vrijednost v, tako da svaki ispravno radni čvor mora prihvatiti ovu vrijednost v.
- završetak - svi ispravno radni čvorovi će na kraju poprimiti neku vrijednost (svojstvo životnosti), što omogućava algoritmu da ima napredak u sistemu. Svaki pojedinačni čvor koji radi ispravno mora prije ili kasnije prihvatiti konačnu vrijednost i potvrditi je: "Za mene je ova vrijednost istinita, slažem se sa cijelim sistemom."
Primjer kako radi algoritam konsenzusa
Iako svojstva algoritma možda nisu sasvim jasna. Stoga ćemo na primjeru ilustrovati kroz koje faze prolazi najjednostavniji algoritam konsenzusa u sistemu sa modelom sinhrone razmjene poruka, u kojem svi čvorovi funkcionišu kako se očekuje, poruke se ne gube i ništa se ne kvari (da li se to zaista dešava?).
- Sve počinje sa ponudom za brak (Propose). Pretpostavimo da se klijent povezuje na čvor koji se zove "Čvor 1" i započinje transakciju, prenoseći novu vrijednost čvoru - O. Od sada ćemo zvati "Čvor 1" ponuda. Kako sada predlagač "Čvor 1" mora obavijestiti cijeli sistem da ima svježe podatke, a svim ostalim čvorovima šalje poruke: "Pogledajte! Dobio sam vrijednost "O" i želim je zapisati! Molimo potvrdite da ćete također upisati "O" u svoj dnevnik."
- Sljedeća faza je glasanje za predloženu vrijednost (Voting). čemu služi? Može se dogoditi da drugi čvorovi dobiju novije informacije, a imaju podatke o istoj transakciji.
Kada čvor "Čvor 1" pošalje svoj propust, ostali čvorovi provjeravaju svoje dnevnike za podatke o ovom događaju. Ako nema sukoba, čvorovi objavljuju: „Da, nemam drugih podataka za ovaj događaj. Vrijednost 'O' je najažurnija informacija koju zaslužujemo."U svakom drugom slučaju, čvorovi mogu odgovoriti na "Čvor 1": "Slušajte! Imam novije podatke o ovoj transakciji. Ne "Oh", nego nešto bolje."
U fazi glasanja čvorovi donose odluku: ili svi prihvataju istu vrijednost, ili jedan od njih glasa protiv, što znači da ima novije podatke.
- Ako je krug glasanja bio uspješan, a svi su bili za, onda sistem prelazi u novu fazu - prihvatanje vrijednosti (Accept). "Čvor 1" prikuplja sve odgovore od drugih čvorova i izvještava: "Svi su se složili oko vrijednosti 'O'! Sada i zvanično izjavljujem da je "O" naše novo značenje, isto za sve! Zapišite u svoju svesku, ne zaboravite. Pišite u svoj dnevnik!"
- Ostali čvorovi šalju potvrdu (Prihvaćeno) da su zapisali vrijednost “O” za sebe, ništa novo nije primljeno za to vrijeme (neka vrsta dvofaznog urezivanja). Nakon ovog značajnog događaja, smatramo da je distribuirana transakcija završena.
Dakle, algoritam konsenzusa u jednostavnom slučaju sastoji se od četiri koraka: predlaganje, glasanje (glasanje), prihvatanje (prihvatanje), potvrda prihvatanja (prihvaćeno).
Ako u nekom koraku ne možemo postići dogovor, algoritam se ponovo pokreće, uzimajući u obzir informacije koje su dali čvorovi koji su odbili da potvrde predloženu vrijednost.
Algoritam konsenzusa u asinhronom sistemu
Prije toga je sve bilo glatko, jer se radilo o modelu sinhrone razmjene poruka. Ali znamo da smo u modernom svijetu navikli sve raditi asinhrono. Kako sličan algoritam funkcionira u sistemu sa asinkronim modelom razmjene poruka, gdje vjerujemo da vrijeme čekanja na odgovor od čvora može biti proizvoljno dugo (usput, kvar čvora se također može uzeti u obzir kao primjer kada čvor može odgovoriti proizvoljno dugo).
Sada kada znamo kako algoritam konsenzusa funkcioniše u principu, pitanje je za one radoznale čitaoce koji su došli do ove tačke: koliko čvorova u sistemu od N čvorova sa asinhronim modelom poruke može da se spusti tako da sistem još uvek može da postigne konsenzus ?
Tačan odgovor i obrazloženje iza spojlera.Tačan odgovor je: 0. Ako se čak i jedan čvor u asinhronom sistemu pokvari, sistem neće moći postići konsenzus. Ova izjava je dokazana u dobro poznatoj FLP teoremi (1985, Fischer, Lynch, Paterson, link na original na kraju članka): “Nemogućnost postizanja distribuiranog konsenzusa ako barem jedan čvor otkaže.”
Ljudi, onda imamo problem, navikli smo da je kod nas sve asinhrono. I evo ga. Kako nastaviti živjeti?
Upravo smo pričali o teoriji, o matematici. Šta znači "konsenzus se ne može postići", prevodeći sa matematičkog jezika na naš - inženjerstvo? To znači da se „ne može uvek postići“, tj. postoji slučaj u kojem nije moguće postići konsenzus. A kakav je ovo slučaj?
To je upravo kršenje svojstva životnosti opisanog iznad. Nemamo zajednički dogovor, a sistem ne može napredovati (ne može se prekinuti u konačnom vremenu) u slučaju da nemamo odgovor od svih čvorova. Zato što u asinhronom sistemu nemamo predvidljivo vreme odgovora i ne možemo znati da li je čvor u kvaru ili je potrebno mnogo vremena da odgovori.
Ali u praksi možemo pronaći rješenje. Neka naš algoritam može raditi dugo vremena u slučaju kvarova (potencijalno može raditi neograničeno). Ali u većini situacija, kada većina čvorova ispravno funkcionira, imat ćemo napredak u sistemu.
U praksi imamo posla sa djelimično sinhronim komunikacijskim modelima. Djelomični sinhronizam se razumijeva na sljedeći način: u opštem slučaju imamo asinhroni model, ali se formalno uvodi određeni koncept “globalnog stabilizacionog vremena” određene tačke u vremenu.
Ovaj trenutak u vremenu možda neće doći proizvoljno dugo, ali jednog dana mora doći. Virtuelni budilnik će zazvoniti i od tog trenutka možemo predvideti vremensku deltu u kojoj će stići poruke. Od ove tačke, sistem prelazi iz asinhronog u sinhroni. U praksi se bavimo takvim sistemima.
Paxos algoritam rješava probleme konsenzusa
je porodica algoritama koji rješavaju problem konsenzusa za djelomično sinhrone sisteme, pod uslovom da neki čvorovi mogu otkazati. Autor Paxosa je . Predložio je formalni dokaz postojanja i ispravnosti algoritma 1989. godine.
Ali pokazalo se da dokaz nije nimalo trivijalan. Prva publikacija objavljena je tek 1998. godine (33 stranice) koja opisuje algoritam. Kako se ispostavilo, bilo je izuzetno teško razumjeti, a 2001. godine objavljeno je objašnjenje za članak na 14 stranica. Obim publikacija dat je kako bi se pokazalo da zapravo problem konsenzusa nije nimalo jednostavan, a iza ovakvih algoritama stoji ogroman rad najpametnijih ljudi.
Zanimljivo je da je i sam Leslie Lampor u svom predavanju primetio da u drugom članku-objašnjenju postoji jedan iskaz, jedan red (nije precizirao koji), koji se može tumačiti na različite načine. I zbog toga, veliki broj modernih Paxos implementacija ne radi sasvim ispravno.
Za detaljnu analizu rada Paxosa potrebno je više od jednog članka, pa ću pokušati vrlo ukratko prenijeti glavnu ideju algoritma. Na linkovima na kraju mog članka naći ćete materijale za daljnje udubljivanje u ovu temu.
Uloge u Paxosu
Paxos algoritam ima koncept uloga. Razmotrite tri glavne (postoje modifikacije s dodatnim ulogama):
- Predlagači (mogu postojati i termini: vođe ili koordinatori). To su momci koji od korisnika uče o nekom novom značenju i preuzimaju ulogu lidera. Njihov zadatak je pokrenuti krug prijedloga za novu vrijednost i koordinirati daljnje akcije čvorova. Štaviše, Paxos dozvoljava prisustvo nekoliko vođa u određenim situacijama.
- Prihvatači (glasači). Ovo su čvorovi koji glasaju da prihvate ili odbiju određenu vrijednost. Njihova uloga je veoma važna, jer od njih zavisi odluka: u kakvo će stanje sistem otići (ili ne ići) nakon sledeće faze algoritma konsenzusa.
- Učenici. Čvorovi koji jednostavno prihvataju i pišu novu prihvaćenu vrijednost kada se stanje sistema promijeni. Oni ne donose odluke, oni samo primaju podatke i mogu ih dati krajnjem korisniku.
Jedan čvor može kombinirati nekoliko uloga u različitim situacijama.
Koncept kvoruma
Pretpostavljamo da imamo sistem od N čvorovi. I većina njih F čvorovi mogu otkazati. Ako F čvorovi pokvare, onda bismo trebali imati barem 2F+1 akceptorski čvorovi.
Ovo je neophodno kako bismo uvijek, čak iu najgoroj situaciji, imali većinu „dobri“, ispravno radni čvorovi. To je Ž + 1 "dobri" čvorovi koji su se složili, a konačna vrijednost će biti prihvaćena. U suprotnom, može doći do situacije u kojoj će različite lokalne grupe poprimiti različita značenja i neće moći da se dogovore među sobom. Dakle, potrebna nam je apsolutna većina da bismo dobili glasove.
Opća ideja Paxos konsenzus algoritma
Paxos algoritam pretpostavlja dvije velike faze, koje su zauzvrat podijeljene u dva koraka:
- Faza 1a: Pripremite se. Tokom pripremne faze, voditelj (predlagač) obavještava sve čvorove: „Počinjemo novu fazu glasanja. Imamo novu rundu. Broj ove runde je n. Sada ćemo početi da glasamo." Do sada samo prijavljuje početak novog ciklusa, ali ne prijavljuje novu vrijednost. Zadatak ove faze je da pokrene novi krug i obavijesti svakoga o svom jedinstvenom broju. Okrugli broj je važan, mora biti veći od svih prethodnih glasova svih prethodnih lidera. Budući da će zahvaljujući okruglom broju drugi čvorovi u sistemu razumjeti koliko su svježi podaci lidera. Vjerovatno drugi čvorovi već imaju rezultate glasanja iz mnogo kasnijih rundi i jednostavno će reći lideru da je u zaostatku za vremenom.
- Faza 1b: Obećanje. Kada akceptorski čvorovi dobiju broj nove faze glasanja, moguća su dva ishoda:
- Broj n novog glasanja veći je od broja bilo kojeg od prethodnih glasova u kojima je akceptant učestvovao. Tada akceptant šalje obećanje lideru da više neće učestvovati ni u jednom glasanju sa brojem manjim od n. Ako je akceptant već za nešto glasao (tj. već je prihvatio neku vrijednost u drugoj fazi), onda on svom obećanju dodaje prihvaćenu vrijednost i broj glasa u kojem je učestvovao.
- U suprotnom, ako primalac već zna za glas sa visokim brojem, može jednostavno zanemariti korak pripreme i ne odgovoriti lideru.
- Faza 2a: Prihvati. Vođa treba da sačeka odgovor od kvoruma (većina čvorova u sistemu) i, ako dobije potreban broj odgovora, ima dve mogućnosti za razvoj događaja:
- Neki od učesnika su predali vrijednosti za koje su već glasali. U ovom slučaju, lider bira vrijednost iz glasova s najvećim brojem. Nazovimo ovu vrijednost x, i pošaljimo poruku poput ove svim čvorovima: "Prihvati (n, x)", gdje je prva vrijednost broj glasanja iz vlastitog koraka Predloži, a druga vrijednost je ono zbog čega su se svi okupili, tj. vrijednost za koju, u stvari, glasamo.
- Ako niko od onih koji prihvataju nije poslao nijednu vrijednost, a jednostavno su obećali da će glasati u ovom krugu, lider ih može pozvati da glasaju za njihovu vrijednost, vrijednost zbog koje je on uopće postao lider. Nazovimo to y. Šalje svim čvorovima poruku u obliku: "Prihvati (n, y)", po analogiji sa prethodnim ishodom.
- Faza 2b: Prihvaćeno. Nadalje, akceptorski čvorovi, po prijemu poruke "Prihvatam (...)", od lidera se slažu s tim (šalju potvrdu svim čvorovima da se slažu sa novom vrijednošću) samo ako nisu obećali neke (druge) lider da učestvuje u glasanju sa brojem kruga n' > ninače ignorišu upit za potvrdu.
Ako je većina čvorova odgovorila lideru i svi su potvrdili novu vrijednost, tada se nova vrijednost smatra prihvaćenom. Ura! Ako većina nije upisana ili postoje čvorovi koji su odbili prihvatiti novu vrijednost, onda sve počinje ispočetka.
Ovako radi Paxos algoritam. Svaka od ovih faza ima mnogo suptilnosti, praktički nismo razmatrali razne vrste kvarova, probleme višestrukih lidera i još mnogo toga, ali svrha ovog članka je samo da uvede čitatelja u svijet distribuiranog računarstva na vrhunskom nivou.
Također je vrijedno napomenuti da Paxos nije jedini te vrste, postoje i drugi algoritmi, na primjer, , ali ovo je tema za drugi članak.
Linkovi na materijale za dalje proučavanje
Nivo početnika:
- , Preethi Kasireddy, članak na blogu Medium
- , Adi Kancherla, članak na blogu Medium
- Ittai Abraham blog
- , Ittai Abraham, članak na blogu
Leslie Lamport Nivo:
- Fischer, Lynch i Paterson, istraživački rad, 1985
- Leslie Lamport, istraživački rad, 1998
- Leslie Lamport, istraživački rad, 2001
izvor: www.habr.com