The LRU strategy is based on the usage of cache elements. Some statistics are maintained to be able to sort elements by the last usage date, and when eviction is needed, the cache just goes through the elements in order and evicts them in the same order.
You can imagine it as the cache maintaining a map of data (storage) and a list of the usage of the data (or keys). Here is a sequence to help you visualize it:
|
Action
|
Cache storage (unsorted)
|
Eviction list (sorted)
|
| - | [] | [] |
| add key/value E1 | [E1] | [E1] |
| add key/value E2 | [E1, E2] | [E1, E2] |
| add key/value E3 | [E1, E2, E3] | [E1, E2, E3] |
| read E2 | [E1, E2, E3] | [E1, E3, E2] |
What is important to notice here is that each usage (put, get, and so on) will first ...
