Conceitos
Hashing consistente
Intuição
Imagine um grande mostrador de relógio em que cada posição representa um possível dado, e cada máquina que você tem recebe um ou mais pontos nesse relógio. Para achar onde um dado mora, você parte da posição dele e anda no sentido horário até encontrar a primeira máquina — essa máquina é a dona do dado. Se você adiciona ou remove uma máquina, só os dados entre ela e a vizinha se movem; todo o resto do relógio continua exatamente onde estava. Esse é o truque inteiro: em vez de uma fórmula como "divida os dados pelo número de máquinas" (que reembaralha quase tudo no instante em que a quantidade de máquinas muda), você coloca dados e máquinas no mesmo anel e deixa a posição decidir a quem cada dado pertence.
Como funciona
O hashing consistente organiza os nós em um anel lógico, aplicando o hash do identificador de cada nó (ou, no caso do Dynamo, de vários identificadores) ao mesmo espaço de hash usado pelas chaves. Uma chave é atribuída ao primeiro nó alcançado ao andar no sentido horário a partir da posição do hash da própria chave. Como a propriedade depende apenas da posição no anel, adicionar ou remover um nó afeta somente as chaves que caem entre ele e seu predecessor imediato no anel — o restante do mapeamento não é perturbado, e é isso que mantém o custo de redistribuição proporcional ao tamanho da mudança, e não ao tamanho do conjunto de dados. O Dynamo constrói a replicação diretamente sobre isso: para uma dada chave, ele anda no sentido horário a partir da posição dela e replica nos N-1 nós físicos distintos seguintes que encontra, formando uma "lista de preferência" (preference list) que qualquer nó consegue calcular localmente, sem perguntar a um coordenador. Para evitar carga desigual causada por uma posição aleatória azarada quando há poucos nós físicos, o Dynamo dá a cada máquina física várias posições no anel (nós virtuais), o que suaviza a distribuição de carga e permite que máquinas mais potentes assumam proporcionalmente mais do anel ao manter mais tokens.
Na prática
Esse é o esquema de particionamento por baixo do Dynamo da Amazon, e ele foi levado quase direto para o Apache Cassandra (co-criado por um autor do Dynamo) e para o Riak e o Voldemort, todos precisando adicionar ou remover capacidade sem disparar um reembaralhamento completo dos dados. Recorra ao hashing consistente sempre que estiver construindo um armazenamento escalável horizontalmente em que nós entram e saem com frequência e você não pode se dar ao luxo de uma operação que toque o conjunto de dados inteiro toda vez que o tamanho do cluster muda; a variante com nós virtuais é o que você acrescenta quando percebe que a carga está desigual entre as máquinas físicas.
Use em um desenho
Pratique na escola de System Design os casos que dependem deste conceito.