Hot keys і нерівномірне навантаження

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

Що таке hot key

Hot key — це ключ, до якого надходить непропорційно велика кількість запитів порівняно з іншими ключами.

Наприклад, сервіс зберігає перегляди публікацій:

text

post:101   120 запитів/сек
post:102    95 запитів/сек
post:103    80 запитів/сек
post:999  85000 запитів/сек

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

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

javascript

const requests = [
  "article:1",
  "article:2",
  "article:1",
  "article:3",
  "article:2",
  "article:42",
  "article:42",
  "article:42",
  "article:42",
  "article:42",
  "article:42",
  "article:42",
  "article:42",
  "article:42",
  "article:42",
  "article:4",
  "article:5",
  "article:5",
];

const counts = new Map();

for (const key of requests) {
  counts.set(key, (counts.get(key) ?? 0) + 1);
}

const values = [...counts.values()].sort((a, b) => a - b);

function median(numbers) {
  const middle = Math.floor(numbers.length / 2);

  if (numbers.length % 2 === 0) {
    return (numbers[middle - 1] + numbers[middle]) / 2;
  }

  return numbers[middle];
}

const medianRps = median(values);
const absoluteThreshold = 5;
const relativeThreshold = 4;

const hotKeys = [...counts.entries()]
  .filter(([key, count]) => {
    const exceedsAbsoluteThreshold = count >= absoluteThreshold;
    const exceedsRelativeThreshold = count >= medianRps * relativeThreshold;

    return exceedsAbsoluteThreshold || exceedsRelativeThreshold;
  })
  .sort((a, b) => b[1] - a[1]);

console.log("Кількість запитів за ключами:");
for (const [key, count] of counts) {
  console.log(`${key}: ${count}`);
}

console.log(`\nМедіанне навантаження: ${medianRps}`);
console.log("\nГарячі ключі:");

for (const [key, count] of hotKeys) {
  console.log(`${key}: ${count}`);
}

javascript

function bucketForRequest(requestId, bucketCount) {
  let hash = 0;

  for (const character of requestId) {
    hash = (hash * 31 + character.charCodeAt(0)) >>> 0;
  }

  return hash % bucketCount;
}

function keyForBucket(baseKey, bucket) {
  return `${baseKey}:${bucket}`;
}

function totalCounter(values) {
  return values.reduce((sum, value) => sum + value, 0);
}

const baseKey = "views:article:42";
const bucketCount = 4;
const requestId = "request-9281";

const bucket = bucketForRequest(requestId, bucketCount);
const physicalKey = keyForBucket(baseKey, bucket);

console.log(`Запит використовує: ${physicalKey}`);

const bucketValues = [120, 135, 118, 127];
console.log(`Загальне значення: ${totalCounter(bucketValues)}`);

Hot keys і нерівномірне навантаження

Що таке hot key

Чому звичайний хешинг не розв’язує проблему

Як виявляти hot keys

Лічильники запитів за ключем

Метрики, які варто збирати

Простий критерій аномалії

Приклад пошуку гарячих ключів

Стратегія 1: реплікація

Коли реплікація допомагає

Read-after-write і затримка реплікації

Обмеження реплікації

Стратегія 2: кешування

Стратегія 3: розподіл одного ключа між кількома підключами

Читання розділеного ключа

Переваги розподілу ключа

Недоліки

Стратегія 4: правильне шардування

Шардування за ідентифікатором

Шардування за діапазоном

Шардування з урахуванням навантаження

Стратегія 5: обмеження та деградація

Як вибрати стратегію

Гарячі читання, рідкі записи

Гарячі записи до лічильника

Гарячий об’єкт із частими повними оновленнями

Перевантажений шард через багато різних ключів

Практичний план впровадження

Типові помилки

Помилка: додати більше шард без аналізу ключів

Помилка: реплікувати primary і не розподілити читання

Помилка: використовувати випадковий salt для читання без збереження правил

Помилка: розділити ключ без плану агрегації

Помилка: ігнорувати cache stampede

Помилка: визначати hot key за середнім значенням

Помилка: не врахувати записи

Summary