一个闪存芯片是由区块 (block) 所组成，每个区块是由页面 (page) 所组成，每个页面包含一个数据区与一个额外区，数据区是用来存放数据而额外区是用来存放管理数据(如错误更正码、数据区所存数据的逻辑地址...等)。区块是数据抹除的单位，而页面是读写的基本单位。当一个页面被写入数据之后就不能再写入数据，必须要等到它所在的区块被整个抹除后才能再写入数据。因此为了效能的考虑，通常我们会把写入的数据写到空闲页面 (free page)，而不是写回原来的页面，因此，同一份数据可能会同时有多个版本存在于闪存之中，然而只有最后一版的数据为有效数据，其余旧版的数据皆为过期或无效数据。存放最后一版数据的页面称为有效页面，存放旧版数据的页面称为无效页面。如图一所示，闪存装置上通常会搭配一个管理机来管理闪存，使得主机系统能够使用逻辑地址直接存取闪存存储装置上相对映逻辑地址的数据，而不需了解闪存的存取特性及实际数据所存在的实体地址。为了管理闪存，在闪存存储装置上需要一个逻辑地址与实体地址的转换机制 (address translation) 或转换信息，这样才能找到每个逻辑地址的数据存在处。另外，当系统没有足够的空闲区块时，空间回收单元 (garbage collector) 就会被启动来回收存放过期或旧版数据的空间。由于每个区块所能被抹除的次数有限，因此在选择回收并抹除的区块时，必须尽量使得每个区块被抹除的次数较为平均，以延长闪存的使用寿命。

《图一 》

闪存又可分为传统较高成本的 Single-Level Cell (SLC) 闪存，以及高密度低成本的 Multi-Level Cell (MLC) 闪存，其中SLC闪存的每个内存单元(cell)只能记录一个位 (bit) 的数据，而MLC闪存的每个内存单元可记录两个位以上的数据。传统上有许多不同的管理机制被提出 [1][2][3][4]，然而随着制程密度的上升，闪存的效能也快速下滑，再加上 MLC 闪存又新增两个写入的限制：一个是每一个页面只能被写入一次，另一个是每个区块内的每个页面必须要循序被写入。因此使得传统的管理方法无法管理这些高密度低成本的 MLC 闪存芯片，或是效能变得十分低落。为了改善存取效能，有研究提出利用特别的方法来管理随机小量被写入的数据，以提升整体系统效能 [5][6][7]。 有些研究更进一步提出可调性的地址转换机置来管理大容量的闪存存储系统，以提升管理机制的可扩充性 [8][9]。另外，有一些不同的研究是利用写入缓冲区来提升闪存的写入效能 [10][11][11]，不过这些机制都没有办法在页面数据毁损失时还原毁损页面中的数据，且通常会在系统当机或断电时产生数据流失，而使得储存系统丧失数据的一致性。

不同以往的方法，本文提出一个「提交式管理机制」来提升闪存的可靠性，可还原毁损页面中所存的数据。同时，此机制包含一个「三层式地址转换架构」以加速地址转换效能并减少主存储器的使用量，以及一个「可调性区块管理方法」以利用对多颗内存芯片平行写入的特性来加速数据存取的速度，并且可依随机或顺序访问模式自动调整以降低管理的额外负担。另外，此管理机制同时考虑到高密度MLC闪存的写入限制、系统快速开机及系统快速当机回复等特质。

提交式管理机制

闪存区编排方式

在本文所提出的提交式管理机制之中，一个多芯片的闪存存储装置的实体区块，会被分割成多个实体区域，及一个额外区域(如图二所示)。在不同芯片的同一编号的实体区块，组成一个实体区块集，同一个实体区块集中，各个区块中相同偏移量的页面组成一个实体页面集。一个实体区块集为空间回收与空间分配的最小单位，而一个实体页面集为数据读写的最小单位。额外区域的实体区块只能用来取代同一芯片内的毁损实体区块，因此即使有毁损实体区块存在且被取代时，读写指令仍然能够同时对实体区块集内的每一个区块做读写的动作，达到善用系统效能的平行性。每当有毁损实体区块发生时，就会从同一个芯片的额外空间分配一个好的实体区块来取代该毁损区块，而此取代信息就记录在「区块取代表」里。一个实体区块集内的数据写入是从第一个页面集循序写入，以符合高密度 MLC 闪存的写入限制。在逻辑地址空间方面，连续的逻辑地址组成一个虚拟页面，连续的虚拟页面组成一个虚拟区块，连续的虚拟区块组成一个虚拟区域，每一个虚拟区域都会依序对映到一个实体区域，而一个虚拟区域中的虚拟区块可以对映到相对实体区域中的任一个实体区块集，且每一个虚拟区块最多可以对映到两个实体区块集，其中较早被分配对映的实体区块集称为旧实体区块集，而较晚被分配对映的则称为新实体区块集。

