背景

現(xiàn)有的計(jì)算機(jī)體系架構(gòu)中通常采用層級(jí)緩存來(lái)彌補(bǔ)外存和內(nèi)存之間的性能差距。但是，層緩存都有極限帶寬和有限的命中率，在層級(jí)緩存下數(shù)據(jù)需要頻繁的在各個(gè)層級(jí)緩存之前遷移，造成過(guò)高的數(shù)據(jù)拷貝開(kāi)銷。同時(shí)，隨著高性能的外部存儲(chǔ)設(shè)備的出現(xiàn)，外存的帶寬并沒(méi)有被充分的利用。這篇文章介紹了非分級(jí)緩存（NHC），這是一種在現(xiàn)代存儲(chǔ)層次中進(jìn)行緩存的新方法。與傳統(tǒng)的緩存相比，NHC通過(guò)在有利的情況下將多余的負(fù)載重定向到層次結(jié)構(gòu)中較低的設(shè)備來(lái)提高性能。NHC動(dòng)態(tài)調(diào)整分配和訪問(wèn)決策，從而使性能最大化（例如，高吞吐量、低99%的延遲）。這篇文章在Orthus-CAS（一個(gè)塊層緩存內(nèi)核模塊）和Orthus-KV（一個(gè)鍵值存儲(chǔ)的用戶級(jí)緩存層）中實(shí)現(xiàn)了NHC。通過(guò)全面的實(shí)證研究表明了NHC的有效性。Orthus-KV和Orthus-CAS在一系列現(xiàn)實(shí)的工作負(fù)載下，比各種現(xiàn)代層次的傳統(tǒng)緩存提供了明顯更好的性能（最高可達(dá)2倍）。

問(wèn)題

1. 緩存還是分層

為了應(yīng)對(duì)層次結(jié)構(gòu)的性質(zhì)，系統(tǒng)通常采用兩種策略：緩存和分層，如圖1所示?？紤]一個(gè)有兩個(gè)存儲(chǔ)層的系統(tǒng)：一個(gè)（快、貴、小）性能層和一個(gè)（慢、便宜、大）容量層。通過(guò)緩存，所有的數(shù)據(jù)都駐留在容量層，而熱數(shù)據(jù)的副本通過(guò)緩存替換算法被放置在性能層。分層也是將熱門數(shù)據(jù)放在性能層；然而，與緩存不同的是，它在更長(zhǎng)的時(shí)間范圍內(nèi)遷移數(shù)據(jù)（而不是復(fù)制）。如果有足夠多的請(qǐng)求進(jìn)入快速層，整體性能就會(huì)接近快速層的峰值性能。因此，傳統(tǒng)的緩存和分層努力確保大多數(shù)的訪問(wèn)都能到達(dá)性能層。傳統(tǒng)的緩存和分層都是為了最大限度地提高性能，努力確保大多數(shù)訪問(wèn)是由性能良好的設(shè)備提供的。因此，大多數(shù)緩存和分層策略都是為了最大限度地提高快速設(shè)備的點(diǎn)擊率。在傳統(tǒng)的層次結(jié)構(gòu)中，高層的性能明顯高于底層，這種方法提供了高性能。然而，隨著存儲(chǔ)環(huán)境的快速變化，現(xiàn)代設(shè)備的性能特征也在不斷重疊，因此，必須重新思考如何管理這些設(shè)備。

圖1 緩存類型

2. 緩存之間存在性能特征重疊

雖然緩存和分層這種優(yōu)化命中率的傳統(tǒng)智慧對(duì)于傳統(tǒng)的層次結(jié)構(gòu)（例如，CPU緩存和DRAM，或DRAM和硬盤）來(lái)說(shuō)可能仍然是正確的，但在現(xiàn)代存儲(chǔ)層次結(jié)構(gòu)中，存儲(chǔ)設(shè)備的快速變化使這種敘述變得復(fù)雜。具體來(lái)說(shuō)，許多新的非易失性存儲(chǔ)器和低延遲固態(tài)硬盤的出現(xiàn)引入了具有（有時(shí)）重疊的性能特征的設(shè)備。因此，必須重新思考如何在存儲(chǔ)層次中管理這些設(shè)備。為了更好地理解這些設(shè)備的性能重疊，圖2顯示了各種實(shí)際設(shè)備在4KB讀/載和寫/存時(shí)的吞吐量，同時(shí)改變了并發(fā)水平。該圖顯示了成對(duì)設(shè)備之間的性能比。DRAM/NVM繪制了內(nèi)存（SK Hynix 16GB DDR4）與單個(gè)英特爾Optane DCPM（128GB）的帶寬；NVM/Optane使用DCPM與英特爾905P Optane SSD；最后，Optane/Flash使用相同的Optane SSD和三星970 Pro Flash SSD。對(duì)于任何一對(duì)X/Y，如果X的性能大于Y，則繪出正比（YX）；否則，繪出負(fù)比（-XY）（在灰色區(qū)域）。

