algorithmcachingsystem-design

Why does cache use Most Recently Used (MRU) algorithm as evict policy?

I know the algorithms of MRU and its reversed one Least Recently Used (LRU).

I think LRU is reasonable, as LRU element means it will be used at least possible in future. However, MRU element means the element is very possible to be used in future, why evict it? What is the reasonable scenario?

Solution

  • Imagine you were looking up the details of buses as they arrived at a bus stop, based on their bus number (or whatever identifier you use).

    It's somewhat reasonable to think that if you've just seen a number 36 bus, you're less likely to see another one imminently than to see one of the other buses that stops there.

    Just one example, but the idea is more general: in some cases, having "just seen something" is a good indicator that you're unlikely to see the same thing again soon.