00. 什么是 freecache？

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

相關(guān)的 github 地址：https://github.com/coocood/freecache

它有幾個特性值得注意：

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

這幾個優(yōu)秀特性使得他非常適合用在生產(chǎn)環(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. 功能概覽

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

• 如何做到零 gc？
• 數(shù)據(jù)結(jié)構(gòu)
• 動態(tài)索引
• 緩存失效

03. 如何做到 0 GC？

這個庫之所以做到了 0 gc，是因為設(shè)定了很巧妙的數(shù)據(jù)結(jié)構(gòu)，這個數(shù)據(jù)結(jié)構(gòu)有以下的特點：

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

04. 數(shù)據(jù)結(jié)構(gòu)

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

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

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

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

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

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

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

05. 動態(tài)索引

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

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

06. 緩存失效

緩存失效主要包括兩種：

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

這兩種失效都有缺陷。

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

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

以上就是Go 語言進(jìn)階freecache源碼學(xué)習(xí)教程的詳細(xì)內(nèi)容，更多關(guān)于Go語言freecache的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論