關於NAND快閃記憶體損耗均衡演算法的優化

0. 引 言

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

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

在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軟體完成了對比測試，實驗證明改進後的損耗均衡演算法有效的降低了物理塊擦除次數的標準差，使得損耗均衡效果得到提高.

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！