基于NAND闪存的自适应闪存映射层设计

发布时间：2010-8-20 14:33 发布者：lavida

闪存存储器主要分为NAND和XOR两种类型，其中NAND型是专为数据存储设计。本文的闪存映射方法主要是针对NAND类型的闪存芯片。一个NAND类型的闪存芯片的存储空间是由块(Block)构成，每个块又划分为固定大小的页，块是擦写操作的最小单元，页是读写操作的最小单元。由于闪存存储器的硬件特性，闪存的更新操作有自己的特点，在对数据进行更新前需要先进行擦写操作，然后才能将新数据写入，并且擦写操作是以块为单位，读写操作是以页为单位。由于擦写操作涉及的最小单元远大于读写操作的最小单元，需要对一个擦写块内不需要更新的数据提供有效的保护。在闪存存储管理中普遍采用的数据更新方法是非本地更新的方法(Out-place Update)，通过构建闪存映射层，在进行更新操作时，将更新的数据写到其他空闲的存储位置，利用内存中的地址映射表记录数据存储位置的变化。非本地更新的方法避免了更新时整块数据的读出写入，从而减少数据复制次数和块擦写次数，提高系统的整体性能。闪存映射层是闪存进行非本地更新存储管理的关键，主要由地址映射和垃圾回收机制两部分构成。

根据地址映射粒度的不同，可以将地址映射方法分为三种：页映射(Page Mapping)、块映射(BlockingMapping)和混合映射(Hybrid Mapping)。页映射是以页为单位进行地址映射，在内存中保存基手页的映射表，每一逻辑页都有一项与之对应的物理页，页映射方法具有灵活性高的优点，但由于需要为每个逻辑页面建立地址映射表项，需要占用大量内存空间。块映射算法是以块为单位进行地址映射，逻辑块内地址偏移与物理块内偏移保持一致。该方法仅需要在内存中保留块映射表，建立从逻辑块到物理块的映射关系，块映射算法优点是内存占用量少，不受闪存容量增大的影响，缺点是在处理小数据更新上性能较差，一小块数据的更新会引起对整个块内容的复制。混合映射方法结合了块映射和页映射的优点，首先以块映射方法建立逻辑块和物理块的映射关系，同时对块内数据采用页映射方法组织。混合映射算法内存空间占用量少，同时对小数据更新比块映射算法更加灵活、代价少。

垃圾回收是闪存存储系统特有的空间管理机制。在闪存存储管理中，由于采用非本地更新的方法，当闪存的存储空间消耗完时，就需要回收无效数据占用的空间。为了回收无效数据占用的空间，必须先将擦写单位内的有效数据转移到其他空闲区域，然后擦写整个单元，回收过程主要涉及有效数据复制和块擦写两个耗时耗能的操作。垃圾回收工作需要从闪存中选择回收对象，转移有效数据，最后完成对象擦除。进行垃圾回收时选择不同的区域进行擦除，代价是不同的，垃圾回收器设计的目就是要减少有效数据复制和块擦写次数，以提高系统性能。不同粒度的地址映射方法在不同写模式下，垃圾回收的性能有较大差异。在此给出了一种能够根据写模式进行自适应判断的闪存映射方法。通过对顺序写和随机写进行判断，将顺序写从随机写中分离，对顺序写采用块映射组织日记块数据，对随机写采用混合映射方法，并为热数据分配多个日记块，延迟对热数据的垃圾回收，以提高垃圾回收的性能。通过实验表明这里构建的闪存映射方法能够在不需要占用大量的内存空间前提下，减少垃圾回收过程的有效数据复制和块擦写，从而优化闪存系统的性能。

1 闪存存储系统的体系结构

本文构建的闪存存储管理的体系结构见图1，将系统分为文件系统层、闪存管理层和闪存驱动层。闪存映射层负责对闪存设备进行存储管理，通过地址映射和垃圾回收技术将闪存转换为块设备。地址映射主要完成闪存块的分配和地址映射信息管理，负责处理文件系统层的读写请求，将文件系统提供的逻辑地址转换为闪存的物理地址；垃圾回收则负责回收无效数据占用的空间，主要涉及有效数据复制和块擦写两个耗时耗能的过程。

1.1 地址映射结构

