從零開始的緩存生活-LRU

上篇文章討論的 LFU 淘汰算法太過複雜，並且熱點數據變成冷門數據後無法有效的被移除，爲此 LRU 提供了簡單且有效的替代方案。最近最少使用的是冷門數據應該被淘汰，最近使用的數據距離當前時間越近它就越熱門。實現起來也簡單很多使用一個鏈表，每次使用了數據就將其移動到鏈表尾，緩存滿了就刪除鏈表頭的數據(一直沒被訪問所以才會在鏈表頭，一直沒被使用所以它應該是冷門數據)，而真正熱門的數據通常在被刪除前會被持續訪問所以持續被移動到鏈表尾始終不被刪除，從而保證了緩存中存儲了正在熱門的數據而非只是如 LFU 存儲了曾經熱門但當前已經變得冷門的數據。

LRU 實現簡單效率也很高(實現難度幾乎和 FIFO 一樣，Put Get Delete 執行時間也幾乎和 FIFO 算法一致)，故是目前最常使用的緩存算法之一。

LRU 實現也和前面文章的 FIFO 幾乎一致，唯一需要做出修改的地方是 Get 接口中將被訪問的數據移動到鏈表尾。

實現 LRU

和 FIFO 一樣 LRU 需要三個基本屬性，一個 Map 用於存儲緩存，一個 List 實現淘汰算法，一個 capacity 定義緩存容量上限：

// 爲緩存數據定義一個類型
type cacheValue struct {
	Key   interface{}
	Value interface{}
}

// LRU 爲緩存定義一個自定義類型
type LRU struct {
	// 此字段設置緩存容量上限
	capacity int
	// Map 爲 查詢緩存數據提供 支持
	keys map[interface{}]*list.Element
	// 緩存淘汰算法使用 此鏈表實現 最近最少訪問的先被淘汰
	hot *list.List
}

// 因爲golang沒有構造函數 提供一個 New 函數 創建緩存
func NewLRU(capacity int) *LRU {
	if capacity < 1 {
		panic(`capacity must > 0`)
	}
	return &LRU{
		capacity: capacity,
		keys:     make(map[interface{}]*list.Element, capacity),
		hot:      list.New(),
	}
}

實現最簡單的 Delete 接口，直接將 FIFO 實現拷貝過來即可：

func (c *LRU) Delete(key interface{}) {
	ele, exists := c.keys[key]
	if !exists {
		// 緩存不存在 直接返回即可
		return
	}

	// 緩存存在 從 Map 和 List 刪除之
	delete(c.keys, key)
	c.hot.Remove(ele)
}

實現 Get 接口，首先將 FIFO 實現拷貝過濾，然後修改下在數據存在時將其移動到鏈表尾即可：

func (c *LRU) Get(key interface{}) (value interface{}, exists bool) {
	ele, exists := c.keys[key]
	if !exists {
		return
	}
	// 緩存存在 將緩存設置給返回值
	v := ele.Value.(cacheValue)
	value = v.Value
	// 將節點移動到連接尾
	c.hot.MoveToBack(ele)
	return
}

實現最後的 Put 接口，直接將 FIFO 實現拷貝過來即可：

func (c *LRU) Put(key, value interface{}) {
	ele, exists := c.keys[key]
	if exists { // 緩存存在 更新值 並將其在鏈表中的位置移動到鏈表尾
		ele.Value = cacheValue{
			Key:   key,
			Value: value,
		}
		c.hot.MoveToBack(ele)
		return
	}
	// 不存在首先判斷緩存是否已滿
	if len(c.keys) == c.capacity {
		// 緩存已滿 刪除鏈表頭部的緩存
		ele = c.hot.Front()
		v := ele.Value.(cacheValue)
		c.hot.Remove(ele)
		delete(c.keys, v.Key)
	}

	// 將新緩存內容加入
	ele = c.hot.PushBack(cacheValue{
		Key:   key,
		Value: value,
	})
	c.keys[key] = ele
}

至此我們便完成了 LRU 緩存算法，下面來寫個簡單的測試示例：

