WAPFTL:支持预测机制的负载自适应闪存转换层算法

谢徐超，宋振龙，李 琼，魏登萍，方 健，肖立权

(国防科学技术大学计算机学院，湖南 长沙 410073)

1 引言

基于NAND Flash的固态盘SSD(Solid State Drive)具有低延迟、低功耗、高可靠性等优点，可以有效地提升存储系统的性能，在企业级和消费级存储领域得到广泛应用。在高性能计算领域，固态盘已成为用来提高系统IO性能的主要手段之一，例如位居2013年6月TOP 500榜首的“天河二号”计算机系统就采用了PCIe接口的SSD作为数据加速层，大幅提高了全系统的IO性能。而NAND Flash的写前擦除、擦除次数有限等固有特性使得基于NAND Flash的写性能相对其读性能要差，整体性能还有待提高。

作为固态盘控制器的核心，闪存转换层FTL(Flash Translation Layer)可以将底层NAND Flash阵列封装成一个和硬盘一样的块设备，隐藏擦除操作，保证现有文件系统对SSD的兼容性。FTL的主要功能包括地址映射、垃圾回收、磨损均衡等。地址映射将来自文件系统的读写请求的逻辑地址转换成固态盘内的物理地址，保证了异地更新策略的实现，是FTL中最重要的一项功能。当垃圾回收被触发时，对被擦除的数据块中有效页回收，然后将该数据块进行擦除。由于需要涉及对其中有效页的迁移和对块的擦除操作，对数据块进行垃圾回收是一个非常耗时的操作。

FTL中地址映射方式主要有页映射、块映射和混合映射等[1～4]。其中页映射机制以页为基本映射粒度，是最灵活、性能最优的地址映射方式。但是，随着固态盘容量的增加，地址映射过程中对页映射表的缓存需要更大的SRAM存储空间，造成成本增加。基于页映射机制的DFTL[5]算法将经常用到的部分映射关系存放到SRAM中，而整个映射表保存在Flash中，但是SRAM中部分缓存的地址映射信息很大程度上依赖于负载的时间局部性。另外，因地址映射信息在SRAM中未命中而引起的额外的读写操作，及其可能触发的垃圾回收操作等所产生的延迟对整个存储系统性能的影响是巨大的。因此，如何选择性地缓存地址映射信息，提高命中率，对于提升SSD的性能至关重要。

为了有效利用缓存空间对地址映射信息进行缓存，减少FTL对SRAM存储空间的依赖，我们提出了一种新的地址映射算法。该算法在有效协同利用访问请求的时间局部性和空间局部性的同时，能根据负载的数据请求特点动态预测请求的特点，并动态调整地址映射信息的缓存管理策略，提高命中率，有效改善系统的写性能。

2 WAPFTL算法设计

2.1 WAPFTL整体设计

WAPFTL的整体结构如图1所示，NAND Flash在逻辑上被划分为数据块(Data Blocks)和转换块(Translation Block)。数据块占据了绝大部分Flash空间，主要用来存储数据，转换块只占据小部分Flash空间，用来存储数据块中的所有逻辑页地址到物理页地址之间的地址映射关系。

Figure 1 Architecture of WAPFTL图1 WAPFTL结构

如图1所示，WAPFTL在固态盘SRAM中建立顺序缓存映射表SCMT(Sequential Cached Mapping Table)、缓存分裂表CST(Cached Split Table)、缓存映射表CMT(Cached Mapping Table)和全局转换目录GTD(Global Translation Directory)，并预先设置一个阈值threshold。其中SCMT、CST和CMT协同记录SRAM中处于活跃状态的页映射关系，全局转换目录GTD用来记录所有逻辑页对应地址映射信息在Flash中存放的物理页号。threshold的大小决定一个请求的地址映射信息在SRAM中缓存的方式，通过对threshold的动态调整，可以使整个算法针对当前负载请求的特点进行自适应调整，有效提高SRAM中映射信息的命中率。

SCMT和CST有三个表项：起始逻辑页号LPN、起始物理页号PPN和长度SIZE，其中长度SIZE指明了该映射关系中以该逻辑页号为起始页的一组起始逻辑页号和起始物理页号都连续的页的数量。SCMT和CST中SIZE的大小表示该映射关系的映射范围，但是其最大值不会超过一个块中所拥有页的总数量；在WAPFTL中，针对当前固态盘及其所用NAND Flash的规格，为保证足够的寻址空间，我们将LPN和PPN分别设置为4 B，将SIZE设置为2 B，因此，在SCMT和CST中一个地址映射信息所占用的空间为10个字节大小，而CMT中只用8个字节。

