Continuamos a considerar exemplos do uso da replicação em cadeia. Definições básicas e arquiteturas foram fornecidas na primeira parte ; eu recomendo que você se familiarize com isso antes de ler a segunda parte.

Neste artigo, estudaremos os seguintes sistemas:

• O Hibari é um repositório distribuído e tolerante a falhas, escrito em erlang.
• HyperDex - armazenamento de valor-chave distribuído com suporte para pesquisa rápida por atributos secundários e pesquisa por intervalo.
• ChainReaction - Causal + consistência e georreplicação.
• Construindo um sistema distribuído sem usar processos adicionais de monitoramento / reconfiguração externos.

5. Hibari

O Hibari é um repositório KV tolerante a falhas distribuído, escrito em erlang. Utiliza replicação em cadeia (abordagem básica), ou seja, alcança consistência estrita. Nos testes, o Hibari mostra alto desempenho - vários milhares de atualizações por segundo são obtidas em servidores de duas unidades (solicitações de 1 KB)

5.1 Arquitetura

Hash consistente é usado para colocar dados. A base do armazenamento são blocos físicos e lógicos. O bloco físico é um servidor com Linux, talvez uma instância do EC2 e, em geral, a VM como um todo. Um bloco lógico é uma instância de armazenamento com a qual os principais processos do cluster funcionam e cada bloco é um nó em qualquer cadeia. No exemplo abaixo, o cluster é configurado com 2 blocos lógicos em cada bloco físico e com um comprimento de cadeia de 2. Observe que os nós da cadeia são "manchados" sobre os blocos físicos para aumentar a confiabilidade.

O processo mestre (veja a definição na primeira parte) é chamado de servidor Admin .

Os dados são armazenados em "tabelas", que são simplesmente divididas em espaços para nome, cada tabela é armazenada em pelo menos uma cadeia e cada cadeia armazena dados em apenas uma tabela.

O cliente Hibari recebe atualizações do servidor Admin com uma lista de todas as cabeças e cauda de todas as cadeias (e todas as tabelas). Assim, os clientes sabem imediatamente para qual nó lógico enviar a solicitação.

5.2 Hashing

Hibari usa um par $$$\ {T, K \}$ para determinar o nome da cadeia que armazena a chave $$$K$ na mesa $$$T$ : chave $$$K$ mapeado para o intervalo $$$[0,1, 1,0)$ (usando MD5), dividido em seções pelas quais uma cadeia é responsável. As seções podem ter larguras diferentes, dependendo do "peso" da corrente, por exemplo:



Assim, se alguns blocos físicos são muito poderosos, as cadeias localizadas nele podem receber seções mais largas (mais teclas cairão sobre eles).

6. HyperDex

O objetivo deste projeto era construir um armazenamento de valor-chave distribuído, que, diferentemente de outras soluções populares (BigTable, Cassandra, Dynamo), suporta uma pesquisa rápida por atributos secundários e pode executar rapidamente uma pesquisa por intervalo. Por exemplo, nos sistemas considerados anteriormente, para procurar todos os valores em um determinado intervalo, você precisa passar por todos os servidores, o que, obviamente, é inaceitável. O HyperDex resolve esse problema usando Hyperspace Hashing .

6.1 Arquitetura

A idéia do hash do hiperespaço é construir $$$n$ espaço tridimensional em que cada atributo corresponde a um eixo de coordenadas. Por exemplo, para objetos (nome, sobrenome, número de telefone), o espaço pode ser assim:



O hiperplano cinza passa por todas as chaves, onde sobrenome = Smith, amarelo - por todas as chaves, onde nome = John. A interseção desses planos forma uma resposta aos números de telefone da consulta de pesquisa de pessoas com o nome John e o sobrenome Smith. Portanto, o pedido de $$$k$ atributos retorna $$$(n-k)$ subespaço tridimensional.

O espaço de pesquisa é dividido em $$$n$ regiões disjuntas tridimensionais e cada região é atribuída a um único servidor. Um objeto com coordenadas de uma região é armazenado no servidor dessa região. Assim, um hash é construído entre objetos e servidores.

Uma consulta de pesquisa (por intervalo) determinará as regiões incluídas no hiperplano resultante e, portanto, reduzirá o número de servidores pesquisados ​​ao mínimo.

Há um problema com essa abordagem: o número de servidores necessários cresce exponencialmente a partir do número de atributos, ou seja, se atributos $$$k$ então você precisa $$$O (2 ^ k)$ servidores. Para resolver esse problema, o HyperDex aplica uma partição do hiperespaço em subespaços (com uma dimensão inferior) com, respectivamente, um subconjunto de atributos:

