利用頁面重構與數據溫度識別的閃存緩存算法

曾祥偉，鄧玉輝,2+

1.暨南大學信息科學技術學院，廣州510632

2.中國科學院計算技術研究所計算機體系結構國家重點實驗室，北京100190

基于閃存的固態盤（solid state disk，SSD）因讀寫速度快、低能耗、耐沖擊和重量輕等特點被逐漸應用到大規模存儲系統中[1-2]。與磁盤相比，因為沒有機械磁頭尋道時間，所以具有優越的隨機讀性能。對于順序讀和寫操作，SSD 也保持著比機械硬盤（hard disk drive，HDD）更加出色的性能。但是大多數情況下用戶對閃存系統的訪問都是隨機的，這將導致隨著SSD 的寫入量不斷增加寫性能降低，從而造成寫性能不穩定的情況[2]。因此，提高SSD寫效率非常重要。

與HDD 相比，SSD 除有普通的讀寫操作外，擦除操作也是頻繁操作之一。對閃存進行讀寫操作的最小單位是閃存頁，擦除操作的最小單位是閃存塊。閃存具有寫入之前必須先擦除的物理特性，因此對固態盤的更新操作通常先將邏輯頁寫到其他空閑物理頁，將之前的物理頁標記為失效頁，最后修改映射關系，這種更新操作稱為異地更新操作[3-4]。閃存系統采用異地更新操作來代替磁盤的本地更新操作，正是因為這種更新特性，SSD 在使用過程中會不斷產生無效數據頁。為了回收無效頁，SSD 內部會觸發垃圾回收（garbage collection，GC）操作，先將要回收的閃存塊中的有效頁數據搬遷到其他空閑塊中，然后對該回收塊進行擦除操作。SSD 進行垃圾回收操作會占用該芯片的數據總線，如果此時正好有請求需要處理，將導致請求延遲，降低SSD 整體性能[5-6]。因此，降低SSD 在使用過程中的垃圾回收次數也很重要。

通常，閃存完成一次讀請求需要幾十微秒，完成一次寫請求需要幾百微秒甚至更多。當一次寫請求下發至閃存中正好引發異地更新操作時，完成一次寫請求的時間可能要比完成一次讀請求的時間高幾個數量級[3]。根據邏輯頁和物理頁的有效數據狀態，SSD 將異地更新操作分成覆蓋寫和非覆蓋寫操作。

覆蓋寫操作，是即將要寫入的頁有效數據能夠對閃存中已經存在的有效數據進行覆蓋。如圖1 的覆蓋寫操作所示，當LPN1 要寫回閃存時，由映射信息可知要發生異地更新操作，通過映射信息能夠確定LPN1 中的有效數據能夠直接覆蓋PPN1 中的數據，此時PPN1 將被設置為無效頁，LPN1 被寫入新的空閑頁PPN1′，最后更新LPN1 的映射關系。

非覆蓋寫操作，是即將要寫入的頁不能覆蓋閃存中已經存在的有效數據。如圖1 的非覆蓋寫操作所示，LPN2 在寫回閃存時由映射信息可知不能覆蓋PPN2 中的有效數據D4，因此閃存系統將從PPN2 中讀取D4，將LPN2 與D4 進行合并后再寫入空閑頁PPN2′，隨后將PPN2 設置為無效頁，并更新LPN2 的映射關系。由此可知非覆蓋寫操作會引起額外的讀取和數據重組操作，給寫請求帶來延遲。因此，理論上在異地更新操作不可避免的情況下盡可能用覆蓋寫代替非覆蓋寫操作能提高SSD 寫性能。

Fig.1 Overwrite and non-overwrite write operations under out-update圖1 異地更新下的覆蓋寫與非覆蓋寫操作

為了提高SSD 的寫性能，許多廠商會在SSD 內部嵌入DRAM（dynamic random access memory）用作緩存讀寫請求[7-10]，因為實際情況下SSD 的寫性能要遠低于讀性能，所以合理使用DRAM 緩存對SSD 的性能具有重大影響。

