A konfliktusmentes replikált adattípus (CRDT) az elosztott számítástechnikában egy olyan adatszerkezet, amely egy hálózat több számítógépén replikálódik, és a következők jellemzik:

az alkalmazás bármelyik replikát önállóan, egyidejűleg és a többi replikával való egyeztetés nélkül frissítheti; egy algoritmus (amely maga is az adattípus része) automatikusan feloldja az esetlegesen előforduló ellentmondásokat; bár a replikák állapota egy adott időpontban eltérő lehet, garantáltan egy közös állapothoz konvergálnak.

A CRDT koncepciót hivatalosan 2011-ben definiálta Marc Shapiro, Nuno Preguiça, Carlos Baquero és Marek Zawirski. A fejlesztést kezdetben a kollaboratív szövegszerkesztés és a mobil számítástechnika motiválta. CRDT-ket használnak az online chatrendszerekben, az online szerencsejátékokban és a SoundCloud hangterjesztő platformon is. A Redis, a Riak és a Cosmos DB NoSQL elosztott adatbázisok is rendelkeznek CRDT adattípusokkal.

Háttér Ugyanazon adatok több replikájának egyidejű frissítése a replikákat tároló számítógépek közötti koordináció nélkül a replikák közötti ellentmondásokat eredményezhetnek, amelyek általános esetben nem feltétlenül oldhatók fel. A frissítések közötti konfliktusok esetén a konzisztencia és az adatintegritás helyreállítása megkövetelheti a frissítések egy részének vagy egészének teljes vagy részleges visszavonását.

Ennek megfelelően az elosztott számítástechnika nagy része arra a problémára összpontosít, hogy hogyan lehet megakadályozni a replikált adatok egyidejű frissítését.

Egy másik lehetséges megközelítés azonban az optimista replikáció, ahol az összes egyidejű frissítést átengedik, esetleg ellentmondások keletkeznek, és az eredményeket később összevonják vagy „feloldják”. Ebben a megközelítésben a replikák közötti konzisztencia végül az eltérő replikák „összevonásával” áll helyre. Míg az optimista replikáció általános esetben nem feltétlenül működik, az adatszerkezeteknek van egy jelentős és gyakorlatban hasznos osztálya, a CRDT-k, ahol ez jól működik: mindig lehetséges az adatszerkezet különböző replikáinak egyidejű frissítéseit konfliktusok nélkül összevonni vagy feloldani. Ez ideálissá teszi a CRDT-ket az optimista replikációhoz.

Példaként egy egyirányú Boolean eseményjelző (event flag) egy triviális CRDT: egy bit, igaz vagy hamis értékkel. Az igaz azt jelenti, hogy egy adott esemény legalább egyszer bekövetkezett. A hamis azt jelenti, hogy az esemény nem következett be. Ha egyszer igazra állítottuk, a jelző nem állítható vissza hamisra (egy már bekövetkezett eseményt nem lehet meg nem történtté tenni). A feloldási módszer a „true wins” (az Igaz nyer): amikor egy olyan replikát egyesítünk, ahol a jelző igaz (az adott replika megfigyelte az eseményt), és egy másikat, ahol a jelző hamis (az adott replika nem figyelte meg az eseményt), a feloldás eredménye igaz: az eseményt megfigyeltük.

A CRDT-k típusai

A CRDT-knek két megközelítése van, mindkettő erős konzisztenciát biztosíthat: az állapotalapú CRDT-k és a műveletalapú CRDT-k.

Állapotalapú CRDT-k

Az állapotalapú CRDT-ket (más néven konvergens replikált adattípusok, vagy CvRDT-k) két eljárás határozza meg: a helyi állapotokhoz és egy az állapotokon végzett műveletekhez tartozik; valamint három függvénnyel (állapotváltozás): egy függvény egy kezdeti állapot előállítására, egy állapotok egyesítésére szolgáló függvény, és egy függvény egy állapot frissítésére szolgáló művelet alkalmazására. Az állapotalapú CRDT-k minden frissítéskor egyszerűen elküldik a teljes helyi állapotukat a többi replikának, ahol a kapott új állapotokat beolvasztják a helyi állapotba.

A végső konvergencia biztosítása érdekében a függvényeknek a következő tulajdonságoknak kell megfelelniük: Az egyesítési függvénynek ki kell számítania az egyesülést a replikák bármelyik állapotpárjára, és egy félrácsot kell alkotnia, amelynek semleges eleme a kezdeti állapot. Ez különösen azt jelenti, hogy az egyesítő függvénynek kommutatívnak, asszociatívnak és idempotensnek kell lennie. A kommutativitás, asszociativitás és idempotencia mögött az az intuíció áll, hogy ezek a tulajdonságok arra szolgálnak, hogy a CRDT változatlan legyen a csomagok átrendeződése és duplikációja esetén. Továbbá, a frissítési függvénynek monotonnak kell lennie az említett félrács által meghatározott részleges sorrend tekintetében.

