Introduzione ai tipi di dati replicati senza conflitti

1. Panoramica

In questo articolo, esamineremo i tipi di dati replicati senza conflitti (CRDT) e come utilizzarli in Java. Per i nostri esempi, utilizzeremo le implementazioni dalla libreria wurmloch-crdt .

Quando abbiamo un cluster di N nodi di replica in un sistema distribuito, potremmo incontrare una partizione di rete: alcuni nodi non sono temporaneamente in grado di comunicare tra loro . Questa situazione è chiamata cervello diviso.

Quando abbiamo uno split-brain nel nostro sistema, alcune richieste di scrittura, anche per lo stesso utente, possono andare a repliche diverse che non sono collegate tra loro . Quando si verifica una situazione del genere, il nostro sistema è ancora disponibile ma non è coerente .

Dobbiamo decidere cosa fare con scritture e dati che non sono coerenti quando la rete tra due cluster divisi riprende a funzionare.

2. Tipi di dati replicati senza conflitti in soccorso

Consideriamo due nodi, A e B , che si sono scollegati a causa di uno split-brain.

Diciamo che un utente cambia la sua login e che la richiesta va al nodo A . Poi lui / lei decide di cambiare di nuovo, ma questa volta la richiesta passa al nodo B .

A causa dello split-brain, i due nodi non sono collegati. Dobbiamo decidere come dovrebbe apparire il login di questo utente quando la rete funzionerà di nuovo.

Possiamo utilizzare un paio di strategie: possiamo dare l'opportunità di risolvere i conflitti all'utente (come si fa in Google Docs), oppure possiamo utilizzare un CRDT per unire i dati da repliche divergenti per noi.

3. Dipendenza da Maven

Innanzitutto, aggiungiamo una dipendenza alla libreria che fornisce una serie di CRDT utili:

 com.netopyr.wurmloch wurmloch-crdt 0.1.0 

L'ultima versione può essere trovata su Maven Central.

4. Set di sola coltivazione

Il CRDT più semplice è un set di sola coltivazione. Gli elementi possono essere aggiunti solo a un GSet e mai rimossi. Quando il GSet diverge, può essere facilmente unito calcolando l'unione di due insiemi.

Innanzitutto, creiamo due repliche per simulare una struttura dati distribuita e connettere queste due repliche utilizzando il metodo connect () :

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

Una volta ottenute due repliche nel nostro cluster, possiamo creare un GSet sulla prima replica e referenziarlo sulla seconda replica:

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

A questo punto, il nostro cluster funziona come previsto e c'è una connessione attiva tra due repliche. Possiamo aggiungere due elementi al set da due repliche differenti e affermare che il set contiene gli stessi elementi su entrambe le repliche:

replica1.add("apple"); replica2.add("banana"); assertThat(replica1).contains("apple", "banana"); assertThat(replica2).contains("apple", "banana");

Diciamo che all'improvviso abbiamo una partizione di rete e non c'è connessione tra la prima e la seconda replica. Possiamo simulare la partizione di rete usando il metodo disconnect () :

crdtStore1.disconnect(crdtStore2);

Successivamente, quando aggiungiamo elementi al set di dati da entrambe le repliche, tali modifiche non sono visibili a livello globale perché non vi è alcuna connessione tra di loro:

replica1.add("strawberry"); replica2.add("pear"); assertThat(replica1).contains("apple", "banana", "strawberry"); assertThat(replica2).contains("apple", "banana", "pear");

Una volta stabilita nuovamente la connessione tra entrambi i membri del cluster, il GSet viene unito internamente utilizzando un'unione su entrambi i set ed entrambe le repliche sono nuovamente coerenti:

crdtStore1.connect(crdtStore2); assertThat(replica1) .contains("apple", "banana", "strawberry", "pear"); assertThat(replica2) .contains("apple", "banana", "strawberry", "pear");

5. Contatore solo incremento

Il contatore di solo incremento è un CRDT che aggrega tutti gli incrementi localmente su ogni nodo.

Quando le repliche si sincronizzano, dopo una partizione di rete, il valore risultante viene calcolato sommando tutti gli incrementi su tutti i nodi : è simile a LongAdder da java.concurrent ma a un livello di astrazione più alto.