本文提出PRLRU（least recently used algorithm by page reconstruction）新型閃存緩存算法來提高閃存系統的寫性能。PRLRU 就寫請求在下發至閃存系統時會產生非覆蓋寫操作的問題，提出了兩種機制：頁面重構和數據溫度識別機制。頁面重構機制是在寫緩存中，如果隊尾頁有效數據不滿一個頁規格大小，則將寫隊列中其他滿足相應條件并且不滿一個頁大小的頁與隊尾頁進行頁面重構操作后再進行寫回。數據溫度識別機制是在緩存隊列中，如果隊尾頁有效數據夠一個頁大小，則通過溫度識別機制，其中溫度是由緩存節點命中次數來表示，將部分緩存區域中的數據頁按照溫度優先級順序進行調整，最后將隊尾數據頁寫回存儲介質。

1 背景和相關工作

1.1 閃存轉換層FTL

SSD 存儲系統由存儲介質和軟件系統組成，其中軟件系統就是閃存轉換層（flash translation layer,FTL）。FTL 主要實現兩部分功能：地址映射和垃圾回收[11]。地址映射用于將邏輯頁/塊映射到物理頁/塊，而垃圾回收則用于回收物理層的無效頁。

FTL 在SSD 內部維持一個映射表用于存儲邏輯頁/塊映射到的物理位置。當一個讀請求達到時，控制器會在緩沖中查找是否命中，若未命中則查找位于FTL 內部的映射表并從閃存相應物理位置讀取數據。當寫請求從緩存區回寫至閃存時，FTL 會為該邏輯頁分配物理頁并將映射信息保存在映射表中。當邏輯頁寫回發生異地更新操作時，FTL 會為該邏輯頁分配新的物理頁，并將原來的物理頁置為無效頁，同時將映射信息保存在映射表中。

按照地址分配粒度可將映射分為頁級映射、塊級映射和混合映射。頁級映射：這種映射方式是以頁為映射單位，將邏輯頁與物理頁一一對應，具有高效的尋址能力[12]。頁級映射的主要問題是需要較大的映射表來存儲所有映射信息，通常在頁大小為4 KB時，1 GB 的SSD 需要至少1 MB 大小的映射表。塊級映射：這種映射僅僅將塊信息記錄在映射表中，因此映射表很小。在NFTL（NAND flash translation layer）[13]中，映射信息由數據塊（D-Block）和更新塊（U-Block）組成，D-Block 是需要被寫入數據的物理塊，而UBlock 表示需要寫入D-Block 的實際位置。如果DBlock 發生更新，則相應的U-Block 會失效，因此在閃存中D-Block 的數量要遠多于U-Block，因此這種映射方式尋址效率較低[13]。混合映射：這種映射方式將頁級映射和塊級映射相結合，在頁級映射基礎上降低了映射表大小，在塊級映射基礎上提高了尋址效率[14]。主要的案例包括FAST（fully-associative sector translation）[14]和LAST（locality-aware sector translation）[15]等，本研究采用頁級映射方式。

1.2 相關工作

目前，企業級SSD 一般會嵌入DRAM 用作緩存數據和映射表。對用作緩存數據部分的緩存區而言，采用的緩存算法會直接影響SSD 性能。Kim 等人提出BPLRU（block padding least recently used）算法，主要針對隨機寫操作，基于LRU（least recently used algorithm）[16]算法原理對數據塊進行緩存管理，在緩存節點回寫時采用頁級填充技術，將隨機寫請求轉換成順序寫請求，以此提高SSD 隨機寫性能。大部分的I/O 負載都具有局部性原理[17-20]，基于閃存的緩存管理算法有很多，其中基于I/O 負載局部性原理的算法有LRU-WSR（the least recently used and writes sequence reordering）[19]、exLRU（expectation-based least recently used）[20]、AD-LRU（adaptive double least recently used）[21]等。

LRU-WSR 在CFLRU（clean-first least recently used）[22]基礎上將緩存中每個頁設置一個以命中次數代表溫度的標志位屬性，命中邏輯頁則修改相應的溫度值，然后按照溫度值大小依次選擇回寫的數據頁。ExLRU 為緩存中的每個頁都設置了一個命中數量標識位和請求數量標識位，通過這兩者標識位的權重比決定數據頁是否發生回寫操作。He 等人提出2QW-Clock[23]算法，在LRU 和2Q[24]的基礎上將緩存區劃分成三部分，分別是兩個雙向鏈表和一個環狀鏈表，按照每個邏輯頁的命中次數以及各個隊列是否已滿依次替換三個緩存隊列數據，提高緩存命中率。

