0. 引 言

現(xiàn)在越來越多的筆記本電腦、智能手機(jī)、固態(tài)硬盤等新型電子設(shè)備開始裝備NAND閃存，憑借特有的存儲(chǔ)方式和超高的穩(wěn)定性、可靠性，NAND閃存得到越來越多廠商的青睞.配備NAND閃存的固態(tài)硬盤也憑借諸多優(yōu)勢逐漸取代傳統(tǒng)機(jī)械硬盤[1].

采用NAND閃存作為存儲(chǔ)裝置的固態(tài)硬盤沒有采用像機(jī)械硬盤那樣的復(fù)雜精密結(jié)構(gòu)，讀取數(shù)據(jù)不需要尋道時(shí)間，并且也有獨(dú)特的寫入方式，所以能夠獲得比較快的讀取和寫入速度.并且由于NAND閃存體積小，接口應(yīng)用廣泛，適應(yīng)各種結(jié)構(gòu)形式，所以可以被手機(jī)、筆記本電腦等精密設(shè)備采用[2].然而NAND閃存存儲(chǔ)器使用電子管來存儲(chǔ)，重復(fù)寫入擦除數(shù)據(jù)極易導(dǎo)致?lián)p壞，其物理塊僅能承受幾千次的擦寫操作.要想廣泛的應(yīng)用NAND閃存就需要采用合適的平均每個(gè)物理塊磨損的機(jī)制，也就是損耗均衡機(jī)制，以此才能延長閃存的使用壽命.

[[228943]]

在1994年，PCMCIA(個(gè)人計(jì)算機(jī)內(nèi)存卡國際協(xié)會(huì))提出了Flash轉(zhuǎn)換層(FTL)的概念，F(xiàn)AT文件系統(tǒng)用于NAND Flash時(shí)，是由控制器通過管理NAND Flash建立一個(gè)邏輯的FAT文件系統(tǒng)，供上層應(yīng)用調(diào)用，同時(shí)它也可以高效的執(zhí)行損耗均衡[3].實(shí)現(xiàn)閃存損耗均衡的算法按照類型分為：動(dòng)態(tài)損耗均衡和靜態(tài)損耗均衡[4].Ban等[3]針對(duì)靜態(tài)均衡算法的觸發(fā)機(jī)制進(jìn)行了研究，并提出兩種觸發(fā)機(jī)制：確定性觸發(fā)機(jī)制和隨機(jī)性觸發(fā)機(jī)制.Yared Hailu Gudeta等[5]提出了基于概率的靜態(tài)損耗平均算法.在每個(gè)狀態(tài)下，磨損平均分布使用標(biāo)準(zhǔn)偏差來計(jì)算，以確定其是否超過閾.如果它超過閾值，則在所有塊中維持損耗平衡通過將熱塊與冷塊交換在閃存中.Lee等[6]在靜態(tài)損耗均衡算法上進(jìn)行了研究，該算法會(huì)在系統(tǒng)初始化時(shí)將閃存存儲(chǔ)空間劃分成若干組，從開始***次更新之后就記錄每一個(gè)組的擦寫次數(shù).到達(dá)損耗均衡的觸發(fā)條件時(shí)統(tǒng)計(jì)高于平均擦寫次數(shù)的組及組內(nèi)的物理塊，然后將這些塊的數(shù)據(jù)搬運(yùn)至空塊，再更新地址映像表.

邢春波[7]提出一種混合損耗均衡算法(HWL)，該法也是在系統(tǒng)初始化時(shí)將閃存空間分塊，每塊的擦寫次數(shù)由單獨(dú)分配的一個(gè)字節(jié)的存儲(chǔ)空間記錄擦寫情況，并采用一個(gè)數(shù)組來維護(hù)所有的塊的擦寫情況.該算法統(tǒng)計(jì)每一個(gè)系統(tǒng)更新周期內(nèi)的各塊擦寫情況， HWL算法是目前應(yīng)用最廣發(fā)的算法之一，本文也是建立在該算法的基礎(chǔ)上進(jìn)行改進(jìn)而來.

