Konzistentnost Flashcards
Garancije Konzistentnosti
Konzistentnost u distribuiranim sistemima se obično odnosi na činjenicu da ukoliko pogledamo isti podatak na dva čvora, možemo videti dva različita podatka
Većina nerelacionih baza daje garanciju eventualne konzistentnosti
Postoje i viši nivoi garancija od eventualne konzistentnosti
Možemo primetiti sličnosti sa garancijama na nivou transakcija, gde koristimo izolacione nivoe
Linearizabilnost
(Atomična konzistentnost)
Osnovna ideja iza garancije linearizabilnosti :
1.Da se sistem ponaša kao da postoji samo jedna kopija podataka, i da su sve operacije atomične.
2.Kada jedan korisnik završi write operaciju, tu write operaciju mogu svi ostali klijenti videti.
Međutim ove pravilnosti ne zadovoljavaju ono što bi mi smatrali linearizabilnost, potrebno je da tačno identifikujemo momenat flipovanja 0 u 1, kako bi deklarisali da posle ove tačke svaki read će vratiti istu vrednost
Da bi smo dobili nešto što više liči na linearizabilnost, možemo celu operaciju svesti na jednu tačku u vremenu kada je operacija “odrađena” na serveru
Postoji određena problematika…
Ukoliko imamo dva konkuretna read-a nad write-om, prvi read diktira šta je “ažurno”, drugi read ne sme vratiti stariju vrednost od prvog read-a
Dakle moguće je utvrditi da li ponašanje sistema linearizabilno tako što detektujemo timestampove svih request-ova i response-ova, i proverimo da li su orderovani pravilnim redosledom
Serijazibilnost
Ponašanje tranaskcije pri izolaciji, gde svaka transakcija može čitati ili pisati više objekata. Garantuje da će se transakcije ponašati kao da su se izvršile u NEKOM serijskom redosledu
Okej je da transakcije budu pokrenute u redosledu koji nije striktno redosled po vremenu pokretanja transakcije
Linearizabilnost
Garancija skorosti nad read i write operacijama jednog objekta. Ne grupiše operacije u transakcije, dakle write skew je sasvim moguć.
striktna serijazibilnost
Baza podataka može nuditi i linearizabilnost i serijazibilnost, kada se ova dva nude u paketu to se zove striktna serijazibilnost
Impelementacije serijazibilnosti bazirane na two phase lockingu ili izvršavanju na jednom thread-u su zapravo i linearizabilne.
Međutim Serializable Snapshot Izolacija ipak nije, jer čitamo sa snapshot-a
Cena Linearizabilnosti
Glavna osobina koju smo primetili je da ukoliko klijent ima samo pristup zastarelim replikama, da je linearizabilnost nemoguća
Ukoliko su neke replike izolovane od ostatka mreže zbog pada mreže, onda ne smeju procesuirati ni read ni write requestove dok se ne vrate u sistem, u međuvremenu moraju vraćati error
Ukoliko naša aplikacija ne zahteva linearizavilnost onda:
Svaka replika sme primati zahteve nezavisno od ostatka sistema, čak iako je izolovana od njega (npr. Multileader). Na ovaj način aplikacija ostaje dostupna (available) pri padovima mreže, ali NIJE linearizabiln
Ova pravilnost je osnov CAP teoreme
CAP teorema
CAP teorema predstavlja tri promenjive između kojih treba balansirati
Konzistentnost (Linearizabilnost)
Dostupnost (Availability)
Tolerancija na padove (Partition tolerance)
Česta je praksa da se teorema predstavi kao…
Postoje tri promenjive, morate odabrati dve, ne postoji sistem koji zadovoljava sve tri
Ovo je apsolutno netačno, Padovi mreže su svakodnevica, i ne postoji naš izbor u tome da li će se desiti
Nedostatci ove pretpostavke:
AP teorema uzima u obzir samo padove mreže, međutim postoji mnogo više ozbiljnijih problema koji mogu ugroziti availability i konzistentnost mreže
Network lag
Mrtvi node-ovi
Garancije Redosleda
Linearizabilnost implicira da se operacije dešavaju u dobro poznatom redosledu.
Redosled operacija je bitan jer bez njega nije moguće utvrditi kauzalnost radnji
Ukoliko sistem poštuje pravila kauzalnosti, onda kažemo da je kauzalno konzistentan.
Totalni redosled i kauzalni redosled
Totalni redosled ukazuje da svi elementi mogu biti međusobno poređeni (Da znamo koji je manji a koji veći)
Linearizabilnost
Postoji totalni order operacija, za svake dve operacije možemo reći kada se koja desila
Kauzalnost
Sa kauzalnoscu imamo problem što ne možemo sve da poredimo sa svačim.
Kauzalnost nam daje parcijalni redosled operacija, neke operacije su uređene da se dese jedna nakon druge, dok druge nisu
Linearizabilnost i Kauzalnost
Linearizabilnost sa sobom povlači da postoji kauzalnost
Međutim Linearizabilnost nije jedini način na koji se kauzalnost može postići
Kauzalnost predstavlja najači model konzistentnosti koji može biti implementiran bez uticaja na performanse sistema, i ostati dostupan pri padovima mreže
Cilj je da u skorijoj budućnosti imamo baze podataka koje obezbedjuju kauzalnost, ali imaju perforamnse sistema koji trenutno rade u eventualno konzistentnom režimu!
Kauzalnost
Da bi smo uopšte imali kauzalnost moramo prvo utvirditi koje operacije se moraju izvršiti pre drugih
Međutim kako da znamo koje su to operacije kauzalno povezane
Glavni problem sa ovakvom detekcijom kauzalnosti je što je moramo pratiti nad celom bazom podataka, a ne nad ključevima kako smo to do sada radili.
Za ovo su version vektori satovi idealno rešenje
Dakle baza podataka mora da ima informaciju o tome koju verziju podatka je aplikacija pročitala, pre same operacije
Ukoliko imamo transakcije, potrebno je da znamo koje podatke je neka transakcija pročitala
Nekauzalni timestamp-ovi
Kada imamo više leader-a ili leaderless replikaciju, generisanja timestampova nije toliko prosto, ima više potencijalnih rešenja
Međutim ovi time stampovi nemaju kauzalnu konzistentnost između različitih node-ova
Drugo potencijalno rešenje je da koristimo Lamport Timestamp
—Svaki klijent i node čuva dve informacije, id node-a i svoj lični inkrementator
Imamo totalni order, sve dok se counter prenosi sa operacije na operaciju
Lamport Timestamp nije isto kao i Vektorski sat!
Nedostatak Timestapova
Timestampovi sami po sebi ne mogu da nam obezbede dovoljni uslov za kauzalnost
Recimo da imamo sistem gde samo jedan korisnik može da napravi nalog pod nekim username-om
U slučaju da se dva slučaja sa istim counterom pojave, uzmi onaj sa većim id-em noda
Međutim, kako da budemo uopšte i svesni da neko drugi uopšte i pokušava da odradi istu operaciju…
Rešenje je da pitamo sve ostale node-ove šta tačno sada rade, i da na osnovu međusobnog dogovora napravi total order operacija
Total Order Broadcast
/ Atomic Broadcast
Ukoliko naš program radi sa jednim masteru, onda je totalni order jednostavno redosled u kome je master odradio operacije
Međutim kako natarati sistem bez mastera da se složi oko redosleda
Posmatramo slanje poruka kao “Log”
Dostavljanje poruke dodaje u log
Pošto svaka poruka mora da bude prosledjena u istom redosledu, svaki node može pročitati svoj log i videti sve dostavljene poruke
Ovaj “Log” možemo koristiti i za potrebe lockovanja, gde faktički imamo konzistentni red čekanja za neki resurs
U Zookeeper-u se ovo zove zxid
