闪存数据库缓冲区置换算法综述

郑　开（西南大学 应用技术学院，重庆 401147）

闪存数据库缓冲区置换算法综述

郑开
（西南大学 应用技术学院，重庆 401147）

随着闪存技术的发展和闪存容量的不断增大，闪存存储被广泛应用，给闪存数据库管理带来机遇和挑战。因为闪存和磁盘读写方式不同，读写性能也有差别，所以对于闪存缓冲区的管理成为一个亟待解决的问题。为了提高闪存的访问性能，缓冲区置换算法在保证命中率的同时要尽量减少写和擦除操作的次数。对主流的闪存数据库缓冲区置换算法进行分析，比较了几种算法的优点和不足，并给出了未来研究的方向。

闪存；闪存数据库；缓冲区置换算法

0　引言

近年来，闪存存储作为新一代的存储介质，凭借其存写速度快、功耗低、体积小、抗震等优良特性，已经被广泛应用在嵌入式系统、航空航天以及各种企业级的数据存储系统中［1］。

由于闪存和磁盘在物理结构、数据存取方式等方面存在明显的差异，而现有的数据库系统中的各类数据结构和算法都是针对磁盘专门开发的，因此目前已有的基于磁盘的应用（如文件系统等）无法直接支持闪存而充分发挥闪存存储的优越性［2］。因此，针对闪存存储的数据结构和算法（如数据存储、索引、缓冲区管理等）都很有研究的必要。其中缓冲区作为闪存数据库的系统的核心组件，其替换算法更是一个比较热门的研究问题，受到深度的重视。

1　闪存及缓冲区管理算法

1.1闪存存储

闪存存储器一般可以分为NOR型和NAND型两种，其中NOR型闪存以字节为存取单位，按位进行访问，读速快，但擦除和写速较慢，主要用于存储程序和少量数据。NAND型闪存以数据页为存储单位，容量较大，价格低，主要用于存储数据。闪存硬盘中通常使用的是NAND型芯片。

闪存具备读、写和擦除三种操作，页是闪存读写操作的基本单位，而擦除操作则是以块为单位的。闪存与磁盘不同，具有异位更新的特点，即不能直接在某个有数据的数据页上进行写操作，必须先擦除才能写，即便是只更新数据块中的一个数据页也需要将整块数据擦除。这样频繁的擦除操作可能会使闪存的性能变得不稳定，故通常更新不会直接在原位上进行，而是将写和擦除操作均匀地分布在所有的数据块上。此外，闪存和磁盘在读写上的差异也很大，两者在I/O操作性能上的对比［3］如表 1所示，闪存写的速度总是比读的速度慢，在研究闪存数据库缓冲区置换算法时，必须对读写操作进行区分，以便达到更好的性能。

表1　闪存与磁盘I/O性能对比

1.2缓冲区管理算法

当系统发出读写数据页的请求时，缓冲区管理需要做如下处理：

（1）检查页表，判断请求页是否在缓冲区，若请求页在缓冲区则访问命中，直接读取所需数据并执行对该页的操作，否则访问脱靶（缺页），执行步骤（2）；

（2）检查缓冲区是否已满，若还存在可用空间则为请求页分配空间，读入请求页执行相关操作，否则执行步骤（3）；

（3）按照某种置换策略选择一页作为置换页，若该页是只读页则直接置换出内存，否则先将置换页的内容写回外存再读入请求页。

2　闪存的缓冲区置换算法

经典的磁盘缓冲区替换算法主要是根据数据访问的频度和最近性为设计原则，以追求高的访问命中率为主要目标。闪存与传统的磁盘不同，闪存的读写代价是不对称的，其随机写的代价远远高于其连续写的代价，传统的磁盘存储缓冲区置换算法通常假设存储设备具有相同的读写延迟，这些特性决定了闪存的缓冲区置换算法必须对读写操作进行区分，在保证命中率的同时尽量减少写操作，更好地提升闪存的整体性能。目前，关于闪存的缓冲区管理策略，有不少学者对其做了相关的研究，也取得了一些成果，现有的闪存数据库缓冲区替换策略主要分为基于页级和基于块级两类。

2.1基于页级的闪存缓冲区替换算法

2.1.1CFLRU

CFLRU［4］是PARK S Y等人最先提出的一种面向闪存缓冲区的置换算法。该算法在LRU的基础上充分考虑闪存读写延迟的非对称性，优先替换出缓冲区的干净页，减少闪存写操作和擦除操作的次数，从而提高闪存的访问性能，获得整体性能的提升。

CFLRU算法的基本思想是：把 LRU链表分为工作区和替换区，工作区负责维护最近访问的数据页，替换区则负责维护替换候选队列，替换时总是优先替换替换区中的干净页，若替换区没有干净页，则选择LRU链表尾部的第一个脏页作为置换页。在CF-LRU算法中替换区的大小是由窗口大小ω决定的。图1是CFLRU的一个例子。假设缓冲区最多只能同时容纳6个页，ω的大小为3。在某个时刻，一个访问请求p7到达，替换区中有干净页P5则优先替换出干净页，而不是替换LRU链表尾部的P6。

