Послідовне хешування: Кольцеве перемішування

Проблема з обчисленням хешу server = hash(key) % n

Найочевидніший спосіб розподілити ключі між n керованими серверами – це server = hash(key) % n. Це одна лінія коду, яка ідеально рівномірно розподіляє навантаження – за умови, що n ніколи не змінюється. Як тільки до п’ятивидового кластера додають шостий сервер, оператор модуля змінюється з %5 на %6 для практично кожного ключа, і сервер, якому призначається кожен ключ, майже випадковим чином переходить на інший. В середньому приблизно (n-1)/n усіх ключів – близько 83% для n=6 – потрапляють на інший сервер, ніж раніше, хоча лише один сервер змінився. Кожен з цих ключів тепер призведе до промаху кешу, і вони всі одночасно надходять до початшої бази даних, коли кластер вже перебуває під додатковим навантаженням через масштабування.

Розміщення серверів та ключів на одному колі

Консистентне хешування, опубліковане Karger et al. у MIT у 1997 році, вирішує цю проблему шляхом хешування серверів і ключів в одну й ту ж область та розміщення цієї області як коло – хеш-кільце – що охоплює діапазон від 0 до 2³²−1 і обертається назад до 0. Обидва імена серверів та ключі передаються через одну хеш-функцію (зазвичай використовуються швидкі, некриптографічні хеші, такі як MurmurHash3 або xxHash, оскільки важлива рівномірність, а не безпека тут) для отримання позиції на цьому колі. Ключ належить серверу, який знаходиться в першому місці за годинниковою стрілкою від власної позиції ключа – без модуля та без фіксованого розміру таблиці, просто "пройдіть за годинниковою стрілкою до того, як ви натрапите на сервер".

Лише сусідній дуг рухається

З цієї однієї зміни щодо обчислення власності випливає драматичний наслідок. Коли новий сервер вставляється між існуючими серверами A та B на позиції P, лише ключі, які раніше потрапляли у дугу між A та P, повинні переміститися – тепер вони належать новому вузлу замість того, щоб продовжувати до B. Усі інші ключі будь-якого місця на колі все ще знаходять точний сервер за годинниковою стрілкою від них, оскільки нічого в їхньому сусідстві не змінилося. Видалення сервера працює аналогічно у зворотньому напрямку: його ключі просто перетікають до його наступника за годинниковою стрілкою.

// lookup: перша колійна позиція >= hash(ключ), бінарний пошук відсортованих позицій function getServer(key, sortedPositions, ring) { const pos = hash32(key); let lo = 0, hi = sortedPositions.length - 1; while (lo > 1) if (sortedPositions[mid] < pos) lo = mid + 1; else hi = mid; return ring.get(sortedPositions[idx]); } // очікується перемапірування ключей, коли до кільця або з нього додається/видаляється вузол ≈ 1/n Для кільця з п’яти вузлів додавання шістого сервера перемарінує лише приблизно 1/6 ключів замість 5/6 – це зменшення приблизно (n-1)× порівняно з наївним хешуванням modulo, і це теоретичний мінімум: ви не можете збільшити ємність без перенесення деяких ключів на новий сервер, але consistent hashing гарантує, що ключі будуть переміщені лише тоді, коли це необхідно.

// lookup: first ring position >= hash(key), binary search over sorted positions
function getServer(key, sortedPositions, ring) {
  const pos = hash32(key);
  let lo = 0, hi = sortedPositions.length - 1;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (sortedPositions[mid] < pos) lo = mid + 1; else hi = mid;
  }
  const idx = lo >= sortedPositions.length ? 0 : lo;   // wrap to first node
  return ring.get(sortedPositions[idx]);
}
// expected keys remapped when 1 node joins or leaves an n-node ring ≈ 1/n

Віртуальні вузли: згладжування нерівномірного кільця

З обмеженою кількістю фізичних серверів їх випадкові позиції на кільці можуть скупчитися через випадковість, залишаючи один сервер відповідальним за великий сегмент, а інший – практично нічого. Рішенням є віртуальні вузли: кожен фізичний сервер хешується у багато позицій на кільці (Apache Cassandra за замовчуванням використовує 256 на вузол, історично часто 100-200 в інших системах), кожна з яких є окремим невеликим сегментом. За достатньої кількості віртуальних вузлів на сервер закон великих чисел починає діяти і кожен фізичний сервер бере на себе приблизно рівну загальну частку кільця – а більш потужний сервер може просто отримати більше віртуальних вузлів для поглинання пропорційно більшої частини навантаження, що є чистою механізмом для нерівномірного обладнання.

Де з'являється коло

Консистентне хешування є шаром маршрутизації, що лежить в основі більшості еластичних розподілених систем зберігання даних. Клієнти Memcached використовують його (через бібліотеку libketama), щоб додавання вузла кешу не призводило до недійсності всього кластера кешу. Amazon DynamoDB та Apache Cassandra використовують розділення на коло з віртуальними вузлами (конфігуруваний num_tokens у Cassandra) у поєднанні з N-швидкісним списком послідовників за годинниковою стрілкою для реплікації. Розподілені хеш-таблиці (DHT), такі як Chord у мережах peer-to-peer, а також маршрутизація запитів CDN у компаніях, таких як Akamai, будуються на тій самій ідеї кола – відображають ідентифікатори ресурсів та ідентифікатори вузлів в один простір і дозволяють близькості визначати володіння.

Frequently asked questions

Спробуйте наживо

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