本文經過研究發現，BPLRU 以塊為單位管理映射關系并采用頁級填充技術將隨機寫轉化為順序寫時，需要提前將多個物理頁中的數據讀取出來，然后與緩存中的數據塊進行數據合并再按順序寫回到物理頁，此時每對一個數據塊進行頁級填充并寫回時，額外發生了多次讀操作和寫操作。此外，BPLRU 未對物理頁的更新操作作出優化。

本文提出的PRLRU 是基于BPLRU 的塊級緩存和頁級填充思想和2QW-Clock 的緩存區劃分思想及回寫策略而改進的，不同之處在于：

（1）對寫更新操作進行優化。BPLRU 和2QWClock 都未對閃存更新操作進行優化，PRLRU 對寫更新操作可能產生的覆蓋寫和非覆蓋寫操作進行分析，通過盡可能觸發覆蓋寫操作代替非覆蓋寫操作提高寫效率，同時減少寫操作數量。

（2）填充機制和粒度不同。BPLRU 采用塊級緩存管理和頁級填充技術作為回寫機制，PRLRU 采用頁級緩存管理機制和子頁填充數據頁，避免了BPLRU 緩存回寫時發生的額外讀寫操作，且緩存管理機制和填充機制也不同，本文稱為頁面重構機制。

（3）緩存區劃分機制和回寫策略不同。2QWClock 將緩存區劃分為三部分，分別采用兩個雙向鏈表和一個循環鏈表處理用以提高緩存命中率，此算法較為復雜。PRLRU 為數據頁設置溫度值等級，將緩存區劃分為溫度搜索區和非搜索區兩部分，在頁面重構機制的基礎上按照數據頁溫度等級依次進行回寫操作。PRLRU 在提高緩存命中率的基礎上降低了系統整體復雜性。

2 頁面重構與數據溫度識別策略

2.1 系統概要

圖2 闡述了閃存系統軟硬件I/O 模型，包括由緩存策略、頁面映射、磨損均衡和垃圾回收等模塊組成的FTL 以及閃存芯片。PRLRU 有三個重要模塊，分別是頁面重構（page reconstruction，PR）、數據溫度識別（data temperature recognition，DTI）和頁面重構映射表（refactor the mapping table，RMAP）。

將PRLRU 應用到SSD 內部板載緩存為寫請求服務，從應用層下發的讀寫請求將經由文件系統和塊設備層解析后通過主機接口發送給SSD。SSD 對讀寫請求的處理一般包括：緩存管理和對閃存的讀寫操作。在PRLRU 中，緩存隊列中的數據將會按照PR 和DTI 機制進行回寫操作。PR 的工作原理是在發生寫回操作時將寫緩存中多個不足一個整頁大小的頁進行頁面重構達到一個整頁大小后進行回寫操作，同時減少非覆蓋寫操作。在每一次觸發PR 機制之后相關的邏輯頁都會生成一條重構頁映射，重構頁映射組成的合并映射表稱之為RMAP。原來的邏輯頁與物理頁是一一映射的關系，觸發PR 之后將變成一對一和一對多并存的映射現象，在服務讀請求的時候將需要讀多條映射，可能給讀性能帶來影響。因此提出DTI 機制，利用I/O 負載的局部性原理，將緩存區邏輯劃分為溫度搜索區和非搜索區，并為緩存中的每個邏輯頁設置溫度值，通過判斷溫度值優先級來選取合適邏輯頁進行回寫。通過提高緩存命中率的方式來緩解PR 操作帶來的讀性能問題。

Fig.2 I/O architecture diagram of PRLRU in SSD圖2 PRLRU 在SSD 中的I/O 架構圖

2.2 頁面重構機制

PRLRU 是以頁為單位對緩存隊列進行管理，因為閃存頁是SSD 最小讀寫單位，所以基于頁級映射的SSD 在收到塊設備層下發的I/O 請求后將對請求按頁大小進行拆分。板載緩存上的緩存隊列由大量的數據頁組成，而緩存隊列中的每個頁有效數據并不一定都是一個整頁大小，因此當發生非覆蓋寫操作時，SSD 需要先將對應物理頁中的有效數據讀取出來，再與即將要寫入的邏輯頁進行數據重組，最后寫入閃存。此時，因額外的一次讀取操作而造成寫延時。PRLRU 針對上述問題，盡可能減少SSD 使用過程中的非覆蓋寫操作以提高寫性能。

