o problema
Banco NoSQL nasceu de uma troca explícita: quem queria particionamento automático, replicação tolerante a falha e latência previsível abria mão de SQL e de transação. A conta funcionou por anos. O DynamoDB atende centenas de milhares de clientes e sustenta a Alexa, os sites da Amazon e todos os centros de distribuição da empresa; no Prime Day de 2022 os sistemas da Amazon fizeram trilhões de chamadas à API, com pico de 105,2 milhões de requisições por segundo e resposta em milissegundos de um dígito. Só que os clientes começaram a pedir ACID de verdade — atomicidade e isolamento sobre itens de partições diferentes, ou de tabelas diferentes — sem abrir mão de nada do que já tinham.
O caminho conhecido para atender esse pedido estraga as três propriedades. Transação delimitada por BEGIN e COMMIT deixa o aplicativo segurando recurso de servidor por tempo indeterminado, o que num serviço multi-tenant é veneno. Two-phase locking limita concorrência, cria deadlock e exige mecanismo de recuperação para soltar lock de cliente que morreu no meio. MVCC obrigaria a mudar o storage server, criar política de retenção de versão e cobrar o armazenamento extra do cliente. Nenhuma das três saídas era aceitável, e a equipe descobriu, trabalhando de trás para frente a partir dos casos de uso, que também não precisava delas: os clientes não pediam transação longa, e as cargas não eram muito contenciosas.
a ideia
A transação vira uma chamada só. TransactWriteItems e TransactGetItems recebem o conjunto inteiro de operações num request e ou passam ou falham na hora, sem bloquear. Com isso o sistema sabe, no instante em que recebe a transação, tudo o que ela vai tocar — e pode decidir sem manter estado aberto.
A ordem serial vem de timestamp, não de lock. O coordenador carimba a transação com o relógio dele e os storage nodes, cada um sozinho, verificam se conseguem executar a parte que lhes cabe naquela posição da ordem; quem não consegue, recusa. Como não há lock, não há deadlock nem recuperação de lock órfão. E o mais importante para a latência do caso comum: get e put avulsos continuam indo direto do request router para o storage node, sem passar por coordenador nenhum, e ainda assim ficam serializados com as transações.
como funciona
O request router autentica e encaminha a transação para uma frota de coordenadores — qualquer um pode assumir qualquer transação. O coordenador atribui o timestamp (os relógios da frota vêm do AWS time-sync, com desvio de poucos microssegundos), quebra a transação em operações por item e roda o protocolo de duas fases.
No prepare, cada storage node primário aceita a operação se as precondições passarem, se o item não violar restrições do sistema, se o timestamp da transação for maior que o da última escrita do item e se não houver outra transação já aceita escrevendo o mesmo item. As duas últimas condições são corretas mas restritivas demais, e o paper dedica uma seção inteira a relaxá-las — parte já implementada, parte planejada. Aceitos todos, o coordenador comita e cada node aplica a escrita e grava o timestamp da transação no item; item que só teve precondição checada também tem o timestamp atualizado. Item deletado não guarda timestamp, então a partição mantém um max delete timestamp único e compara contra ele quando chega prepare para item inexistente.
A transação de leitura usa duas fases sem escrever nada. Na primeira, o coordenador lê todos os itens e recebe de volta o valor e o LSN comitado de cada um; item sendo escrito por outra transação derruba a leitura. Na segunda, lê tudo de novo: LSN igual significa snapshot consistente, LSN diferente significa rejeição. Manter um read timestamp por item, como manda o esquema clássico, transformaria toda leitura numa escrita replicada — caro demais.
Falha de storage node não interessa ao protocolo, porque a metadata da transação está replicada no grupo e o novo primário a herda. Falha de coordenador interessa: cada transação e seu desfecho ficam num ledger, que é uma tabela DynamoDB, e recovery managers varrem o ledger em paralelo a partir de chaves aleatórias procurando transação parada para reatribuir. Coordenador declarado morto por engano não causa dano — escrita duplicada do mesmo item é ignorada pelo storage node.
o que isso custou
Custou latência mensurada e admitida. Uma escrita transacional de um único item leva cerca de 4x o tempo de um PutItem, por causa das duas fases mais a persistência no ledger; uma leitura transacional de um item leva pouco menos que 2x um GetItem, por causa das duas rodadas. Transação com mais operações fica mais lenta que transação pequena, mesmo com as operações em paralelo, porque a latência é a da operação mais lenta e transação grande tem mais chance de encontrar uma. No P99, a latência sobe com a carga por conta do garbage collection do Java nos coordenadores.
Custou cancelamento sob contenção. Com índice de contenção de 0,001 — mil itens quentes, 10 itens por transação — a taxa de cancelamento cresce junto com o throughput em todos os workloads. Sem MVCC, leitura e escrita conflitam de verdade: no workload misto com operações avulsas, o TransactGetItems foi a operação mais cancelada de todas, porque ele é otimista e qualquer escrita concorrente o derruba, enquanto o GetItem avulso não foi cancelado nenhuma vez.
E custou expressividade. Não existe transação longa nem interativa, por decisão de projeto. Precondição já verificada num prepare impede que uma escrita avulsa passe na frente da transação, e o storage node não tem como avaliar em geral se uma condição arbitrária seria violada — o paper aponta que dar esse tratamento a condições comuns, como limite numérico, reduziria bastante a rejeição em carga contenciosa, e deixa isso como trabalho futuro junto com a leitura transacional em rodada única.
onde isso aparece hoje
O desenho é a resposta pública da AWS a uma pergunta que o Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service deixara em aberto, e fecha o arco que começou no Dynamo, onde transação não estava sequer no cardápio.
Vale ler em contraste com o Spanner, que o próprio paper cita como o sistema que escolheu relógio preciso e MVCC — caminho oposto ao de atualizar item no lugar e aceitar que leitura conflite com escrita. Antes dele, o Megastore resolvera o problema restringindo a transação a um grupo de entidades, e o Percolator pagara o preço da transação distribuída em cima de um key-value aceitando latência alta. O ponto do DynamoDB é outro: a transação foi encaixada num serviço que já rodava em escala de dezenas de milhões de requisições por segundo, e o custo dela ficou confinado a quem a usa.