本文根據(jù)閃存的物理塊在使用過程中擦寫的次數(shù)，對(duì)閃存數(shù)據(jù)塊進(jìn)行分類并給出相應(yīng)的判斷標(biāo)準(zhǔn)，同時(shí)引入與損耗均衡算法密切相關(guān)的閥值的概念；針對(duì)損耗均衡算法不能隨著存儲(chǔ)需求作調(diào)整的缺陷，給出根據(jù)數(shù)據(jù)塊擦寫次數(shù)的標(biāo)準(zhǔn)差動(dòng)態(tài)調(diào)整閥值的算法；結(jié)合傳統(tǒng)的動(dòng)態(tài)損耗均衡算法和靜態(tài)損耗均衡算法，給出損耗均衡算法的評(píng)價(jià)標(biāo)準(zhǔn)，將靜態(tài)損耗均衡算法和動(dòng)態(tài)損耗均衡算法兩者結(jié)合設(shè)計(jì)出新的均衡損耗算法；根據(jù)需求設(shè)計(jì)了評(píng)估損耗均衡算法效果的測試實(shí)驗(yàn)，對(duì)損耗均衡算法的效果進(jìn)行了實(shí)驗(yàn)測試.實(shí)驗(yàn)結(jié)果表明本文提出的改進(jìn)算法對(duì)減小閃存存儲(chǔ)器擦寫的不均衡性有很好的效果.

1 NAND閃存損耗均衡機(jī)制及策略

1.1 NAND閃存的工作原理

NAND是一種計(jì)算機(jī)閃存設(shè)備.隨著人們持續(xù)不斷追求功耗更低、重量更輕和性能更佳的產(chǎn)品，這證明了NAND***吸引力.閃存存儲(chǔ)器按照存儲(chǔ)單元的存儲(chǔ)控制方式可分為單層單元SLC和多層單元MLC控制方式.單層單元SLC控制方式是依靠MOS管疊柵上不同的電荷量來區(qū)分0與1兩種狀態(tài)，多個(gè)MOS管組成疊柵成為一個(gè)存儲(chǔ)單元.相對(duì)應(yīng)的多層單元MLC控制方式由單層單元SLC控制方式改進(jìn)而來，它的一個(gè)疊柵可以識(shí)別四種存儲(chǔ)狀態(tài)：00、01、10、11.但同時(shí)由于該種MOS管需要去識(shí)別多種電荷量，然而這會(huì)造成物理性能不穩(wěn)定，導(dǎo)致這種閃存的壽命較少.正是因?yàn)檫@種問題，損耗均衡機(jī)制的重要性被進(jìn)一步提高，為了保證多層單元MLC控制方式閃存的使用壽命，必須在文件系統(tǒng)中使用損耗均衡和機(jī)制.

1.2 損耗均衡評(píng)價(jià)指標(biāo)

損耗均衡(wear leveling)[8]是指用來延長固態(tài)存儲(chǔ)設(shè)備使用壽命的過程.閃存損耗均衡技術(shù)的設(shè)計(jì)目標(biāo)是：在盡可能減少閃存中所有塊的總擦除次數(shù)的前提下，盡可能使閃存中的每個(gè)塊擦除次數(shù)趨向一致或在一定范圍內(nèi).根據(jù)統(tǒng)計(jì)學(xué)的知識(shí)我們可以知道平均值描述了一個(gè)樣本的平均水平，標(biāo)準(zhǔn)差能反映一個(gè)數(shù)據(jù)集的離散程度.根據(jù)這個(gè)設(shè)計(jì)目標(biāo)提出衡量閃存損耗均衡度的兩個(gè)指標(biāo)：平均擦除次數(shù)擦除次數(shù)標(biāo)準(zhǔn)偏差Deviation,簡寫為Dev.

公式(1)、(2)中E(i)表示第i塊的擦除次數(shù)，n為閃存的總塊數(shù).

綜合以上因素可以知道，一個(gè)較好的閃存系統(tǒng)損耗均衡策略可以使熱數(shù)據(jù)和冷數(shù)據(jù)的遷移次數(shù)盡可能多，同時(shí)總的物理塊擦除次數(shù)的平均值越小，這樣閃存的使用壽命大大延長.另外物理塊的擦除次數(shù)的標(biāo)準(zhǔn)差越小，表明每一個(gè)物理塊的擦出次數(shù)偏離平均擦除次數(shù)較少，損耗均衡機(jī)制的執(zhí)行效果較好.相反，損耗均衡機(jī)制的執(zhí)行效果較差.

