一種基于分類(lèi)策略的聚簇頁(yè)級(jí)閃存轉(zhuǎn)換層算法

姚英彪 杜晨杰,2 王發(fā)寬

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

一種基于分類(lèi)策略的聚簇頁(yè)級(jí)閃存轉(zhuǎn)換層算法

姚英彪1杜晨杰1,2王發(fā)寬1

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

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

固態(tài)硬盤(pán)；閃存轉(zhuǎn)換層；分類(lèi)策略；映射表；本地性

近半個(gè)世紀(jì)來(lái)，隨著計(jì)算機(jī)體系結(jié)構(gòu)技術(shù)及芯片加工技術(shù)的不斷進(jìn)步，計(jì)算機(jī)系統(tǒng)的CPU性能與IO性能的差距不斷擴(kuò)大[1].計(jì)算機(jī)系統(tǒng)IO性能的瓶頸在于硬盤(pán)(hard disk drive， HDD).這些年雖然HDD容量有了很大的提升，但由于其存在機(jī)械旋轉(zhuǎn)結(jié)構(gòu)，訪問(wèn)速度提升有限，這使得基于HDD的存儲(chǔ)系統(tǒng)成為計(jì)算機(jī)系統(tǒng)的性能瓶頸之一.相比于傳統(tǒng)的硬盤(pán)，固態(tài)硬盤(pán)(solid state drive， SSD)呈現(xiàn)出許多優(yōu)良的性能：低功耗、讀寫(xiě)速度快、防震抗摔性好、無(wú)噪音、重量輕、體積小等，因此SSD在許多領(lǐng)域已經(jīng)開(kāi)始替代傳統(tǒng)硬盤(pán)，它是當(dāng)前存儲(chǔ)領(lǐng)域的研究熱點(diǎn)之一.

目前常見(jiàn)的SSD主要基于NAND閃存，而NAND閃存的結(jié)構(gòu)與傳統(tǒng)的磁存儲(chǔ)介質(zhì)不同，其主要特點(diǎn)有：1)閃存只提供讀、寫(xiě)和擦除3種操作，且這3種操作性能不對(duì)稱(chēng)，讀最快，寫(xiě)次之，擦除最慢.2)閃存是按頁(yè)(page)、塊(block)、平面(plane)的結(jié)構(gòu)進(jìn)行組織.頁(yè)是讀寫(xiě)的最小單位，一般為2 KB，4 KB，8 KB；塊是擦除的最小單位，一個(gè)塊一般包含64頁(yè)、128頁(yè).3)閃存擦除后只能寫(xiě)1次，即所謂的寫(xiě)前擦除(erase-before-write)[2]，這造成閃存不能原地更新，否則會(huì)帶來(lái)巨大的開(kāi)銷(xiāo).4)閃存每個(gè)存儲(chǔ)單元的編程擦除(PE)次數(shù)有限[3]，通常SLC閃存的PE次數(shù)是10萬(wàn)次左右，MLC閃存的PE次數(shù)是1萬(wàn)次左右，超過(guò)PE次數(shù)后，閃存存儲(chǔ)數(shù)據(jù)不再可靠.

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

1 相關(guān)工作

1.1 FTL地址映射算法

FTL是一個(gè)中間軟件轉(zhuǎn)換層，它隱藏了閃存的擦除操作，將SSD模擬成只有讀寫(xiě)操作的傳統(tǒng)硬盤(pán)的形式，以適應(yīng)當(dāng)前的文件系統(tǒng).FTL一般包括地址映射、磨損平衡和垃圾回收3個(gè)模塊，其中地址映射是FTL最核心的功能，它負(fù)責(zé)將來(lái)自文件系統(tǒng)的邏輯地址轉(zhuǎn)換為閃存中的物理地址.根據(jù)邏輯地址與物理地址映射粒度的大小，F(xiàn)TL可以分為頁(yè)映射[5-7]、塊映射[8-10]以及混合映射[11-15].

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

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

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