圖2 各個(gè)設(shè)備之間的性能比

總結(jié)一下，以下是存儲(chǔ)時(shí)代層次結(jié)構(gòu)的主要趨勢(shì)。與傳統(tǒng)的層次結(jié)構(gòu)（如DRAM與HDD）不同，新的存儲(chǔ)層次結(jié)構(gòu)可能不是一個(gè)層次；兩個(gè)相鄰的層次（如NVM與Optane SSD）的性能可能相似。其次，新設(shè)備的性能取決于許多因素，包括不同的工作負(fù)載（讀與寫）和并發(fā)水平。用傳統(tǒng)的緩存和分層來(lái)管理這些設(shè)備已不再有效。

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

1. 非分層緩存設(shè)計(jì)目標(biāo)

這篇文章提出了非分級(jí)緩存（NHC），這是一個(gè)緩存框架，它利用了設(shè)備的性能，而這些設(shè)備在傳統(tǒng)的緩存中只被視為一個(gè)容量層。NHC有以下目標(biāo)：

1. 表現(xiàn)與經(jīng)典緩存一樣好或更好。經(jīng)典緩存通過(guò)優(yōu)化上級(jí)設(shè)備的性能來(lái)優(yōu)化存儲(chǔ)層次結(jié)構(gòu)的性能；這種性能是通過(guò)找到最大化命中率的工作集來(lái)優(yōu)化的。NHC在最壞的情況下應(yīng)該退化為經(jīng)典的緩存，并且應(yīng)該能夠利用任何經(jīng)典的緩存策略（例如，驅(qū)逐和寫分配）。
2. 不需要特殊知識(shí)或配置。NHC不應(yīng)該比經(jīng)典緩存做出更多的假設(shè)。NHC不應(yīng)該要求事先了解工作負(fù)載或設(shè)備的詳細(xì)性能特征。NHC應(yīng)該能夠管理任何存儲(chǔ)層次結(jié)構(gòu)。
3. 對(duì)動(dòng)態(tài)工作負(fù)載具有魯棒性。工作負(fù)載隨著時(shí)間的推移，在其負(fù)載量和工作集方面發(fā)生變化。NHC應(yīng)該適應(yīng)動(dòng)態(tài)變化。

NHC的主要思想（圖1）是將多余的負(fù)載轉(zhuǎn)移到容量大的設(shè)備上，當(dāng)這樣做可以提高整體的緩存性能。NHC可以用三個(gè)步驟來(lái)描述。首先，在系統(tǒng)預(yù)熱時(shí)（或在工作負(fù)載發(fā)生重大變化后），NHC利用經(jīng)典緩存來(lái)識(shí)別當(dāng)前的工作集并將數(shù)據(jù)加載到高性能設(shè)備中；這確保NHC的性能至少與經(jīng)典緩存一樣好。第二，在命中率穩(wěn)定后，NHC通過(guò)向容量設(shè)備發(fā)送多余的負(fù)載來(lái)改進(jìn)傳統(tǒng)緩存。這種多余的負(fù)載有兩部分組成：一是由于高性能設(shè)備已經(jīng)達(dá)到最大性能，所以在高性能設(shè)備上沒(méi)有提供額外的性能；二是導(dǎo)致兩個(gè)設(shè)備之間不必要的數(shù)據(jù)移動(dòng)的讀取失誤。傳統(tǒng)的緩存在漏讀發(fā)生時(shí)將數(shù)據(jù)從容量設(shè)備轉(zhuǎn)移到性能設(shè)備，以提高命中率。然而，當(dāng)性能設(shè)備已經(jīng)達(dá)到最大性能時(shí)，提高命中率是沒(méi)有好處的。因此，NHC減少了進(jìn)入性能設(shè)備的數(shù)據(jù)量。使用基于反饋的方法，NHC確定了過(guò)剩的負(fù)載；它不需要對(duì)設(shè)備或工作負(fù)載有任何了解。最后，如果觀察到工作負(fù)載的變化，NHC會(huì)返回到經(jīng)典緩存；如果工作負(fù)載從未穩(wěn)定下來(lái)，該算法就會(huì)退化為經(jīng)典緩存。NHC可以利用與傳統(tǒng)緩存相同的寫分配策略（例如，繞寫或回寫）。

