《电子技术应用》

基于4 KB数据块映射的固态硬盘算法

2017年电子技术应用第4期 作者:骆建军1,陈艳芬1,方立春1,Chris Tsu2
2017/5/8 13:47:00

骆建军1,陈艳芬1,方立春1,Chris Tsu2

(1.杭州电子科技大学,浙江 杭州310018;2.Sage Microelectronics Corp,California 95008)


    摘  要: 固态硬盘(Solid-State Drive,SSD)采用NAND型闪存(Flash Memory)为主要存储介质,闪存的读写不同于其他介质,需要闪存转换层(Flash Translation Layer,FTL)对闪存的存储空间进行管理。传统方式的映射算法随着页面(Page-size)的逐渐扩大,在随机数据块写入的速度方面难以提升。针对这个问题,提出一种基于4 KB数据块映射的闪存转换层算法,固态硬盘控制器芯片采用110 nm工艺实现,集成了SATA-II接口(3 Gb/s数据传输速率),最大可以并行驱动5通道的闪存芯片。该算法结合芯片的内部资源,经过了可靠性检测,达到了预期的可靠性和读写速度。

    关键词: 闪存(Flash Memory);固态硬盘(SSD);闪存转化层(FTL)

    中图分类号: TP391.41

    文献标识码: A

    DOI:10.16157/j.issn.0258-7998.2017.04.009


    中文引用格式: 骆建军,陈艳芬,方立春,等. 基于4 KB数据块映射的固态硬盘算法[J].电子技术应用,2017,43(4):36-38,42.

    英文引用格式: Luo Jianjun,Chen Yanfen,Fang Lichun,et al. A solid-state drive controller design based on 4 KB-size flash translation layer[J].Application of Electronic Technique,2017,43(4):36-38,42.

0 引言

    随着半导体技术的进步,NAND型闪存(Flash Memory)容量越来越大,价格也却越来越便宜,固态硬盘SSD在越来越多的领域取代以磁带为媒介的传统机械硬盘(HDD)。与传统机械硬盘相比,固态盘因无伺服寻址、盘片旋转和剩磁的影响而具有较高的带宽、低能耗、抗震性和数据的完全可删除性的特点而成为研究热点[1,2]。并且固态硬盘具有更快的数据处理速度,更高的可靠性和耐用性[3,4]。固态硬盘的存储器件采用的是闪存[5],具有以下几个特点:

    (1)读写基本单位是以页(Page)为单位,擦除是以块(Block)为单位。

    (2)每个物理块,必须先擦除,才能够写入数据。

    (3)每个块有一定的寿命,即擦除次数是有限的。

    基于这些问题,在固态硬盘中引入了闪存转换层FTL[6]。它包括数据映射、垃圾回收、损耗均衡、数据缓存等问题。FTL算法,特别是闪存映射表FMT(Flash Mapping Table),是影响固态硬盘性能高低的关键。传统的数据映射方式采用页映射,随着闪存页面的增大,页映射在随机读写上速度的不足显现出来。本文提出一种以4 KB数据块为单元做映射的算法(以下简称4 KB映射算法)来改善随机读写的速度,并通过测试验证该算法的有效性。

1 FTL及页映射

    FTL位于文件系统和物理介质之间,把Flash的操作习惯虚拟成以传统硬盘的512 B扇区进行操作。操作系统就可以按照传统的扇区方式操作,而不用担心之前说的擦除/读/写问题。一切逻辑到物理的转换,都由FTL来完成。

    页映射是将逻辑页映射到Flash中的任何一个物理页。该映射算法在物理页不大于4 KB时性能最好。但是随着Flash物理页的增大,目前主流基本为16 KB的物理页,并有扩大到32 KB的趋势,写入放大WA(Write Amplification)系数就会变大,随着物理页大小的增大,这种算法的劣势会越来越大。假设Page大小为16 KB,每次写入4 KB,基本需要:

    (1)读出此Page内不需要修改的12 KB;

    (2)寻找新的物理Page写入完整的16 KB数据(包括读出的12 KB、新写入的4 KB)。也就是说,写入4 KB, 实际上写入16 KB,写入放大系数为式(1):

    wdz1-gs1.gif

    考虑到映射表格FMT的更新以及其他管理资源的调度,实际WA肯定是大于4。显然,按照这样简单的映射方法是无法满足写入速度的要求,同时,也大大消耗了闪存的“寿命”。

