概念

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

不同用例

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

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

愚蠢的設(shè)計(jì)

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

更好的方式

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

限制條件

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

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

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

需求

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

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

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

API設(shè)計(jì)

鍵值存儲(chǔ)的意思是，如果請(qǐng)求鍵，緩存會(huì)返回那些存在的鍵的值，類似于hash-map抽象數(shù)據(jù)類型，以提供以下API概念的應(yīng)用程序?yàn)槔?

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

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

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

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

設(shè)計(jì)概念

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

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

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

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

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

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

并發(fā)控制

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

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

并發(fā)問(wèn)題案例

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

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

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

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

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

防止這種情況發(fā)生的最簡(jiǎn)單方法是使用互斥(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ù)存儲(chǔ)訪問(wèn)功能，如Put、Delete、Clear等。

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

生存時(shí)間(Time To Live)

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

這種方法不需要消耗大量CPU時(shí)間來(lái)定期遍歷所有節(jié)點(diǎn)，但是緩存很可能會(huì)保存過(guò)期的值。

大多數(shù)情況下，這么做沒(méi)有問(wèn)題，因?yàn)檫^(guò)期節(jié)點(diǎn)很可能是"最近最少使用"狀態(tài)。但是，如果有函數(shù)通過(guò)數(shù)據(jù)結(jié)構(gòu)清除過(guò)期節(jié)點(diǎn)就更好了，所以我們使用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)用以清除所有過(guò)期節(jié)點(diǎn)。

結(jié)果

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

結(jié)論

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

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

審核編輯：劉清