Согласованное хеширование (consistent hashing)

Коротко: Согласованное хеширование размещает ключи и серверы на кольце. Ключ принадлежит следующему по часовой стрелке серверу. Когда сервер присоединяется или уходит, меняется лишь небольшая часть назначения.

Подробнее: При простом hash(key) % n почти все назначения меняются, когда меняется n. С кольцом в среднем перемещается лишь около K/n ключей. Виртуальные узлы (каждый сервер появляется на кольце несколько раз) обеспечивают равномерное распределение.

Подробности

• Кольцо: хеш-пространство 0 … 2^32−1, представленное как…

См. также: шардирование и партиционирование, протоколы сплетен