（国防科学技术大学计算机学院 长沙 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 地址映射
闪存转换层要实现逻辑地址（文件系统的访问地址）到物理地址（闪存的实际地址）的映射。地址映射可以在块级、页级或混合级实现。
在块级地址映射中，一个页的逻辑地址被分为逻辑块号和块内偏移两部分。地址映射表只保存逻辑块到物理块的映射关系，而逻辑地址的块内偏移与物理块内偏移相同。块级映射的优点是映射信息少，占用的存储空间小，但是会带来较严重的更新前擦除问题。
在页级地址映射中，一个逻辑页可以映射到任何物理页中。这种映射方法非常灵活，但是映射信息较多，占用的存储空间较大。
为了解决块级和页级地址映射的问题，大多闪存转换层策略都采用混合级地址映射的方法。混合级映射在级块映射的基础上，同时维护一个页级映射表，对更新的数据进行映射。
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年，在读博士，主要研究方向是海量数据存储和管理、体系结构。
