Beskonfliktni kopirajući tip podataka

U distribuiranom računarstvu, nekonfliktno kopirajući tip podataka je vrsta specijalno dizajniranih struktura podataka koje se koriste za postizanje jake eventualne konzistencije (strong eventual consistency - SEC) i monotonije. Postoje dva alternativna načina obezbeđivanja SEC-a: rad zasnovan na CRDT-ovima i stanje zasnovano na CRDT-u. Ove dve alternative su ekvivalentne, tako što jedan može simulirati drugi, ali radno-zasnovan CRDT zahteva dodatne garancije od posredničke komunikacije.

CRDT-ovi se koriste da umnože podatke na više računara u mreži, izvrše ažuriranja bez potrebe za daljinskom sinhronizacijom. To dovodi do spajanja sukoba u sistemima koji koriste SEC tehnologiju, ali CRDT-ovi su dizajnirani tako da su sukobi matematički nemogući. Prema ograničenjima CAP teoreme koja pruža najjaču konzistentnost garancije za partitivno raspoloživa podešavanja. Nasuprot tome, konsenzus protokoli kao što je Paxos su potrebni za partitivno konzistentna podešavanja.

Koncept CRDT je prvi put formalno definisan 2007. godine od strane Marc Shapiro i Nuno Preguiça. Razvoj je prvobitno motivisan uređivanjem teksta. Koncept evolucije repliciranja stanja definisan je od strane Baquero i Moura 1997. i prvobitno je motivisan mobilnim računarstvom. Ova dva koncepta su spojena 2011.

Pregled

Eventualna konzistentnost

Neformalno, eventualna konzistentnost znači da replike na kraju dostižu istu vrednost, ako klijenti zaustave podnošenje ispravke. Eventualno konzistentni sistemi prihvataju lokalne ispravke bez daljinske sinhronizacije, poboljšavajući performanse i skalabilnost preko jake konzistencije. Bez daljinske sinhronizacije, replike istovremeno imaju različite vrednosti za koje se očekuje da se približe tokom vremena. Približavanje je zakomplikovano sukobima koji se javljaju spajanjem vrednosti između replika. Sukob je kombinacija istovremenih ažuriranja koja mogu biti pojedinačno tačna, ali zajedno ugrožavaju invarijantu sistema.

Jaka eventualna konzistentnost

Jaka eventualna konzistentnost je svojina nekih eventualno kozistentnih sistema: replike na koje su primenjena ista ažuriranja imaju ekvivalentna stanja. Ne postoji konflikt arbitraže procesa, jer konflikti ne postoje u jako konzistentnim sistemima. CRDT se koristi za postizanje jake eventualne konzistencije u distribuiranom sistemu.

Мatematička svojstva

Ako stanje sistema monotono raste, klijenti nikada ne posmatraju povratnu vrednost. Skup sistemskih stanja je delimično naređen, i operacija spajanja može biti komutativna, asocijativna i idempotentna.

CRDT klase

Poznato je da postoje dve klase CRDT-ova. Iako bilo koji CRDT jedne klase ima ekvivalenta druge klase, klase se razlikuju u pretpostavkama i karakteristikama performansi.

Radno zasnovan CRDT

Radno zasnovan CRDT je skraćenica za komutativne replicirane vrste podataka, ili CmRDT. CmRDT replike propagiraju stanje emitovanjem stanja ažuriranja same operacije, koja mora biti komutativna. Na primer, CmRDT od jednog integer-a može da emituje operacije (+10) ili (-20). Replike primaju ažuriranja i primenjuju ih na lokalnom nivou. Operacije su komutativne, tako da mogu biti primljene i primenjene bilo kojim redom, međutim, one nisu idempotentne, a dodatne garancije mrežnog protokola su dužne da obezbede jedinstvenu isporuku.

CRDT zasnovan na stanju

CRDT zasnovan na stanju je konvergentni replicirani tip podataka, ili CvRDT. Za razliku od CmRDT, CvRDT šalje svoje celokupno lokalno stanje drugim replikama. CvRDT ima sledeći lokalni interfejs:

• Upit - čita stanje replika bez neželjenih efekata
• Ažuriranje - upisuje na stanje replike u skladu sa određenim ograničenjima
• Spajanje - spaja lokalno stanje sa stanjem neke replike

Funkcija spajanja mora biti komutativna, asocijativna i idempotentna. Ona obezbeđuje spajanje stanja nekog para replika, tako da skup svih stanja formira polurešetku. Unutrašnje stanje funkcije ažuriranja mora monotono da raste.

Poređenje

