背景

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

問題

1. 緩存還是分層

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

圖1 緩存類型

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

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

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

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

方法和設(shè)計

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

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

1. 表現(xiàn)與經(jīng)典緩存一樣好或更好。經(jīng)典緩存通過優(yōu)化上級設(shè)備的性能來優(yōu)化存儲層次結(jié)構(gòu)的性能；這種性能是通過找到最大化命中率的工作集來優(yōu)化的。NHC在最壞的情況下應(yīng)該退化為經(jīng)典的緩存，并且應(yīng)該能夠利用任何經(jīng)典的緩存策略（例如，驅(qū)逐和寫分配）。

2. 不需要特殊知識或配置。NHC不應(yīng)該比經(jīng)典緩存做出更多的假設(shè)。NHC不應(yīng)該要求事先了解工作負(fù)載或設(shè)備的詳細(xì)性能特征。NHC應(yīng)該能夠管理任何存儲層次結(jié)構(gòu)。

3. 對動態(tài)工作負(fù)載具有魯棒性。工作負(fù)載隨著時間的推移，在其負(fù)載量和工作集方面發(fā)生變化。NHC應(yīng)該適應(yīng)動態(tài)變化。

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

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

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

圖3 非層級緩存架構(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ù)不變，同時調(diào)整發(fā)送到每個設(shè)備的負(fù)載。

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

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

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

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

實驗結(jié)果

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

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

圖5 吞吐量實驗結(jié)果圖

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

圖6 動態(tài)工作負(fù)載實驗結(jié)果

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

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

總結(jié)

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

審核編輯：劉清