Amazon Dynamo e Cassandra: o KV store sem líder

01 · CONTEXTO

O problema: nunca recusar uma escrita

A plataforma descrita no paper é uma loja online com centenas de serviços, rodando em dezenas de milhares de servidores espalhados por vários data centers. Nessa escala, sempre há componentes de servidor e de rede falhando, e o desenho trata a falha como o caso normal, não como exceção. O exemplo que guia tudo é o carrinho de compras: o serviço precisa sempre conseguir gravar e ler o carrinho, mesmo com discos falhando ou um data center fora do ar.

A maior parte desses serviços só grava e busca dados pela chave primária e não precisa das consultas complexas de um banco relacional. Para eles, o banco relacional era uma solução ineficiente: a funcionalidade extra exige hardware caro e pessoal muito qualificado, as tecnologias de replicação disponíveis tendem a escolher consistência em vez de disponibilidade e escalar horizontalmente com particionamento inteligente não era simples. O paper acrescenta que, na experiência da empresa, armazenamentos com garantias ACID costumam ter disponibilidade ruim.

A escolha de desenho decorre daí. Diante de falhas de rede, consistência forte e alta disponibilidade não podem ser obtidas ao mesmo tempo. Armazenamentos tradicionais podem rejeitar escritas quando não alcançam todas as réplicas ou a maioria delas. O Dynamo, ao contrário, escolhe ser eventualmente consistente: as atualizações chegam a todas as réplicas, mas só com o tempo. Ele quer ser sempre gravável, então empurra a resolução de conflitos para a leitura, de modo que nenhuma escrita seja rejeitada. Isso levanta duas perguntas, quando resolver e quem resolve, que as seções 04 em diante respondem.

O contrato é deliberadamente estreito. A interface é só por chave primária, os objetos são pequenos (em geral abaixo de 1 MB) e guardados como blobs, não há garantias de isolamento e só se atualiza uma chave por vez. O ambiente é assumido como confiável, sem autenticação nem autorização, e cada serviço roda a própria instância, com projeto inicial para até centenas de hosts.

A latência também faz parte do contrato. Em vez de média ou mediana, os acordos de nível de serviço da Amazon são medidos no percentil 99,9, porque clientes com mais histórico exigem mais processamento e ficam na ponta alta da distribuição, que uma média esconderia. Uma página da loja pode depender de mais de 150 serviços, então cada dependência precisa cumprir seu limite. Um SLA típico para quem usa o Dynamo é que 99,9% das leituras e escritas terminem em até 300 ms.

02 · PARTICIONAMENTO E REPLICAÇÃO

O anel e a lista de preferência

A primeira técnica é o particionamento por hashing consistente. A saída da função de hash é tratada como um círculo fixo, o anel, em que o maior valor volta ao menor. O Dynamo aplica MD5 à chave, obtendo um identificador de 128 bits, e cada nó recebe uma posição nesse espaço. Para achar o dono de uma chave, calcula-se a posição dela e anda-se no sentido horário até o primeiro nó com posição maior. Assim, cada nó responde pela região entre ele e o antecessor, e a chegada ou saída de um nó afeta só os vizinhos imediatos.

O hashing consistente básico tem dois problemas: a posição aleatória de cada nó gera distribuição desigual de dados e carga, e o algoritmo ignora diferenças de desempenho entre as máquinas. O Dynamo responde com nós virtuais: em vez de um ponto no círculo, cada servidor recebe vários, chamados tokens. Se um nó cai ou entra em manutenção, sua carga se espalha de forma equilibrada pelos demais; quando ele volta, assume uma parcela aproximadamente igual de cada um dos outros. E o número de nós virtuais de cada máquina pode seguir a sua capacidade. É isso que permite crescer um nó por vez.

Para durabilidade, cada item é copiado em N nós, com N configurado por instância. O nó dono da chave, o coordenador, grava localmente e replica nos N-1 sucessores no sentido horário. A lista de nós responsáveis por uma chave é a lista de preferência. Ela tem mais de N nós, para absorver falhas, e é montada pulando posições do anel até conter só máquinas físicas distintas, já que um nó com vários tokens poderia ocupar mais de uma posição. Qualquer nó consegue calcular a lista de qualquer chave, e a lista é construída para espalhar as réplicas por vários data centers.

Como o pedido chega ao coordenador? O cliente pode passar por um balanceador de carga genérico, que escolhe um nó pela informação de carga, ou usar uma biblioteca cliente que conhece as partições e fala direto com o coordenador. No primeiro caso, o pedido pode cair em qualquer nó do anel; se esse nó não estiver entre os primeiros da lista de preferência da chave, ele repassa a requisição ao primeiro deles. Para manter baixa a latência nos percentis altos, o Dynamo evita o roteamento em vários saltos: cada nó guarda informação suficiente para rotear direto, o que o paper chama de DHT de zero salto.