1.2 CPFTL算法

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

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

2) 為利用連續(xù)請(qǐng)求的空間本地性，CPFTL預(yù)取多個(gè)連續(xù)的映射項(xiàng)到S-CMT中，提高它對(duì)連續(xù)請(qǐng)求的處理能力；

3) 為減少新型頁(yè)級(jí)映射算法的轉(zhuǎn)換頁(yè)讀寫(xiě)開(kāi)銷(xiāo)，CPFTL的C-CMT采用聚簇策略，即將屬于同一轉(zhuǎn)換頁(yè)中的映射項(xiàng)進(jìn)行聚簇，按簇進(jìn)行最近最少使用(least recently used, LRU)管理；當(dāng)C-CMT滿時(shí)，根據(jù)簇內(nèi)包含的映射項(xiàng)個(gè)數(shù)和簇的LRU來(lái)選取合適的簇剔除到閃存中去.

實(shí)驗(yàn)結(jié)果顯示，平均而言，CPFTL相比經(jīng)典的DFTL算法，總體緩存命中率提高50.59%，響應(yīng)時(shí)間減少24.43%，地址轉(zhuǎn)換頁(yè)操作次數(shù)減少82.87%，閃存塊擦除次數(shù)減少29.35%；相比最新的SDFTL算法，總體緩存命中率提升9.88%，響應(yīng)時(shí)間減少8.25%，地址轉(zhuǎn)換頁(yè)操作次數(shù)減少50.62%，閃存塊擦除次數(shù)減少9.26%.

2 CPFTL算法設(shè)計(jì)

2.1 總體構(gòu)架

CPFTL總體結(jié)構(gòu)如圖1所示，圖1中DLPN和DPPN分別表示數(shù)據(jù)的邏輯頁(yè)地址和物理頁(yè)地址，TVPN和TPPN分別表示轉(zhuǎn)換塊區(qū)域中頁(yè)的虛擬地址和物理地址.在CPFTL中，閃存被分為數(shù)據(jù)塊區(qū)域和轉(zhuǎn)換塊區(qū)域，RAM被分為H-CMT，S-CMT，C-CMT，GTD四個(gè)部分.

Fig. 1 The overall architecture of CPFTL圖1 CPFTL的總體構(gòu)架

數(shù)據(jù)塊區(qū)域用于實(shí)際的數(shù)據(jù)存儲(chǔ)，轉(zhuǎn)換塊區(qū)域用于頁(yè)級(jí)映射表的存儲(chǔ).H-CMT用于緩存訪問(wèn)頻率較高的請(qǐng)求的映射項(xiàng)；C-CMT用于緩存訪問(wèn)頻率低下的請(qǐng)求的映射項(xiàng)，以及當(dāng)H-CMT滿時(shí)從H-CMT剔除的、發(fā)生更新的映射項(xiàng)；S-CMT用于緩存高空間本地性請(qǐng)求(連續(xù)請(qǐng)求)的映射項(xiàng);GTD的作用與DFTL的類(lèi)似，用來(lái)記錄轉(zhuǎn)換塊區(qū)域中每個(gè)頁(yè)的地址映射項(xiàng).

2.2 CPFTL關(guān)鍵結(jié)構(gòu)

1) H-CMT

H-CMT主要是用來(lái)緩存訪問(wèn)頻繁的請(qǐng)求的映射項(xiàng).當(dāng)有請(qǐng)求到來(lái)且請(qǐng)求的映射項(xiàng)在H-CMT中時(shí)，就可立即得到服務(wù).當(dāng)請(qǐng)求不在H-CMT，則到S-CMT 和C-CMT中查詢.再者，H-CMT使用LRU策略對(duì)每個(gè)映射項(xiàng)進(jìn)行管理.當(dāng)H-CMT滿時(shí)，選擇最近最少訪問(wèn)的請(qǐng)求的映射項(xiàng)進(jìn)行剔除.此時(shí)，若該映射項(xiàng)已更新，則將其剔除到C-CMT中；反之，則直接從緩存中剔除出去.