FTL 中的緩存管理算法有很多，PRLRU 是以LRU 為基礎進行替換策略優化。圖3 描述了PRLRU中PR 模型的操作原理，在觸發頁面重構操作時會出現以下兩種情況：

Fig.3 Example of page reconstruction operation圖3 一次頁面重構操作示例

（1）隊尾節點觸發非覆蓋寫操作，如圖3 中緩存中D10 與Blockn中的物理頁D10 是映射關系，但是不能覆蓋物理頁D10。

（2）隊尾節點不會觸發非覆蓋寫操作，如圖3，假設緩存中D4 是隊尾節點，它能覆蓋Block2 中的物理頁D4，但是為了減少寫操作數量也可能會觸發頁面重構操作。

針對（1）中情況，在緩存隊列中從尾部（如D10）往后依次查詢滿足條件的緩存節點，找到了這種節點（如D2）則將該節點與尾節點合并，合并結果為(D10,D2)，同時從緩存隊列中剔除這兩個節點。

對（2）情況處理與（1）情況處理類似，唯一區別在于（2）情況下在回寫數據之后對原始映射物理頁需要設置為無效，而（1）情況下回寫數據后不會立刻將原始物理頁置為無效頁。

圖3 中數據頁D10 位于LRU 隊列尾部并且將要被寫入閃存，這時PR 模型會檢測D10 有效數據大小是否滿一個整頁大小，若滿足，則不需要進行PR 操作；否則，將進入PR 處理函數，執行算法1。

算法1 將從LRU 隊列尾部往首部開始逐個檢測數據頁有效數據是否滿足一個整頁大小，若不滿足，則檢測該數據頁能否與隊尾頁重構成一個整頁，若滿足頁面重構條件，則進行頁面重構操作，將該數據頁和隊尾數據頁重構成新的頁并寫回閃存介質，同時修改各個數據頁映射表并將該數據頁和隊尾數據頁從緩存中剔除，此時完成了PR 操作。若該數據頁不滿足頁面重構條件或者在緩存隊列中找不到符合條件的數據頁，則進入PRLRU 的DTI 機制進行處理。PR 算法盡可能在緩存中提前消除在回寫時可能發生的非覆蓋寫操作，同時減少了寫操作數量。

算法1頁面重構操作算法

在SSD 內部，FTL 會為每個被寫入閃存的閃存頁維護一條映射存儲在映射表中。在緩存隊列中進行PR 操作后，由于避免了一次或多次非覆蓋寫操作，原本將要失效的物理頁將繼續保持有效性，只有當該邏輯頁被更新時才失效。PRLRU 為重構頁產生一條新映射并分別添加進未發生重構之前的邏輯頁映射表中，這樣邏輯頁和物理頁可能是一對一和一對多并存的映射關系。PRLRU 為每個邏輯頁設置一個非覆蓋寫標志位，初始化為0，默認沒有發生非覆蓋寫操作，發生了PR 操作的數據頁的相應標志位被置為1。

對于讀操作，如果在緩存中未被命中，則FTL會在映射表中檢索，首先檢測頁面重構標志位，如果發生了頁面重構操作，則需要查詢RMAP，按照新映射關系和原始映射（未發生頁面重構操作之前的映射關系）進行相應數據的讀取，進行數據合并后返回給用戶，否則直接讀取原始映射關系即可完成相應的讀請求。

由上述可知，頁面重操作也會帶來一些問題，SSD 內部映射關系增加，勢必影響SSD 的讀響應性能。當緩存中的臟數據頁發生頁面重構操作時，可能在原對應的物理頁中仍然保存著部分有效數據，當對該數據頁進行讀操作時，原本對一個邏輯頁的讀操作只需要對物理頁進行一次讀取操作變成可能需要對多個物理頁進行讀取操作，因此頁面重構操作對讀性能帶來的影響主要表現在對發生了頁面重構操作的數據頁的讀操作次數會增加。因此，還需針對讀性能問題進行研究。

2.3 數據溫度識別回寫機制

為了解決PRLRU 可能因PR 操作帶來的讀性能下降問題，在PR 的基礎上提出了利用時間局部性的DTI機制。

