Papers
Dynamo: Amazon's Highly Available Key-value Store
Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall, Werner Vogels · SOSP (21st ACM Symposium on Operating Systems Principles), 2007
O problema do sempre disponível
A plataforma da Amazon é construída a partir de muitos serviços independentes, e até um pequeno aumento de indisponibilidade em qualquer um deles — como o carrinho de compras — pode custar receita de verdade e corroer a confiança do cliente. Em meados dos anos 2000, a equipe de engenharia observou que a maioria dos serviços que armazenavam estado precisava apenas de um acesso simples chave-valor pela chave primária, e não do modelo relacional completo nem das consultas complexas que os bancos de dados tradicionais ofereciam. Ainda assim, os bancos que vinham usando continuavam impondo trade-offs que prejudicavam a disponibilidade: eram difíceis de escalar na horizontal, exigiam um particionamento manual cuidadoso e recusavam ou atrasavam operações quando algumas réplicas estavam inalcançáveis, tratando a consistência como mais importante do que conseguir responder. Os autores do paper argumentaram que, para muitos desses serviços com estado, sacrificar a consistência estrita em troca da capacidade de sempre aceitar uma escrita ou devolver uma leitura — mesmo que possivelmente desatualizada — era o trade-off certo, já que os clientes raramente eram prejudicados por uma pequena desatualização, mas sempre eram prejudicados por uma página de erro. Isso motivou um novo ponto de projeto: um armazenamento de dados incrementalmente escalável, em que adicionar nós para ter mais capacidade não exige grandes migrações, que trata a disponibilidade de escrita como o seu objetivo central de projeto e garante apenas que a consistência será alcançada eventualmente, e não de imediato.
Particionamento e replicação: o anel de hashing consistente
Para espalhar dados e carga por muitas máquinas sem exigir um coordenador central, o Dynamo organiza todos os nós em um anel lógico usando hashing consistente: a cada nó são atribuídas uma ou mais posições (tokens) no anel, e uma chave é armazenada a partir do primeiro nó cuja posição segue o valor de hash da chave no sentido horário. Esse esquema mantém baixos os custos de redistribuição quando o número de nós muda — adicionar ou remover uma máquina apenas desloca as chaves que pertencem aos seus vizinhos imediatos no anel, em vez de reembaralhar o conjunto de dados inteiro, o que fez de escalar a capacidade para cima ou para baixo um evento operacional, e não arquitetural. Para durabilidade e disponibilidade, cada chave não é armazenada em um único nó: o Dynamo anda no sentido horário a partir da posição da chave e a replica nos N-1 nós físicos distintos seguintes que encontra, formando o que o paper chama de lista de preferência (preference list) — a configuração padrão usava N=3, de modo que cada dado normalmente vivia em três máquinas diferentes. Como a lista de preferência é derivada puramente da posição no anel, qualquer nó consegue calcular, sem contatar mais ninguém, exatamente quais nós devem guardar uma cópia de uma dada chave, o que é essencial para um sistema em que nenhum nó é o coordenador oficial. O uso de nós virtuais (vários tokens por máquina física) também permitiu ao Dynamo balancear a carga de forma mais uniforme e deixar hardware heterogêneo assumir uma fatia proporcionalmente maior ou menor do anel.
Trocando consistência por disponibilidade: sloppy quorums, hinted handoff e relógios vetoriais
O Dynamo permite que os operadores ajustem dois números por leitura ou escrita: R, o número de réplicas que precisam responder a uma leitura, e W, o número que precisa confirmar uma escrita, dentre as N réplicas da lista de preferência de uma chave. Definir R+W maior que N dá uma sobreposição semelhante a um quorum, que reduz a chance de ler dados obsoletos, enquanto definir R+W igual ou menor que N favorece menor latência e maior disponibilidade ao custo de mais desatualização possível — o paper relata configurações típicas de produção de N=3, R=2, W=2. De forma crítica, o Dynamo não exige que todos os N nós preferenciais estejam alcançáveis para aceitar uma escrita: se um deles está fora do ar, a escrita é enviada a outro nó mais adiante no anel, marcada com uma "dica" (hint) que registra a qual nó ela realmente se destinava — uma técnica chamada hinted handoff — e esse nó encaminha os dados quando a réplica original se recupera. Esse "sloppy quorum" é o que permite ao Dynamo se dizer sempre gravável (always writeable) mesmo durante falhas ou partições de rede. O efeito colateral é que escritas concorrentes na mesma chave, feitas sem conhecimento uma da outra, podem criar versões divergentes. Em vez de escolher uma arbitrariamente, o Dynamo marca cada versão com um relógio vetorial (vector clock) — um conjunto de contadores por nó — para poder dizer se uma versão descende causalmente de outra ou se elas conflitam. As versões que ele não consegue ordenar causalmente são todas devolvidas à aplicação solicitante, que deve mesclá-las ou escolher entre elas (como, de forma famosa, mesclar dois carrinhos de compras divergentes unindo seus itens).
Mantendo a sincronia sem um mestre: read repair, árvores de Merkle e gossip
Como os sloppy quorums e o hinted handoff deixam as réplicas temporariamente fora de sincronia, o Dynamo precisa de mecanismos em segundo plano para trazê-las de volta ao acordo sem que nenhum coordenador central jamais seja envolvido. O mecanismo mais simples é o read repair: sempre que uma leitura toca várias réplicas e as versões delas discordam, o nó coordenador devolve a versão mais recente às réplicas defasadas como parte do tratamento daquela mesma leitura, de modo que as chaves populares tendem a se curar sozinhas rapidamente apenas com o tráfego normal. Para as chaves que não são lidas com frequência, o Dynamo também executa um processo de anti-entropia entre pares de réplicas usando árvores de Merkle — árvores de hash em que cada folha calcula o hash de uma pequena faixa de chaves e cada pai calcula o hash dos seus filhos, de modo que duas réplicas podem comparar apenas os hashes raiz primeiro e descer somente nos ramos que diferem, em vez de comparar cada chave individualmente. Isso mantém a banda e a computação necessárias para detectar divergência proporcionais à quantidade de diferença real entre as réplicas, e não ao tamanho do conjunto de dados. Por fim, o Dynamo não tem um registro central de quais nós estão vivos nem de quais nós possuem quais posições do anel: em vez disso, cada nó periodicamente propaga por gossip a sua visão do anel e da membership para um par escolhido ao acaso, e os dois mesclam suas visões. Combinado com um detector de falhas puramente local (um nó deixa de considerar um par vivo depois de tentativas de contato falhas suficientes, independentemente de qualquer votação global), isso permite que o quadro de membership inteiro convirja sem nenhum ponto único de coordenação ou de falha.
Legado: do Dynamo à geração NoSQL
O Dynamo nunca foi lançado pela Amazon como software externo — o paper de 2007 descrevia um sistema interno —, mas suas ideias se espalharam diretamente para os sistemas que vieram depois. Um dos coautores do próprio Dynamo, Avinash Lakshman, foi co-criar o Apache Cassandra, levando quase diretamente o particionamento por hashing consistente em anel e a membership baseada em gossip, combinando-os com um modelo de dados de famílias de colunas ao estilo do Bigtable. O Riak, construído pela Basho, e o Voldemort, construído no LinkedIn, também são amplamente descritos como implementações diretas do projeto do Dynamo: ambos usam anéis de hashing consistente, quorums ajustáveis no estilo N/R/W e relógios vetoriais (ou um mecanismo de causalidade semelhante) para detectar conflitos. Anos depois, a própria Amazon lançou um serviço gerenciado chamado literalmente DynamoDB, que manteve a filosofia de "sempre disponível e escalável na horizontal" do paper original ao mesmo tempo em que simplificou o modelo operacional ao longo do tempo, em vez de expor o ajuste de quorum diretamente a cada cliente. De modo mais amplo, o paper do Dynamo costuma ser citado junto com o paper do Bigtable, do Google, como uma das duas influências fundadoras do movimento NoSQL mais amplo do fim dos anos 2000 e dos anos 2010, porque juntos eles mostraram que abrir mão das garantias relacionais estritas e até da consistência estrita podia liberar uma escalabilidade horizontal e uma disponibilidade que a geração anterior de bancos relacionais tinha dificuldade em oferecer na escala da internet.
Veja as ideias em ação
Pratique na escola de System Design os desenhos que usam este paper.