2. 非層級(jí)緩存架構(gòu)

如圖3所示，經(jīng)典緩存可以通過(guò)在其緩存控制器和非分級(jí)緩存調(diào)度器上增加決策點(diǎn)來(lái)升級(jí)為NHC。傳統(tǒng)的緩存控制器為用戶/應(yīng)用程序向存儲(chǔ)設(shè)備的讀寫提供服務(wù)，并根據(jù)其替換策略（例如LRU）控制性能設(shè)備的內(nèi)容。本文提出一個(gè)新的緩存調(diào)度器監(jiān)控性能，并控制是否執(zhí)行經(jīng)典緩存，以及在哪里提供緩存讀取命中。調(diào)度器優(yōu)化目標(biāo)性能指標(biāo)，該指標(biāo)可以由用戶提供（例如，IOPS/s）或使用設(shè)備級(jí)指標(biāo)（例如，請(qǐng)求延遲）。NHC調(diào)度器通過(guò)一個(gè)布爾值data_admit（da）和一個(gè)變量load_admit（la）進(jìn)行控制。當(dāng)性能設(shè)備上發(fā)生讀取缺失時(shí)，da標(biāo)志控制行為：當(dāng)da被設(shè)置時(shí)，根據(jù)緩存替換策略，將缺失的數(shù)據(jù)項(xiàng)分配到性能設(shè)備中；當(dāng)da未被設(shè)置時(shí)，缺失由容量設(shè)備處理，不分配到性能設(shè)備中。經(jīng)典緩存對(duì)應(yīng)的情況是，da標(biāo)志為真。la變量控制如何處理讀取命中，并指定了應(yīng)該發(fā)送到性能設(shè)備的讀取命中的百分比；當(dāng)la為0時(shí)，所有的讀取命中都被發(fā)送到容量設(shè)備。具體來(lái)說(shuō)，對(duì)于每個(gè)讀取命中，會(huì)產(chǎn)生一個(gè)隨機(jī)數(shù)R∈[0,1.0]；如果R<=la，請(qǐng)求被發(fā)送到性能設(shè)備中；否則，被發(fā)送到容量設(shè)備中。在經(jīng)典緩存中，la總是1。NHC框架與任何傳統(tǒng)的緩存寫分配策略（由用戶指定）一起工作，處理寫命中/缺失。NHC根據(jù)政策將寫缺失納入性能設(shè)備；da、la不控制寫命中/缺失。在回寫的情況下，緩存寫入會(huì)在性能設(shè)備中引入臟數(shù)據(jù)，而存儲(chǔ)設(shè)備上的數(shù)據(jù)可能是過(guò)時(shí)的；在這種情況下，NHC不會(huì)向存儲(chǔ)設(shè)備發(fā)送臟讀。

圖3 非層級(jí)緩存架構(gòu)圖

3. 緩存調(diào)度器算法

NHC調(diào)度器調(diào)整控制器的行為以優(yōu)化目標(biāo)性能指標(biāo)。如圖4所示，調(diào)度器有兩種狀態(tài)：增加性能設(shè)備上緩存的數(shù)據(jù)量以最大化命中率，或保持緩存的數(shù)據(jù)不變，同時(shí)調(diào)整發(fā)送到每個(gè)設(shè)備的負(fù)載。

狀態(tài)1：提高命中率。NHC調(diào)度器首先讓緩存控制器以其默認(rèn)的替換策略（da為真，la為1）執(zhí)行傳統(tǒng)的緩存；在這個(gè)過(guò)程中，緩存被預(yù)熱，隨著工作集在性能設(shè)備上的緩存，命中率得到提高。NHC調(diào)度器監(jiān)控性能設(shè)備的命中率，并在命中率相對(duì)穩(wěn)定時(shí)結(jié)束這一階段；此時(shí)，性能設(shè)備為工作負(fù)載提供的性能接近其峰值。

