🥇Mačka Schrödinger bez kutije: problem konsenzusa u distribuiranim sustavima

Zamislite sljedeće. U prostoriji su zaključana 5 mačaka, i kako bi otišle probuditi vlasnika, moraju se zajedno dogovoriti o tome, jer mogu otvoriti vrata samo zajedno, naslonivši se na njih. Ako je jedna od mačaka mačka Schrödinger, a ostale mačke ne znaju za njezinu odluku, postavlja se pitanje: "Kako to mogu učiniti?"

U ovom članku ću vam jednostavnim jezikom objasniti teorijsku komponentu svijeta distribuiranih sustava i principe njihovog rada. Također ću površno razmotriti glavnu ideju koja leži u osnovi Paxosa.

Kada programeri koriste oblačne infrastrukture, različite baze podataka i rade u klasterima s velikim brojem čvorova, uvjereni su da će podaci biti cjeloviti, očuvani i uvijek dostupni. No, odakle dolaze jamstva?

U suštini, jamstva koja imamo su jamstva davatelja usluga. Oni su opisana u dokumentaciji otprilike ovako: „Ova usluga je dovoljno pouzdana, ima zadani SLA, ne brinite, sve će raditi distribuirano, kao što očekujete.“

Skloni smo vjerovati u najbolje, jer nas pametni muški iz velikih kompanija uvjeravaju da će sve biti u redu. Ne postavljamo si pitanje: zašto bi ovo uopće moglo raditi? Ima li nekog formalnog opravdanja ispravnosti rada takvih sustava?

Nedavno sam išao na školu o distribuiranim računalnim sustavima i bio sam jako inspiriran ovom temom. Predavanja u školi više su podsjećala na satove iz matematičke analize nego na nešto vezano uz računalne sustave. No, upravo su tako u svoje vrijeme dokazivani najvažniji algoritmi koje svakodnevno koristimo, a da toga nismo ni svjesni.

U većini modernih distribuiranih sustava koristi se algoritam konsenzusa Paxos i njegove razne modifikacije. Najbolje je što se opravdanost i, u principu, sama mogućnost postojanja ovog algoritma može dokazati jednostavno uz pomoć olovke i papira. Pri tom se algoritam praktično primjenjuje u velikim sustavima koji rade na ogromnom broju čvorova u oblacima.

Lagana ilustracija o čemu će se dalje raditi: zadatak dvaju generalaHajde da se malo razgibamo analizom zadatka dvaju generala.

Imamo dvije vojske – crvenu i bijelu. Bijele trupe su smještene u opsjednutom gradu. Crvene trupe pod vodstvom generala A1 i A2 nalaze se s obje strane grada. Zadatak crvenih je napasti bijeli grad i pobijediti. Međutim, vojska svakog crvenog generala pojedinačno je manja od vojske bijelih.

Uvjeti pobjede za crvene: obojica generala moraju napasti istovremeno kako bi imali brojčanu prednost nad bijelima. Za to se generali A1 i A2 trebaju dogovoriti međusobno. Ako svaki napadne pojedinačno, crveni će izgubiti.

Da bi se dogovorili, generali A1 i A2 mogu slati glasnike jedni drugima kroz teritorij bijelog grada. Glasnik može uspješno doći do saveznika ili ga može uhvatiti protivnik. Pitanje je: postoji li takva sekvenca komunikacija između crvenih generala (sekvenca slanja glasnika od A1 do A2 i obrnuto od A2 do A1), u kojoj će se oni jamčivo dogovoriti o napadu u čas X. Ovdje, pod jamstvima podrazumijevamo da će obojica generala imati jednoznačnu potvrdu da saveznik (drugi general) sigurno napada u dogovoreno vrijeme X.

Pretpostavimo da A1 šalje glasnika A2 s porukom: „Napadnimo danas u ponoć!“. General A1 ne može napasti bez potvrde od generala A2. Ako je glasnik od A1 stigao, tada general A2 šalje potvrdu s porukom: „Da, napadnimo danas bijele“. No sada general A2 ne zna je li njegov glasnik stigao ili ne, nema jamstava da će napad biti simultan. Sada generalu A2 opet treba potvrda.

