LRU Eviction: Removing the Least Recently Used Item

Eviction is how a full cache makes room for a new item, and LRU, least recently used, is the most common rule for it: remove the item that has gone longest without being read. Every read moves an item to the most recent end, so items in steady use stay, whatever order they arrived in.

Why a rule is needed. Memory is finite, so a cache holds a fixed number of items or bytes. When it is full and a new item arrives, something must go. A good rule removes the item least likely to be read again, and the item untouched for longest is a strong guess.

Trace a four-slot cache through seven reads. Each frame lists the items from least to most recently used, so the leftmost item is the next to be evicted. Before each eviction, predict which item goes.

What to notice. A was the first item in, yet it stayed, because reading it moved it to the recent end. A rule that evicted by arrival, called FIFO for first in, first out, would have removed A at the fifth step and missed on it later. LRU removes by last use, not by age.

Where you meet it. Redis can evict with an approximation of LRU when it reaches its memory limit, set by its maxmemory-policy option, and in-process caches in most languages offer an LRU variant. Without a rule, a cache either refuses new items or grows until memory runs out.

So give every cache a size limit and an eviction rule, and expect LRU to keep what is in steady use and drop what has gone quiet.