一种针对时间局部性访问的固态硬盘缓存算法*

张 剑 吴崇建 闵绍荣 杨子晨

（中国舰船研究设计中心 武汉 430064）

1 引言

随着人类对自然界了解的不断深入，以及建模技术、信息技术的不断发展，人类用数据抽象自然界中客观事物的能力逐渐增强，从而使得积累的数据呈现出领域越来越广、数量越来越多、类型越来越丰富的趋势。由于这些数据表现出不同的特点，因此在使用这些数据的过程中，存储系统的数据访问模式会不断变化。其中的一种典型数据访问模式就是时间局部性［1］。时间局部性访问有两个显著的特点：1）热点迁移［2］。随着时间的变化，数据热点区域会发生变化，在不同的时间段内不同存储区域的数据分别被频繁访问。2）访问频率变化。某段时间内特定的数据被高频次访问，而过了这段时间后该数据被访问的可能性大大降低甚至不再被访问。

为了有效应对存储系统中的时间局部性访问，本文针对内存、固态硬盘、机械硬盘构成的混合存储系统，设计了一种基于变化替换代价［3～4］的动态缓存算法DRCC，并将DRCC算法与多种主流缓存算法进行了测试对比。测试结果表明，与其他缓存算法相比，DRCC算法具有更高的读写效率。

2 相关研究

缓存算法主要解决数据的组织方式和容量满时数据的淘汰机制。国内外对于缓存算法开展了广泛研究。其中，比较经典的算法为LRU［5～6］算法、LFU［7］算法。由于固态硬盘具有区别于内存的特点，于是一些针对固态硬盘的缓存算法被提出，其中的典型代表就是CFLRU（Clean-First LRU）缓存算法［8］和LRU-WSR（LRU-Write Sequence Reordering）算法［9～10］。

LRU算法着重考虑数据是否最近被访问，通过一个队列来保留缓存页的访问时间信息，优先淘汰最久没有被访问的数据。如图1所示。

图1 LRU算法示意图

LFU算法着重考虑数据的访问频次，认为访问频次最低的页最不可能被再次访问，按照访问频次从大到小对缓存页进行排序，容量满时优先淘汰访问频次最低的数据。如图2所示。

图2 LFU算法示意图

CFLRU算法将链表分为工作区和淘汰区两个区域，工作区管理最近被访问的页，淘汰区管理即将被淘汰的页。当发生替换操作时，算法会在淘汰区中优先选择干净的页进行淘汰，如果淘汰区不存在干净的页，那么就把LRU端的脏页作为替换页。如图3所示。

图3 CFLRU缓存算法示意图

LRU-WSR算法将缓存页划分为三种类型：干净页，冷脏页和热脏页。脏页通过一个冷热标识进行冷热划分。发生淘汰时，判别LRU端的页类型：若为干净页或冷脏页，直接淘汰；若为热脏页，则将标记为冷脏页，并把该页插入MRU端，给热脏页一次被保留的机会。如图4所示。

图4 LRU-WSR缓存算法示意图

3 DRCC算法设计

3.1 数据记录结构

使用DRCC算法时，固态硬盘的数据按照两个队列进行组织：预约队列和最小代价优先队列，如图5所示。

图5 预约队列和最小代价优先队列示意图

两个队列的内涵分别如下：

1）预约队列

预约队列记录刚被访问不久的数据块。当数据块初次被访问加入到固态硬盘中时，先将其加入固态硬盘的预约队列中，预约队列使用LRU算法排序。

2）最小代价优先队列。

最小代价优先队列记录从预约队列中筛选出来的达到一定访问次数阈值的数据块。最小代价优先队列以替换代价为标准进行排序。最小代价优先队列中的数据被访问会重新计算其替换代价，根据替换代价插入到队列的相应位置。

计算数据块的替换代价以及对最小代价优先队列进行排序会带来较大的开销，一定程度上会影响整个存储系统的性能。为此通过降低代价计算复杂度和排序复杂度，在不影响命中率的前提下，牺牲部分热数据的排序精确度来降低系统开销，从而获得性能的提升。最小代价优先队列采用最小堆［11～12］的形式进行不完全排序，以完全二叉树的形式，每次只确定最小代价的根节点位置。

最小代价优先队列的长度设置要适中，才能使得算法更能适应时间局部性的数据访问特点。最小代价优先队列的长度设置过大，会使很多变冷的数据污染固态硬盘缓存空间；最小代价优先队列的长度设置过小，则会造成热数据的频繁替换，增大替换开销和对底层存储的读写次数。因此，需要给最小代价优先队列设置一个合适的长度。假设固态硬盘的容量为V，默认设置最小代价优先队列的最大长度为，具体取值可以根据实际情况动态调整。

3.2 替换代价计算

替换代价计算方法如式（1）所示：

式（1）中各变量的含义如下：

CR代表最小代价优先队列中数据块的替换代价；dircost代表写操作和读操作的时间开销比；accenum代表数据块访问次数；accedis代表数据块最近一次访问到现在的时间间隔。