Ako se nastavi s njihovom komunikacijom, otkriva se sljedeće: koliko god ciklusa razmjene poruka bilo, ne postoji način da se jamčito obavijeste obojica generala o tome da su njihove poruke primljene (pod uvjetom da bilo koji glasnik može biti uhvaćen).

Zadatak dva generala odlična je ilustracija vrlo jednostavnog distribuiranog sustava, gdje postoje dva čvora s nepouzdanom komunikacijom. To znači da nemamo 100% jamstvo da će se sinkronizirati. O sličnim problemima, ali na većem razmjeru, bit će riječi dalje u članku.

Uvodimo pojam distribuiranih sustava.

Distribuirani sustav je skup računala (dalje ćemo ih zvati čvorovima) koji mogu razmjenjivati poruke. Svaki pojedini čvor je autonomna entitet. Čvor može samostalno obrađivati zadatke, ali da bi komunicirao s drugim čvorovima, mora slati i primati poruke.

Kako su poruke konkretno implementirane, koje se protokoli koriste – to nas ne zanima u ovom kontekstu. Važno je da čvorovi distribuiranog sustava mogu razmjenjivati podatke međusobno slanjem poruka.

Samo definicija izgleda prilično jednostavno, ali treba uzeti u obzir da distribuirani sustav ima brojne atribute koji će nam biti važni.

Atributi distribuiranih sustava

Konkurentnost je mogućnost nastanka istovremenih ili konkurentnih događaja u sustavu. Štoviše, smatrat ćemo da su događaji koji su se dogodili na dva različita čvora potencijalno konkurentni sve dok nemamo jasan redoslijed nastanka tih događaja. A, obično, nemamo.
Nedostatak globalnog vremena. Nemamo jasan redoslijed događaja zbog nedostatka globalnog vremena. U običnom ljudskom svijetu navikli smo da imamo satove i apsolutno vrijeme. Sve se mijenja kada se radi o distribuiranim sustavima. Čak i najtočniji atomski satovi imaju pomake, a moguća su i stanja kada ne možemo reći koji od dva događaja se dogodio ranije. Stoga se ne možemo oslanjati na vrijeme.
Neovisno otkazivanje čvorova sustava. Postoji još jedan problem: nešto može poći po zlu jednostavno zato što naši čvorovi nisu vječni. Može otkazati tvrdi disk, virtualka u oblaku se može ponovno pokrenuti, mreža može zatreptati i poruke se mogu izgubiti. Štoviše, moguća su i stanja kada čvorovi rade, ali istovremeno djeluju protiv sustava. Posljednja klasa problema čak je dobila posebno ime: problem bizantskih generala. Najpopularniji primjer distribuiranog sustava s ovakvim problemom je Blockchain. No, danas nećemo razmatrati ovu posebnu klasu problema. Zanimat će nas situacije u kojima jednostavno jedan ili više čvorova mogu otkazati.
Modeli komunikacije (modeli razmjene poruka) između čvorova. Utvrdili smo da čvorovi komuniciraju putem razmjene poruka. Postoje dva poznata modela razmjene poruka: sinkroni i asinkroni.

Modeli komunikacije između čvorova u distribuiranim sustavima

Sinkroni model – znamo točno da postoji konačna poznata delta vremena u kojoj poruka garancirano dolazi s jednog čvora na drugi. Ako to vrijeme istekne, a poruka nije stigla, možemo sigurno reći da je čvor otkazao. U takvom modelu imamo predvidivo vrijeme č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 otkazao. Tj. vrijeme čekanja poruke od čvora može biti proizvoljno dugo. Ovo je važno definiranje, i o tome ćemo dalje razgovarati.

Pojam konzensa u distribuiranim sustavima

Prije formalne definicije pojma konzensa, razmotrimo primjer situacije u kojoj nam je potreban, a to je – Replikacija strojne države.

