Головна / Статті / Від модуля до кільця хешів: масштабування флоту кешів Node.js без проблем

Node.jsSystem DesignCachingDistributed SystemsRedisPerformance

Від модуля до кільця хешів: масштабування флоту кешів Node.js без проблем

Дізнайтеся, чому шардування за принципом hash-mod-N призводить до краху баз даних під час зміни вузлів, як порівнюються алгоритми rendezvous, jump та ring hashing, та як створити збалансований ваговий кільцевий структуру в Node.js.

4407 слів

Кластер кешу, який успішно працював протягом кількох місяців, може припинити роботу бази даних протягом кількох хвилин після звичайної зміни – додавання одного вузла. Причиною зазвичай є окремий рядок коду клієнта, який обирає сервер за формулою hash(key) % N. У цьому посібнику детально пояснюється, чому цей рядок призводить до проблем, порівнюються чотири серйозні альтернативи, створюється кільце консистентного хешування високої якості для продакшну у Node.js, а також наводяться операційні підводні камені, від яких сам алгоритм не зможе захистити.

Патерн відмов

Ніхто не діяв бездбало. Клієнт просто розподіляв ключі так, як завжди:

const node = nodes[hash(key) % nodes.length];

Цей вираз дуже рівномірно розподіляє ключі, тому здається правильним. Проблема полягає у тому, що він робить у момент зміни значення nodes.length, і саме тут починається решта цього посібника. У ньому розглядаються чотири окремі проблеми, аналізуються реальні альтернативи, а потім створюється та тестується структура типу „кільце“ у Node.js.

Чотири проблеми, приховані за однією ідеєю

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

Проблема 1: зміна N призводить до переміщення майже всіх ключів

За допомогою формули hash(key) % N зміна значення N призводить до переміщення майже всіх ключів, а не лише кількох.

Корисно розглянути ці числа. Ключ із хешем 1,000,003 відповідає вузлу 3 за значенням % 4, і водночас випадково відповідає також вузлу 3 за значенням % 5. Ключ із хешем 1,000,004 відповідає вузлу 0 за значенням % 4 та вузлу 4 за значенням % 5. Ці два способи мапування не пов’язані між собою, тож ключ залишається на своєму місці лише випадково, з ймовірністю приблизно 1 до N.

Якщо проаналізувати мільйон ключів, закономірність є чіткою: перехід від 8 до 9 вузлів призводить до переміщення 88,93% ключів, а у кластері зі ста вузлами додавання одного вузла унеможливлює доступ до приблизно 99% кешу.

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

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

Проблема 2: та сама перерозподіл, але без планування

Принаймні перша проблема виникає тоді, коли ви вирішуєте масштабувати систему. Друга — це той самий процес, спричинений збоєм, але у найменш підходящий момент.

Вузол вичерпує свою пам’ять, хост завершує роботу або мережевий розкол приховує один вузол від половини системи. Кількість вузлів зменшується з 8 до 7, і кожен клієнт, діючи самостійно, перемапує близько 87% своїх ключів на залишені вузли.

Ситуація зараз критична: зникло 12,5% ємності кешу, база даних стикається з 87% випадків неможливості знаходження даних, а сім залишених вузлів беруть на себе трафік втраченого вузла одночасно з поповненням майже всіма ключами. Частим наслідком є зрив другого вузла, що змушує проводити ще одну повну перерозподілку, а це, у свою чергу, призводить до зриву третього вузла.

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

Проблема 3: наївний кільцевий механізм сильно дисбалансований

Очевидним рішенням проблеми 1 є розміщення вузлів та ключів у одному числовому просторі та призначення кожного ключа вузлу, який знаходиться після нього у годинному напрямку. Це суть консистентного хешування, і воно дійсно усуває необхідність масової перерозподілки.