2 基于4 KB数据块映射的FTL设计

2.1 4 KB数据块映射算法

    根据随机读写数据的最小单元4 KB,把FTL的最小管理单元也适应性地调整为4 KB数据块来进行映射和管理。基本原理为:来自主机的写入数据,每4 KB给予一个地址进行管理,连续几个4 KB达到一个完整的闪存Page数据量的时候,把它们一次性写入一个完整的闪存Page。如图1所示,页映射一个Page只是写入了4 KB,剩余的部分用其他数据填满,16 KB的空间只记录了4 KB有效数据,特别当Flash读写采用4 KB随机读写(4 KB Random R/W)时,页映射的劣势特别明显,而4 KB映射的写优势就凸显出来。理性状态下,4 KB映射写入放大系数WA=1。这种写入方法使得随机写入速度几乎接近于连续数据流的写入,大大提高了随机写入的性能。

wdz1-t1.gif

    当然,上述分析是理想状态的,前提是具有无限的空白闪存块(或者页)等待着使用。实际上,闪存块(页)是有限的,闪存管理需要把一些包含了无效数据的块释放出来,这就是通常说的垃圾回收“Garbage Collection”,并且要把回收的块在合适的时机擦除干净备用。这就会引起映射表的更新(写),使得WA略大于1。同时,垃圾回收和块擦除也需要时间,使得随机写入速度虽然接近连续写入数据流,但是真实测试还是只能够“接近”而不是“等于”或者“超过”。

    基于4 KB为单元的映射,固然大大提高了写入性能,但在读取信息的时候,带来了额外的负担:

    (1)在16 KB Page的映射情况下,一次映射表的搜索,可以读取16 KB数据,即每16 KB搜索一次闪存映射表。在4 KB为单元的映射下,读取时候的搜索就变为每4 KB就要搜索一次。因此,随机写性能的增加,一定程度上是以降低随机读性能为折中的。只是在硬件性能大大提高的前提下,搜索速度很高,随机读速度的降低相比于随机写性能的提高和写入放大系数WA的降低,这是非常值得的。

    (2)以4 KB为最小单元的映射引起了映射表存储空间的成倍增大。

     wdz1-gs2.gif

    假设硬盘存储空间128 GB,每个映射单元的地址表征字节数为4,采用4 KB映射,映射表大小为128 MB。由于映射表需在集成电路芯片内调度使用,芯片内的缓存一般采用SRAM来实现。超过1 MB大小的SRAM空间对于当前的集成电路芯片需占据很大的空间,性价比不高。现实设计中,采用分段调度的方式可以解决问题。即把当前需用到的表格部分读入SRAM,而把其余部分存放在芯片外部空间。芯片外部空间存放的形式有两种:外部的DRAM(Dynamic Random Access Memory)和闪存(Flash Memory)。

2.2 算法读写速度及性能分析

    下面分析随机写入4个4 KB的数据,Flash的页大小为16 KB的两种映射的速度。

    随机写入4个4 KB的数据时,4 KB映射算法最大写速度(不更换映射表)见式(3):

wdz1-gs3-5.gif

    最小写速度(每个4 KB都要更换全部的映射表)见式(6):

    wdz1-gs6.gif

    Tp是一个12 KB数据的搬移时间,Tr是一个读的延迟时间(即读busy)。对比式(3)和式(5),式(4)和式(6),得知4 KB映射的写速度高于页映射。

    针对128 GB的固态硬盘,闪存映射表为32 MB,按本文芯片资源给予的8 KB SRAM,具有4 M个“映射表段”(每个8 KB大小),其中只有一段8 KB映射表段被导入SRAM(称为“当前内存表段”),可以随时被搜索查询。因此,随机写入的4个4 KB数据,有4种可能性分布对应于落入FMT中:

wdz1-3-s1.gif

3 基于4 KB数据块映射算法的芯片架构

    固态硬盘控制器的算法主体最终是以固件形式在固态硬盘控制器芯片内运行的。针对本文的4 KB数据块映射的算法,图2给出了用来验证算法的固态硬盘控制器芯片的结构。该芯片分成两部分:主监处理器模块(Supervisor Processor Unit,SPU)和闪存通道控制器(Channel Processor,CHP)。