Imamo neki distribuirani zapis. Željeli bismo da bude dosljedan i da sadrži identične podatke na svim čvorovima distribuiranog sustava. Kada neki od čvorova sazna novu vrijednost koju želi zabilježiti u zapis, njegov zadatak postaje predložiti tu vrijednost svim ostalim čvorovima kako bi se zapis ažurirao na svim čvorovima i sustav prešao u novo dosljedno stanje. Pritom je važno da se čvorovi dogovore: svi čvorovi su se složili da je predložena nova vrijednost ispravna, svi čvorovi su prihvatili tu vrijednost, i samo u tom slučaju svi mogu zabilježiti novu vrijednost u zapis.

Drugim riječima: nitko od čvorova nije prigovorio da ima ažurirane informacije, a predložena vrijednost je netočna. Dogovor između čvorova i suglasnost o jedinstvenoj ispravnoj prihvaćenoj vrijednosti jest konsenzus u distribuiranom sustavu. Dalje ćemo govoriti o algoritmima koji omogućuju da distribuirani sustav garantirano postigne konsenzus.

Možemo formalno definirati algoritam postizanja konsenzusa (ili jednostavno algoritam konsenzusa) kao funkciju koja prenosi distribuirani sustav iz stanja A u stanje B. Ovo stanje trebaju prihvatiti svi čvorovi, a svi čvorovi ga moraju potvrditi. Kako pokazuje iskustvo, ovaj zadatak nije nimalo trivijalan kao što se na prvi pogled čini.

Svojstva algoritma konsenzusa

Algoritam konsenzusa mora imati tri svojstva kako bi sustav mogao postojati i napredovati u prijelazu iz jednog stanja u drugo:

Sporazum – svi ispravno funkcionirajući čvorovi moraju prihvatiti istu vrijednost (u literaturi, ovo svojstvo se također naziva svojstvo sigurnosti). Svi čvorovi koji trenutno rade (nisu u kvaru i nisu izgubili vezu s ostalima) trebaju postići sporazum i prihvatiti neku konačnu zajedničku vrijednost.
Ovdje je važno razumjeti da čvorovi u ovom distribuiranom sustavu žele postići dogovor. Drugim riječima, govorimo o sustavima u kojima može doći do kvara (na primjer, neki čvor može otkazati), ali u ovom sustavu nema čvorova koji namjerno djeluju protiv drugih (zadatak bizantijskih generala). Zbog ovog svojstva sustav ostaje konzistentan.
Integritet – ako svi ispravno funkcionirajući čvorovi nude istu vrijednost v, svaki ispravno funkcionirajući čvor mora prihvatiti tu vrijednost v.
Završetak – svi ispravno funkcionirajući čvorovi na kraju će prihvatiti neku vrijednost (svojstvo aktivnosti), što omogućuje algoritmu napredovanje u sustavu. Svaki pojedinačni ispravno funkcionirajući čvor mora prije ili kasnije prihvatiti konačnu vrijednost i potvrditi to: „Za mene, ova vrijednost je istinita, slažem se s cijelim sustavom.“

Primjer rada algoritma konsenzusa

Dok svojstva algoritma možda nisu potpuno jasna, ilustrirajmo na primjeru koje faze prolazi najjednostavniji algoritam konsenzusa u sustavu s sinkronim modelom razmjene poruka, gdje svi čvorovi rade ispravno, poruke se ne gube i ništa se ne kvari (stvarno li se to događa?).

Sve počinje s prijedlogom ruke i srca (Propose). Pretpostavimo da se klijent povezao na čvor nazvan "Čvor 1" i započeo transakciju, šaljuci čvoru novu vrijednost – O. Od ovog trenutka "Čvor 1" nazivamo proposer. Kao proposer, "Čvor 1" sada mora obavijestiti cijeli sustav da ima nove podatke i šalje poruke svim ostalim čvorovima: "Gledajte! Primio sam vrijednost 'O', i želim je zapisati! Molim vas, potvrdite da ćete i vi zapisati 'O' u svoj log."
Sljedeća faza je glasovanje za predloženu vrijednost (Voting). Zašto je to potrebno? Može se dogoditi da su drugim čvorovima došle novije informacije i da imaju podatke o istoj transakciji.

