Dakle, zamislimo se. U sobi je zaključano 5 mačaka, a da bi išle probuditi vlasnika, moraju se sve međusobno dogovoriti jer vrata mogu otvoriti samo ako se njih pet na njih nasloni. Ako je jedna od mačaka Schrödingerova mačka, a druge mačke ne znaju za njegovu odluku, postavlja se pitanje: "Kako oni to mogu?"
U ovom ću vam članku na jednostavan način reći o teoretskoj komponenti svijeta distribuiranih sustava i principima njihovog rada. Također ću površno ispitati glavnu ideju na kojoj se temelji Paxos.
Kada programeri koriste cloud infrastrukture, različite baze podataka i rade u klasterima velikog broja čvorova, sigurni su da će podaci biti potpuni, sigurni i uvijek dostupni. Ali gdje su jamstva?
U biti, jamstva koja imamo su jamstva dobavljača. U dokumentaciji su opisani na sljedeći način: "Ova je usluga prilično pouzdana, ima zadani SLA, ne brinite, sve će raditi distribuirano kako očekujete."
Skloni smo vjerovati u najbolje, jer su nas pametni momci iz velikih kompanija uvjeravali da će sve biti u redu. Ne postavljamo pitanje: zašto, zapravo, to uopće može funkcionirati? Postoji li formalno opravdanje za ispravan rad takvih sustava?
Nedavno sam otišao u i bio je vrlo inspiriran ovom temom. Predavanja u školi bila su više nalik na satove matematike nego na nešto vezano uz računalne sustave. No, upravo tako su se svojedobno dokazali najvažniji algoritmi koje svakodnevno koristimo, a da toga i ne znamo.
Većina modernih distribuiranih sustava koristi Paxos konsenzusni algoritam i njegove različite modifikacije. Najbolja stvar je što se valjanost i, u principu, sama mogućnost postojanja ovog algoritma može dokazati jednostavno olovkom i papirom. U praksi se algoritam koristi u velikim sustavima koji rade na velikom broju čvorova u oblacima.
Lagana ilustracija onoga o čemu ćemo dalje raspravljati: zadatak dvojice generalaIdemo pogledati za zagrijavanje .
Imamo dvije vojske - crvenu i bijelu. Bijele trupe nalaze se u opkoljenom gradu. Crvene trupe predvođene generalima A1 i A2 nalaze se na dvije strane grada. Zadatak crvenokosih je napasti bijeli grad i pobijediti. Međutim, vojska svakog crvenog generala pojedinačno manja je od bijele vojske.
Uvjeti pobjede za crvene: oba generala moraju napasti u isto vrijeme kako bi imali brojčanu prednost nad bijelima. Da bi to učinili, generali A1 i A2 moraju se međusobno dogovoriti. Ako svi napadnu zasebno, crvenokosi će izgubiti.
Da bi postigli dogovor, generali A1 i A2 mogu slati glasnike jedni drugima preko teritorija bijelog grada. Glasnik može uspješno doći do savezničkog generala ili ga može presresti neprijatelj. Pitanje: postoji li takav slijed komunikacije između crvenokosih generala (slijed slanja glasnika od A1 do A2 i obrnuto od A2 do A1), u kojem se garantirano dogovaraju o napadu u satu X. Evo, jamstva znače da će oba generala imati nedvosmislenu potvrdu da će saveznik (drugi general) sigurno napasti u dogovoreno vrijeme X.
Pretpostavimo da A1 šalje glasnika A2 s porukom: “Napadnimo danas u ponoć!” General A1 ne može napasti bez potvrde generala A2. Ako je glasnik iz A1 stigao, tada general A2 šalje potvrdu s porukom: "Da, ubijmo bijelce danas." Ali sada general A2 ne zna je li njegov glasnik stigao ili ne, nema jamstva hoće li napad biti istodoban. General A2 sada opet treba potvrdu.
Ako dalje opišemo njihovu komunikaciju, postaje jasno da bez obzira na to koliko ciklusa razmjene poruka postoji, ne postoji način da se jamči da su oba generala primila svoje poruke (pod pretpostavkom da se bilo koji glasnik može presresti).
Problem dva generala odlična je ilustracija vrlo jednostavnog distribuiranog sustava u kojem postoje dva čvora s nepouzdanom komunikacijom. To znači da nemamo 100% jamstvo da su sinkronizirani. O sličnim problemima raspravlja se samo u širem opsegu kasnije u članku.
Uvodimo koncept distribuiranih sustava
Distribuirani sustav je skupina računala (u daljnjem tekstu ćemo ih zvati čvorovi) koja mogu razmjenjivati poruke. Svaki pojedinačni čvor je neka vrsta autonomnog entiteta. Čvor može sam obrađivati zadatke, ali da bi komunicirao s drugim čvorovima, mora slati i primati poruke.
Kako se točno implementiraju poruke, koji se protokoli koriste - to nas u ovom kontekstu ne zanima. Važno je da čvorovi distribuiranog sustava mogu međusobno razmjenjivati podatke slanjem poruka.
Sama definicija ne izgleda jako komplicirano, ali moramo uzeti u obzir da distribuirani sustav ima niz atributa koji će nam biti važni.
Atributi distribuiranih sustava
- Konkurencija – mogućnost istodobnih ili istodobnih događaja koji se događaju u sustavu. Štoviše, događaje koji se dogode na dva različita čvora smatrat ćemo potencijalno istodobnim sve dok nemamo jasan redoslijed pojavljivanja tih događaja. Ali mi ga u pravilu nemamo.
- Nema globalnog sata. Nemamo jasan redoslijed događaja zbog nedostatka globalnog sata. U običnom svijetu ljudi navikli smo na činjenicu da apsolutno imamo satove i vrijeme. Sve se mijenja kada su u pitanju distribuirani sustavi. Čak i ultraprecizni atomski satovi imaju drift, a mogu postojati situacije u kojima ne možemo reći koji se od dva događaja prvi dogodio. Stoga se ne možemo pouzdati ni u vrijeme.
- Neovisni kvar čvorova sustava. Postoji još jedan problem: nešto može poći po zlu jednostavno zato što naši čvorovi ne traju vječno. Tvrdi disk može pokvariti, virtualni stroj u oblaku može se ponovno pokrenuti, mreža može treptati i poruke će se izgubiti. Štoviše, mogu postojati situacije u kojima čvorovi rade, ali u isto vrijeme rade protiv sustava. Posljednja klasa problema čak je dobila zasebno ime: problem . Najpopularniji primjer distribuiranog sustava s ovim problemom je Blockchain. Ali danas nećemo razmatrati ovu posebnu klasu problema. Zanimat će nas situacije u kojima jednostavno jedan ili više čvorova mogu otkazati.
- Komunikacijski modeli (modeli slanja poruka) između čvorova. Već smo utvrdili da čvorovi komuniciraju razmjenom poruka. Postoje dva dobro poznata modela slanja poruka: sinkroni i asinkroni.
Modeli komunikacije između čvorova u distribuiranim sustavima
Sinkroni model – pouzdano znamo da postoji konačna poznata delta vremena tijekom kojeg će poruka zajamčeno stići od jednog čvora do drugog. Ako je to vrijeme prošlo, a poruka nije stigla, možemo sa sigurnošću reći da je čvor pokvaren. U ovom modelu imamo predvidljiva vremena čekanja.
Asinkroni model – u asinkronim modelima smatramo da je vrijeme čekanja konačno, ali ne postoji takva delta vremena nakon koje možemo jamčiti da je čvor pao. Oni. Vrijeme čekanja poruke od čvora može biti proizvoljno dugo. Ovo je važna definicija i o njoj ćemo dalje govoriti.
Koncept konsenzusa u distribuiranim sustavima
Prije nego formalno definiramo koncept konsenzusa, razmotrimo primjer situacije u kojoj nam je potreban, naime - Replikacija stroja stanja.
Imamo distribuirani dnevnik. Željeli bismo da bude konzistentan i da sadrži identične podatke na svim čvorovima distribuiranog sustava. Kada jedan od čvorova nauči novu vrijednost koju će zapisati u dnevnik, njegov zadatak postaje ponuditi tu vrijednost svim drugim čvorovima tako da se dnevnik ažurira na svim čvorovima i sustav se pomiče u novo konzistentno stanje. U ovom slučaju, važno je da se čvorovi međusobno dogovore: svi čvorovi se slažu da je predložena nova vrijednost točna, svi čvorovi prihvaćaju ovu vrijednost i samo u tom slučaju svi mogu upisati novu vrijednost u dnevnik.
Drugim riječima: niti jedan od čvorova nije prigovorio da ima relevantnije informacije, a predložena vrijednost je bila netočna. Dogovor između čvorova i dogovor o jednoj ispravnoj prihvaćenoj vrijednosti je konsenzus u distribuiranom sustavu. Zatim ćemo govoriti o algoritmima koji omogućuju da distribuirani sustav zajamčeno postigne konsenzus.
Formalnije, možemo definirati konsenzusni algoritam (ili jednostavno konsenzusni algoritam) kao određenu funkciju koja prenosi distribuirani sustav iz stanja A u stanje B. Štoviše, to stanje prihvaćaju svi čvorovi i svi ga čvorovi mogu potvrditi. Kako se pokazalo, ovaj zadatak uopće nije tako trivijalan kao što se čini na prvi pogled.
Svojstva algoritma konsenzusa
Algoritam konsenzusa mora imati tri svojstva kako bi sustav nastavio postojati i imao određeni napredak u prelasku iz stanja u stanje:
- Ugovor – svi čvorovi koji ispravno rade moraju imati istu vrijednost (u člancima se ovo svojstvo naziva i sigurnosnim svojstvom). Svi čvorovi koji trenutno funkcioniraju (nisu otkazali ili izgubili kontakt s ostalima) moraju se dogovoriti i prihvatiti neku konačnu zajedničku vrijednost.
Ovdje je važno razumjeti da se čvorovi u distribuiranom sustavu koji razmatramo žele složiti. Odnosno, sada govorimo o sustavima u kojima jednostavno nešto može zakazati (npr. zakaže neki čvor), ali u ovom sustavu definitivno nema čvorova koji namjerno rade protiv drugih (zadatak bizantskih generala). Zbog ovog svojstva sustav ostaje konzistentan.
- Integritet — ako svi čvorovi koji ispravno rade nude istu vrijednost v, što znači da svaki čvor koji ispravno radi mora prihvatiti ovu vrijednost v.
- Završetak – svi čvorovi koji ispravno rade na kraju će poprimiti određenu vrijednost (svojstvo živosti), što algoritmu omogućuje napredak u sustavu. Svaki pojedini čvor koji ispravno radi mora prije ili kasnije prihvatiti konačnu vrijednost i potvrditi je: “Za mene je ova vrijednost istinita, slažem se s cijelim sustavom.”
Primjer kako radi algoritam konsenzusa
Iako svojstva algoritma možda nisu sasvim jasna. Stoga ćemo primjerom ilustrirati kroz koje faze prolazi najjednostavniji konsenzusni algoritam u sustavu sa sinkronim modelom slanja poruka, u kojem svi čvorovi funkcioniraju prema očekivanjima, poruke se ne gube i ništa se ne kvari (događa li se to stvarno?).
- Sve počinje bračnom ponudom (Propose). Pretpostavimo da se klijent spojio na čvor pod nazivom "Čvor 1" i započeo transakciju, prosljeđujući novu vrijednost čvoru - O. Od sada ćemo zvati "Čvor 1" ponuda. Kao predlagač, “čvor 1” sada mora obavijestiti cijeli sustav da ima svježe podatke, a svim ostalim čvorovima šalje poruke: “Gledajte! Došlo mi je značenje "O" i želim ga zapisati! Molimo potvrdite da ćete također zabilježiti "O" u svoj dnevnik."
- Sljedeća faza je glasovanje za predloženu vrijednost (Voting). Čemu služi? Može se dogoditi da su drugi čvorovi primili novije informacije, a imaju podatke o istoj transakciji.
Kada čvor "Čvor 1" pošalje svoj prijedlog, ostali čvorovi provjeravaju svoje zapisnike za podatke o ovom događaju. Ako nema proturječja, čvorovi objavljuju: “Da, nemam drugih podataka za ovaj događaj. Vrijednost “O” je najnovija informacija koju zaslužujemo.”U svakom drugom slučaju, čvorovi mogu odgovoriti na “Čvor 1”: “Slušaj! Imam novije podatke o ovoj transakciji. Ne 'O', nego nešto bolje."
U fazi glasovanja, čvorovi donose odluku: ili svi prihvaćaju istu vrijednost ili jedan od njih glasa protiv, pokazujući da ima novije podatke.
- Ako je krug glasovanja bio uspješan i svi su bili za, tada sustav prelazi na novu fazu - prihvaćanje vrijednosti. “Čvor 1” prikuplja sve odgovore drugih čvorova i izvještava: “Svi su se složili oko vrijednosti “O”! Sada službeno izjavljujem da je "O" naše novo značenje, isto za sve! Zapišite to u svoju malu knjižicu, ne zaboravite. Zapiši to u svoj dnevnik!”
- Preostali čvorovi šalju potvrdu (Accepted) da su zapisali vrijednost “O”; za to vrijeme ništa novo nije stiglo (neka vrsta dvofaznog predavanja). Nakon ovog značajnog događaja smatramo da je distribuirana transakcija dovršena.
Dakle, algoritam konsenzusa u jednostavnom slučaju sastoji se od četiri koraka: predložiti, glasovati (glasovanje), prihvatiti (prihvatiti), potvrditi prihvaćanje (prihvaćeno).
Ako u nekom koraku nismo uspjeli postići dogovor, tada algoritam počinje ponovno, uzimajući u obzir informacije koje su dali čvorovi koji su odbili potvrditi predloženu vrijednost.
Algoritam konsenzusa u asinkronom sustavu
Prije ovoga je sve bilo glatko, jer smo govorili o modelu sinkronog slanja poruka. Ali znamo da smo u modernom svijetu navikli sve raditi asinkrono. Kako sličan algoritam radi u sustavu s modelom asinkronog slanja poruka, gdje vjerujemo da vrijeme čekanja na odgovor od čvora može biti proizvoljno dugo (usput, kvar čvora također se može smatrati primjerom kada čvor može odgovarati proizvoljno dugo).
Sada kada znamo kako algoritam konsenzusa funkcionira u načelu, pitanje za one radoznale čitatelje koji su dogurali ovako daleko: koliko čvorova u sustavu od N čvorova s modelom asinkrone poruke može pasti tako da sustav ipak može postići konsenzus?
Točan odgovor i obrazloženje nalaze se iza spojlera.Ispravan odgovor je: 0. Ako čak i jedan čvor u asinkronom sustavu zakaže, sustav neće moći postići konsenzus. Ova izjava je dokazana u FLP teoremu, dobro poznatom u određenim krugovima (1985, Fischer, Lynch, Paterson, poveznica na izvornik na kraju članka): “Nemogućnost postizanja distribuiranog konsenzusa ako barem jedan čvor ne uspije .”
Ljudi, onda imamo problem, navikli smo da je sve asinkrono. I evo ga. Kako nastaviti živjeti?
Samo smo pričali o teoriji, o matematici. Što znači “konsenzus se ne može postići” u prijevodu s matematičkog jezika na naš - inženjerski? To znači da se “ne može uvijek postići”, tj. Postoji slučaj u kojem se konsenzus ne može postići. Kakav je ovo slučaj?
To je upravo gore opisano kršenje svojstva živosti. Nemamo zajednički dogovor, a sustav ne može napredovati (ne može završiti u konačnom vremenu) u slučaju kada nemamo odgovor od svih čvorova. Zato što u asinkronom sustavu nemamo predvidljivo vrijeme odgovora i ne možemo znati je li se čvor srušio ili samo treba dugo da odgovori.
Ali u praksi možemo pronaći rješenje. Neka naš algoritam može dugo raditi u slučaju kvarova (potencijalno može raditi neograničeno). Ali u većini situacija, kada većina čvorova radi ispravno, imat ćemo napredak u sustavu.
U praksi se radi o djelomično sinkronim komunikacijskim modelima. Djelomična sinkronija se shvaća na sljedeći način: u općem slučaju imamo asinkroni model, ali je formalno uveden određeni koncept "globalnog vremena stabilizacije" određene vremenske točke.
Ovaj trenutak u vremenu možda neće doći još dugo, ali jednog dana mora doći. Virtualna budilica će zazvoniti i od tog trenutka možemo predvidjeti vremensku deltu za koju će poruke stići. Od tog trenutka sustav prelazi iz asinkronog u sinkroni. U praksi se bavimo upravo takvim sustavima.
Paxos algoritam rješava probleme konsenzusa
je obitelj algoritama koji rješavaju problem konsenzusa za djelomično sinkrone sustave, ovisno o mogućnosti da neki čvorovi zakažu. Autor Paxosa je . Predložio je formalni dokaz postojanja i ispravnosti algoritma 1989. godine.
Ali pokazalo se da je dokaz daleko od trivijalnog. Prva publikacija objavljena je tek 1998. (33 stranice) u kojoj se opisuje algoritam. Kako se pokazalo, to je bilo iznimno teško razumjeti, a 2001. objavljeno je objašnjenje članka koje je zauzelo 14 stranica. Opseg publikacija je naveden kako bi se pokazalo da zapravo problem konsenzusa nije nimalo jednostavan, a iza takvih algoritama stoji ogroman rad najpametnijih ljudi.
Zanimljivo je da je sam Leslie Lamport u svom predavanju primijetio da u drugom članku objašnjenja postoji jedna tvrdnja, 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 potpuno ispravno.
Za detaljnu analizu Paxosovog rada bilo bi potrebno više od jednog članka, stoga ću pokušati vrlo kratko prenijeti glavnu ideju algoritma. U poveznicama na kraju mog članka pronaći ćete materijale za daljnje poniranje u ovu temu.
Uloge u Paxosu
Paxos algoritam ima koncept uloga. Razmotrimo tri glavna (postoje modifikacije s dodatnim ulogama):
- Predlagatelji (mogu se koristiti i izrazi: voditelji ili koordinatori). To su dečki koji od korisnika uče o nekoj novoj vrijednosti i preuzimaju ulogu vođe. Njihov je zadatak pokrenuti krug prijedloga za novu vrijednost i koordinirati daljnje radnje čvorova. Štoviše, Paxos dopušta prisutnost nekoliko voditelja u određenim situacijama.
- Prihvatitelji (glasači). To su čvorovi koji glasaju za prihvaćanje ili odbijanje određene vrijednosti. Njihova je uloga vrlo važna, jer o njima ovisi odluka: u kakvo će stanje (ili neće) sustav prijeći nakon sljedeće faze konsenzusnog algoritma.
- učenici. Čvorovi koji jednostavno prihvaćaju i zapisuju novu prihvaćenu vrijednost kada se stanje sustava 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.
Pojam kvoruma
Pretpostavljamo da imamo sustav N čvorovi I od njih maksimum F čvorovi mogu zakazati. Ako F čvorovi zakažu, onda moramo imati najmanje 2F+1 akceptorski čvorovi.
To je neophodno kako bismo uvijek imali većinu, čak iu najgoroj situaciji, "dobrih" čvorova koji ispravno rade. To je Ž + 1 "dobri" čvorovi koji su se složili, a konačna vrijednost će biti prihvaćena. Inače, može doći do situacije u kojoj naše različite lokalne skupine poprimaju različita značenja i ne mogu se međusobno složiti. Dakle, potrebna nam je apsolutna većina za pobjedu na izborima.
Opća ideja o tome kako radi algoritam konsenzusa Paxos
Paxos algoritam uključuje dvije velike faze, koje su zauzvrat podijeljene u dva koraka:
- Faza 1a: Pripremite se. Tijekom pripremne faze voditelj (predlagač) obavještava sve čvorove: „Počinjemo s novom fazom glasovanja. Imamo novu rundu. Broj ove runde je n. Sada ćemo krenuti s glasanjem." Za sada samo javlja početak novog ciklusa, ali ne javlja novu vrijednost. Zadatak ove faze je pokrenuti novi krug i obavijestiti svakoga o njegovom jedinstvenom broju. Okrugli broj je važan, mora biti vrijednost veća od svih prethodnih glasova svih prethodnih vođa. Budući da će zahvaljujući okruglom broju drugi čvorovi u sustavu shvatiti koliko su noviji podaci vođe. Vjerojatno je da drugi čvorovi već imaju rezultate glasovanja iz mnogo kasnijih krugova i jednostavno će reći vođi da je u zaostatku.
- Faza 1b: Obećanje. Kada akceptorski čvorovi prime broj novog stupnja glasanja, moguća su dva ishoda:
- Broj n novog glasa veći je od broja bilo kojeg prethodnog glasanja u kojem je sudjelovao akceptant. Zatim akceptant šalje obećanje vođi da više neće sudjelovati ni u jednom glasovanju s brojem manjim od n. Ako je akceptant već glasao za nešto (tj. već je prihvatio neku vrijednost u drugoj fazi), tada svom obećanju pridaje prihvaćenu vrijednost i broj glasovanja u kojem je sudjelovao.
- Inače, ako akceptant već zna za glas većeg broja, može jednostavno zanemariti korak pripreme i ne odgovoriti vođi.
- Faza 2a: Prihvatite. Voditelj treba pričekati odgovor kvoruma (većina čvorova u sustavu) i, ako dobije potreban broj odgovora, tada ima dvije opcije za razvoj događaja:
- Neki akceptanti poslali su vrijednosti za koje su već glasali. U ovom slučaju voditelj odabire vrijednost iz glasovanja s maksimalnim brojem. Nazovimo ovu vrijednost x i ona šalje poruku svim čvorovima poput: "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 zapravo glasamo.
- Ako nitko od akceptanata nije poslao nikakve vrijednosti, već su samo obećali glasovati u ovom krugu, voditelj ih može pozvati da glasaju za njihovu vrijednost, vrijednost zbog koje je uopće postao voditelj. Nazovimo to y. Šalje poruku svim čvorovima poput: "Prihvati (n, y)", slično prethodnom ishodu.
- Faza 2b: Prihvaćeno. Nadalje, akceptorski čvorovi, po primitku poruke “Prihvati(...)” od voditelja, slažu se s njom (šalju potvrdu svim čvorovima da se slažu s novom vrijednošću) samo ako nisu obećali neke (druge) ) voditelj za sudjelovanje u glasovanju s okruglim brojem n' > n, inače ignoriraju zahtjev za potvrdu.
Ako je većina čvorova odgovorila voditelju i svi su potvrdili novu vrijednost, tada se nova vrijednost smatra prihvaćenom. hura! Ako većina nije postignuta ili postoje čvorovi koji su odbili prihvatiti novu vrijednost, tada sve počinje ispočetka.
Ovako radi algoritam Paxos. Svaka od ovih faza ima mnogo suptilnosti, praktički nismo razmatrali razne vrste kvarova, probleme više voditelja i još mnogo toga, ali svrha ovog članka je samo upoznati čitatelja sa svijetom distribuiranog računarstva na visokoj razini.
Također je vrijedno napomenuti da Paxos nije jedini te vrste, postoje i drugi algoritmi, npr. , ali to je tema za drugi članak.
Veze na materijale za daljnje proučavanje
Početni stupanj:
- , Preethi Kasireddy, članak na blogu na Mediumu
- , Adi Kancherla, članak na blogu na Mediumu
- , Ittai Abraham, blog
- , Ittai Abraham, članak na blogu
Razina Leslie Lamport:
- , 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