6.2 Replicação

Para garantir consistência estrita, os autores desenvolveram uma abordagem especial baseada na replicação em cadeia - encadeamento dependente de valor , em que cada nó subsequente é determinado por hash do atributo correspondente. Por exemplo, a chave $$$("John", "Smith")$ primeiro ele será dividido no espaço principal (obtemos a cadeia principal, também chamada líder de pontos ), depois o hash de$$ $ inline $ "John" $ inline $ para a coordenada no eixo correspondente e assim por diante. (Veja a imagem abaixo para um exemplo de atualização. $$$u_1$ )

Todas as atualizações passam por um líder de ponto, que solicita solicitações (linearizabilidade).



Se a atualização levar a uma alteração na região, primeiro a nova versão será gravada imediatamente após a antiga (consulte atualização $$$u_2$ ) e depois de receber o ACK da cauda, ​​o link para a versão antiga do servidor anterior será alterado. Para solicitações simultâneas (por exemplo, $$$u_2$ e $$$u_3$ ) não violou o líder do ponto de consistência que adiciona controle de versão e outras meta informações ao servidor, se recebidas $$$u_3$ antes $$$u_2$ pode determinar que o pedido está quebrado e você precisa esperar $$$u_2$ .

7. ChainReaction

É usado um modelo causal + convergência, que adiciona a condição de convergência livre de conflito à convergência causal (causal). Para atender à convergência causal, os metadados são adicionados a cada solicitação, o que indica as versões de todas as chaves causalmente dependentes. O ChainReaction permite a replicação geográfica em vários data centers e é um desenvolvimento adicional da ideia do CRAQ.

7.1 Arquitetura

A arquitetura do FAWN é usada com pequenas alterações - cada controlador de domínio consiste em servidores de dados - back-end (armazenamento de dados, replicação, forma um anel DHT) e proxies de cliente - front-end (envia uma solicitação para um nó específico). Cada chave é replicada para R nós consecutivos, formando uma cadeia. As solicitações de leitura são processadas pela cauda e gravadas pela cabeça.

7.2 Um data center

Observamos uma propriedade importante decorrente da replicação em cadeia - se o nó $$$k$ causal consistente com algumas operações do cliente, e todos os nós anteriores - também. Então, se a operação $$$Op$ foi visto pela última vez por nós no site $$$j$ , todos os dependentes causais (de $$$Op$ ) operações de leitura só podem ser executadas em nós da cabeça ao $$$j$ . Assim que $$$Op$ será executado na cauda - não haverá restrições de leitura. Indique as operações de gravação que foram executadas por cauda no controlador de domínio $$$d$ como DC-Write-Stable (d) .

Cada cliente armazena uma lista (metadados) de todas as chaves solicitadas pelo cliente no formato (chave, versão, chainIndex), em que chainIndex é a posição do nó na cadeia que respondeu à última solicitação da chave de chave. Os metadados são armazenados apenas para chaves que o cliente não está ciente se é DC-Write-Stable (d) ou não .

7.2.1 Operação de gravação

Observe que quando a operação se tornar DC-Write-Stable (d), nenhuma solicitação de leitura poderá ler as versões anteriores.

Para cada solicitação de gravação, uma lista de todas as chaves nas quais as operações de leitura foram executadas antes da adição da última operação de gravação. Assim que o proxy do cliente recebe a solicitação, ele executa leituras de bloqueio nas caudas de todas as chaves dos metadados (estamos aguardando confirmação da presença da mesma ou da versão mais recente, ou seja, atendemos à condição de consistência causal). Assim que as confirmações são recebidas, a solicitação de gravação é enviada ao chefe da cadeia correspondente.



Depois que o novo valor for armazenado em $$$k$ nós da cadeia, uma notificação é enviada ao cliente (com o índice do último nó). O cliente atualiza o chainIndex e remove os metadados das chaves enviadas, conforme ficou conhecido sobre eles que eles eram DC-Write-Stable (d). Paralelamente, a gravação continua ainda mais - propagação lenta . Assim, é dada prioridade para escrever operações no primeiro $$$k$ nós. Assim que o tail armazena a nova versão da chave, uma notificação é enviada ao cliente e transmitida a todos os nós da cadeia, para que eles marquem a chave como estável.

7.2.2 Operação de leitura

