SSD中一种地址映射算法研究

马福祥

（青海师范大学 计算机学院，青海 西宁810008）

近年来，CPU的运行速度按照摩尔定律快速增长，每年大约成长30%-50%，而硬盘速度由于机械寻道等原因增长很慢，只能成长约7%，因此在系统中硬盘一直都是系统性能的瓶颈。为解决硬盘速度慢的问题，产生了磁盘阵列和固态硬盘(Solid-State Disk,SSD)两种技术。磁盘阵列通过专用控制器将多组传统硬盘进行RAID （Redundant Arrays of Inexpensive Disks,RAID）组合的技术，这样提高了读写速度、存储容量和可靠性，此技术一般用在机群服务里。采用多组Flash芯片的固态硬盘技术，通过将多组Flash芯片形成阵列来提高读写速度和可靠性，与磁盘阵列相比，SSD技术具有成本低、体积小、重量轻、抗震摔、无噪音和工作温度范围大的诸多优点，目前吸引了大量的工业和学术界所关注的热点。它也是近几年最有希望代替传统硬盘成为主流存储设备的新型存储设备。目前有一系列的SSD研究主题，从接口技术到缓冲器管理、从Flash转换层 （Flash Translation Layer,FTL)到性能和能耗效率等等。在FTL中，地址映射策略是FTL最基本的组件，它在一定程度上决定了其它组件的设计，所以，地址映射机制是 FTL的核心部分，是垃圾回收和损耗均衡的基础。但目前的地址映射算法都各有利弊，本文分析了一种性能较好的页映射和混合映射按给定阀值进行转化的算法，此方法比较有效的避免了存储映射表所需的大空间、浪费过多的系统资源和映射表的更新相当频繁等问题。

1 SSD存储介质介绍

目前，市场上SSD的组建方式有基于DRAM的和基于FLASH芯片的，由于DRAM的SSD能耗高于普通硬盘，且需要不间断供电，因此目前应用范围小。而基于FLASH芯片的SSD，数据写入后不需要外界电力来维持其记忆，因此目前市场上绝大部分SSD都是基于Flash的。Flash技术主要有2种类型，NOR（Intel 1988 年）和 NAND（Toshiba 1989 年）。 相比NOR Flash，NAND Flash具有存储密度更高、容量更大、功耗更低、芯片引脚兼容性更好和成本效益更高等优点，因此大多数SSD也都是基于NAND Flash。NAND Flash读操作和写操作的最小单位是页 （page），擦除操作的最小单位是块（block），对于一个已经保存数据的页，在写入新数据时，需要先擦除，再写新数据，每个块擦写次数是有限制的，一般是10K到100K，并且每块芯片在出厂时都有一定比例的坏块存在。NAND Flash技术采取特殊的浮栅场效应管（Field Effect Transistor,FET)通过储存电荷来存储数据，写数据就是向浮栅中注入或者排除一定量的电子，读数据是通过检查场效应管的电流电压，根据电流电压的大小判断该场效应管所存储的状态。根据状态的个数NAND Flash存储单元又分为两类：单层单元 (Single Layer Cell,SLC)和多层单元 (Multi-Level Cell,MLC)，SLC每个单元只存放1bit数据，能表示0和1两种状态。MLC每个单元可存放2bit数据，能表示00、01、10和11这4种状态。虽然MLC提高了容量，由于存放的信息多，结构复杂而带来了更高的出错率。因此，对数据进行修正，正是错误修正这个动作导致其性能相对于SLC大幅落后，此外，MLC的复写次数也仅为SLC的十分之一。但是由于成本和容量的优势，市场上大多数SSD都是MLC型的。

2 SSD内部结构分析

如图 1所示，SSD主要由接口芯片、微处理器、DMA、DRAM和Flash存储阵列组成。其中接口主要有PATA、SATA、PCIe和USB 3.0。PATA是为了与当时的硬盘接口相吻合，以方便SSD主攻PC市场，让消费者也更容易接受SSD。 SATA接口于2001年推出SATA 1.0时，传输速率已达150 MB/s，高于 PATA最大传输速率133MB/s，随着 SATA 2.0与3.0的陆续推出，传输速率更倍速成长至300MB/s和600MB/s，传输速度演进之快，非PATA接口能及，近年来已逐渐取代PATA，成为储存设备主流接口。 SATA3是串行ATA国际组织发布的新版规范，主要是传输速度达到6Gbps，是未来的主流接口。SSD的核心部分是硬盘控制器[1]，一般由 FPGA作为载体，移植 MicroBlaze嵌入式处理器软核，通过片内总线OPB(On-Chip Peripheral Bus)连接各个功能模块，实现固态硬盘控制器的功能。DRAM控制器以及外接一块 DRAM，作为处理器工作时的程序和数据缓冲。NAND Flash控制器实现对 NAND Flash阵列的并行操作。