算法LRU-WSR 采用冷數據識別算法和臟數據回寫策略，冷數據識別算法為每一個邏輯頁設置一個標志位表示冷屬性，初始未命中的頁溫度為1，命中后的邏輯頁溫度值修改為0，緩存滿了需要發生回寫操作時優先回寫溫度值為1 的頁。臟數據回寫策略是優先識別緩存中的邏輯頁是否是臟數據，邏輯頁與對應物理頁數據不一致即為臟數據（需觸發寫更新操作），按照每個邏輯頁的冷標志位和是否為臟數據回寫邏輯頁。與LRU-WSR 算法相比，本文提出的DTI 策略保留了LRU-WSR 冷屬性標志位的數據結構，同時細化了數據溫度等級，以保證更充分利用負載的時間局部性特點。此外，由于頁面重構機制會優先處理臟數據問題，因此DTI階段將不考慮臟數據額外處理情況。

算法2QW-Clock 將緩存分為兩個雙向鏈表和一個環狀鏈表，為讀和寫請求服務，為每個邏輯頁設置一個權重值，讀請求數據頁初始權重值等于0，命中則設為1。寫請求默認權重設為5，每當緩存區空間不足需要騰出空間時，將其中一個雙向鏈表中的寫請求數據頁權重值依次減1。與算法2QW-Clock 相比，DTI 機制將專門為寫請求服務，因此在溫度等級劃分上更為簡單，DTI 模型為緩存中的數據頁新增一個溫數據等級，目的是為了能更加充分利用負載的局部特性，盡可能提高緩存命中率。

DTI 機制為緩存中的每個數據頁設置一個整型溫度屬性表示溫度值，溫度梯度分為0、1、2 共三個等級，0 表示冷數據，1 表示溫數據，2 表示熱數據。每個剛進入緩存中的數據頁溫度值被默認設置為0，表示未被命中過，數據頁被命中一次則溫度值加1，溫度值達到2 后將不再增加。溫度值峰值為2 避免了緩存區中的數據頁設置溫度值下降操作。因此，在每觸發一次回寫操作時避免了觸發如2QW-Clock 算法中的循環設置緩存鏈表中每個邏輯頁的溫度值操作。同時，為了避免特殊情況下某些數據因溫度值過高，即使以后長時間未被命中也依舊停留在緩存中，將溫度值峰值保持相對平均水平，以減少緩存污染和增強算法的適用性。

算法2數據溫度識別回寫算法

Fig.4 Example of data temperature identification cache replacement圖4 一次數據溫度識別緩存替換示例

DTI 將緩存區邏輯拆分為溫度搜索區和非搜索區，如圖4。當緩存區隊尾數據頁不滿足PR 算法條件時，FTL 將執行DTI 函數。算法2 說明了DTI 函數的執行路徑，如果隊尾數據是冷數據，則直接回寫至閃存并修改映射表；如果隊尾數據是溫數據，在溫度搜索區從隊尾開始往前搜索冷數據，查找到了后將該數據頁與隊尾數據頁進行交換后再將隊尾數據頁回寫至閃存；如果沒有搜索到冷數據，則直接將隊尾的溫數據回寫至閃存并修改映射表；如果隊尾是熱數據，則按照回寫優先級大小（冷數據＞溫數據＞熱數據）在溫度搜索區依次搜索冷、溫數據，查找到了冷數據則與隊尾熱數據替換再回寫隊尾冷數據，不需執行溫數據搜索；若沒有找到冷數據再搜索溫數據，替換方式與冷數據一致；當溫度搜索區不存在冷、溫數據時，直接回寫隊尾熱數據。

根據I/O 負載的時間局部性原理，被訪問過后的數據頁很可能不久將被再次訪問，DTI 函數正是利用了這種I/O 特性，將數據溫度細分成三個等級，盡可能將有可能被未來訪問的數據駐留在緩存中，通過提高緩存命中率來提升SSD 的讀性能，同時也能提高寫命中率。

3 實驗評估與分析

3.1 實驗環境

本實驗將PRLRU 在SSDsim[11]模擬器上實現，SSDsim 是一款能夠真實有效地模擬真實硬件平臺的開源模擬器，能夠準確模擬FTL 算法。表1 是硬件配置參數以及性能計算參數，閃存介質采用MLC（multilevel cell）。本文實驗采用主頻3.4 GHz，8 核i7-6700處理器，8 GB DDR4 內存的機器。

3.2 測試數據集