2) S-CMT

S-CMT主要是用來(lái)緩存高空間本地性請(qǐng)求，也即連續(xù)請(qǐng)求的映射項(xiàng).當(dāng)一個(gè)新的請(qǐng)求到來(lái)時(shí)，如果請(qǐng)求大小大于2 KB，CPFTL便認(rèn)為該請(qǐng)求具有連續(xù)性，進(jìn)而1次加載1組連續(xù)的映射項(xiàng)到S-CMT中，本文將在3.2節(jié)中研究1組包含多少個(gè)映射項(xiàng)的參數(shù)設(shè)置問(wèn)題.當(dāng)請(qǐng)求在S-CMT再次命中后，則認(rèn)為該請(qǐng)求為頻繁訪問(wèn)請(qǐng)求，并把命中的映射項(xiàng)加載到H-CMT中.再者，S-CMT采用先進(jìn)先出(first in first out，F(xiàn)IFO)的管理策略，即每次選擇停留時(shí)間最長(zhǎng)的1組映射項(xiàng)進(jìn)行剔除或更新.

3) C-CMT

C-CMT主要用來(lái)緩存訪問(wèn)頻率低的請(qǐng)求的映射項(xiàng).一方面，大小小于或者等于2 KB的請(qǐng)求不在緩存中命中時(shí)，都被認(rèn)為是訪問(wèn)頻率低的請(qǐng)求，直接加載到C-CMT中；另一方面，C-CMT還存儲(chǔ)從H-CMT剔除的、發(fā)生更新的映射項(xiàng).此外，若C-CMT中的映射項(xiàng)被二次訪問(wèn)，同樣認(rèn)為該請(qǐng)求為頻繁訪問(wèn)請(qǐng)求，需要將此映射項(xiàng)加載到H-CMT中.再者，C-CMT采用聚簇的思想，即將屬于同一轉(zhuǎn)換頁(yè)中的映射項(xiàng)進(jìn)行聚簇，并使用LRU策略對(duì)所有的簇進(jìn)行管理，如圖2所示：

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

當(dāng)C-CMT滿后，按簇為單位進(jìn)行剔除.選擇剔除簇時(shí)，考慮到：一方面，若僅根據(jù)簇的映射項(xiàng)個(gè)數(shù)選擇剔除簇，即選擇映射項(xiàng)最多的簇進(jìn)行剔除，則可能會(huì)使訪問(wèn)頻率低下的簇對(duì)應(yīng)的映射項(xiàng)長(zhǎng)時(shí)間滯留在C-CMT中，浪費(fèi)了寶貴的C-CMT緩存空間；另一方面，若僅根據(jù)LRU原則選擇剔除簇，即選擇最近最少訪問(wèn)的簇進(jìn)行剔除，則可能造成每次剔除回收的緩存空間有限，從而造成經(jīng)常的地址轉(zhuǎn)換頁(yè)訪問(wèn)，即增大地址轉(zhuǎn)換頁(yè)的讀寫(xiě)開(kāi)銷(xiāo).實(shí)際上，本文3.2節(jié)的實(shí)驗(yàn)數(shù)據(jù)也證實(shí)了上述2點(diǎn).因此，CPFTL在選擇剔除簇時(shí)，綜合考慮簇的映射項(xiàng)個(gè)數(shù)和簇在LRU隊(duì)列中的位置.具體來(lái)說(shuō)，當(dāng)C-CMT滿時(shí)，先判斷具有最多映射項(xiàng)的簇包含的映射項(xiàng)個(gè)數(shù)是否大于某個(gè)閾值，如果是，選擇該簇進(jìn)行剔除；否則，根據(jù)LRU原則選擇最近最少訪問(wèn)簇進(jìn)行剔除.本文將在后續(xù)的實(shí)驗(yàn)中研究這個(gè)閾值設(shè)置問(wèn)題.

2.3 CPFTL處理流程

