Какие политики очистки кэша существуют?

Кэширование — это техника хранения часто используемых данных в быстром хранилище для ускорения доступа. Когда кэш заполняется, необходимо решить, какие элементы удалить, чтобы освободить место для новых. Алгоритмы, управляющие этим процессом, называются политиками вытеснения (eviction policies).

Основные политики очистки кэша

• LRU (Least Recently Used): Удаляет элемент, к которому дольше всего не было обращений. Эффективен, когда недавно использованные данные с высокой вероятностью понадобятся снова. Реализуется с помощью двусвязного списка и хэш-таблицы для быстрого доступа.
• LFU (Least Frequently Used): Удаляет элемент с наименьшим количеством обращений. Подходит для сценариев, где некоторые данные запрашиваются постоянно, а другие — редко. Может требовать больше ресурсов для подсчёта частот.
• FIFO (First In, First Out): Удаляет самый старый элемент по времени добавления, независимо от частоты использования. Прост в реализации, но может вытеснять популярные данные, если они были добавлены рано.
• TTL (Time To Live): Каждому элементу назначается время жизни. По его истечении элемент удаляется. Часто комбинируется с другими политиками для обеспечения актуальности данных.
• Random Replacement: Случайный выбор элемента для удаления. Прост, но непредсказуем по производительности.

Пример реализации LRU на Python

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key):
        if key not in self.cache:
            return -1
        # Перемещаем ключ в конец (как недавно использованный)
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            # Удаляем первый (самый старый) элемент
            self.cache.popitem(last=False)

# Использование
cache = LRUCache(2)
cache.put(1, 'a')
cache.put(2, 'b')
print(cache.get(1))  # 'a'
cache.put(3, 'c')    # Вытеснит ключ 2
print(cache.get(2))  # -1 (не найден)

Политики применяются в базах данных (например, буферный пул InnoDB), операционных системах (кэш страниц), веб-браузерах (кэш ресурсов) и распределённых кэшах (Redis, Memcached). Выбор зависит от workload: LRU хорош для общих целей, LFU — для долгоживущих популярных данных, TTL — для данных с ограниченным сроком актуальности.

Вывод: Понимание политик очистки кэша позволяет проектировать эффективные системы, балансируя между скоростью доступа, использованием памяти и актуальностью данных. LRU — наиболее распространённый выбор для универсальных сценариев.