一种基于缓存对象未来价值的淘汰算法

任 飞， 汤 英， 段翰聪

(1.四川长虹电器股份有限公司， 四川 绵阳 621000；2.电子科技大学 计算机科学与工程学院， 四川 成都 611731)

随着Internet普及和网络应用的迅速发展，从Web Cache到内容分发网络(Content Delivery Network，CDN)，再到信息中心网络(Information Centric Networking，ICN)和内容中心网络(Content Centric Network，CCN)，分布式存储技术不断进步，其应用也有了显著的发展，但也面临着巨大的挑战：数据分布的地理空间更加广阔，数据存储容量呈爆炸性增长，数据的可靠性要求不断提高。分布式存储系统的构建必须解决“大规模、高效率、易扩展、高可靠”等系统性需求问题[1-4]。由于存储资源的限制，缓存替换策略对于提升文件系统性能尤其重要。一个最优化的缓存替换策略是能够根据未来价值高低找出最无用的缓存对象，进而淘汰处理，并可降低带宽开销和提高用户体验。

虽然缓存淘汰算法已经有很多研究成果，但都存在一定程度的不足。

(1)研究和应用最多的是LRU(Least Recently Used，最近最少使用)算法，将最近最久未被访问的对象淘汰。由于这种算法只考虑了缓存对象被访问的时间特性，忽略了对象的大小等其他因素，在块大小固定的情况下，大多数计算机系统工作良好，但在某些特殊场合存在很多限制，在访问大的对象时甚至可能崩溃，因此，不能提供最佳性能[5-7]。

(2)其次，是LFU(Least Frequently Used，最不常用)算法，将访问频度最低的缓存对象淘汰。由于这种算法只考虑了对象的被访问频次，对那些曾经高频访问，但近期已经过时的对象，也会被长期保留，造成缓存污染[6]。此外，当缓存空间总体较小时，LFU算法的性能也会降低[8]。

(3)再次，是SIZE算法，在缓存空间一定时，为确保存储更多的缓存对象，将占用空间最大的缓存对象淘汰[5-6]。这种算法只考虑了对象的大小，没有考虑时间和频率特性，会导致已经过时的小的数据对象长时间保留在缓存空间，同样会造成缓存污染。

(4)FIFO(First in First out，先进先出)算法，认为缓存对象中的第一个对象应该先被淘汰[7]，于是选择缓存空间中最早的对象淘汰。这种算法只考虑了对象缓存时长，没有考虑对象被使用的时间和频率特性，以及对象的大小，虽然算法简单，但应用价值不大。

(5)兼顾对象被访问的时间特性和频率特性的LRFU(Least Recent Frequently Used，最近最不常用)算法[8]，计算每个对象的CRF(Combined Recency and Frequency，最近和频率组合)值来确定近期被访问的可能性。CRF值由权重函数决定，通过调整函数因子寻找最佳性能。虽然LRFU实验结果优于LRU和LFU策略[8]，但没考虑对象大小，应用领域也存在一定程度的限制。

上述几种算法都是基于缓存对象被访问的概率来进行评估的，这也是基于回归预测缓存机制的重点。衡量一个缓存对象淘汰算法优劣主要有以下3个指标[6]：

(1)请求命中率：命中缓存对象的请求数量与全部请求数量的比率。

(2)字节命中率：缓存对象的请求字节数与所有请求的字节数的比率，这种评价指标更适于大对象，因为大尺寸对象被访问的次数可能较少，但被访问后将产生更大的数据流量。

(3)响应时间：用户发送请求和用户接收响应之间的时间。

一个理想的缓存替换策略应该最大限度地提高缓存命中率或字节命中率，并最小化响应时间[4-10]。为了实现这一目标，本文以使用分片的流媒体系统为研究对象，综合考虑缓存对象最近的访问时间、访问频次、分片优先级和对象大小等因素，提出一种基于最小未来价值(Least Future Value，LFV)的缓存淘汰算法，改进现有算法中存在的一些缺点，如抖动现象、缓存污染等，提升缓存性能。

1 设计思路

关键问题是如何确定一个缓存对象的价值。如果价值预测错误，可能出现抖动现象，即一个缓存对象被淘汰以后马上被请求，从而再次被缓存。理想情况下，在不久的将来被访问的价值应该比不被访问的价值大。

