從零開始的緩存生活-LRUK

前面文章談到 LRU 算法在面對批量操作時，很容易讓熱點數據被批量數據替換出緩存，爲此衍生出了 LRUK 算法。批量操作往往都是訪問一次後便不再需要數據了，LRUK 正是利用這一點，LRUK 的 K 是一個計數，當數據被訪問了至少 k 次，才將數據加入到 LRU 緩存。所以 LRU 其實可以算是 LRU-1。

LRUK 需要一個 歷史隊列 history 新的緩存都存儲在 history 中，在其中保存着數據被訪問的次數，另外需要一個 lru 緩存，當 history 中數據到達 k 次就將其放入到 lru 隊列。 history 可以使用任意結構實現例如也可以是一個 lru 緩存隊列。

此外通常會使用 LRU-2，因爲如果 k 數字太大 lru 緩存中的數據很難被新數據替換。

實現 LRUK

來考慮需要的結構 需要定義一個新類型，在 history 保存緩存條目，和之前的 cacheValue 類似 但需要多一個屬性 k 記錄數據訪問次數：

type lrukValue struct {
	Key   interface{}
	Value interface{}
	K     int
}

然後是爲 LRUK 定義一個類型，兩個緩存隊列即可，一個是 history 隊列，一個是 lru 隊列(直接使用 前面文章實現的算法即可)：

// LRU 爲緩存定義一個自定義類型
type LRUK struct {
	// lru 緩存
	lru *LRU
	// 訪問歷史記錄
	history Cache
	// 訪問到達多少次加入 lru
	k int
}

// 因爲golang沒有構造函數 提供一個 New 函數 創建緩存
func NewLRUK(lru *LRU, history Cache, k int) Cache {
	if lru == nil {
		panic(`lru not supported nil`)
	}
	if k < 1 {
		panic(`lruk's k must > 0`)
	} else if k == 1 {
		return lru
	}
	if history == nil {
		panic(`history not supported nil`)
	}

	return &LRUK{
		lru:     lru,
		history: history,
		k:       k,
	}
}

首先實現 Delete 需要從兩個隊列中都刪除：

func (c *LRUK) Delete(key interface{}) {
	c.lru.Delete(key)
	c.history.Delete(key)
}

然後是 Get 接口，首先查詢 lru 隊列中是否存在存在就返回緩存值，如果不存在就查詢 history 接口：

func (c *LRUK) Get(key interface{}) (value interface{}, exists bool) {
	value, exists = c.lru.Get(key)
	if exists {
		// 存在 返回 緩存
		return
	}
	// 不存在 查詢 是否有歷史記錄
	hk, exists := c.history.Get(key)
	if !exists {
		// 不存在直接返回
		return
	}
	// 存在記錄 設置返回值
	v := hk.(*lrukValue)
	value = v.Value

	// 增加訪問記錄
	v.K++
	if v.K == c.k {
		// 到達 計數 k 將緩存移動到 lru
		c.lru.Put(key, v.Value)
		c.history.Delete(key)
	}
	return
}

最後實現 Put 接口，同樣要注意兩個隊列的操作：

func (c *LRUK) Put(key, value interface{}) {
	_, exists := c.lru.Get(key)
	if exists { //已經存在緩存中 更新值即可
		c.lru.Put(key, value)
		return
	}
	hv, exists := c.history.Get(key)
	if exists { // 存在歷史 更新歷史
		v := hv.(*lrukValue)
		v.Value = value
		v.K++
		if v.K == c.k {
			// 到達 計數 k 將緩存移動到 lru
			c.lru.Put(key, v.Value)
			c.history.Delete(key)
		}
		return
	}

	// 不在歷史 添加到歷史中
	c.history.Put(key, &lrukValue{
		Key:   key,
		Value: value,
		K:     1,
	})
}

慣例寫個簡單的測試示例：

package cache

import "testing"

func TestLRUK2(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)
			}
		}
	}

	lru := NewLRU(3)
	history := NewLRU(3)
	lruk2 := NewLRUK(lru, history, 2)
	// 插入 3 個緩存
	// history [0,1,2]
	// lru []
	for i := 0; i < 3; i++ {
		lruk2.Put(i, i)
	}
	// 驗證 緩存存在
	assertExists(t, history, 0, 1, 2)

	// 訪問 1 此後 key 1 計數到達 k 被移動到 lru
	// history [0,2]
	// lru [1]
	lruk2.Get(1)
	assertExists(t, history, 0, 2)
	assertExists(t, lru, 1)
}

完整代碼

package cache

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

// LRU 爲緩存定義一個自定義類型
type LRUK struct {
	// lru 緩存
	lru *LRU
	// 訪問歷史記錄
	history Cache
	// 訪問到達多少次加入 lru
	k int
}

// 因爲golang沒有構造函數 提供一個 New 函數 創建緩存
func NewLRUK(lru *LRU, history Cache, k int) Cache {
	if lru == nil {
		panic(`lru not supported nil`)
	}
	if k < 1 {
		panic(`lruk's k must > 0`)
	} else if k == 1 {
		return lru
	}
	if history == nil {
		panic(`history not supported nil`)
	}

	return &LRUK{
		lru:     lru,
		history: history,
		k:       k,
	}
}
func (c *LRUK) Delete(key interface{}) {
	c.lru.Delete(key)
	c.history.Delete(key)
}
func (c *LRUK) Get(key interface{}) (value interface{}, exists bool) {
	value, exists = c.lru.Get(key)
	if exists {
		// 存在 返回 緩存
		return
	}
	// 不存在 查詢 是否有歷史記錄
	hk, exists := c.history.Get(key)
	if !exists {
		// 不存在直接返回
		return
	}
	// 存在記錄 設置返回值
	v := hk.(*lrukValue)
	value = v.Value

	// 增加訪問記錄
	v.K++
	if v.K == c.k {
		// 到達 計數 k 將緩存移動到 lru
		c.lru.Put(key, v.Value)
		c.history.Delete(key)
	}
	return
}
func (c *LRUK) Put(key, value interface{}) {
	_, exists := c.lru.Get(key)
	if exists { //已經存在緩存中 更新值即可
		c.lru.Put(key, value)
		return
	}
	hv, exists := c.history.Get(key)
	if exists { // 存在歷史 更新歷史
		v := hv.(*lrukValue)
		v.Value = value
		v.K++
		if v.K == c.k {
			// 到達 計數 k 將緩存移動到 lru
			c.lru.Put(key, v.Value)
			c.history.Delete(key)
		}
		return
	}

	// 不在歷史 添加到歷史中
	c.history.Put(key, &lrukValue{
		Key:   key,
		Value: value,
		K:     1,
	})
}

2q

2q 算法其實是 lru-2 的一種，所以上述測試代碼其實就算是 2q，2q 即2個隊列的意思，數據首次出現將其緩存到隊列1中，當數據再次被使用將其從隊列1移動到隊列2中，兩個隊列按照各自的實現添加和淘汰緩存。所以當 lruk 的 k 爲 2 時就是一種 2q 算法。

此外如果不使用 lruk 單獨實現 2q 的話，緩存條目不需要多一個屬性保存歷史訪問次數，可以節省一點內存。

lruk 和 2q 的問題

lruk 和 2q 面臨同樣的問題，即現在有兩個隊列，所以需要爲兩個隊列配置容量，每個隊列容量多少將很難把握。此外每次 Get Put Delete 需要調整兩個隊列也比只使用一個隊列的結構多耗費少許資源。