一種基于分類策略的聚簇頁級閃存轉換層算法

姚英彪 杜晨杰,2 王發寬

1(杭州電子科技大學通信工程學院 杭州 310018)2 (浙江萬里學院科研部 浙江寧波 315100)(yaoyb@hdu.edu.cn)

一種基于分類策略的聚簇頁級閃存轉換層算法

姚英彪1杜晨杰1,2王發寬1

1(杭州電子科技大學通信工程學院 杭州 310018)2(浙江萬里學院科研部 浙江寧波 315100)(yaoyb@hdu.edu.cn)

提出一種基于分類策略的聚簇頁級閃存轉換層算法——CPFTL.1)CPFTL將地址映射緩存分為熱映射表緩存、冷映射表緩存和連續映射表緩存，分別用來緩存訪問頻繁的請求的映射項、訪問不頻繁的請求的映射項和高空間本地性的連續請求的映射項，有效提升各類請求的處理能力;2)為利用連續請求的空間本地性，CPFTL的連續映射表緩存預取多個連續的映射項，提高它對連續請求的響應性能;3)為減少頁級映射算法的轉換頁讀寫開銷，CPFTL的冷映射表緩存采用聚簇策略，即將屬于同一轉換頁中的映射項進行聚簇，按簇進行LRU管理，當冷映射表緩存滿時，根據簇的映射項個數和LRU選取合適的簇剔除到閃存.實驗結果顯示，相比經典的頁級DFTL算法和最新的SDFTL算法，CPFTL的緩存命中率、平均響應時間、地址轉換頁操作次數和閃存塊擦除次數都有顯著提升.

固態硬盤；閃存轉換層；分類策略；映射表；本地性

近半個世紀來，隨著計算機體系結構技術及芯片加工技術的不斷進步，計算機系統的CPU性能與IO性能的差距不斷擴大[1].計算機系統IO性能的瓶頸在于硬盤(hard disk drive， HDD).這些年雖然HDD容量有了很大的提升，但由于其存在機械旋轉結構，訪問速度提升有限，這使得基于HDD的存儲系統成為計算機系統的性能瓶頸之一.相比于傳統的硬盤，固態硬盤(solid state drive， SSD)呈現出許多優良的性能：低功耗、讀寫速度快、防震抗摔性好、無噪音、重量輕、體積小等，因此SSD在許多領域已經開始替代傳統硬盤，它是當前存儲領域的研究熱點之一.

目前常見的SSD主要基于NAND閃存，而NAND閃存的結構與傳統的磁存儲介質不同，其主要特點有：1)閃存只提供讀、寫和擦除3種操作，且這3種操作性能不對稱，讀最快，寫次之，擦除最慢.2)閃存是按頁(page)、塊(block)、平面(plane)的結構進行組織.頁是讀寫的最小單位，一般為2 KB，4 KB，8 KB；塊是擦除的最小單位，一個塊一般包含64頁、128頁.3)閃存擦除后只能寫1次，即所謂的寫前擦除(erase-before-write)[2]，這造成閃存不能原地更新，否則會帶來巨大的開銷.4)閃存每個存儲單元的編程擦除(PE)次數有限[3]，通常SLC閃存的PE次數是10萬次左右，MLC閃存的PE次數是1萬次左右，超過PE次數后，閃存存儲數據不再可靠.

本文研究SSD的閃存轉換層(flash translation layer， FTL)中的地址映射算法，它對SSD的性能、壽命有至關重要的影響，也是當前SSD固件設計中的研究熱點和難點[4].

1 相關工作

1.1 FTL地址映射算法

FTL是一個中間軟件轉換層，它隱藏了閃存的擦除操作，將SSD模擬成只有讀寫操作的傳統硬盤的形式，以適應當前的文件系統.FTL一般包括地址映射、磨損平衡和垃圾回收3個模塊，其中地址映射是FTL最核心的功能，它負責將來自文件系統的邏輯地址轉換為閃存中的物理地址.根據邏輯地址與物理地址映射粒度的大小，FTL可以分為頁映射[5-7]、塊映射[8-10]以及混合映射[11-15].

頁映射需要維護邏輯頁和物理頁之間的映射關系，即建立頁映射表.傳統的頁映射將整個頁映射表存儲在RAM中，當SSD容量增大時，頁級映射表需要大量的RAM空間，這造成傳統的頁級映射很難適應目前的大容量SSD.塊級映射表僅需維護邏輯塊和物理塊之間的映射關系，因而RAM開銷大幅減少；但邏輯頁只能映射到塊中的固定頁，從而降低了地址映射的靈活性[16].為克服以上2種映射方式的缺陷，混合映射機制被提出.混合映射機制將閃存分為數據塊和日志塊，日志塊內使用頁級映射表，數據塊使用塊級映射表，用日志塊來記錄更新.混合映射機制能夠有效降低頁映射占用空間過大和塊映射頻繁擦除的問題，但存在垃圾回收效率低和處理隨機訪問請求性能差的缺點.