算法1給出了CPFTL算法的偽代碼，輸入的是請(qǐng)求的邏輯頁(yè)號(hào)、請(qǐng)求的大小和請(qǐng)求類(lèi)型，算法2、算法3和算法4分別是H-CMT，C-CMT，S-CMT加載映射項(xiàng)時(shí)的偽代碼.

算法1. CPFTL算法.

輸入: 請(qǐng)求R的邏輯頁(yè)號(hào)RLPN、 請(qǐng)求大小RSize、請(qǐng)求類(lèi)型Rtype；

輸出: NULL.

①Size=RSize;

② while (Size≠0)

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

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

⑥ 執(zhí)行算法2，加載RLPN的相關(guān)映射項(xiàng) 到H-CMT;

⑦ end if

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

⑨ 執(zhí)行算法3，加載RLPN的相關(guān)映射項(xiàng)到 C-CMT;

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

輸入:RLPN;

輸出: NULL.

① if (H-CMT已滿)

② 根據(jù)LRU策略選擇犧牲項(xiàng);

③ if (犧牲項(xiàng)已更新)

④ 執(zhí)行算法3，加載犧牲項(xiàng)到C-CMT;

⑤ else

⑥ 將犧牲映射項(xiàng)直接從H-CMT中剔除出去;

⑦ end if

⑧ end if

⑨ 加載RLPN的相關(guān)映射項(xiàng)到H-CMT.

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

輸入:RLPN;

輸出: NULL.

① if (C-CMT已滿)

② if (擁有最多映射項(xiàng)的簇的映射項(xiàng)數(shù)目大于閾值)

③ 從C-CMT中將這個(gè)簇剔除出去;

④ else

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

⑥ end if

⑦ end if

⑧ 加載RLPN的相關(guān)映射項(xiàng)到C-CMT.

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

輸入:RLPN;

輸出: NULL.

① if (S-CMT已滿)

② 根據(jù)FIFO策略，從S-CMT中剔除一組 映射項(xiàng);

③ end if

④ 加載RLPN的相關(guān)映射項(xiàng)和隨后的一些映射項(xiàng)到S-CMT.

下面給出一個(gè)示例，該示例詳細(xì)描述了CPFTL處理請(qǐng)求的流程，為方便演示，我們?nèi)趸司彺婵臻g的大小.假設(shè)請(qǐng)求到達(dá)的順序如下：(15,4,R)，(16,1,W)，(3584,1,W)，(2,1,R).其中，括號(hào)內(nèi)的3個(gè)參數(shù)分別表示請(qǐng)求的邏輯頁(yè)號(hào)、請(qǐng)求大小和請(qǐng)求類(lèi)型；R表示讀請(qǐng)求，W表示寫(xiě)請(qǐng)求.圖3給出了H-CMT，S-CMT，C-CMT在各階段的存儲(chǔ)狀態(tài)，假設(shè)邏輯頁(yè)3586，1的映射項(xiàng)已經(jīng)發(fā)生改變，且H-CMT已存滿映射項(xiàng)，S-CMT不存儲(chǔ)映射項(xiàng)，如圖3(a)所示.

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

Fig. 3 An example of CPFTL process圖3 CPFTL處理請(qǐng)求的示例

3 性能評(píng)估

3.1 實(shí)驗(yàn)設(shè)置

在實(shí)驗(yàn)中，CPFTL采用FlashSim[22]進(jìn)行性能評(píng)估.FlashSim是賓夕法尼亞州立大學(xué)開(kāi)發(fā)的固態(tài)硬盤(pán)仿真器，它是對(duì)DiskSim[23]的擴(kuò)展，即在DiskSim的基礎(chǔ)上添加閃存仿真模塊和閃存與上層的接口模塊.實(shí)驗(yàn)中，固態(tài)硬盤(pán)大小為16 GB，地址映射緩存大小為64 KB，閃存的關(guān)鍵參數(shù)如表1所示：

Table 1 Configuration Parameters of Flash Memory

