Узгоджене гешування — розподілене балансування навантаження з віртуальними вузлами

1. Проблема гешування за модулем

Простий підхід до розподілу N елементів між M серверами — обчислити server = hash(key) % M. Це добре працює, доки M ніколи не змінюється. Але в реальній розподіленій системі сервери падають, а нову потужність додають постійно.

Узгоджене гешування розв’язує це, будуючи простір, де додавання чи вилучення одного вузла зміщує лише близько 1/N частки ключів — мінімум можливого.

2. Геш-кільце

Уявіть вихід геш-функції (наприклад, SHA-1 з 2³² можливими значеннями), розташований як коло — геш-кільце — від 0 до 2³²−1. І сервери, і ключі відображаються на це кільце за допомогою тієї самої геш-функції:

• Кожен сервер гешується до позиції на кільці: pos(server_i) = hash(server_i).
• Кожен ключ гешується до позиції на кільці: pos(key) = hash(key).

Позиції зберігаються у відсортованій структурі даних (відсортований масив або збалансоване двійкове дерево пошуку). Кільцева структура виникає з концептуального «згортання»: після максимального значення гешу позиції продовжуються з 0.

3. Пошук вузла за ключем

Щоб знайти, який сервер відповідає за ключ, обчисліть його геш-позицію, а потім знайдіть перший сервер за годинниковою стрілкою від цієї позиції:

// Геш-кільце узгодженого гешування на JavaScript (спрощено)
class ConsistentHashRing {
  constructor() {
    this.ring = new Map();   // позиція → сервер
    this.sorted = [];          // відсортовані позиції
  }

  addServer(name) {
    const pos = hash32(name);
    this.ring.set(pos, name);
    this.sorted = [...this.ring.keys()].sort((a, b) => a - b);
  }

  getServer(key) {
    const pos = hash32(key);
    // двійковий пошук першої позиції >= pos
    let lo = 0, hi = this.sorted.length - 1;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (this.sorted[mid] < pos) lo = mid + 1;
      else hi = mid;
    }
    // згорнути до першого сервера, якщо вийшли за кінець кільця
    const idx = lo >= this.sorted.length ? 0 : lo;
    return this.ring.get(this.sorted[idx]);
  }
}

Пошук має складність O(log N) із двійковим пошуком, де N — кількість позицій серверів. Для N = 1000 позицій потрібно лише 10 порівнянь — незначні накладні витрати.

4. Приєднання та вихід вузла

Критична перевага: коли вузол додається або вилучається, мігрувати на інші сервери має лише частка 1/N усіх ключів.

Порівняйте з гешуванням за модулем, яке перепризначає приблизно (N−1)/N ≈ 80% ключів при додаванні одного сервера до пулу з 5 — узгоджене гешування зменшує міграцію в N−1 разів.

5. Віртуальні вузли

За небагатьох фізичних серверів позиції на кільці можуть бути згрупованими — одні сервери відповідають за великі дуги, інші — за малі, що спричиняє нерівномірне навантаження. Віртуальні вузли (vnodes) виправляють це: кожен фізичний сервер розміщується в кількох позиціях на кільці.

addServer(name, replicas = 150) {
  for (let i = 0; i < replicas; i++) {
    const pos = hash32(`${name}#${i}`);
    this.ring.set(pos, name);
  }
  this.sorted = [...this.ring.keys()].sort((a, b) => a - b);
}

За 150 віртуальних вузлів на сервер розподіл навантаження наближається до теоретичного рівномірного розподілу. Серверам із більшою апаратною потужністю можна призначити більше vnodes, щоб вони отримували пропорційно більше навантаження — простий механізм для гетерогенних кластерів.

6. Реплікація та списки переваг

Для відмовостійкості кожен ключ зберігається на кількох серверах — зазвичай на N послідовних вузлах за годинниковою стрілкою на кільці (N — коефіцієнт реплікації, наприклад, 3). Цей набір із N вузлів є списком переваг ключа.

• Читання та записи можуть спрямовуватися до будь-якої з N реплік.
• Узгодженість на основі кворуму: читання потребують R підтверджень; записи потребують W. За R + W > N принаймні один вузол мусить мати найсвіжішу версію (сильна узгодженість).
• Налаштування Cassandra за замовчуванням (N=3, R=1, W=1) дає кінцеву узгодженість, але максимальну доступність; (N=3, R=2, W=2) дає сильнішу узгодженість ціною затримки.

Коли використовуються vnodes, список переваг пропускає віртуальні вузли, що належать тому самому фізичному серверу, щоб репліки потрапили на різні стійки чи домени відмов.

7. Системи в реальному світі

Оригінальну статтю про узгоджене гешування опублікував Каргер та ін. у MIT 1997 року. Попри свою простоту, основна ідея — відображення як ідентифікаторів ресурсів, так і ідентифікаторів серверів у той самий абстрактний простір та використання близькості для призначення відповідальності — залишається однією з найвпливовіших ідей у розподілених системах, досі безпосередньо помітною в логіці призначення сховища кожного Kubernetes StatefulSet.