表2是選自微軟劍橋研究院的8條真實設備層I/O負載[25]，使用不同FTL 緩存算法和PRLRU 進行實驗對比，經過人工處理后的負載特性如表2 所示。Web和Web1 網頁搜索服務器負載，大部分是讀請求；Syn負載來自郵件服務器，讀寫請求比例相對均衡；Fin1、Fin2 和Fin3 負載是來自金融服務器，以寫請求為主；Syn1 是郵件服務器負載，以寫請求為主；Ms 是以寫請求為主的實時通訊服務器負載。

Table 1 Parameters of SSD simulation in experiment表1 本實驗SSD 模擬的各項參數

Table 2 Characteristics of real workload used in experiments表2 本實驗采用的真實負載的特性

3.3 頁面重構機制額外空間分析

頁面重構機制通過重構部分有效頁減少了實際寫操作數量，但是破壞了原本的頁級映射機制，將映射粒度進一步降低，從而可能增加映射表大小。

本實驗閃存頁大小設置為4 KB，在每個映射表項保存物理地址占4 B 空間且在不觸發頁面重構操作的情況下，映射表空間約占SSD 總空間容量的1‰大小。每觸發一次頁面重構操作且發生了異地更新后，需要在原本的映射關系的基礎上增加一條映射關系，因此增加的額外映射數量來源于非覆蓋寫操作。由于觸發頁面重構操作的數量跟負載特性密切相關，對于長度小的寫請求會發生較多頁面重構操作，而對于長度大的寫請求觸發的頁面重構操作較少，因此額外增加的映射表大小也是不穩定的。

為了確定額外映射空間范圍，對額外增加的映射表開銷的計算通過分析實際負載特性以及頁面重構操作數量來確定。圖5 是選取的8 條真實負載頁面重構操作數量在寫操作數量中的占比情況，頁面重構操作數量占比較大的負載有Fin1、Fin2、Fin3 和Ms，占比范圍是12.33%～14.77%，由表2 可知，這4 個負載的寫請求占比范圍是64.50%～96.94%，寫請求平均大小范圍是4.65～19.34 KB。

Fig.5 Proportion of real workload page reconstruction operations in write operations圖5 真實負載中頁面重構操作在寫操作數量中占比

額外映射表開銷取決于非覆蓋寫更新的頁面重構操作數量，由此可見，頁面重構操作造成的額外映射數量取決于負載寫請求占比和寫請求平均大小。當寫請求占比很大并且平均寫請求大小很小時，頁面重構操作帶來的額外映射表開銷最大，如負載Fin2；當寫請求占比很小并且平均寫請求很大時，頁面重構操作帶來的額外映射表開銷最小，如Web1。這兩種極端情況在選取的負載中都有覆蓋，按最壞情況下計算，即所有負載都是非覆蓋寫情況下的頁面重構操作，額外增加的映射表開銷大致范圍是0%～15%，實際要遠小于15%，平均額外增加的映射表開銷實際要遠小于9.1%。假設固態盤容量為500 GB，在頁大小為4 KB，映射表中每個映射條目占4 B 情況下，映射表總大小約為500 MB。在采用PRLRU 策略時，極端情況映射表額外最多增加75 MB，實際情況下要遠遠小于75 MB，最壞情況下平均額外增加45.5 MB，實際情況下也要遠遠小于45.5 MB。盡管額外增加的映射需要占據小量空間，但是頁面重構機制減少了大量寫操作并能降低垃圾回收數量，能夠有效延長固態盤使用壽命，對固態盤存儲系統整體性能影響較小，同時能夠較大幅度提升讀寫性能。

3.4 溫度搜索區閾值

不同負載具有不同的局部特性，而DTI機制需要利用負載的時間局部特性，因此需要對不同負載分別進行DTI 機制的性能測試。DTI 將緩存區分為溫度搜索區和非搜索區，溫度搜索區的閾值大小會影響DTI對時間局部性的依賴程度，需要確定緩存區中合理的溫度搜索區閾值。從表2 中的8 條負載中選取了4 條具有不同特征的負載作為各類服務器中負載讀寫特性的代表，分別是Syn、Web、Fin1 和Fin2，用作緩存溫度搜索區閾值確定。