SCMT和CMT是用于记录SRAM中页映射信息最主要的数据结构。在高性能计算及企业级服务器中，有顺序写请求，也有较小的随机请求，CMT主要是用于缓存那些物理地址不连续的随机请求的地址映射信息。对于逻辑页号连续的读请求，在当前NAND Flash中，其数据所在的物理页的页号并不一定是连续的。因此，读请求从转换块中的某个转换页中一次只能读出一个逻辑页号对应的映射信息，当读失效时，SCMT中的SIZE并不能发挥其效果。因此，在这些情况下，设置SIZE造成了SRAM中存储空间的浪费。CMT中没有设置SIZE域，其实质是SIZE=1的SCMT，但是可以在随机请求和读请求密集的负载条件下更有效地利用SRAM空间。缓存分裂表CST主要用于记录缓存映射表中某些页映射关系由于部分更新分裂而形成的子页映射关系。CST在保证不破坏根据时间局部性原理而组织的SCMT的内部逻辑结构的前提下，更有效地利用IO请求的空间局部性原理。

2.2 地址转换

WAPFTL接收来自文件系统的IO请求，IO请求所携带的信息包括该IO请求的请求类型(读/写)、起始逻辑页号LPN、请求的长度SIZE页。

WAPFTL首先检查当前IO请求的起始逻辑页在SCMT或CST中的命中情况，即判断该请求的起始逻辑页号是否在SCMT或CST中某个地址映射关系所表示的区间内，可以得到命中和未命中两种结果。对命中的结果，通过判断该命中的地址映射信息表示的范围是否包含此IO请求的所有逻辑页，可得到完全命中或者部分命中两种结果。假设当前IO请求为写请求，请求逻辑地址为LPN，请求长度为SIZE页，SCMT中被命中的映射关系为(SCMTLPN,SCMTPPN,SCMTSIZE)，根据请求的SIZE以及SCMT和CST中命中的映射串信息，判断该请求的命中类型及相应操作的过程为：

(1)完全命中：该地址映射串包含了所有此IO请求需要的地址映射信息。生成两个长度不小于0的额外的子映射关系(SCMTLPN,SCMTPPN,LPN-SCMTSIZE)和(LPN+SIZE,SCMTPPN+LPN+SIZE-SCMTLPN,SCMTLPN+SCMTSIZE-LPN-SIZE)。对新生成的两个子映射信息，分别比较它们的长度与当前threshold的大小，若大于threshold，则将其放入CST中缓存，若小于threshold，则将该映射信息中包含的多个映射关系分别缓存到CMT中。

(2)部分命中：该地址映射串中只包含了此IO请求需要的部分地址映射信息。将当前IO请求根据缓存映射表映射关系表项中满足命中的范围分裂为两个子请求REQ1= (LPN,SIZE1)和REQ2= (LPN+SIZE1,SIZE-SIZE1)，其中，SIZE1 =SCMTLPN+SCMTSIZE-LPN。REQ1为在该映射关系中能够满足的子请求，REQ2为不能够满足的子请求，SIZE1为映射关系中满足命中部分的长度。同时，该过程中还会生成新的子映射关系(SCMTLPN,SCMTPPN,SCMTSIZE-SIZE1)。对于新生成的子映射关系，其处理方式与命中情况相同。

若该IO请求的起始逻辑页号未在SCMT和CST中命中，则继续到CMT中查找。与SCMT和CST中的命中情况不同，在CMT中命中的映射关系，一次只能得到该IO请求需要的所有映射信息中的一条，而在SCMT和CST中则可以一次得到多条。若该IO请求的起始逻辑页号在CMT中也没有命中，则表示该请求所需要的地址映射信息并没有缓存在SRAM中，需要通过GTD访问存有该信息的转换块，从其相应的页中取出所需要的映射关系，并根据当前缓存管理策略放入SRAM相应的表中缓存。在WAPFTL中，每个表都采用Segment LRU[3]进行组织。

2.3 地址映射信息的缓存策略

对于写请求，当SSD中有新的数据写入Flash时，FTL会在当前所有的空闲块中选择一块磨损次数最少的数据块作为当前数据块(Current Block)，用来存储最近被写入的数据。对于SIZE大于1的写请求，其写入该当前块中页的数量为SIZE，并且写入Flash后的物理地址也是连续的。因此，对于顺序写请求，我们可以利用这一特性在一个地址映射信息中记录多条页地址映射关系，如图2所示。

