Кешування в Python. Мистецтво памʼятати лише потрібне
Гарна пам’ять — це та, яка навчена забувати дрібниці.
Кліфтон Фадіман
Привіт усім шукачам істини. Це остання частина серії статей про памʼять в Python, і сьогодні поговоримо про мистецтво памʼтати лише потрібне — кешування. Коли код працює правильно, але все ще не так швидко, як хотілося б — це означає, що настав час замислитись не над тим, що ми рахуємо, а як часто. Саме тут і починається історія кешування — одного з найелегантніших способів змусити програму памʼятати те, що нам необхідно, та забувати зайве, не захаращуючи такий цінний простір.
У минулих статтях ми вже обговорювали анатомію памʼяті в Python, розглядали, як він працює з копіями та до чого це може призвести, виходили за межі звичних Python-based практик. Тут візьмемо інший вектор і обговоримо таку атомарну тему як кешування. Аля у будь-якому разі осмислення вже розглянутих тем дасть ширше розуміння поточної, тож перш за все раджу прочитати минулі частини серії.
Частина 1. Анатомія памʼяті в Python. З чого починається оптимізація
Частина 2. Фрагменти й копії. Як Python марнує памʼять
Частина 3. Поза межами Python. Шлях до швидкодії, що дихає на C
Уявімо, що ти щодня ходиш у кав’ярню біля дому. Першого разу бариста запитує: «Яку каву будете?». Ти відповідаєш: «Лате з вівсяним молоком, будь ласка». Наступного ранку — та сама історія. І через день, і через тиждень. Поки одного разу бариста не каже: «Лате з вівсяним молоком, як завжди?». Це й є кешування у чистому вигляді.
Бариста просто зберігає інформацію про наш попередній запит і використовує її замість повторних уточнень. Те саме відбувається в програмах: замість того, щоб знову виконувати обчислення чи отримувати дані з повільного джерела, ми можемо зберегти результат і використати його наступного разу.
👉 Теорія кешування
Мемоізація vs табуляція
Механізми TTL та політики видалення
👉 Розмір кешу
Розмір робочого набору
Кеш теплової області
👉 Кешування як архітектурний підхід
Консистентність та інвалідація
👉 Висновки
Теорія кешування
Кешування — це техніка, що подібно баристі, котрий запамʼятав наше минуле замовлення, зберігає результат, коли програма виконує складну операцію — наприклад, читає дані з бази, обробляє файл чи робить запит до API. Якщо з таким самим запитом система зустрінеться вдруге, вона просто поверне вже збережений результат. По суті, це тимчасова пам’ять між джерелом даних і споживачем, яка дозволяє зменшити затримки та навантаження на систему.
І хоч концепція виглядає простою, від ефективності кешу часто залежить «відчуття швидкості» системи — як у веббраузері, що відкриває сторінку без затримки, або у функції Python, яка повертає відповідь миттєво, бо вже робила це раніше, — кеш може бути застосований на різних рівнях системи.
Кешування — це різниця між «зберегти» і «не перераховувати». Воно як таке не прискорює самі обчислення й існує не для збереження даних — воно прибирає повтори. Завдяки цьому програма реагує швидше, хоча під капотом просто обходить дорогу частину шляху.
У цьому й полягає його філософія: результат одного обчислення може стати коротким шляхом для наступного. Саме через це мені найбільше подобається слово «запамʼятати» в контексті кешу, бо воно краще відображає сутність підходу, адже ціль саме запамʼятати, а не зберегти.
Що цікаво, така ідея запамʼятовування інформації — дуже давня, вона з’явилася задовго до появи комп’ютерів, це пряме відображення того, як математики оптимізовували рекурсивні обчислення задовго до того, як алгоритми стали кодом.
Мемоізація vs табуляція
Насправді у класичних алгоритмах існує дві фундаментальні техніки, які лягли в основу сучасного кешування в програмуванні: мемоізація (англ. memoization, від memorandum — «те, що варто запам’ятати») та табуляція (англ. tabulation). Обидві вони виникли в контексті динамічного програмування — підходу, який дозволяє розв’язувати складні задачі коштом збереження результатів підвищеної вартості.
Проте в їхній природі закладені різні способи мислення про кеш: «зверху вниз» і «знизу вгору».
Мета мемоізації проста, але елегантна: усунути повторні обчислення в рекурсивних алгоритмах. Це особливо помітно у задачах, де існує значна кількість повторюваних кроків, як-от пошук шляхів у дереві, обчислення сум уздовж гілок, визначення кількості маршрутів у графі, підрахунок чисел Фібоначчі.
У реалізації алгоритм «рухається зверху», тобто починає з вихідної задачі й поступово спускається до менших підзадач. Перевага мемоізації в тому, що вона динамічно адаптується: зберігає лише ті підзадачі, які реально виникли. Це робить її ефективною для структур, де шляхи нерівномірні або обчислення відбуваються вибірково.
Я багато разів використовувала приклад з числами Фібоначчі у минулих статтях навмисно без оптимізацій, бо так часто краще можна показати різницю швидкодії чи споживання памʼяті, от нарешті настав час його оптимізувати, і кешування у цьому допоможе як ніколи.
Тож у класичному прикладі з числами Фібоначчі кожне значення fib(n) викликає два підзапити — fib(n-1) і fib(n-2). Без кешування ці виклики створюють ціле дерево повторів: fib(5) викликає fib(4) і fib(3), але fib(4) знову викликає fib(3) — і так далі.
Тобто функція обчислює ті самі значення знову і знову, лише тому, що не пам’ятає попередніх. Мемоізація розв’язує це просто: ми створюємо «пам’ять» — таблицю відповідностей між аргументом і результатом — і якщо функція викликається повторно з тим самим аргументом, вона не рахує знову, а повертає записане.
У математичному сенсі мемоізація спирається на властивість детермінованості: якщо функція f(x) завжди повертає однакове y для даного x, її можна кешувати без ризику. Такі функції називають чистими (англ. pure functions). По факту це є функціонал, на який не впливають якісь сторонні ефекти (англ. side effects), що можуть зашкодити отриманню однакового результату при однакових вхідних даних.
Найпростіша та найефективніша реалізація кешу — звичайний словник. Коли функція викликається повторно, інтерпретатор спершу перевіряє, чи є результат у словнику: якщо так — одразу повертає його, без повторних обчислень.
Швидкість словника базується на хеш-таблиці, тож доступ до елемента у середньому має O(1). Це амортизована складність: за нормального розподілу хешів колізії рідкісні. У гіршому випадку, коли всі ключі потрапляють в одну «комірку», пошук деградує до O(n). Але на практиці словник майже завжди працює за сталий час, тому це чудовий варіант для простого кешу: знайти готовий результат коштує стільки ж, скільки перевірити наявність ключа.
Але загальна часова складність цього рішення O(n), тобто лінійна, бо функція фактично будує таблицю fib(0)...fib(n), підраховуючи кожне значення один раз. На відміну від простого варіанту реалізації «в лоб», де маємо аж O(2ⁿ) - експоненційну складність, оскільки фактично в нас T(n) = T(n-1) + T(n-2) ... T(n-m) + O(1), варіант з кешуванням значно оптимальніший.
Подивимося, як це працює на практиці, розглянувши результати на прикладі підрахунку чисел Фібоначчі. Звичайна реалізація:
def compute_fib_plain(n: int) -> int: if n <= 1: return n return compute_fib_plain(n - 1) + compute_fib_plain(n - 2)
Реалізація з використанням кешу:
cache = {}
def compute_fib_cached(n: int) -> int:
if n <= 1:
return n
if n not in cache:
cache[n] = compute_fib_cached(n - 1) + compute_fib_cached(n - 2)
return cache[n]
Функція для заміру продуктивності:
from typing import Callable
import time
from memory_profiler import memory_usage
def measure(task_func: Callable, n: int):
start = time.perf_counter()
mem_usage = memory_usage(
(task_func, (n,), {}),
interval=0.01,
max_usage=True,
retval=False,
)
end = time.perf_counter()
print(f'Час: {end - start:.4f} с')
print(f'Памʼять: {mem_usage:.2f} MB')
Для більш-менш великого значення 50 я отримала такі результати:
Без кешування: Час: 1263.2324 с Памʼять: 101.78 MB З кешуванням: Час: 3.2323 с Памʼять: 102.19 MB
Результати показують прірву між двома підходами. Звичайна рекурсія працює експоненційно: щоб дістатися Fib(50), вона перебирає мільйони однакових підвиразів, тому час вимірюється вже не секундами, а десятками хвилин. Кешована версія робить цю саму роботу всього один раз для кожного n, тому обчислення упираються в лінійну швидкість.
Цікаво, що споживання памʼяті у двох варіантів майже однакове. І це логічно: рекурсія витрачає памʼять на глибокий стек викликів, а мемоізація — на словник із результатами. У сумі виходить схожа цифра, хоча природа цих витрат різна. Але виграш у швидкості настільки сильний, що кешування буквально перетворює алгоритм з майже непридатного для великих значень на цілком робочий.
Табуляція використовує протилежний підхід. Замість рекурсії — ітерація, замість «запам’ятати коли потрібно» — «заповнити все наперед».
Якщо у минулому підході ми починали з визначення основної проблеми та її розбиття на менші підпроблеми, тут алгоритм починає із найпростішої форми задачі та поступово формує таблицю або матрицю значень, де кожен елемент залежить від попередніх. Коли приходить час отримати остаточний результат — він уже є в таблиці, без необхідності повторних обчислень.
Табуляція особливо ефективна у задачах, які можна чітко розбити на впорядковані рівні підпроблем. Однак у складніших структурах — наприклад, великих графах з багатьма варіантами зв’язків — обсяг пам’яті, необхідний для побудови таблиці, швидко росте, а сама ініціалізація стає дорожчою за рекурсію з мемоізацією.
Поглянемо, як це працює на практиці:
def compute_fib_tabulated(n: int) -> int: if n <= 1: return n table = [0] * (n + 1) table[1] = 1 for i in range(2, n + 1): table[i] = table[i - 1] + table[i - 2] return table[n]
У результаті маємо:
Час: 3.2585 с Памʼять: 102.08 MB
Табуляція показує результат, дуже близький до версії з мемоізацією: час на рівні кількох секунд і практично така сама кількість використаної памʼяті. Це очікувано, адже обидва підходи виконують рівно n кроків і тримають у памʼяті лінійну кількість проміжних значень. Різниця лише в підході, а точніше «напрямку» побудови значень: для мемоізації — «зверху вниз», для табуляції — «знизу вгору», але з точки зору продуктивності вони поводяться майже однаково.
Механізми TTL та політики видалення
Кеш не може жити вічно. Памʼять обмежена, а дані старішають. Тому кожен кеш має мати відповідь на два запитання. Перше — коли саме значення стає неактуальним? Друге — що саме треба видалити, коли місця більше немає?
Один зі способів контролювати актуальність — механізм часу існування кешу (англ. time-to-live, абрев. TTL). Кожен запис у кеші отримує свій «термін придатності». Поки час не сплив, значення вважається свіжим, і його можна повертати без додаткових обчислень. Коли TTL закінчується, запис або видаляється негайно, або позначається простроченим і оновлюється під час наступного запиту. Це доволі корисно, бо дані, що живуть надто довго, майже завжди втрачають свою користь, і з цим треба щось робити.
from typing import Callable
import time
from functools import wraps
def ttl_cache(ttl_seconds: float) -> Callable:
def wrap(func: Callable) -> Callable:
cache = {}
@wraps(func)
def inner(*args, **kwargs) -> dict:
key = (args, tuple(sorted(kwargs.items())))
now = time.time()
if key in cache:
expires_at, value = cache[key]
if now < expires_at:
print('Значення взято з кешу')
return value
else:
print('Значення протермінувалося, оновлюємо')
print('Значення не знайдено - викликаємо функцію')
value = func(*args, **kwargs)
cache[key] = (now + ttl_seconds, value)
return value
return inner
return wrap
@ttl_cache(ttl_seconds=2.0)
def fetch_user_profile(user_id: int) -> dict:
time.sleep(1) # імітуємо повільний запит
return {'user_id': user_id, 'status': 'active'}
print(fetch_user_profile(1))
print(fetch_user_profile(1))
time.sleep(2.1)
print(fetch_user_profile(1))
Отримуємо:
Значення не знайдено — викликаємо функцію
Значення не знайдено - викликаємо функцію
{'user_id': 1, 'status': 'active'}
Значення взято з кешу
{'user_id': 1, 'status': 'active'}
Значення протермінувалося, оновлюємо
Значення не знайдено - викликаємо функцію
{'user_id': 1, 'status': 'active'}
Результати говорять самі за себе: ми бачимо всю історію змін у кеші та повторних викликів функції. Щойно життя значення закінчується, його замінює новоотримане за допомогою повторного підрахунку.
Найгірше в цьому всьому те, що в Python немає вбудованих механізмів, що працювали б з TTL. Максимум, що може допомогти у цьому питанні, це cachetools.TTLCache, але він не вбудований.
За допомогою цього інструменту ми можемо створити словник з «годинником» на кожному ключі. Далі це можна використовувати як декоратор @cached.
import time
from cachetools import TTLCache, cached
user_cache = TTLCache(maxsize=128, ttl=2)
@cached(cache=user_cache)
def expensive_operation(x: int) -> int:
print(f'Обчислення {x}*{x}')
time.sleep(1) # імітація довгої роботи
return x * x
print('Перший виклик', expensive_operation(10))
print('Другий виклик (кешований)', expensive_operation(10))
print('Чекаємо, поки TTL вийде з ладу')
time.sleep(2.2)
print('Третій виклик (з заекспайреним TTL)', expensive_operation(10))
За результатами бачимо, що обчислення повторюється, коли TTL експайриться.
Обчислення 10*10 Перший виклик 100 Другий виклик (кешований) 100 Чекаємо, поки TTL вийде з ладу Обчислення 10*10 Третій виклик (з заекспайреним TTL) 100
TTLCache дійсно реалізує механізм TTL, але робить це у спосіб, який відрізняється від того, що зазвичай очікують від «повноцінного» time-based кешу. Кожному ключу при вставці призначається момент завершення життя: фактично зберігається пара «значення + час, коли воно має видалится».
Саме цей момент є критичним: TTL у TTLCache працює ліниво. Ніхто не перевіряє ключі на фоні, вони не зникають самі по собі, і кеш не живе окремим внутрішнім циклом. Уся логіка TTL активується лише тоді, коли ми читаємо або записуємо ключ.
Сучасні кеші на кшталт Redis, Memcached чи in-memory cache у фреймворках часто мають активний механізм очищення: ключ може зникнути навіть тоді, коли ми взагалі не чіпаємо кеш. TTLCache цього не робить. Якщо ключ «помер», але ми його не читаємо — він продовжує лежати у пам’яті до наступного доступу, і тільки після цього буде видалений.
Інших інструментів для легкого повсякденного використання, на жаль, немає. Звісно, існують такі вбудовані механізми в flask-caching, Django Cache Framework, в Redis та Memcached, або ж більш вузькі — expiringdict та diskcache тощо, але якщо казати про інструмент, що завжди під рукою, — на жаль, це хіба що власна реалізація, або ж TTLCache.
Але навіть із TTL кеш усе одно переповнюється, і тоді вступають у гру політики видалення, або як по-іншому це називають, — евікція в кеші. Це механізми примусового видалення елементів тоді, коли кеш досягає свого ліміту.
У сучасних системах найчастіше зустрічаються кілька підходів, коротко розглянемо кожен.
- TTL (time-to-live). Уже розглянутий концепт, де кожен запис живе певний час. Поки TTL не сплив, значення вважається свіжим. Після — видаляється або переобчислюється. Добре працює там, де дані регулярно змінюються або швидко старіють.
- LRU (Least Recently Used). Видаляємо те, до чого давно не зверталися. Логіка проста: якщо ключ довго лежав без дії, він, скоріш за все, більше не потрібен. Це найпрактичніша політика у загальних системах.
- LFU (Least Frequently Used). Видаляється те, що використовували найрідше. Якщо деякі дані стабільно популярні, вони гарантовано залишаються у кеші. Підходить для систем зі «сталим попитом».
- FIFO (First In, First Out). Першим видаляється найстаріший елемент, незалежно від того, наскільки часто або недавно його використовували, тобто механіка черги. Добре для потокових даних, де важливі «свіжі» значення.
- MRU (Most Recently Used). Навпаки: видаляємо те, що використовували щойно. Застосовується рідко, але підходить у сценаріях, де повторні звернення малоймовірні.
Найпоширеніша стратегія — LRU. Вона покладається на інтуїтивне правило: якщо значення давно не використовували, швидше за все, воно не потрібне. Кеш відстежує порядок звернень, і коли потрібно звільнити місце, видаляє той запис, до якого зверталися найдавніше.
Python уже має LRU-кеш у стандартній бібліотеці — це functools.lru_cache. Подивимося його на прикладі: до вже написаної попередньо звичайної реалізації підрахунку чисел Фібоначчі compute_fib_plain допишемо декоратор:
from functools import lru_cache @lru_cache(maxsize=16) def compute_fib_plain(n: int) -> int: …
Результат:
Час: 3.2256 с Памʼять: 102.30 MB
Результат показує, що LRU-кеш фактично перетворив звичайну експоненційну рекурсію Фібоначчі на майже лінійну, як ми й розглядали попередньо. Попри дуже малий розмір кешу (лише 16 значень), цього достатньо, щоб зберегти всі проміжні fib(n), потрібні для обчислення fib(50).
Під капотом він тримає звичайний словник, який відповідає за миттєвий доступ до значень за ключем, і двозв’язний список, який стежить за тим, наскільки недавно кожен ключ використовували.
Коли функцію викликають повторно з тими самими аргументами, lru_cache повертає значення напряму зі словника, а коли кеш переповнюється, декоратор видаляє той елемент, який не використовували найдовше — просто витягує перший вузол двозв’язного списку. Усі ці операції — O(1), тому механізм швидкий і «дешевий».
Розмір кешу
Таким чином ми підійшли до питання розміру кешу. Кеш у Python живе у купі (англ. heap), там же, де розташована більшість об’єктів. Коли ми кешуємо значення, Python фактично створює нові об’єкти (числа, словники, кортежі), розкладає їх у купі й повʼязує між собою через посилання — звичайний процес алокацій, що ми вже розглядали в минулих частинах серії, бо це такі самі обʼєкти Python.
Відповідно лічильник посилань, поведінка збирача сміття (англ. garbage collector, абрев. GC) і інші частини життєвого циклу обʼєкта в памʼяті та механізмів його видалення залишаються незмінними.
Головний ефект кешування в тому, що воно змушує Python зберігати дані довше. Для Python це просто ще одна додаткова структура, яка нічим не відрізняється від «основних», що використовуються в програмі, але з точки зору програми — це спосіб зменшити кількість роботи, переклавши її частину на час життя об’єктів.
У кешуванні завжди є тиха угода, яку ми укладаємо із системою: або ми витрачаємо більше пам’яті, щоб зекономити час, або економимо памʼять, але гальмуємо на обчисленнях. Це той самий «time vs space trade-off», тільки з Python-об’єктами.
І тут постає питання, як обрати найоптимальніший розмір кешу, щоб балансувати між цими двома шальками терезів. Вибір розміру кешу це радше зважування того, що в нас закінчиться першим: памʼять чи терпіння :). Універсальної цифри немає, але є природні орієнтири, які допомагають не помилитися з вибором значення.
Якщо сказати просто: розмір кешу визначає швидкість повторних звернень, розмір об’єктів і обсяг доступної памʼяті. Ми не хочемо кеш, який тримає все, бо тоді він перетворюється на сміттєзвалище. Але й замалий кеш не допоможе — він просто постійно викидатиме щойно обчислені значення й усе одно запускатиме функцію з нуля.
Звісно ж єдиний можливий (і відповідно найкращий) варіант визначити найвлучніше значення — емпірично заміряти, як поводиться система при різних розмірах.
Ще може допомогти орієнтуватися на характер задачі. Якщо функція працює лише з невеликою кількістю унікальних ключів, скажімо десятком-другим значень, кеш на сотні елементів буде марнотратним. Натомість якщо ключів мільйони, але «гарячими» серед них є лише невелика підмножина, кеш у кілька тисяч або десятків тисяч може стати ідеальним компромісом між споживанням пам’яті та частотою «потраплянь» (англ. hit rate).
Ще одна порада — дивитися на об’єкти. Якщо кожен запис «важить» кілька мегабайт, кеш навіть у 20 елементів уже буде відчутним навантаженням. Якщо це дрібні числа чи словники — можна дозволити собі більше.
Зрештою, розмір кешу — це питання балансу: ми шукаємо точку, де кеш достатньо великий, щоб уникати повторної роботи, але достатньо малий, щоб не роздувати купу. Ідеальної формули немає, але профілювання та розуміння характеру даних дають наближену до точної відповідь.
Я все-таки запропоную варіанти того, як можна допомогти собі відшукати найоптимальніший розмір кешу, але це може слугувати хіба що підказкою, з якого значення починати профілювання, щоб не губитися у множині буквально безкінечності значень. Але брати результати наступних міркувань як джерело безсумнівної правди, звісно ж, не варто.
Розмір робочого набору
Є проста емпірична формула: її часто використовують інженери у високонавантажених системах:
Розмір робочого набору (англ. working set size, абрев. WSS) — це кількість унікальних ключів, які реально «обертаються» у памʼяті протягом характерного періоду роботи. Тобто якщо наша функція за хвилину роботи отримує приблизно 800 різних аргументів, то робочий набір і є ці 800.
Якщо кеш може вмістити весь цей набір, hit-rate уже близький до свого максимуму. Але в реальних системах навантаження нерівне: зʼявляються короткі сплески, «зсуви популярності» та тимчасові бурсти (англ. bursts). Вибір значення в межах від 1.5 до 3 (що у більшості випадків зводиться до вибору числа 2) створює запас, який згладжує ці коливання і не дає LRU або LFU постійно витісняти потрібні дані.
Якщо поставити кеш рівно на 800 елементів, кожен такий сплеск почне виштовхувати корисні значення, і hit-rate просідатиме. А якщо кеш приблизно удвічі більший — він покриває і стабільний робочий набір, і коливання навколо нього. Це не математичний закон, а емпіричне правило: кеш працює стабільно, коли він здатен тримати «усе, що часто повторюється» + «запас під пікові зміни».
Кеш теплової області
Ця модель виходить із дуже простої ідеї: кеш ефективний рівно настільки, наскільки він підвищує hit-rate. У певний момент збільшення кешу перестає давати відчутний приріст — крива hit-rate вирівнюється, і ми фактично «платимо памʼяттю даремно». Тож якщо hit-rate кешу майже не зростає після збільшення кешу — ми досягли оптимуму.
Формально:
Де H(k) — hit-rate при розмірі k; ε — практично «невідчутний» приріст, наприклад
Під капотом цей підхід спирається на природну властивість більшості систем: розподіл популярності ключів не рівномірний. Завжди є «гаряче ядро» (малий відсоток ключів, які зустрічаються надзвичайно часто) і «довгий холодний хвіст» (відповідно те, що зустрічається рідше). Коли ми налаштовуємо кеш, ми намагаємося спіймати саме це «гаряче ядро». Щойно це вийде, подальше збільшення розміру кешу означатиме, що ми почнемо зберігати холодний, рідко вживаний хвіст, який практично не впливає на швидкість.
Теоретична модель «кеш теплової області» (англ. cache locality) ще інколи записують так:
Де N₉₀ - це мінімальна кількість елементів, яка покриває 90% усіх звернень до функції. Тоді кеш тримає «гаряче ядро» даних, які інтенсивно використовуються.
Давайте подивимося це на прикладі в реаліях активного використання кешу, створивши ці умови самостійно.
import numpy as np
import matplotlib.pyplot as plt
from collections import OrderedDict, Counter
def generate_zipf_trace(num_items: int, num_requests: int, skew: float, seed: int = 0) -> np.ndarray:
rng = np.random.default_rng(seed)
ranks = rng.zipf(skew, size=num_requests)
ranks = np.clip(ranks, 1, num_items)
return ranks - 1 # перетворюємо у діапазон [0..num_items-1]
def compute_hotset_n90(requests: np.ndarray) -> tuple[int, Counter]:
freq = Counter(requests)
sorted_items = sorted(freq.items(), key=lambda kv: kv[1], reverse=True)
counts = np.array([count for _, count in sorted_items])
cumulative = np.cumsum(counts)
threshold = 0.9 * len(requests)
n90 = int(np.searchsorted(cumulative, threshold) + 1)
return n90, freq
def simulate_lru_hit_rate(trace: np.ndarray, cache_capacity: int) -> float:
if cache_capacity <= 0:
return 0.0
cache = OrderedDict()
hits = 0
for item in trace:
if item in cache:
hits += 1
cache.move_to_end(item, last=True) # оновлюємо LRU
else:
cache[item] = True
if len(cache) > cache_capacity:
cache.popitem(last=False) # видаляємо найстаріший елемент
return hits / len(trace)
def plot_lru_efficiency_curve(requests: np.ndarray, n90: int, max_items: int):
cache_sizes = np.unique(
np.concatenate([
np.arange(0, 65),
np.linspace(64, max_items, 32, dtype=int)
])
)
hit_rates = np.array([simulate_lru_hit_rate(requests, size) for size in cache_sizes])
hit_rate_at_n90 = simulate_lru_hit_rate(requests, n90)
plt.figure(figsize=(8, 4))
plt.plot(cache_sizes, hit_rates, marker='o', label='Hit rate')
plt.axvline(n90, linestyle='--', color='orange', label=f'N90 = {n90}')
plt.xlabel('Розмір кешу (елементів)')
plt.ylabel('Hit rate')
plt.title('Ефективність LRU кешу для Zipf-навантаження')
plt.grid(True)
plt.legend()
plt.text(n90, 0.05, f'H(N90) = {hit_rate_at_n90:.2f}', rotation=90, va='bottom')
plt.show()
def main():
"""Запуск повної симуляції кешу з побудовою графіка."""
NUM_ITEMS = 512
NUM_REQUESTS = 20_000
ZIPF_SKEW = 1.2
requests = generate_zipf_trace(NUM_ITEMS, NUM_REQUESTS, ZIPF_SKEW)
n90, _ = compute_hotset_n90(requests)
plot_lru_efficiency_curve(requests, n90, NUM_ITEMS)
if __name__ == '__main__':
main()
Розберемося поступово з кожним кроком. Щоб показати, як у реальних системах формується «гаряче ядро» звернень, ми моделюємо потік запитів, що підпорядковується закону Ципфа (англ. Zipf’s law). Це дуже поширена ситуація: невелика кількість «топових» елементів отримує левову частку всіх звернень, а довгий «хвіст» використовується рідко. Частота елементів падає приблизно як 1/rank, і саме це породжує ефект, коли маленький піднабір даних постійно «гріється» у кеші.
Іншими словами, закон Ципфа — це емпіричне правило, яке каже: «частота будь-якого елемента обернено пропорційна його рангу», тобто якщо впорядкувати елементи за частотою появи, то другий зустрічається приблизно вдвічі рідше за перший, третій — утричі, четвертий — вчетверо, і так далі.
Математично це виглядає так:
Тут f( r ) - частота елемента, r — його ранг.
Це загальне правило, і воно діє не тільки у сферах, дотичних до IT. До прикладу розмір міст: друге найбільше місто країни ≈ половина населення першого, третє — третина, і т. д. Дійсно, за даними Вікіпедії станом на 2020 рік для Києва — 2 967 360 осіб, Харків налічував 1 443 207, що справді є приблизно вдвічі менше, Одеса — 1 017 699, що є менше приблизно втричі за Київ.
Чому так працює? Немає єдиного пояснення, але є кілька ідей. Перше — принцип мінімізації зусиль: все організоване так, щоб людям було зручно, друге — ефект «багатий стає ще багатшим», тобто що частіше елемент використовується, то більше шансів, що його використають знову, і останнє — еволюційна оптимізація систем: системи самоорганізуються до ефективності.
Повернемося до коду. Перший блок — генерація Zipf-трейсу (функція generate_zipf_trace).
Ми створюємо синтетичний потік запитів до елементів (ключів), який поводиться так само, як реальний трафік у базах даних, CDN, API або файлових системах.
Закон Ципфа гарантує, що перший елемент найпопулярніший, другий має приблизно половину запитів, третій — третину, і так далі. Це дозволяє побачити, як кеш поводиться зі «справжніми» даними, а не рівномірним шумом.
Далі — визначення N₉₀ (функція compute_hotset_n90). Тут, нагадую, N₉₀ - це мінімальна кількість елементів, які покривають 90% усіх запитів. Код рахує частоту кожного елемента, сортує їх за популярністю, накопичує їхню частку у загальному трафіку і знаходить точку, де ми перетнули 90%. Це і є те саме «гаряче ядро», для Zipf-навантаження N₉₀ зазвичай дуже маленьке, зазвичай менше 5% усіх ключів.
Йдемо далі — симуляція LRU-кешу (функція simulate_lru_hit_rate). Ми запускаємо простий LRU та вимірюємо hit-rate для різних розмірів кешу. Це відповідає питанням: скільки елементів треба тримати в кеші, щоб не втрачати ефективність, та скільки кешу достатньо?
Наступний крок — побудова кривої ефективності (функція plot_lru_efficiency_curve).
Можемо зробити висновок, що навіть якщо всього елементів сотні чи тисячі, реально навантаження концентрується на дуже малому наборі, кеш розміром приблизно N₉₀ дає майже максимальний hit-rate при мінімальному розмірі, і на такому навантаженні класичні політики витіснення працюють близько до оптимуму.
Отже, базуючись на проведеному експерименті, можемо обирати розмір кешу N₉₀ або трохи більше (N₉₀ * [1.1, 1.3]), що дасть
Кешування як архітектурний підхід
До цього моменту ми говорили про кешування як про локальний механізм — спосіб уникнути повторних обчислень усередині однієї програми. Але кешування не обмежується пам’яттю функції чи процесу. У реальних системах воно часто живе на зовсім іншому рівні — між компонентами, тобто до прикладу між сервісом і базою даних, між API і користувачем, між мікросервісами, CDN і браузером.
Тут кеш стає не просто оптимізацією, а частиною архітектури. Він допомагає системі виживати під навантаженням, зменшуючи кількість звернень до повільних джерел даних.
Саме на цьому рівні з’являються інші проблеми: узгодженість, інвалідація іншого рівня, політики оновлення, шардінг і реплікація кешів. Кеш стає частиною даних системи, і тепер важливо не просто «запам’ятати результат», а підтримувати актуальність швидко і без втрати достовірності.
Для кешування на системному рівні зазвичай використовують сховища, оптимізовані під швидке читання і запис, і найпоширеніші серед них — Redis і Memcached.
Redis — це, по суті, інтелектуальний кеш-сервер: він зберігає дані в оперативній пам’яті, підтримує TTL, LRU/LFU політики, атомарні операції, черги, структури даних і навіть реплікацію. Redis часто виступає як «проміжний буфер» між сервісом і базою даних, даючи швидкість у мілісекунди там, де SQL-запит зайняв би сотні.
Memcached, навпаки, — мінімалістичний. Це легковісний in-memory кеш без складних структур, але з дуже низькими накладними витратами. Його сила — у простоті: ключ-значення, TTL і стабільність під великим навантаженням.
Окрім серверних сховищ, важливу роль у кешуванні відіграють мережеві рівні, і найбільш відомий серед них — Content Delivery Network (абрев. CDN). Він є розподіленою мережею вузлів, що зберігають копії статичного або динамічного контенту максимально близько до користувача. На відміну від Redis чи Memcached, що працюють усередині інфраструктури сервісу, CDN кешує результат, який уже віддається клієнтам: зображення, файли, HTML-сторінки, API-відповіді, навіть відеопотоки. Такий периферійний кеш (англ. edge cache) різко зменшує затримку, розвантажує бекенд і знижує вартість запитів до основного сховища чи серверів.
Обидва види кешів — in-memory (Redis/Memcached) та мережеві CDN — використовуються не лише для прискорення читання, а й для координації розподілених систем: зберігання токенів, сесій користувачів, тимчасових результатів аналітики, прапорців станів чи попередньо сформованих відповідей. Усі ці механізми виконують одну роль: забезпечують максимально швидкий доступ до даних, знімаючи навантаження з баз і сервісів. Фактично, Redis або Memcached — це оперативна пам’ять, винесена за межі застосунку, а CDN — це кеш, винесений у мережу, доступний користувачам у будь-якій точці світу.
Консистентність та інвалідація
Питання кешування — це майже завжди питання балансу між важливими для системи критеріями. Тема консистентності — це компроміс між швидкістю і правдою. Коли ми зберігаємо дані в кеші, ми фактично створюємо копію, яка з часом може розійтися з джерелом істини (базою даних чи зовнішнім API тощо). Ця розбіжність називається застарілими даними (англ. stale data).
Під капотом усе впирається у два моменти: момент оновлення і механізм інвалідації. Якщо кеш не знає, що дані в джерелі змінилися — він продовжує віддавати старе. Навіть мілісекундна затримка між зміною й оновленням кешу створює «вікно неузгодженості».
У системах із сильною консистентністю кеш оновлюється або інвалідовується синхронно з оновленням бази — це безпечніше, але повільніше. У слабко консистентних моделях кеш «підтягується» асинхронно (у буденному розумінні цього слова), тому певний час може жити зі старими значеннями, зате система працює швидше.
Попри різноманітність підходів усі вони зводяться до того, коли саме звертатися до кешу і як саме синхронізувати його з основною базою даних. На архітектурному рівні виділяють кілька ключових моделей.
Cache through — стратегія, де застосунок завжди працює з кешем як з єдиним джерелом істини. У запитах на читання застосунок звертається до кешу першим; якщо даних немає, кеш сам «пробиває шлях» до бази даних, зберігає отриманий результат і повертає його застосунку. Аналогічно поводиться й стратегія запису: усі зміни спочатку надходять до кешу, а вже кеш гарантує їх доставку в базу. Цей підхід мінімізує дублювання логіки в застосунку та забезпечує акуратну синхронність між шарами, але робить кеш критичною ланкою — якщо він падає, страждає весь шлях даних.
Стратегія cache aside працює зовсім інакше. Тут кеш не є обов’язковою точкою доступу, а скоріше помічником, яким застосунок користується за потреби. У сценарії читання застосунок спочатку шукає дані в кеші, а якщо їх немає — запитує з бази, після чого самостійно зберігає результат у кеш. У сценарії запису логіка ще простіша: застосунок оновлює базу даних і лише потім, за бажанням, оновлює або інвалідовує кеш. Цей підхід часто називають відкладеним завантаженням (англ. lazy loading): кеш наповнюється поступово, тоді як контроль за даними залишається у застосунку. Це робить систему більш стійкою до збоїв, але може призводити до коротких провалів у продуктивності після очищення кешу.
Там, де важливо, щоб дані в кеші були готові до моменту запиту, застосовують cache ahead. Це стратегія завчасного заповнення: кеш поповнюється наперед, зазвичай через регулярні фонові завдання або передбачувані сценарії доступу. Клієнт отримує дані миттєво, без холодного старт-ефекту. Такий підхід часто використовують у високонавантажених системах з передбачуваними патернами — рекомендовані списки, топ-попит, сторінки каталогу. Проблема полягає у балансі: завантажувати наперед забагато — означає витрачати ресурси даремно, замало — знову повертає холодний старт.
Паралельно існує протилежний підхід — cache behind або write-behind. Тут застосунок записує дані лише в кеш, а асинхронний процес періодично кидає ці зміни в базу даних. Модель створена для сценаріїв з високою інтенсивністю записів, де основна база не витримала б прямого навантаження. Вона дозволяє згладжувати піки, групувати операції та забезпечувати низьку затримку під час роботи з користувачами. Проте разом з перевагами приходить ризик: у разі падіння кешу не відправлені зміни можуть бути втрачені, тому такі системи зазвичай доповнюють логуванням або механізмами стійких черг.
Усі ці стратегії вирішують різні задачі, але жодна з них не є універсальною. Cache through підходить там, де критична узгодженість; cache aside — у більшості вебсервісів, де читання переважає над записами; cache ahead — там, де треба миттєва відповідь без холодного старту; cache behind — у системах з інтенсивними, але не критично-синхронними записами. Правильний вибір дає архітекторам ключ до продуктивності: кеш стає не лише «тимчасовим сховищем», а повноцінним шаром логіки, який формує поведінку всієї системи.
Висновки
Кешування — це концепція про керування часом: ми обмінюємо памʼять на швидкодію, щоб прискорювати повільні операції й розвантажувати системи, які не завжди можуть відповідати миттєво. Це майже завжди компроміс між актуальністю даних і швидкістю. Абсолютна консистентність робить систему повільною, а повна відсутність контролю за оновленнями — небезпечно неточною. Завдання інженера — знайти прийнятний баланс, зважаючи на характер трафіку, критичність даних, можливість появи stale data та витрати на інвалідацію. Сподіваюсь, ця стаття трохи допоможе вправніше з цим впоратися.
На цьому серію закінчено, юхув! Звісно ж раджу прочитати і минулі частини.
Частина 1. Анатомія памʼяті в Python. З чого починається оптимізація
Частина 2. Фрагменти й копії. Як Python марнує памʼять
Частина 3. Поза межами Python. Шлях до швидкодії, що дихає на C
Усім, хто пройшов крізь усі чотири частини цієї серії та розділив зі мною дослідження памʼяті в Python, — щиро дякую. Сподіваюся, ці матеріали були для вас цінними й захопливими.
І памʼятайте, Python — це інструмент, а справжня магія завжди в руках розробника. Дякую за увагу! Не прощаємось.
Сподобалась стаття? Підписуйтесь на автора, щоб отримувати сповіщення про нові публікації на пошту.
marchelloua
Yaroslav Tkachenko
Valentin Nechayev
Oleksandr Suvorov
Oleksandr Suvorov
8 коментарів
Додати коментар Підписатись на коментаріВідписатись від коментарів