針對混合映射機制出現的問題，Gupta等人[6]重新設計頁級映射機制，提出一種按需的頁級FTL(demand-based FTL, DFTL)算法.DFTL采用基于頁的映射機制，將整個映射表都存儲在閃存中，并將閃存從邏輯上分為數據塊區域和轉換塊區域，分別用于存儲常規數據和映射表信息；然后根據實際請求動態加載部分映射表(cached mapping table， CMT)到RAM中，來處理訪問頻繁的請求；同時，DFTL設置了一個全局轉換目錄(global translation directory, GTD)來記錄轉換頁的變化.相對混合映射機制，DFTL取得明顯的響應時間的改善.

在DFTL思想的啟發下，國內外的研究人員提出各種新型頁級閃存轉換層算法，代表有SDFTL[16]，S-FTL[17]，HAT[18]，OAFTL[19]，CDFTL[20]，WAPFTL[21]等.算法SDFTL提出在RAM中增設連續映射表緩存和二級映射表緩存；算法S-FTL提出通過識別3種空間本地性(順序寫、簇寫和稀疏寫)訪問模式來減少按頁映射的映射表大小；算法HAT提出將頁映射表存儲在PCM芯片，實現數據訪問和頁映射信息訪問的并行；算法OAFTL提出根據訪問操作的類型來組織映射表信息，并為映射頁保留日志信息來緩沖頻繁修改的映射信息；算法CDFTL提出以“簇”的方式來裝載剔除映射項；算法WAPFTL提出基于頁映射機制的自適應地址映射算法，能夠在地址轉換過程中預測負載讀寫特性并自適應地調整地址映射信息緩存的策略.

1.2 CPFTL算法

本文提出的聚簇頁級閃存轉換層(clustered page-level flash translation layer, CPFTL)也是一種新型頁級映射機制，與以上工作相比，本文創新主要體現在3點：

1) 采用分類策略思想，將地址映射緩存分為熱映射表緩存(hot CMT，H-CMT)、冷映射表緩存(cold CMT，C-CMT)和連續映射表緩存(sequential CMT， S-CMT)，分別用來緩存訪問頻繁的請求的映射項，訪問不頻繁的請求的映射項和高空間本地性請求(連續請求)的映射項；

2) 為利用連續請求的空間本地性，CPFTL預取多個連續的映射項到S-CMT中，提高它對連續請求的處理能力；

3) 為減少新型頁級映射算法的轉換頁讀寫開銷，CPFTL的C-CMT采用聚簇策略，即將屬于同一轉換頁中的映射項進行聚簇，按簇進行最近最少使用(least recently used, LRU)管理；當C-CMT滿時，根據簇內包含的映射項個數和簇的LRU來選取合適的簇剔除到閃存中去.

實驗結果顯示，平均而言，CPFTL相比經典的DFTL算法，總體緩存命中率提高50.59%，響應時間減少24.43%，地址轉換頁操作次數減少82.87%，閃存塊擦除次數減少29.35%；相比最新的SDFTL算法，總體緩存命中率提升9.88%，響應時間減少8.25%，地址轉換頁操作次數減少50.62%，閃存塊擦除次數減少9.26%.

2 CPFTL算法設計

2.1 總體構架

CPFTL總體結構如圖1所示，圖1中DLPN和DPPN分別表示數據的邏輯頁地址和物理頁地址，TVPN和TPPN分別表示轉換塊區域中頁的虛擬地址和物理地址.在CPFTL中，閃存被分為數據塊區域和轉換塊區域，RAM被分為H-CMT，S-CMT，C-CMT，GTD四個部分.

Fig. 1 The overall architecture of CPFTL圖1 CPFTL的總體構架

數據塊區域用于實際的數據存儲，轉換塊區域用于頁級映射表的存儲.H-CMT用于緩存訪問頻率較高的請求的映射項；C-CMT用于緩存訪問頻率低下的請求的映射項，以及當H-CMT滿時從H-CMT剔除的、發生更新的映射項；S-CMT用于緩存高空間本地性請求(連續請求)的映射項;GTD的作用與DFTL的類似，用來記錄轉換塊區域中每個頁的地址映射項.

2.2 CPFTL關鍵結構

1) H-CMT

H-CMT主要是用來緩存訪問頻繁的請求的映射項.當有請求到來且請求的映射項在H-CMT中時，就可立即得到服務.當請求不在H-CMT，則到S-CMT 和C-CMT中查詢.再者，H-CMT使用LRU策略對每個映射項進行管理.當H-CMT滿時，選擇最近最少訪問的請求的映射項進行剔除.此時，若該映射項已更新，則將其剔除到C-CMT中；反之，則直接從緩存中剔除出去.