闪存映射层的作用是将文件系统的逻辑地址转换为闪存的物理地址，因此需要在内存建立逻辑地址和物理地址的映射关系，同时管理物理地址的状态变换。本文通过图2所示的地址映射结构进行地址映射管理，将文件系统提供的逻辑地址分为四部分：逻辑组号、组内块号、块内页号和页内偏移地址。其中逻辑页和逻辑块大小分别与闪存存储器的读写页和擦写块大小相同。每个逻辑组是由N个连续的逻辑块构成，N可以根据应用类型进行设置，在图2中N的数目为2。将闪存存储器中的物理块分为数据块和日记块，数据块用于存放原数据，日记块用于存放更新数据，同时又将日记块划分为顺序日记块和随机日记块。数据块和顺序日记块内的内容是以块映射方法组织，而随机日记块采用混合映射粒度组织数据。逻辑块和数据块通过内存中的块映射表建立对应关系，每一个逻辑块都有惟一的数据块与之对应。与逻辑组对应的N个数据块构成一个数据组。每个顺序日记块对应惟一的数据块，在对数据块进行顺序更新操作时，为其分配顺序日记块存储更新数据。每个数据组可以根据需求动态分配多个随机日记块，日记块的数目是由该组数据访问的冷热属性来决定的，对于有频繁更新数据的组会动态分配较多的日记块。随机日记块是组内共享的，对组内任一数据块的随机更新数据都可以存储到随机日记块中，从而提高空间利用率。为了提高查找效率，对有随机日记块的数据组，在内存中构建组内页映射表，记录逻辑地址对应的更新数据在随机日记块内的存储位置，通过组内页映射表，在进行读取时不需要遍历日记块来获取数据的存储位置，从而提高系统性能。

1.2 写请求处理过程

地址映射的主要作用是通过在内存中构建地址映射表，将文件系统的逻辑地址转换为物理地址，在系统进行读请求时，利用地址映射表查找到存储在闪存设备中的数据，在系统进行写请求时在闪存设备上查找空闲位置存储数据，更新地址映射表，记录数据的新存储位置，同时将旧数据标记为无效。

在本文中为每个数据块设定状态位来标记该块当前的访问模式，将每个数据块访问模式分为顺序写和随机写。在进行写请求时，首先计算出数据所属的逻辑块和块内偏移地址，判断数据所在块的访问模式，如果所在块是顺序写，利用块映射表，将数据写到顺序日记块中。如果所在块为随机写，将更新数据写到数据组的随机日记块中。访问模式主要是根据过去的数据存储访问行为进行判断的，如果对某一逻辑地址在短时间内进行了多次更新，认为系统对该地址进行的是随机写，对其所属块将采用混合映射方法进行存储管理，以优化小数据频繁更新导致的性能问题。访问模式的判断是通过内存中的双链表来实现的，如图3所示。在内存中构建两定长的地址链表，一个链表为顺序链表，另一个链表为随机链表。顺序链表中保存最近进行顺序写的数据块，而随机链表中保留最近进行随机写的数据组。两链表都根据最后一次访问时间进行排序，将链表分为最近最少访问端(LRU)和最近最多访问端(MRU)，在每次进行更新操作时，将更新数据所在的块或组提升到链表的最近最多访问端。当对数据块首次进行更新操作时，判断该数据块进行的是顺序写，标记该块的访问状态为顺序写，并将该数据块添加到顺序链表中。如果数据块内已更新过的数据在短时间内再一次被更新，即顺序日记块内对应的存储空间已填充数据，判断该数据块的访问模式为随机写，将其从顺序链表中删除，标记该块的访问状态为随机写，同时添加该块所在的数据组到随机链表中，以后对该块的更新数据将存储到随机日记块中，直到该数据组从随机链表中删除。

顺序链表的项数设有上限值，该值为系统中分配的顺序日记块数目。当表项超过上限值时，将从顺序链表的最近最少访问端删除数据块，合并日记块和数据块中的有效数据。当顺序日记块完全更新时，即数据块内的数据完全无效，采用切换操作，用顺序日记块替换数据块，并将该块从顺序链表中删除。在本文中始终保留了一定数据的顺序日记块，以优化系统的顺序写。

