閃存循環位圖的損耗均衡機制研究

劉智朋，羅洪元，陽小珊，邱全偉，鄭 良

(1.中國電子科技集團公司第十五研究所國家電子計算機質量監督檢驗中心，北京100083;2.中國傳媒大學存儲實驗室，北京100024)

0 引言

由于閃存 (flash memory)具有體積小、能耗低、零噪音、抗震動等優勢，因此得到了廣泛應用。在閃存中，頁是數據讀寫的基本單位，塊是數據擦除的基本單位。對于頁來說，只有當包含它的整個物理塊被擦除時，才可以重新寫入。此外，閃存的物理塊對擦除次數也有限制。對于SLC(single level cell)型閃存，在現有技術下的擦除次數為10萬次，而MLC(multi-level cell)型閃存更少，一般為1 萬次［1］。

為了將擦除寫入操作平均分配到閃存中的物理塊中，提高物理塊的使用率，延長閃存的使用壽命，提出了損耗均衡機制。損耗均衡機制能夠顯著提高物理塊的利用率，最終延長閃存設備的壽命，對閃存的設計和實際應用都具有重要指導意義。現有的閃存設備使用的大都是動態和靜態兩種損耗均衡機制，但由于它們在自身運行效率和提高塊利用率方面的不足，因此如何彌補和改進原有機制就變得亟待解決了。

1 相關研究

1.1 閃存的壽命與損耗均衡機制的數學關系

閃存中的物理塊的擦除次數決定著閃存壽命，我們通過如下的數學公式進行定量的分析

式中:Lifetime——閃存的壽命，單位是年。Cap——閃存的存儲容量，常見的 NAND Flash［2］容量為 8～128MB。EC(erase cycle)——閃存物理塊的擦除次數上限，或者說是擦除次數的期望值。Usa_Per-_D［3］是每天進行擦除寫入的存儲空間，那么Usa_P-er_D*365是一年進行擦除寫入的存儲空間的大小。Rate是在閃存中寫入數據時，需要寫空間與實際寫空間的比值，全稱為Write Amplification Rate［4］(寫擴大倍數)，在閃存上進行連續寫操作時，其Rate維持在1.1左右。

Util是閃存在使用過程時所有物理塊實際擦除次數之和與期望擦除次數之和的百分比，即

式中:Ri——PBA i(Physical Block Address)的實際擦除次數，Rsum——所有物理塊實際擦除次數之和;Ei——物理塊PBA i的期望擦除次數［5］，Esum——所有物理塊的期望擦除次數之和;n——閃存中物理塊總量。由于特定型號、容量和應用的閃存，Cap、EC、Usa_Per_D和Rate都是不變的，所以根據式 (1)可知閃存的壽命和Util成正比。在式(2)中Esum是固定不變的，所以Util的值由Rsum決定。假設某閃存設備中，有25%的內容為動態內容 (經常被更新的數據)，75%為靜態內容 (很少被更新的數據)。若不使用損耗均衡機制，系統會集中使用20%～30%的塊進行數據寫入操作，剩下70%～80%塊的利用率就會降低。由于塊的損耗不均衡關系，當20%～30%塊的擦除次數達到上限時，70%～80%的塊的擦除次數卻很少，此時Rsum相應的就會很低。相反，如果在閃存中使用損耗均衡機制，那么Rsum就會增多，進而增大 Util的值，使塊的利用率得到顯著提高。

隨著閃存擦除寫入利用率的提高，閃存的壽命也會延長。由此可見，損耗均衡機制對于提高閃存的壽命具有重大意義。

1.2 損耗均衡技術現狀與分析

現在主流的損耗均衡分為動態損耗均衡［6］和靜態損耗均衡［6］兩種。

動態損耗均衡機制是在所有空閑塊中尋找擦除次數最小的進行寫入，從而保證數據的擦除寫入被均勻地分布到閃存的所有塊中。動態損耗均衡主要回收動態數據塊 (經常被更新的塊)，而那些靜態數據塊 (很少被更新的塊)，在動態損耗均衡過程中卻沒有被回收，因而造成動態數據塊和靜態數據塊的擦除次數相差很大。因此，為了獲得更好的損耗均衡，閃存中引入了靜態損耗均衡機制。它會強制搬移靜態數據到動態數據塊中去，在更大程度上增加閃存的使用壽命和可靠性。然而，系統要花費大量的時間和資源尋找擦除次數最多和最少的塊，而且在特定的時間內不能保證靜態數據塊的擦除。為了進一步提高閃存的損耗均衡的效果，研究和設計了循環位圖損耗均衡機制。

