一种针对混合存储系统的高效缓存算法∗

张 剑

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

1 引言

随着科技的发展，固态硬盘（Solid State Drive，SSD）［1～2］作为一种拥有高速I/O、低能耗等优点的新型存储介质，在存储系统中得到了广泛应用。然而，固态硬盘相对机械硬盘（Hard Disk Drive，HDD）来说有着寿命相对较短以及小写放大等问题，考虑到数据安全要素，一般不采用完全替代机械硬盘的方式使用固态硬盘，而采用固态硬盘作为缓存来构建混合存储系统，在提升性能的同时保证系统数据的持久安全性。

为了实现系统数据存储的更好管理与I/O性能提升，本文针对内存、固态硬盘、机械硬盘（实际使用中一般采用磁盘阵列）构成的混合存储系统，设计了一种兼顾时间局部性和空间局部性的缓存算法ODCA（Order Distance Cache Algorithm），并在特定的架构下进行了该算法的性能测试。测试结果表明，ODCA算法可以显著提高混合存储系统的I/O效率，并且具有较强的稳定性。

2 相关研究

2.1 混合缓存系统研究

国内外有很多采用固态硬盘作为二级缓存构建混合存储系统的研究，典型的系统包括SieveS⁃tore系统［3］、OP-FCL系统［4］。

普渡大学的Pritchett等提出了SieveStore混合存储系统，系统使用1个固态硬盘为多个机械硬盘服务器做缓存，并通过两种不同的方案来识别服务器中的热数据：离线、离散分配方法SieveStore-D，通过写入日志的方式精确记录一个时间段内每个数据块的访问次数，当时间段结束后，在离线状态下完成访问次数的整合，把访问次数超过门限的数据块缓存到固态硬盘；在线、连续分配方法SieveS⁃tore-C，在一段时间内，当对某个数据块的访问丢失连续达到一定次数后，则将它缓存到固态硬盘。

Yongseok Oh等提出了OP-FCL（Optimal Parti⁃tioning flash，最佳点闪存）混合存储系统，系统使用固态硬盘作为机械硬盘的缓存，并根据系统的性能变化，合理划分固态硬盘存储空间，以达到性能最佳。该系统将固态硬盘存储空间分为两部分，一部分是数据缓存空间，用来存放数据，另一部分是预分配空间，用来垃圾回收。通过适当分配两个空间的大小，提高系统的性能。预分配空间增大时，数据缓存空间减小，缓存性能下降，导致系统性能降低，但同时数据更新开销减小，使得系统性能提升，如图1所示，最终会存在一个最优点使系统性能达到最优。

2.2 缓存算法

内存的缓存替换算法已经相对成熟，例如LRU［5］、LFU［6］、MQ［7］等，但由于固态硬盘具有区别于内存的特点，于是一些针对固态硬盘的缓存算法被提出。

Seon-yeong等提出一种 CFLRU［8］（Clean-First LRU）缓存算法。如图2所示，算法将链表分为工作区和淘汰区两个区域，工作区管理最近被访问的页，淘汰区管理即将被淘汰的页。当发生替换操作时，算法会在淘汰区中优先选择干净的页进行淘汰，如果淘汰区不存在干净的页，那么就把LRU端的脏页作为替换页。

图2 CFLRU缓存算法示意图

Hoyoung Jung等基于CFLRU算法进行改进，设计了 LRU-WSR［9～10］（LRU-Write Sequence Reorder⁃ing）算法。如图3所示，算法将缓存页划分为三种类型：干净页，冷脏页和热脏页。脏页通过一个冷热标识进行冷热划分。发生淘汰时，判别LRU端的页类型：若为干净页或冷脏页，直接淘汰；若为热脏页，则将标记为冷脏页，并把该页插入MRU端，即多给热脏页一次被保留的机会。

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

3 算法设计

为了提高缓存的命中率，针对内存和固态硬盘两级缓存，ODCA缓存算法设计均采用尽可能满的方式，以确保更多的数据留在缓存中，提高系统性能。ODCA缓存算法对时间局部性和空间局部性均进行考虑，并结合LRU和LFU的特性，采用一个热度值来表示数据页的热度。系统从运行时开始记录累计有多少数据页提取到缓存中，该值命名为S值（Sum），并对缓存中的每个数据页记录如下信息：

1）O值（Order）：该页最近一次被访问时系统的S值。

2）D值（Distance）：该页最近一次被访问时系统的S值与该页当前O值之差，若该页刚被提取到缓存中，则D值为无穷大。

图4为O值及D值的一个示例，假设初始状态（S=0）下缓存中无数据，系统依次读取1、2、3、4、3、1、5页。

图4 O值D值示意图

显然，对于数据页来说，O值是反映数据最近是否被访问的度量，数值越大，说明其越近被访问；D值是反映数据访问频度的度量，数值越小，说明其越频繁被访问。ODCA算法将二者相结合，使用权值公式来对缓存数据的冷热进行判断，得出每一个数据页的热度值。热度值的计算方式如式（1）所示。

