shad-go/consistenthash/README.md
2023-04-18 14:48:06 +04:00

1.3 KiB
Raw Permalink Blame History

consistenthash

Реализуйте consistent hashing.

Consistent hashing - это хеш функция, которая отображает множество ключей на множество нод (процессов в кластере).

Пусть у вас есть N процессов. Можно было бы использовать функцию hash(key) % N, где hash - какая-то "хорошая" хеш функция. Но если в систему добавить еще один процесс, почти все ключи "переедут". Потому что hash(key) % N != hash(key) % (N + 1).

Такие "переезды" в распределённой системе могут вызывать недоступность или просто создавать большую нагрузку. Эту проблему решает consistent hashing. Он гарантирует, что при добавлении новой ноды, "переедут" только ~ 1/N ключей.

Для реализации используйте кольцо с виртуальными нодами, которое описано в CS168: Introduction and Consistent Hashing