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

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

0 引言

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

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

1 相關研究

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

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

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

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

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

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

1.2 損耗均衡技術現(xiàn)狀與分析

現(xiàn)在主流的損耗均衡分為動態(tài)損耗均衡［6］和靜態(tài)損耗均衡［6］兩種。

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

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

2 基于循環(huán)位圖的損耗均衡機制的設計

2.1 整體結構

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

圖1 系統(tǒng)架構

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

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

2.2 FTL

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

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

圖2 關系記錄

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

2.3 熱點列表

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

圖3 熱點列表

2.4 循環(huán)位圖

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

循環(huán)位圖是本機制的核心部分，可通過它找到空閑物理塊和靜態(tài)數(shù)據塊，進行寫入和擦除操作。

圖4 循環(huán)位圖

循環(huán)位圖包括兩個指針，分別為動態(tài)控制指針 (dynamic control pointer，dcp)和靜態(tài)控制指針 (static control pointer，scp)。其中dcp始終指向循環(huán)位圖中EMB為1的物理塊即空閑物理塊，而scp始終指向EMB為0的物理塊即靜態(tài)數(shù)據塊?？刂浦羔樢勒昭h(huán)位圖順序查找，直到找到符合要求的物理塊為止;如果查找到位圖尾部，仍舊無法找到，那么跳轉到位圖首部繼續(xù)按順序查找，如此循環(huán)，直到找到為止。

2.5 機制設計

2.5.1 動態(tài)寫入階段

圖5 動態(tài)寫入階段流程

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

(1)將數(shù)據寫入Target_PBA中;

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

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

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

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

2.5.2 靜態(tài)回收階段

對于那些寫入閃存并存儲了相當長一段時間甚至無限期的數(shù)據，動態(tài)寫入階段無法起作用。此外，在動態(tài)寫入階段，空閑物理塊會不斷被消耗，直至閃存中沒有空閑塊提供數(shù)據的寫入操作?；诖耍緳C制提出了靜態(tài)回收階段。

圖6為損耗均衡機制靜態(tài)回收階段的流程圖。

圖6 靜態(tài)回收階段流程

主要流程如下:

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

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

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

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

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

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

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

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

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

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

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

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

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

3 性能分析

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

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

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

圖7 靜態(tài)回收階段過程

表1 參數(shù)值

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

那么由此得到靜態(tài)數(shù)據塊被回收的最長等待時間t5為

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

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

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

4 結束語

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

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

［1］Marco A A Sanvido，F(xiàn)rank 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存儲器技術和發(fā)展 ［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-存儲系統(tǒng)架構與底層原理極限剖析［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).［王偉能，倪凱，馬建設，等.多通道并行訪問模式下的閃存靜態(tài)損耗均衡設計［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.