?

Log in

Previous Entry | Next Entry

View more presentations from Anton. Download here.
Зачем?

Есть большой пласт технологий для создания распределенных систем: создание железных решений, распределенного ПО для управления системой, распределенных хранилищь, etc. Все это двигает grid технологии и cloud computing, и при разработки всего этого люди встречаются со множеством проблем. Так как проблем много мне хотелось бы остановиться на одной конкретной проблеме: хранение данных в распределенных системах, а именно на способе создания ключей, так как распределенные хранилища строиться из нескольких серверов и традиционной парадигмой хранения данных являеться Key-Value. Т.е. каждому элементу ставится в соответствие какой-либо ключ. Этот ключ выступает средством однозначного соответствия сервера и данных, и с помощью него всегда можно достатать те данные, которые тебе нужны.

Традиционные подходы.
  • Необходима функция:
     f(ключ)= номер_сервера 

    У данного подхода есть очевидные проблемы, в том что мы не знаем заранее значение ключей и в любом случае данная функция сводиться к следующему подходу.
  • «Стандартный вариант» по модулю:
     f(ключ)= crc32(ключ) % кол-во_серверов 

    При этом подходе проблемы возникают когда изменяться структура системы, каждый раз когда у нас удаляется или добавляется сервер нам необходимо перераспределять данные, при чем этих данных будет очень много. Для примера пусть у нас есть 100 ключей, по 25 на каждом (4 сервера), пусть хэш каждого ключа соответствует его номеру. Тогда ключи 0, 4, 8,… лежат на 1-м сервере, 1, 5, 9,… — на 2-м, 2, 6, 10,… — на 3-м и 3, 7, 11,… — на 4-м. Вдруг случается, что 4-й сервер выходит из строя, и теперь функция распределения ключей меняется на: ключ % 3. И в этоге ключи 3, 7, 11,… и их значения потеряны (т. к. лежали на упавшем сервере), это 25% потерянных данных. Далее получается что на надо перераспределить ключи так как, ключ 6 — лежал на 3-м сервере, теперь он лежит на 1-м, ключ 5 — раньше лежал на 1-м, теперь он на 3-м сервере и т. д. Сколько ключей сохранили своё расположение? Те, для которых k % 3 = k % 4. Сколько таких?
Consistent hashing.

Где же выход? А он где то рядом, а именно в консистентные хэшах.
consistent_hashing_1.pngconsistent_hashing_2.png
Суть алгоритма заключается в следующем: мы рассматриваем набор целых чисел от 0 до 2^32, «закручивая» числовую ось в кольцо (склеиваем 0 и 2^32). Каждому сервера из пула серверов мы сопоставляем число на кольце (рисунок слева, сервера A, B и C). Ключ хэшируется в число в том же диапазоне (на рисунке – синие точки 1-4), в качестве сервера для хранения ключа мы выбираем сервер в точке, ближайшей к точке ключа в направлении по часовой стрелке. Если сервер удаляется из пула или добавляется в пул, на оси появляется или исчезает точка сервера, в результате чего лишь часть ключей перемещается на другой сервер. На рисунке 2 справа показана ситуация, когда сервер C был удалён из пула серверов и добавлен новый сервер D. Легко заметить, что ключи 1 и 2 не поменяли привязки к серверам, а ключи 3 и 4 переместились на другие сервера. На самом деле одному серверу ставится в соответствие 100-200 точек на оси (пропорционально его весу в пуле), что улучшает равномерность распределения ключей по серверам в случае изменения их конфигурации.
В случае консистентного хэширования ключей ранее рассмотренный пример будет выглядеть так, что ключи которые были на 3х серверах и остались в рабочем состоянии, на них же и останутся. А ключи с 4-го сервера равномерно распределяться по 3-м оставшимся, мы потеряли ровно 25% ключей — возможный минимум.

Применение.

Picture 24.pngPicture 27.png


Comments