Neste artigo, consideraremos a arquitetura de armazenamento KV simples e eficiente usando replicação em cadeia, que é ativamente investigada e usada com sucesso em vários sistemas.

Esta é a primeira metade de um artigo de replicação em cadeia. A segunda parte está aqui . A princípio, haverá um pouco de teoria, depois alguns exemplos de uso com várias modificações.

1. O objetivo é a declaração do problema e a comparação com o protocolo primário / de backup.
2. A replicação em cadeia é uma abordagem básica.
3. Replicação em cadeia - solicitações distribuídas.
4. FAWN: uma matriz rápida de nós Wimpy.

1. Introdução

1.1 Finalidade

Suponha que desejemos criar um simples armazenamento de valores-chave. O repositório terá uma interface muito mínima:

1. write (key, object): salva / atualiza o valor do valor por chave de tecla.
2. read (key): retorna o valor armazenado pela tecla key.

Também sabemos que o tamanho dos dados é relativamente pequeno (tudo se encaixa em um servidor, não há necessidade de sharding), mas pode haver muitas solicitações de gravação / leitura.

Nosso objetivo é suportar um grande número de solicitações ( alta taxa de transferência, HT ), alta disponibilidade ( HA ) e forte consistência ( SC ).

Em muitos sistemas, o SC é sacrificado por HA + HT, porque cumprir todas as três propriedades é uma tarefa não trivial. O Amazon Dynamo foi um grande salto em frente e gerou vários bancos de dados no estilo Dynamo, como Cassandra, Riak, Voldemort, etc.

1.2 Primário / Backup

Uma das abordagens mais comuns e simples para criar um sistema de armazenamento é usar a replicação primária / de backup.
Temos um servidor principal, vários servidores de backup e operações de gravação / leitura passam apenas pelo servidor principal.


Aqui a imagem mostra um dos protocolos de interação possíveis (espera principal pela confirmação de todos os backups antes de enviar a confirmação ao cliente), existem outras opções (não mutuamente exclusivas), por exemplo:

• O primário organiza estritamente solicitações de gravação.
• O primário envia confirmação assim que um dos backup responde com confirmação.
• Quorum desleixado e entrega sugerida.
• Etc.

Também é necessário um processo separado que monitore o estado do cluster (distribua a configuração aos participantes) e, quando o servidor host trava, faz (inicia) a eleição de um novo e também determina o que fazer no caso de um cérebro dividido. Novamente, dependendo dos requisitos, parte dessa lógica pode ser executada como parte do algoritmo de replicação, parte como um aplicativo de terceiros (por exemplo, um tratador para armazenar a configuração), etc.

Obviamente, mais cedo ou mais tarde, o desempenho da replicação primária / de backup será limitado por dois gargalos:

• Desempenho do servidor primário.
• Número de servidores de backup.

Quanto mais requisitos de confiabilidade / consistência forem apresentados a um cluster, mais rápido será esse momento.

Existem outras maneiras de alcançar nosso objetivo?

1.3 Replicação em cadeia

Em geral, a replicação em cadeia consiste em uma sequência (cadeia) de servidores, com funções especiais HEAD (o servidor com o qual o cliente se comunica) e TAIL (fim da cadeia, garantia SC). Uma cadeia possui pelo menos as seguintes propriedades:

1. Suporta queda para n - 1 servidores.
2. A velocidade de gravação não é significativamente diferente da velocidade do SC Primário / Backup.
3. A reconfiguração do cluster no caso de uma falha do HEAD ocorre muito mais rápido que o Primário, o restante dos servidores é comparativamente ou mais rápido que no Primário / Backup.

Um ponto pequeno, mas significativo - é necessária uma conexão FIFO confiável entre servidores.

Vamos examinar mais detalhadamente os vários métodos de construção da replicação em cadeia.

2. A abordagem básica

2.1 Algoritmo operacional