A delta állapotú CRDT-k (vagy egyszerűen csak delta CRDT-k) olyan optimalizált állapotalapú CRDT-k, amelyekben a teljes állapot helyett csak a közelmúltban alkalmazott állapotváltozásokat terjesztik.

Műveletalapú CRDT-k

A műveletalapú CRDT-k (más néven kommutatív replikált adattípusok, vagy CmRDT-k) egyesítési függvény nélkül definiálhatók. Az állapotok továbbítása helyett a frissítési műveletek kerülnek közvetlenül a replikákhoz továbbításra és alkalmazásra. Például egy egyetlen egész szám művelet alapú CRDT-je a (+10) vagy (-20) műveleteket továbbíthatja. A műveletek alkalmazásának továbbra is kommutatívnak és asszociatívnak kell lennie. Ahelyett azonban, hogy megkövetelnénk, hogy a műveletek alkalmazása idempotens legyen, a kommunikációs infrastruktúrával szemben erősebbek az elvárások: minden műveletet duplikáció nélkül és keletkezési sorrendben kell eljuttatni a többi replikához.

A tisztán műveletalapú CRDT-k a műveletalapú CRDT-k egy olyan változata, amely csökkenti a metaadatok méretét.

Összehasonlítás

A két alternatíva elméletileg egyenértékű, mivel mindkettő képes emulálni a másikat. A gyakorlatban azonban vannak különbségek. Az állapotalapú CRDT-ket gyakran egyszerűbb megtervezni és megvalósítani; egyetlen követelményük a kommunikációs hordozóval szemben valamilyen pletyka protokoll. Hátrányuk, hogy minden CRDT teljes állapotát végül minden más replikának továbbítani kell, ami költséges lehet. Ezzel szemben a műveletalapú CRDT-k csak a frissítési műveleteket továbbítják, amelyek jellemzően kis méretűek. A művelet-alapú CRDT-k azonban garanciákat igényelnek a kommunikációs middleware-től; hogy a műveletek nem esnek ki vagy duplikálódnak a többi replikának való továbbításkor, és hogy azok ok-okozati sorrendben kerülnek átadásra.

Bár a műveletalapú CRDT-k több követelményt támasztanak a replikák közötti műveletek továbbításának protokolljával szemben, kevesebb sávszélességet használnak, mint az állapotalapú CRDT-k, ha a tranzakciók száma a belső állapot méretéhez képest kicsi. Mivel azonban az állapotalapú CRDT egyesítési függvény asszociatív, az egyesítés valamely replika állapotával az adott replika összes korábbi frissítésének eredményét adja. A pletyka protokollok jól működnek az állapotalapú CRDT állapot más replikák felé történő továbbítására, miközben csökkentik a hálózathasználatot és kezelik a topológiaváltozásokat.

Az állapotalapú CRDT-k tárolási komplexitására vonatkozóan ismert néhány alsó korlát.

Ismert CRDT-k

G-Számláló (G-Counter, Grow-only Counter) payload integer[n] P initial [0,0,...,0] update increment() let g = myId() P[g] := P[g] + 1 query value() : integer v let v = Σi P[i] compare (X, Y) : boolean b let b = (∀i ∈ [0, n - 1] : X.P[i] ≤ Y.P[i]) merge (X, Y) : payload Z let ∀i ∈ [0, n - 1] : Z.P[i] = max(X.P[i], Y.P[i])

Ez az állapotalapú CRDT egy n csomópontból álló csoport számlálóját valósítja meg. A csoport minden egyes csomópontjához egy 0 és n – 1 közötti azonosítót rendelünk, amelyet a myId() hívásával kapunk meg. Így minden csomópontnak saját slotja van a P tömbben, amely helyileg növekszik. A frissítések a háttérben terjednek, és a P minden elemének max() értékét figyelembe véve egyesülnek. A compare függvényt az állapotok részleges sorrendjének szemléltetésére használjuk. Az egyesítő függvény kommutatív, asszociatív és idempotens. A frissítő függvény monoton módon növeli a belső állapotot az összehasonlító függvénynek megfelelően. Ez tehát egy helyesen definiált állapotalapú CRDT, és erős végső konzisztenciát biztosít. A műveleteken alapuló CRDT növelő műveleteket küld, amikor azok keletkeznek.

