Conceitos
Árvores de Merkle para anti-entropia
Intuição
Imagine duas pessoas que mantêm, cada uma, uma cópia do mesmo enorme armário de arquivos, e você quer verificar se as cópias ainda são iguais. Você poderia comparar cada página, uma por uma, o que leva uma eternidade — ou poderia primeiro comparar apenas um resumo de uma página do armário inteiro. Se os resumos coincidem, acabou: tudo o que está por baixo também tem de coincidir. Se não coincidem, você abre só as gavetas em que os resumos divergem e vai aproximando o foco até encontrar as páginas exatas que diferem. Esse atalho — comparar primeiro um resumo e só aprofundar onde ele discorda — é a ideia inteira.
Como funciona
Uma árvore de Merkle transforma esse truque do resumo em uma árvore de hashes sobre a faixa de chaves de uma réplica: cada folha é o hash de uma pequena fatia de chaves, e cada nó pai é o hash dos hashes de seus filhos, até chegar a um único hash raiz que resume todo o conjunto de dados que a réplica guarda. Duas réplicas podem comparar primeiro apenas os hashes raiz — se coincidem, as faixas são comprovadamente idênticas e não há mais trabalho a fazer. Se as raízes diferem, cada lado desce um nível e compara os hashes dos filhos, descartando qualquer subárvore cujos hashes já coincidam e descendo apenas nos ramos que discordam, até que as chaves realmente divergentes sejam isoladas. É isso que o Dynamo executa como seu processo de anti-entropia em segundo plano entre pares de réplicas, separado do read repair, justamente para capturar a divergência em chaves que não são lidas com frequência suficiente para se curarem sozinhas pelo tráfego normal (divergência que os sloppy quorums e o hinted handoff tornam possível em primeiro lugar). A propriedade-chave é que o custo de detectar a divergência — banda e comparações — cresce com o quanto as réplicas realmente diferem, e não com o tamanho total do conjunto de dados, o que torna prático executá-lo continuamente em segundo plano em um cluster grande.
Na prática
Essa é a técnica padrão de anti-entropia em armazenamentos de consistência eventual no estilo Dynamo: é como uma réplica repara dados que ninguém lê há algum tempo, em vez de depender apenas do reparo no momento da leitura. Você recorreria a ela sempre que tiver muitas réplicas de grandes conjuntos de dados que podem se afastar silenciosamente (por hinted handoff, partições temporárias ou falhas) e comparar os conjuntos completos chave a chave fosse caro demais para rodar regularmente — as ferramentas de repair do Cassandra, descendentes da mesma linhagem, usam a mesma comparação de árvores de hash exatamente por esse motivo.
Use em um desenho
Pratique na escola de System Design os casos que dependem deste conceito.