摘要：
????????隨著每比特價格的下降，SSD越來越成為云應(yīng)用數(shù)據(jù)庫中熱數(shù)據(jù)的默認(rèn)存儲介質(zhì)。盡管SSD的每位價格低于10倍，并且與DRAM相比，它提供了足夠的性能（當(dāng)通過網(wǎng)絡(luò)訪問時），但閃存的耐用性限制了其在大量使用情況下的應(yīng)用，例如鍵值緩存。這是因為鍵值緩存需要經(jīng)常插入，更新和逐出小對象。這會導(dǎo)致閃存存儲器的寫入和擦除過多，從而大大縮短閃存的使用壽命。我們介紹Flashield，一種混合??鍵值緩存，它使用DRAM作為“過濾器”來控制和限制對SSD的寫入。Flashield執(zhí)行輕量級機器學(xué)習(xí)準(zhǔn)入控制，以預(yù)測哪些對象可能經(jīng)常被讀取而無需更新;?這些對象，哪些是存儲在SSD上的主要候選者，順序地以大塊寫入SSD。我們描述了Flashield的設(shè)計和實現(xiàn)，并使用廣泛使用的緩存服務(wù)Memcachier對實際痕跡進行評估。我們?yōu)榇鎯υ陂W存中的可變大小的對象設(shè)計了一種新穎的內(nèi)存索引，在DRAM中每個對象只需要4個字節(jié)。與具有2.5倍或更高寫入放大率的最先進系統(tǒng)相比，F(xiàn)lashield保持0.5倍的中值寫入放大率（因為許多濾波對象根本不會寫入閃存），而沒有任何命中率損失或吞吐量。
背景：
????????與DRAM相比，F(xiàn)lash的每比特成本要低一個數(shù)量級。因此，對于需要高吞吐量和低延遲的熱數(shù)據(jù)，它已經(jīng)成為首選的存儲介質(zhì)。例如，谷歌[36]和Face-book[30]使用它存儲照片，而像Lev-elDB[5]和RocksDB[9]這樣的數(shù)據(jù)庫部署在flash之上。
? ??????????鍵值緩存是現(xiàn)代web規(guī)模應(yīng)用程序中的一個重要層，幾乎被所有web服務(wù)(包括Facebook、Twitter和Airbnb)廣泛使用。大型web服務(wù)提供者運行自己的鍵值緩存集群，而較小的提供者通常使用緩存即服務(wù)的功能，如Amazon ElastiCache[1]和Memcachier[7]。
? ??????然而，由于它在寫操作下的持久性有限，flash通常不用于像memcached[6]和Redis[8]這樣的鍵值緩存。這就更加令人困惑了，因為這些緩存通常部署在一個專用的remote集群[31]或遠(yuǎn)程數(shù)據(jù)中心[1,7]中，或者使用客戶端批處理[31]。因此，客戶端觀察到的訪問時間可以是數(shù)百微秒到毫秒，因此與使用DRAM相比，flash只會增加一小部分延遲。
? ??????此外，由于緩存的性能主要是由它們提供的內(nèi)存容量決定的[13,14]，而且SSD的每比特成本比DRAM低10多美元，與DRAM相比，flash有望帶來顯著的經(jīng)濟效益。表1顯示，只有DRAM緩存和混合緩存(都具有4.25 TB的容量)之間的成本差異大于10。由于電力成本的原因，總擁有成本(TCO)的差異將會更大，因為flash消耗的電力比DRAM要少得多，而且可以在請求更少時關(guān)閉，而不需要重新預(yù)熱緩存。
??????????flash沒有被廣泛用作鍵值緩存的原因是緩存工作負(fù)載會很快耗盡閃存驅(qū)動器。這些工作負(fù)載通常由小對象組成，其中一些對象需要經(jīng)常更新[10,31]。但是，ssd內(nèi)的現(xiàn)代閃存芯片在其生命周期中只能在每個位置寫入幾千次。
? ??????????此外，ssd還受到寫放大(WA)的影響。也就是說，對于應(yīng)用程序所寫的每個字節(jié)(例如鍵值緩存)，在設(shè)備級別上還要向flash寫入幾個字節(jié)。WA的發(fā)生是因為flash頁面被物理地分組在大塊中。在覆蓋頁面之前，必須先刪除它們，但這只能在塊的粒度中完成。結(jié)果是，隨著時間的推移，這些大塊通常包含有效頁面和無效頁面的混合。在刪除一個塊之前，必須將任何有效的頁面復(fù)制到其他flash塊。這個垃圾收集過程創(chuàng)建了設(shè)備級寫放大(DLWA)，它可以將寫入flash的數(shù)據(jù)量增加幾個數(shù)量級。現(xiàn)代ssd通過將許多flash塊分割在一起(512 MB或更多)來提高順序?qū)懶阅?x2.1，[38])，從而加劇了這種情況。
? ??????為了最小化閃存寫入的數(shù)量，SSD存儲系統(tǒng)被限制為以大的連續(xù)塊寫入數(shù)據(jù)。這就強制了一種二階寫放大，這是緩存特有的，我們稱之為緩存級寫放大(CLWA)。當(dāng)緩存被迫重新定位對象以避免DLWA時，就會發(fā)生CLWA。例如，當(dāng)一個熱對象占用了與許多準(zhǔn)備清除的項相同的flash塊時，緩存將面臨一個選擇。它可以用冷對象驅(qū)逐熱對象，也可以將熱對象重寫為新的大型寫入的一部分。因此，在現(xiàn)有的SSD緩存設(shè)計中，對象被多次重寫到flash中。
? ??????為了解決這個問題，最新的RIPQ[38]系統(tǒng)建議，在flash中，通過將熱對象和冷對象插入到不同的物理區(qū)域來存儲它們。然而，flash上有效的數(shù)據(jù)放置并不足以對抗高CLWA，事實上，在某些情況下可能會進一步增加CLWA。例如，考慮一個應(yīng)用程序，其中大量對象不常被訪問(或頻繁更新)。因為RIPQ將所有對象(熱對象和冷對象)都包含在flash中，所以不經(jīng)常訪問的對象將被插入到“冷”插入點中，并且在再次訪問之前，類型很容易被刪除。因此，可以多次插入和刪除這些對象。我們展示了在這樣的工作負(fù)載下，RIPQ的CLWA高達(dá)150 (x5)，這意味著對于許多應(yīng)用程序來說，它將很快耗盡flash設(shè)備。
? ??????隨著時間的推移，閃速可靠性問題將變得更加嚴(yán)重，因為隨著閃速密度的增加，其耐久性將繼續(xù)降低[20]。特別是，下一代flash技術(shù)(QLC)可以比現(xiàn)有技術(shù)(TLC)少忍受30次寫入[3,29,32]。
? ??????我們提出了一種新的混合鍵值緩存Flashield，它同時使用DRAM和ssd。我們的貢獻(xiàn)是一種新的緩存策略，它顯著延長了ssd的生命周期，通過控制和最小化對flash的寫操作數(shù)量，它可以與DRAM相媲美。我們的主要觀察是，并非所有進入緩存的對象都適合放置在SSD中。特別是，緩存應(yīng)該避免將對象寫入flash，這些對象將在不久的將來被更新或不會被讀取。然而，當(dāng)對象第一次進入緩存時，它不知道哪些對象適合SSD，哪些不適合。
? ??????因此，F(xiàn)lashield設(shè)計的一個關(guān)鍵思想是，插入到緩存中的對象總是要在DRAM中花費一段時間，在此期間，緩存知道它們是否適合閃存。如果他們真的證明自己是值得閃光的，F(xiàn)lashield會把他們變成閃光。如果沒有，它們將永遠(yuǎn)不會移動到flash中，這將減少結(jié)果寫入放大。由于flash層比DRAM大得多(例如，比DRAM大10個)，移動到flash中的對象在緩存中的平均停留時間要比那些留在DRAM中的對象長得多。
? ??????為了動態(tài)地確定哪些對象是適合在變化工作負(fù)載下使用flash的對象，我們使用基于機器學(xué)習(xí)的支持向量機(SVM)分類實現(xiàn)了允許控制算法。我們?yōu)榫彺嬷械拿總€應(yīng)用程序訓(xùn)練一個不同的分類器。為了訓(xùn)練分類器，我們設(shè)計了一種輕量級的采樣技術(shù)，它可以隨著時間的推移對對象進行一致采樣，收集關(guān)于過去讀取和更新次數(shù)的統(tǒng)計信息。分類器預(yù)測一個對象在未來是否會被讀取n次以上而不被更新，用來確定它是否適合存儲在flash上。我們稱這種度量為閃光。
? ??????Flashield設(shè)計的第二個主要思想是，它為存儲在flash上的可變長度對象提供了新穎的基于戲劇的查找索引，每個對象只需要不到4字節(jié)的DRAM。這比RIPQ小5個多，后者每個對象包含22個字節(jié)。由于flash層比DRAM的容量要大得多,一個na¨?ve查找索引的對象存儲在閃存將消耗整個DRAM的能力。由于沒有存儲對象的位置及其對應(yīng)的鍵，我們的索引消耗的內(nèi)存相對較少。相反,為每一個對象存儲在閃存上,該指數(shù)包含一個指針指向一個地區(qū)的flash對象存儲,它存儲一個額外的4位指定對象上的一個哈希函數(shù)關(guān)鍵指示對象的插入點在其地區(qū)閃光。索引利用bloom過濾器來指示對象是否駐留在flash上，而不需要在DRAM中存儲完整的鍵。平均而言，F(xiàn)lashield的查找索引只需要從SSD讀取1.03個數(shù)據(jù)就可以返回存儲在其中的對象。
? ??????我們在C語言中實現(xiàn)Flashield，并在一組使用memcachier[7](一種流行的基于云的緩存服務(wù))的實際應(yīng)用程序上評估它的性能。我們表明，與RIPQ[38]相比，F(xiàn)lashield在保持相同的平均命中率的同時，將寫入放大中值降低了5，平均降低了16，索引大小降低了5以上。我們表明，當(dāng)對象從SSD讀取時，F(xiàn)lashield的讀取延遲和吞吐量接近SSD的延遲和吞吐量，當(dāng)對象寫到緩存或從DRAM讀取時，它的延遲和吞吐量類似于基于戲劇的緩存，比如Memcached。
? ??????本文的主要貢獻(xiàn)有三:
1. Flashield是第一個明確使用DRAM作為允許控制過濾器來決定將哪些對象插入flash的SSD存儲系統(tǒng)。
2. Flashield的新穎閃存內(nèi)存查找索引在DRAM中每個對象占用不到4個字節(jié)，同時又不犧牲閃存的寫入和讀取功能。
3.Flashield是第一個使用基于機器學(xué)習(xí)的承認(rèn)控制算法和輕量級時間采樣來預(yù)測哪些對象將是flash的良好候選對象的鍵值緩存。
由于新一代flash技術(shù)可以容忍更少的寫操作[3,20,29,32]，我們對flash的動態(tài)允許控制可以擴展到緩存之外的其他系統(tǒng)，比如flash數(shù)據(jù)庫和文件系統(tǒng)。
問題：
????????設(shè)計基于ssd的高速緩存需要解決兩個控制問題。ssd的性能很差，并且很快就會耗盡，除非寫操作很大而且是連續(xù)的。這與緩存工作負(fù)載的特性有關(guān)。緩存存儲具有高度可變生存期的小對象;這使得緩存更傾向于使用小的隨機I/O進行寫操作，這將很快耗盡閃存驅(qū)動器。
????????SSD的生命周期由閃存設(shè)備制造商定義為，在設(shè)備產(chǎn)生不可糾正的讀取錯誤(例如，遇到損壞位的概率為10 - 15)之前的時間量。SSD的生命周期取決于幾個因素，包括寫和擦除的數(shù)量(稱為程序擦除周期)、SSD單元刷新周期之間的平均時間、單元技術(shù)、錯誤糾正代碼等等。閃存電池的典型壽命是3-5年，平均每天寫3-5次。
????????器件磨損的關(guān)鍵指標(biāo)是寫入放大。許多寫模式迫使SSD對flash執(zhí)行額外的寫操作，以便重新組織數(shù)據(jù)。寫入放大是指寫入閃存芯片的字節(jié)數(shù)與應(yīng)用程序發(fā)送到SSD的字節(jié)數(shù)之比。寫入放大為1表示應(yīng)用程序?qū)懭氲拿總€字節(jié)導(dǎo)致一個字節(jié)寫入到flash。寫入放大10表示應(yīng)用程序?qū)懭氲拿總€字節(jié)會導(dǎo)致額外的9字節(jié)數(shù)據(jù)被重新組織并寫入flash。
設(shè)備級的寫放大：
?????????設(shè)備級寫放大(DLWA)是由SSD內(nèi)部重組引起的寫放大。DLWA的主要來源是flash重用單元的大小。Flash是讀和寫在小(?8 KB)頁面。然而，如果不先擦除，就不能重寫頁面。擦除發(fā)生在幾頁稱為組塊的粒度(?256 KB)。當(dāng)設(shè)備處于高利用率時，頁面大小(或?qū)ο蟠笮?與擦除單元大小之間的不匹配會導(dǎo)致寫入放大。
????????例如，當(dāng)應(yīng)用程序覆蓋頁面的內(nèi)容時，SSD將其寫入一個不同的新塊，并維護一個名為Flash Translation Layer (FTL)的重新定位映射。原始塊還不能被刪除，因為同一塊中的其他頁可能仍然是活動的。當(dāng)閃存芯片完全被占用時，SSD必須刪除塊，以便為新寫的頁面騰出空間。如果沒有一個塊中所有的頁面都被最近編寫的數(shù)據(jù)所遍歷，那么來自多個塊的活動頁面必須合并到一個flash塊中。
????????這種整合或垃圾收集是DLWA的來源。如果一個設(shè)備的占用率達(dá)到90%，它的DLWA可能會非常高。圖1顯示了順序?qū)懭牒蛂andom寫入下的DLWA。測量是在一臺480 GB的英特爾535系列SSD上進行的，使用的是一種用于監(jiān)控設(shè)備內(nèi)部結(jié)構(gòu)的智能系統(tǒng)。對于每個數(shù)據(jù)點，隨機生成的4tb數(shù)據(jù)被隨機或順序地寫入具有不同緩沖區(qū)大小的設(shè)備的原始邏輯塊地址。具體來說，在隨機工作負(fù)載中，邏輯塊空間被劃分為相鄰的固定緩沖區(qū)大小的區(qū)域;每次寫操作都會隨機地用隨機數(shù)據(jù)的完整緩沖區(qū)覆蓋其中一個區(qū)域。順序工作負(fù)載是循環(huán)的;區(qū)域在其邏輯塊地址的順序中被覆蓋，根據(jù)需要循環(huán)回到設(shè)備的開始。對于這兩種模式，我們通過將寫限制在邏輯塊地址的較小部分來改變設(shè)備空間的利用率。
? ??????結(jié)果表明，隨機排列的1mb閃存寫入體驗接近8個DLWA。這是令人驚訝的，因為閃存擦除塊小于1 MB。這種寫放大的原因是因為ssd越來越優(yōu)化高寫帶寬。SSD內(nèi)的每個閃存包都是通過一個相對較慢的鏈接訪問的(目前為50- 90mb /s);ssd在多個flash包中并行條帶大順序?qū)?，以獲得高的寫帶寬。這有效地將多個包中的擦除塊融合到一個邏輯擦除塊中。一個1mb的隨機寫標(biāo)記了一個大區(qū)域的頁面已經(jīng)準(zhǔn)備好被擦除，但是這個區(qū)域是跨幾個仍然包含大部分活動頁面的擦除單元分段的。其他人也證實了這一效應(yīng)。
????????有兩種方法可以對抗這種影響。第一個是用bw的單位寫其中B是擦除塊的大小w是SSD條帶寫過的塊數(shù)。我們的結(jié)果表明，為了消除DLWA，緩存必須以512 MB的塊寫入。第二種方法是按順序編寫設(shè)備，始終按fifo順序編寫。這是可行的，因為每個寫的bw產(chǎn)生一個完全空的bw單元，即使寫的單元小于bw。圖1顯示了8mb的順序?qū)懭胍蚕薉LWA。
????????這意味著我們的緩存在如何向flash寫入數(shù)據(jù)方面受到了極大的限制。為了最小化DLWA，緩存必須以大塊或順序?qū)懭雽ο?。在這兩種情況下，緩存幾乎無法精確控制應(yīng)該在flash上替換哪些對象。
緩存級寫入放大：
????????在大段(連續(xù)的數(shù)據(jù)塊)中寫入閃存是對總體寫入放大進行微型化的必要條件，但不是充分條件。大分段寫入的主要副作用是緩存級寫入放大(CLWA)。當(dāng)從SSD中刪除的對象被緩存清除策略重寫到它時，就會發(fā)生CLWA。如果段的大小(MBs)明顯大于對象的大小(字節(jié)或KBs)，則很難保證緩存中的高級對象總是與低級別對象或包含舊值的對象在物理上分開存儲。因此，當(dāng)從緩存中刪除具有許多低級別對象的段時，它也可能無意中刪除一些高級別對象。
????????表2給出了Memcachier(一個商業(yè)Memcached服務(wù)提供者)長達(dá)一周的跟蹤的一般統(tǒng)計數(shù)據(jù)[13,14]，圖2給出了在跟蹤中編寫的對象大小的分布。圖中顯示對象大小差異很大，而且通常非常小:寫入緩存的對象的平均大小為257字節(jié)，80.67%的對象小于1 KB。因此，即使使用順序?qū)懭氲亩未笮?mb(這是不會導(dǎo)致額外寫入放大的最小段大小)，每個段平均也將包含32,000多個惟一對象。
????????此外，60.6%的寫操作(和5.8%的所有請求)是未讀的寫操作，這意味著它們在被寫之后永遠(yuǎn)不會被讀，0.5%的請求是更新。未讀寫和更新都有助于寫放大。理想情況下，未讀的寫不應(yīng)該寫入緩存。在更新的情況下，為了在對象更新之后回收該對象的空間，緩存需要擦除并重寫該對象。
????????RIPQ[38]代表了將CLWA最小化的最新技術(shù);它是一個基于ssd的照片緩存，通過插入在過去一起讀取k次的對象來最小化CLWA。當(dāng)對象第一次插入緩存時，它們被緩沖在內(nèi)存中，并定期與其他讀取相同次數(shù)的對象一起作為段移動到flash中。這個想法是，在過去被讀取k次的對象可能在未來具有類似的清除級別。例如，一個讀取過一次的對象與其他讀取過一次的對象存儲在同一段flash中。包含讀取次數(shù)較少的對象的段將比讀取次數(shù)較多的對象的段更快地被清除。
????????RIPQ適用于較大且不可變的照片，但它在web緩存工作負(fù)載中會失效，因為在web緩存工作負(fù)載中，值較小且更新更頻繁。為了說明這一點，我們使用Memcachier跟蹤模擬了RIPQ的CLWA (RIPQ實現(xiàn)是不可公開使用的)，使用一個帶有8個隊列的分段LRU。我們還用受害者緩存策略相比,SSD的nat?ve方法只是作為L2高速緩存(即。，從DRAM中移除的每個對象都寫入SSD)。Facebook的圖形數(shù)據(jù)存儲TAO[11]使用了這種策略，它利用有限的flash作為存儲在DRAM中的數(shù)據(jù)的受害者緩存。仿真為跟蹤中的每個應(yīng)用程序分配相同的內(nèi)存，DRAM與SSD的比例為1:7。
? ??????結(jié)果如表3所示，雖然RIPQ對受害者緩存有了很大的改進，但它仍然從一個非常高的CLWA開始使用。請注意，受害者緩存將受到更大的總WA的影響，因為它還受到DLWA的影響(因為它沒有在大的段中寫入flash)。RIPQ患有CLWA有兩個原因。首先，RIPQ沒有允許策略，它將所有傳入的對象都寫入flash;甚至是未讀的對象或快速更新的對象。其次，當(dāng)某個對象的讀取頻率發(fā)生變化時，它會創(chuàng)建額外的寫操作。例如，如果一個對象在寫完之后的一段時間內(nèi)被讀了兩次，那么它將與在flash上讀了兩次的其他對象分組。但是，如果它被讀了5次以上，那么RIPQ需要重寫它，將它與其他級別更高的對象分組。由于對象比段大小小得多，而且跟蹤中寫入的比例相對較高，所以RIPQ很難保證在同一時間讀取的對象存儲在同一段中。
????????這些結(jié)果提供了兩條線索，說明緩存應(yīng)該如何以不同的方式利用DRAM來最小化web緩存工作負(fù)載的CLWA。首先，并不是應(yīng)用程序插入緩存的每個對象都適合存儲在SSD上。例如，對象在第一次寫入后不久就會更新，或者對象在將來被讀取的可能性很低。然而，這些對象的出現(xiàn)在不同的應(yīng)用程序中有很大的差異。例如，在Memcachier跟蹤的一些應(yīng)用程序中，超過一半的已寫對象將不再讀取，而在一些應(yīng)用程序中，絕大多數(shù)對象將被多次讀取，并且應(yīng)該寫入緩存。其次，由于段大小和對象大小之間的差異，很難保證被驅(qū)逐策略排序相似的對象將存儲在SSD上物理上相鄰的區(qū)域。
????????這兩種觀點都激發(fā)了Flashield，一個成功地在沒有DWLA的情況下最小化CLWA的緩存。
設(shè)計：
????????Flashield的設(shè)計目標(biāo)是最小化緩存級和設(shè)備級的寫放大，同時保持正常的命中率。Flashield設(shè)計的關(guān)鍵觀點是使用DRAM作為過濾器，它可以防止將對象移動到flash中，而flash很快就會被刪除或更新，并保持高效的內(nèi)存索引，從而保持低的寫和讀放大。
????????圖3說明了Flashield中對象的生存期。對象總是首先寫入DRAM。第一次讀取對象之后，F(xiàn)lashield開始收集描述其性能的特性。這些包含關(guān)于對象何時以及多少次被讀取和更新的信息。對象可以通過Flashield的清除算法從DRAM中清除。
????????Flashield會周期性地將一個由許多DRAM對象組成的段(如512 MB)移動到flash中。Flashield使用機器學(xué)習(xí)分類器根據(jù)對象的特征對其進行排序。如果一個對象通過了一個等級閾值，它將被認(rèn)為是移動到flash的候選對象。然后根據(jù)他們的分?jǐn)?shù)對flash的候選人進行排名，這決定了他們被Flashield移動到flash中的順序。這一順序非常重要，當(dāng)有更多的華而不實的候選人，超過可以容納在一個單一的部分。當(dāng)對象被移動到flash后，它將在緩存中駐留相對較長的時間。一旦它的段按FIFO順序從flash中刪除，它就會被移出flash。此時，如果對象的回收優(yōu)先級較低，那么它將被回收;如果對象的回收優(yōu)先級較高，那么它將被重新插入DRAM。一旦對象被重新插入到DRAM中，它必須再次證明自己具有flash的價值，然后再將其重寫到flash中。有關(guān)詳細(xì)信息，請參見x4.3。
????????在Flashield中，DRAM有三個用途。首先，它被用作一個過濾器來決定應(yīng)該將哪些對象插入SSD。其次，它存儲用于在flash上查找和刪除對象的元數(shù)據(jù)。第三，在對象轉(zhuǎn)移到SSD之前，它充當(dāng)對象的緩存層，并為不適合SSD的對象提供緩存層。
? DRAM作為過濾器：
????????在Flashield中，DRAM是將物體移動到flash中的試驗場。當(dāng)對象首次被寫入DRAM時，F(xiàn)lashield并不知道它們是否適合flash。此外，應(yīng)用程序具有獨特的工作負(fù)載，因此需要單獨學(xué)習(xí)它們的訪問模式。
????????判斷哪些對象值得閃速的稻草人方法是根據(jù)簡單的指標(biāo)(如頻率或頻率)對它們進行排序，就像標(biāo)準(zhǔn)的緩存替換策略(如LRU或LFU)所做的那樣。然而，很難為flash設(shè)置一個適用于所有應(yīng)用程序的正弦閾值。例如，系統(tǒng)可以定義一個基于頻率的閾值，要求對象在進入flash之前被讀取多次。然而，對于某些應(yīng)用程序，這種閾值被證明過于嚴(yán)格，因為訪問模式很長，并且由于過早的清除而降低了命中率。對于其他應(yīng)用程序，它也可能過于寬松，因為在這些應(yīng)用程序中，對象將被不必要地寫入flash。即使對于單個應(yīng)用程序，這樣的閾值也是一種啟發(fā)式，必須手動調(diào)優(yōu)(參見下面描述的示例和表4中描述的示例)。
????????機器學(xué)習(xí)不是使用一種放之四海而皆準(zhǔn)的方法，而是可以作為一種動態(tài)學(xué)習(xí)方法，來了解哪些對象適合每個應(yīng)用程序的flash。
Flashiness：
????????我們將flashiness定義為一個指標(biāo)，它可以預(yù)測一個對象是否適合flash。flashiness得分高的對象是滿足兩個條件的對象。首先，它是一個在不久的將來將被訪問n次的對象(其中n是一個可配置參數(shù))。這保證了它不會被緩存的清除函數(shù)清除。其次，它需要在不久的將來是不可變的，因為更新SSD中的對象需要額外的寫操作
????????系統(tǒng)可以使用閾值n(一個對象在未來被讀取的次數(shù))來表示寫放大的敏感度。如果系統(tǒng)對寫入放大非常敏感，它可以將n設(shè)置為一個相對較高的數(shù)字，這將確保Flashield只會將其預(yù)測將在未來多次讀取的對象移動到flash中。另一方面，如果系統(tǒng)對命中率更敏感，則將n設(shè)置為一個較低的數(shù)字。此外，F(xiàn)lashield允許操作員對flash寫速率設(shè)置一個固定的限制，以保持一定的目標(biāo)生存期。
????????通過預(yù)測一個對象在不久的將來將被讀取的次數(shù)(例如，一個小時)，以及省略預(yù)測在這個preiod期間將被更新的對象，可以捕獲上述兩個flash標(biāo)準(zhǔn)。Flashield通過收集兩個特征(1)過去的讀取次數(shù)和(2)過去的更新次數(shù)，使用支持向量機(SVM)的二元分類器來預(yù)測閃度。圖4提供了與Memcachier跟蹤不同應(yīng)用程序的分類器的準(zhǔn)確性，其值為變量n。準(zhǔn)確度定義為，其中tp為真陽性，tn為真陰性，fp為假陽性，fn為假陰性。分類器使用一個小時的訓(xùn)練時間來預(yù)測一個對象在未來是否會被至少n次訪問而不被更新。
? ??????由于不同的應(yīng)用程序的工作負(fù)載不同，預(yù)測的準(zhǔn)確性也不同(從75%到99%)。此外，隨著n個折痕的增加，精度通常會降低。這是因為隨著n的增加，分類器試圖預(yù)測更罕見的事件，其中觀察到的訓(xùn)練數(shù)據(jù)點更少。例如，在接下來的一個小時內(nèi)，被閱讀超過一次的對象比被閱讀超過五次的對象要多。
????????要演示為什么機器學(xué)習(xí)比使用固定的閾值來確定flash的過去訪問次數(shù)更有效，請考慮下面的示例。我們在跟蹤的應(yīng)用程序之間訓(xùn)練了一個簡單的分類器，該分類器使用深度為1的決策樹，利用單個特性(過去讀取的次數(shù))，嘗試用n = 5預(yù)測閃度。表4給出了決策樹根據(jù)其訓(xùn)練樣本為每個應(yīng)用程序選擇的閾值，該閾值將提供最高的預(yù)測精度。結(jié)果表明，沒有一個單一的靜態(tài)閾值對所有應(yīng)用程序都是最優(yōu)的。這也表明很難預(yù)先確定這個閾值是多少。例如，對于應(yīng)用程序d，過去僅發(fā)生兩次讀取就足以預(yù)測將來它將被讀取5次或更多。
? ??Flashiness設(shè)計的討論：
? ??????我們嘗試了幾個與讀取和更新的數(shù)量和頻率相關(guān)的不同特性。我們發(fā)現(xiàn)，在預(yù)測和捕獲讀取和更新的過去信息時，唯一有效的特性是:(1)讀取的過去次數(shù)和(2)更新的過去次數(shù)。
????????令我們驚訝的是，我們發(fā)現(xiàn)，在我們測量的所有應(yīng)用程序中，與最近時間相關(guān)的特性(例如，兩次讀取之間的時間，上次讀取之后的時間)對預(yù)測沒有正面影響，而且事實上，在某些情況下，分類器的準(zhǔn)確性降低了。這支持我們的設(shè)計選擇，將flashiness度量(基于過去訪問的數(shù)量和類型)與驅(qū)逐令策略(通?；谧罱?解耦(例如，LRU或其衍生物之一，請參見x3.4)。
????????此外，我們還嘗試了幾種不同的分類算法。最初，我們嘗試使用邏輯回歸直接預(yù)測這個數(shù)字。我們在Memcachier trace上運行了這個分類器，發(fā)現(xiàn)預(yù)測非常不準(zhǔn)確。嘗試不同的特性和分類后,我們發(fā)現(xiàn)很難準(zhǔn)確預(yù)測到底多少次訪問一個對象將在未來,這就是為什么我們使用二進制分類、預(yù)測未來的讀取次數(shù)是否超過n。我們也試著用一個不同的二元分類器,決策樹,它提供了非常相似的支持向量機的精度。我們決定使用SVM，因為它提供了一個連續(xù)的分?jǐn)?shù)，用來為對象提供一個全局的Flashiness等級。對于決策樹，分?jǐn)?shù)的范圍僅限于葉子的數(shù)量。
?DRAM作為Flash的索引：
????????與日志結(jié)構(gòu)的合并樹(LSM)不同，F(xiàn)lashield將索引存儲在DRAM中(對于DRAM中的對象和flash中的對象)。這允許Flashield以更低的延遲服務(wù)請求，因為索引是從DRAM讀取的。更重要的是，將索引存儲在flash上需要LSMs在對象更新時不斷更新索引，這將創(chuàng)建大量的寫操作[24,27,39]。當(dāng)索引在DRAM上時，更新它很簡單。然而，由于Flashield也使用DRAM作為一個允許控制層，我們必須確保索引將在DRAM上占用最少的空間。
????????與Memcached類似，F(xiàn)lashield將索引存儲在散列表中，以啟用有效的查找。本機索引將包含存儲在flash中的鍵的標(biāo)識、值的位置以及它們在清除隊列中的位置。然而，這樣一個指數(shù)的成本將高得令人望而卻步。如果我們把一個6結(jié)核病閃存設(shè)備平均對象大小257字節(jié)(等于平均對象大小Memcachier跟蹤前20名的應(yīng)用程序),為每一個對象存儲一個散列的關(guān)鍵,避免碰撞至少需要8個字節(jié),每個對象存儲的確切位置是43位,并保持一個指向隊列中的位置將4 - 8個字節(jié)。在DRAM上為每個對象存儲17個字節(jié)將需要406gb的DRAM。這將占用(或超過)高端服務(wù)器的所有DRAM。例如，在RIPQ中，每個內(nèi)存索引條目都是22字節(jié)。我們?yōu)榭勺兇笮〉膶ο笤O(shè)計了一種新的內(nèi)存查找索引，每個對象使用不到4個字節(jié)，不會引起額外的閃存寫入放大。
????????身份的鑰匙。Flashield沒有在索引中存儲鍵的標(biāo)識，而是將它們作為對象元數(shù)據(jù)的一部分保存在flash設(shè)備中。為了在查找哈希表中識別哈希沖突，F(xiàn)lashield比較了flash中的鍵。為了限制鍵查找期間的flash讀取次數(shù)并避免復(fù)雜的表擴展，F(xiàn)lashield使用了一個沒有鏈的多選擇哈希表。在查找過程中，將逐個使用預(yù)定義的散列函數(shù)，這樣，如果沒有找到鍵，就使用下一個散列函數(shù)。使用所有散列函數(shù)，但仍未找到密鑰，F(xiàn)lashield返回一個誤操作。類似地，如果在插入期間發(fā)生沖突，則使用下一個散列函數(shù)重新散列密鑰，以將其映射到查找表中的另一個條目。如果使用了所有散列函數(shù)，并且仍然存在沖突，則將刪除最后一個沖突對象，以便為新鍵騰出空間。
? ??????為了減少在出現(xiàn)哈希沖突時從flash中讀取的多余數(shù)據(jù)，F(xiàn)lashield為每個段使用內(nèi)存中的bloom過濾器，該過濾器指示鍵是否存儲在該段中。我們決定為每個段使用一個bloom過濾器，而不是全局bloom過濾器，以消除bloom過濾器支持刪除的需要(因為每個段都是不可變的)。我們使用bloom過濾器，假陽性率為1%。對于Memcachier跟蹤，這將轉(zhuǎn)換為平均每點擊一次flash，就有1.03次對flash的訪問，每個條目的額外內(nèi)存開銷為10位。
????????對象的位置。索引不直接存儲SSD對象的位置，而是包含兩個單獨的字段:段號和預(yù)定義散列函數(shù)的ID。段號表示flash中存儲對象的連續(xù)段。使用預(yù)定義的散列函數(shù)散列對象的鍵可以提供對象在段中的偏移量。使用哈希函數(shù)來指示段中的對象位置可能會降低閃存的利用率，因為它限制了在段中放置對象的可能位置的數(shù)量。注意，這些哈希函數(shù)與用于哈希表查找的哈希函數(shù)是正交的。我們選擇使用16個預(yù)定義的哈希函數(shù)(即。由于增加了哈希函數(shù)的數(shù)量，使得flash的使用性能得到了顯著的改善。我們將在x5.3中探討flash的使用。注意，由于數(shù)據(jù)是按順序?qū)懭雈lash的，因此8 MB或更大的段大小可以實現(xiàn)最小的DLWA。為了減少索引開銷，我們使用512 MB的段。
????????拆遷政策。為了避免維護由雙鏈點列表組成的完整回收隊列的開銷，F(xiàn)lashield使用時鐘算法[16]，類似于其他內(nèi)存鍵值緩存[18]。CLOCK近似于LRU策略，因此為了評估它的影響，我們在模擬中運行了Memcachier跟蹤中的前5個應(yīng)用程序，并比較了CLOCK和LRU之間的結(jié)果。結(jié)果表明，對于時鐘時間戳，每個對象只保留2位，與LRU相比，平均命中率僅下降0.1%。
????????圖5總結(jié)了Flashield的查找過程。首先對查找鍵進行散列，以在lookup散列表中找到對應(yīng)的條目ID，該散列表提供了段ID。然后，F(xiàn)lashield在段的bloom過濾器中執(zhí)行鍵查找。如果在bloom過濾器中找到鍵，F(xiàn)lashield將從flash上的段讀取對象。由于bloom過濾器可能導(dǎo)致假陽性，如果從flash中讀取的對象與正在查找的對象沒有相同的鍵，那么將再次散列該鍵，F(xiàn)lashield將在查找散列表中再次查找該鍵。類似地，如果在bloom過濾器中沒有找到鍵，則再次散列鍵，F(xiàn)lashield在lookup散列表中執(zhí)行另一個查找。Flashield將嘗試使用所有配置的哈希函數(shù)(默認(rèn)為16)查找對象，直到找到對象為止。如果在所有嘗試之后都沒有找到該對象，則該對象在flash中不存在，F(xiàn)lashield返回一個miss。
? ? ?圖6總結(jié)了哈希表條目格式。索引包含一個額外的位(ghost)，它指示對象是否計劃從flash中刪除。我們在x4.3中描述了這個標(biāo)志的用途。
實現(xiàn)：
????????本節(jié)介紹Flashield的實現(xiàn)。我們在C語言中從頭開始實現(xiàn)Flashield，除了傳輸、分派、請求處理和DRAM對象的哈希表，這些都是從Memcached 1.4.15借來的。Flashield有四個主要功能:讀取、寫入、將數(shù)據(jù)移動到flash和刪除。圖7描述了Flashield架構(gòu)的高級組件。它支持通用的Memcached協(xié)議，因此部署Memcached的應(yīng)用程序可以透明地使用Flashield。
????????對于讀取，F(xiàn)lashield首先檢查DRAM對象的哈希表中是否存在對象，該對象基于memcached的哈希表。如果沒有，它將使用一個單獨的哈希表來檢查對象是否仍然存在于flash中。如果對象存在于DRAM或flash中，F(xiàn)lashield將返回該對象，否則該請求將被視為一個錯誤。傳入的寫和更新總是首先存儲在DRAM中。對于更新，更新后的對象存儲在DRAM中，舊版本無效。Flashield總是在DRAM中為傳入的寫保持一個段大小的空閑空間。
????????Flashield使用大量可配置的工作線程并行處理客戶機請求。為了在DRAM上保持足夠的空閑空間，F(xiàn)lashield使用了一個專用的干凈線程，它在后臺工作，并且不在正常請求(讀/寫)處理的關(guān)鍵路徑上。此外，F(xiàn)lashield讓操作人員配置一個flash寫限制，以確保一定的目標(biāo)生存期。當(dāng)DRAM上的空閑空間下降到段大小以下時，如果有足夠多的對象達(dá)到了flash評分的閾值，并且沒有達(dá)到flash寫速率限制，那么清理器將它們復(fù)制到段緩沖區(qū)中。當(dāng)緩沖區(qū)被填滿時，清理器將段寫入flash，然后釋放對象在DRAM中占用的空間。根據(jù)對象的flashiness評分，將對象按順序移動到flash。當(dāng)SSD已滿時，清潔器將根據(jù)FIFO順序從flash中刪除最后一個段。
? ??????Flashield對所有對象保持全局優(yōu)先級，無論它們是存儲在DRAM或flash中。基于這個全局優(yōu)先級，對象被從Flashield中驅(qū)逐。默認(rèn)情況下，優(yōu)先級是使用時鐘的LRU的近似值。如果下一個被驅(qū)逐的對象是在DRAM中，F(xiàn)lashield只會驅(qū)逐它。如果下一個要清除的對象在flash中，F(xiàn)lashield將它標(biāo)記為ghost對象，當(dāng)它的段從flash中刪除時，它將被清除。注意，將數(shù)據(jù)從DRAM移動到flash是與清除解耦的。它們是并行進行的，并使用不同的度量對對象進行排序。在flash和DRAM之間移動的對象總是保持它們的全局優(yōu)先級排序。當(dāng)DRAM中沒有足夠的對象達(dá)到flash評分的閾值，或者flash寫入速度達(dá)到極限時，清理器將從DRAM中刪除條目，以保持足夠的空閑空間。
????????本節(jié)的其余部分將詳細(xì)描述Flashield如何將對象移動到flash中，以及Flashield分類器和清除算法的實現(xiàn)。
向Flash寫入對象：
? ??????Flashield在DRAM中構(gòu)建了一個flash綁定段，通過一個接一個地為段中的對象尋找空間。預(yù)先確定的哈希函數(shù)的輸出位為每個對象在段中提供不同的可能插入點。Flashield首先根據(jù)對象的flashiness組合一組需要移動到flash的對象。然后，它嘗試根據(jù)對象的大小從這個組中插入對象。首先是大對象，因為它們比小對象需要更多的連續(xù)空間。在這個過程中，一些對象在段中沒有可用的空間。Flashield跳過這些對象，并試圖在下次創(chuàng)建新段時再次插入它們。我們在x 5.3中評估結(jié)果段的利用率。
分類器的實現(xiàn)：
? ??????Flashield的flashiness評分是根據(jù)每個對象的兩個特性計算的。由于這些特性依賴于跨多個對象訪問的信息，因此對象的特性僅在至少讀取一次對象之后生成。如果一個對象從未被讀取過，那么它的flashiness值將自動等于零。
????????Flashield定期為每個應(yīng)用程序訓(xùn)練一個單獨的分類器。對于我們使用的商業(yè)跟蹤，我們發(fā)現(xiàn)在跟蹤開始時一個小時的培訓(xùn)時間就足夠了。 訓(xùn)練分類器的原始方法是在每次訪問DRAM時更新特性。但是，這種方法可能會過度使用某些對象，從而導(dǎo)致分類器不平衡。例如，如果一個小的對象集占所有訪問的99%，那么將為這些對象創(chuàng)建多個特性集，并且flash估計將偏向于流行對象。
????????為了解決這個問題，我們實現(xiàn)了一種抽樣技術(shù)，該技術(shù)為每個對象生成一個單獨的抽樣，在訓(xùn)練期間對其所有訪問進行統(tǒng)一選擇。Flashield沒有在每次對象訪問時更新特性，而是只以1n的概率進行更新，其中n是到目前為止讀取和更新對象的次數(shù)。
????????要演示這種抽樣技術(shù)，請考慮下面的示例。假設(shè)一個對象是第一次寫的，然后讀取。其特征向量為:1;0(過去的讀取次數(shù)，過去的更新次數(shù))。由于讀取和更新的次數(shù)等于1，因此第一次讀取生成的特征向量將是我們用于訓(xùn)練的特征，概率為1。更新對象時(特征向量為:1;1)， Flashield保留第二組特性的概率為12，因為讀取和更新的次數(shù)等于2。這等于從第一次或第二次訪問中均勻采樣特性。每次后續(xù)訪問的采樣概率都是1n，之前訪問的采樣概率也是相同的。
????????在收集了一個小時的樣本后，我們測量了在接下來的一個小時內(nèi)每個物體被擊中的次數(shù)。這個數(shù)字作為訓(xùn)練的目標(biāo)函數(shù)。經(jīng)過這兩個階段后，F(xiàn)lashield使用這些訓(xùn)練樣本和標(biāo)簽訓(xùn)練分類器。
Eviction：
????????Flashield使用時鐘算法對要驅(qū)逐的對象進行排序。每個對象的哈希表條目中只有兩個表示優(yōu)先級的時鐘位，而不是保持精確的優(yōu)先級排序。為了近似LRU，當(dāng)讀取對象時，它的位都設(shè)置為1。MFU(最常用)的近似方法是每次讀取時將位增加1。
????????當(dāng)set操作將對象插入緩存時，可能會觸發(fā)驅(qū)逐。在清除時，F(xiàn)lashield循環(huán)遍歷索引中的每個對象條目，將其時鐘值遞減1。當(dāng)它到達(dá)一個時鐘值為零的條目時，它停止行走。這個物體是choo -sen作為下一個被驅(qū)逐的受害者。如果受害者對象在DRAM中，那么它的空間將被釋放，并且可以為即將到來的值重用。如果在釋放受害者之后有足夠的空間，驅(qū)逐就會停止，否則這個過程會根據(jù)需要重復(fù)。如果對象在flash中，F(xiàn)lashield不能立即從flash中刪除它，因為對SSD的細(xì)粒度寫入會導(dǎo)致高DLWA。相反，條目被標(biāo)記為一個ghost對象，它充當(dāng)flash清理過程的提示。稍后，當(dāng)對象所在的on-flash段即將被覆蓋時，ghost對象將不會被預(yù)先服務(wù)，從而有效地將存儲釋放出來，作為批量flash清理過程的一部分。即便如此，如果ghost對象是與特定鍵關(guān)聯(lián)的最當(dāng)前值，那么它仍然是可訪問的，只要flash清理過程還沒有覆蓋它在flash上的段。在某種意義上，ghost對象接近全局清除級別的底部(包括兩個flash)和DRAM);非鬼對象，被認(rèn)為是在全球驅(qū)逐排名的頂端，我們稱之為熱對象。
????????Flashield在分配一個新段并準(zhǔn)備將其從DRAM移動到flash時觸發(fā)段刪除，前提是flash已滿且未超過配置的寫速率限制。清潔器按FIFO順序從flash中刪除最后一個段。在段擦除期間，它的ghost對象將從緩存中刪除，而熱對象將重新插入DRAM。圖8總結(jié)了這個過程。
????????將對象從flash移動回DRAM將觸發(fā)驅(qū)逐;如果不選中此選項，將會產(chǎn)生兩個問題。首先，如果過早地將對象從DRAM中刪除，而沒有證明它們是華麗的，那么命中率可能會受到影響。其次，如果清除了太多花哨的對象，就會導(dǎo)致寫入放大。Flashield通過一個熱數(shù)據(jù)閾值(HDT)來防止這種情況發(fā)生，它確保在有限的時間內(nèi)可以丟棄足夠多的對象，從而在flash上釋放足夠的空間，而不會對清除造成太大的壓力。在沒有HDT的情況下，清理器可以重新分配低級別對象，以犧牲駐留在DRAM中的高級別對象為代價。
HDT定義為DRAM + SSD hot，其中DRAM是DRAM中可用的對象存儲，SSD是SSD的總大小，hot是分配給熱對象的SSD的百分比。Flashield努力維護HDT，即使傳入的對象在DRAM中有足夠的空間。為此，每當(dāng)熱數(shù)據(jù)量超過HDT時，F(xiàn)lashield就會觸發(fā)一個新的清除，如果其他對象駐留在flash上，則會將其標(biāo)記為ghost。默認(rèn)情況下，hot是70%，所以flash上大約30%的對象是ghost對象。
Ghost對象被標(biāo)記為Ghost之后仍然可以訪問，因為它們不會立即從flash中刪除。如果訪問了ghost對象，它就不再被認(rèn)為是ghost, Flashield將其標(biāo)記為熱對象(ghost位設(shè)置為零)。由于Flashield總是維護HDT，所以將ghost對象從ghost切換到hot可能會觸發(fā)驅(qū)逐。為了避免不必要的DRAM清除，在這種情況下，F(xiàn)lashield不會從DRAM中驅(qū)逐低等級的對象，而只是遍歷flash對象來將對象標(biāo)記為幽靈。
盡管清理器負(fù)責(zé)在DRAM中維護足夠的空閑空間(通過向flash分配新段)，但在極少數(shù)情況下，DRAM可能沒有足夠的空閑空間來容納傳入的寫。當(dāng)flash寫入速率達(dá)到極限時，或者當(dāng)flash -ss得分超過閾值的對象數(shù)量不足以形成一個新的段時，可能會發(fā)生這種情況。在這種情況下，F(xiàn)lashield將觸發(fā)一個特殊的清除，它將只遍歷DRAM對象，并將從DRAM中驅(qū)逐低級別對象以容納傳入的寫。
圖9展示了一個set操作向緩存插入新對象時Flashield的流程圖。
Flashield中的刪除操作不會引起對flash的寫操作。如果對象在DRAM中，則只刪除它。如果它駐留在flash中，則不會立即從flash中刪除它，因為這會導(dǎo)致DLWA。它也沒有被標(biāo)記為ghost，因為ghost對象仍然可以被訪問。相反，F(xiàn)lashield刪除對象的查找條目。在段刪除期間，清理過程通過將其對應(yīng)的查找條目中的段ID與被刪除的段ID進行比較來標(biāo)識已刪除的對象，并且不會保存它們。在此基礎(chǔ)上，F(xiàn)lashield將更新操作處理為刪除操作，然后進行新的插入。
Evaluation：
在本節(jié)中，我們評估了與現(xiàn)有系統(tǒng)相比，F(xiàn)lashield的端到端性能。不幸的是，據(jù)我們所知，沒有大規(guī)模鍵值緩存的公共蹤跡。我們使用Memcachier提供的整個星期的實際跟蹤，Memcachier是一個廣泛使用的memcached服務(wù)提供商。由于Memcachier跟蹤在請求率方面相當(dāng)稀疏，所以我們運行了一組合成的微基準(zhǔn)測試來強調(diào)系統(tǒng)的性能，以度量它的吞吐量和延遲。
端到端性能：
通過從Memcachier跟蹤中重新運行實際應(yīng)用程序，我們比較了Flashield到RIPQ和受害者緩存策略的端到端命中率和寫入放大。由于RIPQ沒有公開的[38]實現(xiàn)，我們不得不運行并比較這三個系統(tǒng)的仿真。每個策略都使用Memcachier跟蹤中分配的相同數(shù)量的內(nèi)存，DRAM和SSD的比例為1:7。我們運行Flashield，其閾值為一個未來讀取。換句話說，預(yù)測未來至少有一次讀取的對象被認(rèn)為是足夠閃速的。由于Flashield為每個應(yīng)用程序使用一個單獨的SVM，我們比較了單個應(yīng)用程序的結(jié)果。要用8個插入點運行RIPQ，并且在flash上至少運行8個不同的段，我們只運行Memcachier分配了足夠內(nèi)存的應(yīng)用程序。
表5給出了Flashield和RIPQ的比較結(jié)果。結(jié)果表明，F(xiàn)lashield的CLWA明顯低于RIPQ和受害者緩存。Flashield的CLWA中值為0.54,RIPQ中值為2.85，而受害者緩存的中值為3.67。即使Flashield對將來讀取的flash使用一個較低的閾值，它仍然阻止了大量不適合SSD的寫操作被寫入到flash中。Flashield和RIPQ有著幾乎相同的命中率。兩者的命中率都比vic-tim緩存低，但是受害者緩存的CLWA要高得多(因為它不處理DLWA，所以總體寫放大也要高得多)。
表6比較了不同閃度預(yù)判閾值下的Flashield。不同應(yīng)用的結(jié)果不同，一般來說，閾值越高，CLWA越低，命中率越低。注意，在一些應(yīng)用程序中，例如在應(yīng)用程序a中，這種權(quán)衡并不適用，因為我們在每個應(yīng)用程序上分別訓(xùn)練分類器，并且每個應(yīng)用程序的執(zhí)行方式不同。
表7描述了在保持每個應(yīng)用程序的內(nèi)存總量不變的情況下，改變DRAM和SSD的比例時的結(jié)果。結(jié)果表明，如果我們過多地減少DRAM的數(shù)量，系統(tǒng)的命中率就會下降。這是因為，當(dāng)DRAM較低時，對象沒有足夠的時間證明自己足夠華麗，可以在從DRAM中移除之前移動到SSD。注意，我們在這些運行中使用了更小的段大小，以便能夠以1:15的DRAM比例顯示結(jié)果。
Microbenchmarks：
我們使用微基準(zhǔn)來驅(qū)動Flashield的實現(xiàn)，以強調(diào)系統(tǒng)的性能，并使用Memcached來減少它的延遲和吞吐量。我們使用4核3.4 GHz Intel Xeon E3-1230 v5(共8個硬件線程)，32 GB的DDR4 DRAM (2133 MHz)和480 GB Intel 535系列SSD。所有實驗都是使用Debian 8.4 AMD64上的標(biāo)準(zhǔn)內(nèi)核、編譯器和庫編譯和運行的。微基準(zhǔn)測試請求基于隨機鍵，平均對象大小為257字節(jié)，這是Memcachier跟蹤中前20個應(yīng)用程序的平均對象大小。我們禁用了操作系統(tǒng)緩沖區(qū)緩存，以確保SSD讀取被直接路由到SSD驅(qū)動器。由于SSD和DRAM的性能相差一個數(shù)量級，我們分別測量了SSD和DRAM命中。最后，我們測量了Memcached 1.4.15的延遲和吞吐量作為基線。
表8給出了microbenchmark實驗的吞吐量和延遲。注意，對于Memcachier和Facebook, Memcached都不是CPU綁定的，而是內(nèi)存容量綁定的[14,15]。Flashield中DRAM hits的延遲和吞吐量與Memcached的延遲和吞吐量非常相似。雖然SSD點擊率的平均延遲顯著高于DRAM，但是當(dāng)在網(wǎng)絡(luò)上部署時，它們的延遲變得相似(網(wǎng)絡(luò)訪問時間通常為100秒或更長)。Flashield的miss延時與DRAM hits的延時相似，因為Flashield的所有查找索引都存儲在DRAM中，只有當(dāng)內(nèi)存中的bloom過濾器之一返回false positive時，F(xiàn)lashield才需要在miss中訪問flash。Flashield的寫吞吐量和延遲與Memcached相同，因為寫總是進入Flashield的DRAM。
Utilization on Flash：
當(dāng)將數(shù)據(jù)從DRAM移動到flash時，F(xiàn)lashield試圖使用預(yù)定義的哈希函數(shù)為flash段中不同可能的插入點分配對象空間。如果沒有插入點引用對象的足夠連續(xù)自由空間，F(xiàn)lashield將跳過對象，并嘗試在下一個段分配期間插入它。
圖10描述了Flashield的flash分配算法的使用情況。為了測量內(nèi)存利用率，我們在Memcachier跟蹤上運行Flashield分配算法，在512 MB的段大小上使用不同數(shù)量的哈希函數(shù)，分配貪婪地試圖分配空間給更多的數(shù)據(jù)，并測量結(jié)果的利用率。注意，當(dāng)段的利用率達(dá)到60%左右時，段的利用率曲線梯度下降，因為當(dāng)Flashield試圖分配對象時，段中與其他前輔助對象發(fā)生碰撞的概率更高。使用16個散列函數(shù)，大約需要1gb的對象才能達(dá)到99%的利用率，平均每個對象需要散列8.2次，直到找到一個具有足夠空間的插入點。
相關(guān)工作：
先前的研究有兩種類型。以前有幾種基于ssd的鍵值緩存用于特定的工作負(fù)載(例如，照片緩存、圖形數(shù)據(jù)庫)，但是在沒有使用專門硬件的情況下，在具有小鍵和可變對象的通用鍵值工作負(fù)載下，它們的閃存壽命都很短。還有大量以前的基于ssd的持久性鍵值存儲。與緩存不同，持久性存儲不維護準(zhǔn)入控制和清除策略，也不受CLWA的影響，因此它們的寫放大問題沒有那么嚴(yán)重。
基于ssd的Key Value緩存Facebook基于flash的照片緩存從McDipper[19]發(fā)展到BlockCache[2]，再到RIPQ[38]，試圖在保持低寫放大的同時提高命中率。McDipper使用了一個簡單的FIFO策略，這使得它的命中率很低。塊緩存通過利用SLRU策略來提高緩存命中率，SLRU策略在flash上也采用了類似的優(yōu)先級控制，但是會導(dǎo)致比McDipper更高的寫入放大。與塊緩存相比，RIPQ的命中率甚至更高，同時它的寫入幅度與McDipper[2]相當(dāng)。RIPQ使用優(yōu)先級感知內(nèi)存塊執(zhí)行插入，并在訪問項時使用虛擬塊跟蹤增加的優(yōu)先級值。然而，在像Memcachier這樣的通用鍵值服務(wù)中，RIPQ比Flashield有5個以上的寫放大，在特定的應(yīng)用中高達(dá)150個。此外，RIPQ的內(nèi)存索引映射每個條目占用22個字節(jié)，消耗了大量DRAM。Flashield的新索引需要每個對象少于4個字節(jié)的DRAM。Facebook的圖形數(shù)據(jù)存儲TAO[11]使用有限的flash作為存儲在DRAM中的數(shù)據(jù)的受害者緩存。因此，它的寫速率很高，因為不經(jīng)常訪問的項被寫入flash并在不久后被刪除。
Twitter已經(jīng)使用Fatcache[21]為其數(shù)據(jù)中心緩存探索了基于ssd的緩存，F(xiàn)atcache[21]是Memcached的修改版本，它緩沖小的寫操作，并利用FIFO作為一個清除策略。Flashield具有比Fatcache更好的寫放大功能，因為不是所有的寫請求都寫到了flash中，而且命中率更高，因為它使用了與LRU類似的清除策略，而LRU提供了比FIFO更高的命中率。此外，F(xiàn)atcache的內(nèi)存索引每個條目需要32字節(jié)(或更多)，比Flashield大8個字節(jié)。
一些系統(tǒng)試圖通過修改SSD的Flash轉(zhuǎn)換層(FTL)來支持基于SSD的緩存。Duracache[26]試圖通過動態(tài)增加flash設(shè)備的糾錯能力來延長SSD緩存的壽命。Shen等人的[37]允許緩存直接將密鑰映射到設(shè)備本身，并消除閃存垃圾收集器的開銷。與這些系統(tǒng)不同的是，F(xiàn)lashield在不改變flash設(shè)備的情況下處理CLWA。
除了鍵值緩存之外，還有一些系統(tǒng)利用flash作為塊級緩存來存儲磁盤[4,22,23,33,35,40]。與Flashield不同，這些系統(tǒng)中的存儲塊總是被寫到flash中，并且是固定大小的(通常是千字節(jié)大小)。由于這個原因，他們使用一個簡單(低效)的內(nèi)存索引來將block的鍵映射到flash中的一個位置。這些屬性使得它們不適用于具有變量和平均較小對象大小的通用鍵值工作負(fù)載。
Cheng等人對塊級緩存中的寫放大和刪除策略之間的權(quán)衡進行了離線分析。他們將Belady的MIN算法推廣到基于閃存的緩存中，并證明了基于lru的清除遠(yuǎn)遠(yuǎn)不是最優(yōu)的oracle清除策略。但是，它們沒有提供在線算法和減少基于ssd的緩存寫入放大的實現(xiàn)。
基于ssd的鍵值存儲由于這些系統(tǒng)是獨立存儲的，所以所有對象最終都必須寫入flash，因此它們不維護承認(rèn)控制和evic策略，而這對于像Flashield這樣的緩存系統(tǒng)是必需的。因此，持久性鍵值存儲不會受到CLWA及其影響的影響，因此它們的生存期約束沒有緩存工作負(fù)載中那么嚴(yán)重。但是，為了提高性能，他們?nèi)匀慌懛糯笞钚』?，因為壓縮數(shù)據(jù)和更新索引仍然需要付出寫放大成本。
LevelDB[5]和RocksDB[9]等系統(tǒng)使用日志結(jié)構(gòu)合并樹(LSM)在flash上存儲整個數(shù)據(jù)集和索引，并在DRAM中向flash寫入緩沖區(qū)以避免DLWA。為了啟用有效的查找，lsm -tree不斷地執(zhí)行一個后臺壓縮過程，對鍵值對進行排序并重新寫入到flash中，從而創(chuàng)建一個主要的寫入放大，特別是對于鍵值緩存之類的工作負(fù)載。WiscKey[27]通過分隔鍵和值來減少寫放大。鍵在LSM-tree中保持排序，而值單獨存儲在日志中，這對于值較大的工作負(fù)載很有幫助。PebblesDB[34]的目標(biāo)是通過使用片段日志結(jié)構(gòu)的合并樹(FLSM)減少壓縮過程中的寫放大，避免在同一樹級別重寫數(shù)據(jù)。此外，NVMKV[28]是一個鍵值存儲，它依賴于高級FTL功能(高級多塊寫入)來提供更高的性能和更低的寫入放大。淤[25]是一個flash鍵值數(shù)據(jù)庫，它利用三個基本的鍵值存儲來最小化存儲在內(nèi)存中的索引。對象首先插入到一個寫優(yōu)化的存儲中，然后重寫并合并到內(nèi)存效率越來越高的存儲中。對象的主要屬性存儲在內(nèi)存效率最高的存儲中，使得每個鍵的平均索引成本很低。然而，與Flashield不同的是，淤泥并沒有優(yōu)化寫入放大，并且假設(shè)值是固定長度的。
總結(jié)：
SSD在采用鍵值緩存用例方面面臨著獨特的挑戰(zhàn)，因為較小的對象大小和頻繁的清除和更新速度會導(dǎo)致過多的寫操作和擦除操作。Flashield是第一個使用DRAM作為對象篩選器的鍵值緩存，這些對象不適合SSD。Flashield使用輕量級機器學(xué)習(xí)配置對象，并動態(tài)學(xué)習(xí)和預(yù)測哪些對象最適合flash。它為可變大小的對象引入了一種新的內(nèi)存索引，每個對象的開銷小于4字節(jié)，同時又不犧牲閃存的寫和讀放大。
本文的思想可以擴展到其他用例。例如，非易失性內(nèi)存(NVM)也面臨持久性方面的挑戰(zhàn)，特別是在用作DRAM的替代品時，可能還需要一個允許策略[17]。這在多層存儲系統(tǒng)中也是如此，在多層存儲系統(tǒng)中，更便宜的存儲層以性能下降為代價提供更多的容量。最后，隨著flash的密度增加(其容忍寫操作的能力降低)，如何處理flash的持久性成為一個越來越緊迫的問題。
