從零開始的緩存生活-FIFO

FIFO 緩存算法是最原始和最簡單的緩存算法之一。其思想相當單純先進先出，當一個數據先被緩存下來，那麼這個數據也將先失效。

比如緩存容量爲3，訪問了數據 1 2 3 三個數據，此時緩存中的數據是 1 2 3。然後再訪問數據 4 此時 緩存已達容量上限故需要刪除數據源 1 來存儲數據4，因爲 1 是最先進入緩存的所以 1需要最先被淘汰，此時緩存中的數據變爲 2 3 4。如果此時再訪問了數據 5，緩存中的數據 2 被淘汰，緩存變成 3 4 5。

FIFO 對數據來說是最公平的算法因爲所有數據都按照同樣的先進先出原則被淘汰，但數據往往有所謂的熱點數據，熱點數據應該有更大的權重(在緩存中待更久)，而非熱點數據應該儘快被熱點數據替換，這樣才能提高緩存命中率(緩存有效指標)。但FIFO是基礎，後續算法大多都由此衍生，故我們還是先來看下FIFO如何實現。

實現 FIFO

首先來爲緩存定義一個類型，考慮我們需要的屬性。需要一個Map存儲緩存，然後需要一個先進先出的數據結構，使用一個鏈表添加數據時加入鏈表尾部，緩存滿時從鏈表頭部開始刪除即可實現先進先出，正好golang標準庫都有提供。此外因爲要實現 Delete 函數，需要同時刪除 Map 和 List 所以 Map 的 value 應該存儲 List 的 Element 這樣刪除時便可以從 Map 中查到 Element 再從 List 中刪除節點。最後需要一個屬性存儲緩存容量，當緩存達到容量上限時淘汰最先進入的緩存(此時需要從List中的 Element 刪除 Map 的key 所以可以自定義一個 cacheValue 同時包含 key 和 value 存儲到 鏈表的 Element 中)。其結構定義如下：

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

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

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

上篇文章緩存概述中有定義一組接口 分別需要實現 Put Get Delete。我們先來實現最簡單的 Delete，只需要先查詢緩存是否存在，如果存在將其刪除即可：

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

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

下面來實現相對簡單的 Get 接口，直接從 Map 中查詢如果存在就返回緩存的值和 exists 即可，不存在就返回 nil 和 not exists：

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

最後來實現 Put，首先應該檢查 key 是否存在如果存在就更新 key 存儲的值並將 List 中存儲的元素移動到鏈表尾(更新相當於是存入新值所以應該移動到鏈表尾)，如果不存在就創建新緩存分別插入到 Map 和 List尾(但是要注意插入前應該判斷緩存是否達到上限，達到上限就刪除 鏈表頭的緩存)：

func (c *FIFO) 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
}

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

package cache

import "testing"

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

	c := NewFIFO(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 ，key爲 1 的已經存在所以被移動到緩存淘汰算法的尾部
	c.Put(1, 1)
	assertExists(t, c, 1, 2, 3)

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

完整代碼

下面是上述 FIFO 實現的完整代碼：

package cache

import "container/list"

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

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

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

	// 緩存存在 從 Map 和 List 刪除之
	delete(c.keys, key)
	c.hot.Remove(ele)
}
func (c *FIFO) Get(key interface{}) (value interface{}, exists bool) {
	ele, exists := c.keys[key]
	if !exists {
		return
	}
	// 緩存存在 將緩存設置給返回值
	v := ele.Value.(cacheValue)
	value = v.Value
	return
}
func (c *FIFO) 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
}

FIFO 算法的問題

FIFO的緩存算法並不常用因爲命中率太低，對於所有數據FIFO都一視同仁按照先進先出的原則所以熱點數據和冷門數據在緩存中存在的權重是相同的，比如容量爲3所有數據能夠在緩存中存在的權重都是3，而爲了解決這一問題後續衍生了多種算法來試圖增加熱點數據的權重使用其能更久的存在與緩存中，同時降低冷門數據的權重使其能夠更快的被刪除。

下篇文章將介紹 LFU 算法試圖來解決熱點數據和冷門數據的權重問題。