Figure 2 Cache strategy of address mappings in WAPFTL图2 WAPFTL地址映射信息缓存策略

由于SSD所采取的异地更新策略，在当前写请求完成对数据的存储以后，原有的地址映射关系发生改变，FTL需要作废原有映射信息并记录最新的地址映射关系。WAPFTL比较当前写请求的SIZE与当前threshold，如果SIZE大于threshold，则表示在当前负载情况下，WAPFTL的决策是及该地址映射信息缓存到SCMT中，WAPFTL在SCMT中缓存一个映射串，记录此次请求将该IO请求的所有映射关系。如果SIZE小于threshold，则表示在当前负载情况下，WAPFTL的决策是将每条地址映射关系单独缓存到CMT中。

对于读请求，由于SSD在完成读请求的过程中并不会发生对数据的更新操作，原有的地址映射关系也不会发生改变，因此，如果读请求的逻辑页号可以在SRAM任何一个表中命中，则无需处理。当所需地址映射关系在SRAM中未命中时，WAPFTL将所需映射关系从转换块中相应的转换页读入SRAM，并缓存到CMT中。显然，只有当threshold的值为1时，因读失效而从Flash的转换块中读入SRAM的映射关系才可能缓存到SCMT中。

2.4 预测及自适应

WAPFTL统计并分析在一段时间间隔内负载的请求类型与请求的大小，对以后的IO请求可能具有的特点进行预测，以调整当前SRAM对地址映射信息的缓存管理策略。WAPFTL通过改变当前threshold的值，动态调整SRAM中地址映射信息的缓存方式，以便在当前负载下可以尽可能地缓存更多的页映射关系，扩大SRAM地址映射范围，提高命中率，减少SRAM与Flash之间因为地址映射而造成的额外读写开销。在WAPFTL中，threshold值的变化规律如图3所示。

Figure 3 State transitions of workloads and the process of threshold in WAPFTL图3 WAPFTL中负载特性状态转换及threshold值变化规律

WAPFTL用“随机写”、“顺序写”和“读”三个状态表示当前负载请求的特点。对于所取时间间隔内，如果所有的请求中写请求比例超过40%，并且写请求所请求的页数大于当前threshold值的比例超过25%，则表明相对于SRAM中所缓存的映射关系来说，当前负载的顺序写请求较多，WAPFTL认为该负载当前的特点为“顺序写”，并执行threshold++。这是因为对于大量的写请求，如果threshold值较低，必然造成所有由于写操作而新形成的映射关系都直接存放到SCMT中，当SCMT内无空闲表项时，会造成SCMT中大量的具有较大SIZE值的映射信息写回Flash，而该映射关系所表示的映射范围直接影响WAPFTL中SRAM的命中率。WAPFTL通过执行threshold++，让SIZE值较小的映射关系缓存到CMT中，SCMT中SIZE较大的映射关系保证了SCMT中映射信息表示的逻辑范围。若当前负载请求的状态为“随机写”且threshold值仍大于1，WAPFTL则执行threshold--，以保证SRAM中SCMT空间的有效利用。

如果该时间间隔内所有的请求中读请求的数量占据了多数，WAPFTL则标记当前负载状态为“读”。如果threshold值仍大于1，WAPFTL执行threshold--。由于逻辑页号连续的页，其当前在Flash中所存放的页的物理页号不一定是连续的，对于读请求所需的地址映射信息未在SRAM中命中时，只能一条一条地从Flash中取出。但是，当读请求较密集时，就会造成CMT映射关系与Flash转换块之间频繁的数据交换。为了避免SCMT不能发挥作用，当WAPFTL检测到当前负载状态为“读”时，就执行threshold--，直至threshold值为1。

3 性能分析与评价

3.1 实验环境

为了验证WAPFTL的性能，我们扩展了SSD仿真环境Flashsim[7]，并在Flashsim中实现了页映射算法、FAST[8]、DFTL和WAPFTL算法。SSD的详细配置如表1所示。其中SRAM空间设置为64 KB，并假设整个SRAM空间足以缓存页映射算法和FAST的所有映射表。

Table 1 Specification of SSD configuration表1 SSD配置说明

实验应用的trace文件中，SPC1和SPC2来自于SPC[9]，MSRC1和MSRC2是由MSRCambridge所采集[10]。这些用来驱动Flashsim的trace的特点如表2所示。

Table 2 Workload characteristics表2 负载特点 %

