分布式网络内置缓存优化技术研究

周锦程, 王浩畅

(东北石油大学 计算机与信息技术学院， 大庆 163318)

0 引言

随着云计算、大数据技术的不断发展，以分布式网络进行数据存储和应用已经成为互联网数据服务模式的主要形式之一。在分布式网络中，内置缓存策略决定了网络数据的传输性能，而目前分布式网络各节点缓存相对独立，无法充分的、高效的利用缓存资源。为此，对于分布式网络内置缓存的全局优化非常具有研究的价值。

网络内置缓存策略根据作用范围可以分为单节点缓存数据和多节点缓存数据。单节点缓存数据是依据节点本地缓存数据进行决策的单节点缓存策略；多节点缓存数据是基于复杂算法的缓存资源协商决策多节点协调缓存策略[1]。单节点缓存策略算法主要有页面置换算法LRU(Least Recently Used)、最不经常使用页置换算法lFU(least Frequently Used)等，多节点缓存策略算法主要为CLS(Concept Learning System)[2]。单节点缓存策略算法简单，但是不能反映全局网络中的数据传输特性，存在缓存数据冗余和频繁更替的问题；多节点缓存策略算法复杂，能够提高全网的缓存利用率，但是多节点协同具有较高的复杂度，网络服务器的压力较大。同时，分布式网络默认的缓存是网内节点独立、基于应用层无数据区分的全局缓存策略，这样会导致缓存中存在数据冗余和无法做到缓存资源高效利用的问题[3]。为此，研究如何降低缓存数据冗余度、提高有限缓存空间对数据频率缓存的比例、注重边缘化缓存、降低算法复杂度对于提高分布式网络缓存利用效率具有非常重要的现实意义。

1 分布是网络内置缓存数据放置分析

1.1 网络环境模型构建

在进行分布式网络分析时，由于网络环境的复杂化需要对网络环境进行简化和限定。在已有的研究中，潘越伟通过分析分布是网络数据传输模型，证实了无论是线性拓扑的网络结构还是树状拓扑的网络结构，其数据请求的命中率基本保持一致[4]。所以本文对网络环境模型形式化直接采用线性拓扑结构进行分析，构建单链路缓存数据分配模型如图1所示[5]：

图1 单链路缓存数据分配模型

如图1所示网络数据请求满足连续序列分布，随着数据序列的增长，请求频率逐渐降低，如果设分布网络存在K条单链路缓存节点，则其中一个节点k的数据请求概率可以表示为[6]式(1)。

(1)

其中，α为数据序列指数特征参数，α>1，k∈{1,2,…,K}。根据式(1)，α值越大数据请求分布越集中在热节点上；相反，α值越小则数据请求分布则数据请求分布越均匀。

在分布式网络中，其不同于传统网络能够建立完整的数据缓存，而是根据数据块分别缓存，如果假设数据块数量为δ，各路由节点具有相同大小的缓存空间n，节点k上的缓存数据集合为Ck，节点上的数据可以标记为Ck1，Ck2，…，Ckn。当网络节点接收到网络数据请求包后，查询本地是否已经缓存了数据，如果缓存了则继续接收请求，如果没有缓存则跳到下一个路由节点[7]。

1.2 缓存数据放置模型

根据网络环境模型分析，设Ckj为节点k上的某个数据，函数f(Ckj)为数据Ckj的数据序列，f(Ckj)分布满足齐普夫定律条件，g(Ck)为数据分布函数，计算公式表示为式(2)。

(2)

其中，1≤k≤N，1≤j，α为数据分布指数特征参数。

在节点k缓存请求获得数据，Pk为数据请求在k节点上的概率，如果在第一个节点，第一个节点上的概率为P1=g(C1)g(B)，如果第一个节点上未接收请求则转向第二个节点，第二个节点上的概率为P2=g(C2-C1)/g(B)，以此类推得到数据存储节点上的概率为式(3)。

(3)

其中，Rt为数据请求延时，如果经过n次跳转后接收请求则Rt=nt,由此可推算出请求的平均延时为式(4)。

(4)

