LRU vs LFU

業(yè)務本地緩存中我們經(jīng)常需要維護一個池子，存放熱點數(shù)據(jù)，單機的內(nèi)存是有限的，不可能把所有數(shù)據(jù)都放進來。所以，合理的逐出策略是很重要的。我們需要在池子的元素達到容量時，把一些不那么熱點的緩存清理掉。

那怎么評估該清理哪些緩存呢？LRU 和 LFU 是兩個經(jīng)典的逐出策略：

• Least Recently Used (LRU) ：逐出最早使用的緩存；
• Least Frequently Used (LFU) ：逐出最少使用的緩存。

舉個例子，比如目前我們有 A, B, C, D 四個元素，按照時間由遠及近的訪問順序為：

A, B, A, D, C, D, D, C, C, A, B

在這個時間線里，A, C, D 都各自被訪問 3 次，而 B 只有 2 次。

按照 LFU 的標準，B 是訪問次數(shù)最少的，也就是【最少使用】的，所以需要逐出。

但是按照 LRU 的標準，B 是剛剛被訪問，還新著呢，按照時間回頭看，在四個元素被訪問順序是：D,C,A,B。這個 D 是最早訪問，后來人家 C, A, B 都訪問了，D 比它們?nèi)齻€都落后，所以要逐出 D。

LRU 和 LFU 并沒有高下之分，大家需要按照業(yè)務場景選擇最適合的逐出策略（eviction algorithm）。

container/list

在上一篇文章 解析 Golang 官方 container/list 原理 中，我們介紹了這個官方標準庫里的雙向鏈表實現(xiàn)，本質(zhì)是借用 root 節(jié)點實現(xiàn)了一個環(huán)形鏈表。

基于這個雙向鏈表，我們可以干很多事，今天我們就來看看，怎樣基于 container/list 實現(xiàn)一個帶上 LRU 逐出機制的本地緩存。

原理分析：用雙向鏈表實現(xiàn) LRU

既然是 LRU 緩存，我們首先要確定底層承載 localcache 的結構：

• 使用一個 map[string]interface{} 來存儲緩存數(shù)據(jù)；
• 需要明確緩存容量，超過了就要逐出。

type Cache struct {
	MaxEntries int
	cache map[string]interface{}
}

但僅僅如此肯定不夠，我們怎樣判斷 Least Recently Used 呢？

需要有一個結構用來記錄，每次有緩存被訪問，我們就把它權重提高，這樣隨著其他緩存請求，這個緩存的權重會慢慢落下來，如果觸發(fā)了 MaxEntries 這個上限，我們就看看誰的權重最小，就將它從 localcache 中清理出去。

使用 container/list 雙向鏈表就可以天然支持這一點！

雖然底層實現(xiàn)是個 ring，但對外來看，container/list 就是個雙向鏈表，有自己的頭結點和尾結點。利用API，我們可以很低成本地獲取頭尾結點，移除元素。

所以，我們可以以【節(jié)點在鏈表中的順序】來當做【權重】。在 list 里越靠前，就說明是剛剛被訪問，越靠后，說明已經(jīng)長時間沒有訪問了。當緩存大小和容量持平，直接刪除雙向鏈表中的【尾結點】即可。

而且，container/list 中的節(jié)點 Element 承載的數(shù)據(jù)本身也是個 any（interface{})，天然支持我們存入任意類型的緩存數(shù)據(jù)。

// Element is an element of a linked list.
type Element struct {
	// Next and previous pointers in the doubly-linked list of elements.
	// To simplify the implementation, internally a list l is implemented
	// as a ring, such that &l.root is both the next element of the last
	// list element (l.Back()) and the previous element of the first list
	// element (l.Front()).
	next, prev *Element
	// The list to which this element belongs.
	list *List
	// The value stored with this element.
	Value any
}

代碼實戰(zhàn)

有了上面的推論，我們就可以往 Cache 結構里內(nèi)嵌 container/list 來實現(xiàn)了。其實這就是 groupcache 實現(xiàn)的 LRU 的機理，我們來看看怎么做到的：

localcache 結構

// Cache is an LRU cache. It is not safe for concurrent access.
type Cache struct {
	// MaxEntries is the maximum number of cache entries before
	// an item is evicted. Zero means no limit.
	MaxEntries int
	// OnEvicted optionally specifies a callback function to be
	// executed when an entry is purged from the cache.
	OnEvicted func(key Key, value interface{})
	ll    *list.List
	cache map[interface{}]*list.Element
}
// A Key may be any value that is comparable. See http://golang.org/ref/spec#Comparison_operators
type Key interface{}
// New creates a new Cache.
// If maxEntries is zero, the cache has no limit and it's assumed
// that eviction is done by the caller.
func New(maxEntries int) *Cache {
	return &Cache{
		MaxEntries: maxEntries,
		ll:         list.New(),
		cache:      make(map[interface{}]*list.Element),
	}
}

首先是結構調(diào)整，注意幾個關鍵點：

• 新增 ll 屬性，類型為 *list.List，這就是我們用來判斷訪問早晚的雙向鏈表；
• cache 從 map[string]interface{} 變成了 map[interface{}]*list.Element，直接緩存了雙向鏈表的節(jié)點，同時 key 也改為 interface{}，這樣能支持更多場景，只要 key 的實際類型支持比較即可。
• 新增了 OnEvicted func(key Key, value interface{}) 函數(shù)，支持在某些 key 被逐出時回調(diào)，支持業(yè)務擴展，可以做一些收尾工作。