1.3 損耗均衡策略

1)動(dòng)態(tài)損耗均衡策略

動(dòng)態(tài)損耗均衡算法[9]主要原理是：先將所有的閃存物理塊鏈接到一個(gè)動(dòng)態(tài)維護(hù)的表格，在表格中將各物理塊的擦除次數(shù)從大到小進(jìn)行排序.當(dāng)數(shù)據(jù)更新時(shí)，要求數(shù)據(jù)寫入到表格***的物理塊，也就是擦除次數(shù)最小的物理塊，然后再按照擦寫次數(shù)進(jìn)行排序.按照這樣的方法數(shù)據(jù)永遠(yuǎn)都是寫入到擦除次數(shù)最小的物理塊，使得閃存的各塊均得到同樣的磨損狀況.

2)靜態(tài)損耗均衡策略

靜態(tài)損耗均衡算法在動(dòng)態(tài)損耗均衡算法的基礎(chǔ)上改進(jìn)而來，考慮到動(dòng)態(tài)損耗均衡算法中一直優(yōu)先將數(shù)據(jù)寫入到擦出次數(shù)較少的物理塊中，原先儲(chǔ)備的更新較少的冷數(shù)據(jù)就會(huì)一直占據(jù)該物理塊，得不到釋放.所以靜態(tài)損耗均衡算法考慮了冷數(shù)據(jù)的搬運(yùn)，使得整個(gè)閃存存儲(chǔ)空間都在不斷的進(jìn)行均衡磨損.靜態(tài)損耗均衡算法將焦點(diǎn)放在冷數(shù)據(jù)上，預(yù)先設(shè)置擦寫次數(shù)的閥值，采用遍歷各塊的方法統(tǒng)計(jì)得出更新頻率低于閥值的方法，篩選出冷數(shù)據(jù)塊，然后將數(shù)據(jù)搬遷至擦出次數(shù)較多的物理塊中.用同樣的方法篩選出熱數(shù)據(jù)塊，將熱數(shù)據(jù)塊搬遷至擦除次數(shù)較少的物理塊中.通過這種方法，閃存中的各物理塊的擦除次數(shù)比較均衡，并且隨著靜態(tài)均衡機(jī)制的不斷觸發(fā)，熱數(shù)據(jù)塊的擦出次數(shù)增長十分緩慢，冷數(shù)據(jù)塊的擦出次數(shù)有一定的提高，從而是十分有效的損耗均衡算法.

2 靜態(tài)均衡算法設(shè)計(jì)

本文的靜態(tài)損耗均衡算法是將現(xiàn)有的動(dòng)態(tài)均衡算法與靜態(tài)算法相結(jié)合，設(shè)計(jì)出一種更加完善的算法流程.靜態(tài)損耗均衡算法的設(shè)計(jì)基本原理在前文介紹過，為此定義擦除次數(shù)最多為Nmax，擦除次數(shù)最少為Nmin，兩者差值為Th，則需要研究的問題[10]的表述為：

這里式(4)中的Th就是本文所研究的靜態(tài)損耗均衡算法的核心，即要選擇恰當(dāng)?shù)拈y值Th，使得物理塊的擦除次數(shù)上下限相差不會(huì)太大.同時(shí)又要滿足盡可能小的平均值和標(biāo)準(zhǔn)差.

2.1 觸發(fā)條件的優(yōu)化

確定性觸發(fā)的難點(diǎn)在于難以找到合適的系統(tǒng)更新次數(shù)，隨機(jī)性觸發(fā)只是用于系統(tǒng)更新頻率較高的情況[11].

為此本文設(shè)計(jì)了一種可以動(dòng)態(tài)選擇觸發(fā)機(jī)制的算法，將確定性觸發(fā)和隨機(jī)性觸發(fā)相結(jié)合，該算法會(huì)統(tǒng)計(jì)系統(tǒng)的更新頻率.如果更新頻率較高則選擇隨機(jī)觸發(fā)條件，如果更新頻率較低則選擇確定性觸發(fā)條件.參考損耗均衡機(jī)制的評(píng)價(jià)標(biāo)準(zhǔn)，選擇系統(tǒng)更新次數(shù)的均值當(dāng)做判別條件.流程圖如圖1所示.

圖1 優(yōu)化的觸發(fā)條件流程圖

