Qualquer conjunto de dados grande demais para uma única máquina precisa ser dividido, e a regra de divisão define o quanto crescer vai doer. A regra óbvia, hash(key) mod N, distribui as chaves por igual, mas amarra cada chave ao número de nós: mude N de 8 para 9 e quase todas as chaves se movem. Para um cache, isso significa uma partida a frio repentina; para um banco de dados, mover quase todos os dados.
O hashing consistente coloca nós e chaves no mesmo anel e entrega cada chave ao próximo nó no sentido horário. Ao adicionar um nó, ele assume apenas as chaves do seu novo arco, cerca de 1/N delas. Sistemas reais dão a cada máquina muitas posições virtuais no anel para que a carga continue equilibrada e as chaves de uma máquina perdida se distribuam entre muitas sobreviventes. O hashing não resolve uma única chave muito acessada; para isso é preciso replicá-la ou dividir a própria chave.
Escolha uma regra de particionamento que mantenha o rebalanceamento pequeno e a carga equilibrada.