图1　CFLRU缓冲区置换策略示例

通过以上可以看出，CFLRU通过优先替换出替换区的干净页，在一定程度上可以有效地减少对闪存的写和擦除操作，提升了性能。但还存在一些不足：（1）很难确定一个合适窗口大小的值来适应不同的任务。ω的大小直接影响了置换算法的效率，ω过大缺页率则会增加，ω过小替换代价也会相应地增加。（2）当链表较长时，查找干净页作为置换页的代价会较高。由于算法在选择置换页时需要沿着链表反向查找干净页，当链表较长时查找代价会增加。（3）该算法没有考虑数据页的访问频率，访问频率作为数据页的一个重要特征，若不考虑访问频率过早地替换出频率高的干净页和过晚替换出频率低的数据页都会增加访问的开销，降低替换的效率。

2.1.2LRU-WSR

LRU-WSR［5］是一种对CFLRU改进的面向闪存缓冲区的置换算法。该算法不仅考虑了脏页的频度，而且对脏页的冷热进行区分，优先替换出干净页和冷的脏页，能够有效避免冷脏页长期驻留内存，减少写操作，提高访问效率。

LRU-WSR算法的基本思想是：为缓冲区数据页设置一个冷热标识位，标识位为1则表示该页为冷页，为0则表示该页为非冷页。算法在选择置换页时，首先检查该页是否是干净页或冷脏页，是则直接替换。若该页是非冷脏页，则将标识位置为1并把该页移到MRU端，再对链表LRU端数据页进行判断。当访问脏页时，则把标识位改为0。图2是一个LRU-WSR缓冲区置换策略示例，假设缓冲区最多只能同时容纳6个页，在某个时刻，一个顺序访问请求 p7、p1到达，则会替换出干净页P1和冷脏页P2。

图2　LRU-WSR缓冲区置换策略示例

LRU-WSR算法运用标识冷标识位的方法，区分脏页的冷热程度，在保证命中率的同时减少了写和擦除操作的次数，实验表明该算法较LRU、CFLRU等算法有较大的提升。虽然LRU-WSR有不错的性能，但仍存在一些不足，该算法只考虑了脏页的冷热属性并没有关注到干净页的冷热属性，干净页优先被替换出去，可能会导致热的干净页很快被置换出去而增加额外开销。在图2的例子中若考虑到P1是热的干净页，则优先置换出冷脏页P2而不是热干净页P1，当访问请求p1到达时则会直接命中，这样就减少了操作次数。

2.1.3AD-LRU

AD-LRU［6］是一种自适应的面向闪存缓冲区的置换算法。算法根据最近性和频度将缓冲区分为冷区和热区两个队列，冷区存放只访问过一次的数据页，而热区则存放至少被访问过两次的数据页。冷热区的大小是根据被引用频度动态调整的。当需要置换时并不是一味地选择冷区的数据页，而是根据一个下界值 min_lc来选择的，当冷区容量大于或等于min_lc时则选择冷区进行替换，相反则选择热区。

算法在选择置换页时，首先从冷区的LRU端开始查找干净页，若存在则直接替换，若不存在则判断冷区容量是否大于或等于min_lc，若大于等于则选择冷区的页面进行替换，若冷区容量小于min_lc则选择热区脏页。该算法综合考虑了最近性、引用频度等特性，既可以减少写的代价，而且还保持了高的命中率。但这种方法还是无法避免干净页刚读入缓冲区就被替换的情况。

2.2基于块级的闪存缓冲区替换算法

考虑到页级的置换策略可能会产生大量的存储碎片而引发频繁的写操作影响闪存的效率，学者们研究把缓冲区中相近的数据页以聚簇的方式分组成块，以块为单位将数据批量地置换出内存，以减少随机写的次数。

2.2.1FAB

FAB［7］是 JOH等人提出的一种针对装有闪存芯片的多媒体播放器、移动电话等具有典型顺序访问比较密集特性而设计的基于块级的闪存缓冲区替换算法。该算法将缓冲区中的数据以数据块的形式组织起来形成一个LRU链表（如图3所示）每个块包含了同属于这个块的数据页，当需要读取、更新或插入新的数据页时，则将该数据块放到链表的头部；当需要置换时优先选择数据页最多的块进行替换，若存在多个候选块则选择最近最少访问的块（即链表尾部的块）。

图3　FAB缓冲区链表结构图