2) S-CMT

S-CMT主要是用來緩存高空間本地性請求，也即連續請求的映射項.當一個新的請求到來時，如果請求大小大于2 KB，CPFTL便認為該請求具有連續性，進而1次加載1組連續的映射項到S-CMT中，本文將在3.2節中研究1組包含多少個映射項的參數設置問題.當請求在S-CMT再次命中后，則認為該請求為頻繁訪問請求，并把命中的映射項加載到H-CMT中.再者，S-CMT采用先進先出(first in first out，FIFO)的管理策略，即每次選擇停留時間最長的1組映射項進行剔除或更新.

3) C-CMT

C-CMT主要用來緩存訪問頻率低的請求的映射項.一方面，大小小于或者等于2 KB的請求不在緩存中命中時，都被認為是訪問頻率低的請求，直接加載到C-CMT中；另一方面，C-CMT還存儲從H-CMT剔除的、發生更新的映射項.此外，若C-CMT中的映射項被二次訪問，同樣認為該請求為頻繁訪問請求，需要將此映射項加載到H-CMT中.再者，C-CMT采用聚簇的思想，即將屬于同一轉換頁中的映射項進行聚簇，并使用LRU策略對所有的簇進行管理，如圖2所示：

Fig. 2 Cluster strategy of C-CMT圖2 C-CMT的聚簇策略

當C-CMT滿后，按簇為單位進行剔除.選擇剔除簇時，考慮到：一方面，若僅根據簇的映射項個數選擇剔除簇，即選擇映射項最多的簇進行剔除，則可能會使訪問頻率低下的簇對應的映射項長時間滯留在C-CMT中，浪費了寶貴的C-CMT緩存空間；另一方面，若僅根據LRU原則選擇剔除簇，即選擇最近最少訪問的簇進行剔除，則可能造成每次剔除回收的緩存空間有限，從而造成經常的地址轉換頁訪問，即增大地址轉換頁的讀寫開銷.實際上，本文3.2節的實驗數據也證實了上述2點.因此，CPFTL在選擇剔除簇時，綜合考慮簇的映射項個數和簇在LRU隊列中的位置.具體來說，當C-CMT滿時，先判斷具有最多映射項的簇包含的映射項個數是否大于某個閾值，如果是，選擇該簇進行剔除；否則，根據LRU原則選擇最近最少訪問簇進行剔除.本文將在后續的實驗中研究這個閾值設置問題.

2.3 CPFTL處理流程

算法1給出了CPFTL算法的偽代碼，輸入的是請求的邏輯頁號、請求的大小和請求類型，算法2、算法3和算法4分別是H-CMT，C-CMT，S-CMT加載映射項時的偽代碼.

算法1. CPFTL算法.

輸入: 請求R的邏輯頁號RLPN、 請求大小RSize、請求類型Rtype；

輸出: NULL.

①Size=RSize;

② while (Size≠0)

③ if (RLPN在H-CMT或S-CMT或C-CMT得到命中)

⑤ if (RLPN在S-CMT或C-CMT二次命中)

⑥ 執行算法2，加載RLPN的相關映射項 到H-CMT;

⑦ end if

⑧ else if (Size≤2 KB)*加載映射項到C-CMT*

⑨ 執行算法3，加載RLPN的相關映射項到 C-CMT;

算法2. H-CMT更新策略.

輸入:RLPN;

輸出: NULL.

① if (H-CMT已滿)

② 根據LRU策略選擇犧牲項;

③ if (犧牲項已更新)

④ 執行算法3，加載犧牲項到C-CMT;

⑤ else

⑥ 將犧牲映射項直接從H-CMT中剔除出去;

⑦ end if

⑧ end if

⑨ 加載RLPN的相關映射項到H-CMT.

算法3. C-CMT更新策略.

輸入:RLPN;

輸出: NULL.

① if (C-CMT已滿)

② if (擁有最多映射項的簇的映射項數目大于閾值)

③ 從C-CMT中將這個簇剔除出去;

④ else

⑤ 從C-CMT中剔除最久未使用的簇;

⑥ end if

⑦ end if

⑧ 加載RLPN的相關映射項到C-CMT.

算法4. S-CMT更新策略.

輸入:RLPN;

輸出: NULL.

① if (S-CMT已滿)

② 根據FIFO策略，從S-CMT中剔除一組 映射項;

③ end if

④ 加載RLPN的相關映射項和隨后的一些映射項到S-CMT.