Однак при наївній реалізації вона погано балансує навантаження. Вузли розташовуються там, де опиняються їхні хеші, тож відстані між ними є випадковими, а випадкові відстані рідко бувають однаковими. Коли кожен хеш розміщує по чотири вузли, у одному вимірюванні один вузол контролював 45% простору ключів, а інший — лише 13%; різниця становила 3,4 рази, причому жодних помилок не було.

Цей дисбаланс також є постійним. Він походить від самих назв вузлів, тож той самий вузол, наприклад cache-04, залишається активним доти, доки його не перейменують, а будь-хто, хто досліджує ситуацію, бачить код, який працює саме так, як написаний.

У більшому масштабі ситуація погіршується. Якщо у 8 вузлів є по одній точці кільця, найбільш завантажений вузол мав 434% своєї справедливої частки, а найменш завантажений — 3,7%. Це фактично один перевантажений сервер та сім бездіяльних.

Проблема 4: кожен клієнт мусить погодитися

Найменш помітна проблема стосується авторитетності. Хтось має прив’язувати ключ до вузла, і цей процес має давати однакову відповідь на кожному пристрої, який запитує.

Одним із варіантів є використання сервісу-координатора, який зберігає авторитетну карту шардів. У такому разі або кожен пошук коштує двох подорожей по мережі, або клієнти кешують карту, і тоді потрібен спосіб її анулювання. Якщо два клієнти матимуть різні версії карти, навіть на мить, один може записати user:42 у вузол A, тоді як інший буде читати його з вузла B. Нічого не втрачається, що, можливо, ще гірше: тепер існує два можливі значення.

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

Конкретний сценарій та варіанти

Щоб зробити порівняння конкретнішим, розгляньмо цю систему.

Система. API електронної комерції зберігає дані сеансу та профілю у пулі вузлів Redis. Максимальне навантаження становить близько 40 000 запитів на секунду до 25 мільйонів ключів із коефіцієнтом успішних пошуків 94%. База даних існує лише завдяки тим 6% запитів, які не знаходять потрібних даних. (Щоб ознайомитися з основами механізмів кешування, див. Основи кешування в Redis.)

Вимоги:

  1. Збільшити кількість вузлів з 8 до 12 перед початком продажів, не спричиняючи хвилі невдалих пошуків
  2. Витримати втрату одного вузла з обмеженим, прийнятним радіусом впливу
  3. Зберігати рівномірне навантаження, щоб жоден вузол не перевищував приблизно 120% своєї частки
  4. Уникати використання будь-якого координатора у шляху читання даних
  5. Враховувати різний обладнання: деякі вузли мають 64 ГБ, інші — 16 ГБ, і вони не повинні нести однакове навантаження

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

Варіант А: модульне хешування

hash(key) % N забезпечує ідеальний баланс, вимагає лише однієї інструкції та не використовує пам’ять.

Він повністю не відповідає вимогам 1 та 2. Проте його варто згадати, оскільки саме його спочатку пишуть усі, і він функціонує ідеально до моменту, коли це перестає бути таким.

Обирайте його тоді, коли N справді ніколи не змінюється, наприклад під час розподілу завдання серед фіксованої кількості працівників або шардування всередині одного процесу.

Варіант Б: координатор та таблиця пошуку

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

Перевага справжня: повний контроль. Ви можете перемістити окремий „гарячий“ шард, поступово відновлювати баланс у певному діапазоні, стежачи за показниками, або прив’язати конкретного користувача до певного обладнання. Жоден підхід, заснований на хешуванні, не пропонує нічого з цього, і при певному розмірі системи вам це стане необхідним.

Ціна також є реальною: потрібна система консенсусу, складність у підтримці актуальності кожної кешованої копії карти та обов’язкова залежність від шляху читання даних.

Обирайте цей підхід тоді, коли ви переміщуєте стійкі дані, а не тимчасові записи кешу, і коли вам потрібен контроль над процесом міграції, а не дозволити всьому змінитися одночасно.

Варіант C: хешування з зустріччю (HRW)

Метод з найвищою випадковою вагою порівнює кожен ключ із кожним вузлом та обирає переможця:

