Почему кеш использует алгоритм «Недавно использованный» (MRU) в качестве политики исключения?

Question

Я знаю алгоритмы MRU и его обратного наименьшего из недавно использованных (LRU).

Я думаю, что LRU является разумным, поскольку элемент LRU означает, что он будет использоваться, по крайней мере, в будущем. Тем не менее, элемент MRU означает, что элемент очень возможно использовать в будущем, зачем его выселять? Каков разумный сценарий?

Answer 1

Представьте, что вы просматривали информацию об автобусах, когда они прибыли на автобусную остановку, на основе номера их автобуса (или любого другого идентификатора, который вы используете).

Несколько разумно подумать, что если вы просто видел автобус № 36, вы меньше скорее всего увидите другой, чем тот, который останавливается там.

Только один пример,но идея более общая: в некоторых случаях «только что что-то увиденное» является хорошим показателем того, что вы вряд ли скоро увидите то же самое.

Answer 2

Я думаю, что ответы @Jon Skeet и @Jeremiah Willcock описывают использование MRU как способа избежать загрязнения кеша бесполезными записями.

1. Это работает только в том случае, если ваши API-интерфейсы кеша позволяют вам изменять политику на лету; например на основе запроса. Установка политики кэширования на MRU в «нормальных» ситуациях, вероятно, является плохой идеей ... потому что ваш кэш становится неэффективным после его заполнения.

2. Проблема MRU в том, что если вы получаете удар по записи, которая часто используется в «обычном» режиме при поиске MRU, вы в конечном итоге выбрасываете запись ...

Лучшими альтернативами MRU для сканирования без кеширования являются:

• полностью обойти кеш,
• зондировать кэш без чтения / обновления и без изменения цепочек LRU.

---

Что бы это ни стоило, я не могу вспомнить ни одного варианта использования MRU, который бы не подходил под эту общую схему.

---

Между прочим, пример @Jon Skeet о прибытии автобусов не всегда подтверждается фактами группирования.

• Если автобус опаздывает, вероятно, на каждой автобусной остановке будет больше, чем обычные люди. Автобус должен останавливаться чаще и дольше останавливаться на каждой остановке. Это замедляет опоздание автобуса.

• На автобусе, который вовремя следует за опоздавшим автобусом, обычно будет меньше людей, чем в среднем на каждой остановке. (Потому что они просто садятся в опоздавший автобус.) Это ускоряет следующий автобус.

• В результате автобусы собираются в кучу.

См .: https://en.wikipedia.org/wiki/Bus_bunching

Answer 3

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

Answer 4

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