Kada čvor "Čvor 1" pošalje svoj prijedlog, ostali čvorovi provjeravaju u svojim logovima podatke o ovom događaju. Ako nema proturječnosti, čvorovi objavljuju: "Da, nemam drugih podataka o ovom događaju. Vrijednost 'O' je najnovija informacija koju smo dobili."
U svakom drugom slučaju, čvorovi mogu odgovoriti "Čvoru 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 jednu vrijednost, ili netko od njih glasa protiv, označavajući da ima novije podatke.
Ako je krug glasovanja prošao uspješno, i svi su bili 'za', sustav prelazi u novu fazu - prihvaćanje vrijednosti (Accept). "Čvor 1" prikuplja sve odgovore drugih čvorova i javlja: "Svi su se složili s vrijednošću 'O'! Sada službeno izjavljujem da je 'O' naša nova vrijednost, jedinstvena za sve! Zapisujte u svoju knjižicu, ne zaboravite. Zapisujte u svoj log!"
Ostali čvorovi šalju potvrdu (Accepted) da su zapisali vrijednost 'O', ništa novo tijekom tog vremena nije pristiglo (svojstveni dvofazni commit). Nakon ovog značajnog događaja, smatramo da je distribuirana transakcija izvršena.

Tako algoritam konsenzusa u jednostavnom slučaju sastoji se od četiri koraka: propose, glasovanje (voting), prihvaćanje (accept), potvrda prihvaćanja (accepted).

Ako na nekom koraku nismo uspjeli postići saglasnost, algoritam se pokreće ispočetka, uzimajući u obzir informacije koje će pružiti čvorovi koji su odbili potvrditi predloženu vrijednost.

Konsenzus algoritam u asinkronom sustavu

Do sada je sve bilo jednostavno, jer se radilo o sinkronom modelu razmjene poruka. No, mi znamo da smo u modernom svijetu navikli raditi asinkrono. Kako onda sličan algoritam funkcionira u sustavu s asinkronim modelom razmjene poruka, gdje smatramo da vrijeme čekanja na odgovor od čvora može biti proizvoljno dugo (usput, kvar čvora također možemo smatrati primjerom kada čvor može odgovarati koliko god dugo želi).

Sada kada znamo kako algoritam konsenzusa u osnovi funkcionira, pitanje za znatiželjne čitatelje koji su stigli do ovog mjesta: koliko čvorova u sustavu od N čvorova s asinkronim modelom poruka može otkazati da bi sustav i dalje mogao postići konsenzus?

Točan odgovor i objašnjenje su ispod.Točan odgovor: 0. Ako barem jedan čvor u asinkronom sustavu otkaže, sustav ne može postići konsenzus. Ova tvrdnja je dokazana u poznatoj teoremi FLP (1985, Fischer, Lynch, Paterson, izvor u završnom dijelu članka): „Nemogućnost postizanja distribuiranog konsenzusa pri otkazu barem jednog čvora“.

Dakle, imamo problem, navikli smo da je sve asinkrono. A sada ovo. Kako dalje živjeti?

Sada smo govorili o teoriji, o matematici. Što znači „konsenzus se ne može postići“, prevođenjem s matematičkog jezika na naš – inženjerski? To znači da „ne može uvijek biti postignut“, tj. postoji slučaj u kojem konsenzus nije moguće postići. A koji je to slučaj?

To je zapravo kršenje svojstva živosti, opisano iznad. Nemamo zajednički dogovor, i sustav ne može napredovati (ne može završiti u konačnom vremenu) u slučaju kada nemamo odgovor od svih čvorova. Jer u asinkronom sustavu nemamo predvidivo vrijeme odgovora, i ne možemo znati je li čvor otkazao ili samo dugo odgovara.

