從零開始的緩存生活-LFU

lfu 緩存算法 介紹 以及 golang 實現示例

FIFO 算法的問題在於熱點數據和冷門數據擁有相同的權重，所謂熱點數據就是經常被訪問的數據，意味着熱點數據將獲得更多的 Get 查詢，LFU 便是建立在此想法之上。LFU 關注緩存被訪問的次數並依此來判斷數據的熱度，越常被訪問的數據其熱度越高，而越冷門的數據熱度越低。

LFU 爲每筆數據管理一個計數來表示其熱度，每當數據被 Get 就將其計數 +1，這樣經常被訪問的熱點數據計數就會很高，而冷門數據的計數就會很低，當緩存已滿時就刪除計數最低(即熱度最少)的緩存以騰出空間存儲新的緩存。

網路查看到的資料並未看到關於 Put 時計數的操作，但本喵認爲 Put 時如果緩存存在也應該爲計數 +1 因爲這樣實現簡單，而且無論是 Get Put 都是關注的緩存的 key 計數應該是和 key 綁定，當然知道原理在 Put 時是否要將計數增加你可依自己的需要實現。

LFU 需要緩存按照熱度計數排序，想下可以使用 二叉排序樹，最小堆，或者鏈表，通常的做法是使用鏈表和最小堆，二叉排序樹是完整的排序其實沒有必要我們每次只需要計數最小的值這個特性最小堆最適合了，此外如果用鏈表的話鏈表可以按照計數大小互相連接因爲每次計數都+1，當熱點增加時調整鏈表位置只需要一直和Next比較如果計數不大於自己的就交互位置即可(所以交換次數和相同熱度緩存的數量相關，當存在大量同熱度緩存時調整鏈表的消耗將增加)。

最小堆是本喵認爲最適合實現 LFU 淘汰算法的結構，剛好 golang 標準庫也有提供。

實現 LFU

首先我們來爲緩存數據定義一個 lfuValue 類型和 FIFO中的定義的 cacheValue 相比需要一個新的屬性來記錄熱度，另外還需要一個屬性記錄在堆中的位置以便刪除時使用：

// 爲緩存數據定義一個類型
type lfuValue struct {
	Key   interface{}
	Value interface{}
	Hot   int
	Index int // 記錄在堆中的位置
}

然後 golang 沒有模板，所以標準庫的最小堆很難用，我們先包裝一下並且爲 lfuValue 實現標準庫中最小堆需要的接口：

// 實現 標準庫需要的接口
type lfuValueHeap []*lfuValue

func (a lfuValueHeap) Len() int {
	return len(a)
}
func (a lfuValueHeap) Swap(i, j int) {
	a[i], a[j] = a[j], a[i]
	// 更新在堆中的位置
	a[i].Index = i
	a[j].Index = j
}
func (a lfuValueHeap) Less(i, j int) bool {
	return a[i].Hot < a[j].Hot
}
func (h *lfuValueHeap) Push(x interface{}) {
	v := x.(*lfuValue)
	v.Index = len(*h) // 添加到堆時 記錄位置
	*h = append(*h, v)
}
func (h *lfuValueHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	old[n-1] = nil
	return x
}

// 包裝一下 最小堆
type lfuHeap struct {
	heap lfuValueHeap
}

func newLFUHeap(capacity int) *lfuHeap {
	heap := make(lfuValueHeap, 0, capacity)
	return &lfuHeap{
		heap: heap,
	}
}
func (h *lfuHeap) Push(val *lfuValue) int {
	heap.Push(&h.heap, val)
	return val.Index
}
func (h *lfuHeap) Len() int {
	return h.heap.Len()
}

func (h *lfuHeap) Remove(i int) *lfuValue {
	v := heap.Remove(&h.heap, i)
	if v == nil {
		return nil
	}
	return v.(*lfuValue)
}
func (h *lfuHeap) Fix(i int) {
	heap.Fix(&h.heap, i)
}

已經有了一個最小堆 lfuHeap 我們來看下 LFU 需要的屬性，和 FIFO 類似一個 Map 存儲緩存，一個 capacity 存儲最大容量，另外一個 hot 實現淘汰算法這裏使用上面實現的最小堆即可：