O proxy do cliente envia uma solicitação de leitura para $$$index: = rand (1, chainIndex)$ nó no circuito, enquanto distribui a carga. Em resposta, o nó envia o valor e a versão desse valor. A resposta é enviada ao cliente, enquanto:

• Se a versão for estável, o novo chainIndex será igual ao tamanho da cadeia.
• Se a versão for mais recente, o novo chainIndex = index.
• Caso contrário, chainIndex não será alterado.

7.2.3 Failover de nó

É quase completamente idêntico à abordagem básica, com algumas diferenças no fato de que, em alguns casos, o chainIndex no cliente se torna inválido - isso é facilmente determinado ao executar solicitações (não há chave nesta versão) e a solicitação é redirecionada ao chefe da cadeia para procurar o nó com a versão desejada.

7.3 Vários ( $$$N$ ) data centers (replicação geográfica)

Tomamos como base os algoritmos de uma arquitetura de servidor único e os adaptamos ao mínimo. Para iniciantes, em metadados, em vez de apenas valores version e chainIndex, precisamos de vetores versionados de N dimensões.

Definimos Global-Write-Stable de maneira semelhante ao DC-Write-Stable (d) - a operação de gravação é considerada Global-Write-Stable se for executada na cauda em todos os CDs.

Um novo componente aparece em cada controlador de domínio - remote_proxy , sua tarefa é receber / enviar atualizações de outros controladores de domínio.

7.3.1 Executando uma operação de gravação (no servidor $$$i$ )

O começo é semelhante a uma arquitetura de servidor único - executamos leituras de bloqueio, gravamos na primeira $$$k$ nós de uma corrente. Nesse momento, o proxy do cliente envia ao cliente um novo vetor chainIndex, onde zeros estão em toda parte, exceto a posição $$$i$ - existe um significado $$$k$ . Próximo - como de costume. Uma operação adicional no final - a atualização é enviada para remote_proxy, que acumula várias solicitações e envia tudo.

Dois problemas surgem aqui:

• Como garantir dependências entre diferentes atualizações provenientes de diferentes controladores de domínio?
  
  Cada remote_proxy armazena um vetor de versão local $$$rvp$ dimensões $$$N$ , que armazena o número de atualizações enviadas e recebidas e as envia em cada atualização. Portanto, ao receber uma atualização de outro controlador de domínio, o remote_proxy verifica os contadores e, se o contador local for menor, a operação será bloqueada até que a atualização correspondente seja recebida.
• Como fornecer dependências para esta operação em outros controladores de domínio?
  
  Isso é obtido usando um filtro Bloom. Ao executar operações de gravação / leitura a partir do proxy do cliente, além dos metadados, um filtro bloom também é enviado para cada chave (denominada filtros de resposta). Esses filtros são armazenados na lista AccessedObjects e, ao solicitar operações de gravação / leitura, os metadados também enviam chaves OR enviadas aos filtros (chamados de filtro de dependência). Da mesma forma, após a operação de gravação, os filtros correspondentes são excluídos. Ao enviar uma operação de gravação para outro controlador de domínio, também são enviados um filtro de dependência e um filtro de resposta para essa solicitação.
  
  Além disso, o controlador de domínio remoto, depois de receber todas essas informações, verifica se, se os bits definidos do filtro de resposta coincidem com os bits definidos de vários filtros de consulta, essas operações são potencialmente dependentes ocasionais. Potencialmente - porque um filtro de floração.

7.3.2 Operação de leitura

Da mesma forma que uma arquitetura de servidor único, ajustada para o uso do vetor chainIndex em vez de um escalar e a possibilidade de ausência de uma chave no controlador de domínio (porque as atualizações são assíncronas) - aguarde ou redirecione a solicitação para outro controlador de domínio.

7.3.3 Resolução de conflitos