No, u praksi možemo pronaći rešenje. Neka naš algoritam može raditi dugo u slučaju otkaza (potencijalno može raditi beskonačno). No, u većini situacija, kada većina čvorova ispravno funkcionira, imat ćemo napredak u sustavu.

U praksi se susrećemo s djelomično sinkronim komunikacijskim modelima. Djelomična sinkronost se shvaća ovako: općenito imamo asinkroni model, ali se formalno uvodi koncept „global stabilization time“ nekog vremenskog trenutka.

Ovaj vremenski trenutak može se ne ostvarivati beskrajno dugo, ali jednom mora doći. Aktivirat će se virtualni alarm, i od tog trenutka možemo predvidjeti delta vremena potrebno da poruke stignu. Od tog trenutka sustav se iz asinkronog pretvara u sinkroni. U praksi se radi upravo o takvim sustavima.

Paxos algoritam rješava probleme konsenzusa

Paxos – to je skup algoritama koji rješavaju problem konsenzusa za djelomično sinkrone sustave, pod uvjetom da neki čvorovi mogu otkazati. Autor Paxosa je Leslie Lamport. On je 1989. godine predložio formalni dokaz o postojanju i točnosti algoritma.

No, dokaz se pokazao daleko od trivijalnog. Prva publikacija objavljena je tek 1998. godine (33 stranice) s opisom algoritma. Kako se ispostavilo, bila je izuzetno teška za razumijevanje, a 2001. godine objavljeno je objašnjenje članka koje je zauzelo 14 stranica. Obujam publikacija naveden je kako bi se pokazalo da je problem konsenzusa zapravo vrlo složen i da iza takvih algoritama stoji ogroman trud najpametnijih ljudi.

Zanimljivo je da je sam Leslie Lamport u svom predavanju primijetio da u drugom članku-objašnjenju postoji jedno tvrdnja, jedna rečenica (nije precizirao koja), koja se može različito tumačiti. Zbog toga veliki broj modernih implementacija Paxosa ne radi potpuno ispravno.

Detaljna analiza rada Paxosa zauzet će više od jednog članka, pa ću se potruditi vrlo sažeto prenijeti osnovnu ideju algoritma. U linkovima na kraju mog članka naći ćete materijale za daljnje istraživanje ove teme.

Uloge u Paxosu

U algoritmu Paxos postoji pojam uloga. Razmotrit ćemo tri osnovne (postoje modifikacije s dodatnim ulogama):

Proposers (također se mogu susresti termini: vođe ili koordinatori). To su momci koji saznaju o nekom novom predlogu od korisnika i preuzimaju ulogu lidera. Njihov zadatak je da pokrenu krug predlaganja novog vrednovanja i koordiniraju daljnje akcije čvorova. Osim toga, Paxos dopušta postojanje više lidera u određenim situacijama.
Priznavaoci (Glasači). To su čvorovi koji glasaju za usvajanje ili odbijanje određenog vrednovanja. Njihova uloga je veoma važna, jer upravo od njih zavisi odluka: u koje stanje će preći (ili neće preći) sistem nakon sledeće faze algoritma konsenzusa.
Učitelji. Čvorovi koji jednostavno prihvataju i beleže novo usvojeno vrednovanje kada se stanje sistema promeni. Oni ne donose odluke, samo primaju podatke i mogu ih predati krajnjem korisniku.

Jedan čvor može obavljati više uloga u različitim situacijama.

Pojam kvoruma

Pretpostavljamo da imamo sistem od N čvorova. I od njih najviše F čvorova može otkazati rad. Ako F čvorova otkaže rad, to znači da u klasteru mora biti najmanje 2F + 1 čvorova priznavatelja.

To je neophodno za to da uvek, čak i u najgorem scenariju, imamo većinu „dobrih“, ispravno funkcionišućih čvorova. To jest, F + 1 „dobrih“ čvorova koji su se složili, i konačna vrednost će biti prihvaćena. U suprotnom, može doći do situacije u kojoj različite lokalne grupe prihvate različite vrednosti i ne mogu se dogovoriti. Stoga nam je potrebno apsolutna većina da pobedimo u glasovanju.