根据式(3)可知，节点缓存数据冗余度较低时，则数据源服务器压力小，再结合式(4)可知，数据平均请求延时与缓存节点接收数据有直接的关系，数据缓存离请求节点越近，则请求延时越小。但是，由于受到缓存空间大小的限制，如果距离近的节点无法有足够的容量完全接收数据，那么则根据网络节点的热度逐渐接收，最大限度的降低数据的请求时间和网络的消耗。

2 基于数据频率的缓存优化策略

2.1 基于数据频率缓存策略

在发出数据请求时，数据源响应会经过路由节点传送给用户。如果数据请求的容量小于节点缓存容量，则不影响网络的响应效率，如果用户的请求数据不断的增加，分布式网络会将请求频率高的数据优先存储在离用户近的网络节点上。根据缓存数据分配模型(图1)保证网络运行稳定的前提下，Nod1节点缓存用户请求频率最高的n个数据f(C1)，当用户请求数据在数据集f(C1)中可直接得到Nod1节点缓存相应。Nod2缓存接收其他用户请求数据f(C2)。由此，数据频率策略将用户请求频率高的数据缓存到本地，但是并不会依据请求频率来替换原有缓存的内容，而是在统计最近时间段数据请求频率，考虑到数据频率衰减过程，数据频率策略在原有数据结构基础上增加请求记录表如图2所示。

图2 请求记录表

请求记录表记录节点接收到最近的N次请求。当数据请求CX在请求过程中，请求记录表数量达到了上限，则统计出CX在请求记录表中被请求的次数，并与其他数据被请求的次数做比较，当CX频率在请求记录表中的次数排在请求数据签名，则将CX缓存到节点中。

根据请求记录表，计算当前及诶单中数据频率高低，以数据请求次数作为衡量标准，最近N此请求中数据ci被请求的次数所占比例Ch(i)计算表达式为式(5)。

(5)

其中，δcout(i,j)为数据ci与请求记录表中的第j条数据ci相同时计数加1。

数据频率策略由数据频率计算、缓存数据替换和请求记录表三部分构成，数据频率计算根据公式(5)计算出数据的频率。当新数据到来时首先检查节点缓存是否已满，如果未满直接存储在缓存中，如果已满则计算数据的频率Ch(i)，判断数据ci的频率是否处于所有请求前列，如果是则将数据存储到该节点，如果不是则跳转下一个节点，维护当前节点请求记录表。

2.2 基于数据频率缓存优化

根据基于数据频率的缓存策略所采用的算法分为计算数据数据频率的算法，缓存数据替换算法和请求记录表维护算法构成，优化流程如下：

(1) 接收新缓存数据时检查CS表是否已满，若未满则将缓存数据添加到CS表中，若CS表已满则计算将要缓存数据的流行度Ch(i)；

(2) 判断新缓存数据流行度是否处于前m个受欢迎的内容，如果是则进行第(3)步，如果不会则跳到第(4)步；

(3) 按照LRU方案将新缓存数据存储到节点CS上；

(4) 根据新缓存数据更新RRT表，并采用FIFO原则对RRT表进行维护。

3 实验仿真

3.1 实验环境介绍

为了检验本文提出的基于数据频率的缓存优化策略具有一定的可行性，构建基于NS-3的ndnSIM仿真平台环境，ndnSIM是离散事件驱动网络模拟器。环境搭建要先安装boost-lib 1.55和python bindings 2.7，再安装NS-3 v0.4.3，设置路径后检查关键模块是否安装成功，安装R语言3.02并给R环境安装模块，最后进行运行测试，测试搭建成功后进行仿真。

实验采用了单链路拓扑(Single Path Network,SPN)结构和模拟真实网络的无标度网络拓扑结构(Scale-Free Network,SFN)[8]。SPN链路包括一个请求节点、一个数据源节点、10个网络节点，SPN链路网络结构如图3所示。

图3 SPN链路网络结构

SFN结构利用NetworkX工具生成50个节点的拓扑结构，将节点1和8作为资源点，叶子节点作为用户节点，其他节点为网络节点，SFN网络结构如图4所示。

图4 SFN网络结构

数据包路由采用ndnSIM的BestRoute路由策略[9]，用户数据请求满足Zipf-like分布[10]。在分布式网络中网络节点具有相同缓存空间大小，实验参数设置如表1所示。