Os clientes enviam solicitações de gravação para o nó principal e as solicitações de leitura são enviadas para o nó final. A resposta sempre vem da cauda. O Head, após receber uma solicitação de mudança, calcula a mudança de estado necessária, aplica-a e envia-a para o próximo nó. Assim que a cauda a processa, uma resposta ACK é enviada de volta à cadeia. Obviamente, se uma solicitação de leitura retornar algum valor de x, ela será armazenada em todos os nós.

2.2 Protocolo de Replicação

Numeramos os servidores da cabeça à cauda e, em cada nó $$$i$armazenaremos adicionalmente:

• $$$Pending_i$- uma lista de solicitações recebidas pelo nó que ainda não foram processadas por cauda.
• $$$Sent_i$- uma lista de solicitações enviadas pelo servidor ao sucessor que ainda não foram processadas por cauda.
• $$$Histórico_i (chave)$- um histórico de alterações no valor da chave (você pode armazenar o histórico e apenas o valor total). Note que:

  $$

  $$History_j (chave) \ subseteq History_i (chave), \ forall j> i$$
  
  
• E também:

  $$

  $$Sent_i \ subseteq Pendente_i \\ Histórico_i (chave) = Histórico_ {i + 1} (chave) \ xícara Sent_i$$
  
  

2.3 Failover do servidor

Conforme mencionado na introdução, precisamos de algum tipo de processo mestre que:

• Identifica um servidor com falha.
• Notifica seu antecessor e sucessor de alterações no circuito.
• Se o servidor for de ponta a ponta, notificará os clientes sobre suas alterações.

Acreditamos que o processo mestre é estável e nunca falha. A escolha desse processo está além do escopo deste artigo.

A segunda suposição muito importante é que assumimos que os servidores são parados por falha:

• No caso de qualquer falha (interna), o servidor para de funcionar e não fornece um resultado incorreto.
• A falha do servidor é sempre determinada pelo processo mestre.

Vamos ver como um novo servidor é adicionado:
Teoricamente, um novo servidor pode ser adicionado a qualquer lugar da cadeia, adicionando à cauda parece ser o menos difícil - você só precisa copiar o status da cauda atual para o novo servidor, notificar o mestre sobre a alteração na cadeia e notificar a cauda antiga que as solicitações devem agora ser enviadas mais adiante.

Por fim, considere três possíveis cenários de falha:

2.3.1 Queda de cabeça
Basta remover o servidor da cadeia e atribuir o próximo novo cabeçalho. Somente a perda desses pedidos de $$$Pendente_ {head}$que não foram enviados mais - $$$Pendente_ {head} \ setminus Enviado_ {head}$

2.3.2 Cauda de queda
Removemos o servidor da cadeia e atribuímos o anterior à nova cauda, ​​antes que $$$Sent_ {tail - 1}$(todas essas operações são marcadas como cauda processada), respectivamente $$$Pendente_ {tail - 1}$diminui.

2.3.3 Nó intermediário em queda $$$k$
O assistente informa os nós $$$k-1$e $$$k + 1$sobre reordenar em uma cadeia.
Possível perda $$$Sent_ {k-1}$se o nó $$$k$Não consegui enviá-los ainda mais ao meu sucessor, portanto, depois de excluir o nó $$$k$da cadeia a primeira coisa é enviada novamente $$$Enviado_ {k - 1}$e somente depois desse nó $$$k - 1$continua a processar novos pedidos.

2.4 Comparação com o backup / protocolo primário

• Na replicação em cadeia, apenas um servidor (cauda) está envolvido na execução das solicitações de leitura e fornece uma resposta imediatamente, enquanto no P / B primário, pode esperar pela confirmação da conclusão das solicitações de gravação.
• Nas duas abordagens, a solicitação de gravação é executada em todos os servidores, o P / B é mais rápido devido à execução paralela.

Atrasos na replicação da cadeia de falhas:

• Cabeça: a execução das solicitações de leitura não é interrompida, as solicitações de gravação são atrasadas em 2 mensagens - do mestre para todos os servidores sobre o novo cabeçote e do mestre para todos os clientes sobre o novo cabeçote.
• Servidor intermediário: solicitações de leitura não são interrompidas. Solicitações de gravação podem ser atrasadas no tempo de execução $$$Sent_i$Não há perdas de atualização.
• Tail: Atraso nos pedidos de leitura e gravação de duas mensagens - notificação $$$cauda - 1$sobre a nova cauda e alertar os clientes sobre a nova cauda.

