Кешування CDN: LRU проти LFU при Реальному Zipf Трафіку

Чому взагалі існує CDN

Світло у волокні поширюється приблизно на дво третинах c, що встановлює твердий ліміт для затримки: від Нью-Йорка до Сіднея та назад це становить близько 160 мілісекунд, незалежно від того, наскільки швидкий ваш сервер. CDN вирішує цю проблему не шляхом підвищення швидкості основного сервера, а шляхом роблення його непотрібним для більшості запитів — воно розміщує периферійні кеші в сотнях фізичних локацій поблизу користувачів і маршрутизує кожен запит до найближчого за допомогою DNS або Anycast. Якщо контент вже знаходиться в цьому периферійному кеші, основний сервер взагалі не контактується.

Індекс попадання визначає економічну вигоду

Індекс попадання в кеш (cache hit rate) – це відношення кількості запитів, які обробляє крайній вузол (edge node) з власного сховища, – єдине число, яке визначає, чи виправдана експлуатація CDN. Відхилення (miss) означає, що крайній вузол повинен отримати дані з початкового сервера (origin) або батьківського кешу, сплативши повну затримку в обмінних шляхах, і вирішити, чи зберігати результат для наступного разу. Кожен кеш має обмежений обсяг пам’яті, тому коли він заповнений та надходить новий об'єкт, необхідно виключити (evict) один із існуючих – і саме, який об'єкт буде виключений, є ключовим питанням.

LRU: Релевантність як єдиний сигнал

Алгоритм LRU (Least Recently Used) зберігає об'єкти в порядку їх останнього доступу та видаляє той, який не використовувався найдовше. Реалізовано за допомогою подвійного зв’язного списку плюс хеш-мапи; як пошук, так і переміщення вузла на початок списку при потраплянні (hit) займають O(1):

при запиті(ключ): якщо ключ є в кеші: перемісти вузол[ключ] на початок списку // O(1) — релевантність оновлено поверни вузол[ключ].значення // ТРИМАЄСЯ інакше: якщо кеш заповнений: видали вузол в кінці // найхолодніший об'єкт, O(1) завантаж з вихідного джерела, встав вузол[ключ] на початок // НЕ ТРИМАЄСЯ LRU дешевий, простий і миттєво адаптується до змін популярності — учорашній вірусний відеоролик природним чином випадає, коли сьогоднішній бере його на себе. Його слабкість полягає в тому, що один доступ обробляється так само, як сто тисяч: великий об'єкт, за richiestій один раз (пауер-скрейпер, який переглядає каталог, або хтось прокручує відео) може вимити популярний контент з кешу лише тому, що він був торкався найнещодавніше — це режим відмови, зазвичай називається забрудненням кеша або відмова від сканування.

on request(key):
  if key in cache:
    move node[key] to front of list        // O(1) — recency updated
    return node[key].value                 // HIT
  else:
    if cache is full: evict node at back    // the coldest item, O(1)
    fetch from origin, insert node[key] at front   // MISS

LFU: частота як сигнал замість

Найменш використовуваний алгоритм вимикання зберігає лічильник попадалень для кожного об'єкта та вимикає той, що має найнижчий показник, зазвичай реалізований з використанням хеш-мапи плюс міні-куща або списку кошиків, відсортованого за частотою, для операцій O(1) або O(log n). Він протидіє проблемі одноразового сканування, яка шкодить LRU – об'єкт, який був надзвичайно популярним минулого тижня, але зараз неактуальний, може утримувати високий лічильник і відмовлятися від вимикання, постійно займаючи місце, необхідне для нового популярного контенту. У виробничих системах майже завжди додають занепад – періодично зменшують всі лічильники вдвічі або використовують вагу, що базується на нещодавності та частоті (сім'я LRU-K та ARC, а також приблизно-LFU Redis з логарифмічними лічильниками та часовим розкладом затухання є спробами поєднати два сигнали замість того, щоб вибрати один).

Чому розподіл Зіпа, а не рівномірний трафік, змінює все

Реальний трафік запитів до CDN не розподілений рівномірно по контенту – він слідує за розподілом Зіпа: якщо сортувати об’єкти за популярністю, частота запитів до k-го ранжованого об’єкта пропорційна 1/k^s для деякого параметра нахилу s (s = 1 є класичним законом Зіпа; виміряний веб-трафік і трафік відео зазвичай становить приблизно s = 0.6–0.9),

частота(ранг k) ∝ 1 / k^s

s = 1.0, верхній 1% об’єктів → несе приблизно 60-70% усіх запитів,

s = 1.0, верхній 10% об’єктів → несе приблизно 90%+ всіх запитів

Це вся причина, чому працює кешування на рівні Інтернету: оскільки невелика група надзвичайно популярного контенту відповідає за переважну більшість запитів, кеш, що містить лише 1-5% від загального каталогу об’єктів, може досягти коефіцієнту попадання понад 80% – за умови, що політика виключення дійсно підтримує присутність цієї групи. При розподілі трафіку Зіпа LFU схиляється до кращої продуктивності в порівнянні з LRU щодо коефіцієнта попадання саме тому, що він безпосередньо відстежує кількість (частоту), яку визначає нахил трафіку Зіпа; LRU все ще може добре працювати, оскільки популярні об’єкти також схильні до нещодавніх запитів, але він більш чутливий до забруднення від холодних сканувань через довгий хвіст.

frequency(rank k)  ∝  1 / k^s

s = 1.0, top 1% of objects  →  carries roughly 60-70% of all requests
s = 1.0, top 10% of objects →  carries roughly 90%+ of all requests

Час життя (TTL) та вилучення з кешу: інша частина проблеми

Оцінка відвідуваності окремо не дає повної картини — кешований об'єкт також має Час Життя, після якого він вважається застарілим і потребує перевірки з вихідного джерела (за допомогою умовного запиту з використанням заголовків ETag або Last-Modified), навіть якщо його не було вилучено з кешу. Якщо задати занадто великий TTL, користувачі будуть бачити застаріле вміст після зміни в вихідному джерелі; якщо задати занадто малий TTL, відвідуваність різко знизиться, оскільки об'єкти закінчать термін свого життя до того, як вони будуть використані. Відоме твердження Філа Карлтона — «в комп’ютерних науках є лише дві складні речі: вилучення з кешу та назва речей» — безпосередньо стосується цієї компромісної ситуації, і виробничі CDN витрачають величезні зусилля інженерів на швидкі API очищення та стратегії перевірки під час оновлення, тому що неправильний вибір TTL в будь-якому напрямку є дороговартісним.

Многоуровневе кешування: крайній, регіональний, захисний рівень

Одиночний шар кешу на краю одночасно отримує всі відсутні дані та безпосередньо атакує вихідний сервер (проблема «громового стада», яка часто виникає після глобального очищення кешу або раптового стрибка трафіку), тому великі CDN вставляють проміжний рівень – регіональні або захисні кеші – між сотнями крайніх вузлів та вихідним сервером. Відсутність даних на крайньому вузлі спочатку перевіряється у захисному кеші; лише відсутність даних у захисному кеші досягає вихідного сервера. Це перетворює сотні одночасних запитів до вихідного сервера на не більше ніж один для кожного унікального об'єкта в регіоні, і це той самий ієрархічний принцип, що й L1/L2/L3 кеш CPU, але в масштабі Інтернету та з латентністю мережі, яка замінює латентність пам’яті.

Часті запитання

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

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