3.1 Cache Replacement Policies

This is a historical learning note and may contain outdated or incomplete understanding.

1. What It Is

A cache can improve lookup efficiency, but cache space is limited, so data that is not needed must be evicted from the cache.

2. Categories

2.1. FIFO

2.1.1. What It Is

First In First Out: preferentially evict the data that entered the cache earliest.

2.1.2. Implementation

A queue is enough.

2.2. LRU

2.2.1. What It Is

Least Recently Used: preferentially evict the data that has not been accessed for the longest time. - Assume the cache size is 4. Initially all positions are NULL. The left side is the head and the right side is the tail: the least recently used item is at the head, and the newest inserted item is at the tail.

Initial state
```
NULL NULL NULL NULL
```
Add 1
```
NULL NULL NULL 1 
```
Add 2
```
NULL NULL 1 2
```
Add 3
```
NULL 1 2 3
```
Add 4
```
1 2 3 4
```
Add 0, so 1 at the head is evicted
```
2 3 4 0
```
Access/add 2, so the existing 2 moves to the tail
```
3 4 0 2
```

2.2.2. Implementation

HashMap + doubly linked list
Design an LRU Cache

2.2.3. Problem

Occasional or periodic batch queries that include cold data can evict a large amount of hot data, sharply reducing the LRU hit rate and causing serious cache pollution.

2.3. LFU

2.3.1. What It Is

Least Frequently Used: preferentially evict the least frequently used data. -

2.3.2. Implementation

Compared with LRU, this adds an access-frequency count to each cached item and determines the order according to access frequency.

2.3.3. Problem

Early hot data may occupy space for a long time. For example, if the cache measurement window is 1 hour (data is ordered by access count in the most recent hour), data accessed an average of 1000 times per hour may be evicted before data that was accessed 1001 times in the previous hour.