К словарю | К разделу Fundamentals
MRU (Most Recently Used) — стратегия вытеснения данных из ограниченного
хранилища, при которой первым удаляется самый недавно использованный элемент.
На первый взгляд MRU выглядит менее интуитивно, чем LRU: обычно кажется, что
недавно использованные данные стоит сохранить. Но есть workload, где последнее
использованное значение как раз с меньшей вероятностью понадобится снова.
Как работает MRU-кеш
MRU-кеш, как и LRU, хранит элементы и порядок их использования. Разница в том,
какой элемент удаляется при переполнении.
Операции:
- get(key) — возвращает значение и помечает элемент как самый недавно
использованный; - put(key, value) — добавляет или обновляет элемент и помечает его как самый
недавно использованный; - если после добавления превышен лимит, удаляется most recently used элемент.
Пример для кеша ёмкостью 3:
- Добавили
A,B,C. - Обратились к
A, теперь он самый недавно использованный. - Добавили
D. - Вытесняется
A, потому что MRU удаляет последний использованный элемент.
На практике конкретная реализация может сначала выбрать жертву, а потом
добавить новый элемент, чтобы не удалить только что добавленное значение.
Главная идея остаётся той же: жертвой становится элемент с самым свежим
использованием среди уже находящихся в кеше кандидатов.
Когда MRU полезен
MRU подходит для сценариев, где после использования объект с высокой
вероятностью больше не понадобится в ближайшее время.
Примеры:
- последовательный проход по данным, когда возврата к последнему элементу не
ожидается; - некоторые сценарии сканирования таблиц или файлов;
- циклические паттерны доступа, где недавно использованный элемент уже
«пройден»; - специализированные кеши в системах управления базами данных.
Для обычных application-level кешей MRU встречается реже, чем LRU, потому что
многие пользовательские и сервисные сценарии имеют временную локальность.
Отличие от LRU
| Стратегия | Что вытесняется | Когда обычно подходит |
|---|---|---|
| LRU | Самый давно использованный элемент | Недавние обращения хорошо предсказывают будущие |
| MRU | Самый недавно использованный элемент | Последний использованный элемент вряд ли скоро понадобится |
LRU пытается сохранить горячие данные. MRU полезен, когда «горячесть» последнего
доступа обманчива и последний элемент скорее является уже обработанным.
Типичная реализация
MRU можно реализовать теми же базовыми структурами, что и LRU:
- hash map для поиска по ключу за
O(1); - двусвязный список или упорядоченная структура для хранения порядка
последнего использования.
Если начало списка хранит самый недавно использованный элемент, то при
вытеснении MRU удаляется голова списка. При каждом get или put элемент
переносится в начало.
Важно аккуратно определить поведение put при заполненном кеше: если новый
элемент сначала пометить как MRU, наивная реализация может тут же удалить его.
Обычно жертву выбирают среди существующих элементов до вставки или явно
исключают новый элемент из кандидатов на вытеснение.
Ограничения
MRU плохо подходит для workload с временной локальностью, где недавно
использованные элементы часто запрашиваются повторно.
Проблемные случаи:
- пользователь часто возвращается к последним открытым объектам;
- сервис повторно читает недавно полученные данные;
- одни и те же ключи многократно используются короткими сериями;
- стоимость повторной загрузки недавно использованного элемента высока.
В таких условиях MRU будет вытеснять самые полезные элементы и снижать cache hit
rate.
Что важно сказать на собеседовании
MRU — это политика, противоположная LRU по выбору жертвы, но не «ошибочная»
политика. Она имеет смысл для специальных паттернов доступа, особенно когда
последний использованный элемент уже обработан и с низкой вероятностью нужен
снова.
Хороший ответ должен объяснить не только механику, но и workload: без понимания
паттерна доступа нельзя сказать, какая стратегия вытеснения лучше.