下面給出一個示例，該示例詳細描述了CPFTL處理請求的流程，為方便演示，我們弱化了緩存空間的大小.假設請求到達的順序如下：(15,4,R)，(16,1,W)，(3584,1,W)，(2,1,R).其中，括號內的3個參數分別表示請求的邏輯頁號、請求大小和請求類型；R表示讀請求，W表示寫請求.圖3給出了H-CMT，S-CMT，C-CMT在各階段的存儲狀態，假設邏輯頁3586，1的映射項已經發生改變，且H-CMT已存滿映射項，S-CMT不存儲映射項，如圖3(a)所示.

CPFTL的處理流程為：當請求(15,4,R)到來時，由于請求的映射項不在緩存，且CPFTL判斷出請求的連續性，則預取一組映射項到S-CMT中，使得該連續請求的后3個邏輯頁16～18都能在S-CMT命中，如圖3(b)所示.當請求(16,1,W)到來時，由于該請求的映射項在S-CMT中且被二次訪問，需將其加載到H-CMT中，這時H-CMT已滿，則剔除、更新邏輯頁1的映射項到C-CMT，然后將邏輯頁16的映射項加載到H-CMT中，如圖3(c)所示.當請求(3584,1,W)到來時，由于該請求的映射項不在緩存，則需將該請求的映射項加載到C-CMT中，這時C-CMT已滿，假設具有最多映射項的簇包含的映射項個數小于閾值，則剔除C-CMT中最近最少訪問的簇，然后加載邏輯頁3584的映射項到C-CMT，如圖3(d)所示.當請求(2,1,R)到來時，由于該請求的映射項在C-CMT且被二次訪問，則需要其加載到H-CMT，這時H-CMT已滿，則剔除、更新邏輯頁3586的映射項到C-CMT中，然后加載邏輯頁2的映射項到H-CMT中，如圖3(e)所示.

Fig. 3 An example of CPFTL process圖3 CPFTL處理請求的示例

3 性能評估

3.1 實驗設置

在實驗中，CPFTL采用FlashSim[22]進行性能評估.FlashSim是賓夕法尼亞州立大學開發的固態硬盤仿真器，它是對DiskSim[23]的擴展，即在DiskSim的基礎上添加閃存仿真模塊和閃存與上層的接口模塊.實驗中，固態硬盤大小為16 GB，地址映射緩存大小為64 KB，閃存的關鍵參數如表1所示：

Table 1 Configuration Parameters of Flash Memory

在實驗中，使用一系列真實的企業級負載、DiskSim產生的合成負載以及用磁盤驅動數據跟蹤器DiskMon[24]收集的負載，來仿真3種FTL算法的性能.Financial1和Financial2[25]來自OLTP應用，是金融機構處理在線聯機事務的Trace.WebSearch1和WebSearch2[26]是來自存儲性能委員會(storage performance council, SPC)，以讀為主的網頁搜索引擎Trace.Systemdisk 是由專門的Trace收集工具DiskMon收集的Trace，Test是由DiskSim合成的Trace.表2給出了實驗中使用的各負載的特性.

Table 2 The Trace Characteristics

實驗中，我們選取經典的頁級映射算法DFTL[6]和最新的頁級映射算法SDFTL[16]作為比較算法.我們選取4個性能指標——緩存命中率、地址轉換頁操作次數、平均響應時間和閃存塊擦除次數作為評價標準，具體解釋如下：

1) 緩存命中率指請求的映射項在映射緩存中的命中比率，即直接在映射緩存中得到服務的請求占總請求的比例.

2) 地址轉換頁操作包括轉換頁讀操作和寫操作，即當請求未在映射緩存中命中時引起的轉換頁讀操作或者映射緩存滿時，發生剔除引起的寫操作.

3) 響應時間是指請求完成服務時間與到達時間的時間差，它是垃圾回收、地址映射的開銷以及數據訪問時間的綜合，也是衡量SSD性能的關鍵指標.

4) 塊擦除次數包括地址轉換塊的擦除次數和數據塊的擦除次數，它直接決定了SSD的使用壽命.

3.2 CPFTL參數設置研究

1) H-CMT，S-CMT，C-CMT的空間配置

為獲得最佳的H-CMT，S-CMT，C-CMT的緩存空間配置，我們進行了36組實驗.在實驗中，S-CMT與C-CMT的大小依次設置為4 KB，8 KB，…，24 KB，總容量為64 KB不變.S-CMT的映射項預取個數和C-CMT的閾值分別設為4和100.仿真Trace選擇具有代表性的Financial1和Financial2，性能指標選擇平均響應時間(average response time)，仿真結果如圖4所示.