1. O serviço do carrinho chama put; o balanceador encaminha o pedido a um nó qualquer do anel, aqui o nó A.

2. O hash da chave vira uma posição no anel. Andando no sentido horário, o primeiro nó com posição maior é o B, o dono da chave.

3. O nó A não está entre os primeiros da lista de preferência dessa chave, então repassa a requisição ao coordenador B.

4. B grava a chave localmente e a replica nos sucessores no sentido horário, C e D, formando a lista de preferência no tamanho N escolhido para a instância.

03 · CONSISTÊNCIA AJUSTÁVEL E FALHAS TEMPORÁRIAS

R, W e o quorum frouxo

Para manter as réplicas coerentes, o Dynamo usa um protocolo parecido com o de sistemas de quorum com dois valores configuráveis: R é o mínimo de nós que precisam participar de uma leitura bem-sucedida e W é o mínimo para uma escrita. Com R + W > N obtém-se um sistema tipo quorum. A latência de uma operação é ditada pela mais lenta das R (ou W) réplicas consultadas; por isso R e W costumam ser menores que N, em troca de latência melhor.

No caminho de escrita, o coordenador gera o relógio de versão, grava a nova versão localmente e a envia aos N nós alcançáveis de maior posição na lista; se ao menos W-1 responderem, a escrita é considerada bem-sucedida. Na leitura, o coordenador pede todas as versões existentes a esses nós, espera R respostas e devolve o resultado; se houver versões sem relação causal, devolve todas elas.

Se usasse um quorum tradicional, o Dynamo ficaria indisponível durante falhas de servidor e partições de rede. Por isso ele adota um quorum frouxo: leituras e escritas usam os primeiros N nós saudáveis da lista de preferência, que podem não ser os primeiros N encontrados ao andar pelo anel. Se um nó preferido está fora do ar, a réplica que iria para ele segue para outro nó e leva nos metadados uma dica sobre o destinatário original. Quem recebe réplicas com dica as guarda numa base local separada, varrida periodicamente; ao detectar que o destinatário se recuperou, tenta entregar a réplica e, se conseguir, pode apagar a cópia sem reduzir o total de réplicas.

1. Durante uma escrita, o nó C está inacessível. Com um quorum tradicional a operação ficaria indisponível; o Dynamo não exige que os nós preferidos estejam todos acessíveis.

2. B usa os primeiros nós saudáveis da lista de preferência, pulando o que está fora; a réplica que iria para C segue para E, o próximo da lista depois de D.

3. A réplica entregue a E leva nos metadados uma dica de que o destinatário original era C. E a guarda numa base local separada, varrida periodicamente.

4. Quando E detecta que C se recuperou, tenta entregar a réplica a C. Concluída a entrega, E pode apagar a cópia sem reduzir o total de réplicas.

Há ressalvas. A entrega com dica funciona melhor quando a mudança de membros é baixa e as falhas são transitórias; réplicas com dica podem se perder antes de voltar ao dono, e para isso existe a sincronização em segundo plano, tratada na seção 05. E, na prática, a maioria dos serviços em produção usa W maior que 1, para atingir a durabilidade desejada. A configuração comum de (N, R, W) em várias instâncias é (3, 2, 2).

04 · VERSÕES E CONFLITOS

Relógios vetoriais e o carrinho

Como as escritas nunca são rejeitadas, o Dynamo trata cada modificação como uma nova versão imutável do dado e admite várias versões ao mesmo tempo. Na maioria das vezes a nova versão substitui as anteriores e o próprio sistema decide qual é a autoritativa, o que o paper chama de reconciliação sintática. Quando falhas se combinam com atualizações concorrentes, as versões se ramificam e o sistema não consegue reduzi-las; então o cliente precisa fazer a reconciliação semântica. O exemplo típico é mesclar versões do carrinho: assim, um adicionar ao carrinho nunca se perde, mas itens removidos podem reaparecer.

Para saber se duas versões estão em ramos paralelos ou têm ordem causal, o Dynamo usa relógios vetoriais. Um relógio vetorial é uma lista de pares (nó, contador), associada a cada versão de cada objeto. Se os contadores do primeiro relógio são menores ou iguais aos do segundo, o primeiro é ancestral do segundo e pode ser esquecido; caso contrário, as mudanças estão em conflito e exigem reconciliação. Ao atualizar um objeto, o cliente informa qual versão está atualizando, repassando o contexto obtido numa leitura anterior.

