CRDTs usano la matematica per far rispettare la coerenza tra un cluster distribuito, senza doversi preoccupare di consenso e un latenza/indisponibilità associate.
L'insieme di valori che un CRDT può assumere in qualsiasi momento rientra nella categoria di un semi-reticolo (in particolare un semi-reticolo di unione), che è un POSET (set parzialmente ordinato) con una funzione di limite superiore (LUB).
In termini semplici, un POSET è una raccolta di elementi in cui non tutti sono comparabili. Per esempio. in una serie di coppie: {(2,4), (4, 5), (2, 1), (6, 3)}
, (2,4)
è < (4,5)
, ma non può essere confrontato con (6,3)
(poiché un elemento è più grande e l'altro più piccolo). Ora, un semi-lattice è un POSET in cui date 2 coppie, anche se non è possibile confrontare i due, è possibile trovare un elemento più grande di entrambi.
Un'altra condizione è che gli aggiornamenti di questo tipo di dati devono essere in aumento, i CRDT hanno uno stato di aumento monotono, in cui i client non osservano mai il rollback dello stato.
Questo excellent article utilizza l'array che ho usato sopra come esempio. Per un CRDT che mantiene tali valori, se 2 repliche cercano di raggiungere il consenso tra (4,5)
e (6,3)
, possono scegliere un LUB = (6,5)
come consenso e assegnare entrambe le repliche. Poiché i valori sono in aumento, questo è un buon valore da regolare.
Ci sono 2 modi per CRDTs per mantenere in sincronia con l'altro attraverso le repliche, che possono trasferire lo stato tra periodicamente (convergente replicato tipo di dati), oppure possono trasferire aggiornamenti (delta) attraverso mentre ottengono loro (commutativa replicato tipo di dati). Il primo richiede più larghezza di banda.
SoundCloud's Roshi è un buon esempio (sebbene non sia più in sviluppo sembra), memorizzano i dati associati a un timestamp, in cui il timestamp sta ovviamente incrementando. Gli aggiornamenti che arrivano con un timestamp inferiore o uguale a quello memorizzato vengono scartati, il che garantisce l'idempotenza (le scritture ripetute sono OK) e la commutatività (le scritture fuori servizio sono corrette Commutatività è a=b means b=a
, che in questo caso significa update1 seguito da update2 è come update2 seguito da update1)
Le scritture vengono inviate a tutti i cluster e, se alcuni nodi non rispondono a causa di un problema come la lentezza o la partizione, ci si aspetta che recuperino più tardi tramite un read-repair
, che assicura che il i valori convergono. La convergenza può essere raggiunta tramite 2 protocolli come ho detto sopra, propagare lo stato o gli aggiornamenti ad altre repliche. Credo che Roshi faccia il primo. Come parte dello read-repair
, lo stato di scambio delle repliche e poiché i dati sono conformi alla proprietà semi-lattice, convergono.
PS. I sistemi che utilizzano CRDT sono alla fine coerenti, cioè adottano AP (altamente disponibile e tollerante alle partizioni) nello CAP theorem.
Another excellent read on the subject.
Contrassegnare la risposta accettata se risponde alla tua domanda. –