通用緩存引擎cachelib介紹

背景

網(wǎng)絡(luò)服務(wù)幾乎在系統(tǒng)架構(gòu)的每一層都依賴于緩存。大型網(wǎng)絡(luò)服務(wù)依靠緩存系統(tǒng)來實(shí)現(xiàn)高性能和高效率。例如，在Facebook，CDN緩存為70%的網(wǎng)絡(luò)請(qǐng)求提供服務(wù)，將延遲降低了一個(gè)或多個(gè)數(shù)量級(jí)。一臺(tái)緩存服務(wù)器可以取代幾十臺(tái)后端數(shù)據(jù)庫服務(wù)器，實(shí)現(xiàn)20倍的吞吐量和超過80%的命中率。通常，每個(gè)緩存都是由一個(gè)不同的團(tuán)隊(duì)獨(dú)立實(shí)現(xiàn)和維護(hù)的，并且對(duì)其功能高度專業(yè)化。在Facebook，各種各樣的緩存系統(tǒng)構(gòu)成了系統(tǒng)架構(gòu)的一個(gè)組成部分。Facebook的架構(gòu)包括CDN緩存、鍵值應(yīng)用緩存、社交圖譜緩存和媒體緩存（圖1）。緩存在亞馬遜、Twitter、Reddit以及其他許多大型網(wǎng)絡(luò)服務(wù)中扮演著類似的角色。然而，每個(gè)團(tuán)隊(duì)獨(dú)立實(shí)現(xiàn)和維護(hù)的緩存系統(tǒng)存在重復(fù)的邏輯和功能，忽略了不同緩存系統(tǒng)共同面臨的困難挑戰(zhàn)，大大增加了部署、維護(hù)和擴(kuò)展每個(gè)緩存所需的整體努力。

問題

1. 多種緩存系統(tǒng)的冗余

Facebook的每個(gè)緩存系統(tǒng)都是單獨(dú)實(shí)現(xiàn)的。例如，如圖1所示，F(xiàn)acebook分別設(shè)計(jì)了CDN緩存、鍵值緩存、社交圖譜緩存、存儲(chǔ)緩存、數(shù)據(jù)庫緩存，以及其他許多緩存。這些高度專業(yè)化的系統(tǒng)都需要一個(gè)高度專業(yè)化的緩存，以實(shí)現(xiàn)復(fù)雜的一致性協(xié)議，利用自定義的數(shù)據(jù)結(jié)構(gòu)，并針對(duì)所需的硬件平臺(tái)進(jìn)行優(yōu)化。盡管這些緩存系統(tǒng)服務(wù)于不同的工作負(fù)載，需要不同的功能，但它們?cè)谠O(shè)計(jì)和部署方面有許多共同的挑戰(zhàn)。所有這些系統(tǒng)每秒都要處理數(shù)以百萬計(jì)的查詢，緩存工作集大到需要同時(shí)使用閃存和DRAM進(jìn)行緩存，并且必須容忍因應(yīng)用程序更新而頻繁重啟，這在Facebook的生產(chǎn)環(huán)境中很常見。隨著Facebook的緩存系統(tǒng)數(shù)量的增加，為每個(gè)系統(tǒng)維持獨(dú)立的緩存實(shí)現(xiàn)變得難以維持。通過重復(fù)解決相同的工程難題，團(tuán)隊(duì)重復(fù)了彼此的努力，產(chǎn)生了多余的代碼。此外，維護(hù)獨(dú)立的緩存系統(tǒng)也阻礙了系統(tǒng)之間分享性能優(yōu)化帶來的效率提升。

圖1 緩存類型

2. DRAM開銷

隨著傳統(tǒng)的動(dòng)態(tài)隨機(jī)存取存儲(chǔ)器 (DRAM) 緩存變得更加昂貴并且需要更多的能力來擴(kuò)展。在大型服務(wù)器的場(chǎng)景下，全部采用DRAM作為緩存介質(zhì)是不現(xiàn)實(shí)的，這將會(huì)造成巨大的成本開銷。像 Facebook 這樣的公司正在探索硬件選擇，例如非易失性存儲(chǔ)器 (NVM) 驅(qū)動(dòng)器來增強(qiáng)他們的緩存系統(tǒng)。這種 DRAM 和 NVM 混合模型向前邁進(jìn)了一步，但需要?jiǎng)?chuàng)新的緩存設(shè)計(jì)來利用混合緩存的全部潛力。

探索

1. 緩存數(shù)據(jù)集分布（冷熱）

工作負(fù)載的流行度分布衡量的是每個(gè)鍵在某個(gè)時(shí)間范圍內(nèi)的取樣跟蹤的頻率。這些頻率表明系統(tǒng)中不同對(duì)象的相對(duì)受歡迎程度。之前對(duì)CDN和網(wǎng)絡(luò)工作負(fù)載的測(cè)量表明，高度傾斜的Zipf分布是一種常見的流行分布。在Zipf分布中，"最受歡迎的20%的對(duì)象占了80%的請(qǐng)求"。圖2顯示了Facebook四個(gè)工作負(fù)載的對(duì)數(shù)尺度的流行分布。在這個(gè)尺度上，Zipf分布將是一條具有負(fù)斜率（-α）的直線。Lookaside是四個(gè)系統(tǒng)中唯一一個(gè)流行度分布為Zipfian的系統(tǒng)，α接近于1。Storage的分布在分布的頭部更平坦，盡管尾部遵循Zipf分布。此外，盡管是Zip-fian分布，SocialGraph和CDN的分布分別表現(xiàn)為α=0.55和α=0.7。較低的α意味著明顯較高比例的請(qǐng)求進(jìn)入流行分布的尾部，這導(dǎo)致了更大的工作集。