Creiamo un contatore solo incremento utilizzando GCounter e lo incrementiamo da entrambe le repliche. Possiamo vedere che la somma è calcolata correttamente:

LocalCrdtStore crdtStore1 = new LocalCrdtStore(); LocalCrdtStore crdtStore2 = new LocalCrdtStore(); crdtStore1.connect(crdtStore2); GCounter replica1 = crdtStore1.createGCounter("ID_1"); GCounter replica2 = crdtStore2.findGCounter("ID_1").get(); replica1.increment(); replica2.increment(2L); assertThat(replica1.get()).isEqualTo(3L); assertThat(replica2.get()).isEqualTo(3L); 

Quando disconnettiamo entrambi i membri del cluster ed eseguiamo operazioni di incremento locali, possiamo vedere che i valori sono incoerenti:

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

Ma una volta che il cluster è di nuovo integro, gli incrementi verranno uniti, producendo il valore corretto:

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

6. Contatore PN

Utilizzando una regola simile per il contatore di solo incremento, possiamo creare un contatore che può essere sia incrementato che decrementato. Il PNCounter memorizza tutti gli incrementi e le diminuzioni separatamente.

Quando le repliche vengono sincronizzate, il valore risultante sarà uguale alla somma di tutti gli incrementi meno la somma di tutti i decrementi :

@Test public void givenPNCounter_whenReplicasDiverge_thenMergesWithoutConflict() { LocalCrdtStore crdtStore1 = new LocalCrdtStore(); LocalCrdtStore crdtStore2 = new 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.increment(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. Registro delle vincite dell'ultimo autore

A volte abbiamo regole aziendali più complesse e operare su set o contatori non è sufficiente. Possiamo usare il registro Last-Writer-Wins, che mantiene solo l'ultimo valore aggiornato quando si uniscono set di dati divergenti . Cassandra utilizza questa strategia per risolvere i conflitti.

Dobbiamo essere molto cauti quando si utilizza questa strategia perché elimina i cambiamenti avvenuti nel frattempo .

Creiamo un cluster di due repliche e istanze della classe LWWRegister :

LocalCrdtStore crdtStore1 = new LocalCrdtStore("N_1"); LocalCrdtStore crdtStore2 = new LocalCrdtStore("N_2"); crdtStore1.connect(crdtStore2); LWWRegister replica1 = crdtStore1.createLWWRegister("ID_1"); LWWRegister replica2 = crdtStore2.findLWWRegister("ID_1").get(); replica1.set("apple"); replica2.set("banana"); assertThat(replica1.get()).isEqualTo("banana"); assertThat(replica2.get()).isEqualTo("banana"); 

Quando la prima replica imposta il valore su mela e la seconda lo cambia in banana, il registro LWW mantiene solo l'ultimo valore.

Vediamo cosa succede se il cluster si disconnette:

crdtStore1.disconnect(crdtStore2); replica1.set("strawberry"); replica2.set("pear"); assertThat(replica1.get()).isEqualTo("strawberry"); assertThat(replica2.get()).isEqualTo("pear");

Ogni replica conserva la sua copia locale dei dati che non è coerente. Quando chiamiamo il metodo set () , LWWRegister assegna internamente un valore di versione speciale che identifica l'aggiornamento specifico a ogni utente che utilizza un algoritmo VectorClock .

Quando il cluster si sincronizza, prende il valore con la versione più alta e scarta ogni aggiornamento precedente :

crdtStore1.connect(crdtStore2); assertThat(replica1.get()).isEqualTo("pear"); assertThat(replica2.get()).isEqualTo("pear");

8. Conclusione

In questo articolo abbiamo mostrato il problema della coerenza dei sistemi distribuiti mantenendo la disponibilità.

In caso di partizioni di rete, dobbiamo unire i dati divergenti quando il cluster è sincronizzato. Abbiamo visto come utilizzare i CRDT per eseguire un'unione di dati divergenti.

Tutti questi esempi e frammenti di codice possono essere trovati nel progetto GitHub: questo è un progetto Maven, quindi dovrebbe essere facile da importare ed eseguire così com'è.