本文中的損耗均衡機制分為動態寫入和靜態回收兩個階段。動態寫入階段利用動態控制指針追蹤到空閑物理塊對數據進行寫入。靜態回收階段首先利用靜態控制指針追蹤含有靜態數據的物理塊 (記為PBA1)，然后找到活動頻繁的物理塊 (記為PBA2)，將PBA1中的內容復制到PBA2中，從而減少PBA2的損耗。新的損耗均衡機制的設計不僅可以免除尋找最大和最小擦除次數塊所帶來的時間和性能消耗，而且可以將擦除寫入更加平均地分配到閃存物理塊中，延長了閃存的壽命，使損耗均衡取得令人滿意的效果。

2 基于循環位圖的損耗均衡機制的設計

2.1 整體結構

本文提出的損耗均衡設計所基于的系統架構如圖1所示。

圖1 系統架構

應用系統通過系統接口向閃存設備發送讀寫操作命令，微處理器 (CPU)接收命令后通過閃存接口對閃存進行操作［7］。基于循環位圖的損耗均衡機制主要是在控制器中加入一個管理單元。管理單元包括熱點列表、循環位圖、關系記錄表、地址映射表和擦除計數表。這些圖表相互配合，保證均衡損耗機制的實現。

管理單元中的圖表存儲在固定的閃存塊中。在閃存設備接通電源時，它們從閃存塊載入靜態隨機存儲器 (Static RAM，SRAM)中，并在周期時期段或者斷電時重新在閃存塊中進行備份。

2.2 FTL

在傳統的損耗均衡機制中，FTL［8］通過地址映射表(mapping address table，MAT)尋找邏輯地址 (logical block address，LBA)到物理地址 (physial block address，PBA)的映射，同時對閃存塊進行擦除計數管理。塊的擦除次數記錄在擦除計數 (erase count table，ECT)中。

此文中的機制，在FTL中添加一個關系記錄表 (relation note table，RNT)，它用來記錄每個邏輯塊和其所對應的多個物理塊之間的連接關系。如圖2所示。

圖2 關系記錄

使用圖2中的PBA2進行簡單說明。PBA2所對應的邏輯塊為LBA0。某時刻當應用系統需要修改LBA0所對應的內容時，控制器就會在已經進行擦除操作的PBA7中記錄更新的內容，然后在BNT中記錄PBA2和PBA7之間的連接關系。當LBA0所對應的內容需要再次修改的時候，控制器就會繼續在已經擦除的PBA10中記錄更新的內容，并同時記錄PBA2、PBA7和PBA10之間的連接關系。這樣，在BNT中就構成了一個由PBA2、PBA7和PBA10組成的物理塊鏈。其中，PBA2記為Block，PBA7和PBA10記為Junior_Block。

2.3 熱點列表

熱點列表［9］(hot list，HL)記錄的是最近頻繁被寫入或者修改的邏輯塊。當控制器完成數據寫入的操作后，HL就會隨之更新。根據物理塊和邏輯塊之間的對應關系，只需要隨時檢驗HL，就可以通過表中的邏輯塊找到擦除次數較多的物理塊。圖3所示的為某時刻閃存的 HL，其中LBA0是活動最頻繁的邏輯塊。

圖3 熱點列表

2.4 循環位圖

循環位圖是使用擦除標志位［10］(erase marked bit，EMB)判斷物理塊的擦除狀態。EMB值為1表示塊已經被擦除，EMB值為0表示塊尚未進行擦除。這些塊按照存儲地址的升序組織，最后一塊指向第一塊。圖4為某時刻閃存的循環位圖。

循環位圖是本機制的核心部分，可通過它找到空閑物理塊和靜態數據塊，進行寫入和擦除操作。

圖4 循環位圖

循環位圖包括兩個指針，分別為動態控制指針 (dynamic control pointer，dcp)和靜態控制指針 (static control pointer，scp)。其中dcp始終指向循環位圖中EMB為1的物理塊即空閑物理塊，而scp始終指向EMB為0的物理塊即靜態數據塊。控制指針依照循環位圖順序查找，直到找到符合要求的物理塊為止;如果查找到位圖尾部，仍舊無法找到，那么跳轉到位圖首部繼續按順序查找，如此循環，直到找到為止。

2.5 機制設計

2.5.1 動態寫入階段

圖5 動態寫入階段流程