圖2 數(shù)據(jù)集流行度分布

2. 緩存數(shù)據(jù)集分布流失（冷熱變化）

流失指的是由于新keys的引入和現(xiàn)有keys的流行程度隨著時(shí)間的推移而產(chǎn)生的工作集的變化。流行的YCSB工作負(fù)載生成器假設(shè)沒有流失，即每個(gè)密鑰在整個(gè)基準(zhǔn)期間保持同樣的流行。這個(gè)基準(zhǔn)和無流失假設(shè)被廣泛用于系統(tǒng)論文的評(píng)估中。

圖3 流失程度

在Facebook的生產(chǎn)工作負(fù)載中體現(xiàn)出有很高程度的流失率。如果一個(gè)對(duì)象屬于收到最多請(qǐng)求的10%的對(duì)象，我們就定義它是受歡迎的。圖3顯示了流行對(duì)象的集合如何隨時(shí)間變化。例如，x=3處的藍(lán)條顯示了一個(gè)3小時(shí)前很受歡迎的對(duì)象仍然在前10%最多請(qǐng)求的對(duì)象中的概率。在所有的工作負(fù)載中，超過三分之二的熱門對(duì)象在一小時(shí)后就跌出了前10%的位置。這種高流失率與使用哪個(gè)小時(shí)作為基線、不同的百分比（例如前25%）以及不同的時(shí)間粒度（例如，10分鐘后，50%的熱門對(duì)象不再受歡迎）無關(guān)。這種高流失率增加了時(shí)間定位的重要性，使緩存策略更難根據(jù)過去的訪問模式來估計(jì)對(duì)象的受歡迎程度。

3. 緩存對(duì)象的粒度變化

除了受歡迎程度和流失率之外，對(duì)象的大小在緩存性能上也起著關(guān)鍵作用。圖4顯示了四個(gè)大型用例的對(duì)象大小分布。對(duì)于Storage和CDN，64KB和128KB的小塊非常常見，這是將大對(duì)象分成小塊的結(jié)果。對(duì)于Lookaside和SocialGraph，對(duì)象的大小跨越了七個(gè)數(shù)量級(jí)。

圖4 緩存對(duì)象粒度分布

4.急促訪問

Facebook的工作負(fù)載流量是相當(dāng)突發(fā)性的。圖5顯示了與泊松到達(dá)序列相比的實(shí)際請(qǐng)求到達(dá)率，這通常是在系統(tǒng)評(píng)估中假設(shè)的。圖5顯示，實(shí)際到達(dá)率的變化比Poisson暗示的要大得多。這對(duì)CDN來說尤其明顯，它在相當(dāng)穩(wěn)定的請(qǐng)求率之上有急劇的流量爆發(fā)。多變的到達(dá)率使得緩存系統(tǒng)很難有足夠的資源來維持負(fù)載高峰期的低延遲。

圖5 請(qǐng)求數(shù)量分布

方法和設(shè)計(jì)

1. 混合式緩存架構(gòu)

相對(duì)來說這些東西需要寫很多相同的緩存邏輯：換出策略，內(nèi)存使用，處理 empty cache 等，所以 Facebook 造了一套通用的 CacheLib，用來節(jié)省團(tuán)隊(duì)造輪子的功夫。同時(shí)，很重要的一點(diǎn)是對(duì)于 Flash 的使用。用 SSD/Flash 當(dāng)緩存，相對(duì)來說能夠提供較低的成本，和可以接受的性能。相對(duì) DRAM，機(jī)器一般會(huì)提供更大的盤，同時(shí)，SSD 也會(huì)提供更低的成本和更可接受的性能。這套功能在 CacheLib 中叫做 HybridCache，CacheLib 允許指定存儲(chǔ)設(shè)備。CacheLib 對(duì)外提供的是 byte-addressable 的對(duì)象和 cache。它提供了一套線程安全的 api，來處理對(duì)應(yīng)的邏輯：

圖6 API

此外，CacheLib 還給自定義的 Serialize/Deserialize 定義了接口，以便用戶塞一些自定義結(jié)構(gòu)體。

2.小對(duì)象緩存優(yōu)化 (Small Object Cache)

SOC存儲(chǔ)很多小對(duì)象，如果像LOC一樣存儲(chǔ)它們的索引，系統(tǒng)整個(gè)DRAM開銷會(huì)非常大。所以SOC使用了一個(gè)近似的索引來實(shí)現(xiàn)對(duì)應(yīng)的邏輯。如圖7所示，SOC 把小對(duì)象劃分成很多 sets，每個(gè)包含一個(gè)4kB page，按照FIFO存儲(chǔ)對(duì)象。每組有一個(gè)8 bytes的Bloom Filter。這里把key查一下Bloom Filter，如果不存在則返回不存在，否則讀取整個(gè)Page并順序掃描。

