曾祥偉，鄧玉輝,2+

1.暨南大學(xué)信息科學(xué)技術(shù)學(xué)院，廣州510632

2.中國科學(xué)院計(jì)算技術(shù)研究所計(jì)算機(jī)體系結(jié)構(gòu)國家重點(diǎn)實(shí)驗(yàn)室，北京100190

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

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

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

覆蓋寫操作，是即將要寫入的頁有效數(shù)據(jù)能夠?qū)﹂W存中已經(jīng)存在的有效數(shù)據(jù)進(jìn)行覆蓋。如圖1 的覆蓋寫操作所示，當(dāng)LPN1 要寫回閃存時，由映射信息可知要發(fā)生異地更新操作，通過映射信息能夠確定LPN1 中的有效數(shù)據(jù)能夠直接覆蓋PPN1 中的數(shù)據(jù)，此時PPN1 將被設(shè)置為無效頁，LPN1 被寫入新的空閑頁P(yáng)PN1′，最后更新LPN1 的映射關(guān)系。

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

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

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

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

1 背景和相關(guān)工作

1.1 閃存轉(zhuǎn)換層FTL

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

FTL 在SSD 內(nèi)部維持一個映射表用于存儲邏輯頁/塊映射到的物理位置。當(dāng)一個讀請求達(dá)到時，控制器會在緩沖中查找是否命中，若未命中則查找位于FTL 內(nèi)部的映射表并從閃存相應(yīng)物理位置讀取數(shù)據(jù)。當(dāng)寫請求從緩存區(qū)回寫至閃存時，F(xiàn)TL 會為該邏輯頁分配物理頁并將映射信息保存在映射表中。當(dāng)邏輯頁寫回發(fā)生異地更新操作時，F(xiàn)TL 會為該邏輯頁分配新的物理頁，并將原來的物理頁置為無效頁，同時將映射信息保存在映射表中。

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

1.2 相關(guān)工作

目前，企業(yè)級SSD 一般會嵌入DRAM 用作緩存數(shù)據(jù)和映射表。對用作緩存數(shù)據(jù)部分的緩存區(qū)而言，采用的緩存算法會直接影響SSD 性能。Kim 等人提出BPLRU（block padding least recently used）算法，主要針對隨機(jī)寫操作，基于LRU（least recently used algorithm）[16]算法原理對數(shù)據(jù)塊進(jìn)行緩存管理，在緩存節(jié)點(diǎn)回寫時采用頁級填充技術(shù)，將隨機(jī)寫請求轉(zhuǎn)換成順序?qū)懻埱?，以此提高SSD 隨機(jī)寫性能。大部分的I/O 負(fù)載都具有局部性原理[17-20]，基于閃存的緩存管理算法有很多，其中基于I/O 負(fù)載局部性原理的算法有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]基礎(chǔ)上將緩存中每個頁設(shè)置一個以命中次數(shù)代表溫度的標(biāo)志位屬性，命中邏輯頁則修改相應(yīng)的溫度值，然后按照溫度值大小依次選擇回寫的數(shù)據(jù)頁。ExLRU 為緩存中的每個頁都設(shè)置了一個命中數(shù)量標(biāo)識位和請求數(shù)量標(biāo)識位，通過這兩者標(biāo)識位的權(quán)重比決定數(shù)據(jù)頁是否發(fā)生回寫操作。He 等人提出2QW-Clock[23]算法，在LRU 和2Q[24]的基礎(chǔ)上將緩存區(qū)劃分成三部分，分別是兩個雙向鏈表和一個環(huán)狀鏈表，按照每個邏輯頁的命中次數(shù)以及各個隊(duì)列是否已滿依次替換三個緩存隊(duì)列數(shù)據(jù)，提高緩存命中率。

本文經(jīng)過研究發(fā)現(xiàn)，BPLRU 以塊為單位管理映射關(guān)系并采用頁級填充技術(shù)將隨機(jī)寫轉(zhuǎn)化為順序?qū)憰r，需要提前將多個物理頁中的數(shù)據(jù)讀取出來，然后與緩存中的數(shù)據(jù)塊進(jìn)行數(shù)據(jù)合并再按順序?qū)懟氐轿锢眄?，此時每對一個數(shù)據(jù)塊進(jìn)行頁級填充并寫回時，額外發(fā)生了多次讀操作和寫操作。此外，BPLRU 未對物理頁的更新操作作出優(yōu)化。

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

（1）對寫更新操作進(jìn)行優(yōu)化。BPLRU 和2QWClock 都未對閃存更新操作進(jìn)行優(yōu)化，PRLRU 對寫更新操作可能產(chǎn)生的覆蓋寫和非覆蓋寫操作進(jìn)行分析，通過盡可能觸發(fā)覆蓋寫操作代替非覆蓋寫操作提高寫效率，同時減少寫操作數(shù)量。

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

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

2 頁面重構(gòu)與數(shù)據(jù)溫度識別策略

2.1 系統(tǒng)概要

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

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

Fig.2 I/O architecture diagram of PRLRU in SSD圖2 PRLRU 在SSD 中的I/O 架構(gòu)圖

2.2 頁面重構(gòu)機(jī)制

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

FTL 中的緩存管理算法有很多，PRLRU 是以LRU 為基礎(chǔ)進(jìn)行替換策略優(yōu)化。圖3 描述了PRLRU中PR 模型的操作原理，在觸發(fā)頁面重構(gòu)操作時會出現(xiàn)以下兩種情況：

Fig.3 Example of page reconstruction operation圖3 一次頁面重構(gòu)操作示例

（1）隊(duì)尾節(jié)點(diǎn)觸發(fā)非覆蓋寫操作，如圖3 中緩存中D10 與Blockn中的物理頁D10 是映射關(guān)系，但是不能覆蓋物理頁D10。

