Consistent hashing решает проблему перераспределения при добавлении/удалении шардов. В обычном хэшировании (hash % N) при изменении N почти все ключи переезжают. В consistent hashing шарды и ключи размещаются на кольце (0..2^32). Ключ попадает на ближайший шард по часовой стрелке. При добавлении нового шарда переезжает только часть ключей от соседнего шарда. Virtual nodes — каждый шард представлен множеством точек на кольце для равномерного распределения. Используется в DynamoDB, Cassandra, кэш-кластерах.

Что такое consistent hashing для шардинга?