Atrasos P / B com falha:

• Primário: atraso de 5 mensagens para selecionar um novo estado primário e de sincronização.
• Backup: não há atrasos de leitura se não houver solicitações de gravação. Quando uma solicitação de gravação é exibida, é possível um atraso de 1 mensagem.

Como você pode ver, a pior falha de cauda para replicação em cadeia é mais rápida que a pior para P / B (Primária).

Os autores dessa abordagem realizaram testes de carga, que mostraram desempenho comparável ao do protocolo P / B.

3. Consultas distribuídas (replicação em cadeia com consultas distribuídas - CRAQ)

A abordagem básica tem uma óbvia fraqueza - cauda, ​​que lida com todos os pedidos de leitura. Isso pode levar a dois problemas:

• A cauda se torna ponto de acesso, ou seja, um servidor que lida com muito mais solicitações do que qualquer outro nó.
• Ao colocar uma cadeia em vários datacenters, a cauda pode estar muito distante, o que atrasará as solicitações de gravação.

A idéia do CRAQ é bastante simples - deixe que as solicitações de leitura cheguem a todos os servidores, exceto a cauda, ​​e para garantir consistência, armazenaremos o vetor de versões de objetos para solicitações de gravação e, em caso de ambiguidade, os nós farão uma solicitação para obter a última versão fixa.

3.1 CRAQ

Formalizamos a arquitetura CRAQ:
Cada nó, exceto a cauda, ​​processa solicitações de leitura e retorna uma resposta, e head retorna uma resposta das solicitações de gravação (compare com a abordagem básica).


Em cada nó que não é de cauda, ​​várias versões do mesmo objeto podem ser armazenadas e as versões formam uma sequência estritamente monotônica. Para cada versão, um atributo adicional é adicionado "limpo" ou "sujo". Inicialmente, todas as versões estão limpas.

Assim que o nó recebe uma solicitação de gravação, ele adiciona a versão recebida à lista de versões e, em seguida:

• Se o nó é cauda, ​​marca a versão como limpa, neste momento a versão é considerada fixa e envia uma confirmação de volta para a cadeia.
• Caso contrário, ele marca a versão como suja e envia a solicitação mais adiante na cadeia.

Assim que o nó recebe confirmação do sucessor, ele marca a versão como limpa e exclui todas as versões anteriores.

Assim que o nó receber uma solicitação de leitura:

• Se a última versão do objeto conhecida pelo nó estiver limpa, ela retornará.
• Caso contrário, ele faz um pedido para obter a última versão fixa do objeto, que ele retorna ao cliente. (Por construção, essa versão estará sempre no nó).

Para aplicativos com predominância de solicitações de leitura, o desempenho do CRAQ aumenta linearmente com o crescimento de nós ; no caso de predominância de solicitações de gravação, o desempenho não será pior que o da abordagem básica.

O CRAQ pode estar localizado em um ou em vários data centers. Isso permite que os clientes selecionem os nós mais próximos para aumentar a velocidade das solicitações de leitura.

3.2 Consistência no CRAQ

O CRAQ fornece uma consistência forte, exceto em um caso: quando o nó recebe a última versão confirmada da cauda, ​​a cauda pode confirmar a nova versão antes que o nó responda ao cliente. Nessa situação, o CRAQ fornece leitura monótona (as solicitações de leitura sequencial não serão coisa do passado, mas podem retornar dados antigos) em toda a cadeia .

Consistência fraca também é possível:

• Consistência eventual: o nó não solicitará a versão confirmada mais recente da cauda. Isso interromperá a leitura monótona em toda a cadeia, mas manterá a leitura monótona no mesmo nó . Além disso, ele pode suportar a tolerância de particionamento de rede .
• Consistência Eventual Limitada: retorne uma versão suja apenas até um determinado ponto. Por exemplo, a diferença entre as versões suja e limpa não deve exceder N revisões. Ou um limite de tempo.