O exemplo do paper mostra o mecanismo. Um nó Sx trata a primeira escrita e cria a versão D1; a segunda, tratada pelo mesmo nó, cria D2. Depois, o mesmo cliente atualiza o objeto e outro servidor, Sy, trata a escrita, criando D3. Em seguida, um cliente diferente lê D2 e um terceiro servidor, Sz, grava D4. Um nó que conhece D3 e recebe D4 vê que não há relação causal entre eles, e as duas versões precisam ser mantidas e apresentadas ao cliente, numa leitura, para reconciliação.

Quando uma leitura encontra ramos que não podem ser reconciliados sintaticamente, o coordenador devolve os objetos das folhas, cada um com a informação de versão no contexto. Uma atualização feita com esse contexto é considerada a reconciliação, e os ramos se fundem numa nova versão. Se a última versão do carrinho não está disponível, o item é aplicado à versão mais antiga e as versões divergentes são reconciliadas depois.

1. O serviço do carrinho chama get. O coordenador pede todas as versões existentes aos nós alcançáveis da lista de preferência.

2. O coordenador espera apenas R respostas. As réplicas X e Y trazem versões sem relação causal, e ele devolve as duas ao serviço, com o contexto.

3. O serviço mescla as versões, que no carrinho é unir os itens, e grava de volta passando o contexto; a escrita vira uma nova versão que reúne os ramos.

4. Depois de responder, o coordenador aguarda um tempo curto pelas respostas pendentes. Se alguma trouxe versão antiga, como a da réplica Z, ele a atualiza: é o reparo na leitura.

5. Em segundo plano, as réplicas comparam árvores de Merkle por faixa de chaves e sincronizam apenas as chaves fora de sincronia.

Quem resolve os conflitos pode ser o armazenamento ou a aplicação. O armazenamento só dispõe de políticas simples, como última escrita vence; a aplicação conhece o esquema e escolhe o método que melhor serve ao cliente, como mesclar carrinhos. O paper descreve padrões de uso: reconciliação específica da lógica de negócio, que é um caso popular, como no carrinho; reconciliação por carimbo de tempo, em que vence o objeto com o maior timestamp físico, usada pelo serviço de sessão; e motor de leitura de alto desempenho, em que R costuma ser 1 e W igual a N.

Com que frequência as versões divergem? No serviço do carrinho, em 24 horas medidas em produção, 99,94% das requisições viram exatamente uma versão; 0,00057% viram duas, 0,00047% viram três e 0,00009% viram quatro. A experiência mostra que o aumento de versões divergentes vem do aumento de escritores concorrentes, em geral robôs e raramente pessoas, e não de falhas.

05 · SINCRONIZAÇÃO E MEMBROS

Reparo, anti-entropia e gossip

Há duas formas de corrigir réplicas desatualizadas. A primeira é o reparo na leitura: depois de responder, o coordenador espera um pouco pelas respostas pendentes e, se alguma veio com versão antiga, atualiza esses nós com a mais recente, o que alivia a anti-entropia dessa tarefa. A segunda é a anti-entropia, um protocolo de sincronização de réplicas que cobre ameaças à durabilidade como réplicas com dica que se perderam antes de voltar ao dono.

Para achar divergências rápido e transferir pouco dado, a anti-entropia usa árvores de Merkle: uma árvore de hashes em que as folhas são hashes dos valores de chaves individuais e cada nó pai é o hash dos filhos. Cada ramo pode ser verificado de forma independente, sem baixar a árvore nem o conjunto de dados inteiro. Cada nó mantém uma árvore por faixa de chaves que hospeda; dois nós trocam a raiz das faixas em comum e, se as raízes são iguais, nada precisa ser sincronizado. Se diferem, descem trocando hashes dos filhos até as folhas e identificam as chaves fora de sincronia. O custo é que, quando um nó entra ou sai, muitas faixas mudam e as árvores precisam ser recalculadas.

A pertença ao anel não é detectada automaticamente. Uma queda de nó raramente significa saída definitiva e não deve causar rebalanceamento nem reparo das réplicas, e um erro manual poderia iniciar nós novos por engano. Por isso a entrada e a saída de nós são operações explícitas, feitas por um administrador. Um protocolo de gossip propaga as mudanças e mantém uma visão eventualmente consistente da pertença: a cada segundo, cada nó contacta um par escolhido ao acaso e os dois reconciliam seus históricos. Os mapeamentos de tokens trafegam pelo mesmo canal, de modo que cada nó conhece as faixas dos pares e encaminha pedidos direto. Para evitar partições lógicas do anel, alguns nós funcionam como sementes (seeds), conhecidas por todos.

