Qual é a teoria por trás da implementação de dois HashMaps espelhados que podem aceitar operações de gravação? Preciso de um corretor para mediar as gravações conflitantes?

5

Portanto, imagine dois HashMaps que precisam ser espelhados em duas máquinas diferentes, A e B. Sempre que faço uma modificação na máquina A, a máquina B a vê e vice-versa. Problema é:

Esses dois mapas de hash precisam permanecer sempre idênticos. Qual estratégia de ciência da computação podemos usar para realizar isso? É possível fazê-lo sem um broker centralizador / mestre ou mapa de hash?

    
por Peter Mel 19.03.2016 / 18:21
fonte

3 respostas

2

Se houver várias máquinas envolvidas e a latência da rede for diferente de zero, manter os dados nessas máquinas "sempre idênticos" é obviamente impossível.

Mas há muitas formas mais frágeis, porém úteis, de consistência que você pode alcançar ( Wikipedia até tem uma lista delas ). Atingir essas formas de consistência é um problema amplamente ortogonal ao formato dos dados, a menos que os dados tenham alguma estrutura que você possa explorar, como uma ordenação natural. Como você disse hashmaps, assumirei que não há ordenação natural / útil.

Então, a parte da sua pergunta que eu posso dar um direto e uma resposta é:

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

Sim , é possível obter algumas formas úteis de consistência sem uma máquina "mestre" com autoridade.

Um exemplo simples, mas popular, seria "consistência eventual", em que a estratégia de resolução de conflitos é "última gravação vence". Digamos que a cada hora suas máquinas digam umas às outras o que acreditam ser a mudança mais recente para o valor de foobar. Quando isso acontece, cada máquina pode ver todos os timestamps enviados pelas outras máquinas, então, sem qualquer comunicação adicional, cada um pode escolher o último timestamp e usá-lo como o valor de foobar a partir de então. É claro que pode levar até uma hora para que uma determinada operação de gravação seja refletida em todas as máquinas, e é por isso que ela é chamada de consistência eventual . A maioria dos sistemas será muito mais inteligente do que isso (seria estúpido que um site diminuísse por um minuto a cada hora), mas isso deveria ao menos lhe dar uma idéia de quais tipos de garantias você pode obter na prática.

    
por 19.03.2016 / 18:56
fonte
2

O espelhamento que é necessário para o seu propósito deve ser um espelhamento síncrono.

Esse tipo de estratégia de replicação geralmente é obtida por meio do mecanismo que implica transações ACID . Isso sempre implica uma certa latência ao fazer uma operação em qualquer uma das máquinas.

Normalmente, isso funciona da mesma forma (simplificado):

  • A máquina A executa uma operação que requer atualização do mapa.
  • A máquina A define um bloqueio em seu mapa
  • A máquina A pede a B para definir um bloqueio no seu mapa
  • A máquina A atualiza seu mapa
  • A máquina A informa B da atualização necessária
  • A máquina B atualiza seu mapa
  • A Máquina B informa A que terminou e libera o bloqueio
  • A máquina A libera o bloqueio.

Essa abordagem é descentralizada. Sem mestre. Mas essa maneira de proceder é muito pesada se houver muitas gravações nas duas máquinas: seu mapa rapidamente se tornará um gargalo. E é extremamente complexo: você tem que resolver tudo o que pode dar errado, por exemplo, no nó que iria travar enquanto ele trancava a mesa.

Outra abordagem poderia ser tornar uma máquina o mestre para essa tabela e replicar as alterações na outra. Fazer isso substitui o mecanismo de travamento e aumenta a tolerância a falhas em todas as máquinas, exceto no mestre. Em termos de desempenho, você terá as mesmas desvantagens que a abordagem inicial.

Você pode superar esses problemas de replicação adotando uma estratégia de particionamento (cada máquina é responsável por alguma parte dos dados, a ser definida se o particionamento horizontal ou vertical).

Outra abordagem, ainda mais escalável, é ter sincronização assíncrona: cada banco de dados é independente e, de tempos em tempos, eles são sincronizados. Isso pode trabalhar em conjunto de forma muito eficiente se usado em combinação com o particionamento horizontal.

    
por 19.03.2016 / 19:07
fonte
1

Fundamentalmente, isso não é um problema que pode ser resolvido. Você precisa escolher o seu veneno.

Se você precisar que os mashmaps sejam sincronizados o tempo todo, eles não poderão ser distribuídos e você terá introduzido um único ponto de falha.

Se você pode aceitar que às vezes eles estão um pouco fora, você pode chegar muito perto do que você quer. A boa notícia é saber exatamente como eles divergem para que você possa responder de acordo.

Isso é chamado de replicação mestre-mestre e é um problema tão difícil que a maioria dos dbs não o suporta muito bem ou de todo. Um banco de dados que faz é CouchDB . Ele resolve esse problema difícil com um modelo simples em que todas as alterações em um documento (valor em seu hashmap) são versionadas. Se um documento foi atualizado em ambos os espelhos independentemente, ambas as versões são salvas como conflitos (uma é escolhida como padrão) durante a replicação. A capacidade de solicitar conflitos permite que o cliente corrija quaisquer problemas de simultaneidade após o fato.

    
por 20.03.2016 / 10:42
fonte