LRU, LRU-K

LRU - алгоритм, вытесняющий данные, к которым не обращались дольше остальных. Ссылка на анимацию.

Под капотом две структуры данных:

• Двусвязный список: вставка/обновление в head и удаление из tail за O(1)
• Хэшмапа: хранит ключи и указатели на ноды списка, чтобы поиск элемента был за О(1) вместо O(n)

Взяли лучшее от двух структур данных и соединили в одну. На литкоде эта задача медиум. Всего вышесказанного хватит для реализации LRU и тем более для ответа на собеседовании на вопрос "С помощью каких структур данных ты бы реализовал LRU?"

Проблема LRU - sequential flooding

Часто запрашиваемые данные "вымываются" другими редко запрашиваемыми. Например, кэш в базе данных - произошел sequential scans который вымыл все данные.

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

Золотая середина - LRU-K. Paper можете найти здесь. K-access - кол-во обращений к элементу, в качестве обращения берется время когда элемент запросили. Вытесняется элемент по max_dist = time.now() - kth_last если элемент не достиг K его dist = inf и если таких элементов больше одного применяется LRU.

Идеальный баланс: мы больше не пускаем в кэш разовые запросы, пока они не подтвердят свою важность K раз. При этом алгоритм не дает старым данным застаиваться: если время между текущим моментом и их K-м запросом стало слишком большим, они вытесняются более актуальными данными.

P.S Если вы решили упороться и решили сами реализовать LRU-K, есть лаба от CMU на плюсах