Fig.1 Flow chart of optimal trigger condition

2.2 閥值確定數(shù)據(jù)塊的狀態(tài)

數(shù)據(jù)塊的磨損狀態(tài)由該塊的擦寫次數(shù)在數(shù)據(jù)擦寫中所占的比例決定，即

式中wi表示該塊的磨損程度，ei表示該塊在本次系統(tǒng)更新中的擦寫次數(shù)，a0是本次系統(tǒng)更新總的擦寫次數(shù).

在磨損均衡過程中維護(hù)了一個(gè)磨損信息表，表中為每個(gè)物理塊分配一個(gè)字節(jié)的空間記錄磨損狀態(tài)wi.如果wi達(dá)到閥值whigh就將該塊定義為熱數(shù)據(jù)塊，同理低于閥值wlow就將該塊定義為冷數(shù)據(jù)塊.

2.3 算法流程

由以上結(jié)論可知，要想解決損耗均衡的問題，就必須在盡可能小的影響性能的條件下使擦寫任務(wù)均勻的分布在每個(gè)數(shù)據(jù)塊[12].本文在解決這個(gè)問題時(shí)候，通過對(duì)以往動(dòng)態(tài)和靜態(tài)算法的研究下，就此設(shè)計(jì)了動(dòng)態(tài)靜態(tài)算法相結(jié)合的NAND FLASH閃存損耗均衡的算法.

一個(gè)完整的靜態(tài)損耗均衡流程為：在系統(tǒng)更新操作每過一定的擦寫次數(shù)n時(shí)啟動(dòng)靜態(tài)損耗均衡機(jī)制，首先遍歷所有參與擦寫的數(shù)據(jù)塊，計(jì)算得出數(shù)據(jù)塊的磨損狀態(tài).按照磨損狀態(tài)從低到高排序，達(dá)到閥值whigh就將該塊定義為熱數(shù)據(jù)塊，低于閥值wlow就定義為冷數(shù)據(jù)塊.然后將熱數(shù)據(jù)塊中的有效數(shù)據(jù)搬遷至新的空塊或者磨損狀態(tài)wi***塊，將冷數(shù)據(jù)塊搬遷到原先的最熱數(shù)據(jù)塊，重排后依次進(jìn)行，將搬遷后的數(shù)據(jù)塊重新鏈接到文件系統(tǒng).本次損耗均衡結(jié)束后計(jì)算沒有超出閥值的數(shù)據(jù)塊的擦除次數(shù)標(biāo)準(zhǔn)偏差，如果過高則標(biāo)記超出平均擦除次數(shù)一定值的塊為熱數(shù)據(jù)塊，并參與下一次系統(tǒng)更新.這樣熱數(shù)據(jù)塊就會(huì)不斷被搬遷新的物理塊，不會(huì)只在部分塊內(nèi)擦寫，有效降低了閃存數(shù)據(jù)塊的磨損.算法流程如圖2，圖3所示.

圖2 完整的均衡損耗流程圖一

Fig.2 Complete balanced loss flow diagramⅠ

圖3 完整的均衡損耗流程圖二

Fig.3 Complete balanced loss flow diagramⅡ

3 仿真測試

3.1 實(shí)驗(yàn)平臺(tái)搭建

為了測試本文設(shè)計(jì)的損耗均衡算法的效果，借助SSD Sim搭建測試平臺(tái).它可以在普通的計(jì)算機(jī)平臺(tái)上模擬NAND閃存的存儲(chǔ)狀況，用戶可以在SSD Sim軟件中設(shè)置存儲(chǔ)容量、存儲(chǔ)信道、閃存塊大小等參數(shù)，根據(jù)用戶需求可以在沒有閃存硬件的支持下模擬NAND閃存的使用情況.

為了直觀的對(duì)比損耗均衡算法的效果，本文設(shè)計(jì)了兩個(gè)NAND閃存，每個(gè)閃存分配4個(gè)閃存芯片，它們之間以并行方式連接，其中閃存1采用傳統(tǒng)的靜態(tài)損耗均衡算法[13](HWL算法);閃存2采用本文改進(jìn)后的損耗均衡算法，兩個(gè)閃存都寫入同樣的1×106次數(shù)據(jù)量寫入請(qǐng)求.兩個(gè)閃存的其他詳細(xì)配置如表1所示.