// LFU 爲緩存定義一個自定義類型
type LFU struct {
	// 此字段設置緩存容量上限
	capacity int
	// Map 爲 查詢緩存數據提供 支持
	keys map[interface{}]*lfuValue
	// 緩存淘汰算法使用 使用最小堆每次淘汰 熱度最低的元素
	hot *lfuHeap
}

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

還是由易到難先實現最簡單的 Delete 接口，查詢緩存如果存在刪除即可：

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

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

然後是 Get 和 FIFO 實現差不多唯一的區別是，如果緩存存在就爲其熱度+1，並且調整最小堆(或排序你使用的其它數據結構)：

func (c *LFU) Get(key interface{}) (value interface{}, exists bool) {
	v, exists := c.keys[key]
	if !exists {
		return
	}
	// 緩存存在 將緩存設置給返回值
	value = v.Value

	// 增加熱度 並且重新排序
	v.Hot++
	c.hot.Fix(v.Index) // 最小堆只需要調整一下堆結構即可
	return
}

最後是 Put 的實現，和 PIPO 類似先檢查是否存在存在就更新值並調整最小堆，如果不存在就先檢查是否達到容量上限達到就刪除最小堆中第一個元素(熱度最小的元素)，最後插入新緩存：

func (c *LFU) Put(key, value interface{}) {
	v, exists := c.keys[key]
	if exists { // 緩存存在 更新值 熱度 並且重新排序
		v.Hot++
		v.Value = value
		c.hot.Fix(v.Index) // 最小堆只需要調整一下堆結構即可
		return
	}
	// 不存在首先判斷緩存是否已滿
	if len(c.keys) == c.capacity {
		// 緩存已滿 刪除熱度最小的元素
		v := c.hot.Remove(0)
		delete(c.keys, v.Key)
	}

	// 將新緩存內容加入
	v = &lfuValue{
		Key:   key,
		Value: value,
		Hot:   1,
	}
	c.hot.Push(v)
	c.keys[key] = v
}

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

package cache

import (
	"testing"
)

func TestLFU(t *testing.T) {
	type _Hot struct {
		Key interface{}
		Hot int
	}
	makeHot := func(key interface{}, hot int) _Hot {
		return _Hot{
			Key: key,
			Hot: hot,
		}
	}
	// 定義一個輔助函數測試緩存中存在的 key
	assertExists := func(t *testing.T, lfu *LFU, key ..._Hot) {
		for _, k := range key {
			v, exists := lfu.keys[k.Key]
			if !exists {
				t.Fatalf("key not exists : %v", k.Key)
			}
			if v.Hot != k.Hot {
				t.Fatalf("key' hot not match key=%v, %v!=%v", k.Key, k.Hot, v.Hot)
			}
		}
	}

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

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

	// 訪問 數據 key 爲 0 2 的數據
	c.Get(0)
	c.Get(0)
	c.Get(2)
	// 緩存熱度已經變化爲
	// 0 3
	// 1 1
	// 2 2
	assertExists(t, c, makeHot(0, 3), makeHot(1, 1), makeHot(2, 2))

	// 插入 key 3 因爲 key 1 熱度最低 被淘汰
	// 0 3
	// 2 2
	// 3 1
	c.Put(3, 3)
	assertExists(t, c, makeHot(0, 3), makeHot(2, 2), makeHot(3, 1))

	// 插入 key 4 因爲 key 3 熱度最低 被淘汰
	// 0 3
	// 2 2
	// 3 1
	c.Put(4, 4)
	assertExists(t, c, makeHot(0, 3), makeHot(2, 2), makeHot(4, 1))
}

完整代碼

package cache

import "container/heap"

// 爲緩存數據定義一個類型
type lfuValue struct {
	Key   interface{}
	Value interface{}
	Hot   int
	Index int
}

// 實現 標準庫需要的接口
type lfuValueHeap []*lfuValue

