Сегодня в разговоре с одним знакомым всплыл следующий вопрос. В случае, если для дистрибуции ключей по нодам кластера используется типичная схема остатка от деления на количество серверов, какая доля ключей осуществляют миграцию, если один из серверов выводится из схемы? Интуитивным ответом является: “почти все” или “большинство”. Тем не менее, если вы любите тренировать мозг, то вот вам небольшая задачка имеющая приложение в web-программировании.
Формально говоря: при заданном количестве серверов $ N $ и хеширующей функции $ ƒ(x) $ обладающей выходным множеством с мощностью $ P $ ($ \log(P) $ бит, для crc32 $ P = 2^{32} $, для md5 $ P = 2^{128} $) какое количество ключей осуществит миграцию в случае, если серверов станет $ N-1 $, а для дистрибуции ключей используется значение $ f(x) % N $.
Ответом является формула описывающая зависимость количества мигрирующих ключей от изначального количества серверов и/или количества хранимых ключей.
Допущения: функция $ ƒ(x) $ имеет равномерное распределение на всем множестве входных значений, $ P $ несравнимо больше $ N $.
Удачи!