3.3 Failover do servidor

Semelhante à abordagem básica.

3.4 Opcional

O CRAQ possui um recurso interessante - você pode usar multicast durante a operação de gravação. Suponha que o chefe envie a alteração com um multicast e envie para a cadeia apenas algum identificador para esse evento. Se a atualização em si não tiver chegado ao nó, ela poderá esperar e recebê-la do próximo nó quando o Tail enviar uma mensagem de confirmação da alteração. Da mesma forma, a cauda pode enviar a confirmação da fixação com multicast.

4. FAWN: uma matriz rápida de nós Wimpy

Um estudo muito interessante, não diretamente relacionado ao tópico deste artigo, mas serve como um exemplo do uso da replicação em cadeia.

Os armazenamentos de valores-chave de alto desempenho (Dynamo, memcached, Voldemort) têm características comuns - exigem E / S, um mínimo de computação, acesso independente paralelo a chaves aleatórias em grandes quantidades e valores pequenos de chaves de até 1Kb.

Servidores com HDDs não são adequados para esses clusters devido à longa operação de busca (tempo de acesso aleatório), e os servidores com um grande número de DRAM consomem uma quantidade surpreendentemente grande de energia - 2 GB de DRAM é equivalente a 1 TB de HDD.

A construção de um cluster (largura de banda) eficaz com consumo mínimo de energia é o objetivo do estudo original. 50% do custo do servidor por três anos são custos de eletricidade e os modos modernos de economia de energia não são tão eficazes quanto são anunciados - em testes com carga de 20%, o consumo da CPU permaneceu em 50%, além de outros componentes do servidor não possuírem modos de economia de energia ( DRAM, por exemplo, já funciona no mínimo). É importante observar que nesses clusters a diferença entre a CPU e a E / S aumenta - uma CPU poderosa é forçada a aguardar a conclusão da operação de E / S.

4.1 Arquitetura

O cluster FAWN é construído em servidores antigos por US $ 250 (preços de 2009), com uma CPU integrada de 500 MHz, 512 MB de RAM, SSD de 32 GB. Se você estiver familiarizado com a arquitetura do Amazon Dynamo ou com hash consistente, estará familiarizado com a arquitetura FAWN:

1. Cada servidor físico contém vários nós virtuais, cada um com seu próprio VID.
2. Os VIDs formam um anel, cada VID é responsável por um intervalo "atrás de si" (por exemplo, A1 é responsável por chaves no intervalo R1).
3. Para aumentar a confiabilidade, os dados são replicados para R dos seguintes nós no sentido horário. (por exemplo, com R = 2, a chave em A1 é replicada para B1 e C1), para obter replicação em cadeia (abordagem básica).
4. As solicitações de leitura vão para a cadeia de cauda, ​​ou seja, A leitura da chave de A1 irá para C1.
5. Os pedidos de gravação vão para a cadeia principal e vão até o fim.

O mapa do servidor é armazenado em um cluster de servidores front-end, cada um dos quais é responsável por sua lista VID específica e pode redirecionar a solicitação para outro servidor front-end.

4.2 Resultados do teste

No teste de carga, o FAWN atinge um QPS (consultas por segundo) de 90% do QPS em uma unidade flash de leitura aleatória.

A tabela a seguir compara o Custo total de propriedade (TCO) de várias configurações, onde a base para o Traditional é um servidor de US $ 1000 com consumo de 200 W (preços de 2009):

Assim, se:

• Big data, poucas consultas: FAWN + 2Tb 7200 RPM
• Uma pequena quantidade de dados, muitas solicitações: FAWN + 2GB DRAM
• Valores médios: FAWN + SSD de 32 GB

Referências

• Replicação em cadeia para suportar alta taxa de transferência e disponibilidade
• Armazenamento de objetos no CRAQ: replicação em cadeia de alto rendimento para cargas de trabalho com leitura principalmente
• FAWN: Uma matriz rápida de nós Wimpy