function rendezvous(key, nodes) {
  let best = null, bestScore = -1;
  for (const node of nodes) {
    const score = mix(hash(key), hash(node));
    if (score > bestScore) { bestScore = score; best = node; }
  }
  return best;
}

Це і є весь алгоритм. Тут немає кільця, віртуальних вузлів, впорядкованої структури та немає чого відновлювати при зміні складу.

За двома найважливішими показниками він також перевершує кільцеву структуру. Перехід від 8 до 9 вузлів призвів до переміщення 11,09% ключів, що є нижчим за теоретичний мінімум у 11,11%, а балансування відбулося майже ідеально без будь-якої налаштування.

Недоліком є час обробки O(N) на кожен пошук, оскільки кожен ключ гешується щодо кожного вузла, і ця витрата швидко зростає зі збільшенням кількості вузлів.

Обирайте його тоді, коли у вас менше приблизно 30 вузлів. Багато команд використовують близько восьми кеш-вузлів, і для них найкращим варіантом буде алгоритм rendezvous hashing: його легше писати та розуміти, і він краще забезпечує балансування. Кільцева структура є більш відомим рішенням, але не обов’язково кращим.

Варіант D: консистентний геш з стрибком

Цей алгоритм, опублікований Google у 2014 році, складається приблизно з десяти рядків, не вимагає пам’яті, майже ідеально збалансований та переміщує мінімальну кількість ключів.

Його обмеження є структурними. Він відносить ключ до номера контейнера у діапазоні [0, N) та не має уявлення про ідентичність вузла. Контейнери можна додавати або видаляти лише у кінці діапазону; немає способу видалити вузол номер 3 з середини, залишаючи все інше стабільним.

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

Варіант E: кільце хешування з віртуальними вузлами

Це класичний дизайн. Вузли та ключі ділять один круговий простір адрес, і ключ належить до першого вузла, який знаходиться у напрямку годинникової стрілки від нього.

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

Вибір варіанту для сценарію

При переході від 8 до 9 вузлів серед мільйона ключів альтернативи, окрім методу модулювання, наближаються до теоретичного мінімуму, а баланс кільця сильно залежить від кількості віртуальних вузлів, які отримує кожен сервер. Для цієї системи електронної комерції зі змішаною апаратурою, вузлами з іменами, які можуть зламатися, та флотом, що має налічувати 30 вузлів, кільце є правильним вибором. Решта цього посібника описує, як його правильно створити.

Як працює кільце

Відкладімо масиви та залишки. Уявіть собі коло, пронумероване від 0 до 2³² − 1, яке закінчується біля верхньої точки.

Весь алгоритм складається з двох правил:

  1. Гешуємо назву кожного вузла у цьому колі, тож cache-01 розташовується там, де його геш це визначає.
  2. Гешуємо кожен ключ у тому самому колі, а потім рухаємося годинниковою стрілкою. Перший вузол, до якого ми дістанемося, є власником ключа.

Ключова ідея полягає у тому, що вузли та ключі ділять один простір адрес. Усе інше випливає з цього, включаючи те, чому додавання вузла є недорогим.

Чому зміни у членстві залишаються локальними

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

Ключі, що знаходяться поза цим дугою, залишаються недоторканими та потрапляють до свого попереднього власника так само, як і раніше. Новоприбулий у середньому охоплює приблизно 1/(N+1) дуги, тож частка ключів змінюється. При зміні від 8 до 9 цей показник становив 11,06%, що є мінімумом у розмірі 11,11%, на відміну від 88,93% для методу модулю при такій самій зміні та наборі ключів.

Видалення працює у зворотному напрямку: дуга видаленого вузла переходить до його наступника у напрямку годинникової стрілки. При скороченні кількості вузлів з 8 до 7 було переміщено 12,60% ключів, що близько до теоретичних 12,50%. Вплив залишається обмеженим та прийнятним, а інші шість вузлів залишаються недоторканими.