图1 固态硬盘总体结构图Fig.1 Structure diagram of the SSD

SSD是以硬盘的替代者的姿态出现的，为了与现有系统无缝对接，SSD必须对外提供块接口，使主机端所看到的SSD是一个和HDD一样的块设备。为了达到模拟块设备的目的，SSD中需要FTL作为中间层，如图2所示，它由3部分组成，Address mapping(地址映射)、Wear leveling(损耗平衡)和Garbage collection(垃圾回收)。从图可知，FTL从主机文件系统接收块级请求，经过FTL的处理，产生Flash的各种控制命令。

Flash中每个块都有一定的擦写次数限制。如果没有合理的管理机制，SSD在几万次的擦写后就可能损坏。为了延长Flash芯片的整体寿命，增强可靠性，就要在所有的块之间平衡擦除次数，这种技术被称为损耗均衡。这方面的研究成果文献已经很多，基本方法有动态损耗平衡和静态损耗平衡。动态损耗平就是在请求到达时，选取擦除次数较少的块作为请求的物理地址。静态损耗平衡的基本做法是将冷数据从原块取出，存放在擦除次数过多的块，原来存放冷数据的块被释放出来，接受热数据的擦写。

图2 固态硬盘结构框图Fig.2 Structure diagram of the SSD

所谓的垃圾回收是指当需要释放一部分空闲空间时，此块内既有过时或者作废的数据页也包含有有效的数据页，就需要把有效数据和无效数据进行分离，把所有有效数据重新移动到其它块中，把不包含有效数据的块进行擦除来释放自由空间。其过程可以简单地概括为，选择回收对象，回收预处理和擦除整个块3个步骤。

3 地址的映射改进算法

当主机发出读写操作命令，并给出将要操作的逻辑地址时，文件系统根据主机给出的逻辑地址计算出具体的物理地址，由于考虑到均衡损耗，每个逻辑地址对应的实际存储介质的物理地址是变化的。因此存储系统采用地址映射来获取逻辑地址对应的物理地址。根据映射的不同，FTL算法分为页地址映射和块地址映射。页地址映射的基本是页(page)，每个逻辑页都被映射到任何一个物理页[2]。因此，如果文件系统有 m个逻辑页，则映射表的记录数就有m条，如图3所示。逻辑地址 （Logical address）4通过 SRAM上的映射表（Map Table）可以找到对应的内容(0,3)。前者是物理块号（Physical Block Number，PBN），后者为块内偏移地址，通过此方法很方便的找到了对应的页。该方法映射信息管理的灵活度高，空间利用率高，垃圾回收负载小。但它也有一些问题，比如一个SSD总容量为128GB，每页容量为2KB。在映射表中，总共有128GB/2KB=64,000,000条表项，每条表项所占空间为4B，所以要放下这个映射表需要4B*64,000,000=256 MB，而在运行时映射表需要常驻SSD的RAM中，一般而言，SSD所能提供的RAM大小为16 MB到256 MB。所以，对于大容量的SSD，采用页映射是不可能的。

图3 页地址映射Fig.3 Page address mapping

块映射算法的基本单位是块(block)。整个地址空间首先被表示为多个块，而每个块又包含多个页，每个页由所属块号和块内偏移量确定。在一个逻辑块内，逻辑页的偏移量和对应的物理块内的页偏移量是相同的。因此，只有定位到块，页也就可以确认了如图4。逻辑地址包含了两个部分，9/4=2是逻辑的块地址，9%4=1为块内偏移地址。通过映射表可以知道2对应于物理块1，通过偏移量1可以找到其最终的物理页，完成寻址过程。因此，块地址映射只需要很小的RAM空间存储映射信息。比如SSD总容量为128GB，块映射方式下，映射表所需的容量为4 MB，极大地节约了RAM的空间。但是，这种映射方法不灵活，逻辑页只能被映射到同一个物理页。假如文件系统对同一个逻辑页发出多次写请求，由于对应的物理页是同一个页面，因此为了写入数据，必然对该页产生大量的拷贝、擦除操作，导致存储设备空间内碎片较多，进而严重影响存储器的性能及使用寿命。