表1 实验参数设置

3.2 性能评估标准

根据数据频率策略的组成本文选择定义数据请求延时、缓存接收率、缓存数据置换率作为性能指标。

内容请求延时可以反映出网络的访问效率，设请求的总次数为M，请求的时刻为Dreq，数据响应的时刻为Decho,则网络所有节点数据请求的平均延时为式(6)。

(6)

缓存接收率是指请求发出后到达数据源之前得到的数据响应，缓存接收率越高，则说明请求到达的越快，数据源的压力越小。记录节点i在时间段t内的数据请求缓存接收率总次数为NHit(i)，接收总次数为NMis(i)，网络中所有节点平均接收率为式(7)。

(7)

缓存数据置换率是指节点新旧数据替换出来的缓存比例，置换率越高则对服务器的压力越大。设节点i替换出的数次数为rmDate(i)，节点i接收到的数据请求次数为onDate(i)，缓存数据置换率为式(8)。

(8)

3.3 实验分析

此次试验划分为缓存数据分布试验、网络缓存接收率实验、数据请求延时实验和缓存数据置换率实验四组，基于数据频率缓存算法用OCPPC表示，最不经常使用页置换算法用LFU表示，页面置换算法用LRU表示,比较三种缓存策略。

(1) 缓存数据分布试验

此次试验α值1.9，仿真时间200 s，实验参数如表1所示，缓存算法运行平稳后，统计每个节点缓存数据序列平均值，观察缓存算法优化前后对比结果如图5所示。

图5 缓存数据分布对比

通过图5可以看出，节点2上的理论值为150.5，OCPPC缓存内容平均值为184，LFU缓存内容平均值为289，LRU缓存内容平均值为319。基于数据频率缓存算法OCPPC能够使链路节点上的缓存数据更接近理论最优数据分配结果，α越大数据请求越集中，数据频率大对数据分布的影响大。

(2) 网络缓存接收率实验

统计接收率与总请求次数的比值，得网络平均缓存接收率，α=1.9，网络结构选择单链路拓扑结构和无标度网络拓扑结构。单链路拓扑网络缓存接收率对比如图6所示。

图6 单链路拓扑缓存接收率对比

无标度拓扑网络缓存接收率对比如图7所示。

图7 无标度拓扑缓存接收率对比

通过图6和图7可以看出，运行到100 s时，0CPPC算法命中率72%，LFU算法命中率57%，LRU命中率43%，并且随着时间的增加命中率越来越高。由此可见，基于数据频率缓存算法具有较高的网络缓存接收率，相比单链路拓扑缓存无标度拓扑缓存所需的稳定时间较长。

(3) 数据请求延时实验

数据请求延时实验基于数据频率缓存算法序列小于100的数据延时约为30 s，可以在较近节点上请求到数据，基于数据频率缓存算法可以将访问频繁的数据缓存到距离请求者较近的节点上。在较大序列中，虽然请求延时页面置换算法优于基于数据频率缓存算法，但是基于数据频率缓存算法在大量请求记录统计中更加全面。平均数据请求延时对比如图8所示。

图8 平均数据请求延时对比

(4) 缓存数据置换率实验

用较低的缓存数据置换频率置换数据可以减少缓存的维护，α=1.9，缓存数据置换率对比如图9所示。

由图9可以见，算法置换率由高到低分别为页面置换算法、最不经常使用页置换算法、基于数据频率缓存优化算法。在前30 s，OCPPC缓存频率也是快速升高，但是OCPPC进行了自主学习，搜集内容请求逐渐减少，在100 s后换出率逐渐稳定。

图9 缓存数据置换率对比

4 总结

本文针对目前分布式网络采用单节点缓存存在的局限性问题和资源利用率不足的问题进行分析，探讨了数据放置的分析模型，并提出根据数据频率高低来进行缓存放置，数据频率策略根据请求记录构建数据的频率统计模型，依据数据频率在整个链路放置缓存数据，最后通过仿真实验证实了该策略的有效性，能够提高资源的请求效率、降低数据的请求延时和减少服务器的负载，在分布式网络缓存管理中具有较好的优化效果。