Dok CmRDT zahteva dodatne garancije od protokola mreže, koristi manji propusni opseg nego CvRDT kada je broj transakcija mali u odnosu na veličinu unutrašnjeg stanja. Međutim, pošto je funkcija spajanja CvRDT asocijativna, spajanjem sa stanjem neke replike daje sva prethodna ažuriranja za tu repliku. "Gossip" protokoli dobro rade za propagiranje CvRDT stanja sa drugim replikama dok smanjuju upotrebu mreže i manipulišu topologijom promena.

Poznati CRDT-ovi

Inkrementirajući brojač zasnovan na stanju

   payload integer[n] P
     initial [0,0,...,0]
   update increment()
     let g = myId()
     P[g] := P[g] + 1
   query value() : integer v
     let v = \sum\nolimits_{i} P[i]
   compare (X, Y) : boolean b
     let b = (\forall i \in [0, n - 1] : X.P[i] \leq Y.P[i])
   merge (X, Y) : payload Z
     let \forall i \in [0, n - 1] : Z.P[i] = max(X.P[i], Y.P[i])

Ovaj CvRDT implementira brojač za skup od n čvorova. Svakom čvoru u tom skupu je pridružen ID od 0 do n-1, koji je dobijen pozivom funkcije myId(). Tako je svakom čvoru dodeljen indeks u nizu P, koji se lokalno inkrementira. Ažuriranja se izvršavaju u pozadini, i spajana korišćenjem funkcije max() svakog elementa iz P. Funkcija poređenja je komutativna, asocijativna i idempotentna. Unutrašnje stanje funkcije ažuriranja monotono raste u odnosu na funkciju poređenja. Na ovaj način CvRDT je ispavno definisan i obezbeđuje jaku eventualnu konzistentnost.

PN-brojač zasnovan na stanju

   payload integer[n] P, integer[n] N
     initial [0,0,...,0], [0,0,...,0]
   update increment()
     let g = myId()
     P[g] := P[g] + 1
   update decrement()
     let g = myId()
     N[g] := N[g] + 1
   query value() : integer v
     let v = \sum\nolimits_{i} P[i] - \sum\nolimits_{i} N[i]
   compare (X, Y) : boolean b
     let b = (\forall i \in [0, n - 1] : X.P[i] \leq Y.P[i] \and \forall i \in [0, n - 1] : X.N[i] \leq Y.N[i])
   merge (X, Y) : payload Z
     let \forall i \in [0, n - 1] : Z.P[i] = max(X.P[i], Y.P[i])
     let \forall i \in [0, n - 1] : Z.N[i] = max(X.N[i], Y.N[i])

Strategija u razvoju CRDT-a je da se pridruži više primitivnih CRDT-ova da bi se napravio složeniji CRDT. U ovom slučaju, dva inkrementirajuća brojača su kombinovana da naprave CvRDT podržavajući operacije inkrementiranja i dekrementiranja. Treba imati na umu da unutrašnje stanje CvRDT-a mora monotono da raste, iako je njegovo spoljašnje stanje izloženo upitu povratka prethodne vrednosti.

Rastuće postavke zasnovane na stanju

   payload set A
     initial \emptyset
   update add(element e)
     A := A \cup {e}
   query lookup(element e) : boolean b
     let b = (e \in A)
   compare (S, T) : boolean b
     let b = (S.A \subseteq T.A)
   merge (S, T) : payload U
     let U.A = S.A \cup T.A

Rastuće postavke su postavke koje omogućavaju samo dodavanje, koje implementira CvRDT. Sve dok je nemoguća komutacija dodavanja i uklanjanja (jedna mora imati prednost u odnosu na drugu), bilo koji CvRDT koji podržava operacije dodavanja i uklanjanja mora da izabere svoju semantiku.

2P postavke zasnovane na stanju

   payload set A, set R
     initial \emptyset, \emptyset
   query lookup(element e) : boolean b
     let b = (e \in A \and e \notin R)
   update add(element e)
     A := A \cup {e}
   update remove(element e)
     pre lookup(e)
     R := R \cup {e}
   compare (S, T) : boolean b
     let b = (S.A \subseteq T.A \or S.R \subseteq T.R)
   merge (S, T) : payload U
     let U.A = S.A \cup T.A
     let U.R = S.R \cup T.R

Dve rastuće postavke CvRDT-a se kombinuju i stvaraju 2P postavku CvRDT-a. Sa dodatkom postavke "tombstone", elementi mogu da se dodaju i uklanjaju. Jednom uklonjen, element ne može ponovo da se doda, tj. za taj element(e) istinitosna vrednost više nikada neće biti TRUE. 2P postavka koristi "remove-wins" semantiku, što znači da funkcija remove(e) ima prednost u odnosu na add(e).

Upotreba u industriji

Podrška za CRDT se sprovodi u kompaniji RIAK. League of Legends koristi RIAK CRDT implementaciju za svoj chat sistem unutar igre koji barata sa 7.5 miliona istovremenih korisnika i 11.000 poruka u sekundi.