streamalism.org

1. Prehľad

V tomto článku sa pozrieme na bezkonfliktné replikované dátové typy (CRDT) a ako s nimi pracovať v prostredí Java. Pre naše príklady použijeme implementácie z wurmloch-crdt knižnica.

Keď máme zhluk N repliky uzlov v distribuovanom systéme, môžeme sa stretnúť s sieťový oddiel - niektoré uzly dočasne nemôžu navzájom komunikovať. Táto situácia sa nazýva split-brain.

Keď máme v našom systéme rozdelený mozog, niektoré požiadavky na zápis - aj pre toho istého používateľa - môžu ísť do rôznych replík, ktoré nie sú navzájom spojené. Keď dôjde k takejto situácii, naša systém je stále k dispozícii, ale nie je konzistentný.

Keď sieť medzi dvoma rozdelenými klastrami začne opäť fungovať, musíme sa rozhodnúť, čo robiť so zápismi a údajmi, ktoré nie sú konzistentné.

2. Bezkonfliktné replikované typy údajov na záchranu

Uvažujme o dvoch uzloch, A a B, ktoré sa odpojili v dôsledku rozdeleného mozgu.

Povedzme, že používateľ zmení svoje prihlasovacie údaje a že požiadavka smeruje do uzla A. Potom sa rozhodne znova to zmeniť, ale tentoraz ide požiadavka do uzla B.

Kvôli rozdelenému mozgu nie sú dva uzly spojené. Musíme sa rozhodnúť, ako by malo vyzerať prihlásenie tohto používateľa, keď sieť znova funguje.

Môžeme využiť niekoľko stratégií: môžeme dať používateľovi príležitosť na riešenie konfliktov (ako je to v Dokumentoch Google), alebo môžemepoužiť CRDT na zlúčenie údajov z odlišných replík pre nás.

3. Maven závislosť

Najskôr pridajme závislosť do knižnice, ktorá poskytuje množinu užitočných CRDT:

 com.netopyr.wurmloch wurmloch-crdt 0.1.0 

Najnovšiu verziu nájdete na serveri Maven Central.

4. Sada iba na pestovanie

Najzákladnejším CRDT je ​​sada iba na pestovanie. Prvky je možné pridať iba do a GSet a nikdy neodstránené. Keď GSet môže sa rozchádzať ľahko zlúčiteľné výpočtom únie z dvoch sád.

Najskôr vytvorme dve repliky, ktoré simulujú štruktúru distribuovaných údajov, a spojíme tieto dve repliky pomocou pripojiť () metóda:

LocalCrdtStore crdtStore1 = nový LocalCrdtStore (); LocalCrdtStore crdtStore2 = nový LocalCrdtStore (); crdtStore1.connect (crdtStore2);

Akonáhle dostaneme do nášho klastra dve repliky, môžeme vytvoriť GSet na prvej replike a porovnajte ju s druhou replikou:

GSet replica1 = crdtStore1.createGSet ("ID_1"); GSet replica2 = crdtStore2.findGSet ("ID_1"). Get ();

V tomto okamihu náš klaster pracuje podľa očakávania a medzi dvoma replikami je aktívne spojenie. Do sady môžeme pridať dva prvky z dvoch rôznych replík a ubezpečiť sa, že sada obsahuje rovnaké prvky na oboch replikách:

replica1.add ("jablko"); replica2.add ("banán"); assertThat (replica1) .obsahuje („jablko“, „banán“); assertThat (replica2) .obsahuje („jablko“, „banán“);

Povedzme, že zrazu máme sieťový oddiel a medzi prvou a druhou replikou nie je spojenie. Sieťový oddiel môžeme simulovať pomocou odpojiť () metóda:

crdtStore1.disconnect (crdtStore2);

Ďalej, keď do množiny údajov pridáme prvky z oboch replík, tieto zmeny nie sú globálne viditeľné, pretože medzi nimi nie je žiadne spojenie:

replica1.add ("jahoda"); replica2.add ("hruška"); assertThat (replica1) .obsahuje („jablko“, „banán“, „jahoda“); assertThat (replica2) .obsahuje („jablko“, „banán“, „hruška“);

Len čo sa spojenie medzi oboma členmi klastra znova vytvorí, GSet je zlúčený interne pomocou spojenia v oboch množinách a obe repliky sú opäť konzistentné:

crdtStore1.connect (crdtStore2); assertThat (replica1) .obsahuje („jablko“, „banán“, „jahoda“, „hruška“); assertThat (replica2) .obsahuje („jablko“, „banán“, „jahoda“, „hruška“);

5. Počítadlo iba s prírastkom

Počítadlo iba s prírastkom je CRDT, ktorý agreguje všetky prírastky lokálne na každom uzle.

Pri synchronizácii replík sa po sieťovom oddiele výsledná hodnota vypočíta spočítaním všetkých prírastkov na všetkých uzloch - toto je podobné ako LongAdder od java.bežne ale na vyššej úrovni abstrakcie.

Vytvorme počítadlo iba prírastkov pomocou GCounter a zvýšiť ju z oboch replík. Vidíme, že suma je vypočítaná správne:

LocalCrdtStore crdtStore1 = nový LocalCrdtStore (); LocalCrdtStore crdtStore2 = nový LocalCrdtStore (); crdtStore1.connect (crdtStore2); GCounter replica1 = crdtStore1.createGCounter ("ID_1"); GCounter replica2 = crdtStore2.findGCounter ("ID_1"). Get (); replica1.increment (); replica2.prírastok (2L); assertThat (replica1.get ()). isEqualTo (3L); assertThat (replica2.get ()). isEqualTo (3L); 

Keď odpojíme oboch členov klastra a vykonáme lokálne prírastkové operácie, môžeme vidieť, že hodnoty sú nekonzistentné:

crdtStore1.disconnect (crdtStore2); replica1.increment (3L); replica2.prírastok (5L); assertThat (replica1.get ()). isEqualTo (6L); assertThat (replica2.get ()). isEqualTo (8L);

Ale akonáhle je klaster opäť zdravý, prírastky sa zlúčia, čím sa získa správna hodnota:

crdtStore1.connect (crdtStore2); assertThat (replica1.get ()) .isEqualTo (11L); assertThat (replica2.get ()) .isEqualTo (11L);

6. Počítadlo PN

Použitím podobného pravidla pre počítadlo iba s prírastkom môžeme vytvoriť počítadlo, ktoré je možné zvyšovať aj znižovať. The PNCounter ukladá všetky prírastky a úbytky osobitne.

Keď sa repliky synchronizujú, výsledná hodnota sa bude rovnaťsúčet všetkých prírastkov mínus súčet všetkých prírastkov:

@Test public void givenPNCounter_whenReplicasDiverge_thenMergesWithoutConflict () {LocalCrdtStore crdtStore1 = nový LocalCrdtStore (); LocalCrdtStore crdtStore2 = nový LocalCrdtStore (); crdtStore1.connect (crdtStore2); PNCounter replica1 = crdtStore1.createPNCounter ("ID_1"); PNCounter replica2 = crdtStore2.findPNCounter ("ID_1"). Get (); replica1.increment (); replica2.decrement (2L); assertThat (replica1.get ()). isEqualTo (-1L); assertThat (replica2.get ()). isEqualTo (-1L); crdtStore1.disconnect (crdtStore2); replica1.decrement (3L); replica2.prírastok (5L); assertThat (replica1.get ()). isEqualTo (-4L); assertThat (replica2.get ()). isEqualTo (4L); crdtStore1.connect (crdtStore2); assertThat (replica1.get ()). isEqualTo (1L); assertThat (replica2.get ()). isEqualTo (1L); }

7. Last-Writer - vyhráva registráciu

Niekedy máme zložitejšie obchodné pravidlá a fungovanie na množinách alebo pultoch je nedostatočné. Môžeme použiť Register posledných vyhraných spisovateľov, ktorý pri zlučovaní rozdielnych množín údajov ponechá iba poslednú aktualizovanú hodnotu. Cassandra používa túto stratégiu na riešenie konfliktov.

Musíme pri používaní tejto stratégie buďte veľmi opatrní, pretože vylučuje zmeny, ktoré medzitým nastali.

Vytvorme klaster dvoch replík a inštancií LWWRegistrácia trieda:

LocalCrdtStore crdtStore1 = nový LocalCrdtStore ("N_1"); LocalCrdtStore crdtStore2 = nový LocalCrdtStore ("N_2"); crdtStore1.connect (crdtStore2); LWWRegister replica1 = crdtStore1.createLWWRegister ("ID_1"); LWWRegister replica2 = crdtStore2.findLWWRegister ("ID_1"). Get (); replica1.set ("jablko"); replica2.set ("banán"); assertThat (replica1.get ()). isEqualTo ("banán"); assertThat (replica2.get ()). isEqualTo ("banán"); 

Keď prvá replika nastaví hodnotu na jablko a druhá to mení na banán, the LWWRegistrácia ponecháva iba poslednú hodnotu.

Pozrime sa, čo sa stane, ak sa klaster odpojí:

crdtStore1.disconnect (crdtStore2); replica1.set ("jahoda"); replica2.set ("hruška"); assertThat (replica1.get ()). isEqualTo ("jahoda"); assertThat (replica2.get ()). isEqualTo ("hruška");

Každá replika si uchováva svoju miestnu kópiu údajov, ktorá je nekonzistentná. Keď hovoríme sada () metóda, LWWRegistrácia interne priraďuje špeciálnu hodnotu verzie, ktorá identifikuje konkrétnu aktualizáciu každému pomocou a VectorClock algoritmus.

Keď sa klaster synchronizuje, je to má hodnotu s najvyššou verziouazahodí každú predchádzajúcu aktualizáciu:

crdtStore1.connect (crdtStore2); assertThat (replica1.get ()). isEqualTo ("hruška"); assertThat (replica2.get ()). isEqualTo ("hruška");

8. Záver

V tomto článku sme si ukázali problém konzistencie distribuovaných systémov pri zachovaní dostupnosti.

V prípade sieťových oddielov musíme pri synchronizácii klastra zlúčiť rozdielne údaje. Videli sme, ako použiť CRDT na vykonanie zlúčenia rozdielnych údajov.

Všetky tieto príklady a útržky kódu nájdete v projekte GitHub - toto je projekt Maven, takže by malo byť ľahké ho importovať a spustiť tak, ako je.