在實(shí)驗(yàn)中，使用一系列真實(shí)的企業(yè)級(jí)負(fù)載、DiskSim產(chǎn)生的合成負(fù)載以及用磁盤(pán)驅(qū)動(dòng)數(shù)據(jù)跟蹤器DiskMon[24]收集的負(fù)載，來(lái)仿真3種FTL算法的性能.Financial1和Financial2[25]來(lái)自O(shè)LTP應(yīng)用，是金融機(jī)構(gòu)處理在線聯(lián)機(jī)事務(wù)的Trace.WebSearch1和WebSearch2[26]是來(lái)自存儲(chǔ)性能委員會(huì)(storage performance council, SPC)，以讀為主的網(wǎng)頁(yè)搜索引擎Trace.Systemdisk 是由專(zhuān)門(mén)的Trace收集工具DiskMon收集的Trace，Test是由DiskSim合成的Trace.表2給出了實(shí)驗(yàn)中使用的各負(fù)載的特性.

Table 2 The Trace Characteristics

實(shí)驗(yàn)中，我們選取經(jīng)典的頁(yè)級(jí)映射算法DFTL[6]和最新的頁(yè)級(jí)映射算法SDFTL[16]作為比較算法.我們選取4個(gè)性能指標(biāo)——緩存命中率、地址轉(zhuǎn)換頁(yè)操作次數(shù)、平均響應(yīng)時(shí)間和閃存塊擦除次數(shù)作為評(píng)價(jià)標(biāo)準(zhǔn)，具體解釋如下：

1) 緩存命中率指請(qǐng)求的映射項(xiàng)在映射緩存中的命中比率，即直接在映射緩存中得到服務(wù)的請(qǐng)求占總請(qǐng)求的比例.

2) 地址轉(zhuǎn)換頁(yè)操作包括轉(zhuǎn)換頁(yè)讀操作和寫(xiě)操作，即當(dāng)請(qǐng)求未在映射緩存中命中時(shí)引起的轉(zhuǎn)換頁(yè)讀操作或者映射緩存滿時(shí)，發(fā)生剔除引起的寫(xiě)操作.

3) 響應(yīng)時(shí)間是指請(qǐng)求完成服務(wù)時(shí)間與到達(dá)時(shí)間的時(shí)間差，它是垃圾回收、地址映射的開(kāi)銷(xiāo)以及數(shù)據(jù)訪問(wèn)時(shí)間的綜合，也是衡量SSD性能的關(guān)鍵指標(biāo).

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

3.2 CPFTL參數(shù)設(shè)置研究

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

為獲得最佳的H-CMT，S-CMT，C-CMT的緩存空間配置，我們進(jìn)行了36組實(shí)驗(yàn).在實(shí)驗(yàn)中，S-CMT與C-CMT的大小依次設(shè)置為4 KB，8 KB，…，24 KB，總?cè)萘繛?4 KB不變.S-CMT的映射項(xiàng)預(yù)取個(gè)數(shù)和C-CMT的閾值分別設(shè)為4和100.仿真Trace選擇具有代表性的Financial1和Financial2，性能指標(biāo)選擇平均響應(yīng)時(shí)間(average response time)，仿真結(jié)果如圖4所示.

從圖4可知，在C-CMT容量不變時(shí)，一方面，隨著S-CMT的容量逐漸增大，F(xiàn)inancial1和Financial2的平均響應(yīng)時(shí)間經(jīng)歷了由大變小再變大的過(guò)程，大多數(shù)情況下在S-CMT的大小為16 KB時(shí)有最小的平均響應(yīng)時(shí)間；另一方面，這個(gè)變化幅度較小，這也說(shuō)明Financial1和Financial2對(duì)S-CMT的容量并不是很敏感.在S-CMT容量不變時(shí)，隨著C-CMT的容量逐漸增大，F(xiàn)inancial1和Financial2的平均響應(yīng)時(shí)間的變化趨勢(shì)是逐漸減小，尤其是從4 KB增加到16 KB時(shí)，平均響應(yīng)時(shí)間減小還是非常明顯.根據(jù)圖4的實(shí)驗(yàn)結(jié)果，為兼顧各種類(lèi)型負(fù)載，后續(xù)實(shí)驗(yàn)中我們?nèi)-CMT的大小為28 KB，S-CMT的大小為16 KB，C-CMT的大小為20 KB.

