Least Recently Used (LRU) - один из алгоритмов кеширования, который при переполнении удаляет (вытесняет) самый давно неиспользуемый элемент.

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

Обычно LRU реализуется с помощью связанного списка и хэш-таблицы. Связанный список хранит порядок использования элементов: самые “свежие” — в начале, а самые “старые” — в конце. Хэш-таблица (map) обеспечивает быстрый доступ к элементам по ключу. Это позволяет за константное время (O(1)) выполнять обе основные операции: Get и Add.

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

1. Операция Get(key):
   • Если элемент есть в кэше:
     • Переместить в начало списка;
     • Возвратить значение.
   • Если нет - оповестить об этом пользователя (дефолтное значение или флаг).
2. Операция Add(key, value):
   • Если ключ уже есть в кэше:
     • Обновить значение;
     • Переместить в начало списка.
   • Если ключа нет:
     • Если кэш переполнен:
       • Удаляем последний элемент списка;
     • Добавляем новый элемент в начало списка.

Пример операций LRU

Предположим кэш с фиксированным размером три элемента: Добавим в кэш три элемента: LRU кэш полон. Теперь когда необходимо добавить новый элемент, то обязательно нужно выделить место под него, удалив самый давно неиспользуемый элемент, т.е. A: 1 После освобождения места под новый элемент, его можно добавить:

Поведение операции Get(Key) проще, т.к. кроме возвращения значения просто перемещает запрашиваемый объект в начало списка:

Следовательно при следующей вставке нового элемента, вытеснен будет самый долго неиспользуемый элемент - C: 3.

Пример LRU на Go

Пример демонстративного кода LRU кэша с использование реализации связанного списка из стандартной библиотеки:

import "container/list"  
  
type Cache[K comparable, V any] struct {  
    cap   int  
    items map[K]*list.Element  
    ll    *list.List  
}  
  
type Item[K comparable, V any] struct {  
    key   K  
    value V
}  
  
func New[K comparable, V any](capacity int) *Cache[K, V] {  
    return &Cache[K, V]{  
       cap:   capacity,  
       items: make(map[K]*list.Element, capacity),  
       ll:    list.New(),  
    }  
}  
  
func (c *Cache[K, V]) Get(key K) (res V, ok bool) {  
    if node, exists := c.items[key]; exists {  
       c.ll.MoveToFront(node)  
	   res = node.Value.(Item[K, V]).value  
		return res, true
    }  
  
    return  
}  
  
func (c *Cache[K, V]) Add(key K, value V) {  
    if node, ok := c.items[key]; ok {  
       newItem := Item[K, V]{key: key, value: value}  
       node.Value = newItem  
       c.ll.MoveToFront(node)  
  
       return  
    }  
  
    if len(c.items) == c.cap {  
       nodeToRemove := c.ll.Back()  
       item := nodeToRemove.Value.(Item[K, V])  
       delete(c.items, item.key)  
       c.ll.Remove(nodeToRemove)  
    }  
  
    node := c.ll.PushFront(Item[K, V]{key: key, value: value})  
    c.items[key] = node  
}

Для лучшего ознакомления с применением LRU рекомендую готовые к продакшену решению:

• Потокобезопасный и легковесный Expirable LRU Cache, использующий дженерики и не создающий горутины;
• Библиотека с потокобезопасным LRU Cache с использованием дженериков, а также реализация Expirable и ARC LRU;
• Библиотека от разработчиков языка Go с непотокобезопасным LRU Cache и без использования дженериков.

Полезные источники:

• Leetcode LRU Problem
• Habr: Эффективное кеширование. От теории к практике