Graças aos metadados, as operações dependentes de causalidade são sempre executadas na ordem correta (às vezes é necessário bloquear o processo para isso). Mas mudanças competitivas em diferentes CDs podem levar a conflitos. Para resolver essas situações, o Last Write Wins é usado, para o qual um par está presente em cada operação de atualização $$$(relógio (s)$ onde $$$c$ - horas de procuração, e $$$s$ - ID do DC.

7.3.4 Manipulando falhas do nó

Semelhante à arquitetura de servidor único.

8. Aproveitando o sharding no design de protocolos de replicação escalável

O objetivo do estudo é construir um sistema distribuído com shards e com replicação sem usar um processo mestre externo para reconfigurar / monitorar o cluster.

Nas principais abordagens atuais, os autores vêem as seguintes desvantagens:

Replicação:

• Primário / Backup - leva a uma discrepância no estado se o Primário tiver sido identificado por falha por engano.
• Interseção de quorum - pode levar a uma discrepância de estado durante a reconfiguração de cluster.

Consistência estrita:

• Os protocolos contam com algoritmos de votação majoritária (por exemplo, Paxos) quando necessário $$$2 * N + 1$ soltar nós $$$N$ nós.

Detecção de falhas do nó:

• P / B e CR implica a presença de detecção ideal de nós com falha com um modelo de falha-parada, o que é inatingível na prática e você deve escolher um intervalo de varredura adequado.
• O ZooKeeper está sujeito aos mesmos problemas - com um grande número de clientes, uma quantidade significativa de tempo (> 1 segundo) é necessária para que eles atualizem a configuração.

A abordagem proposta pelos autores, denominada replicação elástica , é desprovida dessas deficiências e possui as seguintes características:

• Consistência estrita.
• Para suportar a queda $$$N$ nós devem ter $$$N + 1$ nó.
• Reconfiguração sem perda de consistência.
• Não há necessidade de protocolos de consenso com base na votação majoritária.

Placa de resumo:

8.1 Organização de réplicas

Cada shard define uma sequência de configurações $$$\ mathcal {C} = C_1 :: C_2 :: C_3 \ dots$ por exemplo, a nova configuração não contém algum tipo de réplica caída $$$\ mathcal {C} = \ mathcal {C}: :( Réplicas \ setminus R_j)$

Cada elemento da sequência de configuração consiste em:

• réplicas - um conjunto de réplicas.
• ordenador - ID de uma réplica com uma função especial (veja abaixo).

Cada fragmento é representado por um conjunto de réplicas (por construção - $$$N$ ), ou seja, não dividimos os papéis de "fragmento" e "réplica".

Cada réplica armazena os seguintes dados:

• conf - ID da configuração à qual esta réplica pertence.
• ordenador - qual réplica é o ordenador dessa configuração.
• mode - modo de réplica, um dos três: $$$PENDENTE$ (todas as réplicas de $$$C_1$ ), $$$ATIVO$ (todas as réplicas de $$$C_1$ ), $$$IMMUTABLE$ .
• histórico - sequência de operações nos dados reais da réplica $$$op_1 :: op_2 :: \ dots$ (ou apenas uma condição).
• estável - o comprimento máximo do prefixo do histórico que é corrigido por esta réplica. Obviamente, $$$0 <= estável <= comprimento (histórico)$ .

O objetivo principal de um ordenador de réplicas é enviar solicitações para o restante das réplicas e manter o maior prefixo do histórico:

8.2 Organização de fragmentos

Os fragmentos são combinados em anéis chamados elásticos . Cada fragmento pertence a apenas um anel. O precursor de todo fragmento $$$X$ desempenha um papel especial - ele é um sequenciador para ele. O trabalho do seqüenciador é fornecer ao sucessor uma nova configuração em caso de falhas de réplica.


São necessárias duas condições:

• Cada faixa elástica possui pelo menos um fragmento e uma réplica em funcionamento.
• Cada faixa elástica possui pelo menos um fragmento, no qual todas as réplicas estão funcionando.

A segunda condição parece muito rigorosa, mas é equivalente à condição “tradicional” de que o processo mestre nunca cai.

8.3 Usando replicação em cadeia

Como você deve ter adivinhado, as réplicas são organizadas como uma cadeia (abordagem básica) - o ordenador será o chefe, com pequenas diferenças:

• Em caso de falha no CR, o nó é expulso da cadeia (e substituído por um novo), no ER - uma nova cadeia é criada.
• Os pedidos de leitura no CR são processados ​​por cauda, ​​no ER, eles passam por toda a cadeia da mesma maneira que os pedidos de gravação.

8.5 Reconfiguração em caso de falha

• As réplicas são monitoradas pelas réplicas do seu fragmento e pelas réplicas de um fragmento do seqüenciador.
• Assim que uma falha é detectada, as réplicas enviam um comando sobre isso.
• O seqüenciador envia uma nova configuração (sem uma réplica com falha).
• Uma nova réplica é criada que sincroniza seu estado com a faixa elástica.
• Depois disso, o seqüenciador envia a nova configuração com a réplica adicionada.

Referências

• Hibari
• hyperdex.orgerdex.org
• HyperDex: um armazenamento de valor-chave pesquisável e distribuído
• Reação em cadeia
• Aproveitando o sharding no design de protocolos de replicação escalável