為詳盡分析CPFTL的H-CMT，S-CMT，C-CMT的性能，我們統(tǒng)計(jì)了在Financial1負(fù)載下的命中率分布及平均響應(yīng)時(shí)間，結(jié)果如表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大小下的平均響應(yīng)時(shí)間

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中數(shù)據(jù)可以看到，在C-CMT容量不變時(shí)，隨著S-CMT容量的增大，S-CMT與C-CMT的命中率都在提高，H-CMT的命中率在下降，但變化幅度都不大.從命中率大小來(lái)看，H-CMT的命中率最高，S-CMT次之，C-CMT最少，這說(shuō)明H-CMT中存儲(chǔ)訪問(wèn)頻率較高的映射項(xiàng)，而C-CMT中存儲(chǔ)的映射項(xiàng)訪問(wèn)頻率較低.

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

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

在H-CMT為28 KB，S-CMT為16 KB，C-CMT為20 KB的緩存空間配置下，我們研究了C-CMT中的閾值大小配置問(wèn)題.我們?cè)O(shè)計(jì)了一組仿真實(shí)驗(yàn)，在實(shí)驗(yàn)中閾值大小依次取0，100，300，512.閾值取0表示C-CMT滿時(shí)，選擇包含最多映射項(xiàng)的簇進(jìn)行剔除；閾值取512表示C-CMT滿時(shí)，選擇最近最少訪問(wèn)的簇進(jìn)行剔除.仿真Trace選擇具有代表性的Financial1，仿真結(jié)果如圖5所示.從圖5可以看到，隨著閾值的增大，F(xiàn)inancial1的平均響應(yīng)時(shí)間先減少后增大，當(dāng)閾值取100時(shí)整體性能達(dá)到最優(yōu).另外，其他5個(gè)Trace也有相似的結(jié)果，因此，后續(xù)實(shí)驗(yàn)中我們?nèi)-CMT的閾值為100.

Fig. 5 Average response time of Financial1 under different threshold value of C-CMT圖5 在C-CMT不同預(yù)閾值下Financial1的平均響應(yīng)時(shí)間

3) S-CMT的預(yù)取映射項(xiàng)個(gè)數(shù)

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的預(yù)取映射項(xiàng)個(gè)數(shù)設(shè)置問(wèn)題.我們?cè)O(shè)計(jì)了一組仿真實(shí)驗(yàn)，在實(shí)驗(yàn)中映射項(xiàng)預(yù)取個(gè)數(shù)依次取4，8，16，32，64，128，仿真Trace選擇具有代表性的Financial1，性能指標(biāo)選擇平均響應(yīng)時(shí)間，仿真結(jié)果如圖6所示.從圖6可以看出，隨著預(yù)取映射項(xiàng)個(gè)數(shù)的增加，平均響應(yīng)時(shí)間先減少后增大，當(dāng)預(yù)取映射項(xiàng)個(gè)數(shù)為32時(shí)，平均響應(yīng)時(shí)間為最小.這說(shuō)明，適當(dāng)?shù)卦黾宇A(yù)取映射項(xiàng)個(gè)數(shù)能有效降低SSD平均響應(yīng)時(shí)間整體性能.此外，其他5個(gè)Trace也有相似的結(jié)果.因此，S-CMT預(yù)取映射項(xiàng)個(gè)數(shù)設(shè)置為32.

Fig. 6 Average response time of Financial1 under different numbers of prefetching map entries of S-CMT圖6 在S-CMT不同預(yù)取映射項(xiàng)個(gè)數(shù)下Financial1的平均響應(yīng)時(shí)間