对象被访问的概率和对象的尺寸决定了对象未来的价值，对象未来的价值与被访问概率正相关，与对象的大小负相关，即被访问的概率越大其未来的价值就越大，对象的尺寸越小其未来价值越大(因为当存储空间一定时，对象尺寸越小，可存储的对象数量就越多，请求的命中率就越高，存储空间的价值越大)。一般情况下，我们是知道缓存对象的尺寸大小的，需要做的是确定对象被访问的概率。因此，基于LFV的缓存对象淘汰算法主要包括两部分：预测被访问的概率，规范缓存对象的大小。

(1)利用统计回归分析方法预测被访问的概率。首先，计算当前n个时刻的访问概率；然后，建立指数回归模型，并根据最小二乘原理计算两个待定参数；最后，根据指数回归模型预测对象在第n+1时刻被访问的概率。

(2)规范缓存对象的大小。假设缓存对象的尺寸太大而导致对象数量较少，对象的命中率将受到一定程度的影响。因此，在预测访问概率之前，每个缓存对象的尺寸大小需要规范化，将所有对象的尺寸大小控制在一定范围内。本文采用归一化方法对缓存对象进行规范化处理，采用权重函数来计算缓存对象的归一化尺寸大小。这样，对于确定的缓存空间，对象的数量将由对象归一化尺寸大小决定。

本文基于MATLAB进行算法开发、数据可视化、数据分析以及数值计算，文中所有截图示例均为MATLAB的输出结果。

2 概率预测

2.1 当前概率计算

用户的访问请求属于随机事件，缓存对象在周期内被访问的次数也是随机的，缓存对象的访问概率也具有很大随机性。为便于计算和记录每个缓存对象最近N次被访问的统计概率值p，我们为每个对象建立和维护了一个N元数组[p1,p2,p3,…,pN]。

定义1 设Δt为给定时间t附近的时间区间长度，某缓存对象α1在(t-Δt,t)被访问的概率为pt，REHt为对象α1在Δt内被访问的次数(Request Hits)，TORt为用户在Δt内发出的总的请求次数(Total Requests)，则pt表示为

pt=REHt/TORt。

(1)

设定一个合适的Δt值对于公式(1)的使用尤为重要。因为，数据的连续性决定了回归分析结果的可信度。数据的连续性即所有的数据都可以绘制在光滑曲线附近，越接近光滑曲线表示数据的连续性越强，预测结果越理想。可以通过选取合适的Δt来保证数据的连续性。

图1 Δt的3种选择方案

图2 选择不同Δt时的数据分布

设采样周期的大小为T，δ表示Δt和T的重叠情况，即δ=Δt-T。Δt的3种可能的选择方案如图1所示。

当δ<0时，即在相邻Δt间存在一定时间间隔，如前所述，对象的访问是一种随机事件，相邻Δt间的数据可能存在巨大差异，数据的连续性无法保证。

当δ=0时，相邻Δt首尾相接，同样存在相邻间隔内数据差异性大的问题，数据连续性仍无法保证。

当δ>0时，相邻Δt部分重叠，数据的连续性可以在一定程度上得到保证，数据连续性的强弱可能通过调整重叠部分的大小δ来实现，δ越大，数据越连续。

选择不同的Δt值时，如图2所示，用户请求数据的分布变化不大，但是，Δt越大曲线越平滑，回归分析效果越好。

为了定量分析光滑特征，消除单位和(或)平均数不同对两个或多个曲线变异程度比较的影响，比较其变异程度就不能采用标准差，而需采用标准差σ与平均数μ的比值来比较。标准差与平均数的比值称为变异系数，记为CV(公式表示为CV=σ/μ)，反映单位均值上的离散程度。通过计算3条曲线的变异系数CV，结果如表1所示，当δ>0，即Δt>T时，CV最小，曲线最平滑。因此，选择Δt>T。

表1 3条曲线的CV值

考虑实施的复杂性，在每个采样周期T中记录用户请求次数是容易的，如果Δt等于采样周期T的整倍数，例如2T、3T等，则公式(1)的计算将更容易。假设Δt=2T，即相邻Δt重叠长度δ=T(重叠率50%)，数据的连续性得到保证的同时，实现也较为简单。

