Bevezetés az ütközésmentes replikált adattípusokba

1. Áttekintés

Ebben a cikkben megvizsgáljuk az ütközésmentes replikált adattípusokat (CRDT) és a velük való együttműködést a Java-ban. Példáinkhoz a wurmloch-crdt könyvtár.

Amikor van egy klaszterünk N replika csomópontok egy elosztott rendszerben, találkozhatunk a hálózati partíció - néhány csomópont ideiglenesen nem képes kommunikálni egymással. Ezt a helyzetet hasított agynak nevezzük.

Amikor a rendszerünkben hasított agy van, egyes írási kérelmek - még ugyanazon felhasználó esetében is - különböző másolatokhoz mehetnek, amelyek nincsenek összekapcsolva egymással. Ilyen helyzet bekövetkezésekor a mi rendszer még mindig elérhető, de nem következetes.

El kell döntenünk, hogy mit kezdjünk az írásokkal és az adatokkal, amelyek nem konzisztensek, amikor a hálózat két megosztott klaszter között újra működik.

2. Konfliktusmentes replikált adattípusok a mentéshez

Vegyünk két csomópontot, A és B, amelyek az agyrepedés miatt megszakadtak.

Tegyük fel, hogy egy felhasználó megváltoztatja a bejelentkezési adatait, és egy kérés megy a csomópontra A. Aztán úgy dönt, hogy újra megváltoztatja, de ezúttal a kérelem a csomóponthoz kerül B.

Az osztott agy miatt a két csomópont nincs összekapcsolva. El kell döntenünk, hogy nézzen ki ennek a felhasználónak a bejelentkezése, amikor a hálózat újra működik.

Használhatunk pár stratégiát: lehetőséget adhatunk a konfliktusok megoldására a felhasználónak (ahogy a Google Dokumentumokban is történik), vagy tudunkhasználjon CRDT-t az elválasztott replikák adatainak egyesítéséhez nekünk.

3. Maven-függőség

Először adjunk hozzá egy függőséget a könyvtárhoz, amely hasznos CRDT-ket kínál:

 com.netopyr.wurmloch wurmloch-crdt 0.1.0 

A legújabb verzió megtalálható a Maven Central oldalon.

4. Csak növekedésre szánt készlet

A legalapvetőbb CRDT egy csak növekedésre képes készlet. Elemek csak a GSet és soha nem távolították el. Amikor az GSet eltér, lehet könnyen összevonható az unió kiszámításával két készletből.

Először hozzunk létre két replikát az elosztott adatszerkezet szimulálására, és kapcsoljuk össze ezt a két replikát a connect () módszer:

LocalCrdtStore crdtStore1 = new LocalCrdtStore (); LocalCrdtStore crdtStore2 = new LocalCrdtStore (); crdtStore1.connect (crdtStore2);

Ha két replikát kapunk a fürtünkben, létrehozhatunk egy GSet az első másolaton, és utalja a második másolatra:

GSet replika1 = crdtStore1.createGSet ("ID_1"); GSet replika2 = crdtStore2.findGSet ("ID_1"). Get ();

Ezen a ponton a klaszterünk a várakozásoknak megfelelően működik, és két replika között aktív kapcsolat van. Két elemet hozzáadhatunk a halmazhoz két különböző replikából, és azt állíthatjuk, hogy a halmaz ugyanazokat az elemeket tartalmazza mindkét replikán:

replika1.add ("alma"); replika2.add ("banán"); assertThat (replika1). tartalmaz ("alma", "banán"); assertThat (replika2). tartalmaz ("alma", "banán");

Tegyük fel, hogy hirtelen hálózati partíciónk van, és nincs kapcsolat az első és a második replika között. Szimulálhatjuk a hálózati partíciót a bontás () módszer:

crdtStore1.disconnect (crdtStore2);

Ezután, amikor elemeket adunk mindkét replikából az adatkészlethez, ezek a változások globálisan nem láthatók, mivel nincs kapcsolat közöttük:

replika1.add ("eper"); replika2.add ("körte"); assertThat (replika1). tartalmaz ("alma", "banán", "eper"); assertThat (replika2). tartalmaz ("alma", "banán", "körte");

Miután a kapcsolat mindkét klasztertag között ismét létrejött, a GSet egyesül belsőleg használjon uniót mindkét halmazon, és mindkét replika ismét következetes:

crdtStore1.connect (crdtStore2); assertThat (replika1). tartalmaz ("alma", "banán", "eper", "körte"); assertThat (replika2). tartalmaz ("alma", "banán", "eper", "körte");

5. Csak növekményszámláló

A Csak növekményszámláló egy CRDT, amely az összes növekményt helyileg összesíti az egyes csomópontokon.

A replikák szinkronizálásakor a hálózati partíció után az eredmény kiszámításra kerül az összes csomópont összes növekményének összegzésével - ez hasonló a LongAdder tól től java.egyidejű de magasabb absztrakciós szinten.

Hozzunk létre egy csak növekményszámlálót a használatával GCounter és növelje mindkét másolatból. Láthatjuk, hogy az összeget megfelelően számolták ki:

LocalCrdtStore crdtStore1 = new LocalCrdtStore (); LocalCrdtStore crdtStore2 = new LocalCrdtStore (); crdtStore1.connect (crdtStore2); GCounter replika1 = crdtStore1.createGCounter ("ID_1"); GCounter replika2 = crdtStore2.findGCounter ("ID_1"). Get (); replika1.növekedés (); replika2.növekedés (2L); assertThat (replika1.get ()). isEqualTo (3L); assertThat (replika2.get ()). isEqualTo (3L); 

Amikor mindkét fürt tagot leválasztjuk és helyi növekményes műveleteket hajtunk végre, láthatjuk, hogy az értékek nem konzisztensek:

crdtStore1.disconnect (crdtStore2); replika1.növekedés (3L); replika2.növekedés (5L); assertThat (replika1.get ()). isEqualTo (6L); assertThat (replika2.get ()). isEqualTo (8L);

De amint a fürt ismét egészséges, a növekményeket összevonják, és megkapják a megfelelő értéket:

crdtStore1.connect (crdtStore2); assertThat (replika1.get ()) .isEqualTo (11L); assertThat (replika2.get ()) .isEqualTo (11L);

6. PN számláló

Hasonló szabályt használva a csak növekményszámlálóhoz létrehozhatunk számlálót, amely lehet mind növekményes, mind csökkenthető. A PNCounter minden növekményt és csökkentést külön tárol.

Amikor a másolatok szinkronizálódnak, a kapott érték megegyezik aaz összes növekmény összege mínusz az összes csökkentés összege:

@Test public void givenPNCounter_whenReplicasDiverge_thenMergesWithoutConflict () {LocalCrdtStore crdtStore1 = new LocalCrdtStore (); LocalCrdtStore crdtStore2 = new LocalCrdtStore (); crdtStore1.connect (crdtStore2); PNCounter replika1 = crdtStore1.createPNCounter ("ID_1"); PNCounter replika2 = crdtStore2.findPNCounter ("ID_1"). Get (); replika1.növekedés (); replika2.csökkenés (2L); assertThat (replika1.get ()) .EqualTo (-1L); assertThat (replika2.get ()) .EqualTo (-1L); crdtStore1.disconnect (crdtStore2); replika1.csökkenés (3L); replika2.növekedés (5L); assertThat (replika1.get ()) .EqualTo (-4L); assertThat (replica2.get ()). isEqualTo (4L); crdtStore1.connect (crdtStore2); assertThat (replica1.get ()). isEqualTo (1L); assertThat (replika2.get ()) .EqualTo (1L); }

7. Utolsó író-győzelem regisztráció

Néha bonyolultabb üzleti szabályaink vannak, és a készleteken vagy a számlálókon való működés nem elégséges. Használhatjuk a Last-Writer-Wins nyilvántartást, amely csak az utolsó frissített értéket tartja meg az elválasztott adathalmazok összevonásakor. Cassandra ezt a stratégiát használja a konfliktusok megoldására.

Meg kell legyen nagyon óvatos a stratégia használatakor, mert az időközben bekövetkezett változásokat elveti.

Hozzunk létre egy fürtöt két replikából és a LWWRegister osztály:

LocalCrdtStore crdtStore1 = új LocalCrdtStore ("N_1"); LocalCrdtStore crdtStore2 = új LocalCrdtStore ("N_2"); crdtStore1.connect (crdtStore2); LWWRegister replika1 = crdtStore1.createLWWRegister ("ID_1"); LWWRegister replica2 = crdtStore2.findLWWRegister ("ID_1"). Get (); replica1.set ("alma"); replica2.set ("banán"); assertThat (replika1.get ()). isEqualTo ("banán"); assertThat (replika2.get ()). isEqualTo ("banán"); 

Amikor az első replika értékre állítja alma a második pedig megváltoztatja banán, a LWWRegister csak az utolsó értéket tartja meg.

Lássuk, mi történik, ha a fürt megszakad:

crdtStore1.disconnect (crdtStore2); replica1.set ("eper"); replica2.set ("körte"); assertThat (replika1.get ()). isEqualTo ("eper"); assertThat (replika2.get ()). isEqualTo ("körte");

Minden másolat megőrzi az adatok helyi példányát, amely nem következetes. Amikor felhívjuk a készlet() módszer, az LWWRegister belsőleg hozzárendel egy speciális verzióértéket, amely azonosítja az adott frissítést minden a használó számára VectorClock algoritmus.

Amikor a fürt szinkronizálódik, akkor a legmagasabb verziójú értéket veszi felésminden korábbi frissítést elvet:

crdtStore1.connect (crdtStore2); assertThat (replika1.get ()). isEqualTo ("körte"); assertThat (replika2.get ()). isEqualTo ("körte");

8. Következtetés

Ebben a cikkben bemutattuk az elosztott rendszerek konzisztenciájának problémáját, a rendelkezésre állás fenntartása mellett.

Hálózati partíciók esetén a fürt szinkronizálásakor össze kell egyesítenünk az elválasztott adatokat. Láttuk, hogyan lehet CRDT-ket használni az elválasztott adatok egyesítéséhez.

Mindezek a példák és kódrészletek megtalálhatók a GitHub projektben - ez egy Maven projekt, ezért könnyen importálhatónak és futtathatónak kell lennie.