在计算替换代价时，对于缓存中的脏数据，需要乘上写读操作的开销比dircost，给脏数据块更多保留在缓存中的机会。

具体实施时，由于热数据会随着时间迁移，所以将最小代价优先队列中的数据块访问次数计算考虑时间间隔的因素，同时设置老化周期定时将数据访问次数右移一位，避免在过去时间内访问次数积累较多而现在已经变冷较少被访问的数据块一直占据缓存空间，造成新加入的较低访问次数热数据被替换的情况。

3.3 数据组织方法

当数据被访问时，根据被访问的数据是否已经存在于固态硬盘中，存在两种情况。不同的情况会有不同的数据组织流程。

1）当被访问数据不在固态硬盘时，数据组织流程如图6所示。数据被访问后，将其提取到固态硬盘的预约队列中，并按照LRU算法进行数据的组织。

图6 被访问数据不在固态硬盘时的数据组织流程

2）当被访问的数据存在于固态硬盘中时，数据组织流程如图7所示。若数据被访问时存在于预约队列中，则检查其访问次数是否达到阈值，若达到阈值，则将其提升到最小代价优先队列中，计算其替换代价，并在最小代价优先队列容量满时淘汰替换代价最小的数据；若未达到阈值，则继续保留在预约队列，并按照LRU算法进行排序。若数据被访问时存在于最小代价优先队列中，则重新计算其替换代价，再次确定替换代价最小的数据。

图7 被访问数据在固态硬盘时的数据组织流程

可以看出，预约队列和最小代价队列都有各自的淘汰方式，最小优先代价队列并不等待预约队列为空时才开始淘汰数据。这种数据淘汰方式考虑了时间局部性数据热点迁移的特点，能及时将变冷的数据块淘汰出固态硬盘，避免缓存空间污染［13］。

4 性能测试与结果分析

4.1 测试方案

测试时存储系统的实现基于开源的iSCSI（Internet Small Computer System Interface，Internet小型计算机接口）［14～15］代码。i SCSI是当前存储界的热门技术之一，其使用TCP/IP协议，用广域网仿真高性能本地存储总线，从而创建了一个存储局域网。内存、固态硬盘、机械硬盘构成的混合存储系统安装在作为iSCSI目标端的存储服务器，客户端通过iSCSI发起端将读写请求负载发送到iSCSI目标端的存储服务器。

测试时将本文中所提的DRCC算法与经典的LRU算法、LFU算法，以及针对固态硬盘的高效算法CFLRU进行比较，以证明DRCC算法的优势。

4.2 测试环境

测试环境配置如表1所示。根据测试数据集的大小，通过代码进行控制，将用于测试的混合存储系统的内存大小设置为500M，固态硬盘大小设置为1G×3，机械硬盘大小设置为20G×6。

表1 测试环境配置

4.3 测试数据

测试数据通过模拟产生，在某个服务器部署待访问数据，通过另一个客户端对其进行时间局部性访问。通过访问记录收集工具记录一段时间之内服务器的访问情况。为了充分反映数据的访问特点，记录约120h的数据。

表2所示统计了以1000、5000、10000、20000次访问为数据第一次访问起点，数据被再次重新访问的平均距离。

表2 平均重用距离统计

从表2可以看出，数据以20000次访问为数据第一次访问起点时，平均重用距离相比较以10000次访问为起点时陡然增大了约7倍，这与时间局部性访问的特点非常相符，热数据在一段时间内被频繁访问过后，热度迅速降低甚至不再被访问。

4.4 测试结果

1）每小时平均IOPS对比测试

DRCC算法与LRU算法、LFU算法、CFLRU算法的每小时平均IOPS的测试结果如图8所示。

可以看出，DRCC算法的每小时平均IOPS绝大多数时间都要高于LRU算法、LFU算法、CFLRU算法。

图8 每小时平均IOPS测试结果

2）总平均IOPS对比测试

DRCC算法与LRU算法、LFU算法、CFLRU算法的总平均IOPS的测试结果如图9所示。

图9 总平均IOPS测试结果

可以看出，存储系统运行一小段时间后，DRCC算法的总平均IOPS就开始表现出明显的优势，而且随着时间的推移，这种优势进一步扩大。在总平均IOPS方面，相比较于LRU、LFU、CFLRU三种算法，DRCC算法的提升幅度均超过了10%。

5 结语

本文针对内存、固态硬盘、机械硬盘组成的混合存储系统中的时间局部性访问，设计了一种高效的缓存算法。该算法通过预约队列和最小代价优先队列实现数据的组织，同时两个队列分别进行数据的淘汰，充分解决了高时间局部性数据热点迁移所带来的缓存污染问题。测试结果表明，该算法不仅比经典的LRU算法和LFU算法更有优势，而且相比较于针对固态硬盘的高效缓存算法CFLRU，同样表现出较大的性能提升。