狀態(tài)2：調(diào)整設(shè)備間的負(fù)載。在性能設(shè)備包含了高命中率和性能的工作集后，NHC調(diào)度器探測(cè)是否向存儲(chǔ)設(shè)備發(fā)送一些請(qǐng)求會(huì)增加存儲(chǔ)設(shè)備的性能，同時(shí)不會(huì)降低性能設(shè)備的性能。在這種狀態(tài)下，da被設(shè)置為false，反饋被用來(lái)調(diào)整la以最大化目標(biāo)性能指標(biāo)。具體來(lái)說(shuō)，調(diào)度器（第6-18行）修改la；在每個(gè)迭代中，用la +/-步在一個(gè)時(shí)間間隔（例如，5ms）內(nèi)測(cè)量性能。la的值在三個(gè)數(shù)據(jù)點(diǎn)所指示的方向上進(jìn)行調(diào)整。當(dāng)la的當(dāng)前值導(dǎo)致最佳性能時(shí)，調(diào)度器堅(jiān)持使用當(dāng)前值。la的值被保持在可接受的[0, 1.0]范圍內(nèi)，有一個(gè)負(fù)的懲罰函數(shù)。如果調(diào)度器發(fā)現(xiàn)最佳的la是1，它就會(huì)放棄調(diào)度，回到狀態(tài)1；直觀地說(shuō)，這意味著NHC已經(jīng)將當(dāng)前的工作負(fù)載的訪問(wèn)壓力并沒(méi)有達(dá)到性能設(shè)備的極限，因此需要經(jīng)典緩存來(lái)提高命中率，以進(jìn)一步提高性能。

由于NHC依靠經(jīng)典緩存來(lái)實(shí)現(xiàn)可接受的命中率，所以當(dāng)工作負(fù)載位置發(fā)生變化時(shí)，它會(huì)重新啟動(dòng)優(yōu)化過(guò)程。NHC調(diào)度器在運(yùn)行時(shí)監(jiān)控緩存命中率；如果當(dāng)前命中率下降，調(diào)度器會(huì)重新進(jìn)入狀態(tài)1，用當(dāng)前工作集重新配置緩存。如果工作負(fù)載從未穩(wěn)定下來(lái)，NHC的行為就像傳統(tǒng)的緩存。

圖4 緩存調(diào)度器算法執(zhí)行流程

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

實(shí)驗(yàn)性能對(duì)比包含三個(gè)方面，分別為吞吐量、動(dòng)態(tài)適應(yīng)工作負(fù)載和與以前的工作對(duì)比。

吞吐量性能 ：圖5中展示了Open CAS和Orthus-CAS在不同層次、負(fù)載量和命中率的只讀工作負(fù)載下的標(biāo)準(zhǔn)化吞吐量。Load-1.0定義為最小的讀取負(fù)載，以實(shí)現(xiàn)緩存設(shè)備的最大讀取帶寬；通過(guò)擴(kuò)展Load-1.0產(chǎn)生Load-0.5、1.5和2.0。研究的層次包括DRAM、NVM、Optane SSD和Flash。還使用FlashSim模擬了具有兩種性能差異（50:10和50:25）的層次結(jié)構(gòu)；我們對(duì)FlashSim進(jìn)行了配置，以模擬最高速度為50MB/s、25MB/s和10MB/s的設(shè)備。我們從圖中觀察到以下幾點(diǎn)。首先，當(dāng)負(fù)載較輕時(shí)（例如，負(fù)載-0.5），緩存設(shè)備的性能總是優(yōu)于容量設(shè)備。在這種情況下，NHC不會(huì)繞過(guò)任何負(fù)載，其表現(xiàn)與經(jīng)典緩存相同。第二，當(dāng)工作負(fù)載可以充分利用緩存設(shè)備時(shí)，Orthus-CAS會(huì)提高性能。直觀地說(shuō)，較高的命中率和負(fù)載使NHC有更多機(jī)會(huì)繞過(guò)請(qǐng)求，提高性能。圖5證明了這一直覺(jué)：在95%的命中率和Load-2.0的情況下，NHC在DRAM+NVM、NVM+Optane和Optane+Flash方面分別獲得了21%、32%、54%的改善。在80%的命中率下，這種改進(jìn)會(huì)略有減少。

圖5 吞吐量實(shí)驗(yàn)結(jié)果圖

