Consistent hashing

Когда наступает пара масштабироваться, встает вопрос "как" делить пользовательские запросы между несколькими инстансами. Если у вас stateless сервисы, то от запроса к запросу одного и того же пользователя можно направлять на разные инстансы - никаких проблем нет.

Проблемы появляются, когда у вас есть какой-то state (например, кэш авторизаций пользователей). Ну ничего, можно приземлить пользователей на какой-то один инстанс, если взять его id по модулю количества этих инстансов (instance_id = user_id % instances_count - 1).
Но что, если вам требуется добавить один новый инстанс? Если мы оставим нашу формулу, то большинство клиентов сменит инстанс, что приведет к потере state (и, например, валу перезапросов на сервис авторизации).

Особый вид хэширования Consistent hashing служит для того, чтобы бОльшая часть пользователей (будут переназначены только user_id_count/instances_count ключей) осталась "жить" на том же инстансе при добавлении нового.

В статье объясняется принцип его работы с картинками на основе кольцевого массива.

https://medium.com/better-programming/load-balancers-and-consistent-hashing-in-6-minutes-b5fc460aea4e

#practices #medium #en