Что такое LRU Cache
LRU (Least Recently Used) Cache — eviction policy, который удаляет least-recently-accessed items при переполнении. Classic implementation: HashMap + doubly linked list для O(1) get/put. Redis default: `maxmemory-policy allkeys-lru`. Alternatives: LFU (Least Frequently Used), FIFO, random. LRU универсально хорошо для web caching (recent content is hot).
Ниже: подробности, пример, смежные термины, FAQ.
Подробности
- O(1) operations: get + put
- Structure: HashMap (key → node) + DoublyLinkedList (insertion order)
- On get: move node to head
- On put: add at head; if capacity exceeded → remove tail
- Variants: LFU (frequency), TinyLFU (Google, Caffeine Java cache), W-TinyLFU
Пример
// Python @lru_cache decorator
from functools import lru_cache
@lru_cache(maxsize=128)
def expensive(n): return n * n
// Redis LRU policy
maxmemory 1gb
maxmemory-policy allkeys-lruСмежные термины
Больше по теме
Часто задаваемые вопросы
LRU vs LFU — что лучше?
LRU — recent matters. LFU — frequency matters. Для web: LRU обычно win (recency correlates с future access). LFU лучше для static catalog queries.
Redis LRU реально accurate?
Redis uses approximate LRU для efficiency. Sample 5 keys, evict oldest. Достаточно точный для most use cases.
TTL vs LRU?
Разное. TTL — absolute expiry (delete after N sec). LRU — eviction при memory pressure. Часто сочетают: TTL на data + LRU для overflow.