《图二 》

三层式地址转换架构

给定一个逻辑地址，这三层分别负责「实体区域地址」、「实体区块集地址」及「实体页面集地址」等三层的地址转换以找到该逻辑地址的数据所存放的实体位置。如图三所示，当给定一个将要被存取的逻辑地址，这个逻辑地址就会被分割成「虚拟区域地址」、「虚拟区块地址」及「虚拟页面地址」，而这三个地址会被当成索引来分别从相关的「虚拟区域表」、「虚拟区块表」及「虚拟页面表」来找到存放该逻辑地址的数据的实体页面集。每一个虚拟区域都会维护一个自己的虚拟区块表来维护所有虚拟区块与相对映实体区块集的地址转换信息，而每一个虚拟区块都会有一个自己的虚拟页面表来维护该虚拟区块中虚拟页面对映到相关实体页面集的转换信息，且只有在被使用或参考到时才会从快闪记体读取出来存放在主存储器之中。如此一来，只有被用到的地址转换信息才会被存放在主存储器，因此可以大幅降低主存储器的使用量。由于每个虚拟区域都会对应到一个实体区域，因此需要一个虚拟区域表来记录它们与实体区域的对映关系，当然也可以使用循序对映的方式，这样一来就不需要虚拟区域表，只要直接记算就能得知每个虚拟区域所对映的实体区域。

而当一个虚拟区域被存取时，它相对映的虚拟区块表会马上利用扫描相对映实体区域内每一个实体区块集的一个页面来重建该虚拟区块表。而当一个虚拟区块被存取时，它相对映的虚拟页面表可以马上利用扫描相对映实体区块集内每一个实体页面集来重建该虚拟页面表。由于只有被存取到的虚拟区域(/区块)的相对映虚拟区块(/页面)表需要被重建，所以开机及当机后地址转换信息重建的效能非常高，且不会随着闪存容量上升而变慢。此外，所有的地址转换表可以暂时存放在闪存之中，在被使用时才读取出来，且关机时将所有更新过的地址转换表都写回闪存之中，则当系统有正常关机时，重开机就不用任何地址转换表重建的时间，因此能快速启动。若是系统毁损，则下次开机之时，我们也只需要重建毁损的地址转换表即可。因此具有高度的可扩充性及地址转换效能。

《图三 》 - BigPic:763x430

可调性区块管理方法

在所提出的提交式管理机制中，采用可调性区块管理方法来管理数据的写入。一开始每个逻辑区块都没有对映的实体区块集，当一个逻辑区块第一次被写入数据时，一个空闲的区块集就会被分配来存放被写入的数据，并且对映成该逻辑区块的「新实体区块集」，所写入的数据会依序从该区块集的第一个页面集循序往下写。当此新实体区块集被写满剩下最后一个页面集时，该逻辑区块所有数据的逻辑地址到其相对映实体页面集的地址转换表(注:也就是虚拟页面表)就会存放在最后这个页面之中，称写入地址转换表的这个动作为「确认提交」。如果接下来有数据写入到此逻辑区块，则另一个空闲实体区块集就会被分配来存放写入数据，并且对映成此逻辑区块的新实体区块集，而原来对映的实体区块集就变成「旧实体区块集」，所有写入的数据都会循序地写入新实体区块集。

当一个逻辑区块已经对映到两个实体区块集，且其新实体区块集已经被写满或是已确认提交，则当有新的写入数据到此逻辑区块时，则一个新的空闲实体区块集就会被分配来存放写入的数据，并且设定为其逻辑区块的新实体区块集，而原来的两个实体区块集中，拥有比较多有效数据的区块集就会被设定为旧实体区块集，另一个区块集则会被回收并且抹除。在回收之前，存放在区块集内的有效数据会先被复制到新分配的实体区块集里。

《图四 》 - BigPic:604x392

