123012013137_叶邦宪_林铭炜_自适应的高性能闪存缓冲区替换算法解析

福建师范大学

毕业论文

题 目： 自适应的高性能闪存缓冲区替换算法

姓 名： 叶邦宪

学 院： 软件学院

专 业： 软件工程

学 号： 123012013127

指导教师： 林铭炜

自适应的高性能闪存缓冲区替换算法

软件学院 软件工程专业

123012013127 叶邦宪 指导教师：林铭炜

【摘要】闪存具有存取速度快、抗震性强以及功耗低等优势，已广泛运用于嵌入式系统和消费电子设备，因此闪存可能在未来成为取代机械硬盘的存储介质。但是目前由于闪存的读写不一致特性，针对硬盘开发的缓冲区替换算法无法直接应用于闪存，所以研发最适合闪存的缓冲区替换算法势在必行。本文根据基于概率和替换代价的原理，提出了一种基于预期的闪存缓冲区替换算法--AH-PBR算法。该算法采用了冷热探测机制、基于预期管理的概率替换机制和ARC硬盘缓冲区替换机制，使得本算法具有较好的性能。在通过对AH-PBR算法和国内外目前的闪存缓冲区替换算法进行对比测试，从命中率、物理读操作、物理写操作几个方面进行对比，并且附上了不同情境下的各个算法的性能，确保能全方位的展示AH-PBR算法的优势与劣势。相信本文能为以后更好更深入的研究闪存缓冲区替换算法提供独到的思路。

【关键词】闪存数据库，缓冲区替换算法，传统机械硬盘目 录

1. 引言 ...................................................................................1

1.1 研究背景与意义 ....................................................................1

1.2 本文研究内容 ......................................................................1

1.3 本文结构 ..........................................................................2

2. 相关工作 ...............................................................................3

2.1 经典的替换区置换算法 ..............................................................3

2.2 面向缓存的数据库缓存区置换算法 ....................................................4

3. AH-PBR算法详述 ........................................................................7

3.1 算法由来与结构 ....................................................................7

3.2 算法思路 ..........................................................................8

3.3 算法设计 ..........................................................................9

3.4 AD-LRU算法与AH-PBR算法实例分析..................................................11

3.5 本章小结 .........................................................................12

4. 实验设计与结果 ........................................................................13

4.1 实验目的、实验环境和测试方案 .....................................................13

4.2 命中率 ...........................................................................15

4.3 物理读操作 .......................................................................16

4.4 物理写操作 .......................................................................17

5. 结束语 ................................................................................19

致谢 .....................................................................................20

参考文献 .................................................................................21

1 1. 引言

1.1 研究背景与意义

在计算机应用方兴未艾的当下，计算机在各个领域有着独到的应用，解放了人类的思想，使人们有更多时间去思考和创造。对于计算机而言，存储介质[1]就好像人类的大脑，十分重要，因此存储器的性能直接关系到整个计算机的性能。目前市面上的较为普及的存储设备主要分为两种，机械式硬盘和闪存（电可擦除可编程只读存储器的变种）。

表 1-1 闪存固态盘与传统磁盘的对比参数

机械式硬盘具有较大的存储容量和相对低廉的价格，使得在选择大容量存储装置时多选择机械式硬盘，但是机械式硬盘因为涉及到机械活动，在随机寻找的时候需要移动磁头寻找目标所以难以快速找到。因此，在不需要频繁移动磁头的顺序读写过程中，机械式硬盘更优秀，但是随机读取需要不停的调整磁头的顺序，随机读取的性能往往不如人意。