動(dòng)態(tài)工作負(fù)載性能 ：如圖6(a)所示，Orthus-KV在白天的表現(xiàn)好，最高可達(dá)100%，但在夜間負(fù)荷較低時(shí)表現(xiàn)相似。圖6(a)顯示了Orthus-KV如何調(diào)整數(shù)據(jù)和負(fù)載的承認(rèn)率。在夜間，兩者都在100%左右；當(dāng)命中率穩(wěn)定時(shí)，Orthus-KV偶爾會(huì)調(diào)整負(fù)載接納率，但在發(fā)現(xiàn)沒(méi)有改善后，很快就回到了傳統(tǒng)的緩存。在白天，Orthus-KV將數(shù)據(jù)接受率保持在0，并調(diào)整負(fù)載接受率以適應(yīng)動(dòng)態(tài)負(fù)載。圖12(b)中證明NHC對(duì)工作集的突然變化反應(yīng)良好。實(shí)驗(yàn)以YCSB-C為基礎(chǔ)，從一個(gè)工作集開(kāi)始，然后在時(shí)間10s時(shí)改變。圖中顯示，當(dāng)工作集發(fā)生變化時(shí)（時(shí)間=10s），Orthus-KV迅速檢測(cè)到命中率的變化，并切換到經(jīng)典緩存：負(fù)載和數(shù)據(jù)接納比率增加到1.0。在命中率開(kāi)始穩(wěn)定后（時(shí)間=11s），Orthus-KV調(diào)整了負(fù)載接受率。最初（11s-28s），由于命中率還不夠高，Orthus-KV經(jīng)常將1.0確定為最佳的負(fù)載接納，并返回到傳統(tǒng)的數(shù)據(jù)移動(dòng)的緩存中。在工作負(fù)載變化后約20秒，命中率穩(wěn)定下來(lái)，Orthus-KV達(dá)到了穩(wěn)定的性能，比經(jīng)典緩存高出60%。圖12(c)顯示了Orthus-KV在YCSB-D上的表現(xiàn)（95%讀取，5%插入），在這里，由于對(duì)最近插入的值進(jìn)行讀取，位置性會(huì)隨著時(shí)間而改變。由于位置性的變化和不接納新數(shù)據(jù)到緩存中，Orthus-KV的命中率隨著時(shí)間的推移而下降，直到NHC確定1.0是最佳的負(fù)載接納率。然后Orthus-KV返回到傳統(tǒng)的緩存，并提高命中率。一旦命中率恢復(fù)穩(wěn)定，Orthus-KV就會(huì)恢復(fù)循環(huán)，調(diào)整負(fù)載接納率。

圖6 動(dòng)態(tài)工作負(fù)載實(shí)驗(yàn)結(jié)果

現(xiàn)有工作對(duì)比：SIB的目標(biāo)是具有許多SSD和HDD的HDFS集群，在這種情況下，HDD的總吞吐量是非同小可的：SIB將SSD作為一個(gè)寫緩沖區(qū)（不提升任何讀缺失），并建議使用HDD來(lái)處理額外的讀流量。LBICA確定性能層何時(shí)處于 "突發(fā)負(fù)載 "狀態(tài)，此時(shí)它不會(huì)向性能層分配新的數(shù)據(jù)；與NHC不同，LBICA不會(huì)重定向任何讀取命中。如圖7(a)所示，SIB+表現(xiàn)不佳，因?yàn)樗惶嵘齇ptane中的讀缺失。SIB++表現(xiàn)較好，但當(dāng)工作負(fù)載發(fā)生變化時(shí)，如圖7(b)所示，就會(huì)受到影響；在這些工作負(fù)載中，寫流量每隔一段時(shí)間就會(huì)發(fā)生變化，時(shí)間在10到0.5秒之間。

圖7 現(xiàn)有工作對(duì)比

總結(jié)

這篇文章引入了非分級(jí)緩存，這是一種優(yōu)化的方法，可以從設(shè)備中提取峰值性能。NHC是基于一種新的緩存調(diào)度算法，該算法考慮了工作負(fù)載和設(shè)備特性，以做出分配和訪問(wèn)決定。通過(guò)實(shí)驗(yàn)，我們展示了NHC在各種設(shè)備、高速緩存配置和工作負(fù)載上的優(yōu)勢(shì)。同時(shí)，NHC通過(guò)將部分負(fù)載卸載到容量設(shè)備上，動(dòng)態(tài)調(diào)整卸載工作量，利用容量設(shè)備的帶寬，在性能上有很大改進(jìn)。