Віртуальні вузли усувають дисбаланс

Повернімося до задачі 3: чотири вузли у чотирьох випадкових положеннях створюють дуже нерівномірні дуги.

Рішення на диво просте: не розміщуйте кожен вузол лише один раз. Розмістіть його 160 разів під 160 похідними іменами, такими як cache-01#0 та cache-01#1. Кожне похідне ім’я знаходиться в різному місці, тож кожен фізичний вузол має 160 невеликих розосереджених дуг замість однієї великої, а закон великих чисел вирівнює ситуацію.

При вимірюванні на мільйоні ключів на 8 вузлах баланс поступово покращується зі збільшенням кількості реплік. 160 — це звичайний стандарт, оскільки саме приблизно тут крива покращення стабілізується, проте 500 все одно дає значно кращі результати. Одна точка кільця потребує приблизно 12 байтів (4 байти для позиції та 8 байтів для посилання на власника), тож вісім вузлів із 500 реплік займають менше 50 КБ. Якщо для вас баланс важливіший за обсяг пам’яті, виберіть більшу кількість; це розрахунок, який мало хто з команд береться робити.

Віртуальні вузли також роблять визначення ваги практично безкоштовним. Вузол із вдвічі більшою кількістю пам’яті отримує вдвічі більше балів, а отже, приблизно вдвічі більше трафіку. При співвідношенні ваг 4:4:1:1 спостережуване розподіл було 40,6%, 41,1%, 9,4% та 9,0%, на відміну від ідеального співвідношення 40/40/10/10.

Реалізація кільцевої структури в Node.js

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

export class ConsistentHashRing {
  #positions = new Uint32Array(0); // sorted ring positions
  #owners = []; // owners[i] owns #positions[i]
  #nodes = new Map(); // id -> { weight, points }

  constructor({ replicas = 160, hash = defaultHash } = {}) {
    if (replicas < 1) throw new RangeError("replicas must be >= 1");
    this.replicas = replicas;
    this.hash = hash;
  }

  addNode(id, weight = 1) {
    if (typeof id !== "string" || id.length === 0)
      throw new TypeError("node id must be a non-empty string");
    if (weight <= 0) throw new RangeError("weight must be > 0");
    if (this.#nodes.has(id)) return this;
    this.#nodes.set(id, {
      weight,
      points: Math.max(1, Math.round(this.replicas * weight)),
    });
    this.#rebuild();
    return this;
  }

  removeNode(id) {
    if (this.#nodes.delete(id)) this.#rebuild();
    return this;
  }

  #rebuild() {
    const pairs = [];
    for (const [id, { points }] of this.#nodes) {
      for (let i = 0; i < points; i++)
        pairs.push([this.hash(`${id}#${i}`), id]);
    }
    pairs.sort((a, b) => a[0] - b[0]);
    this.#positions = Uint32Array.from(pairs, (p) => p[0]);
    this.#owners = pairs.map((p) => p[1]);
  }

  /** Index of the first ring point >= h, wrapping to 0. */
  #successor(h) {
    const pos = this.#positions;
    let lo = 0,
      hi = pos.length;
    while (lo < hi) {
      const mid = (lo + hi) >>> 1;
      if (pos[mid] < h) lo = mid + 1;
      else hi = mid;
    }
    return lo === pos.length ? 0 : lo;
  }

  get(key) {
    if (this.#positions.length === 0) return null;
    return this.#owners[this.#successor(this.hash(key))];
  }
}

Три аспекти проектування заслуговують на увагу.

Паралельні масиви замість масиву об’єктів. Зберігання позицій у Uint32Array дозволяє використовувати бінарний пошук у компактній, суміжній пам’яті, яка залишається у кеші CPU. З 8 вузлами та 160 репліками утворюється 1 280 точок, що становить приблизно 5 КБ, а пошук вимагає близько 11 порівнянь.

