（國防科學技術大學計算機學院 長沙 410073）
A Log Block-based flash translation layer using offset-first scheme
Wang Jianxun,Xiao Nong,Liu Fang,Lai Mingche,Chen Zhiguang
(College of Computer,National University of Defense Technology,Changsha 410073)
Abstract NAND flash memory has been widely used due to its advantages such as non-volatile,small size,low power consumption and high access speed.With the increasing capability,NAND flash memory based SSD is becoming a strong competitor of HDD in PC field.However,the physical character of erase-before-update is one of the major bottlenecks which affect the performance and using life of NAND flash memory.In Flash translation layer,there have been many schemes to improve the impact of the physical character of erase-before-update,such as BAST and FAST scheme.In this paper,a novel log block based scheme in flash translation layer called offset-first scheme is proposed,which can get more metathesis operations that erase less blocks at the time of garbage collection process by trying to place the update data in the log block according to the offset.So the offset-first scheme can reduce the erase blocks as a whole,and improve the performance and using life of NAND flash memory.Simulators of four schemes are developed to compare the different performance. The experiment indicates that the offset-first scheme can reduce the erase blocks of NAND flash memory more effectively.A formula which calculate the total erased blocks by calculating the erased log blocks and erased data blocks respectively is proposed too, and the experiment indicates that the offset-first scheme can erase small quantity of both log blocks and data blocks.
Key words NAND flash memory;Flash Translation Layer;erase-before-update;offset-first Scheme;metathesis
摘 要 NAND閃存具有非易失、體積小、功耗低且訪問速度快等諸多優點，已經成為應用十分廣泛的存儲介質。而更新前擦除的物理特性是影響NAND閃存性能的主要瓶頸之一。在閃存轉換層中，已有多種方法可以改善NAND閃存的更新前擦除的影響。這篇文章提出了一種基于日志塊的閃存轉換層策略——偏移優先策略，通過在日志塊中優先按偏移位置存儲更新數據，以在垃圾回收的時候獲得擦除塊數較少的置換操作，從而在整體上減少NAND閃存的擦除次數，提高NAND閃存的性能和使用壽命。實驗表明，偏移優先策略可以非常有效地減少閃存的擦除次數。
關鍵詞 閃存；閃存轉換層；更新前擦除；偏移優先策略；置換
[1]
中圖法分類號 TP333
1 概述
NAND閃存由于其非易失、體積小、功耗低、防震且訪問速度快等諸多優點，已在嵌入式和移動設備中有著非常廣泛的應用。并且，隨著容量的不斷增加，以NAND閃存為存儲介質的固態盤也逐漸在PC領域占有一席之地。
閃存是由很多塊組成的，每個塊包含多個（64或128等）頁。更新前擦除[1]的物理特性成為影響NAND閃存性能的重要瓶頸。首先，對NAND閃存中的某一頁數據進行更新時，必須先對包含此頁的塊進行擦除操作。其次，對塊的擦除開銷相對非常大。在NAND閃存中，讀/寫一頁的開銷大概是20us和200us，而擦除一塊的開銷需要1.5ms[1]。最后，一個塊的擦除次數是有限的， 一般為10萬次到100萬次[2]。因此，對NAND閃存的擦除操作不但影響其性能，而且影響其使用壽命。
在閃存轉換層中，已有多種方法被提出，可以改善NAND閃存的更新前擦除的影響。其中的一個重要指標是減少的擦除次數。本文提出一種基于日志塊的閃存轉換層策略——偏移優先策略，通過在日志塊中優先按偏移位置存儲更新數據，以在垃圾回收的時候獲得擦除塊數較少的置換操作，從而在整體上減少NAND閃存的擦除次數，提高NAND閃存的性能和使用壽命。實驗表明，偏移優先策略可以非常有效地減少閃存的擦除次數。
本文的后續部分安排如下：第2節介紹相關工作，包括閃存轉換層中的地址映射以及幾種典型的閃存轉換層策略；第3節詳細介紹本文提出的偏移優先策略，并將偏移優先策略與其他轉換層策略進行了定性比較和分析；第4節介紹模擬實驗測試和性能分析；第5節對本文進行總結，以及對下一步工作進行展望。
2 相關工作
2.1 閃存轉換層
閃存轉換層（FTL）[2]是文件系統和閃存之間的中間層，其主要功能是向文件系統提供傳統硬盤的塊設備接口，使得閃存設備可以像傳統硬盤一樣被使用。閃存轉換層中的地址映射和垃圾回收機制屏蔽了閃存的更新前擦除的物理特性。
2.1.1 地址映射
閃存轉換層要實現邏輯地址（文件系統的訪問地址）到物理地址（閃存的實際地址）的映射。地址映射可以在塊級、頁級或混合級實現。
在塊級地址映射中，一個頁的邏輯地址被分為邏輯塊號和塊內偏移兩部分。地址映射表只保存邏輯塊到物理塊的映射關系，而邏輯地址的塊內偏移與物理塊內偏移相同。塊級映射的優點是映射信息少，占用的存儲空間小，但是會帶來較嚴重的更新前擦除問題。
在頁級地址映射中，一個邏輯頁可以映射到任何物理頁中。這種映射方法非常靈活，但是映射信息較多，占用的存儲空間較大。
為了解決塊級和頁級地址映射的問題，大多閃存轉換層策略都采用混合級地址映射的方法�；旌霞売成湓诩墘K映射的基礎上，同時維護一個頁級映射表，對更新的數據進行映射。
2.1.2 垃圾回收
在閃存轉換層中，為了減少擦除操作，通常利用一部分閃存塊來存儲更新的數據。這些閃存塊被稱為更新塊[3]]（update block），存儲原始數據的閃存塊被稱為數據塊[3]（data block）。隨著更新的數據增多，占用的更新塊也增多。為此，需要將那些無效（被更新過）的數據占用的空間（垃圾）回收回來。
當選擇對某個更新塊進行垃圾回收時，首先分配一個新的空白塊（被擦除過或未使用過），將更新塊和數據塊內的有效數據（最新更新的數據）都復制到新塊的對應位置，如圖1A，然后將更新塊和數據塊進行擦除操作，這個過程被稱為全合并[3]（full merge[4]）。如果更新塊內的數據均有效且均在正確的偏移位置上，那么只需將數據塊內的有效數據復制到更新塊內，如圖1B和圖1C，然后擦除數據塊，這個過程被稱為部分合并[3]（partial merge[4]）。如果更新塊的所有頁都被順序更新，如圖1D，則只需擦除數據塊即可，這個過程被稱為交換（switch merge[4]）。
在本文中，將圖1B，圖1C,圖1D中的更新塊的特點稱為滿足偏移一致性，并將部分合并和交換過程統稱為置換（metathesis）,并將全合并簡稱為合并。很顯然，置換過程可以避免擦除更新塊。
2.2 閃存轉換層策略
2.2.1 替換塊策略
替換塊策略（Replacement block scheme[5,6]）把數據塊的更新數據按照偏移量存儲到一個更新塊，也叫為替換塊（replacement block）的對應位置上。當某一頁數據被再次更新的時候，此替換塊也會被分配一個更新塊作為其替換塊，如圖2。在垃圾回收時，把有效數據都復制到最新的替換塊中，然后擦除數據塊和其他的替換塊。替換塊策略的缺陷是，當某一頁被多次更新時，會導致多個替換塊的擦除。
2.2.2 BAST策略
BAST策略[7]是由Kim等人在2002年提出的。其主要方法是把數據塊的更新數據按順序存儲到更新塊（被稱為日志塊）內，所以日志塊需要采用頁級地址映射的方式。由于BAST策略把對一個頁的多次更新都存儲到一個日志塊內，所以比較替換塊策略來說，減少了日志塊的擦除數量。但在BAST策略中，采用的是塊相聯方法，即一個日志塊只存儲一個數據塊的更新數據，這帶來兩個問題。一是當更新數據總是來自不同的數據塊時，日志塊在沒有完全利用的情況下被合并。二是對熱點數據塊來說，與其對應的日志塊用滿之后被合并，其他的日志塊卻處于空閑狀態。
2.2.3 FAST策略
FAST策略[8]是由Lee等人在2007年提出的。與BAST最大的不同是其采用的是頁相聯方法，即一個日志塊可以存儲所有數據塊的更新數據，較大地提高了日志塊的空間利用率，減少寫失效。由于FAST中的日志塊可能包含多個數據塊的頁，所以在垃圾回收時會導致多個數據塊的合并操作。此外，由于頁相聯不能很好地利用順序更新的交換操作，所以FAST設置了一個日志塊專門用于順序更新操作。
2.2.4 超級塊策略
Kang等人在2006年提出了一種超級塊策略[9]。超級塊策略把N個連續的邏輯塊合并為一個超級塊（super block[9]），并采用頁級映射的地址映射方法把超級塊映射到N+M個物理塊上，其中M為更新塊的個數。超級塊策略可以把熱點數據集中存放到某些塊內，減少合并操作，并且能較高地利用更新塊的空間利用率。
3 偏移優先策略（offset-first scheme）
置換操作可以減少擦除，因此，盡可能地獲取置換操作，可以減少閃存的整體擦除次數，從而提高閃存的性能和壽命。替換塊策略由于按偏移存儲更新，替換塊滿足偏移一致性，可以獲得最多的置換操作，但是對熱點數據，替換塊策略將擦除較多的替換塊。BAST和FAST策略由于按序存儲更新數據，因此都不能獲得如圖1C所示的置換操作。為此，本文提出一種偏移優先的閃存轉換層策略，通過在日志塊中優先按偏移位置存儲更新數據，以在垃圾回收的時候獲得更多的置換操作，同時將熱點數據集中在一個日志塊內存儲，從而在整體上減少NAND閃存的擦除次數，提高NAND閃存的性能和壽命。
偏移優先策略與BAST策略的組織結構類似，一個日志塊只存儲一個數據塊的更新。不同的是，更新數據優先按偏移量在日志塊中存儲，且允許多個日志塊同時緩存一個數據塊的更新數據。
3.1 對更新請求的處理
當對一個數據塊的更新請求到來時，我們首先嘗試按照偏移量在日志塊中存儲。有如下a，b兩種情況：
a 如果存在日志塊緩存此數據塊的數據 (按照查詢規則，此日志塊存儲最新的更新數據)
a.1 如果日志塊有空閑的空間
a.1.1 如果日志塊滿足偏移一致性，則將更新數據存儲到偏移位置上；
a.1.2 如果日志塊不滿足偏移一致性，則將更新數據存儲到其他空閑位置上；
a.2 如果日志塊沒有空閑的空間，則分配新的日志塊，將更新數據存儲到偏移位置上；
b 如果不存在日志塊緩存此數據塊的數據，則分配新的日志塊，將更新數據存儲到偏移位置上；
3.2 垃圾回收策略
在偏移優先策略對更新請求的處理策略中我們可以看出來，在一個日志塊滿的時候，我們并沒有像BAST策略一樣立即對他進行合并，而是等到日志塊的數量達到限定的閾值時，才會進行垃圾回收。這樣就可能存在多個日志塊對同一個數據塊緩存。而決定做合并還是置換操作的是最新的日志塊是否滿足偏移一致性。
當沒有可用的日志塊可以緩存新的更新數據的時候，偏移優先策略首先選擇一個最新的日志塊；
a 如果日志塊滿足偏移一致性，則把數據塊和其他的日志塊的有效數據復制到這個最新的日志塊中，擦除數據塊和其他的日志塊，也就是置換操作，并修改地址映射信息；
b 如果日志塊不滿足偏移一致性，則找到一個空白塊，把數據塊和其所有日志塊的有效數據復制到這個空白塊中，擦除數據塊和所有的日志塊，也就是合并操作，并修改地址映射信息。
3.3 日志塊的地址映射
偏移優先策略中的日志塊采用混合級映射。滿足偏移一致性的日志塊采用塊級的地址映射映射，不滿足偏移一致性的日志塊采用頁級的地址映射映射。相比較BAST和FAST中日志塊的頁級地址映射，偏移優先策略可以進一步減少映射信息量。
3.4 定性比較和分析
為了對幾種策略進行定性分析，我們提出一個擦出除次數計算公式：
C=U/K/p-M+G*T （1）
我們分別計算日志塊（或替換塊）和數據塊的擦除個數。其中C為整體的擦除塊數；U為更新頁數， K為每塊含有頁數，U和K均為常數，p為日志塊的空間利用率，所以U/K/p為日志塊的使用數量；M為可以做置換操作的日志塊數量，所以U/K/p-M為擦除的日志塊的數量；G為垃圾回收的次數，T為每次垃圾回收平均擦除的數據塊的數量，所以G*T為擦除的數據塊的數量。
相比較替換塊策略，偏移優先策略有著較高的日志塊的空間利用率，而在偏移優先策略的日志塊不滿足偏移一致性的情況下，替換塊策略則需要多個替換塊；偏移優先策略與BAST策略有著近似的日志塊的空間利用率，但是偏移優先策略可以獲得如圖1C所示的置換操作；FAST的日志塊的空間利用率最高，但是比偏移優先策略獲得置換操作要少，并且在一次垃圾回收時，FAST合并的數據塊也較多。
4 實驗
為了比較偏移優先策略與其他閃存轉換層策略的擦除情況，我們用C語言實現了替換塊策略，BAST策略，FAST策略和偏移優先策略的算法。模擬條件如表1.
Table 1 condition of simulation
表 1 模擬條件
|
Description |
Value |
|
Size of page |
512B |
|
Number of pages per block |
64 |
|
Size of block |
32K |
我們采用的是在Windows XP環境的PC上運行了一天Outlook express, UltraEditor, Latex, MSN, IE, Putty, Dr.eye, ftp server等應用的trace。此trace來源于臺灣大學Joshon等人的工作[10]。表2是trace的描述。
Table 2 description of trace
表2 trace描述
|
Description |
Value |
|
Total request |
272439 |
|
Write request |
244787 |
|
Pages of write request |
5853757 |
|
Update pages |
3433560 |
我們比較了不同日志塊額定數量（額定數量是指，當使用的日志塊達到此數量時，需要進行垃圾回收）的情況下，幾種策略的擦除情況，如圖3。橫坐標表示日志塊的額定數量，縱坐標代表擦除塊的數量。
由圖4可以看出，FAST策略和偏移優先策略的擦除塊數明顯比替換塊策略和BAST策略要少。在額定日志塊數量較少的情況下，FAST策略比偏移優先策略的擦除塊數要略少，在額定日志塊數量較多的情況下，FAST策略比偏移優先策略的擦除塊數要多。隨著閃存容量的不斷增大，偏移優先策略將更加有效。
我們以日志塊數量為128為例，分析比較幾種策略的擦除次數計算公式中的各個參數，如表3。
由表3我們可以看出，替換塊策略雖然獲得的置換操作最多，但由于非常低的替換塊的空間利用率，擦除的塊數也最多。FAST策略由于很高的日志塊的空間利用率，擦除的日志塊最少。但是FAST策略每次垃圾回收需要合并較多的數據塊，所以擦除的塊數也較多。偏移優先策略獲得較多的置換操作，擦除的日志塊較少，并且由于允許多個日志塊存儲一個數據塊的更新數據，延遲了合并操作，從而較少了數據塊的擦除。
Table 3 value of each parameter when rated number of log blocks is 128
表3 日志塊額定數量為128時，公式1中各參數情況
下圖說明了隨日志塊的數量變化，公式1中各參數的變化情況。其中橫坐標表示額定的日志塊的數量。
Fig. 4 value of each parameter with different rated number of log blocks
圖4 各參數隨日志塊額定數量變化的情況
圖4a-1，2，3描述的是日志塊的使用，置換和擦除情況。隨著日志塊的額定數量的增加，偏移優先策略的日志塊的空間利用率也增加，其使用的日志塊總數量減少，如圖4a-1。而偏移優先策略的置換操作數量仍多于FAST策略，如圖4a-2。擦除的日志塊數量的情況如圖4a-3，FAST和偏移優先策略擦除非常少的日志塊，而FAST比偏移優先策略略少。圖4b-1，2，3描述的是數據塊的擦除情況。隨著日志塊的額定數量的增加，偏移優先策略的垃圾回收次數明顯少于FAST策略，如圖4b-1。而FAST策略每次垃圾回收的平均擦除數據塊的數量較大，如圖4b-2。擦除的數據塊數量情況如圖4b-3，FAST擦除的數據塊較多，而偏移優先策略擦除最少的數據塊。從而偏移優先策略在整體上擦除的塊數最少。
5 結論
本文提出一種基于日志塊的閃存轉換層策略，偏移優先策略。偏移優先策略通過優先按偏移位置存放更新數據的方法獲得更多的置換操作，減少了日志塊的擦除。同時，將熱點數據集中存放，減少了日志塊的使用。偏移優先策略延遲了垃圾回收，減少了數據塊的擦除數量。實驗證明，偏移優先策略在整體上比其他閃存轉換層策略減少更多的擦除次數，提高了閃存設備的性能和壽命。
參考文獻
[1] CHANIK PARK, WONMOON CHEON, JEONGUK KANG,KANGHO ROH, and WONHEE CHO and JIN-SOO KIM.A ReconFig.urable FTL (Flash Translation Layer) Architecture for NAND Flash-Based Applications[J].ACM Transactions on Embedded Computing Systems, Vol. 7, No. 4, Article 38, July 2008.
[2] GAL, E. AND TOLEDO, S. 2005. Algorithms and data structures for flash memories[J]. ACM Computing Surveys 37, 138–163.
[3] Guo Yufeng,Li Qiong,Liu Guangming,and Zhang Lei.Research on the NAND Flash-Based Solid State Disk[J].Journal of Computer Research and Development Vol.46 Suppl.Ⅱ July 2009.328-332.
郭御風,李瓊,劉光明,張磊.基于NAND閃存的固態盤技術研究[J].計算機研究與發展,第46卷,增刊Ⅱ,2009年7月.
[4] SungJin Lee, DongKun Shin, Young-Jin Kim and Jihong Kim.LAST: Locality-Aware Sector Translation for NAND Flash Memory-Based Storage Systems[C].1st International Workshop on SPEED,2008.
[5] MTD, “Memory Technology Device (MTD) subsystem for Linux,” http://www.linux-mtd.infradead.org.
[6] A. Ban, Flash file system[J]. United States Patent, no. 5,404,485, April 1995.
[7] KIM, J. S.,KIM, J. M.,NOH, S. H.,MIN, S. L., AND CHO, Y. K. 2002. A space-efficient flash translation layer for compactflash systems[J]. IEEE Transactions on Consumer Electronics 48, 366–375.
[8] S. W. Lee, D. J. Park, T. S. Chung, W. K. Choi, D. H. Lee, S.W. Park, and H. J. Song. A log buffer based flash translation layer using fully associative sector translation[J].ACM Transactions on Embedded Computing Systems, vol. 6, no. 3,2007.
[9] J. U. Kang, H. Jo, J. S. Kim, and J. Lee. A superblock-based flash translation layer for NAND flash memory[J], in Proc. International Conference on Embedded Software,161-170, 2006.
Wang Jianxun male，born in 1986，master candidate， Main research direction is computer architecture.
王建勛 男，出生于1986年，在讀碩士，主要研究方向是計算機體系結構。
Xiao Nong male,born in 1969,Doctor,professor of National University of Defense Technology,doctorial tutor,senior membership of China Computer Federation,Main research direction is high performance computing on grid,Mass data memory and management and computer architecture.
肖 儂 男，出生于1969年，博士、國防科技大學教授、博士生導師，中國計算機學會高級會員，主要研究方向是高性能網格計算、海量數據存儲和管理、體系結構。
Liu Fang female,born in 1976,Doctor,associate professor of National University of Defense Technology,,Main research direction is Network storage and Information Security.
劉 芳 女，出生于1976年，博士，國防科技大學副教授，主要研究方向是網絡存儲和信息安全。
Lai Mingche male,born in 1982,Doctor,lecturer of National University of Defense Technology,,Main research direction is computer architecture, VLSI design, on-Chip communication, and optical communication.
賴明澈 男，出生于1982年，博士，國防科技大學講師，主要研究方向是計算機體系結構，VLSI設計，片上互聯和光通信。
Chen Zhiguang male,born in 1984,PH.D candidate,Main research direction is Mass data memory and management and computer architecture.
陳志廣 男，出生于1984年，在讀博士，主要研究方向是海量數據存儲和管理、體系結構。