2.2 回归预测

访问概率随时间而变化，很难预测在未来某一时刻访问的准确概率，未来某一时刻的概率只能根据过去的数据和行为来近似估计，本文使用回归分析方法来预测。回归分析的关键是选择一个近似回归模型，近似的标准是最大化相关系数。

2.2.1 相关分析

相关分析即研究自变量与因变量之间的关联度，是回归分析的前提。本文以时间t为自变量，访问概率p为因变量。关系包括线性关系和曲线关系(也称非线性关系)，时间与访问概率之间的关系是一种曲线关系，关系的判断标准是相关系数R。

(2)

对于曲线关系模型，相关系数的计算，第一步是确定回归方程，然后根据公式(2)计算相关系数R。R反映了因变量p和自变量t之间的密切程度，R越大，回归预测越有意义。

2.2.2 选择合适的回归模型

图3 泊松分布和实时数据

一个好的回归模型应该具有更大的相关系数。曲线的相关系数越大，曲线越接近真实数据。常见的曲线回归模型包括指数曲线、对数曲线、双曲线、幂函数曲线、S曲线、高阶方程等。较可靠的方法是计算所有曲线回归模型的相关系数，然后选择具有最大相关系数的模型，但是，这种方法的计算成本太高。一种合理的假设就是单位时间内的请求数服从泊松分布[9]。图3显示的用户请求数据分布类似于标准泊松分布。

定义2 设p为访问概率，q、m为待定参数，则指数模型可定义为

p=qemt。

(3)

2.2.3 模型转换

通过变量代换将公式(3)表示的指数回归模型转化为线性回归模型。对公式(3)的两边取对数，并设y=lnp和b=lnq，而进行变量代换后得到一元线性回归模型：

(4)

由b=lnq得q=eb，式(3)可变换为

(5)

当确定了m和b的参数值，就可以根据公式(5)进行概率预测。接下来的工作就是确定参数m和b的值。

2.2.4 回归分析

待定参数m和b可以通过最小二乘法估计确定，即找到合适的m和b使残差平方和最小。计算残差项平方和的公式为

(6)

根据最小二乘法原理，当m和b的偏导数分别为0时，φ达到极小值：

(7)

解方程组(7)得到：

(8)

2.2.5 概率预测

确定了参数m和b的值后，可以根据公式(5)预测下一时刻tn+1的对象被访问的概率：

pn+1=eb+mtn+1。

(9)

2.2.6 回归规模

在上述回归分析中，对于每个对象基于前n个时刻(t1,t2,…,tn)的已知数据(p1,p2,…,pn)预测下一时刻tn+1的访问概率pn+1，n代表回归规模，回归结果的精度与n的大小紧密相关。n如果取得太小，回归精度将下降，如果取得太大，虽然回归精度较高，但内存和CPU等计算资源消耗太大，会影响到系统效率。

2.3 缓存淘汰

当缓存空间不足或者系统定时器触发的缓存淘汰时，预测每个缓存对象的未来价值，并选择一定比例的未来价值最小的缓存对象进行淘汰。

2.3.1 未来价值估算

(10)

2.3.2 优先因子设定

在使用分片的流媒体系统中，文件被分成若干个分片(chunk)[11-15]，针对流媒体分片的优化在公式(10)中设置了优先级因子α，针对不同的分片可以设置不同的优先级。对流媒体的请求总是从第一个分片开始的，第一个分片的访问概率最大，因此，如果对第一分片给以最高优先级因子α值，用户请求的响应时间可以大幅降低，系统的响应效率也可以得到改善。比如，将首分片的α值设为1，其他分片的α值设定在0.6～0.8之间。

另外，访问概率p对未来价值fv估算起主导作用，优先级因子α的作用不应超过访问概率p。

2.3.3 对象大小规范化处理

(11)

2.3.4 缓存淘汰过程

缓存淘汰的具体过程如下：

步骤1：按公式(11)对所有对象大小进行预处理，在整个过程中只有一次；

步骤2：按公式(1)计算当前各个时刻t所有对象的访问概率pt(如前所述，计算时选择Δt等于采样周期T的整倍数)；

步骤3：按公式(4)的变量代换关系计算所有对象访问概率对应的y值；