位于随机链表中的数据组，当需要新的存储空间时，将为其分配新的随机日记块。随机链表的项数也设有上限值，当超过上限值时，将从最近最少访问端删除数据组，将随机日记块和数据块中的数据合并，生成新的数据块，同时重设数据块的状态位，当再一次进行数据更新时，将重新进行访问模式判断。采用该方法能够将冷数据及时从链表删除，回收日记块占用的存储空间和页映射表占用的内存空间。

1.3 垃圾回收机制

由于采用日记结构进行存储管理，在长时间运行时需要进行垃圾回收。进行垃圾回收时需要考虑的问题是回收时机和回收对象选择，以及回收方法。垃圾回收机制是建立在地址映射方法基础上，主要由两部分构成：擦写进程和回收进程。擦写进程是专门负责擦写操作，它的优先级比较低。在系统空闲的时候，擦写进程才会轮到执行，每次该进程启动，只负责擦写一个块，以免影响到正常的I／O性能。回收进程是当系统中的日记块消耗完或闪存中的空闲块低于某阈值，将从日记块和数据块中选择回收对象，将有效数据复制到其他空闲区域中，将其交给擦写进程处理，回收存储空间。

本文回收进程主要包括两部分，对顺序日记块的回收和对随机日记块的回收。当系统中的顺序日记块消耗完全时，将从顺序链表的最近最少访问端选择日记块，利用数据块和顺序日记块内数据组织有序的特点，采用如图4所示的方法，将数据块中的有效数据复制到日记块中，用日记块来替换数据块，擦除数据块，回收数据块占用的空间。对于随机日记块，将从随机链表中选择具有最多无效数据的数据组，回收方法是从数据组中选择两个或多个具有较多无效数据的日记块，将日记块中的有效数据复制到数据组的其他随机日记块中，如图5所示，擦除选中日记块，回收日记块空间。

通过根据顺序日记块和随机日记块数据组织特点分别采用不同的回收方法，从而优化了垃圾回收的性能。对于顺序日记块，将数据块与日记块内有效数据合并，用日记块替换数据块，从而减少回收过程中的有效数据复制。而对于随机日记通过选择无效数据最多的块进行回收，同时利用本文的多日记块机制，将有效数据存储到其他日记块。从而不需要合并数据块和日记块的数据，减少了小数据更新情况下的有效数据的复制和块擦写次数，优化了垃圾回收的性能。

2 试验结果与分析

在Linux系统中实现了本文的存储管理方法，同时利用Linux自带的闪存模拟器，模拟闪存存储器的功能，在该模拟器上对本文的闪存映射方法展开研究，并与NFTL和混合映射方法进行比较，NFTL是Linux系统实现的块映射方法。在实验中采用额外写操作次数和擦除操作次数来衡量闪存系统性能的标准，其中额外写操作次数由实验中闪存的实际写次数减去用户请求的写次数来获取，主要是由垃圾回收时有效数据的复制产生的。额外擦写操作次数是指闪存系统的块擦写次数，是由于日记块的消耗引起的。采用这两个指标能够直接反应垃圾回收的性能。首先研究了在进行文件和图像等存取操作下系统的性能。由于仅进行图像存取操作时，系统的大部分操作是顺序写。图6所示是三种方法的额外写操作次数和擦写操作次数对比情况。从图6中可以看出本文方法与NFTL方法接近，需要较少的有效数据复制和块擦写，而混合映射方法表现较差，尤其是有效数据的复制次数，明显多于其他两种方法。主要是由于本文方法与NFTL能够利用块映射方法来处理顺序写模式，在进行垃圾回收时，能够通过将数据块的有效数据复制到日记块中，用日记块替换数据块，而不需要分配新的数据块，减少有效数据复制和块擦写。而混合映射方法在进行垃圾回收时，需要分配新的数据块来合并旧数据块和日记块中的数据，导致系统进行大量的复制操作和擦写操作，降低垃圾回收的性能。

图7的实验结果是在进行图像存取操作的同时加入对局部数据进行随机访问来获取的。从结果可以看出，NFTL方法与混合映射方法的性能接近，都需要较多的额外写次数和块擦写次数。本文的方法由于采用写模式判别机制，能够将随机写从顺序写中分离出来，对顺序写采用块映射方法，对随机写采用混合映射方法进行存储管理，从而垃圾回收次数较少，优化系统性能。