圖6 顯示了溫度搜索區閾值從0.1 等距變化到1.0 過程中各個閾值下歸一化后的讀和寫請求平均響應時間。圖6（a）中顯示對于負載Syn、Web、Fin2 在溫度搜索區閾值為0.9 時寫性能達到最好，而負載Fin1 在閾值0.5 到0.9 之間變化不明顯，結合圖6（b）中負載Fin1 隨著閾值的變化整體讀性能波動較小情況，主要原因是負載Fin1 的整體時間局部特征性不強，在有些請求位置局部特征較強而有些位置局部特征較弱，雖然在不同搜索區閾值下表現的平均響應時間呈整體降低趨勢，但是負載Fin1 中部分I/O 對閾值敏感性較低。

圖6（b）中顯示負載Syn 和Fin2 在閾值為0.9 時讀性能達到最好，而Web 在整個溫度搜索區閾值變化范圍內讀請求平均響應時間變化波動不明顯，且負載Web 基本都是讀請求。由此可見，DTI 在溫度搜索區不同閾值的搜索速度不會顯著影響整體性能。實驗結果顯示，DTI 模塊能帶來閃存系統的整體性能提升，綜合圖6（a）和圖6（b）性能結果，溫度搜索區閾值為0.9 時負載的讀性能和寫性能達到整體最佳，在后面實驗中將以此閾值作為閾值參數進行實驗研究。當然，跟大多數利用負載局部性的緩存分區算法類似，通過負載測試預先設定DTI機制溫度搜索區閾值而不能進行線上動態調整也是DTI 機制存在的不足，但對整體性能沒有負面影響。

Fig.6 Normalized read and write requests average response time in different cache thresholds圖6 不同緩存閾值時歸一化讀寫請求平均響應時間

3.5 性能測試

為了更加真實客觀地分析本文提出的PRLRU 緩存算法性能，在SSDsim 中實現了BPLRU 和2QWClock緩存算法。SSDsim中原生緩存管理算法是采用LRU 算法，BPLRU 在LRU 基礎上利用頁級填充技術來提高閃存系統的隨機寫性能；2QW-Clock基于2Q和LRU 算法進行改進，通過提高緩存命中率來提升SSD性能。本文將PRLRU 與LRU、BPLRU 和2QW-Clock進行實驗性能對比來驗證PRLRU的性能可靠性。

考慮到不同負載的實驗數據結果數值大小差異較大和為了更直觀地體現出實驗結果的對比性，將所有實驗數據（包括讀寫平均響應時間、讀寫命中率和GC 數量）都以LRU 為基準進行歸一化處理。處理過程為：假設Tlru表示LRU 性能測試下的結果平均值（響應時間、命中率或GC 數量），Tothers為BPLRU、2QW-Clock 或PRLRU 實驗下的結果平均值（響應時間、命中率或GC 數量），歸一化結果為其中Nlru和Nothers分別為LRU 和其他三組實驗的歸一化實驗結果。

3.5.1 緩存區大小對系統性能的影響

SSD 內置的板載緩存一般扮演著寫緩存角色，通常DRAM 容量越大，SSD 的讀寫性能越好。為此，對緩存區設置了從1 MB 到32 MB 不等的緩存范圍，測試PRLRU 對緩存大小的敏感性。

針對以上8 個真實負載進行緩存大小敏感性測試，實驗結果趨勢和圖6 類似，因此選取了具有大的寫請求特征并以寫請求為主的Fin2 作為緩存敏感性結果代表，與LRU、BPLRU 和2QW-Clock 算法進行對比分析。

圖7 顯示了緩存區大小在1 MB、2 MB、4 MB、8 MB、16 MB、32 MB 范圍時真實負載驅動下的寫請求平均響應時間對比結果。由圖7 可知，PRLRU 在緩存大小持續增加的情況下，寫請求響應時間與其對比實驗相比能夠保持較穩定的走勢。因此，與其他算法相比，隨著緩存區大小的增加，PRLRU 的性能整體提升較快。本實驗設置SSD 空間大小為24 GB，實驗中在所有性能測試緩存區大小為24 MB。

Fig.7 Normalized write requests average response time when Fin2 has different cache sizes圖7 Fin2 在不同緩存下歸一化寫請求平均響應時間

3.5.2 平均響應時間