3.2 系统响应时间和命中率

通过运行不同的trace，测试WAPFTL对SSD写性能的提高，在实验中我们以页映射算法为性能评测的基准(Baseline)。平均响应时间可以较好地衡量整个FTL的性能，其综合反映了FTL中地址映射、垃圾回收和磨损均衡算法所需的开销。如图4所示，WAPFTL平均响应时间低于DFTL，对系统性能有非常明显的提高。特别对于顺序写请求比例较大的MSRC1和MSRC2，已接近于理想状态下的响应时间。

Figure 4 Average system response time 图4 系统平均响应时间

为了评价WAPFTL中地址映射信息缓存方法的效率，我们对SRAM中地址映射关系的命中率和SRAM与Flash之间读写次数进行分析。如图5所示，WAPFTL中对映射关系的缓存可以有效提高SRAM中各类负载地址映射信息的命中率。

Figure 5 Cache hit ratio图5 命中率

在以页映射算法为基准时，对于DFTL和WAPFTL，额外的读写操作是由于SRAM中地址映射信息未命中而引起的。对于FAST，则是由于大量的完全合并而引起的垃圾回收操作而引起，如图6所示为四种算法在SPC1负载下的垃圾回收次数，FAST算法的垃圾回收操作严重影响了其性能。

Figure 6 Number of block erasures in SPC1图6 SPC1中块擦除次数

如图7所示，在负载一定的情况下，不同地址映射算法会产生不同的读写次数。

Figure 7 Number of read/write operations图7 读写次数

WAPFTL利用负载的当前特性进行预测并自适应调整缓存策略，保证尽可能多的地址映射信息缓存在SRAM中，有效减少了因为地址映射在SRAM中未命中而引起的SRAM与Flash之间额外的读写请求次数，从而减少对Flash的总的读写次数，提高SSD整体性能。

4 结束语

本文面向大容量SSD在高性能计算及企业级服务器中应用的特点，提出了一种闪存转换层中基于页映射机制的自适应地址映射算法WAPFTL。WAPFTL高效协同利用负载的时间局部性和空间局部性，在地址转换处理过程中通过预测当前负载请求特性，实现了对SRAM中映射信息缓存策略的动态调整。仿真与测试结果表明，WAPFTL算法能够提高SRAM中地址映射信息的命中率，减少因地址映射而引起的额外读写操作；同时，WAPFTL有效地减少了垃圾回收次数，提高了SSD整体性能。

[1] Chung T S, Park D J, Park S, et al. A survey of flash translation layer[J]. Journal of Systems Architecture, 2009, 55(5):332-343.

[2] Lim S P, Lee S W, Moon B. Faster FTL for enterprise-class flash memory SSDs[C]∥Proc of 2010 IEEE International Workshop on Storage Network Architecture and Parallel I/Os (SNAPI), 2010:3-12.

[3] Wei Q, Gong B, Pathak S, et al. WAFTL:A workload adaptive flash translation layer with data partition[C]∥Proc of 2011 IEEE 27th Symposium on Mass Storage Systems and Technologies (MSST), 2011:1-12.

[4] Wang C, Wong W F. ADAPT:Efficient workload-sensitive flash management based on adaptation, prediction and aggre-

gation[C]∥Mass Storage Systems and Technologies (MSST),2012 IEEE 28th Symposium on. IEEE,2012:1-12.

[5] Gupta A, Kim Y, Urgaonkar B. DFTL:A flash translation layer employing demand-based selective caching of page-level address mappings[C]∥Proc of the 14th International Conference on Architectural Support for Programming Languages and Operating System,2009:229-240.

[6] Karedla R, Love J S, Wherry B G. Caching strategies to improve disk system performance[J]. Computer, 1994, 27(3):38-46.

[7] Kim Y, Tauras B, Gupta A, et al. Flashsim:A simulator for NAND flash-based solid-state drives[C]∥Proc of the First IEEE International Conference on Advances in System Simulation, 2009:125-131.

[8] Lee S W, Park D J, Chung T S, et al. FAST:A log-buffer based FTL scheme with fully associative sector translation[J]. ACM Transations on Embedded Computing Systems, 2007,6(3):1-18.

[9] Storage performance council (SPC) storage traces[EB/OL].[2007-06-01]. http://traces.cs.umass.edu/index.php/Storage/Storage.

[10] Narayanan D, Donnelly A, Rowstron A. Write off-loading:Practical power management for enterprise storage[J]. ACM Transactions on Storage (TOS), 2008, 4(3):10.