Равномерное распределение данных

При кластеризации становится актуальным вопрос распределения ключей: как наиболее эффективным образом распределить ключи по серверам (шардинг/решардинг). Для этого необходимо определить функцию распределения ключей, которая по ключу возвращает номер сервера, на котором он должен храниться (или номера серверов, если хранение происходит с избыточностью).

Исторически первой функцией распределения была функция модуля:

номер_сервера = crc32(ключ) % количество_серверов

Такая функция обеспечивает равномерное распределение ключей по серверам, однако проблемы возникают при переконфигурировании кластера: изменение количества серверов приводит к перемещению значительной части ключей по серверам, что эквивалентно потере значительной части ключей.

Consistent hashing

Альтернативой для выше описанной функции является механизм консистентного хэширования, который при переконфигурации кластера сохраняет положение ключей по серверам. Этот подход например был реализован в клиентах memcached впервые разработчиками сервиса Last.fm в апреле 2007 года.

Суть алгоритма заключается в следующем: мы рассматриваем набор целых чисел от 0 до 2³², «закручивая» числовую ось в кольцо (склеиваем 0 и 2³²). Каждому сервера из пула memcached-серверов мы сопоставляем число на кольце (рисунок слева, сервера A, B и C). Ключ хэшируется в число в том же диапазоне (на рисунке – синие точки 1-4), в качестве сервера для хранения ключа мы выбираем сервер в точке, ближайшей к точке ключа в направлении по часовой стрелке. Если сервер удаляется из пула или добавляется в пул, на оси появляется или исчезает точка сервера, в результате чего лишь часть ключей перемещается на другой сервер. На рисунке 2 справа показана ситуация, когда сервер C был удалён из пула серверов и добавлен новый сервер D. Легко заметить, что ключи 1 и 2 не поменяли привязки к серверам, а ключи 3 и 4 переместились на другие сервера. На самом деле одному серверу ставится в соответствие 100-200 точек на оси (пропорционально его весу в пуле), что улучшает равномерность распределения ключей по серверам в случае изменения их конфигурации.

Простой пример

Разберем все на простом примере, без учета значения 2³² и без учета веса серверов, предварительно договорившись, что наша функция crc32 возвращает указанные ниже значения (это нужно для наглядности и понимания). Итак, имеем 3 сервера:

Как мы видим, получились некие цепочки: 0-10, 10-20, 20-30.

Рассмотрим ситуацию, когда все сервера доступны

Рассмотрим ситуацию, когда сервер 2 недоступен

Рассмотрим ситуацию, когда сервер 1 недоступен

Фактически расчет выглядит так:

• (значение crc32 ключа) % (max значение crc32 по серверам) = "остаток от деления"
• находим диапазон, в который входит "остаток от деления", можно просто перебрать, например "остаток от деления" равен 29:
  0 > 29 < 10   - диапазон не подходит
  10 > 29 < 20 - диапазон не подходит
  20 > 29 < 30 - диапазон найден

• находим ближайшее значение в диапазоне для числа "остаток от деления":
  "максимальное число диапазона" / 2 = "половина диапазона"
  "остаток от деления" > "половина диапазона" - значит сервер с максимальным значением найденного диапазона
  в противном случае - сервер с минимальным значением найденного диапазона

В реальной жизни цепочки будут не такими пропорциональными, например 0-12, 12-14, 14-30 что повлечет за собой неравномерное распределение данных. Поэтому и появляются разного рода оптимизации.

Советы

Чтобы не реализовывать подобный алгоритм самому, в интернете полно реализаций на множестве языков программирования, например на php и python

Если вы знаете, что у вас будет максимум 10 серверов, возможно, вам нужно простое решение. Например, взять максимально возможное значение crc32 и вручную создать диапазоны по серверам, например:

Таким образом, если у Вас выйдет из строя какой-то сервер, то все будет предсказуемо.

Если думать дальше, то тут однозначного решения не найти, например Вы решите добавить еще какой-то сервер, то тут возможно понадобится ручная миграция данных (до миграции лучше не доводить - трудозатратно). Значит надо брать сервера с запасом или в процессе можно просто докупать память на эти сервера. Если решили увеличить память на серверах, то неплохим решением будет предварительное создание реплики того сервера, который будет обновлен.

Еще мне понравился вариант используемый в компании Badoo, там добавляют новый сервер, на старый сервер данные больше не пишут (только читают, при этом новый сервер в приоритете), таким образом данные на старом сервере протухают и самоудяляются и сервер выводится из строя.

Источник: 1 - 2