從圖4可知，在C-CMT容量不變時，一方面，隨著S-CMT的容量逐漸增大，Financial1和Financial2的平均響應時間經歷了由大變小再變大的過程，大多數情況下在S-CMT的大小為16 KB時有最小的平均響應時間；另一方面，這個變化幅度較小，這也說明Financial1和Financial2對S-CMT的容量并不是很敏感.在S-CMT容量不變時，隨著C-CMT的容量逐漸增大，Financial1和Financial2的平均響應時間的變化趨勢是逐漸減小，尤其是從4 KB增加到16 KB時，平均響應時間減小還是非常明顯.根據圖4的實驗結果，為兼顧各種類型負載，后續實驗中我們取H-CMT的大小為28 KB，S-CMT的大小為16 KB，C-CMT的大小為20 KB.

為詳盡分析CPFTL的H-CMT，S-CMT，C-CMT的性能，我們統計了在Financial1負載下的命中率分布及平均響應時間，結果如表3和表4所示，其中Hit ratio為總的緩存命中率，H-CMT hit ratio為H-CMT的命中率，S-CMT hit ratio為S-CMT的命中率，C-CMT hit ratio為C-CMT的命中率.

Fig. 4 Average response time under different size of S-CMT and C-CMT圖4 不同S-CMT和C-CMT大小下的平均響應時間

SizeofS-CMT∕KBAverageResponseTime∕msHitRatio∕%H-CMTHitRatio∕%S-CMTHitRatio∕%C-CMTHitRatio∕%41．67284．8848．9230．215．7581．67085．0548．6930．605．76121．66985．1148．4030．945．77161．66985．1948．1431．225．82201．67185．1847．7531．535．90241．67285．1047．2331．905．97

Table 4 The Variation of Average Response Time and Hit Ratios of Financial1(Size of S-CMT is 16 KB)

從表3中數據可以看到，在C-CMT容量不變時，隨著S-CMT容量的增大，S-CMT與C-CMT的命中率都在提高，H-CMT的命中率在下降，但變化幅度都不大.從命中率大小來看，H-CMT的命中率最高，S-CMT次之，C-CMT最少，這說明H-CMT中存儲訪問頻率較高的映射項，而C-CMT中存儲的映射項訪問頻率較低.

從表4中數據可以看到，在S-CMT容量不變時，隨著C-CMT容量的增大，總的緩存命中率先增大后減小，但變化并不明顯.具體來說，H-CMT的命中率逐漸減小，S-CMT與C-CMT的命中率都在提高.表4數據還表明，平均響應時間隨著C-CMT的增大一直在減少，但后續減少基本可以忽略.

2) C-CMT的剔除策略的閾值配置

在H-CMT為28 KB，S-CMT為16 KB，C-CMT為20 KB的緩存空間配置下，我們研究了C-CMT中的閾值大小配置問題.我們設計了一組仿真實驗，在實驗中閾值大小依次取0，100，300，512.閾值取0表示C-CMT滿時，選擇包含最多映射項的簇進行剔除；閾值取512表示C-CMT滿時，選擇最近最少訪問的簇進行剔除.仿真Trace選擇具有代表性的Financial1，仿真結果如圖5所示.從圖5可以看到，隨著閾值的增大，Financial1的平均響應時間先減少后增大，當閾值取100時整體性能達到最優.另外，其他5個Trace也有相似的結果，因此，后續實驗中我們取C-CMT的閾值為100.

Fig. 5 Average response time of Financial1 under different threshold value of C-CMT圖5 在C-CMT不同預閾值下Financial1的平均響應時間

3) S-CMT的預取映射項個數

Fig. 7 Cache hit ratio of CPFTL, SDFTL and DFTL under different Traces圖7 CPFTL，SDFTL，DFTL在各Trace下總的緩存命中率

同樣，在H-CMT為28 KB、S-CMT為16 KB、C-CMT為20 KB的緩存空間配置下，我們研究S-CMT的預取映射項個數設置問題.我們設計了一組仿真實驗，在實驗中映射項預取個數依次取4，8，16，32，64，128，仿真Trace選擇具有代表性的Financial1，性能指標選擇平均響應時間，仿真結果如圖6所示.從圖6可以看出，隨著預取映射項個數的增加，平均響應時間先減少后增大，當預取映射項個數為32時，平均響應時間為最小.這說明，適當地增加預取映射項個數能有效降低SSD平均響應時間整體性能.此外，其他5個Trace也有相似的結果.因此，S-CMT預取映射項個數設置為32.

Fig. 6 Average response time of Financial1 under different numbers of prefetching map entries of S-CMT圖6 在S-CMT不同預取映射項個數下Financial1的平均響應時間

3.3 CPFTL與SDFTL,DFTL的性能對比分析

1) 總體緩存命中率比較