闪存具有防震、噪音小、省电、代价不一致[2]、能耗低、快速的读写性能[3]、体积小、断电防丢失[4]等特征，可以弥补硬盘的缺点。NAND型闪存采用双层浮栅MOS组成，因为一个片内的原极是连接在一起的，每次擦除需原极加电压擦除，所以擦除需要整片擦除或分块擦除，因此因为整区删除的原因闪存的擦除的IO开销数量远远大于硬盘，这就是为何闪存读写删除操作的代价不一致的原因。随着物理材料学和电子工艺的发展，闪存的造价越来越低，存储容量和存储速度越来越快，闪存比传统磁盘有着更加广泛的应用前景，从这个趋势来看，基于闪存的存储器将比硬盘存储器发展的更快且占据更大的市场。因为闪存存储具有非易失性，在突然丧失能源提供后也能稳定的存储数据，因此可以与磁盘一样稳定存储数据。

由于传统数据库系统中的各类数据结构和逻辑算法都是针对磁盘开发的，没有根据闪存的擦除代价比读写IO开销更大的特征来设计，所以无法挖掘出闪存的全部潜能，甚至在一些极端情况下甚至表现出比磁盘更差的性能，因此全新的针对闪存的特征开发的算法有着较高的价值。

1.2 本文研究内容

根据闪存数据库[5]的读写代价不对称的特点和NAND型闪存整区擦除的特性，如何研究出在保证整体性能不变的情况下，提高命中率，降低物理读操作和物理写操作的数量是一件具有意义的事。

在研究目前国内外的缓冲区置换算法的时候，发现无论AD-LRU还是CCF-LRU还是FOR算法，都是基于当前的数据环境来设定数据页的权重，有点用数据页的频度和热度，有的用热区和冷区分开来防止不同的数据页，这些做法都是通过尽量长的使冷脏页驻留缓冲区来减少写操作代价，是有利于提升命中效率。但是本文也应该注意到一个关键性的问题，那就是脏页过长时间驻留缓冲区其实是减少了热数据页的存储介质 闪存固态硬盘 传统磁盘

内部组成 NANDFlash、控制IC 马达、碟片、磁盘、转轴

外观尺寸（cm） 60-67 65-68

重量（g） 48-90 98-115

读写功耗（w） 0.13-1.0 2.4-2.5

使用中抗震度（G/ms） >1000/0.5 250-275/2

未使用中抗震度（G/ms） 1500-2000/1 800-900/1

使用中噪音（dB） 0 2.9

平均延迟（ms） 0.2-0.4 8.33

持续传输速度（MB/s） 110

32-56 2 空间，这样又反过来降低了命中率，而且会引起连锁的读写操作。因此基于这个问题，本文设计了全新的自适应的高性能闪存缓冲区替换算法--AH-PBR算法（Adaptive High Performance Flash Buffer Replacement Algorithm），这个算法采用冷热探测机制、基于预期管理的概率替换机制和ARC硬盘缓冲区替换机制来更好的平衡冷脏页在缓冲区带来的益处和坏处，保证收益能大于代价，使得能尽量少的进行读写物理操作。

AH-PBR算法的替换思路很大一部分来源于适用于硬盘的ARC算法，因为硬盘不会出现读写代价不对称的状况，适用于硬盘的ARC算法将缓冲区分做了冷区和热区，分别用于放置只使用过一次的数据页和多次使用的数据页，但是并没有对数据页进行标注究竟何是冷还是热，是脏还是干净。因此始终替换最近最不常使用（LRU）端的数据页，这样就无法通过优先驱逐干净页获得更好的I/O性能，所以适用于硬盘的ARC算法在硬盘能获取较高的I/O性能但是在闪存环境下并不能获取较高的I/O性能的原因由来。

AH-PBR算法采用冷数据判断机制，缓冲区里面的数据页分为冷干净页，热干净页，冷脏页，热脏页。因为在闪存缓冲区内由于电压擦除和加压的过程时耗不一样，所以有着读和写不是一个数量级，因此进行读操作还是写操作对于闪存来讲就很关键。又因为本文的替换算法是始终替换最不常使用（LRU）端的数据页。因此在干净页中，替换冷干净页的代价比替换热干净页的代价来的高；在脏页中，替换冷脏页的代价比替换热脏页的的代价来的高。