圖7 小對(duì)象存儲(chǔ)示意圖

3. 大對(duì)象緩存優(yōu)化 (Large Object Cache)

LOC 存儲(chǔ)的都是 2kB 以上的對(duì)象。作者認(rèn)為，這些大對(duì)象讓用戶能夠在內(nèi)存中放置這些對(duì)象的 Index。具體的對(duì)象按照 4kb 的大小對(duì)齊。論文用了 4 bytes 的大小定位這部分的數(shù)據(jù)：4 bytes最大能表示232個(gè)數(shù)據(jù)，可以放 16T的數(shù)據(jù)了。

LOC 的內(nèi)存索引存儲(chǔ)，LOC 會(huì)主動(dòng)把 SSD 劃分成不同的區(qū)域，根據(jù)這個(gè)來判斷大小。然后LOC對(duì)象的地址會(huì)對(duì)齊4kB，這大概是一個(gè)SSD Page的大小，這樣能夠保證一個(gè) SSD Page 不會(huì)存儲(chǔ)過多的對(duì)象；同時(shí)地址對(duì)齊 4kB，減小地址對(duì)象的開銷。如果對(duì)象很大，那么它會(huì)連續(xù)跨多個(gè)頁，需要把他們都讀起來。如果一個(gè)cache read讀取有一個(gè)相同的hash key，這里會(huì)把Flash中的元數(shù)據(jù)讀起來。這里在元數(shù)據(jù)上需要存儲(chǔ)對(duì)應(yīng)的key。然后把這個(gè)key跟用戶請(qǐng)求的真實(shí) key 比較，判斷具體是否命中緩存。

這里還有一個(gè) Erase 相關(guān)的優(yōu)化。LOC 的 Erase 是以 Block 為單位的，它默認(rèn) 16MB，但是是可配置的。這實(shí)際上相當(dāng)于 抹去 SSD 的 Block，通過這種方式來增加寫的順序?qū)?。如果淘汰出的?duì)象是一個(gè)比較熱的對(duì)象，可能會(huì)重新加入 cache 中。

實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)性能對(duì)比包含三個(gè)方面，分別為緩存命中率、吞吐量和暖啟動(dòng)。

緩存命中率和吞吐量性能：圖12顯示了8到144GB的緩存規(guī)模和1億個(gè)對(duì)象的典型工作集的命中率和吞吐量。Memcached和CacheLib實(shí)現(xiàn)了相似的命中率，Memcached在小的緩存大小時(shí)略高，在大的緩存大小時(shí)略低。在所有的緩存大小中，CacheLib實(shí)現(xiàn)了比Memcached更高的吞吐量，每秒鐘處理的請(qǐng)求比Memcached多60%。

圖8 命中率和吞吐量實(shí)驗(yàn)結(jié)果圖

小對(duì)象緩存性能：圖9顯示，CacheLib對(duì)小對(duì)象的明確處理為Flash緩存提供了比NGINX和ATS更大的優(yōu)勢(shì)。當(dāng)對(duì)象的大小變大時(shí)，這種優(yōu)勢(shì)就會(huì)減弱。最終，對(duì)象的大小變得足夠大，以至于這三個(gè)系統(tǒng)都變成了網(wǎng)絡(luò)約束，其吞吐量急劇下降。

圖9 小對(duì)象吞吐量實(shí)驗(yàn)結(jié)果

暖啟動(dòng)：圖10顯示了L1和L2 SocialGraph緩存重啟時(shí)的命中率，而沒有執(zhí)行暖重啟。在沒有啟用這個(gè)功能的情況下，緩存重啟會(huì)導(dǎo)致命中率下降，然后慢慢恢復(fù)正常。這在二級(jí)混合緩存中尤其具有破壞性，因?yàn)榇笕萘康木彺婵赡苄枰獛滋鞎r(shí)間來 "熱身"。這樣的命中率下降可以轉(zhuǎn)化為后端系統(tǒng)的暫時(shí)過載，因?yàn)楹蠖讼到y(tǒng)假定有相對(duì)穩(wěn)定的到達(dá)率。

圖10 暖啟動(dòng)實(shí)驗(yàn)結(jié)果

總結(jié)

Cachelib的出現(xiàn)避免了緩存系統(tǒng)重復(fù)造輪子的現(xiàn)象，降低了系統(tǒng)的冗余程度和開發(fā)維護(hù)成本。同時(shí)cachelib設(shè)計(jì)了混合式緩存架構(gòu)，使用性價(jià)比高的SSD進(jìn)行混合式緩存，使得緩存系統(tǒng)的成本降低同時(shí)提升性能。與傳統(tǒng)的內(nèi)存作為緩存層相比，cachelib考慮到閃存的特性，進(jìn)行了小對(duì)象緩存優(yōu)化，并且在性能上有很大改進(jìn)。

審核編輯：劉清