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

1.2 写请求处理过程

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

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

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

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

1.3 垃圾回收机制

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

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

来源：中电网