Cache Eviction Policies

LRU (Least Recently Used)

Least Recently Used (LRU) removes the data that has not been accessed for the longest period of time.

The assumption behind LRU is: If data has not been used recently, it is less likely to be needed again in the near future.

How Does It Work?

Consider the following access sequence:

A → B → C → D

Later, the user accesses:

B → C

Current order of recent usage:

D (Least Recent) → A → B → C (Most Recent)

If the cache becomes full, D is removed first because it has not been accessed for the longest time.

Example

After a new mobile phone version is launched:

• Users frequently search for the latest model.
• Older models receive fewer recent accesses.

As a result, product data for older models is evicted first.

Common Use Cases

• Web applications
• Browser caching
• Database query caching
• Content delivery systems

MRU (Most Recently Used)

Most Recently Used (MRU) removes the data that was accessed most recently.

The assumption behind MRU is: If data was just used, there is a lower probability it will be needed again immediately.

How Does It Work?

Access sequence:

A → B → C → D

Most recently accessed item:

D

If eviction is required:

D is removed first.

Example

A user applies a discount coupon during checkout.

Once applied:

• The coupon is unlikely to be used again immediately.
• The cached coupon data can be evicted first.

Common Use Cases

• Batch-processing systems
• Sequential data access workloads
• Certain analytical applications

LFU (Least Frequently Used)

Least Frequently Used (LFU) removes the data that has been accessed the fewest number of times.

The assumption behind LFU is: Data with a low access count is less valuable and should be removed first.

How Does It Work?

Suppose the cache contains:

If space is required:

Plants

is evicted first because it has the lowest access frequency.

Example

In an e-commerce platform:

• Gadgets are searched thousands of times daily.
• Plants receive very few searches.

When the cache becomes full, the Plants category is removed first.

Common Use Cases

• Product recommendation systems
• Search engines
• Streaming platforms
• Frequently accessed content services

FIFO (First In First Out)

First In First Out (FIFO) removes the data that entered the cache first, regardless of how frequently or recently it was accessed.

The oldest cached entries are removed first. FIFO follows a Queue structure.

How Does It Work?

Insertion order:

A → B → C → D

If the cache becomes full:

A is removed first.

Example

Cache entries are inserted as:

User1 → User2 → User3 → User4

When a new entry arrives:

User1 is evicted first.

even if User1 is still frequently accessed.

Common Use Cases

• Basic caching systems
• Queue-based processing
• Systems where simplicity is more important than optimization

LIFO (Last In First Out)

Last In First Out (LIFO) removes the most recently inserted entry first.

The newest entry is considered the first candidate for eviction. LIFO follows a Stack structure.

How Does It Work?

Insertion order:

A → B → C → D

Most recently inserted:

D

If eviction is needed:

D is removed first.

Example

Suppose cache entries are:

Course1 → Course2 → Course3 → Course4

If the cache reaches capacity:

Course4

is removed first because it was inserted most recently.

Common Use Cases

• Stack-based systems
• Specialized processing workloads
• Temporary data structures