3.3 CPFTL與SDFTL,DFTL的性能對(duì)比分析

1) 總體緩存命中率比較

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

2) 地址轉(zhuǎn)換頁(yè)操作次數(shù)比較

CPFTL，SDFTL，DFTL都采用頁(yè)級(jí)地址映射機(jī)制，緩存未命中會(huì)造成額外的轉(zhuǎn)換頁(yè)讀寫(xiě)操作開(kāi)銷(xiāo)，因此，地址轉(zhuǎn)換頁(yè)的操作次數(shù)能體現(xiàn)CPFTL緩存機(jī)制的效果.在不同Trace下，圖8給出的是CPFTL，SDFTL，DFTL的地址轉(zhuǎn)換頁(yè)操作次數(shù)比較.為方便比較，將CPFTL，SDFTL，DFTL的地址轉(zhuǎn)換頁(yè)操作次數(shù)進(jìn)行歸一化處理.實(shí)驗(yàn)結(jié)果表明，對(duì)于不同的負(fù)載類(lèi)型，CPFTL的地址轉(zhuǎn)換頁(yè)操作次數(shù)都優(yōu)于SDFTL和DFTL，平均有50.62%和82.87%的改善，顯著地減少了地址轉(zhuǎn)換頁(yè)的讀寫(xiě)操作次數(shù).

3) 平均響應(yīng)時(shí)間和塊擦除次數(shù)比較

系統(tǒng)的平均響應(yīng)時(shí)間和塊擦除次數(shù)是衡量閃存存儲(chǔ)性能的重要指標(biāo).在不同Trace下，圖9給出的是CPFTL，SDFTL，DFTL的平均響應(yīng)時(shí)間和閃存擦除次數(shù)比較.為方便比較，將CPFTL，SDFTL，DFTL的平均響應(yīng)時(shí)間和塊擦除次數(shù)進(jìn)行歸一化處理.實(shí)驗(yàn)結(jié)果表明，對(duì)于不同的負(fù)載類(lèi)型，CPFTL的平均響應(yīng)時(shí)間和閃存擦除次數(shù)都優(yōu)于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下地址轉(zhuǎn)換頁(yè)操作次數(shù)

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

4 結(jié)束語(yǔ)

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

[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)(陸游游, 舒繼武. 閃存存儲(chǔ)系統(tǒng)綜述[J]. 計(jì)算機(jī)研究與發(fā)展, 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: 一種基于垃圾回收感知的固態(tài)盤(pán)陣列[J]. 計(jì)算機(jī)研究與發(fā)展, 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)(王江濤, 賴(lài)文豫, 孟小峰. 閃存數(shù)據(jù)庫(kù)： 現(xiàn)狀、 技術(shù)與展望[J]. 計(jì)算機(jī)學(xué)報(bào), 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)(陳金忠, 姚念民, 蔡紹濱,等. 基于頁(yè)面寫(xiě)相關(guān)的閃存轉(zhuǎn)換層策略[J]. 通信學(xué)報(bào), 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)(姚英彪, 沈佐兵. 基于連續(xù)緩存和二級(jí)緩存的 DFTL 改進(jìn)算法[J]. 計(jì)算機(jī)研究與發(fā)展, 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: 一種面向企業(yè)級(jí)應(yīng)用 的高效閃存轉(zhuǎn)換層處理策略[J]. 計(jì)算機(jī)研究與發(fā)展, 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： 支持預(yù)測(cè)機(jī)制的負(fù)載自適應(yīng)閃存轉(zhuǎn)換層算法[J]. 計(jì)算機(jī)工程與科學(xué), 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)(張琦, 王林章, 張?zhí)? 等. 一種優(yōu)化的閃存地址映射方法[J]. 軟件學(xué)報(bào), 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

國(guó)家自然科學(xué)基金項(xiàng)目(61100044)；浙江省科技創(chuàng)新基金項(xiàng)目(2013TD03)；浙江省科技計(jì)劃資助項(xiàng)目(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