package cache

import "testing"

func TestLRU(t *testing.T) {
	// 定義一個輔助函數測試緩存中存在的 key
	assertExists := func(t *testing.T, cache *LRU, key ...interface{}) {
		for _, k := range key {
			_, exists := cache.keys[k]
			if !exists {
				t.Fatalf("key not exists : %v", k)
			}
		}
	}

	c := NewLRU(3)
	// 插入 3 個緩存 此時緩存了 key 爲 0 1 2 的數據
	for i := 0; i < 3; i++ {
		c.Put(i, i)
	}

	// 驗證 緩存存在
	assertExists(t, c, 0, 1, 2)

	// 插入 key 3 緩存變爲 1 2 3 ，key 爲 0 的緩存被移除
	c.Put(3, 3)
	assertExists(t, c, 1, 2, 3)

	// 訪問 key 1 緩存變爲 2 3 1
	c.Get(1)
	assertExists(t, c, 1, 2, 3)

	// 插入 key 3 緩存變爲 3 1 4 ，key 爲 2 的緩存被移除
	c.Put(4, 4)
	assertExists(t, c, 1, 3, 4)
}

完整代碼

package cache

import "container/list"

// 爲緩存數據定義一個類型
type cacheValue struct {
	Key   interface{}
	Value interface{}
}

// LRU 爲緩存定義一個自定義類型
type LRU struct {
	// 此字段設置緩存容量上限
	capacity int
	// Map 爲 查詢緩存數據提供 支持
	keys map[interface{}]*list.Element
	// 緩存淘汰算法使用 此鏈表實現 最近最少訪問的先被淘汰
	hot *list.List
}

// 因爲golang沒有構造函數 提供一個 New 函數 創建緩存
func NewLRU(capacity int) *LRU {
	if capacity < 1 {
		panic(`capacity must > 0`)
	}
	return &LRU{
		capacity: capacity,
		keys:     make(map[interface{}]*list.Element, capacity),
		hot:      list.New(),
	}
}
func (c *LRU) Delete(key interface{}) {
	ele, exists := c.keys[key]
	if !exists {
		// 緩存不存在 直接返回即可
		return
	}

	// 緩存存在 從 Map 和 List 刪除之
	delete(c.keys, key)
	c.hot.Remove(ele)
}
func (c *LRU) Get(key interface{}) (value interface{}, exists bool) {
	ele, exists := c.keys[key]
	if !exists {
		return
	}
	// 緩存存在 將緩存設置給返回值
	v := ele.Value.(cacheValue)
	value = v.Value
	// 將節點移動到連接尾
	c.hot.MoveToBack(ele)
	return
}
func (c *LRU) Put(key, value interface{}) {
	ele, exists := c.keys[key]
	if exists { // 緩存存在 更新值 並將其在鏈表中的位置移動到鏈表尾
		ele.Value = cacheValue{
			Key:   key,
			Value: value,
		}
		c.hot.MoveToBack(ele)
		return
	}
	// 不存在首先判斷緩存是否已滿
	if len(c.keys) == c.capacity {
		// 緩存已滿 刪除鏈表頭部的緩存
		ele = c.hot.Front()
		v := ele.Value.(cacheValue)
		c.hot.Remove(ele)
		delete(c.keys, v.Key)
	}

	// 將新緩存內容加入
	ele = c.hot.PushBack(cacheValue{
		Key:   key,
		Value: value,
	})
	c.keys[key] = ele
}

LRU 算法的問題

LRU 算法能夠很好的應對大部分情況，但依然存在着缺陷，比如某人順序請求一批數據，比如請求了 1 2 3 三個數據，因爲請求者打算批量處理這些數據，此時 1 2 3 將會將緩存中的三個已存在的緩存淘汰掉，這時很可能就將熱門數據淘汰了，但 1 2 3 被批量請求後可能就不再使用了。

LRU 在面對批量操作時很容易讓熱點數據被批量數據替換掉，爲此 衍生出了 LRU-K 算法用於解決此問題，本喵將在下篇文章進行討論。