圖8 是在8 個真實負載驅動下歸一化后的讀和寫請求平均響應時間。圖8（a）中實驗結果與LRU、BPLRU 和2QW-Clock 相比，PRLRU 的寫請求平均響應時間分別平均減少了34.5%、22.3%和28.8%。因為頁面重構機制在緩存區中將大部分可能發生非覆蓋寫操作的數據頁進行了重構操作，使得大量的待寫頁能夠直接以接近一個頁的寫操作時間被響應，減少了寫操作數量，從而降低了寫請求響應時間。圖8（b）中實驗結果表明，與LRU、BPLRU 和2QWClock 算法相比，PRLRU 讀請求平均響應時間分別平均減少了12.5%、8.3%和10.6%。與LRU、BPLRU 和2QW-Clock 相比，PRLRU 在多數負載下的讀性能有小部分提升，在Fin2 和Syn 負載下，讀性能提升較大。

2QW-Clock 在Fin2 負載的讀性能提升較小是因為負載Fin2 中有約97%的請求都是小的寫請求，而2QW-Clock 算法內部采用了兩個鏈表和一個環形隊列對數據進行緩存和替換，內部實現較為復雜，主要針對提高請求命中率，在負載局部性較強時性能突出，但是對于大部分是小寫請求的負載處理性能表現不佳。PRLRU 在負載多數是隨機請求情況下能保持較好的寫性能，因此對于局部性較強，或者順序寫請求較多的場景性能提升相對較小。

3.5.3 命中率

為了更全面地測試算法性能，通過實驗測試了PRLRU 在真實負載下的讀和寫請求命中率。圖9（a）顯示了PRLRU、LRU、BPLRU 和2QW-Clock在8個真實負載驅動下的寫請求命中率對比結果。實驗結果表明，PRLRU 能夠顯著提高SSD 的寫緩存命中率，與LRU、BPLRU 和2QW-Clock 相比分別平均提高了35.1%、10.2%和27.7%。圖9（b）顯示了在真實工作負載下4個對比實驗歸一化后的讀請求命中率。可以發現，在Web、Syn、Fin1、Syn1 和Fin3 負載下的LRU、BPLRU 和PRLRU 讀請求命中率接近1，因此對兩個trace 的讀性能難以有大的提升。在Ms、Fin2 和Web1負載下，PRLRU 相比于LRU、BPLRU 和2QW-Clock，讀請求命中率分別平均提高了17.2%、14.6%和10.1%。

3.5.4 GC 數量

閃存塊具有擦除次數限制，每進行一次GC 操作則至少需要對閃存塊進行一次擦除操作，因此盡可能減少閃存塊的GC 數量能夠延長閃存的使用壽命。由于負載特性的不同，每個負載的垃圾回收次數在數量上有較大差異，例如，PRLUR 在負載Web、Fin1、Fin2和Syn驅動下的垃圾回收數量分別為1 120、9 318、28 917 和9 127 次，因此本文所有數據結果以LRU 為基準進行歸一化處理。

圖10 是在4 種真實負載驅動下包括PRLRU 在內的4 種緩存管理算法的歸一化后的GC 數量對比。顯然，PRLRU 在降低GC 數量方面更具有優勢，能夠顯著減少SSD 使用過程中的GC 數量。在4 種真實負載測試下，與LRU、BPLRU 和2QW-Clock 相比，PRLRU的GC 數量分別平均降低了10.5%、6.3%、8.7%。與LRU 相比，PRLRU 最多降低了11.3%的GC 數量。因此，與其他3 組算法相比，PRLRU 更有利于延長SSD使用壽命。

Fig.8 Comparison of normalized read and write requests average response time圖8 歸一化后的讀和寫請求平均響應時間對比

Fig.9 Comparison of write and read requests hit ratio data driven by real workload圖9 真實負載驅動下的讀和寫請求命中率對比

Fig.10 Comparison of normalized GC count圖10 歸一化后的GC 數量對比

4 結束語

本文提出了PRLRU 算法，在緩存觸發寫請求回寫之前將寫請求進行如下兩個處理：（1）當即將發生回寫的邏輯頁有效數據不滿一個整頁大小時，合理觸發PR 機制，同時修改和添加新的映射關系；（2）當即將發生回寫的邏輯頁不滿足（1）中條件時，觸發DTI機制按優先級順序觸發回寫操作并更新映射表。

本次研究主要集中在閃存的寫緩存上。在PRLRU 的DTI 機制中，通過實驗來確定真實負載的溫度搜索區閾值。因此，在進一步工作中可以就如何自適應確定溫度搜索區閾值進行研究。