Как устроен алгоритм Consistent Hashing (согласованное хеширование)? Зачем он нужен при проектировании распределённого кластера кэширования, например из 20 серверов Redis, и как он минимизирует количество перемещаемых ключей при добавлении или выходе из строя одного узла?

Ключи и узлы отображаются на хеш-кольцо; ключ обслуживает следующий узел по кольцу. При изменении состава переносится часть диапазонов, а не почти все ключи, как при hash(key) % N.

Виртуальные узлы помогают распределить нагрузку равномернее и учитывать мощность серверов. При идеальном равномерном распределении добавление двадцать первого узла переносит примерно 1/21 ключей. Потеря узла требует не только нового маршрута, но и реплики либо восстановления данных. Само согласованное хеширование не создаёт резервных копий. Redis Cluster использует фиксированные hash slots, поэтому его устройство нельзя буквально приравнивать к такому кольцу.