Что такое LRU Cache?

Что такое LRU Cache?

LRU Cache (Least Recently Used Cache) — это структура данных типа кэша с вытеснением наименее используемых элементов. Основная идея заключается в том, что при достижении лимита ёмкости кэша, из него удаляется элемент, к которому дольше всего не обращались. Этот алгоритм эффективно управляет памятью, сохраняя «горячие» (часто используемые) данные и удаляя «холодные» (редко запрашиваемые).

Принцип работы

LRU Cache оперирует двумя основными операциями:

1. Get(key) — получить значение по ключу. При успешном получении элемент перемещается в начало (или конец, в зависимости от реализации) как наиболее недавно использованный (MRU).
2. Put(key, value) — добавить или обновить пару ключ-значение. Если ключ существует, его значение обновляется, и элемент становится MRU. Если ключ новый и кэш заполнен, перед добавлением нового элемента удаляется наименее недавно использованный (LRU) элемент.

Ключевые компоненты реализации

Для эффективной реализации LRU Cache в Go (и других языках) обычно используются две структуры в комбинации:

• Хэш-таблица (map) — обеспечивает быстрый доступ O(1) к элементу по ключу.
• Двусвязный список (Doubly Linked List) — поддерживает порядок элементов по времени использования. Голова списка (Head) представляет MRU элемент, хвост (Tail) — LRU элемент.

Пример реализации на Go

package main

import (
	"container/list"
	"fmt"
)

// LRUCache структура кэша
type LRUCache struct {
	capacity int
	cache    map[int]*list.Element
	list     *list.List
}

// entry хранит пару ключ-значение в элементе списка
type entry struct {
	key   int
	value int
}

// Constructor создает новый LRU Cache
func Constructor(capacity int) LRUCache {
	return LRUCache{
		capacity: capacity,
		cache:    make(map[int]*list.Element),
		list:     list.New(),
	}
}

// Get возвращает значение по ключу и обновляет порядок
func (l *LRUCache) Get(key int) int {
	if elem, ok := l.cache[key]; ok {
		l.list.MoveToFront(elem) // Перемещаем в начало как MRU
		return elem.Value.(*entry).value
	}
	return -1 // или другое значение, обозначающее "не найдено"
}

// Put добавляет или обновляет элемент
func (l *LRUCache) Put(key int, value int) {
	// Если ключ существует - обновляем значение и порядок
	if elem, ok := l.cache[key]; ok {
		l.list.MoveToFront(elem)
		elem.Value.(*entry).value = value
		return
	}

	// Если кэш заполнен - удаляем LRU элемент
	if l.list.Len() == l.capacity {
		back := l.list.Back()
		if back != nil {
			delete(l.cache, back.Value.(*entry).key)
			l.list.Remove(back)
		}
	}

	// Добавляем новый элемент в начало списка
	elem := l.list.PushFront(&entry{key, value})
	l.cache[key] = elem
}

func main() {
	cache := Constructor(2)

	cache.Put(1, 100)
	cache.Put(2, 200)
	fmt.Println(cache.Get(1)) // 100 (1 становится MRU)

	cache.Put(3, 300)         // Вытесняет ключ 2 (LRU)
	fmt.Println(cache.Get(2)) // -1 (не найдено)
	fmt.Println(cache.Get(3)) // 300
	fmt.Println(cache.Get(1)) // 100 (все еще в кэше)
}

Сложность операций

• Временная сложность: O(1) для обеих операций Get и Put благодаря использованию хэш-таблицы (прямой доступ) и двусвязного списка (быстрое перемещение и удаление элементов).
• Пространственная сложность: O(n), где n — capacity кэша, так как мы храним все элементы в map и списке.

Преимущества и недостатки

Преимущества:

• Высокая производительность для сценариев с «горячими» данными.
• Простота концепции и эффективность при работе с ограниченной памятью.
• Широко применяется в реальных системах (кэширование в БД, DNS, CDN, ОС).

Недостатки:

• Требует дополнительной памяти для хранения порядка (двусвязный список).
• В некоторых паттернах доступа (например, циклических) может вытеснять полезные данные.
• Не учитывает частоту использования, только время последнего обращения (в отличие от LFU — Least Frequently Used).

Применение в Go-разработке

LRU Cache часто используется в:

• Веб-серверах для кэширования результатов тяжелых запросов или шаблонов.
• Базах данных и ORM для кэширования частых запросов.
• Микросервисных архитектурах для снижения нагрузки на бэкенд-сервисы.
• Пакете groupcache от Google, который является вдохновением для многих кэширующих решений в Go.

В стандартной библиотеке Go нет готовой реализации LRU, но популярные пакеты, такие как github.com/hashicorp/golang-lru, предоставляют оптимизированные и потокобезопасные реализации, которые рекомендуется использовать в production-окружении.