Add 添加緩存

type entry struct {
	key   Key
	value interface{}
}
// Add adds a value to the cache.
func (c *Cache) Add(key Key, value interface{}) {
	if c.cache == nil {
		c.cache = make(map[interface{}]*list.Element)
		c.ll = list.New()
	}
	if ee, ok := c.cache[key]; ok {
		c.ll.MoveToFront(ee)
		ee.Value.(*entry).value = value
		return
	}
	ele := c.ll.PushFront(&entry{key, value})
	c.cache[key] = ele
	if c.MaxEntries != 0 && c.ll.Len() > c.MaxEntries {
		c.RemoveOldest()
	}
}

這里可以看到采用了懶加載，只有當我們嘗試新增一個緩存時，才會初始化 cache map 以及雙向鏈表。

• 首先判斷 key 是否還在緩存，若已經(jīng)在，就利用雙向鏈表的 MoveToFront 將其提到鏈表的頭部（這就是我們前面推演的【提升權重】），語義上表達，這個 key 剛剛使用，還新著呢，權重最大。
• 操作完鏈表后，回來 cache map，將原來節(jié)點的 value 更新為這次的新值即可。
• 若 key 不在緩存里，就構造出來一個 entry，依然 PushFront 插入到鏈表頭部，隨后更新 cache 即可。
• 重點是最后一步，Add 完成后，看看鏈表長度是否已經(jīng)超過了閾值（MaxEntries)，若超過，就該觸發(fā)我們的 LRU 逐出策略了，關鍵在這個 RemoveOldest：

// RemoveOldest removes the oldest item from the cache.
func (c *Cache) RemoveOldest() {
	if c.cache == nil {
		return
	}
	ele := c.ll.Back()
	if ele != nil {
		c.removeElement(ele)
	}
}
func (c *Cache) removeElement(e *list.Element) {
	c.ll.Remove(e)
	kv := e.Value.(*entry)
	delete(c.cache, kv.key)
	if c.OnEvicted != nil {
		c.OnEvicted(kv.key, kv.value)
	}
}

可以看到，基于雙向鏈表，所謂 oldest，其實就是鏈表最尾端的節(jié)點，從 Back() 方法拿到尾結點后，從鏈表中 Remove 掉，并從 map 中 delete，最后觸發(fā) OnEvicted 回調(diào)。三連之后，這個緩存就正式被逐出了。

Get 讀緩存

// Get looks up a key's value from the cache.
func (c *Cache) Get(key Key) (value interface{}, ok bool) {
	if c.cache == nil {
		return
	}
	if ele, hit := c.cache[key]; hit {
		c.ll.MoveToFront(ele)
		return ele.Value.(*entry).value, true
	}
	return
}

根據(jù) key 讀緩存就容易多了，本質(zhì)就是直接查 map。不過注意，如果有，這算一次命中，按照 LRU 規(guī)則是要調(diào)整權重的，所以這里我們會發(fā)現(xiàn) c.ll.MoveToFront(ele) 將緩存的 element 提升到鏈表頭節(jié)點，意味著這是最新的緩存。

Add 和 Get 都代表了【緩存被使用】，所以二者都需要提升權重。

Remove 刪緩存

// Remove removes the provided key from the cache.
func (c *Cache) Remove(key Key) {
	if c.cache == nil {
		return
	}
	if ele, hit := c.cache[key]; hit {
		c.removeElement(ele)
	}
}

刪除的邏輯其實就很簡單了，注意這個是使用方手動刪除，并不是 LRU 觸發(fā)的逐出，所以直接提供了刪除的 key，不用找鏈表尾結點。

removeElement 還是和上面一樣的三連操作，從鏈表中刪除，從 map 中刪除，調(diào)用回調(diào)函數(shù)：

func (c *Cache) removeElement(e *list.Element) {
	c.ll.Remove(e)
	kv := e.Value.(*entry)
	delete(c.cache, kv.key)
	if c.OnEvicted != nil {
		c.OnEvicted(kv.key, kv.value)
	}
}

Clear 清空緩存

// Clear purges all stored items from the cache.
func (c *Cache) Clear() {
	if c.OnEvicted != nil {
		for _, e := range c.cache {
			kv := e.Value.(*entry)
			c.OnEvicted(kv.key, kv.value)
		}
	}
	c.ll = nil
	c.cache = nil
}

其實清空本身特別簡單，我們用來承載緩存的就兩個核心結構：雙向鏈表 + map。

所以直接置為 nil 即可，剩下的交給 GC。

不過因為希望支持 OnEvicted 回調(diào)，所以這里前置先遍歷所有緩存元素，回調(diào)結束后再將二者置為 nil。

結語

這篇文章我們賞析了 groupcache 基于 container/list 實現(xiàn)的 LRU 緩存，整體思路非常簡單，源碼不過 140 行，但卻可以把 LRU 的思想很好地傳遞出來。

細心的同學會發(fā)現(xiàn)，我們上面的結構其實是并發(fā)不安全的，map 和鏈表如果在操作過程中被打斷，存在另一個線程交替操作，很容易出現(xiàn) bad case，使用的時候需要注意。大家也可以考慮一下，如何實現(xiàn)并發(fā)安全的 LRU，是否必須要 RWMutex 實現(xiàn)？

到此這篇關于基于Golang container/list實現(xiàn)LRU緩存的文章就介紹到這了,更多相關Golang LRU內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論