Introduktion til konfliktfri replikerede datatyper

1. Oversigt

I denne artikel ser vi på konfliktfri replikerede datatyper (CRDT) og hvordan man arbejder med dem i Java. For vores eksempler bruger vi implementeringer fra wurmloch-crdt bibliotek.

Når vi har en klynge af N replikanoder i et distribueret system, kan vi støde på en netværkspartition - nogle noder kan midlertidigt ikke kommunikere med hinanden. Denne situation kaldes en split-hjerne.

Når vi har en splittet hjerne i vores system, nogle skriveanmodninger - selv for den samme bruger - kan gå til forskellige replikaer, der ikke er forbundet med hinanden. Når en sådan situation opstår, er vores systemet er stadig tilgængeligt, men er ikke ensartet.

Vi er nødt til at beslutte, hvad vi skal gøre med skrivning og data, der ikke er konsistente, når netværket mellem to splitklynger begynder at arbejde igen.

2. Konfliktfri replikerede datatyper til undsætning

Lad os overveje to noder, EN og B, der er blevet afbrudt på grund af en splittet hjerne.

Lad os sige, at en bruger ændrer sit login, og at en anmodning går til noden EN. Derefter beslutter han / hun at ændre det igen, men denne gang går anmodningen til noden B.

På grund af split-hjernen er de to knudepunkter ikke forbundet. Vi er nødt til at beslutte, hvordan denne brugers login skal se ud, når netværket fungerer igen.

Vi kan bruge et par strategier: vi kan give mulighed for at løse konflikter til brugeren (som det gøres i Google Docs), eller vi kanBrug en CRDT til at flette data fra divergerede replikaer for os.

3. Maven-afhængighed

Lad os først tilføje en afhængighed til biblioteket, der giver et sæt nyttige CRDT'er:

 com.netopyr.wurmloch wurmloch-crdt 0.1.0 

Den seneste version kan findes på Maven Central.

4. Kun vækstsæt

Den mest basale CRDT er et Grow-Only-sæt. Elementer kan kun føjes til en GSet og aldrig fjernet. Når GSet adskiller sig, kan det være let flettes ved at beregne unionen af to sæt.

Lad os først oprette to replikaer for at simulere en distribueret datastruktur og forbinde disse to replikaer ved hjælp af Opret forbindelse() metode:

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

Når vi har fået to replikaer i vores klynge, kan vi oprette en GSet på den første replika og henvise den til den anden replika:

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

På dette tidspunkt fungerer vores klynge som forventet, og der er en aktiv forbindelse mellem to replikaer. Vi kan tilføje to elementer til sættet fra to forskellige replikaer og hævde, at sættet indeholder de samme elementer på begge replikaer:

replika1.add ("æble"); replika2.add ("banan"); assertThat (replika1). indeholder ("æble", "banan"); assertThat (replika2). indeholder ("æble", "banan");

Lad os sige, at vi pludselig har en netværkspartition, og der er ingen forbindelse mellem den første og anden replika. Vi kan simulere netværkspartitionen ved hjælp af koble fra() metode:

crdtStore1.disconnect (crdtStore2);

Når vi derefter tilføjer elementer til datasættet fra begge replikaer, er disse ændringer ikke synlige globalt, fordi der ikke er nogen forbindelse mellem dem:

replika1.add ("jordbær"); replika2.add ("pære"); assertThat (replika1). indeholder ("æble", "banan", "jordbær"); assertThat (replika2). indeholder ("æble", "banan", "pære");

Når forbindelsen mellem begge klyngemedlemmer er etableret igen, GSet er slået sammen internt ved hjælp af en union på begge sæt, og begge replikaer er konsistente igen:

crdtStore1.connect (crdtStore2); assertThat (replika1). indeholder ("æble", "banan", "jordbær", "pære"); assertThat (replika2). indeholder ("æble", "banan", "jordbær", "pære");

5. Tæller, der kun er steget

Increment-Only-tæller er en CRDT, der samler alle trin lokalt på hver node.

Når repliker synkroniseres, beregnes den resulterende værdi efter en netværkspartition ved at summere alle trin på alle noder - dette svarer til LongAdder fra java.concurrent men på et højere abstraktionsniveau.

Lad os oprette en skridt-kun-tæller ved hjælp af GCounter og forøg det fra begge replikaer. Vi kan se, at summen beregnes korrekt:

LocalCrdtStore crdtStore1 = ny LocalCrdtStore (); LocalCrdtStore crdtStore2 = ny LocalCrdtStore (); crdtStore1.connect (crdtStore2); GCounter replika1 = crdtStore1.createGCounter ("ID_1"); GCounter replika2 = crdtStore2.findGCounter ("ID_1"). Get (); replika1.inkrement (); replika2.inkrement (2L); assertThat (replika1.get ()). er EqualTo (3L); assertThat (replica2.get ()). er EqualTo (3L); 

