Konfliktusmentes replikált adattípus

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)

Az OR-Set hasonlít az LWW-Elemhalmazhoz, de időbélyegek helyett egyedi címkéket használ. A halmaz minden egyes eleméhez egy listát vezetünk az add-címkékről és egy listát a remove-címkékről. Egy elemet úgy illesztünk be az OR-Set-be, hogy egy új egyedi címkét generálunk és hozzáadjuk az adott elem add-tag listájához. Az elemek eltávolítása az OR-halmazból úgy történik, hogy az elem add-tag listájában szereplő összes tag hozzáadódik az elem remove-tag (tombstone) listájához. Két OR-halmaz egyesítéséhez minden elem add-tag listája legyen a két add-tag lista egyesítése, és ugyanígy a két remove-tag lista is. Egy elem akkor és csak akkor tagja a halmaznak, ha az add-tag-lista mínusz a remove-tag-lista nem üres. Lehetséges egy olyan optimalizálás, amely kiküszöböli a tombstone-halmaz fenntartásának szükségességét; ezzel elkerülhető a tombstone-halmaz potenciálisan korlátlan növekedése. Az optimalizálás úgy érhető el, hogy minden egyes replikához egy időbélyegző vektort tartunk fenn.

Szekvenciális CRDT-k

Egy szekvencia, lista vagy rendezett halmaz CRDT használható egy együttműködő valós idejű szövegszerkesztő felépítésére, az operatív transzformáció (OT) alternatívájaként.

Néhány ismert szekvencia CRDT a Treedoc, RGA, Woot, Logoot, és az LSEQ. A CRATE egy decentralizált valós idejű szerkesztő, amely az LSEQSplit (az LSEQ kiterjesztése) alapjaira épül, és a WebRTC segítségével böngészők hálózatán futtatható. A LogootSplit a Logoot kiterjesztéseként a szekvencia CRDT-k metaadatainak csökkentése érdekében született javaslat. A MUTE a LogootSplit algoritmusra támaszkodó online webalapú peer-to-peer valós idejű kollaboratív szerkesztő.

Az ipari szekvencia CRDT-k, beleértve a nyílt forráskódúakat is, az optimalizálásoknak és a reálisabb tesztelési módszertannak köszönhetően közismerten felülmúlják az akadémiai implementációkat[24] A legfőbb népszerű példa az Yjs CRDT, amely úttörő volt a fa helyett plainlistát használó (ala Kleppmann automerge).

Alkalmazásuk

• Zed egy nyílt forráskódú, kollaboratív IDE, amelyet a zed-industries épített, és amely CRDT-ket használ a „pufferekben” a konfliktusok kezelésére, amikor közös szerkesztést végeznek ugyanazon a fájlon.
• A Fluid Framework a Microsoft által épített nyílt forráskódú kollaboratív platform, amely mind szerverreferencia implementációkat, mind kliensoldali SDK-kat biztosít a CRDT-ket használó modern, valós idejű webes alkalmazások létrehozásához.
• A Nimbus Note egy kollaboratív jegyzetelő alkalmazás, amely az Yjs CRDT-t használja a kollaboratív szerkesztéshez.
• A Redis egy elosztott, nagy rendelkezésre állású és skálázható, memórián belüli adatbázis, amely rendelkezik „CRDT-kompatibilis adatbázis” funkcióval.
• SoundCloud nyílt forráskódú Roshi, egy LWW-elemkészletű CRDT a SoundCloud streamhez, amelyet a Redis tetején valósítottak meg.
• A Riak egy elosztott NoSQL kulcs-érték adattároló, amely CRDT-ken alapul. League of Legends' a Riak CRDT implementációját használja a játékon belüli chat rendszeréhez, amely 7,5 millió egyidejű felhasználót és 11 000 üzenetet kezel másodpercenként.
• A Bet365 több száz megabájtnyi adatot tárol az OR-Set Riak implementációjában.
• A TomTom CRDT-ket használ a navigációs adatok szinkronizálására a felhasználó készülékei között.
• A Phoenix, egy Elixir nyelven írt webes keretrendszer az 1.2. verzióban CRDT-ket használ a valós idejű, több csomópontból álló információmegosztás támogatására.
• A Facebook a CRDT-ket az Apollo alacsony késleltetésű „konzisztencia méretarányos” adatbázisában valósítja meg.
• A Facebook CRDT-ket használ a FlightTracker rendszerében a Facebook gráf belső kezelésére.
• A Atom Teletype a CRDT-ket alkalmazza, hogy a fejlesztők megoszthassák a munkaterületüket a csapattagokkal, és valós időben dolgozhassanak együtt a kódon.
• A Haja Networks OrbitDB-je műveletalapú CRDT-ket használ az alapvető adatszerkezetében, az IPFS-Logban.
• Apple a CRDT-ket a Notes alkalmazásban valósítja meg az offline szerkesztések több eszköz közötti szinkronizálására.
• A Swim egy platform elosztott valós idejű streaming alkalmazások futtatására, amelyek folyamatos intelligenciát biztosítanak. Olyan streaming szereplőket használ, amelyek tisztán op-alapú CRDT állapotfrissítéseket streamelnek más szereplőkhöz egy DAG-ban, amely egy streaming adatcsatornát valósít meg.
• RxDB egy kliensoldali NoSQL adatbázis elosztott valós idejű streaming alkalmazásokhoz. Van egy CRDT plugin, amely lehetővé teszi egy dokumentum frissítését NoSQL alapú CRDT delták tárolásával és ezek replikálásával más kliensekkel vagy egy backend szerverrel.
• A PGD egy PostgreSQL alapú, több mesterrel rendelkező replikációs megoldás. Támogatja a CRDT oszloptípusokat.

Források

• Ez a szócikk részben vagy egészben a CRDT című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.