概念

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

不同用例

Web服務(wù)中的緩存用于減少數(shù)據(jù)請求的延遲。Web服務(wù)保存第一次查詢的執(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è)計

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

更好的方式

在這種情況下，可以使用單一外部緩存(如上圖所示)，多個服務(wù)器只訪問統(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，先入先出)這樣的詞，這些是"選擇哪一個"的標(biāo)準(zhǔn)，被稱為驅(qū)逐策略(eviction policy)。

設(shè)計&實現(xiàn)

需求

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

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

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

API設(shè)計

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

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

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

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

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

設(shè)計概念

我們使用兩種不同的數(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[]定義。

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

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

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

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

并發(fā)控制

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

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

并發(fā)問題案例

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

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

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

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

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

防止這種情況發(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關(guān)鍵字，將行執(zhí)行推遲到函數(shù)的末尾)。這些代碼應(yīng)用于所有其他數(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{
varcountint64=0
forkey,value:=ranges.table{
ifvalue.ttl.Before(time.Now()){
s.Delete(key)
count++
}
}
returncount
}

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

結(jié)果

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

結(jié)論

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

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

審核編輯：劉清