Что такое LRU Cache

• 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

• Bloom Filter
• Consistent Hashing

LRU Cache работает на основе принципа удаления наименее используемых элементов при достижении лимита памяти. Этот механизм реализуется через связку HashMap и двусвязного списка (doubly linked list). HashMap обеспечивает O(1) время доступа к элементам, а двусвязный список позволяет быстро удалять элементы из начала списка, которые были наименее недавно использованы.

При добавлении нового элемента в кэш, старый элемент, который находился в начале списка (наименее используемый), удаляется. Это позволяет поддерживать актуальность кэша и оптимизировать использование памяти.

Пример реализации LRU Cache в коде может включать следующие шаги:

• Создание HashMap для хранения ключей и значений.
• Создание двусвязного списка для хранения ссылок на элементы.
• Реализация методов get и put, которые будут обновлять порядок элементов в списке и, при необходимости, удалять наименее используемые.

LRU Cache имеет несколько преимуществ, которые делают его популярным выбором для веб-кэширования:

• Эффективность: LRU хорошо справляется с кэшированием веб-контента, поскольку часто запрашиваемый контент остаётся в кэше.
• Простота реализации: классическая реализация LRU Cache с использованием HashMap и двусвязного списка обеспечивает O(1) время выполнения операций get и put.

Однако у LRU Cache есть и недостатки:

• Не всегда оптимален: в некоторых случаях более эффективными могут быть другие стратегии, например, LFU (Least Frequently Used) или FIFO (First In, First Out).
• Сложность настройки: выбор правильного размера кэша и параметров может потребовать тщательной настройки.

Важно учитывать эти факторы при выборе стратегии кэширования для конкретной системы.

Помимо LRU Cache, существуют и другие стратегии кэширования, которые могут быть более эффективными в определённых ситуациях:

• LFU Cache (Least Frequently Used) удаляет элементы, которые наименее часто используются, что может быть полезно для данных с неравномерным распределением запросов.
• FIFO Cache (First In, First Out) удаляет элементы в порядке их добавления, что может быть полезно для кэширования временных данных.
• Random Cache удаляет элементы случайным образом, что может обеспечить равномерное распределение нагрузки на кэш.

Выбор конкретной стратегии зависит от требований к системе, типа данных и ожидаемого поведения пользователей. Например, в Redis можно настроить стратегию кэширования с помощью параметра maxmemory-policy, который по умолчанию установлен в allkeys-lru, но также может быть установлен в allkeys-lfu или другие варианты.