在不同Trace下，CPFTL，SDFTL，DFTL的總體緩存命中率如圖7所示.實驗結果表明，對于這6個Trace，CPFTL的總體緩存命中率優于SDFTL和DFTL，平均有9.88%和50.59%的改善.需要特別指出的是，WebSearch1和WebSearch2都是以讀請求為主，且讀請求較大，但請求地址較為隨機，重復性很小，故DFTL的總體緩存命中率很低；而SDFTL和CPFTL都采用預取技術，預取多個連續映射項到S-CMT，使得大的連續請求的后若干個邏輯頁都能在S-CMT命中，從而大幅度提高總體緩存命中率.

2) 地址轉換頁操作次數比較

CPFTL，SDFTL，DFTL都采用頁級地址映射機制，緩存未命中會造成額外的轉換頁讀寫操作開銷，因此，地址轉換頁的操作次數能體現CPFTL緩存機制的效果.在不同Trace下，圖8給出的是CPFTL，SDFTL，DFTL的地址轉換頁操作次數比較.為方便比較，將CPFTL，SDFTL，DFTL的地址轉換頁操作次數進行歸一化處理.實驗結果表明，對于不同的負載類型，CPFTL的地址轉換頁操作次數都優于SDFTL和DFTL，平均有50.62%和82.87%的改善，顯著地減少了地址轉換頁的讀寫操作次數.

3) 平均響應時間和塊擦除次數比較

系統的平均響應時間和塊擦除次數是衡量閃存存儲性能的重要指標.在不同Trace下，圖9給出的是CPFTL，SDFTL，DFTL的平均響應時間和閃存擦除次數比較.為方便比較，將CPFTL，SDFTL，DFTL的平均響應時間和塊擦除次數進行歸一化處理.實驗結果表明，對于不同的負載類型，CPFTL的平均響應時間和閃存擦除次數都優于SDFTL和DFTL，相比SDFTL分別有8.25%和9.26%的改善，相比DFTL分別有24.43%和29.35%的改善.

Fig. 8 Address translation page operate count of CPFTL, SDFTL and DFTL under different Traces圖8 CPFTL，SDFTL，DFTL在各Trace下地址轉換頁操作次數

Fig. 9 Average response time and erase count of CPFTL, SDFTL and DFTL under different Traces圖9 CPFTL，SDFTL，DFTL在各Trace下平均響應時間和塊擦除次數

4 結束語

本文提出了一種基于分類策略思想的新型聚簇頁級閃存轉換層算法——CPFTL.首先，它將地址映射緩存分為熱映射表緩存、連續映射表緩存、冷映射表緩存，分別用來緩存訪問頻繁的映射項、連續請求的映射項和訪問頻率低下的映射項，從而有效地提升了對各類請求的處理能力，以及提高地址映射緩存的空間利用率；其次，為利用連續請求的空間本地性，CPFTL預取32個連續的映射項到S-CMT中，提高它對連續請求的處理能力；最后，CPFTL的C-CMT采用聚簇思想，即將屬于同一轉換頁中的映射項進行聚簇，按簇進行LRU管理，當C-CMT滿時，根據簇內包含的映射項個數和簇在LRU隊列中的位置來選取合適的簇剔除到閃存中去.實驗中使用了一系列不同的負載對CPFTL的性能進行評估.實驗結果顯示，平均而言，CPFTL相比經典的DFTL算法，總體緩存命中率提高50.59%，響應時間減少24.43%，地址轉換頁操作次數減少82.87%，閃存塊擦除次數減少29.35%；相比最新的SDFTL算法，總體緩存命中率提升9.88%，響應時間減少8.25%，地址轉換頁操作次數減少50.62%，閃存塊擦除次數減少9.26%.但CPFTL 還有改進之處，例如，可以設計更加準確的請求類型識別方式，或者能夠根據負載的特點自適應地調整其參數設置等，這些問題都留待下一階段的研究工作進行解決.

[1]Lu Youyou, Shu Jiwu. Survey on flash-based storage systems[J]. Journal of Computer Research and Development, 2013, 50(1): 49-59 (in Chinese)(陸游游, 舒繼武. 閃存存儲系統綜述[J]. 計算機研究與發展, 2013, 50(1): 49-59)

[2]Wu Suzhen, Chen Xiaoxi, Mao Bo. GC-RAIS: Garbage collection aware and redundant array of independent SSDs[J]. Journal of Computer Research and Development, 2013, 50(1): 60-68 (in Chinese)(吳素貞, 陳曉熹, 毛波. GC-RAIS: 一種基于垃圾回收感知的固態盤陣列[J]. 計算機研究與發展, 2013, 50(1): 60-68)

[3]Kim S, Kim T. QLRU: NCQ-aware write buffer manage-ment algorithm for SSDs[J]. Electronics Letters, 2013, 49(17): 1079-1081

