文章目錄
- 緩存淘汰策略
- LRU
- 核心結構
- 核心操作流程
- 局限性
- 源碼走讀
- Add
- Get
緩存淘汰策略
緩存淘汰策略的存在是為了解決 緩存容量有限性 和 高緩存命中率 之間的矛盾。其核心目標是在有限的緩存空間內，盡可能提高緩存命中率
- 緩存容量有限性：緩存（例如進程的內存緩存）的空間是有限的。當緩存空間被填滿，又來了新數據時，需要淘汰一些老數據，給新數據騰出空間
- 高緩存命中率：決定要淘汰哪些數據，對于提高緩存命中率至關重要。如果選擇淘汰熱數據，那么緩存命中率就低。反之如果淘汰冷數據，緩存命中率就高
常見的緩存淘汰策略有LRU，2q，LFU，tinyLFU等。本文介紹第一種：LRU
LRU
其核心思想是：當緩存空間不足時，優先淘汰最久未被訪問的數據。它基于“時間局部性”原理，即假設最近被訪問的數據更有可能在未來被再次訪問
核心結構
LRU的核心結構為 一個哈希表 + 一個雙向鏈表
-
雙向鏈表：按訪問時間順序維護緩存項，鏈表頭部是最近使用的項，尾部是最久未使用的項（淘汰候選）
- 鏈表的每個節點entry包含以下字段：key，value，prev（鏈表上一個節點），next（鏈表下一個節點）
-
哈希表：存儲鍵（Key）到鏈表節點（Node）的映射
核心操作流程
- 訪問數據（Get）：
- 通過哈希表在 O(1) 時間內找到對應鏈表節點。
- 將該節點從鏈表中刪除（O(1)），并重新插入到鏈表頭部（O(1)）。
- 返回節點值。
- 插入數據（Put）：
- 如果鍵已存在：更新值，并像
Get一樣將節點移動到頭部。 - 如果鍵不存在：
- 創建新節點，插入鏈表頭部（O(1)）。
- 將鍵和節點存入哈希表（O(1)）。
- 如果緩存已滿，刪除鏈表尾部節點（O(1)），并同步刪除哈希表中對應的鍵。
- 如果鍵已存在：更新值，并像
可以看出通過哈希表和雙向鏈表的配合，Get和Put的時間復雜度都是O(1)，非常高效
一些設計上的關鍵問題：
- 為啥不用單鏈表，要用雙向鏈表？
- 拿到要刪除的節點后，單鏈表無法在 O(1) 時間內刪除一個節點
- 為啥節點需要存儲key？
- 當某個節點被淘汰時，可以O(1)時間根據key去哈希表中進行刪除操作
局限性
上面介紹的LRU有下面的局限性：
- 突發流量污染：如果某個很少訪問的項在短時間內被突然大量訪問（即使之后不再訪問），它會長時間占據緩存頭部，擠掉可能更熱（訪問頻率更高但近期未被訪問）的項。
- 沒有考慮緩存項的頻率：例如一個只訪問一次但剛好是最近訪問的項，會排在訪問了十次但稍早訪問的項前面。但這在大多數場景下是不符合預期的
這兩個問題在2q，LFU，tinyLFU會得到解決
源碼走讀
下面將針對一個經典的開源庫https://github.com/hashicorp/golang-lru的LRU實現進行源碼走讀，版本：v2.0.7
數據結構如下：
type LRU[K comparable, V any] struct {// 表示緩存的最大容量size int// 雙向鏈表，用于維護緩存中條目的訪問順序evictList *internal.LruList[K, V]// 是一個哈希表（字典），將鍵（K）映射到對應的緩存條目（*internal.Entry） items map[K]*internal.Entry[K, V]onEvict EvictCallback[K, V]
}
每個entry的核心字段如下：
type Entry[K comparable, V any] struct {next, prev *Entry[K, V]// 屬于哪個鏈表list *LruList[K, V]Key KValue V
}
Add
func (c *LRU[K, V]) Add(key K, value V) (evicted bool) {// 檢查是否已存在相同鍵的條目if ent, ok := c.items[key]; ok {// 如果存在，則將該條目移動到雙向鏈表的最前面（表示最近使用），并更新其值c.evictList.MoveToFront(ent)ent.Value = valuereturn false}// 將新的鍵值對插入到雙向鏈表的頭部，表示這是最新的訪問項ent := c.evictList.PushFront(key, value)// 同時將該條目加入到哈希表 items 中，以便后續快速查找c.items[key] = ent// 判斷是否超出容量限制evict := c.evictList.Length() > c.sizeif evict {// 移除最老的元素c.removeOldest()}return evict
}
移除最老元素流程如下：
func (c *LRU[K, V]) removeOldest() {// 找到雙向鏈表中最老的元素entif ent := c.evictList.Back(); ent != nil {c.removeElement(ent)}
}func (c *LRU[K, V]) removeElement(e *internal.Entry[K, V]) {// 從雙向鏈表中移除c.evictList.Remove(e)// 從哈希表中刪除delete(c.items, e.Key)if c.onEvict != nil {c.onEvict(e.Key, e.Value)}
}
Get
func (c *LRU[K, V]) Get(key K) (value V, ok bool) {// 如果存在，將其移動到鏈表頭部，標識最近訪問if ent, ok := c.items[key]; ok {c.evictList.MoveToFront(ent)return ent.Value, true}return
}
