Uvod u tipove podataka bez sukoba
1. Pregled
U ovom ćemo članku pogledati replicirane tipove podataka (CRDT) bez sukoba i način rada s njima na Javi. Za naše primjere koristit ćemo implementacije iz wurmloch-crdt knjižnica.
Kad imamo skupinu N replika čvorova u distribuiranom sustavu, možemo naići na mrežna particija - neki čvorovi privremeno nisu u mogućnosti međusobno komunicirati. Ta se situacija naziva podijeljeni mozak.
Kada u našem sustavu imamo podijeljeni mozak, neki zahtjevi za pisanje - čak i za istog korisnika - mogu ići na različite replike koje međusobno nisu povezane. Kad se dogodi takva situacija, naša sustav je još uvijek dostupan, ali nije dosljedan.
Moramo odlučiti što učiniti s upisima i podacima koji nisu konzistentni kada mreža između dva podijeljena klastera ponovno počne raditi.
2. Tipovi podataka bez sukoba za spašavanje
Razmotrimo dva čvora, A i B, koji su postali nepovezani zbog podijeljenog mozga.
Recimo da korisnik promijeni prijavu i da zahtjev ide na čvor A. Tada je odluči ponovo promijeniti, ali ovaj put zahtjev ide na čvor B.
Zbog podijeljenog mozga, dva čvora nisu povezana. Moramo odlučiti kako bi trebala izgledati prijava ovog korisnika kada mreža ponovo radi.
Možemo iskoristiti nekoliko strategija: možemo pružiti priliku za rješavanje sukoba korisniku (kao što je to učinjeno u Google dokumentima) ili možemokoristite CRDT za spajanje podataka iz divergiranih replika za nas.
3. Ovisnost Mavena
Prvo, dodamo ovisnost knjižnici koja pruža skup korisnih CRDT-ova:
com.netopyr.wurmloch wurmloch-crdt 0.1.0 Najnoviju verziju možete pronaći na Maven Central.
4. Set samo za uzgoj
Najosnovniji CRDT je Grow-Only Set. Elementi se mogu dodavati samo u GSet i nikad uklonjena. Kada GSet razilazi se, može biti lako se spajaju izračunavanjem unije od dva seta.
Prvo stvorimo dvije replike da simuliramo distribuiranu strukturu podataka i povežemo te dvije replike pomoću Spojiti() metoda:
LocalCrdtStore crdtStore1 = novo LocalCrdtStore (); LocalCrdtStore crdtStore2 = novo LocalCrdtStore (); crdtStore1.connect (crdtStore2);Jednom kada u svoju klaster dobijemo dvije replike, možemo stvoriti GSet na prvoj replici i referencirajte je na drugoj replici:
GSet replika1 = crdtStore1.createGSet ("ID_1"); GSet replika2 = crdtStore2.findGSet ("ID_1"). Get ();U ovom trenutku naša klastera radi prema očekivanjima i postoji aktivna veza između dviju replika. U set možemo dodati dva elementa iz dvije različite replike i ustvrditi da skup sadrži iste elemente na obje replike:
replica1.add ("jabuka"); replica2.add ("banana"); assertThat (replica1) .contens ("apple", "banana"); assertThat (replica2) .contens ("apple", "banana");Recimo da odjednom imamo mrežnu particiju i da nema veze između prve i druge replike. Mrežnu particiju možemo simulirati pomoću odspojiti () metoda:
crdtStore1.disconnect (crdtStore2);Dalje, kada dodamo elemente skupu podataka iz obje replike, te promjene nisu globalno vidljive jer između njih nema veze:
replica1.add ("jagoda"); replica2.add ("kruška"); assertThat (replica1) .sadrži ("jabuka", "banana", "jagoda"); assertThat (replica2) .sadrži ("jabuka", "banana", "kruška");Jednom kada se uspostavi veza između oba člana klastera, GSet je spojen interno koristeći uniju na oba skupa, a obje su replike ponovno dosljedne:
crdtStore1.connect (crdtStore2); assertThat (replica1) .sadrži ("jabuka", "banana", "jagoda", "kruška"); assertThat (replica2) .sadrži ("jabuka", "banana", "jagoda", "kruška");5. Brojač samo za povećanje
Brojač samo za povećanje je CRDT koji agregira sve korake lokalno na svakom čvoru.
Kada se replike sinkroniziraju, nakon mrežne particije, rezultirajuća vrijednost izračunava se zbrajanjem svih prirasta na svim čvorovima - ovo je slično LongAdder iz java.konkurentan ali na višoj razini apstrakcije.
Stvorimo pomoću brojača samo prirast GCounter i povećajte ga iz obje replike. Vidimo da se zbroj pravilno izračunava:
LocalCrdtStore crdtStore1 = novo LocalCrdtStore (); LocalCrdtStore crdtStore2 = novo LocalCrdtStore (); crdtStore1.connect (crdtStore2); GCounter replika1 = crdtStore1.createGCounter ("ID_1"); GCounter replika2 = crdtStore2.findGCounter ("ID_1"). Get (); replika1.increment (); replika2.prirast (2L); assertThat (replica1.get ()). isEqualTo (3L); assertThat (replica2.get ()). isEqualTo (3L); Kada odvojimo oba člana klastera i izvedemo lokalne operacije prirasta, možemo vidjeti da su vrijednosti nedosljedne:
crdtStore1.disconnect (crdtStore2); replika1.prirast (3L); replika2.prirast (5L); assertThat (replica1.get ()). isEqualTo (6L); assertThat (replica2.get ()). isEqualTo (8L);No, nakon što klaster ponovno bude zdrav, koraci će se spojiti, dajući odgovarajuću vrijednost:
crdtStore1.connect (crdtStore2); assertThat (replica1.get ()) .isEqualTo (11L); assertThat (replica2.get ()) .isEqualTo (11L);6. PN brojač
Koristeći slično pravilo za brojač samo za povećanje, možemo stvoriti brojač koji se može povećavati i smanjivati. The PNCounter pohranjuje sve prirastke i umanjenja zasebno.
Kada se replike sinkroniziraju, rezultirajuća vrijednost bit će jednakazbroj svih priraštaja minus zbroj svih priraštaja:
@Test javna praznina danaPNCounter_whenReplicasDiverge_thenMergesWithoutConflict () {LocalCrdtStore crdtStore1 = new LocalCrdtStore (); LocalCrdtStore crdtStore2 = novo LocalCrdtStore (); crdtStore1.connect (crdtStore2); PNCounter replica1 = crdtStore1.createPNCounter ("ID_1"); PNCounter replica2 = crdtStore2.findPNCounter ("ID_1"). Get (); replika1.increment (); replika2.dekrement (2L); assertThat (replica1.get ()). isEqualTo (-1L); assertThat (replica2.get ()). isEqualTo (-1L); crdtStore1.disconnect (crdtStore2); replika1.dekrement (3L); replika2.prirast (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. Registar posljednjih pisaca-pobjeda
Ponekad imamo složenija poslovna pravila, a djelovanje na setovima ili brojačima nije dovoljno. Možemo se koristiti Registrom posljednjih pisaca-pobjeda, koji zadržava samo zadnju ažuriranu vrijednost pri spajanju divergiranih skupova podataka. Cassandra koristi ovu strategiju za rješavanje sukoba.
Moramo budite vrlo oprezni pri korištenju ove strategije jer ona ispušta promjene koje su se dogodile u međuvremenu.
Stvorimo klaster od dvije replike i instance LWWPrijavite se razred:
LocalCrdtStore crdtStore1 = novo LocalCrdtStore ("N_1"); LocalCrdtStore crdtStore2 = novo LocalCrdtStore ("N_2"); crdtStore1.connect (crdtStore2); LWWRegister replika1 = crdtStore1.createLWWRegister ("ID_1"); LWWRegister replika2 = crdtStore2.findLWWRegister ("ID_1"). Get (); replica1.set ("jabuka"); replica2.set ("banana"); assertThat (replica1.get ()). isEqualTo ("banana"); assertThat (replica2.get ()). isEqualTo ("banana"); Kada prva replika postavi vrijednost na jabuka a druga ga mijenja u banana, the LWWPrijavite se zadržava samo zadnju vrijednost.
Pogledajmo što će se dogoditi ako se klaster prekine:
crdtStore1.disconnect (crdtStore2); replica1.set ("jagoda"); replica2.set ("kruška"); assertThat (replica1.get ()). isEqualTo ("jagoda"); assertThat (replica2.get ()). isEqualTo ("kruška");Svaka replika čuva svoju lokalnu kopiju podataka koja nije u skladu. Kad nazovemo postavi () metoda, LWWPrijavite se interno dodjeljuje posebnu vrijednost verzije koja identificira određeno ažuriranje svakom korištenju a VectorClock algoritam.
Kada se klaster sinkronizira, to uzima vrijednost s najvišom verzijomiodbacuje svako prethodno ažuriranje:
crdtStore1.connect (crdtStore2); assertThat (replica1.get ()). isEqualTo ("kruška"); assertThat (replica2.get ()). isEqualTo ("kruška");8. Zaključak
U ovom smo članku pokazali problem dosljednosti distribuiranih sustava uz održavanje dostupnosti.
U slučaju mrežnih particija, moramo spojiti divergirane podatke kada se klaster sinkronizira. Vidjeli smo kako se pomoću CRDT-a može izvršiti spajanje različitih podataka.
Svi ovi primjeri i isječci koda mogu se naći u projektu GitHub - ovo je Maven projekt, pa bi ga trebalo lako uvesti i pokrenuti kakav jest.