如圖5所示，如果控制器接收到外部應用的寫入命令時，就會通過動態控制指針在循環位圖中查找EMB為1的物理塊Target_PBA，然后執行下面的操作:

(1)將數據寫入Target_PBA中;

(2)將相應的物理塊和邏輯塊的映射關系寫入地址映射表和關系記錄表;

(3)更新熱點列表即將物理塊所對應的邏輯塊寫入其中;

(4)循環位圖中動態控制指針對應的物理塊Target_PBA的EMB改為0;同時dcp向前移動到下一個EMB為1的物理塊上。

與動態損耗均衡機制中寫入數據階段相比，此機制不需要尋找擦除次數最小的物理塊，只需要根據動態控制指針找到當前所指向的空閑物理塊。因為指針在循環位圖中移動，所以可以近似地認為物理塊的利用率是大致相等的。

2.5.2 靜態回收階段

對于那些寫入閃存并存儲了相當長一段時間甚至無限期的數據，動態寫入階段無法起作用。此外，在動態寫入階段，空閑物理塊會不斷被消耗，直至閃存中沒有空閑塊提供數據的寫入操作。基于此，本機制提出了靜態回收階段。

圖6為損耗均衡機制靜態回收階段的流程圖。

圖6 靜態回收階段流程

主要流程如下:

(1)在熱點列表中查找活動最頻繁的邏輯塊 (記為Hot_LBA)，通過MAT和RNT找到Hot_LBA

對應的物理塊鏈。此時，物理塊鏈中包含的物理塊是活動較頻繁的物理塊。假設物理塊鏈中有n個物理塊，那么Source_PBA i(i=1，2，…，n)表示物理塊鏈中第i個物理塊;

(2)查找循環位圖中動態控制指針所指向的物理塊(記為Target_PBA);

(3)將物理塊鏈中尾部塊Source_PBA n的內容 (Hot_LBA所對應的最新內容)寫入Target-PBA中，修改MAT和RNT中的對應關系，將循環位圖中Target_PBA的EMB值改為0，位圖中的dcp指向下一個EMB為1的物理塊;

(4)下面的不等式用來判斷物理塊的擦除次數是否大于閃存中物理塊的平均擦除次數

其中Ei表示閃存中第i個物理塊的擦除次數。

如果不等式不成立，那么Source_PBA i需要進行擦除，然后處理下一個物理塊Source_PBA(i+1)，直到物理塊鏈中所有物理塊操作完成。

如果不等式成立，scp所指向的物理塊包含的內容為靜態內容，記為Static_PBA。將Static_PBA中的數據轉移到物理塊Source_PBA i中，然后對其進行擦除操作。這個過程實現了把靜態數據放入活動頻繁的物理塊中;

(5)對于第i+1個物理塊即Source_PBA(i+1)，重復 (4)中的操作，直到物理塊鏈中所有物理塊操作完成。

靜態回收階段流程比較復雜，這里舉例說明。

根據熱點列表查找到活動最頻繁的邏輯塊 LBA0。LBA0對應的物理塊鏈是PBA2、PBA7和PBA10組成的物理塊鏈。此時，動態控制指針 dcp所指向的空閑塊為PBA0，如圖7(a)過程一中所示。

將含有最新更改過的內容的PBA10中的數據寫入PBA0中，PBA0在位圖中的EMB改為0，如圖7(b)過程二中所示。

通過靜態控制指針找到靜態數據塊PBA1。假設PBA2中的擦除次數大于平均擦除次數，那么將PBA1中數據遷移到PBA2中。對管理單元中的圖表進行修改，如圖7(c)過程三所示。物理鏈中剩下的PBA7和PBA10使用同樣的方法處理。

3 性能分析

本機制通過在控制器中加入管理單元來控制損耗均衡機制的實現。在機制運行過程中，管理單元的圖表，尤其是循環位圖的管理在時間和空間上會產生額外損耗，但是和傳統的損耗均衡機制相比，不需要查找擦除次數最大和最小的物理塊，所以對閃存寫入數據的速度沒有影響。

為驗證循環位圖的損耗均衡機制的有效性和實用性，對其進行了性能分析。假設閃存設備的參數如表1所示，其中讀寫操作時間是微秒級的，兩次寫操作間隔時間是毫秒級的［11］。

閃存中有n個物理塊，物理塊鏈中的平均物理塊為m個。假設某一時刻閃存中有an(0＜a＜1)個空閑物理塊，(1-a)n個非空閑物理塊，根據熱點列表找到的物理塊鏈中擦除次數大于平均擦除次數的個數是βm(0＜a＜1)。

