Довідка та теорія
Узгоджене гешування розміщує і ключі, і сервери на круговому гешовому просторі — кільці. Кожен ключ належить першому серверу, знайденому за годинниковою стрілкою від його позиції.
Проблема переназначення
Наївне hash(key) mod N перетасовує майже всі ключі
при зміні N. На кільці новий сервер забирає лише
дугу між ним і попереднім вузлом, тож у середньому переміщується
лише 1/N ключів.
Віртуальні вузли
Одна точка на сервер дає нерівні дуги. Розміщення кожного сервера
в V точках — віртуальних вузлах — розбиває
володіння на багато малих дуг і вирівнює навантаження. Більше
реплік — справедливіший баланс.
Пошук
- Гешуємо ключ у позицію на кільці.
- Рухаємося за годинниковою стрілкою до першого віртуального вузла.
- Фізичний сервер цього вузла володіє ключем.
У реальному світі
Використовують Amazon Dynamo, Cassandra, Riak, клієнтський шардинг memcached, CDN та DHT на кшталт Chord.
Поширені запитання
Що таке узгоджене гешування?
Узгоджене гешування відображає і ключі, і сервери на круговий гешовий простір (кільце). Кожен ключ належить першому серверу, знайденому за годинниковою стрілкою від позиції ключа, тож додавання чи вилучення сервера зачіпає лише ключі поблизу цього сервера.
Чому не можна просто брати ключ mod N для вибору сервера?
За hash(key) mod N зміна N перетасовує майже кожен ключ, бо модуль змінюється для всіх. Узгоджене гешування уникає цього, відв'язуючи позиції ключів від кількості серверів.
Скільки ключів переміщується під час додавання сервера?
У середньому переміщується лише близько 1/N ключів, де N — кількість серверів, бо новий сервер забирає лише ту дугу кільця, що лежить між ним і попереднім сервером за годинниковою стрілкою.
Що таке віртуальні вузли?
Кожен фізичний сервер розміщують у багатьох точках кільця, які називають віртуальними вузлами або репліками. Замість однієї позиції на сервер V позицій розподіляють володіння на багато малих дуг.
Чому віртуальні вузли покращують балансування навантаження?
За однієї точки на сервер випадкове розміщення може дати одним серверам величезні дуги, а іншим — крихітні. Багато віртуальних вузлів усереднюють ці коливання, тож кожен сервер отримує справедливішу частку ключів.
Як ключ знаходить свій сервер на кільці?
Ключ гешується в позицію на кільці, потім рухаються за годинниковою стрілкою, доки не натраплять на перший сервер (віртуальний вузол). Цей сервер володіє ключем. Якщо пройти вершину кільця, відбувається обгортання до початку.
Де застосовують узгоджене гешування?
Воно живить розподілені кеші на кшталт клієнтського шардингу memcached, сховища ключ-значення як-от Amazon Dynamo, Cassandra і Riak, мережі доставки контенту та однорангові розподілені геш-таблиці (DHT) на кшталт Chord.
Що стається з ключами під час вилучення сервера?
Переназначаються лише ключі, що належали віртуальним вузлам вилученого сервера. Кожен зачеплений ключ переходить за годинниковою стрілкою до наступного вцілілого сервера, а всі інші лишаються на місцях.
Скільки віртуальних вузлів варто використовувати?
На практиці системи використовують від близько 100 до кількох сотень віртуальних вузлів на сервер. Більше реплік дає рівніший баланс, але коштує більше пам'яті та накладних витрат на структуру пошуку.
Як саме ключі відображаються на кільце?
Геш-функція відображає кожен ключ і кожну мітку віртуального вузла в число з фіксованого діапазону, наприклад від 0 до 2^32 − 1. Цей діапазон трактують як коло, тож найбільше значення обгортається до найменшого.