其中k为系数，用于调整LFU和LRU之间的权重关系；udisk表示数据页存储设备在系统中所占的权值，通过这一值的设定，可以将热数据缓存算法和多个固态硬盘之间的负载算法相结合，负载重的固态硬盘IO带宽较小，存储在其上的数据页可以拥有较低的缓存权值，从而降低设备的I/O请求数量，提高系统整体性能。udisk值设定如表1所示。

表1 固态硬盘权重设定表

4 性能测试与结果分析

4.1 测试系统架构

测试系统的缓存由内存与固态硬盘组成，内存进行一级缓存，固态硬盘进行二级缓存。考虑到机械硬盘和固态硬盘具有不同的存储特性，将内存划分成两个区域（机械硬盘内存区和固态硬盘内存区）分别进行管理。测试系统的结构及数据流向如图5所示。整个系统中数据页的热度值均采用ODCA算法进行计算。

图5 测试系统的架构及数据流向

机械硬盘内存区只缓存机械硬盘中的数据。数据在机械硬盘内存区缓存期间，若其热度值达到了事先定义好的阈值，则将其提升至固态硬盘内存区；在机械硬盘内存区空间不够而发生数据淘汰时，选择热度值较低的数据，如果其为干净数据，则直接淘汰，如果其为脏数据，则将数据同步到机械硬盘后淘汰。

固态硬盘内存区缓存固态硬盘中的数据以及从机械硬盘内存区提升上来的数据。数据块在固态硬盘内存区缓存期间，完成对数据块的冷热区分。发生数据淘汰时，固态硬盘内存区将小写合并成大写后再一次性写入固态硬盘，减少对固态硬盘的写操作，从而延长固态硬盘的寿命。

4.2 系统实现

系统实现基于开源的 iSCSI［11～12］代码。iSCSI是当前存储界最热门的技术之一，其使用TCP/IP协议，本质上就是用广域网仿真了一个常用的高性能本地存储总线，从而创建了一个存储局域网。系统实现主要包含以下模块：固态盘内存区缓存模块、机械硬盘内存区缓存模块、固态盘缓存模块、机械硬盘内存区数据提升模块、机械硬盘读写模块。

4.3 测试环境

iSCSI的客户端、服务端均在Linux服务器上进行部署。具体测试环境配置如表2所示。

表2 测试环境配置

4.4 测试对象与数据集

采用blktrace工具集进行测试。blktrace是一个针对Linux内核中块设备I/O层的跟踪工具。具体测试时，采用blktrace工具集中的btreply回放工具对微软公司服务器的一周实际请求trace进行回放测试。由于真实trace时间过长，测试过程中采用64倍加速的方式进行回放测试。blktrace测试配置如表3所示，测试trace的基本情况如表4所示。

表3 blktrace测试配置

表4 测试trace基本情况

4.5 测试结果分析

4.5.1 每小时平均IOPS性能测试

每小时平均IOPS测试结果如图6、图7、图8所示。

图6 性能测试结果（rsrch，每小时平均IOPS）

图7 性能测试结果（usr，每小时平均IOPS）

图8 性能测试结果（web，每小时平均IOPS）

可以看出，在拥有不同I/O访问特点的多种trace下，混合存储系统在ODCA缓存算法下每小时平均IOPS大部分时间都要高于LRU及LFU缓存算法，印证了ODCA缓存算法的高命中率和稳定性。

4.5.2 总请求IOPS性能测试

总请求IPOS测试结果如图9、图10、图11、图12所示。其中图9、图10、图11表示的值为从系统启动运行到每一个测试时间点（每个小时一次）的总请求IOPS；图12表示的值为总测试时间（168h）内的总请求IOPS。

图9 性能测试结果（rsrch，总请求IOPS）

图10 性能测试结果（usr，总请求IOPS）

图11 性能测试结果（web，总请求IOPS）

图12 性能测试结果（总测试时间内总请求IOPS）

从图9、图10、图11可以看出，系统运行一段时间后混合缓存系统在ODCA缓存算法下总请求IOPS即优于LRU和LFU缓存算法，而且随着时间推移这种优势越发明显。从图18可以看出，对于rsrch、usr、web三种trace，混合缓存系统在ODCA缓存算法下总请求IOPS分别比LRU缓存算法提高了10.89%、27.27%、20.70%，分别比LFU缓存算法I/O性能提高了1.82%、21.74%、40%。

4.5.3 测试结果分析

rsrch的I/O访问特点是对热数据的短时间高频次访问，对于这类数据访问，ODCA算法性能高于LRU算法，与LFU算法基本相同。

web的I/O访问特点是热数据的访问间隔较长，对于这类数据访问，ODCA性能大幅度高于LRU和LFU。

综上所述，相对于经典的LRU和LFU缓存算法，ODCA缓存算法能更大程度提高混合缓存系统I/O性能，且对不同特点的I/O请求都有较好的适应性。

5 结语

随着大数据时代的发展，人们对存储性能的要求越来越高，固态硬盘作为一种高性能缓存介质，在各类存储系统中得到越来越广泛的应用。本文针对内存、固态硬盘、机械硬盘构成的混合存储系统，提出了一种结合LRU和LFU算法优点、综合考虑数据时间局部性和空间局部性的ODCA缓存算法。通过测试发现，对于不同特点的I/O请求，ODCA缓存算法均优于LRU和LFU算法。