Пошук уроків, статей та іншого контенту
Порівняєте LRU, LFU, FIFO та інші політики витіснення й оціните вплив обмеження пам’яті.
Кеш має обмежений обсяг пам’яті, тому він не може зберігати всі об’єкти безкінечно. Коли кеш заповнений і потрібно додати новий об’єкт, він має видалити один або кілька наявних об’єктів.
Стратегія витіснення визначає, який саме об’єкт потрібно видалити.
Типовий цикл роботи кешу:
Система отримує ключ.
Якщо ключ є в кеші, відбувається cache hit.
Якщо ключа немає, відбувається cache miss.
Дані завантажуються з повільнішого джерела.
Дані додаються до кешу.
Якщо вільного місця немає, один з об’єктів витісняється.
Якість політики витіснення зазвичай оцінюють за такими показниками:
hit rate — частка запитів, знайдених у кеші;
miss rate — частка запитів, яких не було в кеші;
кількість витіснень;
використана пам’ять;
час виконання операцій;
передбачуваність затримки.
Формули для hit rate і miss rate:
hit rate = cache hits / total requests
miss rate = cache misses / total requestsОскільки кожен запит є або влучанням, або промахом:
miss rate = 1 - hit rateLRU витісняє об’єкт, до якого найдовше не зверталися.
Ідея ґрунтується на часовій локальності: якщо об’єкт використовували нещодавно, є ймовірність, що він знадобиться знову.
Приклад. Кеш має місткість 3:
Запити: A B C A DПісля перших трьох запитів:
[A, B, C]Після повторного звернення до A порядок використання змінюється:
[B, C, A]Коли надходить D, найдавніше використаний об’єкт — B, тому він витісняється:
[C, A, D]добре працює для багатьох вебзапитів;
враховує актуальність даних;
проста для пояснення;
ефективна, коли запити мають часову локальність.
потрібно оновлювати порядок після кожного звернення;
реалізація потребує додаткової пам’яті;
послідовне читання великого набору даних може «вимити» корисні об’єкти;
один об’єкт, до якого звернулися один раз, може витіснити часто використовувані об’єкти.
У типовій реалізації для операцій за O(1) використовують хеш-таблицю разом із двозв’язним списком.
LFU витісняє об’єкт із найменшою кількістю звернень.
Для кожного ключа кеш зберігає лічильник використання:
A: 10 звернень
B: 2 звернення
C: 5 зверненьЯкщо потрібно звільнити місце, першим кандидатом буде B.
зберігає об’єкти, які стабільно часто використовуються;
добре підходить для довготривалих «гарячих» даних;
менш чутливий до коротких сплесків активності, ніж LRU.
старі об’єкти можуть залишатися в кеші через великий історичний лічильник;
нові, але перспективні об’єкти можуть витіснятися занадто рано;
потрібно зберігати й оновлювати лічильники;
часто потрібне старіння лічильників або віконна статистика.
Наприклад, сторінка була дуже популярною вчора, але сьогодні більше не використовується. Її високий лічильник може надовго затримати її в кеші.
Тому практичні реалізації LFU часто зменшують старі лічильники з часом або враховують частоту лише за певний часовий інтервал.
FIFO витісняє об’єкт, який найдовше перебуває в кеші, незалежно від кількості звернень до нього після додавання.
Приклад:
Запити: A B C A DКеш місткістю 3 після запиту A має чергу:
[B, C, A]Під час додавання D буде витіснено B, оскільки він був доданий першим серед об’єктів, що залишилися.
проста реалізація;
невеликі витрати на метадані;
передбачувана поведінка;
підходить, коли новизна даних важливіша за частоту доступу.
не враховує звернення після додавання;
може витіснити дуже популярний об’єкт;
за деяких шаблонів доступу може працювати гірше за LRU.
FIFO часто реалізують за допомогою черги: нові об’єкти додаються в кінець, а витісняються з початку.
Розглянемо кеш місткістю 3 і послідовність:
A B C A B D A B C DПолітики реагуватимуть по-різному:
LRU враховує останні звернення;
LFU враховує кількість звернень;
FIFO враховує лише час додавання.
Для такої послідовності A і B використовуються часто, тому LFU може довше їх зберігати. LRU також зазвичай збереже їх, якщо між зверненнями немає надто великої кількості інших ключів. FIFO може витіснити їх лише тому, що вони були додані раніше.
Нижче наведено невеликий симулятор. Він порівнює FIFO, LRU та LFU на одній послідовності запитів.
from collections import OrderedDict, deque
class FIFOCache:
def __init__(self, capacity):
self.capacity = capacity
self.items = {}
self.order = deque()
def get(self, key):
if key in self.items:
return self.items[key]
return None
def put(self, key, value):
if key in self.items:
self.items[key] = value
return
if len(self.items) >= self.capacity:
oldest_key = self.order.popleft()
del self.items[oldest_key]
self.items[key] = value
self.order.append(key)
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.items = OrderedDict()
def get(self, key):
if key not in self.items:
return None
# Переміщуємо нещодавно використаний ключ у кінець.
value = self.items.pop(key)
self.items[key] = value
return value
def put(self, key, value):
if key in self.items:
self.items.pop(key)
elif len(self.items) >= self.capacity:
self.items.popitem(last=False)
self.items[key] = value
class LFUCache:
def __init__(self, capacity):
self.capacity = capacity
self.values = {}
self.frequencies = {}
self.order = {}
self.counter = 0
def get(self, key):
if key not in self.values:
return None
self.frequencies[key] += 1
self.counter += 1
self.order[key] = self.counter
return self.values[key]
def put(self, key, value):
if key in self.values:
self.values[key] = value
self.frequencies[key] += 1
self.counter += 1
self.order[key] = self.counter
return
if len(self.values) >= self.capacity:
key_to_remove = min(
self.values,
key=lambda item: (self.frequencies[item], self.order[item])
)
del self.values[key_to_remove]
del self.frequencies[key_to_remove]
del self.order[key_to_remove]
self.counter += 1
self.values[key] = value
self.frequencies[key] = 1
self.order[key] = self.counter
def simulate(cache, requests):
hits = 0
for key in requests:
if cache.get(key) is not None:
hits += 1
else:
# У реальній системі тут було б завантаження даних із джерела.
cache.put(key, f"value:{key}")
return hits
requests = ["A", "B", "C", "A", "B", "D", "A", "B", "C", "D"]
capacity = 3
caches = {
"FIFO": FIFOCache(capacity),
"LRU": LRUCache(capacity),
"LFU": LFUCache(capacity),
}
for name, cache in caches.items():
hits = simulate(cache, requests)
hit_rate = hits / len(requests)
print(f"{name}: hits={hits}, hit_rate={hit_rate:.2f}")Цей приклад спрощений:
значення мають однаковий розмір;
немає TTL;
немає паралельних запитів;
промах одразу додає значення в кеш;
немає окремого стану для «ключ відсутній» і «значення дорівнює None».
У реальній системі політику потрібно оцінювати на реальних або репрезентативних трасах запитів.
MRU витісняє об’єкт, до якого зверталися найнещодавніше.
На перший погляд це суперечить інтуїції, але така політика може бути корисною для специфічних шаблонів доступу. Наприклад, якщо після читання елемент майже напевно більше не знадобиться, немає сенсу зберігати його як «гарячий».
MRU не є універсальною заміною LRU. Її варто використовувати лише тоді, коли поведінка доступу добре відома й підтверджена вимірюваннями.
Random replacement випадково вибирає об’єкт для видалення.
Переваги:
дуже проста реалізація;
мало метаданих;
немає витрат на підтримку порядку доступу;
може бути корисною в системах, де точне відстеження доступів занадто дороге.
Недолік очевидний: політика не використовує інформацію про популярність або давність об’єктів. Її поведінка може бути нестабільною, тому зазвичай її порівнюють із іншими стратегіями під час тестування.
TTL визначає, як довго об’єкт може залишатися дійсним. Це політика терміну життя, а не обов’язково політика вибору жертви при заповненні кешу.
Наприклад, кеш може одночасно використовувати:
LRU для вибору об’єкта при нестачі місця;
TTL для автоматичного видалення застарілих значень.
Розглянемо два різні випадки:
Об’єкт досяг TTL — він більше не повинен використовуватися, навіть якщо кеш не заповнений.
Кеш заповнений — потрібно вибрати об’єкт для витіснення, навіть якщо всі об’єкти ще не прострочені.
Тому TTL і LRU часто комбінують, але вони вирішують різні задачі.
Місткість кешу безпосередньо впливає на hit rate, але збільшення пам’яті не завжди дає пропорційний результат.
Якщо кеш значно менший за робочий набір даних:
об’єкти часто витісняються;
hit rate низький;
збільшується кількість запитів до основного сховища;
зростає навантаження на базу даних або зовнішній сервіс.
Робочий набір — це набір даних, до якого система регулярно звертається протягом певного періоду.
Якщо кеш може вмістити більшу частину часто використовуваних даних:
hit rate зазвичай зростає;
зменшується кількість дорогих промахів;
подальше збільшення кешу може мати менший ефект.
Занадто великий кеш теж має ціну:
потрібна дорожча інфраструктура;
збільшується вартість пам’яті;
зростає час прогрівання після запуску;
потрібно більше пам’яті для метаданих;
помилки конфігурації можуть призвести до тиску на пам’ять.
Розмір кешу потрібно обирати на основі вимірювань, а не лише припущення.
Обмеження кешу стосується не лише самих значень. Реальне споживання пам’яті включає:
ключі;
значення;
службові структури;
лічильники частоти;
часові мітки;
покажчики або зв’язки між елементами;
накладні витрати самого середовища виконання.
Якщо значення мають різний розмір, кеш із лімітом «1000 елементів» може поводитися непередбачувано з погляду пам’яті. Тисяча маленьких рядків і тисяча великих JSON-документів — це зовсім різне навантаження.
У системах із неоднорідними об’єктами корисніше контролювати:
загальний обсяг у байтах;
кількість елементів;
або обидва обмеження одночасно.
Наприклад:
максимум 100 000 елементів
і не більше 2 ГБ пам’ятіВитіснення може запускатися, якщо порушено хоча б один із лімітів.
важливі нещодавні звернення;
доступ має часову локальність;
популярність об’єктів може швидко змінюватися;
потрібна зрозуміла універсальна стратегія.
є стабільно популярні об’єкти;
важливо зберігати часті звернення протягом тривалого часу;
ви можете коректно обробляти старіння лічильників.
потрібна дуже проста політика;
об’єкти зазвичай корисні приблизно однаковий час;
не потрібно відстежувати кожне звернення.
доступ має спеціальний шаблон;
нещодавно використані об’єкти часто більше не потрібні;
рішення підтверджене тестуванням.
важлива простота;
витрати на підтримку метаданих критичні;
випадкова поведінка прийнятна.
Універсально найкращої політики не існує. Одна й та сама стратегія може мати різні результати для різних послідовностей запитів.
Перед вибором політики варто зібрати або змоделювати трасу запитів:
час, ключ, розмір значення, результат запитуПотім прогнати однакову трасу через кілька політик і порівняти:
hit rate;
miss rate;
кількість витіснень;
середню й максимальну затримку;
використання пам’яті;
поведінку під час пікових навантажень.
Важливо перевіряти не лише середній результат. Наприклад, стратегія може мати хороший середній hit rate, але створювати значні затримки під час зміни робочого набору.
Також потрібно оцінювати поведінку після:
запуску системи;
очищення кешу;
масового оновлення даних;
різкої зміни популярності ключів;
тимчасової недоступності основного джерела.
LRU часто є хорошим початковим вибором, але її результат залежить від шаблону доступу. Послідовне читання великого обсягу даних може витіснити об’єкти, які потрібні для іншого трафіку.
Порівняння має виконуватися за однакових умов:
одна місткість;
одна послідовність запитів;
однакові правила додавання;
однакове трактування промахів.
Інакше результат не покаже різницю між самими політиками.
Ліміт у кількості ключів не гарантує контрольованого використання пам’яті, якщо значення мають різний розмір.
TTL видаляє прострочені об’єкти, а політика витіснення визначає, що видалити через нестачу місця. Це можуть бути окремі механізми.
Історично популярний об’єкт може назавжди отримати перевагу над новими об’єктами. Для динамічних даних потрібно враховувати актуальність частоти.
Влучання в кеш не завжди означає малу затримку. Значення може бути великим, десеріалізація — дорогою, а кеш — перевантаженим. Потрібно вимірювати також затримку та споживання ресурсів.
Стратегія витіснення визначає, який об’єкт видалити, коли кеш заповнений.
LRU видаляє найдавніше використаний об’єкт і часто є хорошим базовим вибором.
LFU видаляє найрідше використовуваний об’єкт і підходить для стабільно популярних даних.
FIFO видаляє найстаріший доданий об’єкт і має просту реалізацію.
MRU та Random корисні для специфічних сценаріїв.
TTL і політика витіснення вирішують різні задачі та можуть працювати разом.
Обмеження пам’яті впливає не лише на кількість елементів, а й на розмір значень та службові метадані.
Політику потрібно вибирати за реальним шаблоном доступу й перевіряти вимірюваннями.