PN-Számláló (Positive-Negative Counter) 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 = Σi P[i] - Σi N[i] compare (X, Y) : boolean b let b = (∀i ∈ [0, n - 1] : X.P[i] ≤ Y.P[i] ∧ ∀i ∈ [0, n - 1] : X.N[i] ≤ Y.N[i]) merge (X, Y) : payload Z let ∀i ∈ [0, n - 1] : Z.P[i] = max(X.P[i], Y.P[i]) let ∀i ∈ [0, n - 1] : Z.N[i] = max(X.N[i], Y.N[i])

A CRDT-fejlesztés során gyakori stratégia több CRDT kombinálása, hogy egy összetettebb CRDT-t hozzanak létre. Ebben az esetben két G-számlálót kombinálunk, hogy létrehozzunk egy olyan adattípust, amely mind a növelő, mind a csökkentő műveleteket támogatja. A „P” G-számláló növekményeket számol, az „N” G-számláló pedig csökkenéseket. A PN-számláló értéke a P-számláló értéke mínusz az N-számláló értéke. Az egyesítés ugyanúgy történik, ahogy két P G-számláló egyesítése, és hasonlóan az N számlálók esetében. Figyeljük meg, hogy a CRDT belső állapotának monoton módon kell növekednie, még akkor is, ha a lekérdezésben visszaadott állapota visszatérhet a korábbi értékekhez.

G-Halmaz (Grow-only Set) payload set A initial ∅ update add(element e) A := A ∪ {e} query lookup(element e) : boolean b let b = (e ∈ A) compare (S, T) : boolean b let b = (S.A ⊆ T.A) merge (S, T) : payload U let U.A = S.A ∪ T.A

A G-készlet (grow-only set) egy olyan halmaz, amely csak hozzáadásokat engedélyez. Egy egyszer hozzáadott elemet nem lehet eltávolítani. Két G-halmaz egyesülése az uniójuk.

2P-Halmaz (Two-Phase Set) payload set A, set R initial ∅, ∅ query lookup(element e) : boolean b let b = (e ∈ A ∧ e ∉ R) update add(element e) A := A ∪ {e} update remove(element e) pre lookup(e) R := R ∪ {e} compare (S, T) : boolean b let b = (S.A ⊆ T.A ∧ S.R ⊆ T.R) merge (S, T) : payload U let U.A = S.A ∪ T.A let U.R = S.R ∪ T.R

Két G-halmazt (csak növekvő készlet) kombinálunk a 2P-halmaz létrehozásához. Egy eltávolító halmaz (az úgynevezett „sírkő” (tombstone) halmaz) hozzáadásával elemek adhatók hozzá és el is távolíthatók. Ha egy elemet egyszer eltávolítottunk, nem lehet újra hozzáadni; vagyis ha egy e elem egyszer bekerült a sírkőhalmazba, a lekérdezés soha többé nem ad vissza Igaz értéket erre az elemre. A 2P-halmaz „remove-wins” (az eltávolítás nyer) szemantikát használ, tehát a remove(e) elsőbbséget élvez az add(e) előtt.

LWW-Elemhalmaz (Last-Write-Wins-Element-Set) Az LWW-Elemhalmaz hasonlít a 2P-készlethez abban, hogy egy „hozzáadási készletből” és egy „eltávolítási készletből” áll, és minden elemhez tartozik egy időbélyegző. Az elemek hozzáadása az LWW-Elemhalmaz úgy történik, hogy az elemet beillesztjük az add set-be, egy időbélyegzővel együtt. Az elemek eltávolítása az LWW-Elemhalmazból az eltávolítási készletbe való felvétellel történik, szintén időbélyeggel. Egy elem akkor tagja az LWW-Elemhalmaznak, ha szerepel az add-halmazban, és vagy nem szerepel a remove-halmazban, vagy szerepel a remove-halmazban, de korábbi időbélyeggel, mint az add-halmazban lévő legutolsó időbélyeg. Az LWW-Elemhalmaz két másolatának egyesítése az add halmazok és az remove halmazok egyesítéséből áll. Ha az időbélyegek megegyeznek, az LWW- Elemkészlet " elfogultsága" lép működésbe. Az LWW-Elemhalmaz lehet a hozzáadások vagy az eltávolítások irányába elfogult. Az LWW-Elemhalmaz előnye a 2P-készlettel szemben az, hogy a 2P-készlettel ellentétben az LWW-Elemhalmaz lehetővé teszi, hogy egy elemet eltávolítás után újra be lehessen illeszteni.

OR-Halmaz (Observed-Remove Set)