00. 什么是 freecache？

freecache 是一個用 go 語言實現的本地緩存系統(tǒng)（類似于 lru）。

相關的 github 地址：https://github.com/coocood/freecache

它有幾個特性值得注意：

• 通過優(yōu)秀的內存管理方案，實現了 go 語言的零 gc
• 是線程安全的，同時支持一定程度的并發(fā)，非常適合并發(fā)場景
• 支持設置失效時間，動態(tài)失效過期緩存
• 在一定程度上支持 lru，即“最近最少使用”，會在容量不足的時候優(yōu)先淘汰較早的數據

這幾個優(yōu)秀特性使得他非常適合用在生產環(huán)境中作為本地緩存。

01. 簡單用法

cacheSize := 100 * 1024 * 1024
cache := freecache.NewCache(cacheSize)
debug.SetGCPercent(20)
key := []byte("abc")
val := []byte("def")
expire := 60 // expire in 60 seconds
cache.Set(key, val, expire)
got, err := cache.Get(key)
if err != nil {
    fmt.Println(err)
} else {
    fmt.Println(string(got))
}
affected := cache.Del(key)
fmt.Println("deleted key ", affected)
fmt.Println("entry count ", cache.EntryCount())

02. 功能概覽

本文計劃先以自然語言描述下列功能的實現方式，再接下來的章節(jié)中深入源碼，扒出其具體實現

• 如何做到零 gc？
• 數據結構
• 動態(tài)索引
• 緩存失效

03. 如何做到 0 GC？

這個庫之所以做到了 0 gc，是因為設定了很巧妙的數據結構，這個數據結構有以下的特點：

• 無論存多少數據，都只會存在 512 個指針
• 所有的具體數據的存儲空間，都是預先就分配好的，而不是動態(tài)分配的
• 使用了一些黑科技，比如強制類型轉換以及結構體對齊等技術，將所有的動態(tài)數據都管理在預先分配好的連續(xù)空間內

04. 數據結構

可以將這個數據結構大體上抽象成一個哈希表。即你會看到哈希函數以及對應的數組空間。但是他和傳統(tǒng)的哈希表是有區(qū)別的，主要有以下幾點：

• 線程安全，支持高并發(fā)，內存空間高度優(yōu)化：

• 為了做到支持高并發(fā)以及線程安全，并且保證內存空間的可用性，freecache 實際上劃分出了 256 個獨立數組空間用來存儲對應的底層數據。
• 這樣在并發(fā)訪問的時候，通過對 key 進行分片，使得請求只會打到一個數組空間上，即只會對這 256 個空間中的一個空間加鎖，這樣就大大降低了資源爭搶。

• 數據的組織方式與傳統(tǒng)哈希表不同：

• 傳統(tǒng)的哈希表只在數組空間中存 value。而 freecache 則不同，他將 key，value 全部存在了數組空間中。
• 傳統(tǒng)哈希表的數組是稀疏的。freecache 數據并不是稀疏的，而是連續(xù)的，即新的值會不斷 append 到最后。
• 傳統(tǒng)哈希表使用 hash func 對 key 取索引，索引到稀疏數組中的位置。而 freecache 則通過維護了一個叫“slot（插槽）”的數據結構，通過對 key 進行 hash func，先拿到對應的 slot，然后 slot 中維護著一個索引，可以定位到具體的數據在數組中的位置。
• 解決哈希沖突的方式不同。當遇到哈希沖突的時候，哈希表需要對底層的稀疏數組進行擴容，會導致可用性大大降低。而 freecache 則是只需要對“slot”的指針數組進行擴容，而無需改變底層數組。因為 slot 指針數組的大小遠小于底層數組，所以擴容的成本是非常非常低的。

• 為了實現緩存淘汰以及定時失效，它的數組空間在邏輯上是一個環(huán)狀的。這么做有以下原因

• 數組存的數據邏輯上是連續(xù)的，而非稀疏數組。充分利用了CPU對數組讀取的緩存優(yōu)化
• 通過使用了一系列的首尾計算方式，是足以保證讀取和存儲在首尾的連續(xù)性。比如讀數據的時候讀到結尾如果還沒讀完，會跳轉到頭部繼續(xù)往下讀。
• 能以 O（1） 的時間復雜度完成新數據對舊數據的淘汰。我們假設如果數組在邏輯上不是環(huán)形的，那么當數組寫滿的時候再寫入新的數據，就需要把數組頭部的數據刪除掉，然后再把之后的數據統(tǒng)統(tǒng)向左移動刪除數據的長度，然后再從最右端寫入新的數據。反之，如果數組是環(huán)形的，只需要在數組頭部把舊數據覆蓋即可
• 通過一些算法手段，可以實現一個很 hack 的 lru 功能。在一定程度上能保證“最近最少使用”的淘汰。

05. 動態(tài)索引

通過上面對數據結構的分析，我們知道他和傳統(tǒng)的哈希表的實現方式大相徑庭。它實際上是使用了一種叫“插槽”的數據結構，專門負責通過 key 索引到數據空間中的某個位置。他的實現比較有意思。它的底層是一個結構體指針數組。他是可以動態(tài)擴容的。每個插槽有一個 id，叫 slotId，范圍是 0～255。當遇到哈希沖突的時候，比如出現了2個 slotId 為 100 的 slot，他就會檢測當前的最大重復 slotID 數量 n。如果這個 2 大于 n，他就會擴容到 2n。

// slot 的數據結構
type entryPtr struct {
	offset   int64  // 記錄了當前 slot 在環(huán)形數組中的偏移量
	hash16   uint16 // 一個 hash 值，用于在 segment 中定位到具體的 slot
	keyLen   uint16 // used to compare a key
	reserved uint32
}
// 每個分片的數據結構
type segment struct {
	rb            RingBuf // 環(huán)形數組
	segId         int
	hitCount      int64
	missCount     int64
	entryCount    int64
	totalCount    int64      // 之后計算 lru 的時候會用到，用于衡量一個數據是否是熱點數據
	totalTime     int64      // 之后計算 lru 的時候會用到，用于衡量一個數據是否是熱點數據
	totalEvacuate int64      // used for debug
	totalExpired  int64      // used for debug
	overwrites    int64      // used for debug
	vacuumLen     int64      // 環(huán)形數組可用容量，主要用于環(huán)形數組首尾相接的算法
	slotLens      [256]int32 // 每個 slotId 的長度的數組
	slotCap       int32      // 每個 slotId 的容量
	slotsData     []entryPtr // 存儲 slots 的切片，根據 hash16 進行順序排列。相同的 hash16 擁有相同的 slotId
}

06. 緩存失效

緩存失效主要包括兩種：

• 基于過期時間的失效
• 基于最近最少使用的失效

這兩種失效都有缺陷。

首先它是一種被動失效，而不是通過一個額外的線程定期check。而是每次 set 新的值的時候，如果發(fā)現空間不夠用了，他才會嘗試從環(huán)形數組的頭端進行check。如果發(fā)現當前check的數據過期了，或者使用頻率過低，就會將記錄有效數據的頭指針進行偏移，即相當于“失效”。如果檢查多次都沒能找到需要失效的數據，那么他會將這些檢查過的數據轉移到尾部，并強制當前的頭部的數據失效。

這種失效是不可靠的。比如一個數據，如果在環(huán)形數組的中間，那么即便它過期了，也很難被 check 到。并且存在一定的失誤概率，即將一個熱點數據給失效了。

以上就是Go 語言進階freecache源碼學習教程的詳細內容，更多關于Go語言freecache的資料請關注腳本之家其它相關文章！

最新評論