Når vi afbryder begge klyngemedlemmer og udfører lokale forøgelsesoperationer, kan vi se, at værdierne er inkonsekvente:

crdtStore1.disconnect (crdtStore2); replika1.forøgelse (3L); replika2.inkrement (5L); assertThat (replika1.get ()). er EqualTo (6L); assertThat (replica2.get ()). er EqualTo (8L);

Men når klyngen er sund igen, vil trinene blive flettet, hvilket giver den rette værdi:

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

6. PN-tæller

Ved hjælp af en lignende regel for tælleren med kun stigning kan vi oprette en tæller, der både kan øges og reduceres. Det PNCounter gemmer alle forøgelser og forøgelser separat.

Når replikaer synkroniseres, vil den resulterende værdi være lig medsummen af ​​alle forøgelser minus summen af ​​alle forøgelser:

@Test offentlig ugyldighed givetPNCounter_whenReplicasDiverge_thenMergesWithoutConflict () {LocalCrdtStore crdtStore1 = ny LocalCrdtStore (); LocalCrdtStore crdtStore2 = ny LocalCrdtStore (); crdtStore1.connect (crdtStore2); PNCounter replika1 = crdtStore1.createPNCounter ("ID_1"); PNCounter replika2 = crdtStore2.findPNCounter ("ID_1"). Get (); replika1.inkrement (); replika2.decrement (2L); assertThat (replika1.get ()). er EqualTo (-1L); assertThat (replica2.get ()). er EqualTo (-1L); crdtStore1.disconnect (crdtStore2); replika1.reduktion (3L); replika2.inkrement (5L); assertThat (replika1.get ()). er EqualTo (-4L); assertThat (replica2.get ()). er EqualTo (4L); crdtStore1.connect (crdtStore2); assertThat (replika1.get ()). er EqualTo (1L); assertThat (replica2.get ()). er EqualTo (1L); }

7. Last-Writer-Wins Register

Nogle gange har vi mere komplekse forretningsregler, og det er utilstrækkeligt at arbejde på sæt eller tællere. Vi kan bruge Last-Writer-Wins Register, som beholder kun den sidst opdaterede værdi, når sammenfletning af forskellige datasæt. Cassandra bruger denne strategi til at løse konflikter.

Vi er nødt til være meget forsigtig, når du bruger denne strategi, fordi den dropper ændringer, der opstod i mellemtiden.

Lad os oprette en klynge af to replikaer og forekomster af LWW Tilmeld klasse:

LocalCrdtStore crdtStore1 = ny LocalCrdtStore ("N_1"); LocalCrdtStore crdtStore2 = ny LocalCrdtStore ("N_2"); crdtStore1.connect (crdtStore2); LWWRegister replika1 = crdtStore1.createLWWRegister ("ID_1"); LWWRegister replika2 = crdtStore2.findLWWRegister ("ID_1"). Get (); replika1.set ("æble"); replica2.set ("banan"); assertThat (replika1.get ()). er EqualTo ("banan"); assertThat (replica2.get ()). er EqualTo ("banan"); 

Når den første replika indstiller værdien til æble og den anden ændrer den til banan, det LWW Tilmeld holder kun den sidste værdi.

Lad os se, hvad der sker, hvis klyngen afbrydes:

crdtStore1.disconnect (crdtStore2); replica1.set ("jordbær"); replica2.set ("pære"); assertThat (replika1.get ()). er EqualTo ("jordbær"); assertThat (replica2.get ()). er EqualTo ("pære");

Hver replika beholder sin lokale kopi af data, der er inkonsekvente. Når vi kalder sæt() metode, den LWW Tilmeld internt tildeler en særlig versionværdi, der identificerer den specifikke opdatering til alle, der bruger en VectorClock algoritme.

Når klyngen synkroniseres, er den tager værdien med den højeste versionogkasserer hver tidligere opdatering:

crdtStore1.connect (crdtStore2); assertThat (replika1.get ()). er EqualTo ("pære"); assertThat (replica2.get ()). er EqualTo ("pære");

8. Konklusion

I denne artikel viste vi problemet med konsistensen af ​​distribuerede systemer, samtidig med at tilgængeligheden opretholdes.

I tilfælde af netværkspartitioner skal vi flette de afvigende data, når klyngen synkroniseres. Vi så, hvordan man bruger CRDT'er til at udføre en fletning af afvigende data.

Alle disse eksempler og kodestykker findes i GitHub-projektet - dette er et Maven-projekt, så det skal være let at importere og køre som det er.


$config[zx-auto] not found$config[zx-overlay] not found