背景

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

問題

1. 緩存還是分層

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

圖1 緩存類型

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

雖然緩存和分層這種優化命中率的傳統智慧對于傳統的層次結構（例如，CPU緩存和DRAM，或DRAM和硬盤）來說可能仍然是正確的，但在現代存儲層次結構中，存儲設備的快速變化使這種敘述變得復雜。具體來說，許多新的非易失性存儲器和低延遲固態硬盤的出現引入了具有（有時）重疊的性能特征的設備。因此，必須重新思考如何在存儲層次中管理這些設備。為了更好地理解這些設備的性能重疊，圖2顯示了各種實際設備在4KB讀/載和寫/存時的吞吐量，同時改變了并發水平。該圖顯示了成對設備之間的性能比。DRAM/NVM繪制了內存（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）；否則，繪出負比（-XY）（在灰色區域）。

圖2 各個設備之間的性能比

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

方法和設計

1. 非分層緩存設計目標

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

1. 表現與經典緩存一樣好或更好。經典緩存通過優化上級設備的性能來優化存儲層次結構的性能；這種性能是通過找到最大化命中率的工作集來優化的。NHC在最壞的情況下應該退化為經典的緩存，并且應該能夠利用任何經典的緩存策略（例如，驅逐和寫分配）。
2. 不需要特殊知識或配置。NHC不應該比經典緩存做出更多的假設。NHC不應該要求事先了解工作負載或設備的詳細性能特征。NHC應該能夠管理任何存儲層次結構。
3. 對動態工作負載具有魯棒性。工作負載隨著時間的推移，在其負載量和工作集方面發生變化。NHC應該適應動態變化。

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

2. 非層級緩存架構

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

圖3 非層級緩存架構圖

3. 緩存調度器算法

NHC調度器調整控制器的行為以優化目標性能指標。如圖4所示，調度器有兩種狀態：增加性能設備上緩存的數據量以最大化命中率，或保持緩存的數據不變，同時調整發送到每個設備的負載。

狀態1：提高命中率。NHC調度器首先讓緩存控制器以其默認的替換策略（da為真，la為1）執行傳統的緩存；在這個過程中，緩存被預熱，隨著工作集在性能設備上的緩存，命中率得到提高。NHC調度器監控性能設備的命中率，并在命中率相對穩定時結束這一階段；此時，性能設備為工作負載提供的性能接近其峰值。

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

由于NHC依靠經典緩存來實現可接受的命中率，所以當工作負載位置發生變化時，它會重新啟動優化過程。NHC調度器在運行時監控緩存命中率；如果當前命中率下降，調度器會重新進入狀態1，用當前工作集重新配置緩存。如果工作負載從未穩定下來，NHC的行為就像傳統的緩存。

圖4 緩存調度器算法執行流程

實驗結果

實驗性能對比包含三個方面，分別為吞吐量、動態適應工作負載和與以前的工作對比。

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

圖5 吞吐量實驗結果圖

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

圖6 動態工作負載實驗結果

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

圖7 現有工作對比

總結

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