Seu serviço de carrinho escreve a cada clique e, em dezembro, não pode rejeitar nem uma única adição ao carrinho. No pico, um disco vai falhar, um switch de rack vai oscilar, talvez um data center saia da rede. Um único banco de dados primário transforma cada um desses eventos em uma indisponibilidade.
O artigo do Dynamo, da Amazon, de 2007, descreveu um store que continua aceitando escritas apesar de tudo isso; Cassandra e Riak KV tomaram emprestada a maior parte de suas ideias de clustering. Este post projeta um store no estilo Dynamo da API ao motor de armazenamento, compara sistemas reais e desenha o resultado.
Requisitos e API
A interface do Dynamo tem duas operações:
get(key) -> [value, ...], context
put(key, context, value) -> ok
get pode retornar versões conflitantes mais um contexto opaco; o próximo put o devolve para dizer quais versões ele substitui. Os requisitos:
- Sempre gravável, mesmo com nós ou links fora do ar.
- Latência de cauda previsível. O SLA de exemplo do artigo é de 300 ms para 99,9% das requisições em um pico de 500 requisições por segundo.
- Valores pequenos, chaves individuais: objetos geralmente abaixo de 1 MB, sem operações sobre várias chaves.
- Escala incremental, um nó por vez.
Dimensionamento, supondo valores de 1 KB e discos pela metade para folga de compactação: 1 bilhão de chaves são 1 TB, 3 TB com três cópias, então seis nós de 1 TB, como o anel do diagrama. Com 30.000 escritas por segundo, três cópias significam 90.000 escritas de réplica, ou 15.000 por nó.
CAP e PACELC em resumo
O CAP diz que, durante uma partição de rede, um store precisa recusar algumas requisições ou arriscar leituras desatualizadas; o Dynamo continua disponível. O PACELC de Daniel Abadi (2012) acrescenta que, sem partição, você ainda troca latência por consistência; ele classifica as configurações padrão de Dynamo, Cassandra e Riak como PA/EL.
Particionamento com anel de hash e nós virtuais
O Dynamo aplica MD5 a cada chave para obter uma posição de 128 bits em um anel, e a chave pertence ao primeiro nó no sentido horário. Quando um nó entra ou sai, apenas os intervalos vizinhos se movem, em vez de quase todas as chaves como com hash(key) % N; o diagrama de consistent hashing mostra como.
Uma posição por nó distribui os dados de forma desigual, então cada nó recebe muitas, chamadas de nós virtuais ou tokens. O Cassandra 5.0 vem com 16 tokens por nó; o anel do Riak tem 64 partições por padrão. Você abre mão de varreduras por intervalo: chaves vizinhas caem em nós diferentes, como explica o diagrama de sharding de banco de dados.
Replicação e listas de preferência
Cada chave vive em N nós: o coordenador (o primeiro nó no sentido horário) e os N − 1 nós físicos distintos seguintes. A lista de preferência da chave continua além deles, para que existam substitutos quando uma réplica está fora do ar. Distribua as réplicas entre domínios de falha: o Dynamo distribuía cada lista entre data centers, e a NetworkTopologyStrategy do Cassandra as distribui entre racks. Toda réplica aceita escritas, diferente das configurações baseadas em líder do diagrama de replicação de banco de dados.
Quóruns: R + W > N
O coordenador envia cada escrita a todas as N réplicas e responde após W confirmações; uma leitura responde após R respostas. Se R + W > N, qualquer conjunto de leitura e qualquer conjunto de escrita confirmada compartilham pelo menos um nó.
| N, R, W | R + W > N | O que você ganha | O que você paga |
|---|---|---|---|
| 3, 2, 2 | Sim | As leituras veem a última escrita confirmada; uma réplica pode falhar | Cada requisição espera a segunda resposta mais rápida |
| 3, 1, 3 | Sim | Leituras rápidas de qualquer réplica | As escritas esperam pelas três |
| 3, 1, 1 | Não | Menor latência, maior disponibilidade | As leituras podem estar desatualizadas |
| 5, 3, 3 | Sim | Duas réplicas podem falhar | Cinco cópias de cada valor |
A configuração comum no artigo do Dynamo era (3, 2, 2), e serviços com muita leitura, como o catálogo de produtos, usavam R = 1, W = N. O Cassandra define um nível de consistência por requisição, de ONE a ALL; QUORUM para leituras e escritas dá R + W > N.
Sobreposição não é linearizabilidade. Uma escrita que chega a uma réplica e depois falha pode aparecer em uma leitura e sumir na seguinte; o read repair bloqueante padrão do Cassandra evita isso nas leituras com quórum. Compare-and-set exige consenso, como nas lightweight transactions do Cassandra ou em um store baseado em Raft.
Conflitos: last write wins, vector clocks ou CRDTs
Escritas concorrentes por réplicas diferentes deixam duas versões. Três saídas:
| Estratégia | Como resolve | Pode perder atualizações? | Usada por |
|---|---|---|---|
| Last write wins | O maior timestamp vence | Sim, em silêncio; o desvio de relógio escolhe o vencedor | Cassandra, DynamoDB global tables, Riak se configurado |
| Vector clocks | Mantém as versões concorrentes; o cliente faz o merge | Não, mas todo cliente precisa fazer o merge | Dynamo, Riak (dotted version vectors) |
| CRDTs | Tipos de dados cujos merges sempre convergem | Não, para os tipos suportados | Counters, sets e maps do Riak |
Um vector clock é uma lista de pares (nó, contador). Uma versão cujos contadores são todos menores ou iguais aos de outra é ancestral e pode ser descartada; caso contrário, as duas são mantidas. O serviço de carrinho fazia o merge dos carrinhos conflitantes, então itens adicionados nunca se perdiam, embora os excluídos pudessem voltar. Os conflitos eram raros: em 24 horas, 99,94% das requisições de carrinho viram exatamente uma versão. Os CRDTs levam o merge para o próprio tipo de dados; editores colaborativos baseados em CRDTs aplicam a mesma ideia ao texto compartilhado.
Tratamento de falhas: hinted handoff, repair e gossip
Sloppy quorum e hinted handoff. O Dynamo usa os primeiros N nós saudáveis da lista de preferência: se C está fora do ar, D assume a cópia de C com uma dica e a devolve quando C se recupera. As escritas continuam funcionando, mas uma leitura de B e do C recuperado pode perder uma escrita que só A e D confirmaram. O Cassandra mantém os quóruns estritos: os hints contam para o nível de consistência apenas em ANY e param depois que um nó fica 3 horas fora do ar (max_hint_window).
Read repair e anti-entropy. Quando as respostas divergem, o coordenador grava a versão mais nova de volta nas réplicas desatualizadas. Para dados frios, as réplicas comparam árvores de Merkle por intervalo de chaves e sincronizam apenas os intervalos que diferem. A documentação do Cassandra recomenda executar nodetool repair em todo nó pelo menos a cada 7 dias: os tombstones são removidos após gc_grace_seconds (10 dias por padrão), e uma réplica sem reparo pode trazer de volta dados excluídos.
Gossip e detecção de falhas. A cada segundo, cada nó troca o estado de associação e de tokens com um par aleatório; nós seed conhecidos por todos impedem que o anel se divida. O detector phi accrual do Cassandra marca um par como fora do ar quando a suspeita ultrapassa phi_convict_threshold (padrão 8).
O caminho de escrita: commit log, memtable, SSTables
O motor de armazenamento do Cassandra é uma árvore log-structured merge (LSM) otimizada para escrita:
- Acrescentar a escrita ao commit log. Por padrão (
periodic), o Cassandra confirma na hora e sincroniza a cada 10 segundos, então uma falha pode perder essa janela. - Inseri-la na memtable, uma estrutura ordenada em memória.
- Descarregar uma memtable cheia em uma SSTable imutável e ordenada no disco.
- Compactar as SSTables em segundo plano, mantendo as versões mais novas e descartando tombstones expirados.
As leituras consultam a memtable e depois as SSTables, e um filtro de Bloom por SSTable pula arquivos que não podem conter a chave: com 10 bits por chave e 7 funções de hash, a taxa de falsos positivos é (1 − e^(−0,7))^7, cerca de 0,8%. A size-tiered compaction é o padrão; o Cassandra 5.0 recomenda sua estratégia unified para novas cargas.
Sistemas reais versus o artigo
| Dynamo (2007) | Amazon DynamoDB | Cassandra 5.0 | Riak KV | |
|---|---|---|---|---|
| Particionamento | Anel MD5, partições iguais | Intervalos que se dividem por tamanho ou tráfego | Anel Murmur3, 16 tokens por nó | Anel de 160 bits, 64 partições |
| Replicação | Sem líder, N por chave | 3 réplicas entre AZs, líder Multi-Paxos | Sem líder, por data center | Sem líder, n_val 3 |
| Consistência | Sloppy quorum | Eventual por padrão; leituras fortes a partir do líder | Nível de consistência por requisição | Sloppy quorum, pr e pw |
| Conflitos | Vector clocks | O líder ordena as escritas; last writer wins entre Regiões | Last write wins | Siblings ou CRDTs |
| Armazenamento | Berkeley DB, MySQL | B-tree mais write-ahead log | LSM tree | Bitcask, LevelDB |
O DynamoDB compartilha o nome, não o design: segundo seu artigo do USENIX de 2022, o líder da partição confirma uma escrita quando duas das três réplicas a registraram. As global tables usam last writer wins entre Regiões por padrão; no momento da escrita (novembro de 2026), também oferecem consistência forte multirregião em exatamente três Regiões.
O diagrama do key-value store no estilo Dynamo
Conteúdo do diagrama
- Node B
- Node A
- Node C
- Node F
- Node D
- Node E
- Cart service
- Inside every node: LSM write path
- Commit log
- Memtable
- SSTables
- put(k, ctx, v)
- replica 2: ack
- replica 3: no reply
- hinted write for C: ack
- hand off when C recovers
- then insert
- flush when full
- gossip
Como ler:
- O anel. Percorrendo o sentido horário a partir de hash(k), o ponto, obtém-se a lista de preferência de A a F.
- A escrita. O serviço de carrinho envia put(k, ctx, v) ao coordenador A, que replica para B e C.
- A falha. C está fora do ar, então D assume a cópia de C com uma dica (tracejado âmbar) e a devolve depois. Com W = 2, o put retorna quando A e B o têm.
- O gossip (pontilhado) corre entre pares aleatórios de nós.
- Os painéis listam N, R, W e o caminho de escrita de cada nó.
Como desenhar diagramas de key-value store com clareza
- Siga uma única chave. Marque seu hash, escreva sua lista de preferência e coloque N, R e W ao lado; um anel sem chave não explica nada.
- Desenhe a falha. Um nó vermelho e uma aresta de reserva tracejada explicam um sloppy quorum mais rápido que o texto.
- Mostre os domínios de falha: colora as réplicas por rack ou zona para que os revisores verifiquem que nenhuma cópia compartilha um mesmo domínio.
- Deixe o interior dos nós para um único quadro. O cluster vem primeiro.
Um erro comum: setas do cliente para cada réplica e nenhum coordenador, o que esconde quem decide que uma escrita teve sucesso. O método passo a passo de system design trata de layout e números.
Monte no Archboard
- Entre com Google ou GitHub e crie um diagrama.
- Adicione uma Elipse grande e cinza do pacote Básico para o anel de tokens.
- Posicione seis nós Servidor do pacote Rede no anel, de Node A a Node F no sentido horário. Pinte A e B de verde, C de vermelho e D de âmbar, e rotule seus papéis com notas de Texto do Básico.
- Adicione uma Elipse pequena no anel, logo antes de Node A, para hash(k), com um rótulo de Texto.
- Adicione um Contêiner do pacote Modelo C4 para o serviço de carrinho, com uma aresta put(k, ctx, v) para Node A.
- Desenhe as arestas: A para B contínua verde, A para C tracejada vermelha com ponta de seta em cruz, A para D e D para C tracejadas âmbar (escrita com dica, depois handoff) e uma aresta de gossip pontilhada entre F e E com uma nota de Texto.
- Adicione um bloco Markdown do pacote Básico com N, R, W e o cenário.
- Adicione uma Moldura do pacote Básico com três nós Componente do pacote Modelo C4, Commit log, Memtable e SSTables, ligados de cima para baixo, e uma nota de Texto sobre filtros de Bloom.
O exemplo usa 14 nós de diagrama e fica dentro do plano Free.
Perguntas frequentes
Como projetar um key-value store distribuído? Particione com consistent hashing, replique cada chave em N nós, ajuste R e W, escolha uma estratégia de conflitos, adicione hinted handoff e reparo anti-entropy, e execute uma LSM tree por nó.
O que significa R + W > N? Das N réplicas, uma escrita espera por W e uma leitura por R. Se R + W excede N, toda leitura alcança pelo menos uma réplica que tem a última escrita confirmada.
O DynamoDB se baseia no artigo do Dynamo? Só em parte: cada partição tem três réplicas com um líder Multi-Paxos e armazenamento B-tree, não sloppy quorums e vector clocks.
O que é hinted handoff? Outro nó guarda a escrita de uma réplica inalcançável com uma dica e a entrega quando a réplica volta. O Cassandra, por padrão, para de guardar hints para um nó após 3 horas fora do ar.
Devo usar last write wins ou vector clocks? Last write wins serve para dados em que perder uma atualização concorrente é aceitável, como sessões. Use vector clocks ou CRDTs quando cada atualização importa, como em carrinhos e counters.