基于Go的緩存實現(xiàn)方法

概念

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

不同用例

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

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

愚蠢的設計

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

更好的方式

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

限制條件

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

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

設計&實現(xiàn)

需求

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

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

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

API設計

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

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

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

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

數(shù)據結構

設計概念

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

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

雙向鏈表: LRU緩存可以通過雙向鏈表實現(xiàn)。

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

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

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

并發(fā)控制

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

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

并發(fā)問題案例

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

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

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

A的調用繼續(xù)執(zhí)行，從鏈表中刪除節(jié)點1，從hash-map中刪除鍵1。

緊接著，B的調用試圖訪問節(jié)點1的地址，并發(fā)現(xiàn)該地址已不存在，從而發(fā)生panic并造成應用失效。

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

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

生存時間(Time To Live)

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

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

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

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

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

結果

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

結論

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

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

審核編輯：劉清