2015-12-10 12 views
8

Sono un novizio nei sistemi distribuiti e sto cercando di ottenere una panoramica sul concetto di CRDT. mi rendo conto che ha tre notazioni:Che cos'è CRDT nei sistemi distribuiti?

Conflict-free Replicated Data Type 
Convergent Replicated Data Type 
Commutative Replicated Data Type 

Qualcuno può dare un esempio in cui usiamo CRDT nei sistemi distribuiti? Grazie mille in anticipo.

+0

Contrassegnare la risposta accettata se risponde alla tua domanda. –

risposta

8

CRDT sono ispirati al lavoro di Marc Shapiro. Nel calcolo distribuito, un tipo di dati replicati privo di conflitti (CRDT abbreviato) è un tipo di struttura dati appositamente progettata utilizzata per ottenere consistenza finale forte (SEC) e monotonicità (assenza di rollback). Esistono due percorsi alternativi per garantire SEC: CRDT basati sulle operazioni e CRDT basati sullo stato.

CRDT su repliche diverse possono divergere l'una dall'altra ma alla fine possono essere unite in modo sicuro fornendo un valore alla fine coerente. In altre parole, i CRDT hanno un metodo di fusione che è idempotente, commutativo e associativo.

Le due alternative sono equivalenti, poiché è possibile emulare l'altra, ma i CRDT basati sulle operazioni richiedono garanzie aggiuntive dal middleware di comunicazione. I CRDT vengono utilizzati per replicare i dati su più computer in una rete, eseguendo aggiornamenti senza la necessità di sincronizzazione remota. Ciò porterebbe a unire conflitti nei sistemi che utilizzano la convenzionale tecnologia di coerenza finale, ma i CRDT sono progettati in modo tale che i conflitti siano matematicamente impossibili. Sotto i vincoli del teorema CAP, forniscono le migliori garanzie di coerenza per le impostazioni disponibili/tolleranti alle partizioni (AP).

Alcuni esempi in cui vengono utilizzati

Riak è la più famosa libreria open source di CRDT di ed è utilizzato da Bet365 e League of Legends. Di seguito sono riportati alcuni link utili che supportano Riak.

1- Bet365 (Usi Erlang e Riak) http://www.erlang-factory.com/static/upload/media/1434558446558020erlanguserconference2015bet365michaelowen.pdf

2- League of Legends utilizza l'implementazione Riak CRDT per il suo sistema di chat in-game (che gestisce 7,5 milioni di utenti simultanei e 11.000 messaggi al secondo)

3- Roshi implementato da SoundCloud che supporta una LWW timestamp Set: -Blog messaggio: https://developers.soundcloud.com/blog/roshi-a-crdt-system-for-timestamped-events

1

Queste tre espansioni della sigla significano praticamente la stessa cosa.

Un CRDT è convergente se le stesse operazioni applicate in una sequenza diversa producono (converge) lo stesso risultato. Cioè, le operazioni possono essere commutate - è un RDT commutativo. La ragione per cui le operazioni possono essere applicate in una sequenza diversa e ottenere sempre lo stesso risultato è che le operazioni sono libere da conflitti.

Quindi CRDT significa la stessa cosa, a prescindere dalle tre espansioni che usi, anche se personalmente preferisco "Convergenza".

+0

Grazie mille @cliffordheath. Hai spiegato tutte e tre le terminologie in dettaglio. Ma puoi per favore fare un esempio per questo? –

+0

Il primo hit di Google per CRDT lo spiega in dettaglio, con esempi. Ho appena spiegato perché i nomi significano la stessa cosa. – cliffordheath

1

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.

Problemi correlati