基於 Go 的緩存實現

緩存是架構設計中的常用概念，本文基於 Go 實現了一個簡單的緩存組件，支持最基本的緩存操作。原文: Implementing Cache With Go[1]

客戶端 - 服務器緩存

簡介

概念

緩存是計算機科學中的一個重要概念。設想某個組件需要訪問外部資源，它向外部源請求資源，接收並使用資源，這些步驟都需要花費時間。當組件再次需要資源時，可以再次請求資源，但這種方式從時間上考慮是比較低效的。相反，組件可以將請求結果保存在本地某處，然後再次使用，使用本地數據總是比請求外部數據要快，這一策略就是緩存的基本概念。我們可以在內存、CPU 緩存和服務器緩存 (如 Redis) 中找到這些例子。

不同用例

Web 服務中的緩存用於減少數據請求的延遲。Web 服務保存第一次查詢的執行結果，然後在需要的時候再次使用，而不用再次訪問數據庫。取決於數據的特性，緩存有不同情況，可以有相對靜態的數據，如統計數據、計算結果，也有可能是經常變化的數據，如評論區或 SNS。

最好的情況是緩存那些很少變化的數據。以月度統計數據爲例，上個月的數據將不會變化，如果對它進行緩存，可能就不需要查詢數據庫獲取上個月的數據了。

愚蠢的設計

對於快速變化的數據，在存在多個服務器時最好謹慎些。看看上面的設計，以評論區服務爲例，考慮如下場景，用戶 A 發表了一些評論，然後 A 決定刪除評論，用戶 B 嘗試回覆評論。在某些情況下，A 和 B 向不同的服務器發送請求。A 的刪除操作可能不會傳播到 B 的服務器緩存。結果會是這樣: 緩存 A 和緩存 B 有不同的數據，數據庫不知道哪個纔是真實的，數據的完整性被破壞了。

更好的方式

在這種情況下，可以使用單一外部緩存 (如上圖所示)，多個服務器只訪問統一的緩存。

限制條件

緩存比數據庫要快，但在大小上要小得多。這是因爲數據庫將數據存儲在驅動器中，緩存將數據存儲在內存中。它們遵循各自相同的特徵，同樣也有不同的特點，如果主機停止工作，緩存的所有數據都會丟失，但數據庫的數據不會丟失。

由於緩存位於內存中，空間是有限的，需要選擇緩存哪些數據。在 CS 課上，我們會聽到 LRU(Least Recently Used，最近最少使用)，LFU(Least Frequently Used，最不常用) 和 FIFO(First In First Out，先入先出) 這樣的詞，這些是 "選擇哪一個" 的標準，被稱爲驅逐策略 (eviction policy)。

設計 & 實現

需求
API 設計

鍵值存儲的意思是，如果請求鍵，緩存會返回那些存在的鍵的值，類似於 hash-map 抽象數據類型，以提供以下 API 概念的應用程序爲例:

func Get(key string) (hit bool, value []byte)
func Put(key string, value []byte) (hit bool)
數據結構

設計概念

我們使用兩種不同的數據結構: hash-map 和雙向鏈表，實現鍵值讀寫和 LRU 策略的特性。

基於這兩種數據結構可以同時提供鍵值特性和 LRU 策略。參考以上設計概念圖，hash-map 的鍵將是字符串鍵，值是指向鏈表節點的指針，節點將保存鍵的值。

如果用戶調用Get()，緩存應用程序將在 hash-map 中搜索鍵，跟隨指針到達鏈表中的一個節點，獲取值，完成 LRU 策略，並將值返回給用戶。

類似的，如果調用Put()，會在 hash-map 中搜索鍵，跟蹤指針並替換值，完成 LRU 策略，或者向 hash-map 中插入新鍵，並向鏈表中插入新節點。

併發控制

由於緩存被設計爲支持頻繁訪問，因此在同一時間會有多個訪問，並且總是存在併發問題的可能性。

在該設計中，存在兩種不同的數據結構，並且並不總是同步的。在執行過程中，hash-map 的修改和鏈表的修改之間有一個微小的時間間隔，請看下面的例子。

併發問題案例

  1. 該問題的觸發條件爲: 當前緩存已滿，最近最少使用的鍵爲 1。這意味着，如果添加了新的鍵，鍵 1 和等效的值將被清除。

  2. 用戶 A 使用新鍵 101 調用 Put()。hash-map 檢查鍵，發現 101 不存在，決定清除 1 並將 101 添加到緩存中。

  3. 同時，用戶 B 使用鍵 1 調用 Put()。hash-map 確認鍵 1 存在，並決定修改該值。

  4. A 的調用繼續執行，從鏈表中刪除節點 1，從 hash-map 中刪除鍵 1。

  5. 緊接着，B 的調用試圖訪問節點 1 的地址，並發現該地址已不存在，從而發生 panic 並造成應用失效。

防止這種情況發生的最簡單方法是使用互斥 (Mutex) ，參考以下代碼。

func (s *CStorage) Get(key string) (data []byte, hit bool) {
  s.mutex.Lock()
  defer s.mutex.Unlock()
  
  n, ok := s.table[key]
  if !ok {
    return nil, false
  }
  if n.ttl.Before(time.Now()) {
    s.evict(n)
    s.size--
    return nil, false
  }
  
  return n.data, true
}

這段代碼是Get()的函數定義，可以看到在第一行中有互斥鎖代碼，在第二行中有 defer 的互斥鎖解鎖代碼 (defer 是 Go 關鍵字，將行執行推遲到函數的末尾)。這些代碼應用於所有其他數據存儲訪問功能，如 Put、Delete、Clear 等。

通過使用互斥鎖，每次執行都不會受到其他操作的影響，保證了數據訪問的安全性。

生存時間 (Time To Live)

目前 TTL 是採用被動方式實現的，這意味着如果執行了數據訪問函數 (Get, Put)，它將檢查 TTL 是否過期並決定是否刪除。這也意味着即使節點已經過期，將仍然存在於數據結構中。

這種方法不需要消耗大量 CPU 時間來定期遍歷所有節點，但是緩存很可能會保存過期的值。

大多數情況下，這麼做沒有問題，因爲過期節點很可能是 "最近最少使用" 狀態。但是，如果有函數通過數據結構清除過期節點就更好了，所以我們使用RemoveExpired()函數。

func (s *CStorage) RemoveExpired() int64 {
  var count int64 = 0
  for key, value := range s.table {
    if value.ttl.Before(time.Now()) {
      s.Delete(key)
      count++
    }
  }
  return count
}

此函數將被定期調用以清除所有過期節點。

結果

實現的 Go 包可以導入其他 Go 項目。另外，我還做了獨立的緩存應用程序，提供 gRPC API，細節可以查看這個存儲庫 [2]。

結論

這是個很好的重新審視緩存概念的機會，並且我們用 Go 實現了緩存。緩存是降低組件延遲的好工具，雖然空間受限，但速度更快。

實現實際的緩存模塊可以用 hash-map 和雙向鏈表完成。併發問題有點棘手，所以不得不使用互斥鎖。此外，我們混合了被動和主動方式來刪除過期數據。

你好，我是俞凡，在 Motorola 做過研發，現在在 Mavenir 做技術工作，對通信、網絡、後端架構、雲原生、DevOps、CICD、區塊鏈、AI 等技術始終保持着濃厚的興趣，平時喜歡閱讀、思考，相信持續學習、終身成長，歡迎一起交流學習。
微信公衆號：DeepNoMind

參考資料

[1]

Implementing Cache With Go: https://medium.com/@cocm1324/implementing-cache-with-go-71e29fcdaf7

[2]

gcache: https://github.com/cocm1324/gcache

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/rP6QCrPG6BQaokpOYnVtHw

猜你喜歡