[4]Wang Jiangtao, Lai Wenyu, Meng Xiaofeng. Flash-based database: Studies, techniques and forecasts[J]. Chinese Journal of Computers, 2013, 36(8): 1549-1567 (in Chinese)(王江濤, 賴文豫, 孟小峰. 閃存數據庫： 現狀、 技術與展望[J]. 計算機學報, 2013, 36(8): 1549-1567)

[5]Ma Dongzhe, Feng Jianhua, Li Guoliang. LazyFTL: A page-level flash translation layer optimized for NAND flash memory[C]Proc of the SIGMOD 2011 and PODS 2011. New York: ACM, 2011: 1-12

[6]Gupta A, Kim Y, Urgaonkar B. DFTL: A flash translation layer employing demand-based selective caching of page-level address mappings[C]Proc of the 14th Int Conf on Architectural Support for Programming Languages and Operating Systems. New York: ACM, 2009: 229-240

[7]Qin Zhiwei, Wang Yi, Liu Duo, et al. A two-level caching mechanism for demand-based page-level address mapping in NAND flash memory storage system[C]Proc of the 17th IEEE Real-Time and Embedded Technology and Applications Symp. Los Alamitos, CA: IEEE Computer Society, 2011: 157-166

[8]Choudhuri S, Givargis T. Performance improvement of block based NAND flash translation layer[C]Proc of the 5th Int Conf on HardwareSoftware Codesign and System Synthesis. New York: ACM, 2007: 257-262

[9]Choudhuri S, Givargis T. Deterministic service guarantees for NAND flash using partial block cleaning[C]Proc of the 6th IEEE & ACMIFIP Int Conf on HardwareSoftware Codesign and System Synthesis. New York: ACM, 2008: 19-24

[10]Qin Zhiwei, Wang Yi, Liu Duo, et al. Demand-based block-level address mapping in large-scale NAND flash storage systems[C]Proc of the 8th IEEE & ACM Int Conf on HardwareSoftware Codesign and System Synthesis. Los Alamitos, CA: IEEE Computer Society, 2010: 173-182

[11]Kim J, Kim J M, Noh S H, et al. A space-efficient flash translation layer for compact systems[J]. IEEE Trans on Consumer Electronics, 2002, 48(2): 366-375

[12]Lee S W, Park D J, Chung T S, et al. A log buffer-based flash translation layer using fully associative sector translation[J]. ACM Trans on Embedded Computing Systems, 2007, 6(3): 1-27

[13]Kang J U, Jo H, Kim J S, et al. A superblock-based flash translation layer for NAND flash memory[C]Proc of the 6th ACM & IEEE Int Conf on Embedded Software. New York: ACM, 2006: 161-170

[14]Lee S, Shin D, Kim Y. LAST: Locality-aware sector translation for NAND flash memory-based storage systems[J]. ACM SIGOPS Operating Systems Review, 2008, 42(6): 36-42

[15]Chen Jinzhong, Yao Nianmin, Cai Shaobin, et al. Page write-related scheme for flash translation layer[J]. Journal on Communications, 2013, 34(6): 76-84 (in Chinese)(陳金忠, 姚念民, 蔡紹濱,等. 基于頁面寫相關的閃存轉換層策略[J]. 通信學報, 2013, 34(6): 76-84)

[16]Yao Yingbiao, Shen Zuobing. An improved DFTL algorithm based on sequential cache and second level cache[J]. Journal of Computer Research and Development, 2014, 51(9): 2012-2021 (in Chinese)(姚英彪, 沈佐兵. 基于連續緩存和二級緩存的 DFTL 改進算法[J]. 計算機研究與發展, 2014, 51 (9): 2012-2021 )

[17]Jiang S, Zhang L, Yuan X, et al. S-FTL: An efficient address translation for flash memory by exploiting spatial locality[C]Proc of the 27th IEEE Symp on Mass Storage Systems and Technologies (MSST). Los Alamitos, CA: IEEE Computer Society, 2011: 1-12

[18]Hu Yang, Jiang Hong, Feng Dan, et al. Achieving page-mapping FTL performance at block-mapping FTL cost by hiding address translation[C]Proc of the 26th IEEE Symp on Massive Storage Systems and Technologies (MSST). Los Alamitos, CA: IEEE Computer Society, 2010: 1-12

[19]Zuan Xiaoying, Tang Xian, Liang Zhichao, et al. OAFTL: An efficient flash translation layer for enterprise application[J]. Journal of Computer Research and Development, 2011, 48(10): 1918-1926 (in Chinese)(繤曉穎, 湯顯, 梁智超, 等. OAFTL: 一種面向企業級應用 的高效閃存轉換層處理策略[J]. 計算機研究與發展, 2011,48(10): 1918-1926)