步骤4：按公式(8)计算参数m、b的值；

步骤5：按公式(9)预测所有对象下一时刻的访问概率；

步骤7：在fv最小的缓存对象中，选择一定比例(比如20%)来执行淘汰操作。

3 仿真实验

3.1 复杂性分析

执行缓存淘汰操作，需要针对每个缓存对象计算其fv。fv的主要计算量是公式(8)，当确定了回归规模后，则n为一常数，因而，该算法的时间复杂度为O(x)，x为缓存空间内的缓存对象的数量，表明本算法的时间复杂度与缓存空间中的对象数量是线性阶的。

3.2 仿真结果

本文设计了一个模拟器来测试和验证该算法，并与其他两个淘汰算法：LRU和LP(Least Popularity，最小流行度)进行比较[10-11]，LP是最小流行度的缓存对象的淘汰。由于本文把流媒体文件分成大小相同的对象，除了最后一个对象可能要小一些，大部分对象具有相同的大小，字节命中率和缓存命中率是非常相似的。因此，本文主要对缓存命中率、访问时延，以及磁盘空间、内存和带宽等重要资源使用情况进行了计算和分析。

模拟器的输入数据是运营商网络中的业务数据，包括何时、哪些流媒体文件被请求、开始时间和结束时间。为了方便描述，将本文的缓存淘汰算法称为最小未来价值算法。图4展示了以1 min为周期3种算法的缓存命中率的比较，缓存命中率即将命中缓存对象(即分片)的请求数量除以所有请求数量。

根据图4，LFV在大多数时间比其他两种算法具有更高的命中率，这意味着保存的文件比在LFV淘汰的文件更有价值，可能的原因是LFV不仅考虑历史数据，还考虑了变化趋势，因此，它可以更准确地预测访问概率。

图5展示了3种算法的用户访问时延的比较。计算实际用户访问时延比较困难，本文以使用服务器之间的hop数来近似计算。例如，0跳意味着用户请求的文件在缓存服务器中，并且可以立即发送给用户，2跳意味着请求的文件将要从一个文件服务器传输到缓存服务器。

图4 3种淘汰算法的缓存命中率结果 图5 3种算法用户访问时延比较

图6 3种算法磁盘空间使用结果

根据图5，在开始时，3种算法对于没有足够的缓存文件具有相似的访问时延，但是随着时间的推移，LFV的接入时延变得比其他两个小。

图6显示了3种算法对磁盘空间使用情况的比较，从图中可以看出，因为算法的差异导致LFV与其他两条曲线存在一定的差异，但3条曲线表现出的走势相似，即他们对磁盘空间使用情况是相似的，表明3种算法的平均空间使用率无显著性差异。

图7显示了3种算法对内存资源使用情况的比较，从图中可以看出，LFV比其他两种算法消耗了更多的内存资源，因为LFV为每个缓存对象记录了n个概率(n为某个整数)，而其他两种算法只为每个缓存对象记录一个参数。

从图8看出，3种缓存淘汰算法的带宽使用情况非常接近，表明LFV对于减少带宽消耗是有限的。

图7 3种算法的内存使用情况比较 图8 3种算法的带宽使用情况比较

4 结 论

与现有LRU、LFU、SIZE等算法相比，本文提出基于回归预测模型的LFV缓存替换策略具有3个显著的优点：第一，避免缓存污染问题，只有最近n个时间间隔内的请求才会影响下一个缓存对象的淘汰；第二，不仅表达了缓存对象的流行度，而且表达了流行度的变化趋势，这是更有用的，例如，一些对象在最近n个时间间隔内有很大的访问概率，但是数据出现了一个意外的下行曲线，那么预测的概率将遵循下行曲线；第三，可以通过提高第一个分片的优先级，使用户请求的响应时间大幅降低，系统响应效率得以大幅提升。

实验数据表明，基于回归预测模型的LFV缓存替换策略比其他的缓存替换算法具有更高的命中率，但是牺牲了更多的系统资源，如内存。换句话说，这个算法用内存资源换来了预测精度。

对这一领域的研究，未来将尝试建立比泊松分布更多的其他回归模型，去寻找最优模型。此外，必须在实际工作负载中进行广泛的实验，以充分利用多种模式之间的实际性能。