如图四所示，为一个逻辑区块的旧实体区块集拥有较多的有效数据或页面集，每个页面集所存放的数据的逻辑地址简写为 vp，通常这样的现象发生在存放系统数据或是小量经常被更新的数据，因此大部分有效数据都留在旧实体区块集，而新实体区块集所存放的为经常被更新的少量数据，因此只有非常少量的有效数据，其余大多为过期或无效数据(灰色底代表的是无效数据)。当逻辑区块所相对映的两个实体区块集都已确认提交，此时，若有一个新的数据写入到此逻辑区块，则新实体区块集中的有效数据(也就是vp 2)会先被写到一个新分配的空闲实体区块集，接着就会被回收并抹除，而这个新分配的实体区块集则变为该逻辑区块的新实体区块集，而原来的旧实体区块集仍然为旧实体区块集。另外一个循序数据存取的例子（如图五所示），大部分的数据都循序被更新到新实体区块集，因此当新实体区块集被写满或确认提交时，大部分或所有的有效数据都在新实体区块集，若有一个新的数据写入该逻辑区块时，旧实体区块集内的有效数据会被复制到新分配的空闲实体区块集，此空闲实体区块集就会变成该逻辑区块的新实体区块集(注：图五的例子中的旧实体区块集没有有效数据)，接着该旧实体区块集就会被回收并且抹除，而原来的新实体区块集就变成该逻辑区块的旧实体区块集。值得一提的是：系统里的实体区块集的数量必须比逻辑区块多，因为每个逻辑区块可能同时对映到两个实体区块集。

《图五 》 - BigPic:676x359

依据上面例子可知，此可调性区块管理方法可以自动调整，使得不论是随机数据写入或是循序数据写入都能有很好的效能。当随机写入发生时(例如写入档案特性、文件系统的系统信息或是小系统档案)，大部分的有效数据都会留在逻辑区块的旧实体区块之中。当循序数据写入的状况发生时(例如写入多媒体档案的内容)，数据通常会留在逻辑区块的新实体区块之中。而本文所介绍的可调性区块管理方法总是会选择有效数据较少的实体区块来抹除，因此不论是随机或循序数据写入，都能有很好的空间回收效能。下面图六是一个连续写入两个1MB大小的档案到一个 FAT 文件系统的过程，在写入这两个档案的过程中包含了一个大量的循序区域写入(逻辑地址 210664-214759)以及三个随机区域的小量数据写入。本发明所提出的方法可以同时对数据内容的写入、文件属性的写入与目录信息更新的写入都有很好的效能。

《图六 》 - BigPic:613x606

值得一提的是：每一个实体区块集都会在实体页面的额外区保留一个指针指向另一个实体区块集，而此实体区块集是在它之前被对映到同一个逻辑区块的实体区块集。因此系统如果当机的话，系统只要从这个指针的指向关系就能知道对映到相同逻辑区块的实体区块集的新旧关系。当然如果系统分配一个新的空闲实体区块集来取代某个实体区块的过程中发生当机或断电，那么系统里就可能会有三个实体区块集会对映到同一个逻辑区块，然而因为最后被分配对映到此逻辑区块的实体区块集一定没有指针指向它，而被它的指针所指到的实体区块集就是没有被取代掉的那个实体区块集，因此就能够找出三个实体区块集的新旧关系，以回复未完成的实体区块集取代动作，达到快速当机回复的目的。

另外，一个实体区块集里头所存放的数据会使用错误更正的方法来还原更正一个实体页面或实体页面集里的数据。一个比较直接的做法是把每一个写入同一个实体区块集里的每一个实体页面数据都使用XOR这个运算来算出「同位检查码」，最后在关机或是实体区块集里的所有实体页面集(除了最后一个页面集)都被写满之时，将该实体区块集所属实体页面集的同位检查码写入到最后一个实体页面集里(注：与虚拟页面表一起写入)，而这个实体页面集里的实体页面称为「总结页面」。当未来实体区块中有任何一个实体页面数据毁损时，该实体区块集的同位检查码就可以用来还原该毁损页面内的数据，同时使用额外区域里的空闲实体区块来取代包含该毁损页面的实体区块，被取代的实体区块内的数据都搬移到新的实体区块内，同时区块取代表的对映也会随着被更新。之所以当一个实体区块内有一个页面毁损时就把该实体区块置换的原因是因为拥有毁损页面的区块通常比较容易产生更多的毁损页面，且对一些特定的管理方法会有不良的影响，例如使得这些方法变得没有效率或是无法正确存取数据。值得一提的是：因每个虚拟区块所属的虚拟页面表同时存放在其相对映的实体区块集的总结页面里头，所以每个虚拟区块集被存取时就不需要重建其相对映的虚拟页面表。

