UK 
EnglishТипова
Polski💍 Узгоджене гешування — гешове кільце
Відображайте ключі й сервери на гешове кільце так, що додавання чи вилучення вузла переносить лише малу частку ключів. Віртуальні вузли вирівнюють навантаження — техніка за розподіленими кешами й DHT.
Про узгоджене гешування
Узгоджене гешування вирішує критичну проблему розподілених систем: як призначати ключі даних серверам так, щоб додавання чи вилучення вузла переносило якомога менше ключів. Техніка відображає і ключі, і сервери на позиції кругового гешового кільця розміром 2^32. Кожен ключ належить першому серверу, знайденому за годинниковою стрілкою від його позиції. За наївного підходу з модулем (hash(ключ) mod N) зміна N з однієї кількості серверів на іншу може перемапити майже кожен ключ — катастрофічно для живого кешу. Узгоджене гешування обмежує порушення приблизно 1/N ключів у середньому, оскільки право власності змінюється лише для дуги кільця, суміжної з доданим чи вилученим сервером.
Віртуальні вузли (також звані репліками) — це практичне вдосконалення: кожен фізичний сервер розміщується у V позиціях на кільці замість однієї, розподіляючи володіння на багато малих дуг. Це різко вирівнює розподіл навантаження — без віртуальних вузлів один сервер може випадково отримати 40% ключів; зі 100+ віртуальними вузлами розподіл наближається до ідеального 1/N на сервер. Налаштуйте кількість серверів, віртуальних вузлів і ключів повзунками, а потім додавайте чи вилучайте сервери, щоб побачити, як мало ключів (виділені білим) потребують переміщення.
Часті запитання
Чому гешування за модулем спричиняє масовий перерозподіл ключів при зміні серверів?
За hash(ключ) mod N слот, у який мапиться кожен ключ, залежить від N. Коли N змінюється — скажімо, з 4 на 5 — модуль змінюється практично для кожного ключа, перемаповуючи приблизно (N−1)/N ≈ 80% з них. Узгоджене гешування усуває це, відв'язуючи позиції ключів від кількості серверів: кожен ключ завжди мапиться на ту саму позицію кільця, і лише пошук за годинниковою стрілкою змінюється при додаванні чи вилученні сервера.
Скільки саме ключів переміщується, коли до кільця додають сервер?
Коли новий сервер S розміщується у позиції p на кільці, він отримує дугу від попереднього сервера (за годинниковою стрілкою) до p. Переміщуються лише ключі, що потрапляють у цю дугу — вони переходять від попереднього власника до S. У середньому це 1/N усіх ключів, де N — нова кількість серверів. Усі інші ключі залишаються зі своїми попередніми власниками.
Яку проблему вирішують віртуальні вузли і скільки їх варто використовувати?
З однією позицією на сервер випадкове розміщення на кільці дає вкрай нерівні довжини дуг: деякі сервери можуть отримати втричі більше за середнє навантаження. Розміщення кожного фізичного сервера у V позиціях віртуальних вузлів ділить кільце на V×N сегментів, вирівнюючи дисбаланс. Виробничі системи (Amazon Dynamo, Cassandra) зазвичай використовують 100–200 віртуальних вузлів на сервер, де стандартне відхилення навантаження падає нижче 10% від середнього.
Як пошук ключа працює за сталий час?
Позиції віртуальних вузлів зберігаються у відсортованому масиві або збалансованому бінарному дереві пошуку. Щоб знайти власника ключа, гешуємо ключ, щоб отримати його позицію на кільці, а потім виконуємо бінарний пошук найменшої позиції віртуального вузла, яка є більшою або рівною позиції ключа (з переходом до позиції 0, якщо жодної не знайдено). Цей пошук виконується за O(log(V×N)) — фактично сталий час для фіксованих V і N.
Які реальні системи використовують узгоджене гешування?
Amazon Dynamo (2007) популяризував узгоджене гешування з віртуальними вузлами для свого сховища ключ-значення; Cassandra успадкувала ту саму архітектуру. Бібліотеки клієнтів memcached (наприклад, алгоритм ketama) використовують його для шардування ключів кешу серед пулу серверів. Мережі доставки контенту та однорангові розподілені хеш-таблиці (DHT), як-от Chord і Kademlia, також покладаються на гешування на основі кільця.
Що стається з даними, коли сервер виходить з ладу і вилучається?
Якщо сервер S виходить з ладу, його позиції віртуальних вузлів звільняються. Ключі, якими володів S, тепер належать наступному серверу за годинниковою стрілкою для кожної дуги. Якщо налаштовано реплікацію (зазвичай 3 репліки в Cassandra), дані вже існують на наступних N−1 серверах за годинниковою стрілкою, тож кластер продовжує обслуговувати читання без втрати даних. Кворуми запису забезпечують узгодженість під час відновлення.
Як узгоджене гешування пов'язане з Chord DHT?
Chord (Стоіка та ін., 2001) — це одноранговий протокол пошуку, побудований безпосередньо на узгодженому гешуванні. Кожному вузлу присвоюється позиція на 160-бітному кільці SHA-1. Chord додає «таблицю пальців» (finger table) з O(log N) скорочень на вузол, тож будь-який ключ можна знайти за O(log N) переходів — поєднуючи узгоджене гешування з ефективною розподіленою структурою маршрутизації.
Чи може узгоджене гешування працювати з серверами різної потужності?
Так. Призначивши більше віртуальних вузлів серверу з більшою потужністю — скажімо, 200 віртуальних вузлів машині з удвічі більшою пам'яттю проти 100 для звичайного вузла — його частка кільця пропорційно збільшується відповідно до потужності. Це зважене узгоджене гешування використовує розподіл токенів Cassandra та хмарні балансувальники навантаження для спрямування більшого трафіку на більші інстанси.
Що таке узгоджене гешування з «обмеженим навантаженням»?
У 2017 році Google опублікувала статтю «Consistent Hashing with Bounded Loads», яка додає обмеження місткості: жоден сервер не може утримувати більше ніж (1 + ε) від середньої кількості ключів. Коли цільовий сервер перевантажений, ключ призначається наступному серверу за годинниковою стрілкою, розподіляючи навантаження рівномірніше. Цей варіант використовується у виробничих балансувальниках навантаження Google.
Як вибір геш-функції впливає на розподіл кільця?
Хороша геш-функція повинна рівномірно розподіляти і ключі, і мітки віртуальних вузлів по 2^32-бітному кільцю. Погані геш-функції спричиняють кластеризацію, через що деякі дуги стають значно довшими за середні навіть за багатьох віртуальних вузлів. На практиці FNV-1a, MurmurHash3 і xxHash — популярні вибори завдяки швидкості та рівномірному розподілу.