（2）隊(duì)尾節(jié)點(diǎn)不會觸發(fā)非覆蓋寫操作，如圖3，假設(shè)緩存中D4 是隊(duì)尾節(jié)點(diǎn)，它能覆蓋Block2 中的物理頁D4，但是為了減少寫操作數(shù)量也可能會觸發(fā)頁面重構(gòu)操作。

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

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

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

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

算法1頁面重構(gòu)操作算法

在SSD 內(nèi)部，F(xiàn)TL 會為每個被寫入閃存的閃存頁維護(hù)一條映射存儲在映射表中。在緩存隊(duì)列中進(jìn)行PR 操作后，由于避免了一次或多次非覆蓋寫操作，原本將要失效的物理頁將繼續(xù)保持有效性，只有當(dāng)該邏輯頁被更新時才失效。PRLRU 為重構(gòu)頁產(chǎn)生一條新映射并分別添加進(jìn)未發(fā)生重構(gòu)之前的邏輯頁映射表中，這樣邏輯頁和物理頁可能是一對一和一對多并存的映射關(guān)系。PRLRU 為每個邏輯頁設(shè)置一個非覆蓋寫標(biāo)志位，初始化為0，默認(rèn)沒有發(fā)生非覆蓋寫操作，發(fā)生了PR 操作的數(shù)據(jù)頁的相應(yīng)標(biāo)志位被置為1。

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

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

2.3 數(shù)據(jù)溫度識別回寫機(jī)制

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

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

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

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

算法2數(shù)據(jù)溫度識別回寫算法

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

DTI 將緩存區(qū)邏輯拆分為溫度搜索區(qū)和非搜索區(qū)，如圖4。當(dāng)緩存區(qū)隊(duì)尾數(shù)據(jù)頁不滿足PR 算法條件時，F(xiàn)TL 將執(zhí)行DTI 函數(shù)。算法2 說明了DTI 函數(shù)的執(zhí)行路徑，如果隊(duì)尾數(shù)據(jù)是冷數(shù)據(jù)，則直接回寫至閃存并修改映射表；如果隊(duì)尾數(shù)據(jù)是溫?cái)?shù)據(jù)，在溫度搜索區(qū)從隊(duì)尾開始往前搜索冷數(shù)據(jù)，查找到了后將該數(shù)據(jù)頁與隊(duì)尾數(shù)據(jù)頁進(jìn)行交換后再將隊(duì)尾數(shù)據(jù)頁回寫至閃存；如果沒有搜索到冷數(shù)據(jù)，則直接將隊(duì)尾的溫?cái)?shù)據(jù)回寫至閃存并修改映射表；如果隊(duì)尾是熱數(shù)據(jù)，則按照回寫優(yōu)先級大?。ɡ鋽?shù)據(jù)＞溫?cái)?shù)據(jù)＞熱數(shù)據(jù)）在溫度搜索區(qū)依次搜索冷、溫?cái)?shù)據(jù)，查找到了冷數(shù)據(jù)則與隊(duì)尾熱數(shù)據(jù)替換再回寫隊(duì)尾冷數(shù)據(jù)，不需執(zhí)行溫?cái)?shù)據(jù)搜索；若沒有找到冷數(shù)據(jù)再搜索溫?cái)?shù)據(jù)，替換方式與冷數(shù)據(jù)一致；當(dāng)溫度搜索區(qū)不存在冷、溫?cái)?shù)據(jù)時，直接回寫隊(duì)尾熱數(shù)據(jù)。

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

3 實(shí)驗(yàn)評估與分析

3.1 實(shí)驗(yàn)環(huán)境

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

3.2 測試數(shù)據(jù)集

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

Table 1 Parameters of SSD simulation in experiment表1 本實(shí)驗(yàn)SSD 模擬的各項(xiàng)參數(shù)

Table 2 Characteristics of real workload used in experiments表2 本實(shí)驗(yàn)采用的真實(shí)負(fù)載的特性

3.3 頁面重構(gòu)機(jī)制額外空間分析

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

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

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

Fig.5 Proportion of real workload page reconstruction operations in write operations圖5 真實(shí)負(fù)載中頁面重構(gòu)操作在寫操作數(shù)量中占比

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

3.4 溫度搜索區(qū)閾值

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

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

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

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

3.5 性能測試

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

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

3.5.1 緩存區(qū)大小對系統(tǒng)性能的影響

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

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

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

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

3.5.2 平均響應(yīng)時間

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

2QW-Clock 在Fin2 負(fù)載的讀性能提升較小是因?yàn)樨?fù)載Fin2 中有約97%的請求都是小的寫請求，而2QW-Clock 算法內(nèi)部采用了兩個鏈表和一個環(huán)形隊(duì)列對數(shù)據(jù)進(jìn)行緩存和替換，內(nèi)部實(shí)現(xiàn)較為復(fù)雜，主要針對提高請求命中率，在負(fù)載局部性較強(qiáng)時性能突出，但是對于大部分是小寫請求的負(fù)載處理性能表現(xiàn)不佳。PRLRU 在負(fù)載多數(shù)是隨機(jī)請求情況下能保持較好的寫性能，因此對于局部性較強(qiáng)，或者順序?qū)懻埱筝^多的場景性能提升相對較小。

3.5.3 命中率

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

3.5.4 GC 數(shù)量

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

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

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

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

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

4 結(jié)束語

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

本次研究主要集中在閃存的寫緩存上。在PRLRU 的DTI 機(jī)制中，通過實(shí)驗(yàn)來確定真實(shí)負(fù)載的溫度搜索區(qū)閾值。因此，在進(jìn)一步工作中可以就如何自適應(yīng)確定溫度搜索區(qū)閾值進(jìn)行研究。