最后，本文同时提出一个快速的「过期数据回收法」。当系统没有足够的空闲实体区块时， 系统的空间回收单元(garbage collector)就会被启动来回收无效数据所占据的空间。空间回收器被启动时就会循环地检查每个逻辑区块，如果某个逻辑区块对映到两个实体区块集，这两个实体区块集里的有效数据就会被合并复制到另一个空闲实体区块集，然后把这两个实体区块集抹除并回收，如此一来不常被更新的数据所占据的空间就能得到回收以得到更好的空间利用率。由于每次合并两个实体区块集就能得到一个空闲的实体区块集，因此空间回收的最差运行时间(worst-case execution time)就能很容易地预测，这样的特性对实时系统来说是非常重要的。

结语

本文所提出的「提交示管理机制」之中所包含的三层式地址转换架构可提升地址转换效率，以提升闪存装置的整体效能，并且达到高度的可扩充性。同时可调性区块管理方法可对多个闪存芯片做同时存取的动作以大幅提升存取效能，并且能自动调整所选中的空间，以最小化回收过期数据时所增加的数据复制量。另外更使用总结页面来存放部分的地址转换信息及错误更正信息来进一步提升高密度低成本闪存储存装置的地址信息重建效率及数据可靠性。

本研究成果已发表于 2009 年设计自动化国际会议 (Design Automation Conference, 2009)。

参考文献

[1]Flash File System. US Patent 540,448. In Intel Corporation.

[2]FTL Logger Exchanging Data with FTL Systems. Technical report, Intel Corporation.

[3]Flash-memory Translation Layer for NAND flash (NFTL). M-Systems, 1998.

[4]A. Birrell, M. Isard, C. Thacker, and T. Wobber. A Design for Highperformance Flash Disks. SIGOPS Oper. Syst. Rev., 41(2):88–93, 2007.

[5]T. Kgil and T. Mudge. FlashCache: a NAND Flash Memory File Cache for Low Power Web Servers. the International Conference on Compilers, Architecture and Synthesis for Embedded Systems (CASES), pages 103–112, 2006.

[6]G. Kim, S. Baek, H. Lee, H. Lee, and M. Joe. LGeDBMS: a Small DBMS for Embedded System with Flash Memory. In the 32nd International Conference on Very Large Data Bases (VLDB), pages 1255–1258. VLDB Endowment, 2006.

[7]C.-H. Wu, L.-P. Chang, and T.-W. Kuo. An Efficient B-Tree Layer for Flash-Memory Storage Systems. In the 9th International Conference on Real-Time and Embedded Computing Systems and Applications (RTCSA), 2003.

[8]L.-P. Chang and T.-W. Kuo. An Efficient Management Scheme for Large-Scale Flash-Memory Storage Systems. In the ACM Symposium on Applied Computing (SAC), pages 862–868, Mar 2004.

[9]C.-H. Wu and T.-W. Kuo. An Adaptive Two-level Management for the Flash Translation Layer in Embedded Systems. In the IEEE/ACM International Conference on Computer-Aided Design (ICCAD), pages 601–606, 2006.

[10]H. Jo, J.-U. Kang, S.-Y. Park, J.-S. Kim, and J. Lee. FAB: Flash aware Buffer Management Policy for Portable Media Players. In IEEE Transactions on Consumer Electronics, pages 485–493. IEEE, 2006.

[11]H. Kim and S. Ahn. BPLRU : A Buffer Management Scheme for Improving Random Writes in Flash Storage. In the 6th USENIX Conference on File and Storage Technologies (FAST), pages 239–252, 2008.

[12]S. yeong Park, D. Jung, J. uk Kang, J. soo Kim, and J. Lee. CFLRU: a Replacement Algorithm for Flash Memory. In the International Conference on Compilers, Architecture and Synthesis for Embedded Systems (CASES), 2006.

---张原豪为国立台湾大学信息工程学博士，现任国立台北科技大学电子工程学系助理教授；郭大维为德州大学奥斯汀分校计算机科学博士，现任国立台湾大学信息工程学系教授---