Консистентні хеші (Consistent hashing)

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)

Суть алгоритму полягає в наступному: ми розглядаємо набір цілих чисел від 0 до 2 ^ 32, «закручуючи» числову вісь в кільце (склеюємо 0 і 2 ^ 32). Кожному сервера з пулу серверів ми співставляємо число на кільці (малюнок зліва, сервера A, B і C). Ключ хешіруется до числа в тому ж діапазоні (на малюнку – сині точки 1-4), в якості сервера для зберігання ключа ми вибираємо сервер в точці, найближчій до точки ключа в напрямку за годинниковою стрілкою. Якщо сервер видаляється з пулу або додається в пул, на осі з’являється або зникає точка сервера, в результаті чого лише частина ключів переміщається на інший сервер. На малюнку 2 праворуч показана ситуація, коли сервер C був видалений з пулу серверів та додано новий сервер D. Легко помітити, що ключі 1 і 2 не поміняли прив’язки до серверів, а ключі 3 і 4 перемістилися на інші сервера. Насправді одному сервера ставиться у відповідність 100-200 точок на осі (пропорційно його вазі в пулі), що покращує рівномірність розподілу ключів за серверів у разі зміни їх конфігурації.
У випадку консистентним хешування ключів раніше розглянутий приклад буде виглядати так, що ключі які були на 3х серверах і залишилися в робочому стані, на них же і залишаться. А ключі з 4-го сервера рівномірно розподілятися по 3-м, що залишилися, ми втратили рівно 25% ключів – можливий мінімум.

Застосування.

Консистентні хеші (Consistent hashing)