表1閃存配置表

Table1Flashconfigurationtable

3.2 測試內(nèi)容及結(jié)果分析

本節(jié)比較了分別采用改進(jìn)前和改進(jìn)后的損耗均衡算法的效果.主要通過對(duì)比兩種磨損狀態(tài)閥值w，系統(tǒng)更新次數(shù)n和靜態(tài)損耗周期M三個(gè)因素對(duì)閃存存儲(chǔ)的磨損均衡性能的影響，評(píng)價(jià)的指標(biāo)用一個(gè)周期內(nèi)的擦除次數(shù)標(biāo)準(zhǔn)偏差來描述.

1)為研究磨損狀態(tài)閥值上限對(duì)閃存存儲(chǔ)的磨損均衡性能的影響，設(shè)置HWL算法下w=1.2%和w=0.8%兩種情況下記錄隨著寫入請(qǐng)求的增加，物理塊擦除次數(shù)標(biāo)準(zhǔn)差的變化情況.

從圖4、圖5可以看出相比HWL算法，改進(jìn)后的靜態(tài)損耗均衡算法的損耗均衡效果更好一些.隨著寫入請(qǐng)求不斷增加，兩者的標(biāo)準(zhǔn)差都是穩(wěn)定增長.這說明隨著寫入請(qǐng)求的不斷增多在靜態(tài)損耗均衡機(jī)制的控制下標(biāo)準(zhǔn)差的增長趨于穩(wěn)定，趨于穩(wěn)定時(shí)改進(jìn)后的擦寫次數(shù)的標(biāo)準(zhǔn)差比HWL算法小約16.4%，這說明改進(jìn)后的閥值使得損耗均衡效果更好.

2)通過物理塊擦寫次數(shù)的標(biāo)準(zhǔn)差變化曲線，比較改進(jìn)之前和改進(jìn)之后的靜態(tài)損耗均衡的周期對(duì)靜態(tài)損耗均衡效果的影響.HWL算法是采用固定周期，改進(jìn)后的算法采用變周期.從圖中可以明顯看出改進(jìn)后的靜態(tài)損耗均衡算法效果顯著：從寫入請(qǐng)求達(dá)到2.2×105次時(shí)，兩者的擦寫次數(shù)標(biāo)準(zhǔn)差均達(dá)到***.但是隨后HWL算法的擦寫次數(shù)標(biāo)準(zhǔn)差繼續(xù)增長，直到寫入請(qǐng)求達(dá)到7.4×105時(shí)才有下降的趨勢；然而改進(jìn)后的擦寫次數(shù)標(biāo)準(zhǔn)差開始下降，并最終穩(wěn)定到10×105左右.由于改進(jìn)后的算法采用了動(dòng)態(tài)的周期選擇的方法，相比HWL的固定周期能更好地適應(yīng)閃存靜態(tài)損耗均衡的需求.

圖4 磨損狀態(tài)閥值上限對(duì)閃存存儲(chǔ)的 磨損均衡性能的影響

Fig.4 Effect of wear state threshold on wear equalization performance of flash

圖5 靜態(tài)損耗均衡的周期對(duì)靜態(tài) 損耗均衡效果影響的對(duì)比分析圖

Fig.5 Comparison and analysis of the influence of static loss equalization cycle on static loss equalization

同時(shí)本文選取了另外一個(gè)M=10的變化曲線對(duì)比觀察，發(fā)現(xiàn)即使是將靜態(tài)損耗及均衡周期設(shè)置的比較短，損耗均衡的效果仍然不理想.

4 結(jié) 論

對(duì)目前較流行的HWL損耗均衡算法進(jìn)行優(yōu)化.重新定義了數(shù)據(jù)塊的冷熱屬性，并以高低閥值作為熱數(shù)據(jù)和冷數(shù)據(jù)的判定條件；對(duì)觸發(fā)機(jī)制進(jìn)行優(yōu)化和將現(xiàn)有的靜態(tài)損耗均衡策略與動(dòng)態(tài)損耗均衡策略相結(jié)合的優(yōu)化策略.通過SSD Sim軟件完成了對(duì)比測試，實(shí)驗(yàn)證明改進(jìn)后的損耗均衡算法有效的降低了物理塊擦除次數(shù)的標(biāo)準(zhǔn)差，使得損耗均衡效果得到提高.