[20]Lee Y, Jung T, Shin I. Demand-based flash translation layer considering spatial locality[C]Proc of the 28th Annual ACM Symp on Applied Computing. New York: ACM, 2013: 1550-1551

[21]Xie Xuchao, Song Zhenlong, Li Qiong, et al. WAPFTL: A workload adaptive page-level flash translation layer with prediction[J]. Computer Engineering and Science, 2014, 36(7): 1238-1243 (in Chinese)(謝徐超, 宋振龍, 李瓊, 等. WAPFTL： 支持預測機制的負載自適應閃存轉換層算法[J]. 計算機工程與科學, 2014, 36(7): 1238-1243)

[22]Kim Y, Tauras B, Gupta A, et al. FlashSim: A simulator for NAND flash-based solid-state drives[C]Proc of the 1st Int Conf on Advances in System Simulation. Los Alamitos, CA: IEEE Computer Society, 2009: 125-131

[23]Bucy J S, Ganger G R. The DiskSim simulation environment version 3.0 reference manual, CMU-CS-03-102[R]. Pittsburgh, PA: Carnegie Mellon University, 2003

[24]Zhang Qi, Wang Linzhang, Zhang Tian, et al. Optimized address translation method for flash memory [J]. Journal of Software, 2014, 25(2): 314-325 (in Chinese)(張琦, 王林章, 張天, 等. 一種優化的閃存地址映射方法[J]. 軟件學報, 2014, 25(2): 314-325)

[25]Liberate M, Shenoy P. OLTP trace[EBOL]. UMass Trace Repository.[2015-07-06]. http:traces.cs.umass.eduindex.phpstoragestorage

[26]Liberate M, Shenoy P. WebSearch trace[EBOL]. UMass Trace Repository.[2015-07-06]. http:traces.cs.umass.eduindex.phpstoragestorage

Yao Yingbiao, born in 1976. Associate professor of the School of Communication Engineering, Hangzhou Dianzi University. Received his PhD degree in communication and information system from Zhejiang University, Hangzhou, China, in 2006. Member of CCF. His main research interests include storage system design, wireless sensor networks, multimedia signal processing, etc.

Du Chenjie, born in 1990. Received his MSc degree in electronics and communi-cation engineering from Hangzhou Dianzi University in 2016. Since 2016, he has been a research assistant of Zhejiang Wanli University. His main research interests include flash-based solid-state drive technique (du526292624@163.com).

Wang Fakuan, born in 1991.Received his BSc degree in electronic and information engineering from Jiaying University in 2014. Since 2014, he has been a MSc candidate in electronic and communication engineering of Hangzhou Dianzi University. His main research interests include SSD technique (469144949@qq.com).

A Clustered Page-Level Flash Translation Layer Algorithm Based on Classification Strategy

Yao Yingbiao1, Du Chenjie1,2, and Wang Fakuan1

1(SchoolofCommunicationEngineering,HangzhouDianziUniversity,Hangzhou310018)2(DepartmentofScienceandTechnology,ZhejiangWanliUniversity,Ningbo,Zhejiang315100)

This paper proposes a novel clustered page-level flash translation layer (CPFTL) algorithm which is based on classification strategy. Firstly, CPFTL divides RAM into hot cached mapping table (H-CMT), cold cached mapping table (C-CMT) and sequential cached mapping table (S-CMT), which are responsible for buffering map entries of requests with high temporal locality, low temporal locality and high spatial locality, respectively. Secondly, in order to benefit from the spatial locality of sequential requests, CPFTL prefetches multiple sequential map entries into S-CMT, and thus it can improve the response time of sequential requests. Finally, in order to reduce the read and write overhead of translation pages, CPFTL clusters the map entries which belong to the same translation page in C-CMT together, and manage these clusters by LRU (least recently used)strategy. When C-CMT is full, according to the map entry number and LRU of clusters, CPFTL chooses an appropriate cluster to evict into Flash. CPFTL has been extensively evaluated under various realistic workloads. Compared with the state-of-art FTL schemes such as classic DFTL and the latest SDFTL, our benchmark results show that CPFTL can improve cache hit ratio, operation counts of translation pages, response time and erase counts.

solid state drive (SSD); flash translation layer (FTL); classification strategy; mapping table; locality

2015-07-13；

2015-12-14

國家自然科學基金項目(61100044)；浙江省科技創新基金項目(2013TD03)；浙江省科技計劃資助項目(2013C31100) This work was supported by the National Natural Science Foundation of China(61100044), Zhejiang Province Science and Technology Innovation Focused Team Foundation (2013TD03), and Zhejiang Province Science and Technology Project (2013C31100).

TP333