Opšta ideja rada algoritma konsenzusa Paxos

Algoritam Paxos podrazumeva dve velike faze, koje se dalje dele na dva koraka svaka:

Faza 1a: Priprema. U fazi pripreme vođa (proposer) obavještava sve čvorove: «Započinjemo novu fazu glasovanja. Imamo novi krug. Broj ovog kruga – n. Sada ćemo početi glasovati». Dok samo obavještava o početku novog ciklusa, ne objavljuje novu vrijednost. Zadatak ove faze je pokrenuti novi krug i obavijestiti sve o njegovom jedinstvenom broju. Broj kruga je važan, to mora biti vrijednost veća od svih prethodnih brojeva glasovanja od svih prethodnih lidera. Zato što upravo zahvaljujući broju kruga drugi čvorovi u sustavu će shvatiti koliko su svježi podaci kod vođe. Vjerojatno već drugi čvorovi imaju rezultate glasovanja iz mnogo kasnijih krugova i samo će obavijestiti vođu da je zapeo.
Faza 1b: Obećanje. Kada su čvorovi-acceptor primili broj nove faze glasovanja, moguća su dva ishoda:
- Broj n novog glasovanja je veći od broja bilo kojeg od prethodnih glasovanja u kojem je sudjelovao acceptor. Tada acceptor šalje vođi obećanje da se više neće sudjelovati u bilo kojem glasovanju s manjim brojem od n. Ako je acceptor već glasovao za neku vrijednost (tj. već je u drugoj fazi prihvatio neku vrijednost), tada uz svoje obećanje prilaže prihvaćenu vrijednost i broj glasovanja u kojem je sudjelovao.
- U suprotnom, ako acceptor već zna za glasovanje s većim brojem, može jednostavno ignorirati fazu pripreme i ne odgovarati vođi.
Faza 2a: Prihvati. Vođa treba čekati odgovor od kvoruma (većine čvorova u sustavu) i, ako dobije potreban broj odgovora, ima dva moguća scenarija:
- Neki od acceptor-a su poslali vrijednosti za koje su već glasovali. U tom slučaju vođa odabire vrijednost iz glasovanja s maksimalnim brojem. Nazovimo tu vrijednost x i šalje svim čvorovima poruku u obliku: «Prihvati (n, x)», gdje je prva vrijednost broj glasovanja iz vlastitog koraka Propose, a druga vrijednost je ona zbog koje su se svi okupili, tj. vrijednost za koju zapravo glasujemo.
- Ako nijedan od acceptora nije poslao nikakve vrijednosti, već su samo obećali glasati u ovom krugu, lider može predložiti da glasaju za svoju vrijednost, onu za koju je uopće postao lider. Nazovimo je y. Šalje svim čvorovima poruku oblika: „Accept (n, y)“, analogno prethodnom ishodu.
Faza 2b: Prihvaćeno. Nadalje, čvorovi-acceptori, prilikom primanja poruke „Accept(…)“ od lidera, pristaju s njim (šalju svim čvorovima potvrdu da se slažu s novom vrijednošću) samo ako nisu obećali nekom (drugom) lideru sudjelovati u glasovanjima s brojem runde n’ > n, u suprotnom ignoriraju zahtjev za potvrdom.
Ako je lideru odgovorilo većina čvorova, i svi su potvrdili novu vrijednost, nova vrijednost se smatra prihvaćenom. Hura! Ako većina nije dostignuta ili postoje čvorovi koji su odbili prihvatiti novu vrijednost, sve počinje iznova.

Eto kako radi algoritam Paxos. Svaka od ovih faza ima mnogo suptilnosti, gotovo nismo razmatrali razne tipove grešaka, probleme višestrukih lidera i još mnogo toga, ali svrha ovog članka je samo upoznati čitatelja s svijetom distribuiranih računala na visokom nivou.

Također vrijedi napomenuti da Paxos nije jedini svog tipa, postoje i drugi algoritmi, na primjer, Raft, ali to je tema za drugi članak.