Qual è la teoria alla base dell'implementazione di due HashMaps con mirroring in grado di accettare operazioni di scrittura? Ho bisogno di un broker per mediare scritture in conflitto?

5

Quindi immagina due HashMap che devono essere specchiati su due macchine diverse, A e B. Ogni volta che apporto una modifica alla macchina A, la macchina B la vede e viceversa. Il problema è:

Queste due mappe di hash devono rimanere sempre identiche. Quale strategia informatica possiamo usare per ottenere ciò? È possibile farlo senza un broker centralizzatore / master o una mappa hash?

    
posta Peter Mel 19.03.2016 - 18:21
fonte

3 risposte

2

Se ci sono più macchine coinvolte e la latenza della rete è diversa da zero, quindi mantenere i dati su tali macchine "sempre identici" è ovviamente impossibile.

Ma ci sono molte forme di coerenza più deboli ma utili che puoi ottenere ( Wikipedia ne ha anche un elenco ). Raggiungere queste forme di coerenza è un problema in gran parte ortogonale rispetto alla forma dei dati, a meno che i dati non abbiano una struttura che è possibile sfruttare come un ordinamento naturale. Dato che hai detto hashmap, presumo che non ci sia un ordine naturale / utile.

Quindi la parte della tua domanda a cui posso dare una risposta diretta è:

Is it possible to do it without a centralizing/master broker or hash map?

, è possibile ottenere alcune forme di coerenza utili senza una macchina "master" autorevole.

Un esempio semplice ma popolare sarebbe "coerenza finale" in cui la strategia di risoluzione del conflitto è "l'ultima scrittura vince". Diciamo che ogni ora o giù di lì le macchine si dicono a vicenda che cosa crede sia la modifica più recente al valore di foobar. Quando ciò accade, ogni macchina può vedere tutti i timestamp inviati dalle altre macchine, quindi senza alcuna ulteriore comunicazione ognuno può scegliere l'ultimo timestamp e usarlo come valore di foobar da quel momento in poi. Naturalmente, può richiedere fino a un'ora affinché una determinata operazione di scrittura venga riflessa su tutte le macchine, motivo per cui si chiama coerenza eventuale . La maggior parte dei sistemi sarà molto più intelligente di così (sarebbe stupido che un sito web scendesse per un minuto ogni ora), ma ciò dovrebbe almeno darti un'idea delle garanzie che puoi ottenere nella pratica.

    
risposta data 19.03.2016 - 18:56
fonte
2

Il mirroring richiesto per il tuo scopo deve essere un mirroring sincrono.

Questo tipo di strategia di replica viene generalmente ottenuta tramite meccanismo che implica transazioni ACID . Implica sempre una certa latenza quando si esegue un'operazione su una qualsiasi delle macchine.

Tipicamente, questo funzionerebbe in qualche modo come questo (semplificato):

  • La macchina A esegue un'operazione che richiede l'aggiornamento della mappa.
  • La macchina A imposta un blocco sulla sua mappa
  • Macchina A chiedi a B di impostare un blocco sulla sua mappa
  • La macchina A aggiorna la sua mappa
  • La macchina A informa B dell'aggiornamento richiesto
  • La macchina B aggiorna la sua mappa
  • La macchina B informa A che è finita e rilascia il blocco
  • La macchina A rilascia il lucchetto.

Questo approccio è decentralizzato. Nessun maestro Ma questo modo di procedere è molto pesante se ci sono molte scritture su entrambe le macchine: la tua mappa diventerà rapidamente un collo di bottiglia. Ed è estremamente complesso: devi affrontare tutto ciò che può andare storto, per esempio, sul nodo che si blocca mentre blocca il tavolo.

Un altro approccio potrebbe essere quello di rendere una macchina il master per questa tabella e replicare le modifiche all'altra. Così facendo si sostituisce il meccanismo di blocco e si aumenta la tolleranza di errore su ogni macchina, ma il master. In termini di prestazioni, avrai gli stessi svantaggi dell'approccio iniziale.

È possibile superare questi problemi di replica adottando una strategia partizionamento (ogni macchina è responsabile per una parte dei dati, da definire se il partizionamento orizzontale o verticale).

Un altro approccio, ancora più scalabile, è la sincronizzazione asincrona: ogni database è indipendente e di volta in volta si sincronizzano. Questo può funzionare insieme in modo efficiente se utilizzato in combinazione con il partizionamento orizzontale.

    
risposta data 19.03.2016 - 19:07
fonte
1

Fondamentalmente questo non è un problema che può essere risolto. Devi scegliere il tuo veleno.

Se richiedi che i mashmap siano sincronizzati in ogni momento non possono essere distribuiti e hai introdotto un singolo punto di errore.

Se riesci ad accettare che a volte sono un po 'fuori puoi arrivare molto vicino a quello che vuoi. La buona notizia è che possono sapere esattamente come divergono in modo da poter rispondere di conseguenza.

Si chiama replica master-master ed è un problema talmente difficile che la maggior parte dei dbs non la supportano molto bene, o del tutto. Un db che fa è CouchDB . Risolve questo difficile problema con un semplice modello in cui tutte le modifiche apportate a un documento (valore nella tua hashmap) sono versioni. Se un documento è stato aggiornato in entrambi i mirror in modo indipendente, entrambe le versioni vengono salvate come conflitti (uno viene scelto come predefinito) durante la replica. La possibilità di chiedere conflitti consente al client di correggere eventuali problemi di concorrenza dopo il fatto.

    
risposta data 20.03.2016 - 10:42
fonte

Leggi altre domande sui tag