圖7 靜態回收階段過程

表1 參數值

在動態寫入階段，一個空閑物理塊被消耗;在靜態回收階段，βm-1個空閑物理塊會產生。為了使消耗和產生的空閑塊達到平衡，需要控制靜態回收階段的啟動時間和啟動次數。假設寫操作時間為t1，擦除操作時間為t2，兩次寫操作之間的間隔時間為t3，那么兩次靜態回收過程的間隔即靜態回收的時間閾值t4為

那么由此得到靜態數據塊被回收的最長等待時間t5為

由此可知，物理塊在特定時間t5內會進行擦除處理，避免了靜態數據被長時間的存放。與靜態損耗均衡機制和動態損耗均衡機制相比，靜態數據塊的回收不再依賴于最大與最小擦除次數，并且有固定的回收時間，避免了大量的靜態塊長久不能被擦除的狀況。

假設某閃存設備中，有25%的內容為動態內容，75%為靜態內容。那么，在特定處理時間內，通過性能分析得到的動態、靜態和循環位圖3種機制閃存空間利用率對比情況如圖8所示。顯然，和靜態與動態損耗均衡機制相比，閃存循環位圖的損耗均衡機制使物理塊的擦除次數更加均衡，從而延長閃存的使用壽命。

圖8 損耗均衡機制閃存空間利用率對比

4 結束語

此研究通過在閃存的系統架構中加入循環位圖，研究和設計了一種新的損耗均衡機制。新的機制包含動態寫入和靜態回收兩個階段。二者相互配合、相互促進，從而使物理塊的擦除次數更加均衡，延長了閃存的使用壽命，有一定的應用價值。

為了保證機制的有效性和實用性，該機制需要在閃存設備中進行大規模地應用，并對應用過程中收集到的測試數據進行分析和研究，從而進一步的優化和完善此機制。

［1］Marco A A Sanvido，Frank R Chu，Anand Kulkarni.NAND flash memory and its role in storage architectures［J］.Proceedings of the IEEE，2008，96(11):1864-1874.

［2］PAN Liyang，ZHU Jun.Flash memory technology and its development［J］.Microelectronics，2002，32(1):1-6(in Chinese).［潘立陽，朱鈞.Flash存儲器技術和發展 ［J］.微電子學，2002，32(1):1-6.］

［3］Alan ROlson，Denis JLanglois.Solid statedrives datareliability and lifetime ［EB/OL］.［2008-04-07］.http://www.csee.umbc.edu.

［4］ZHANG Dong.Discuss storage2-deep analysis of storage system ar-chitecture and the bottom principles［M］.Beijing:Tsinghua University Press，2011:50-60(in Chinese).［張冬.大話存儲2-存儲系統架構與底層原理極限剖析［M］.北京:清華大學出版社，2011:50-60.］

［5］Application note:Wear leveling in NAND flash memory［EB/OL］.［2007-07-01］.http://www.micron.com/.

［6］Wear-leveling techniques in NAND flash devices［EB/OL］.［2008-10-08］.http://www.micron.com/.

［7］Jeong-UK Kang，Jin-Soo Kim，Chanik Park，et al.A multi-channel architecture for high-performance NAND flash-based storage system［J］.Journal of Systems Architecture，2007，53(2007):644-658.

［8］CHANG Lipin，HUANGLichun.A low-cost wear-leveling algorithm for block-mapping solid-state disks［J］.ACM SIGPLAN Notices-LCTES＇10，2011，46(5):31-40.

［9］CHANG Lipin，CHEN Mingdar，HUANG Chienting.Flash memory device with wear-leveling mechanism and controlling method thereof［P］.US:2010/0115186，2010-05-06.

［10］WANG Weineng，NI Kai，MA Jianshe，et al.Static wear-leveling design of flash memory in multi-channel parallel access mode ［J］.JTsinghua Univ(Sci＆Tech)，2011，51(11):1616-1620(in Chinese).［王偉能，倪凱，馬建設，等.多通道并行訪問模式下的閃存靜態損耗均衡設計［J］.清華大學學報 (自然科學版)，2011，51(11):1616-1620.

［11］Muthukumar Murugan，David H C Du Rejuvenator.A static wear leveling algorithm for NAND flash memory with minimized overhead［C］//IEEE 27th Symposium on Mass Storage Systems and Technologies，2011:1-12.