Ефект обертання в lo === pos.length ? 0 : lo. Ключ, який після хешування потрапляє за межі останньої точки, належить до першого вузла у колі. Відсутність цієї умови є найпоширенішою помилкою у саморобних структурах цього типу: результат є правильним майже для кожного ключа, але незрозуміло помилковим для кількох ключів, що знаходяться близько до верхньої межі діапазону.

Перебудова при зміні членства, а не під час пошуку. Зміни членства трапляються рідко, тоді як пошуки відбуваються десятки тисяч разів на секунду, тому періодичне сортування 1 280 записів не має значного ефекту з точки зору виконавчих ресурсів.

Реплікація, тобто пошук наступних власників ключа, — це рух по годинниковій стрілці, під час якого збираються різні фізичні вузли. Слово „різні“ має значення, оскільки сусідні точки на кільці часто належать до одного й того самого сервера:

getReplicas(key, count = 1) {
  const n = this.#positions.length;
  if (n === 0) return [];
  const wanted = Math.min(count, this.#nodes.size);
  const out = [];
  const start = this.#successor(this.hash(key));
  for (let step = 0; step < n && out.length < wanted; step++) {
    const owner = this.#owners[(start + step) % n];
    if (!out.includes(owner)) out.push(owner);
  }
  return out;
}

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

Ретельний вибір функції хешування

Багато навчальних матеріалів пропускають цю частину, хоча саме вона дає найбільш корисні результати для розуміння всього завдання.

Більшість реалізацій кілець за замовчуванням використовують MD5. Він працює, але є повільним: кільце, що використовує його, досягало лише 423 000 операцій пошуку на секунду, а аналіз продуктивності показав, що майже весь час витрачався на обробку даних за допомогою MD5.

Заміна його на FNV-1a — швидкий некриптографічний хеш-функцію — підвищила пропускну здатність приблизно у 15 разів. Однак баланс зламався: стандартне відхилення навантаження на кожну вершину зросло з 10,4% до 30,7%.

Якщо переглянути обчислені координати кількох віртуальних вершин, можна зрозуміти причину:

cache-01#0 → 4037809751
cache-01#1 → 4021032132
cache-01#2 → 4071364989
cache-01#3 → 4054587370
cache-01#4 → 3970699275

Усі вони знаходяться у вузькому діапазоні близько 4,0 мільярда. FNV-1a має слабку поведінку типу аваланчування, тобто схожі вхідні дані дають схожі результати. Назви віртуальних вершин відрізняються лише суфіксом, тому замість розсіювання 160 точок по колу кожна вершина згруповує їх у один щільний клустер. Оптимізація заради швидкості тихо повернула проблему 3.

Рішення полягає у проходженні результату роботи FNV через функцію змішування бітів — останній етап алгоритму MurmurHash3:

function fnv1a(str) {
  let h = 0x811c9dc5;
  for (let i = 0; i < str.length; i++) {
    h ^= str.charCodeAt(i);
    h = Math.imul(h, 0x01000193);
  }
  return h >>> 0;
}

// Scrambles the bits so near-identical inputs land far apart.
function fmix32(h) {
  h ^= h >>> 16;
  h = Math.imul(h, 0x85ebca6b);
  h ^= h >>> 13;
  h = Math.imul(h, 0xc2b2ae35);
  h ^= h >>> 16;
  return h >>> 0;
}

export const defaultHash = (str) => fmix32(fnv1a(str));

fmix32 по черзі використовує зсуви, операції XOR та множення, щоб зміна будь-якого вхідного біта поширювалася на всі вихідні біти. Math.imul здійснює справжнє множення 32-бітних цілих чисел, а >>> 0 перетворює результат назад на беззнакове 32-бітне число, яке підходить для Uint32Array. Завдяки приблизно десяти додатковим операціям комбінований хеш працював краще, ніж MD5, приблизно в 13 разів швидше.

Цей урок актуальний не лише для хешування: коли ви замінюєте компонент на швидший, потрібно перевірити ті властивості, які не оптимізувалися. FNV-1a — це цілком прийнятний хеш; просто він не підходить для цієї роботи, і в його описі немає жодних попереджень.

Перетворення кільця на клієнта кешу

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

Наведений нижче обгорток бере карту іменованих клієнтів, створює з неї кільце та під час кожної операції get пробує спочатку failoverDepth власників по черзі. Вузол, який видає помилку, позначається як недійсний на час downtimeMs та видаляється з кільця, а потім знову додається після закінчення цього терміну.

export class ShardedCache {
  #ring; #clients; #down = new Map();

  constructor(clients, { replicas = 160, failoverDepth = 2, downtimeMs = 10_000 } = {}) {
    this.#clients = new Map(Object.entries(clients));
    this.#ring = new ConsistentHashRing({ replicas });
    for (const id of this.#clients.keys()) this.#ring.addNode(id);
    this.failoverDepth = failoverDepth;
    this.downtimeMs = downtimeMs;
  }

  #markDown(id) {
    this.#down.set(id, Date.now() + this.downtimeMs);
    this.#ring.removeNode(id);
  }

  #reviveExpired() {
    const now = Date.now();
    for (const [id, until] of this.#down) {
      if (now >= until) { this.#down.delete(id); this.#ring.addNode(id); }
    }
  }

  async get(key) {
    this.#reviveExpired();
    for (const id of this.#ring.getReplicas(key, this.failoverDepth)) {
      try {
        return { value: await this.#clients.get(id).get(key), node: id };
      } catch {
        this.#markDown(id);
      }
    }
    return { value: null, node: null, allDown: true };
  }
}

Запуск цього коду на чотирьох симульованих вузлах, які містили по 10 000 ключів, а потім вимкнення одного з них, дало наступний результат:

Keys per node:  cache-01 2213 | cache-02 2462 | cache-03 2923 | cache-04 2402

Killing cache-02...
  served from cache: 7538
  cache misses:      2462
  hard failures:     0
  healthy nodes:     cache-01, cache-03, cache-04

  24.6% of traffic became a miss.

Ця цифра — це ваш план ємності. У флоті з чотирма вузлами одна несправність призводить до того, що додатково 24,6% операцій читання лягає на базу даних, тоді як у флоті з восьмома вузлами цей показник становить 12,5%. Якщо база даних не може витримати навантаження 1/N від загального обсягу операцій читання, яке надходить одночасно, справжньою проблемою є ємність бази даних, а не кешування, і метод послідовного хешування перетворює цю проблему з фатальної на помітну. Також варто зазначити, що не було жодних серйозних несправностей: запити на ключі недіючого вузла передавалися до наступного вузла та ставали звичайними помилками пошуку.

Проблеми у продакшені, які алгоритм не враховує

Кілька проблем залишаються поза межами алгоритму та все одно завдадуть вам проблем.

Відхилення версій кільця

Цей механізм допомагає лише тоді, коли кожен клієнт обчислює однакову відповідь. Поступово впроваджуйте зміни у склад членства: протягом кількох хвилин половина флоту бачитиме 8 вузлів, а інша половина — 9. Ці дві групи не погоджуються щодо приблизно 11% ключів. Для кешу це означає коротке зниження рівня успішних запитів; для будь-чого, що приймає зміни даних, це означає розбіжності у даних. Використовуйте версіонування для набору членства, розповсюджуйте його через єдиний канал та відображайте версію у своїх метриках, щоб ви могли спостерігати за цими відхиленнями, а не лише здогадуватися про них.

Надмірне видалення вузлів

Не видаляйте вузол після одного таймауту. Вузол, який постійно виходить та повертається, спричиняє шторм змін, оскільки кожна транзиція переміщує 1/N ключів. Перед видаленням необхідно, щоб протягом певного часового проміжку сталося кілька послідовних збоїв, а потім вузол слід обережно знову допустити до роботи. У наведеному вище прикладі використовується фіксована штрафна кінцева точка у десять секунд; у продакшн-коді слід використовувати експоненційне збільшення спроб та перевірку стану перед тим, як дозволити вузлу повернутися.

Гарячі ключі не збалансовані

Консистентне хешування рівномірно розподіляє ключі, але нічого не каже про запити. Коли певний продукт раптово стає надзвичайно популярним, його запис знаходиться на одному сервері, і цей сервер перегрівається, незважаючи на те, що система ефективно працює. Існують два рішення: невеликий кеш у межах процесу перед системою для найпопулярніших ключів або варіант обмежених навантажень консистентного хешування з досліджень Google, який обмежує кількість даних, що може обробити кожен вузол, та надсилає зайве у напрямку годинникової стрілки.

Перемапування — це не міграція

Усе вищесказане передбачає, що втрата ключа коштує лише пропуску з кешу. Якщо кільце передає стабільні дані, твердження „11% ключів переміщено“ означає, що 11% даних необхідно фізично скопіювати на новий вузол, перш ніж їх можна буде прочитати там; зазвичай читання або записування відбувається в обох місцях до завершення копіювання. Кільце визначає, що потрібно перемістити; воно саме по собі не здійснює процес переміщення. Саме тому системи на кшталт Vitess покладаються на координатор: їм потрібно керувати процесом міграції, а не лише її розраховувати.

Кількість реплік фактично є постійною

Зміна значення replicas з 160 на 500 змінює положення кожної позиції в кільці та перерозподіляє майже всі ключі, що спричиняє такі ж проблеми, як зміна модуля. Вважайте це одноразовим рішенням щодо проектування, прийнятим до того, як з’являться живі дані; якщо ви не впевнені, оберіть більше значення.

Коли кільце є неправильним інструментом

Частиною інженерного судження є здатність розпізнати, коли вражаюче рішення є неправильним.

  • Менше 30 вузлів: використовуйте алгоритм хешування типу rendezvous. Він потребує менше коду, краще збалансований та не вимагає налаштування кількості копій. Єдиною перевагою такого підходу є швидкість пошуку O(log N), яка при такому розмірі є майже незначною.
  • Обмінні контейнери, де змінюється лише кількість елементів: використовуйте алгоритм jump hash – для цього потрібно лише десять рядків коду та жодної пам’яті.
  • Дані, які мають залишатися стабільними, але потребують контрольованого переміщення: використовуйте координатора. Лише чіткий мапування дозволяє змінити окремий шард, водночас контролюючи наслідки цього, що неможливо зробити за допомогою алгоритмів хешування.
  • K, яке справді ніколи не змінюється: % N підійде. Не створюйте складну інфраструктуру для зміни, яка ніколи не відбудеться.

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

Основні висновки

  • Основна ідея проста: розміщувати ключі та сервери в одному просторі адрес, щоб зміна складу групи впливала лише на сусідні елементи, а не на все.
  • Модульне маршрутизування перетворює кожну подію масштабування та кожен збій вузла на майже повне очищення кешу, причому збитки зростають з розміром кластера.
  • Хешування типу „рендеву“ часто є кращим вибором для невеликих флотів; використовуйте кільцеву структуру, коли мають значення розмір, вагомість та довільне видалення елементів.
  • Без віртуальних вузлів один сервер може обробляти кілька разів більше даних, ніж йому належить. Виберіть кількість реплік заздалегідь, адже її зміна пізніше призведе до повної переробки всього.
  • Швидкий хеш із слабкою ефектом аваланчу може тихо відновити дисбаланс; завжди вимірюйте розподіл даних, а не лише швидкість.
  • Втрата одного вузла призводить до того, що близько 1/N запитів надсилаються до бази даних. Розмір бази даних слід підбирати з урахуванням цього, обережно змінювати склад груп учасників, видаляти вузли та окремо керувати „гарячими“ ключами.

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

    Пов’язана література

    Усі статтіНадіслати бриф