本地內存緩存是一個在基礎軟件架構中非常常見的基礎設施，也正因其過於常見，以至於平時很少去思考它是如何實現的。在尚未設計緩存系統前，完全沒想到原來要需要考慮如此多複雜的事情。本文將由淺入深介紹如何設計一個現代的高性能內存緩存系統。
什麼時候需要本地內存緩存
在大部分業務系統中，都會使用諸如 Redis、Memcached 等遠程緩存，一方面可以避免自身進程內存佔用過大而導致的 OOM 或 GC 問題，另一方面也可以實現多個進程共享同一份一致的緩存數據。但對於某些底層服務（例如數據庫服務），遠程緩存的網絡延遲是不可接受的，這就勢必需要引入本地內存緩存。
本地內存緩存的特點
本地內存緩存可被視作一個基於本地內存的 「KeyValue 數據庫」。但相比較於傳統數據庫而言，它對一致性的要求十分寬鬆：
- 對於更新與刪除的操作，需要保證強一致性
- 對於插入操作可以容忍少量丟失
- 對於讀取操作可以容忍少量 Miss
與磁盤數據庫的另一個不同之處在於，磁盤數據庫的設計有一個前提假設是磁盤是可以隨需要而不斷擴容的，倘若一個磁盤數據庫因磁盤佔滿而崩潰主要責任是在使用方。而內存緩存則沒有這麼寬容的假設可以建立，它必須考慮到內存是昂貴且有限的這一事實。
除此之外，由於本地內存緩存處於業務進程當中，所以其需要考慮更多業務向的問題，比如：
- 由於自身大量老生代的內存佔用，是否會對所處進程產生 GC 問題。
- 當多線程場景下，如何同時解決線程安全、數據競爭、高吞吐等問題。
- 需要能夠適應一些非隨機的訪問統計規律，例如 Zipf。
綜上所述，我們可以歸納出對一個優秀的本地內存緩存系統的要求：
- 線程安全
- 高吞吐
- 高命中率
- 支持內存限制
實現路徑
在實現一個完整的緩存系統前，我們需要將目標一步步拆解。
首先為了實現緩存邏輯，我們必須有一個類 Map 的 KeyValue 數據結構，同時它必須是線程安全的。為了支持內存限制，我們必須要能夠驅逐一些 key，所以需要實現一個驅逐器。為了實現驅逐的同時維持高命中率，我們還需要告訴驅逐器每個 key 的訪問記錄，讓它能夠從中分析出哪些 key 可以被驅逐。綜上分析，我們可以整理出一個大概的 Roadmap：
- 實現一個線程安全的 Map 數據結構：存儲緩存內容
- 實現一個訪問記錄隊列：存儲訪問記錄
- 實現一個驅逐器：管理緩存內容
本文所有代碼均使用 Golang 編寫。
線程安全的 Map
簡易的 Map
cache := map[string]string{}
cache["a"] = "b"在 key 數量固定且極少的情況下，我們一般會用原生 Map 直接實現一個最簡單緩存。但 Golang 原生 Map 並不是線程安全的，當多個 goroutine 同時讀寫該對象時，會發生衝突。
線程安全的 SafeMap
type SafeMap struct {
lock sync.Mutex
store map[string]string
}
func (m *SafeMap) Get(k string) string {
m.lock.Lock()
defer m.lock.Unlock()
return m.store[k]
}
func (m *SafeMap) Set(k, v string) {
m.lock.Lock()
defer m.lock.Unlock()
m.store[k] = v
}這是一個最簡單的線程安全 Map 實現。對於訪問量很小的系統，這已經能夠成為一個非常方便快速的實現了，但需要注意的是，這個 Map 是被該進程下的所有線程所共享的，任何一個修改都需要去競爭得到一個鎖，如果套用數據庫領域的概念，這個鎖就是數據庫級別的鎖，顯然對於併發量大的時候是不適合的，會成為整個系統的瓶頸。
分段鎖的 SafeMap
type SafeMap struct {
locks []*sync.Mutex
store []map[string]string
}
func NewSafeMap() SafeMap {
return SafeMap{
locks: []*sync.Mutex{{}, {}, {}},
store: []map[string]string{{}, {}, {}},
}
}
func hash(k string) int {
h := fnv.New32a()
h.Write([]byte(k))
return int(h.Sum32())
}
func (m *SafeMap) GetLock(k string) *sync.Mutex {
idx := hash(k) % len(m.locks)
return m.locks[idx]
}
func (m *SafeMap) GetStore(k string) map[string]string {
idx := hash(k) % len(m.locks)
return m.store[idx]
}
func (m *SafeMap) Get(k string) string {
lock := m.GetLock(k)
lock.Lock()
defer lock.Unlock()
return m.GetStore(k)[k]
}
func (m *SafeMap) Set(k, v string) {
lock := m.GetLock(k)
lock.Lock()
defer lock.Unlock()
m.GetStore(k)[k] = v
}一個很自然的想法是將 key 進行分桶，從而分散對鎖的競爭。這種方法類似於將「數據庫鎖」打散成「表鎖」。到這一步，我們基本已經完成了一個最簡單的高併發緩存。
讀寫分段鎖的 SafeMap
考慮到緩存系統讀遠大於寫，我們可以對上述 Map 的互斥鎖 Mutex 改為 RWMutex ，從而使得讀時並不互斥，改善讀性能。
使用線程 ID 實現無鎖
需要注意的是，上述 Map 中，我們使用的分桶方法是利用 key 做隨機哈希，這種做法只能緩解鎖競爭的問題，卻無法根治。那麼是否有辦法根治這裡的鎖競爭呢？
辦法和代價都是有的。如果我們可以讓某一塊內存只被某個線程訪問，那麼就可以完全避免這些線程之間的鎖競爭，從而實現無鎖。假設每一個線程都有一個線程ID，我們可以按線程ID去分段，每個線程獨佔一個 SafeMap。
這樣做雖然避免了鎖，但也同時造成了數據「膨脹」。如果同一個 key 被N個線程 Set 了多次，此時內存中就多了 N 份同樣的數據。如果它只被 Set 了一次，也將導致其他線程沒法取得這個數據，從而出現非常高的 Miss 率。但對於那些極其熱門的少量 key，這種方式的確可以作為一種優化選擇。
令人遺憾的是，在 Golang 中，由於 GPM 調度模型的存在，在 Runtime 中屏蔽了線程所有相關信息，所以我們是沒有正常的辦法獲得「線程ID」的信息，因而此文暫不考慮上述方案。
使用 sync.Map 實現無鎖
準確來說， sync.Map 並不是完全的「無鎖」，只是一個在絕大部分讀場景是無鎖的線程安全 Map。具體原理可以參見相關文檔。但由於其底層實現並未採取分段鎖的方法，所以寫的時候會有一個 dirty 上的全局鎖，進而會影響到高併發寫時的性能。所以對於不在乎寫性能同時寫也相對不密集的時候，該數據結構是非常理想的選擇。
設計
訪問記錄隊列
對於訪問記錄的讀寫，同樣牽涉到多線程同時操作同一個內存地址的情況。但我們對其一致性會比緩存內容存儲更低，尤其是在高併發數據的假設下，少量的數據丟失並不會影響最終判斷結果。
與緩存內容存儲的場景不同的是，對於訪問記錄，每次 Get/Set 的時候都會需要進行一次寫入操作，所以它的寫速度要求遠高於前面的緩存內存存儲。更為關鍵的是，即便是在如此高密度的寫情況下，它也同樣需要保證線程安全。
雖然上述要求看似十分複雜，我們依然可以試著通過幾個方面的分析，來拆解這個問題。
在性能方面，我們需要保證該數據結構寫入時是無鎖的，因為一旦有鎖，前面做的降低鎖顆粒度優化都會被這個有鎖的結構給拖累。
在寫入方式方面，由於我們可以接受少量數據丟失，並且我們沒有非常實時的要求，所以我們可以接受異步的寫入。
在存儲內容方面，我們只需要存儲 Key 數據。
根據上述分析，我們不難發現我們需要的是一個基於內存的線程安全的無鎖 Lossy 隊列。但似乎並沒有現成的這種數據結構實現，所以我們可以退一步將這個問題變成，先實現一個 Lossy 隊列，再在此基礎上，實現線程安全的功能。
環形緩衝：RingBuffer
RingBuffer 是一個非常簡單的環形緩衝隊列，由一個數組，加上一個讀指針和寫指針構成。讀指針永遠只能讀到寫指針前的數據。
線程安全支持：sync.Pool
Golang 自帶的 sync.Pool 可以非常好地和 Ring Buffer 協同工作，實現在近乎無鎖的情況下，構造出一個線程安全的高吞吐緩衝隊列。
圖片來源： A Brief Analysis of Golang Sync.Pool
sync.Pool 會在每個線程中維護一個 private 的 Pool（無鎖），以及一個可以被其他線程 shared的 Pool（有鎖），細節原理可以參考相關文檔。在高併發場景下，它基本能夠保證每個線程都能夠獲得一個線程私有的 RingBuffer 對象，從而不需要對其加鎖。但 sync.Pool 有一個缺點是在 GC 時會被釋放掉，此時會丟失緩衝區內的數據。不過由於我們的前提假設是高併發場景，故而可以推導出數據的丟失量較之於全局是微乎其微的。然而在低併發場景下，這種做法有可能導致緩衝區一直被 GC 清理掉而喪失大部分統計數據。
這裡對 RingBuffer 做了一些簡單的改動，當緩衝區寫滿後，會將數據交給驅逐器統計，然後清空緩衝區。
import (
"sync"
)
type ringStripe struct {
store []uint64
capacity uint64
}
func newRingStripe(capacity uint64) *ringStripe {
return &ringStripe{
store: make([]uint64, 0, capacity),
capacity: capacity,
}
}
func (s *ringStripe) PushOrReturn(item uint64) []uint64 {
s.store = append(s.store, item)
if uint64(len(s.store)) >= s.capacity {
ret := s.store[:]
s.store = make([]uint64, 0, s.capacity)
return ret
}
return nil
}
type ringBuffer struct {
stripes []*ringStripe
pool *sync.Pool
}
func newRingBuffer(capacity uint64) *ringBuffer {
return &ringBuffer{
pool: &sync.Pool{
New: func() interface{} {
return newRingStripe(capacity)
},
},
}
}
func (b *ringBuffer) PushOrReturn(item uint64) []uint64 {
stripe := b.pool.Get().(*ringStripe)
defer b.pool.Put(stripe)
got := stripe.PushOrReturn(item)
return got
}
設計
驅逐器
驅逐策略
通過不停讀訪問記錄環形緩衝隊列，我們能夠拿到用戶的訪問記錄。此時我們有兩種驅逐策略：
- LRU（Least Recently Used） ：最少最近使用，即維護一個數組，越靠前訪問時間越近。
- LFU （Least Frequently Used）：最少頻率使用，即需要記錄 Key 使用的頻率，越低越容易被驅逐。
LRU 的問題在於，如果在某個數據在前9分鐘訪問了1萬次，最近1分鐘沒有訪問，那麼依然會認為該 key並不熱門而有可能被驅逐。
LFU 的問題在於，經常會有一些數據在某時刻非常極其熱門，但之後一直沒人訪問，例如因為某些原因被隱藏的用戶動態這類場景。另外，LFU 的頻率信息在緩存失效後依舊會存在內存中。
值得注意的一點是，緩存系統的驅逐往往是由於寫入而引起的，換句話說，是為了在緩存中，給更加重要的 key 騰出空間，才驅逐出那些沒它重要的 key。那麼問題來了，無論是 LRU 還是 LFU 的寫入過程中，都有一個假設是新來的 key 一定是更重要的，以至於我必須犧牲掉某個已有的 key。但這個假設很可能是不成立的。而且這種方式很容易導致一些冷門數據在短時間過熱導致緩存系統迅速驅逐出了原先的那些熱門數據。為了解決上述問題，於是就有了 TinyLFU。
TinyLFU 利用 LFU 作為寫入過濾器，只有當新來的 key 的頻率大於需要被驅逐的 key 時，此時才會執行寫入，否則只進行頻率信息的累加。也就是說所有新的 key 都會有一個被預熱的過程才能夠「夠格」被寫入緩存中。
但此時會存在的一個問題是，當有突發性的稀疏流量（sparse bursts）進來時，他們會由於一直無法建立足夠的頻率使得自己被緩存系統而接納，從而導致擊穿了緩存。為了解決這個問題，於是又有了 W-TinyLFU。
W-TinyLFU 算法吸收了上述算法的優點，在 TinyLFU 前面放了一個基於 LRU 的 Window Cache，從而可以使得前面提到的突發性稀疏流量會緩存在 Window Cache 裡，只有在 Window Cache 裡被淘汰的緩存才會過繼給後面的 TinyLFU。至於最後的 Main Cache，雖然 W-TinyLFU 使用了分段式 LRU 來實現，但我們也可以根據實際情況修改使其符合我們需要的常見。
TinyLFU && W-TinyLFU 算法是由 Gil Einziger、Roy Friedman 和 Ben Manes 三人在 15 年共同寫的論文： TinyLFU: A Highly Efficient Cache Admission Policy 所提出來的，後來 Ben Manes 還依照這個算法寫了一個 Java 領域備受歡迎的緩存系統
Caffeine 。為了簡化本文的實現，我們暫時先不實現 W-TinyLFU 算法（W-TinyLFU 的實現會另外寫一篇文章介紹），而是實現一個簡單的 LFU 驅逐策略。因此我們需要一個能夠用來記錄訪問頻率的數據結構。同時由於我們需要存儲所有 key 的信息，所以還需要這個數據結構能夠有效減少 key 的存儲體積。
即便有了上面的頻率計數器，為了找到那個需要被驅逐的 LFU key，我們似乎需要遍歷所有 key。所以我們不得不再引入一個驅逐候選列表來幫助我們提前排序好需要驅逐的 key。
綜上，我們還需要再實現：
- 能夠有效壓縮數據大小的頻率計數器
- 預先排序的驅逐候選池
頻率計數器：Count-Min Sketch
Count-Min 算法和布隆過濾器類似，核心思想還是通過將相同 Hash 值的數據共享同一份存儲空間，以減小整體體積。h1~hd 代表不同的 Hash 算法，這裡的 value 代表我們要存儲的 key，橫座標表示 Hash 後的值，對哈希值對應每個網格進行 +1 操作。當需要計算某個 key 的估計值時，取對應所有網格數值的最小值。
為了避免一些短時間熱度的 key 一直殘留在緩存中，每隔一個時間間隔，還需要將所有網格計數器衰減一半。
驅逐候選池：最小堆
最小堆是大家所熟知的二叉樹結構，任一非葉子節點值不大於其子節點值。它有著O(1)的獲取最小值速度，和 O(log n)的插入速度。
顯然我們無法為所有 key 維護一個最小堆，所以我們需要為其設定一個固定的大小，只保存那些需要被驅逐的 key。當需要驅逐出某個 key 時，會從最小堆上取第一個 key，然後刪除緩存。
設計
總結
經過一系列的步驟，我們終於實現了一個滿足我們要求的現代內存緩存系統。可以看到，在緩存系統的設計中，對性能影響最大的是緩存的存儲層，需要非常小心地進行鎖的設計和優化。而對於緩存系統命中率影響最大，同時也是實現算法上最複雜的還是淘汰策略的選擇。現代的許多內存緩存系統所選擇的淘汰策略各有不同，許多都在現有的算法基礎上做過一些自己的修改。即便一些緩存系統在 Benchmark 中非常優秀，但如果其測試數據訪問模式與你的實際使用場景並不一致，它的數據對你的參考意義也並不大。所以依舊需要針對性地進行模擬壓測才能夠知道什麼樣的緩存系統適合你業務的場景。
閱讀更多 sandag 的文章