A detecção de falhas é local: um nó considera outro falho se ele não responde às suas mensagens, mesmo que responda a terceiros. Com tráfego constante de requisições, o nó percebe logo a falha, usa nós alternativos para as partições do suspeito e tenta de novo periodicamente. Versões iniciais usavam um detector descentralizado para manter uma visão global do estado de falhas, mas se concluiu que os métodos explícitos de entrada e saída tornam essa visão desnecessária.

O esquema de particionamento evoluiu em produção. A primeira estratégia, a implantada inicialmente, dava T tokens aleatórios a cada nó e, como eles eram escolhidos ao acaso, os intervalos variavam de tamanho. Ela trouxe problemas: na temporada de pico, a inicialização de um nó chegou a levar quase um dia; quando um nó entra ou sai, as árvores de Merkle das faixas afetadas precisam ser recalculadas; e não havia jeito fácil de tirar um snapshot do espaço de chaves, o que complicava o arquivamento.

A segunda estratégia dividia o espaço de hash em Q partições iguais, mantendo T tokens aleatórios por nó, e os tokens passavam a servir só para mapear posições a listas de nós. A vantagem era desacoplar particionamento e posicionamento das partições. Ela foi só uma configuração provisória na migração da primeira para a terceira.

A terceira estratégia também usa partições de tamanho igual, mas com Q/S tokens por nó, sendo S o número de nós. Frente à primeira, teve melhor eficiência de balanceamento e reduziu em três ordens de grandeza o metadado mantido em cada nó. Como as faixas são fixas, uma partição pode ser movida como unidade, transferindo o arquivo, o que simplifica inicialização e recuperação. A desvantagem é que mudar a pertença exige coordenação para preservar as propriedades da atribuição.

06 · RESULTADOS, LIMITES E CASSANDRA

O que se aprendeu e quem herdou a ideia

No uso em produção, o serviço do carrinho atendeu dezenas de milhões de requisições, com bem mais de 3 milhões de checkouts num único dia, e a plataforma escalou para cargas de pico extremas sem indisponibilidade na temporada de festas. Na época do paper, vários serviços internos usavam o Dynamo havia cerca de dois anos; as aplicações receberam respostas bem-sucedidas, sem timeout, para 99,9995% das requisições, e nenhum evento de perda de dados havia ocorrido.

O desempenho também foi trabalhado. A latência no percentil 99,9 fica em torno de 200 ms, uma ordem de grandeza acima das médias, e depende de carga, tamanho dos objetos e localidade. Para serviços que precisavam de mais, cada nó pode manter um buffer de objetos em memória, gravado periodicamente por uma thread. Mesmo com um buffer de mil objetos, a latência no percentil 99,9 caiu por um fator de 5 no pico. O esquema troca durabilidade por desempenho: uma queda do servidor pode perder escritas ainda no buffer. Para reduzir o risco, o coordenador escolhe uma das N réplicas para fazer uma escrita durável, e isso não afeta o desempenho porque ele espera só W respostas.

Outra otimização escolhe como coordenador da escrita o nó que respondeu mais rápido à leitura anterior, o que reduz a variabilidade e melhora o percentil 99,9. E há uma alternativa à coordenação no servidor: mover a máquina de estados para os clientes. O cliente baixa periodicamente a visão de pertença de um nó aleatório, e na medição de 24 horas isso reduziu a latência no percentil 99,9 em pelo menos 30 ms e a média em 3 a 4 ms. O custo é a frescura dessa visão: os clientes consultam um nó aleatório a cada 10 segundos e, no pior caso, veem pertença desatualizada por esse tempo.

O paper também aponta limites. O Dynamo adota um modelo de pertença completa, em que cada nó conhece os dados hospedados pelos pares. Isso funciona para algumas centenas de nós, mas escalar para dezenas de milhares não é trivial, porque o custo de manter a tabela de rotas cresce com o tamanho do sistema; extensões hierárquicas poderiam superar a limitação. Para novas aplicações, é preciso analisar cedo qual mecanismo de resolução de conflitos atende ao caso de negócio.

O Cassandra, do Facebook, é descrito em outro paper, que o apresenta como uma síntese de técnicas conhecidas e toma emprestado do Dynamo o termo lista de preferência. Foi projetado para a busca na caixa de entrada, um problema de vazão de escrita muito alta, na casa de bilhões de escritas por dia, em que replicar entre data centers era essencial para manter a latência de busca baixa. Ele herda o anel, mas diverge em pontos importantes, resumidos abaixo.