0. 引 言

現在越來越多的筆記本電腦、智能手機、固態硬盤等新型電子設備開始裝備NAND閃存，憑借特有的存儲方式和超高的穩定性、可靠性，NAND閃存得到越來越多廠商的青睞.配備NAND閃存的固態硬盤也憑借諸多優勢逐漸取代傳統機械硬盤[1].

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

[[228943]]

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

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

本文根據閃存的物理塊在使用過程中擦寫的次數，對閃存數據塊進行分類并給出相應的判斷標準，同時引入與損耗均衡算法密切相關的閥值的概念；針對損耗均衡算法不能隨著存儲需求作調整的缺陷，給出根據數據塊擦寫次數的標準差動態調整閥值的算法；結合傳統的動態損耗均衡算法和靜態損耗均衡算法，給出損耗均衡算法的評價標準，將靜態損耗均衡算法和動態損耗均衡算法兩者結合設計出新的均衡損耗算法；根據需求設計了評估損耗均衡算法效果的測試實驗，對損耗均衡算法的效果進行了實驗測試.實驗結果表明本文提出的改進算法對減小閃存存儲器擦寫的不均衡性有很好的效果.

1 NAND閃存損耗均衡機制及策略

1.1 NAND閃存的工作原理

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

1.2 損耗均衡評價指標

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

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

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

1.3 損耗均衡策略

1)動態損耗均衡策略

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

2)靜態損耗均衡策略

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

2 靜態均衡算法設計

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

這里式(4)中的Th就是本文所研究的靜態損耗均衡算法的核心，即要選擇恰當的閥值Th，使得物理塊的擦除次數上下限相差不會太大.同時又要滿足盡可能小的平均值和標準差.

2.1 觸發條件的優化

確定性觸發的難點在于難以找到合適的系統更新次數，隨機性觸發只是用于系統更新頻率較高的情況[11].

為此本文設計了一種可以動態選擇觸發機制的算法，將確定性觸發和隨機性觸發相結合，該算法會統計系統的更新頻率.如果更新頻率較高則選擇隨機觸發條件，如果更新頻率較低則選擇確定性觸發條件.參考損耗均衡機制的評價標準，選擇系統更新次數的均值當做判別條件.流程圖如圖1所示.

圖1 優化的觸發條件流程圖

Fig.1 Flow chart of optimal trigger condition

2.2 閥值確定數據塊的狀態

數據塊的磨損狀態由該塊的擦寫次數在數據擦寫中所占的比例決定，即

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

在磨損均衡過程中維護了一個磨損信息表，表中為每個物理塊分配一個字節的空間記錄磨損狀態wi.如果wi達到閥值whigh就將該塊定義為熱數據塊，同理低于閥值wlow就將該塊定義為冷數據塊.

2.3 算法流程

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

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

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

Fig.2 Complete balanced loss flow diagramⅠ

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

Fig.3 Complete balanced loss flow diagramⅡ

3 仿真測試

3.1 實驗平臺搭建

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

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

表1閃存配置表

Table1Flashconfigurationtable

3.2 測試內容及結果分析

本節比較了分別采用改進前和改進后的損耗均衡算法的效果.主要通過對比兩種磨損狀態閥值w，系統更新次數n和靜態損耗周期M三個因素對閃存存儲的磨損均衡性能的影響，評價的指標用一個周期內的擦除次數標準偏差來描述.

1)為研究磨損狀態閥值上限對閃存存儲的磨損均衡性能的影響，設置HWL算法下w=1.2%和w=0.8%兩種情況下記錄隨著寫入請求的增加，物理塊擦除次數標準差的變化情況.

從圖4、圖5可以看出相比HWL算法，改進后的靜態損耗均衡算法的損耗均衡效果更好一些.隨著寫入請求不斷增加，兩者的標準差都是穩定增長.這說明隨著寫入請求的不斷增多在靜態損耗均衡機制的控制下標準差的增長趨于穩定，趨于穩定時改進后的擦寫次數的標準差比HWL算法小約16.4%，這說明改進后的閥值使得損耗均衡效果更好.

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

圖4 磨損狀態閥值上限對閃存存儲的 磨損均衡性能的影響

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

圖5 靜態損耗均衡的周期對靜態 損耗均衡效果影響的對比分析圖

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

同時本文選取了另外一個M=10的變化曲線對比觀察，發現即使是將靜態損耗及均衡周期設置的比較短，損耗均衡的效果仍然不理想.

4 結 論

對目前較流行的HWL損耗均衡算法進行優化.重新定義了數據塊的冷熱屬性，并以高低閥值作為熱數據和冷數據的判定條件；對觸發機制進行優化和將現有的靜態損耗均衡策略與動態損耗均衡策略相結合的優化策略.通過SSD Sim軟件完成了對比測試，實驗證明改進后的損耗均衡算法有效的降低了物理塊擦除次數的標準差，使得損耗均衡效果得到提高.