streamalism.org

1. Oversikt

I denne artikkelen ser vi på konfliktfrie replikerte datatyper (CRDT) og hvordan du jobber med dem i Java. For eksemplene våre bruker vi implementeringer fra wurmloch-crdt bibliotek.

Når vi har en klynge av N replikanoder i et distribuert system, kan vi støte på en nettverkspartisjon - noen noder kan midlertidig ikke kommunisere med hverandre. Denne situasjonen kalles en splittet hjerne.

Når vi har en splittet hjerne i systemet vårt, noen skriveforespørsler - selv for den samme brukeren - kan gå til forskjellige replikaer som ikke er koblet til hverandre. Når en slik situasjon oppstår, er vår systemet er fortsatt tilgjengelig, men er ikke konsistent.

Vi må bestemme hva vi skal gjøre med skriving og data som ikke er konsistente når nettverket mellom to delte klynger begynner å fungere igjen.

2. Konfliktfrie replikerte datatyper til unnsetning

La oss vurdere to noder, EN og B, som har blitt koblet fra på grunn av en splittet hjerne.

La oss si at en bruker endrer påloggingen, og at en forespørsel går til noden EN. Så bestemmer han / hun seg for å endre det igjen, men denne gangen går forespørselen til noden B.

På grunn av splittet hjerne er de to nodene ikke koblet sammen. Vi må bestemme hvordan innloggingen til denne brukeren skal se ut når nettverket fungerer igjen.

Vi kan bruke et par strategier: vi kan gi muligheten til å løse konflikter til brukeren (som det gjøres i Google Docs), eller vi kanbruk en CRDT for å slå sammen data fra avvikende replikaer for oss.

3. Maven avhengighet

La oss først legge til en avhengighet i biblioteket som gir et sett med nyttige CRDTer:

 com.netopyr.wurmloch wurmloch-crdt 0.1.0 

Den siste versjonen finner du på Maven Central.

4. Grow-Only sett

Den mest grunnleggende CRDT er et Grow-Only-sett. Elementer kan bare legges til i GSett og aldri fjernet. Når GSett avviker, kan det være enkelt sammenslått ved å beregne unionen av to sett.

La oss først lage to kopier for å simulere en distribuert datastruktur og koble de to kopiene ved hjelp av koble() metode:

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

Når vi har fått to kopier i klyngen vår, kan vi lage en GSett på den første kopien og referere den til den andre kopien:

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

På dette punktet fungerer klyngen vår som forventet, og det er en aktiv forbindelse mellom to replikaer. Vi kan legge til to elementer i settet fra to forskjellige replikaer og hevde at settet inneholder de samme elementene på begge replikaene:

replika1.add ("eple"); replica2.add ("banan"); assertThat (replika1). inneholder ("eple", "banan"); assertThat (replica2) .contains ("apple", "banana");

La oss si at vi plutselig har en nettverkspartisjon, og det er ingen sammenheng mellom første og andre kopier. Vi kan simulere nettverkspartisjonen ved hjelp av koble fra() metode:

crdtStore1.disconnect (crdtStore2);

Når vi deretter legger til elementer i datasettet fra begge replikaene, er disse endringene ikke synlige globalt fordi det ikke er noen forbindelse mellom dem:

replika1.add ("jordbær"); replica2.add ("pære"); assertThat (replika1). inneholder ("eple", "banan", "jordbær"); assertThat (replica2) .contains ("apple", "banana", "pear");

Når forbindelsen mellom begge klyngemedlemmene er opprettet igjen, vil GSett er slått sammen internt ved hjelp av en union på begge settene, og begge replikaene er konsistente igjen:

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

5. Counter-Only Counter

Inkrement-Only-teller er en CRDT som samler alle trinn lokalt på hver node.

Når replikaer synkroniseres, beregnes den resulterende verdien etter en nettverkspartisjon ved å summere alle trinn på alle noder - dette ligner på LongAdder fra java.concurrent men på et høyere abstraksjonsnivå.

La oss lage en trinnvis teller med GCounter og øk den fra begge kopiene. Vi kan se at summen beregnes riktig:

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

Når vi kobler fra begge klyngemedlemmene og utfører lokale økningsoperasjoner, kan vi se at verdiene er inkonsekvente:

crdtStore1.disconnect (crdtStore2); replika1.inkrement (3L); replika2.inkrement (5L); assertThat (replika1.get ()). erEqualTo (6L); assertThat (replica2.get ()). erEqualTo (8L);

Men når klyngen er sunn igjen, vil trinnene bli slått sammen og gi riktig verdi:

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

6. PN-teller

Ved å bruke en lignende regel for telleren for kun inkrement, kan vi opprette en teller som både kan økes og reduseres. De PNCounter lagrer alle trinn og reduksjoner separat.

Når replikaer synkroniseres, vil den resulterende verdien være liksummen av alle trinn minus summen av alle nedganger:

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

7. Registrering for siste forfatter-gevinst

Noen ganger har vi mer komplekse forretningsregler, og det er ikke tilstrekkelig å operere på sett eller benkeplater. Vi kan bruke Last-Writer-Wins Register, som beholder bare den sist oppdaterte verdien når du slår sammen forskjellige data sett. Cassandra bruker denne strategien for å løse konflikter.

Vi må vær veldig forsiktig når du bruker denne strategien fordi den dropper endringer som skjedde i mellomtiden.

La oss lage en klynge av to kopier og forekomster av LWW Registrer deg klasse:

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

Når den første kopien setter verdien til eple og den andre endrer den til banan, de LWW Registrer deg holder bare den siste verdien.

La oss se hva som skjer hvis klyngen kobler fra:

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

Hver replika beholder sin lokale kopi av data som er inkonsekvente. Når vi kaller sett() metoden, den LWW Registrer deg internt tilordner en spesiell versjonsverdi som identifiserer den spesifikke oppdateringen til alle som bruker en VectorClock algoritme.

Når klyngen synkroniseres, blir den tar verdien med den høyeste versjonenogkaster hver forrige oppdatering:

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

8. Konklusjon

I denne artikkelen viste vi problemet med konsistens av distribuerte systemer mens vi opprettholder tilgjengeligheten.

I tilfelle nettverkspartisjoner, må vi slå sammen de avvikne dataene når klyngen er synkronisert. Vi så hvordan du bruker CRDTs til å utføre en sammenslåing av avvikende data.

Alle disse eksemplene og kodebitene finner du i GitHub-prosjektet - dette er et Maven-prosjekt, så det skal være enkelt å importere og kjøre som det er.