图4 块地址映射Fig.4 Block adress mapping

通过以上分析得知，页映射性能好，但是映射表占用空间大。块映射表占用空间小，但是性能差。针对此问题，Kim等提出了一种更有效的混合地址映射算法，BAST算法[3-4]。该算法首先使用块映射算法得到相应的物理块，然后在块内再使用页映射算法，此算法提高了闪存的空间利用率，但在随机写频繁的情况下，会引起频繁的块擦除操作，导致随机访问性能降低。为解决日志块利用率低的问题，Lee等人提出了FAST算法[5]，该算法进行垃圾回收时会导致日志块与多个数据块的合并操作，影响了运行效率。除此外，还提出了SuperBlock[6]、LAST[7]等算法。无论哪种算法，都需要两次的映射及查表，总体性能不及前面两种。

鉴于上面的分析，我们提出了一种算法，其思想是：首先使用一个大容量的RAM和一个大容量的SSD，并通过特定的文件系统进行管理。然后设置一个阈值T[8]（根据SSD的大小按算法阈值可动态变化），当映射表的容量大于此值时，使用混合地址映射，否则只使用页地址映射。其流程图5所示。

图5 算法的流程图Fig.5 Flow chart the algorithm

4 结束语

文中提出了一种的基于页地址映射和混合地址映射相互转化的策略。当映射表没达到阀值时该算法映射速度快，空间利用率高。当超过阀值[9-10]时采用混合地址映射，避免了存储映射表所需的大空间，浪费过多的系统资源和映射表的更新也相当频繁的问题。

[1]叶朝锋,黄松岭,徐云.基于SATA的嵌入式高速大容量数据存储系统设计[J].电测与仪表，2008，45(2)：41-44.YE Chao-feng,HUANG Song-ling,XU Yun.Design of highspeed and high-capacity embedded data store system based on SATA connection[J].Electrical Measurement&instrumentation,2008，45(2)：41-44.

[2]谢长生,李博等:基于片内SRAM的固态硬盘转换层设计[J].计算机科学，2010,37(7):296-300.Xie Chang-sheng Li Bo,On-chip SRAM-based FTL Design for Solid-state Drive[J].Computer Science,2010,37(7):296-300.

[3]Kim J,Kim JM,Noh SH,et al.A space-efficient flash translation layer for compact flash systems [J].IEEE Transactions on Consumer Electronics,2002,48(2):366-375.

[4]邵亚刚,戴冠中等:基于日志式混合映射的FTL算法设计与实现[J].计算机测量与控制,2009,17(7):1362-1364.Shao Yagang Dai Guanzhong,Design and Implementation of A Log-structured Hybrid Mapping Algorithm for File Translation Layer of Flash Memory [J]. Computer Measurement&Control,2009,17(7):1362-1364.

[5]Lee S,Park D,Chung T,et al.A log buffer based flash translation layer using fully associative sector translation[J].ACM Trans on Embedded Computing Systems,2007,6(3):18-es.

[6]Kang J,Jo H,Kim J,et al.A superblock-based flash translation layer for NAND flash memory[C]//Proc of the 6th ACM&IEEE Int Conf on Embedded Software.ACM,2006:161-170.

[7]Lee S,Shin D,Kim Y,et al.LAST:Locality-aware sector translation for NAND flash memory-based storage systems[J].ACM IGOPSOperating System Review,2008,42(6):36-42.

[8]Gal E,Toledo S.Algorithms and Data Structures for Flash Memories[J].ACM Computing Surveys,2005,37(2):138-163.

[9]张晓宁，孙丽君.一种改进的小波阈值信号去噪方法[J].电子科技，2012（11）:15-17.ZHANG Xiao-ning，SUN Li-jun.An improved method for wavelet threshold signal demonizing[J].Electronic Science and Technology，2012（11）:15-17.

[10]杨昊.CUDA下局部阈值和二值函数的边缘检测[J].电子科技，2014（3）:52-54.YANG Hao.Local threshold and boolean function edge detection alorithm using CUDA [J].Electronic Science and Technology，2014（3）:52-54.