Вот, например, замечательный пост, где объясняется идея этого вида хэширования, в контексте статьи о Amazon Dynamo (ссылка на саму статью). Хорошо все рассказано - и всё равно не понял.
Но Интернет большоооой. Вот, наконец, пост, который смог мне объяснить эту простую идею.
Итак. Есть функция хэширования f(). У нее есть некоторая область значений (fmin, fmax). Сворачиваем ее в кольцо. Берем имеющиеся сервера (по которым нужно равномерно распределить ключи), у каждого своё имя (IP-адрес, например). Хэшируем имена серверов, получаем точки на кольце (эти точки разбивают кольцо на отрезки).
Теперь берем ключи, хэшируем их названия, получаем новые точки, которые распределяются по кольцу. На каком сервере будет размещен данный ключ? Берем ключ, его хэш - точка на кольце. Двигаемся по кольцу по часовой стрелке, находим первую точку, которая представляет сервер. На этом сервере и будет размещен данный ключ. При добавлении/удалении сервера будут перераспределено лишь небольшое количество ключей. В отличие от простейшей методике, где номер сервера определяется по формуле хэш(ключ) % количество_ключей.
В описанной схеме каждый ключ хранится на одном сервере, что небезопасно. Поэтому данный сервер может разреплицировать свои ключи по T следующим серверам в кольце.
Чтоб сделать распределение ключей еще более равномерным, используют концепцию виртуальных узлов - сервер на круге представляет не одна точка, а несколько. Например - точка, полученная хэшированием имени сервера и противоположная.
Комментариев нет:
Отправить комментарий