算法对属于同一块的数据页进行聚簇，并以优先替换出数据页最多的数据块的方式来降低闪存的写和擦除操作次数，在某种程度上提高了闪存的整体性能。但该算法还存在一些不足，如当请求为顺序时，算法性能会较好，但当请求为随机时，算法的性能非常差，因此该算法只适用于顺序访问。此外，FAB在选择替换块时没有考虑时间局部性而是选择数据页最多的块进行替换，若缓冲区中有较多访问频率较高但数据页较少的块时，算法的命中率就会有一定程度上的降低，影响整个I/O性能。

2.2.2CLC

CLC［8］算法与 FAB算法一样，将所属同一块的数据页聚集起来形成一个数据块，并按一定的策略形成链表。与FAB不同的是，CLC同时考虑了替换块的大小和访问频率，优先替换出访问频率低且数据页最多的数据块。这种策略在保证命中率的同时减少了随机写的次数，提高了闪存访问的性能。

算法把缓冲区分成Size-Dependent LRU（SDLRU）和Size-Independent LRU（SILRU）两个链表，SDLRU存放访问频率较低的数据块，SILRU存放访问频率较高的数据块。当有新的数据块或某一数据块被访问时则将该数据块插入到SILRU的头部；当SILRU已满且有新的数据块时则需将 SILRU链表中尾部的数据块转移到 SDLRU中，然后把数据块插入SILRU的头部。通过这种方式可以把访问频率高的数据存放在 SILRU，访问频率低的则存放在SDLRU中。当SDLRU空间不足时，则优先替换出频率低且数据页最多的数据块。然而由于数据块中数据页的访问特性不同，有时若一个数据块中只有少数数据页经常被访问，其他多数的数据页虽然很少被访问也需要驻留在缓冲区，极易造成空间的浪费。

3　结论

随着软硬件技术的发展，闪存存储这种新型存储设备的出现给数据管理性能的提升带来了机遇和挑战。应用这种存储解决海量数据管理是数据库技术未来发展的主要方向。缓冲区管理是闪存技术的关键问题，是闪存数据库领域的一个研究热点。目前基于缓冲区的管理策略主要有基于页级和基于块级两类，两类置换策略都是在保证缓冲区命中率的同时，尽量减少写和擦除操作的次数，进而提高闪存的访问性能，但两种策略都还存在一些不足，性能还有很大的提升空间。未来还可以从数据的访问特性以及硬件特性出发研究更高效的缓冲区置换策略，更好地提升闪存的访问性能。

［1］CHANG L P，KUO T W.Efficient management for largescale flashmemorystorage withresource conservation［J］.IEEE Transactions on Storage，2005，1（4）：381-418.

［2］王江涛，赖文豫，孟小峰.闪存数据库：现状、技术与展望［J］.计算机学报，2013，36（8）：1549-1567.

［3］LEE S W，MOON B.Design of Flash-based DBMS：An in page logging approach［A］.Beijing：Proceedings of the ACMSIGMOD International Conference［C］.2007：55-66.［4］PARK S Y，JUNG D，KANG J，et al.CFLRU：A replacement algorithm for flash-memory［C］.Proceedings of the International Conference on Compilers，Architecture and Synthesis for Embedded Systems，Seoul，2006：234-241.

［5］JUNG H，SHIM H，PARK S，et al.LRU-WSR：integration of LRU and writes sequence reordering for Flash memory［J］.IEEE Transactions on Consumer Electronics，2008，54 （3）：1215-1223.

［6］Jin Peiquan，Qu Yi，HARDER T，et al.AD-LRU：An efficientbuffer replacementalgorithm for Flash-based databases［J］.Journal of Data＆Knowledge Engineering，2012，72（2）：83-102.

［7］JO H，KANG Ju，PARK S Y，et al.FAB：Flash-aware buffer management policyfor portablemediaplayers［J］.IEEETransactions onConsumer Electronics，2006，52（2）：485-493.

［8］KANG S，PARK S，JUNG H，et al.Performance trade-offs in using NVRAM write buffer for Flash memory-based storage devices［J］.IEEE Transactions on Computers，2009，58 （6）：744-758.

Buffer replacement algorithm for Flash-based database

Zheng Kai
（College of Applied Technology，Southwest University，Chongqing 401147，China）

With the development of Flash memory，the Flash memory is widely used，which takes opportunity and challenge to the management of Flash-based database.As the Flash memory is different from the magnetic disk in the way of read and write，as well as the performance of read and write，it is urgent to provide efficient buffer management for Flash memory.In order to improve the Flash memory access performance，buffer replacement algorithm should reduce the number of write/erase operations and retain a highbuffer hit ratio.This paper analyzes the mainalgorithmof buffer replacement for Flash-baseddatabase，compares the advantages and disadvantages of the algorithm，and gives future research directions.

Flash memory；Flash-based database；buffer replacement algorithm

TP392

A

1674-7720（2015）06-0007-03

2014-10-31）

郑开（1988-），女，硕士，助理实验师，主要研究方向：数据库与智能检索技术。