概念

緩存是計算機科學中的一個重要概念。設想某個組件需要訪問外部資源，它向外部源請求資源，接收并使用資源，這些步驟都需要花費時間。當組件再次需要資源時，可以再次請求資源，但這種方式從時間上考慮是比較低效的。相反，組件可以將請求結果保存在本地某處，然后再次使用，使用本地數據總是比請求外部數據要快，這一策略就是緩存的基本概念。我們可以在內存、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)。

設計&實現

需求

鍵值存儲(Key-Value Storage): 緩存既要有輸入鍵、輸出值的讀功能，也要有輸入鍵、值的寫功能。這些函數應該在平均O(logN)時間內完成，其中N是鍵的數量。

LRU驅逐策略: 由于緩存空間有限，如果緩存滿了，一些數據應該被清除，選擇用LRU算法實現。

TTL (Time To Live): 每個鍵值都有生存時間，如果TTL到期，該鍵值應該被驅逐。

API設計

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

funcGet(keystring)(hitbool,value[]byte)
funcPut(keystring,value[]byte)(hitbool)

Get: 通過鍵讀取值的API。如果所提供的鍵在緩存中存在，則返回等效值。如果不存在，則返回hit=false。對于LRU策略，鍵將被標記為最近被使用，從而使該鍵不會被驅逐。

Put: 通過鍵寫入值的API。如果所提供的鍵存在，則value將被替換為新值。如果不存在，將創建新的鍵值存儲。因為該函數可以添加數據，其執行可能會導致溢出。在這種情況下，根據LRU策略，最近最少使用的鍵值將被清除。新添加/修改的鍵將被標記為最近使用的鍵。

數據結構

設計概念

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

Hash-map: Hash-map是使用最廣泛的鍵值數據結構，在Go中是現成的數據類型，可以通過map[]定義。

雙向鏈表: LRU緩存可以通過雙向鏈表實現。

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

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

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

并發控制

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

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

并發問題案例

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

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

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

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

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

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

func(s*CStorage)Get(keystring)(data[]byte,hitbool){
s.mutex.Lock()
defers.mutex.Unlock()

n,ok:=s.table[key]
if!ok{
returnnil,false
}
ifn.ttl.Before(time.Now()){
s.evict(n)
s.size--
returnnil,false
}

returnn.data,true
}

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

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

生存時間(Time To Live)

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

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

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

func(s*CStorage)RemoveExpired()int64{
varcountint64=0
forkey,value:=ranges.table{
ifvalue.ttl.Before(time.Now()){
s.Delete(key)
count++
}
}
returncount
}

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

結果

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

結論

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

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

審核編輯：劉清