Go使用緩存加速外部資源訪問提高性能效率

更新時間：2023年10月17日 11:27:43 作者：俞凡

緩存是架構(gòu)設計中的常用概念，本文基于Go實現(xiàn)了一個簡單的緩存組件，支持最基本的緩存操作，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪

概念簡介

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

不同用例

Web服務中的緩存用于減少數(shù)據(jù)請求的延遲。Web服務保存第一次查詢的執(zhí)行結(jié)果，然后在需要的時候再次使用，而不用再次訪問數(shù)據(jù)庫。取決于數(shù)據(jù)的特性，緩存有不同情況，可以有相對靜態(tài)的數(shù)據(jù)，如統(tǒng)計數(shù)據(jù)、計算結(jié)果，也有可能是經(jīng)常變化的數(shù)據(jù)，如評論區(qū)或SNS。

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

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

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

限制條件

緩存比數(shù)據(jù)庫要快，但在大小上要小得多。這是因為數(shù)據(jù)庫將數(shù)據(jù)存儲在驅(qū)動器中，緩存將數(shù)據(jù)存儲在內(nèi)存中。它們遵循各自相同的特征，同樣也有不同的特點，如果主機停止工作，緩存的所有數(shù)據(jù)都會丟失，但數(shù)據(jù)庫的數(shù)據(jù)不會丟失。

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

設計&實現(xiàn)

需求

鍵值存儲(Key-Value Storage): 緩存既要有輸入鍵、輸出值的讀功能，也要有輸入鍵、值的寫功能。這些函數(shù)應該在平均O(logN)時間內(nèi)完成，其中N是鍵的數(shù)量。
LRU驅(qū)逐策略: 由于緩存空間有限，如果緩存滿了，一些數(shù)據(jù)應該被清除，選擇用LRU算法實現(xiàn)。
TTL (Time To Live): 每個鍵值都有生存時間，如果TTL到期，該鍵值應該被驅(qū)逐。

API設計

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

func Get(key string) (hit bool, value []byte)
func Put(key string, value []byte) (hit bool)

Get: 通過鍵讀取值的API。如果所提供的鍵在緩存中存在，則返回等效值。如果不存在，則返回hit=false。對于LRU策略，鍵將被標記為最近被使用，從而使該鍵不會被驅(qū)逐。
Put: 通過鍵寫入值的API。如果所提供的鍵存在，則value將被替換為新值。如果不存在，將創(chuàng)建新的鍵值存儲。因為該函數(shù)可以添加數(shù)據(jù)，其執(zhí)行可能會導致溢出。在這種情況下，根據(jù)LRU策略，最近最少使用的鍵值將被清除。新添加/修改的鍵將被標記為最近使用的鍵。

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

我們使用兩種不同的數(shù)據(jù)結(jié)構(gòu): hash-map和雙向鏈表，實現(xiàn)鍵值讀寫和LRU策略的特性。

Hash-map: Hash-map是使用最廣泛的鍵值數(shù)據(jù)結(jié)構(gòu)，在Go中是現(xiàn)成的數(shù)據(jù)類型，可以通過map[<type>]<type>定義。
雙向鏈表: LRU緩存可以通過雙向鏈表實現(xiàn)。

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

如果用戶調(diào)用Get()，緩存應用程序?qū)⒃趆ash-map中搜索鍵，跟隨指針到達鏈表中的一個節(jié)點，獲取值，完成LRU策略，并將值返回給用戶。

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

并發(fā)控制

由于緩存被設計為支持頻繁訪問，因此在同一時間會有多個訪問，并且總是存在并發(fā)問題的可能性。

在該設計中，存在兩種不同的數(shù)據(jù)結(jié)構(gòu)，并且并不總是同步的。在執(zhí)行過程中，hash-map的修改和鏈表的修改之間有一個微小的時間間隔，請看下面的例子。

該問題的觸發(fā)條件為: 當前緩存已滿，最近最少使用的鍵為1。這意味著，如果添加了新的鍵，鍵1和等效的值將被清除。
用戶A使用新鍵101調(diào)用Put()。hash-map檢查鍵，發(fā)現(xiàn)101不存在，決定清除1并將101添加到緩存中。
同時，用戶B使用鍵1調(diào)用Put()。hash-map確認鍵1存在，并決定修改該值。
A的調(diào)用繼續(xù)執(zhí)行，從鏈表中刪除節(jié)點1，從hash-map中刪除鍵1。
緊接著，B的調(diào)用試圖訪問節(jié)點1的地址，并發(fā)現(xiàn)該地址已不存在，從而發(fā)生panic并造成應用失效。

防止這種情況發(fā)生的最簡單方法是使用互斥(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()的函數(shù)定義，可以看到在第一行中有互斥鎖代碼，在第二行中有defer的互斥鎖解鎖代碼(defer是Go關鍵字，將行執(zhí)行推遲到函數(shù)的末尾)。這些代碼應用于所有其他數(shù)據(jù)存儲訪問功能，如Put、Delete、Clear等。

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

生存時間(Time To Live)

目前TTL是采用被動方式實現(xiàn)的，這意味著如果執(zhí)行了數(shù)據(jù)訪問函數(shù)(Get, Put)，它將檢查TTL是否過期并決定是否刪除。這也意味著即使節(jié)點已經(jīng)過期，將仍然存在于數(shù)據(jù)結(jié)構(gòu)中。

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

大多數(shù)情況下，這么做沒有問題，因為過期節(jié)點很可能是"最近最少使用"狀態(tài)。但是，如果有函數(shù)通過數(shù)據(jù)結(jié)構(gòu)清除過期節(jié)點就更好了，所以我們使用RemoveExpired()函數(shù)。

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
}

此函數(shù)將被定期調(diào)用以清除所有過期節(jié)點。