wdz1-t2.gif

    SPU模块包括32位CPU、SATA接口模块、相应的数据缓存和芯片的周边接口。这里特别需要SPU针对NCQ(Native Command Que)做出高效的处理,这是随机读写性能的又一重点要素。NCQ处理需要配合闪存4 KB映射算法做一些针对性的重新排队,尽量使连续4个4 KB数据的读(或写),不仅数据流方向一致,而且最好落在同一个映射表段内,即2.2表述的情形(1),提高情形(1)的概率对于算法是最有利的。此款控制器芯片有5个独立的CHP,提供真正的5路并行处理能力。每个CHP模块包括一个8位的RISC CPU、DMA(Direct Memory Access)、数据缓存和闪存总线控制。数据缓存区采用16 K Buffer和8 K FIFO,由于FMT占据空间较大,采用分段调度调用FMT表,而每次调表的大小和SRAM的大小有关,SRAM内存越大,能够调用的映射表段越大,那么映射表段的数量会越少,根据2.2内表述的情形(1),表段越少,相应落入同一个映射表的概率就会增大,这也是提高算法的一个有利因素。

4 实验结果

    基于算法思路和芯片架构,本文实现了一颗固态硬盘控制器芯片的设计。该芯片采用110 nm工艺,已在8英寸硅片上实现了批量生产。芯片尺寸3.908 mm×3.746 mm,SATA PHY为高速模拟电路,具有3 Gb/s的数据传输速率。映射表存储采用SRAM实现。片上集成的电源管理电路,把5 V电源转换成I/O电路和闪存芯片需要的3.3 V电压,也产生芯片内部需要的1.2 V电源。

    为检验本文的算法的效果,采用市场上M公司的两个NAND闪存型号来进行测试和比较,其中一个闪存Page Size为8 KB,另一个闪存为16 KB,出自同系列产品,其余参数基本一致,如读取等待时间为75 μs,编程(写入)等待时间1 300 μs。通过测速软件来测试这两款Flash使用页映射和4 KB映射的随机传输4 KB数据的写速度,如表1所示。可以看出:无论页面大小是8 KB还是16 KB,4 KB映射的平均速度明显比页映射的速度快,并且页面越大,4 KB映射的速度与页映射的速度差距增大。

wdz1-b1.gif

5 结论

    本文提出了一种基于4 KB数据块映射的FTL算法,并证明了基于4 KB数据块大小的映射可以有效提高随机读写速度,尤其是针对算法构建了一颗固态硬盘芯片,通过真正的芯片实体验证了理论分析。本课题组还将进一步研究,包括SATA-III速度匹配的电路结构、如何以有限的片上存储空间来实现越来越大的映射表,以及针对大数据存储要求,处理热数据和冷数据对于固态硬盘存储的差异性。

参考文献

[1] LAURA M G,ADRIAN M C,JOEL C,et al.Characterizing flash memory anmomalies,observations and applications[C]//Proceedings of 42nd annual IEEE/ACM international Symposium on Micro-achiteture,2009:24-33.

[2] TANAKAMARU S,DOI M,TAKEUCHI K.NAND flash Memory/ReRAM hybrid unified solid-state-storage architecture[J].IEEE Transactions on Circuits and Systems I:Regular Papers,2014,61(4):1119-1132.

[3] Huang Jian,AnirudhBadam,Moinuddin K Qureshi,et al.Unified address translation for memory-mapped SSDs with Flash Map[C]//Proceedings of the 42nd Annual International Symposium on Computer Architecture(ISCA).ACM,2015.

[4] Xia Qianbin,Xiao Weijun.Flash-aware high performance and endurable cache[C]//In 23rd IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems(MASCOTS),2015.

[5] IAN S.Osborne.Flash Memory[J].Science,2000,289(5477):217.

[6] Lee Sang-Won,Park Dong-Joo,Chung Tae-Sun,et al.A log buffer-based flash translation layer using fully-associative sector translation[J].ACM Transactions on Embedded Computing Systems,2007,6(3):1-27.

继续阅读>>