func (a lfuValueHeap) Len() int {
	return len(a)
}
func (a lfuValueHeap) Swap(i, j int) {
	a[i], a[j] = a[j], a[i]
	// 更新在堆中的位置
	a[i].Index = i
	a[j].Index = j
}
func (a lfuValueHeap) Less(i, j int) bool {
	return a[i].Hot < a[j].Hot
}
func (h *lfuValueHeap) Push(x interface{}) {
	v := x.(*lfuValue)
	v.Index = len(*h) // 添加到堆時 記錄位置
	*h = append(*h, v)
}
func (h *lfuValueHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	old[n-1] = nil
	return x
}

// 包裝一下 最小堆
type lfuHeap struct {
	heap lfuValueHeap
}

func newLFUHeap(capacity int) *lfuHeap {
	heap := make(lfuValueHeap, 0, capacity)
	return &lfuHeap{
		heap: heap,
	}
}
func (h *lfuHeap) Push(val *lfuValue) int {
	heap.Push(&h.heap, val)
	return val.Index
}
func (h *lfuHeap) Len() int {
	return h.heap.Len()
}

func (h *lfuHeap) Remove(i int) *lfuValue {
	v := heap.Remove(&h.heap, i)
	if v == nil {
		return nil
	}
	return v.(*lfuValue)
}
func (h *lfuHeap) Fix(i int) {
	heap.Fix(&h.heap, i)
}

// LFU 爲緩存定義一個自定義類型
type LFU struct {
	// 此字段設置緩存容量上限
	capacity int
	// Map 爲 查詢緩存數據提供 支持
	keys map[interface{}]*lfuValue
	// 緩存淘汰算法使用 使用最小堆每次淘汰 熱度最低的元素
	hot *lfuHeap
}

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

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

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

func (c *LFU) Get(key interface{}) (value interface{}, exists bool) {
	v, exists := c.keys[key]
	if !exists {
		return
	}
	// 緩存存在 將緩存設置給返回值
	value = v.Value

	// 增加熱度 並且重新排序
	v.Hot++
	c.hot.Fix(v.Index) // 最小堆只需要調整一下堆結構即可
	return
}

func (c *LFU) Put(key, value interface{}) {
	v, exists := c.keys[key]
	if exists { // 緩存存在 更新值 熱度 並且重新排序
		v.Hot++
		v.Value = value
		c.hot.Fix(v.Index) // 最小堆只需要調整一下堆結構即可
		return
	}
	// 不存在首先判斷緩存是否已滿
	if len(c.keys) == c.capacity {
		// 緩存已滿 刪除熱度最小的元素
		v := c.hot.Remove(0)
		delete(c.keys, v.Key)
	}

	// 將新緩存內容加入
	v = &lfuValue{
		Key:   key,
		Value: value,
		Hot:   1,
	}
	c.hot.Push(v)
	c.keys[key] = v
}

LFU 算法的問題

LFU 很好的解決了 FIFO 熱點數據在緩存中的權重問題但同時引入了新的問題

  • 淘汰算法需要依據熱度排序，當緩存大量數據後每筆緩存熱度發生變化都需要調整順序這可能會消耗過多的資源
  • 一份數據熱度很高後很難被淘汰，即使它已經變得冷門(例如今天本喵發佈了一篇有趣的新聞A，它一下子熱度衝到很高，因爲大家都感興趣不斷訪問它，但等過了一個月後沒有發生有趣的事情所以沒有發布爆炸性的新聞以致於這個月來的新聞都沒有熱度超過A的所以即時現在沒人看新聞A了，但它卻依舊倔強的待在緩存中浪費者資源)

鑑於上述問題，更常使用的緩存算法是 LRU，LRU 使用更加簡單有效的方式淘汰數據，本喵將在下篇文章進行討論。

2 則留言

  1. Howdy, i read your blog from time to time and i own a similar one and i was
    just wondering if you get a lot of spam feedback? If so
    how do you reduce it, any plugin or anything you can advise?
    I get so much lately it’s driving me mad so any assistance is very much appreciated.

    • I have set all comments to be reviewed, so that users will not see spam messages, but i need to take the time to review them (basically, I only reject spam or racially motivated comments, and others will be allowed to be displayed).

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *