一种新型分布式缓存系统―双层集群缓存

摘要： 为了提高系统的整体性能，基于内部网络用户访问时间的局部性和相似性，并结合现有的分布式缓存系统，本文提出了一种新型的分布式缓存系统――双层缓存集群。双层缓存集群系统分为网内集群缓存层和集群缓存层，采用双层缓存结构，充分利用现有内部网络资源，分散了的负担，降低了之间的通信开销，还增强了缓存资源的利用率，提高了用户请求命中率，降低了系统的整体资源消耗。

关键词：

中图分类号： TP391．4 文献标识码：A 文章编号：2095－2163（2011）01－0039－05

0引言

随着社会经济的发展，使用Internet用户的迅速增多，WWW服务即World Wide Web的流行，使得网络负载不断加重。同时，用户对网络的速度和效果愈加重视，对网络的访问质量提出了更多的要求，这对互联网服务提供商ISP（Internet Service Provider）提出了更高挑战。根据Internet上的统计资料表明，超过80％的客户经常访问20％的热门内容，因此构建、使用缓存是一个很好的解决思路[1]。

一般的局域网比较简单，在局域网内搭建一台服务器，当内网的某个客户请求某一个WEB服务时，首先向服务器发出请求，如果服务器存在相应的缓存副本，就会直接返回给客户端；否则，则向相应的WEB服务器请求。

构建可以大大提高请求WEB服务的效率，如果在局域网构建相应的服务器，可以有效地节省IP，保护局域网的内部网络安全，容易构建全面的审计功能。但是，随着网络的不断发展，众多的内部网络例如大学，大公司的局域网等不断扩大，构建单一的出口，会出现负载过重、单机故障等众多问题。因此，分布式缓存的提出无疑有效缓解了这个问题[2]。

本文主要分析了现有的两种分布式缓存架构，结合两种架构的优缺点，提出了一种新的分布式缓存架构―双层缓存集群。该架构可以有效地解决现存两种架构的缺陷，并能结合当前内网的用户行为和系统资源做出有效的预测、分析、协调和自适应，达到系统资源与用户请求总体的最优。

1两种分布式缓存模型

1．1ICP（Internet Cache Protocol）缓存模型[3]

对于这个模型，在整个缓存系统内部，采用ICP协议来进行询问通信，并处理请求响应信息。该协议广泛应用于Net Cache和Squid等多个软件中。对于该系统架构，提取一种典型情况如图1所示。

从图1可以看出，整个缓存系统架构的分布层次关系是树状的，Proxy0是根节点，Proxy1到Proxy5是子节点。相应的客户端向整个系统请求缓存数据的时候，是从最底层的子节点向上请求，如果该子节点存在相应的数据，直接返回；否则会向兄弟节点发送询问消息。如果所有的兄弟节点都没有，再依次向父节点请求；若仍没有，父节点再向其兄弟节点请求。依次向上进行，最后，若都没有，再向相应的Web服务器请求数据。

这种ICP缓存模型的特点就是通过发送大量的询问消息，期待获取缓存的存储信息，以及时向客户端反馈。

考虑到查询信息的规模性，因此，在大规模内部网络与大量请求的情况下，对带宽的消耗是十分严重的，同时查询的时延会增加。极端情况下，假设客户端请求的数据在整个分布式缓存系统中不存在，也仍然要发送大规模的查询信息，遍历所有的节点，显然效率较低。

1．2缓冲阵列缓存模型[4]

对于此种模型，比较有代表性的就是缓冲阵列协议模型CARP（Common Access Redundancy Protocol）。针对ISP的询问式架构产生的难以定位缓存位置的问题，缓冲阵列协议提出建立整体映射路由的方式来准确定位缓存存放位置。映射路由的建立是通过建立缓存索引与节点信息融合的方式来实现的，对于任意缓存，根据其索引值直接定位到某一特定存储节点。当下一次，即再次查询的时候，通过缓存的索引值，能够通过索引映射表准确定位到存储节点的信息，从而不必发送大量信息进行查询来定位。其整体的架构如图2所示。

当客户端向缓冲阵列缓存系统请求数据的时候，客户端首先向CM（总体控制器）发出请求，CM根据用户请求缓存数据的索引值，查询相应的索引映射表，直接定位到对应的服务器，从而返回客户数据。该系统维护一个特定成员的列表，该列表监视着对所有阵列节点发出的缓存数据请求，以便确定成员的状态，如果请求不成功，则本地节点会将该节点标记为寿命期内不可用，即请求不会再转发给该节点，直到下一次的查询到来为止。

该模型通过索引映射表的建立能够精确定位到节点的缓存存储信息，从而迅速找到目标缓存，不必发送大量的查询信息。但从另一方面来讲，因为CM控制节点的存在，导致所有客户请求首先向CM节点发送，这样CM节点的负载过高，容易出现单点故障。

2新的分布式缓存模型

针对ICP缓存模型和缓冲阵列缓存模型的优缺点，本文提出了一种基于全资源的集群缓存系统。该缓存系统整体上分为两层，分别是网内集群缓存层和集群缓存层。客户请求缓存数据，首先向网内集群缓存层进行请求，如果存在对应的数据，则返回给客户端；否则再向集群缓存层请求数据，如果集群缓存层没有数据的话，则再向外部服务器请求。双层集群缓存系统的系统架构如图3所示。

2．1网内集群缓存层

考虑对内部客户网络资源的充分利用，客户向外请求数据时候，首先针对内部网络发出请求，查看是否存在缓存数据的内部主机。如果存在的话，就不用再向外请求数据，这种情况对于特定时间段、特定人群的效率是非常高的。在大多数情况下，同一个内部网络的用户在职业状况、兴趣取向、请求的时间和周期方面存在一定的相似度[5－6]，这样就为设计网内集群缓存层提供了一定的理论和经验支持。

2．1．1总体设计

首先对所有的请求URL进行哈希，假设总共的URL数目是m，对所有的URL进行分散结构化，将其分成n组，同时对局域网内所有的主机分成n组，如图4所示，则第i组分散索引值的范围为[?m／n?i，?m／n?（i＋1）－1]。然后用户可根据URL的哈希值向CM进行请求，CM会根据网内集群缓存层索引表定位该URL的子组位置，从而提供给用户信息，用户再向相应的子组进行请求。网内集群缓存层索引表如表1所示。在系统初始化的时候，每个子组的主机数目相同，负责的URL索引值的范围也是一样的，这样就保证了每一个子组负责的缓存存储能力是一样的。但是，考虑到URL的访问频率的不同，相应的每个子组负责的访问负载和通信负载会有较大的不同，因此需要对整个缓存存储的拓扑结构进行动态调整。

2．1．2系统拓扑和缓存的更新

在系统初始化中，将子组主机数目和其负责的URL哈希索引值都设为相同，考虑到每一个URL的访问频率的不同，所以子组的访问负载和通信负载是动态变化的。针对这一点，需要对系统的拓扑结构进行动态的调整。

（1）依据页面访问频率进行均衡调整

（2）依据本组负载限值进行调整

针对组内访问频率的动态变化，考虑每一个组在某一时间段内对访问次数的负载是一定的，假设超过了这个限值，则要进行调整。策略主要有以下三种：

① 因为整个局域网存在着不同数目的候选主机，如果候选主机数目不为零，可以选入主机到该子组中；

② 根据LRU（最近最少使用）算法淘汰掉相应的缓存；

③ 根据频率的排序，移除频率较高的缓存，单独进行组网。

对于缓存的更新，采用设定TTL值的方法，超过TTL值的话就会对缓存进行更新。同时采用LRU算法淘汰掉访问频率较低的缓存，从而省出存储空间。

2．1．3客户请求处理过程

（1）系统初始化时，对URL建立了分散架构化模型，假设整体的索引值上限为m，将内部网络分为n个Group，则第i个Group分散索引值的范围为[?m／n?i，?m／n?（i＋1）－1]。

（2）某个客户端请求某一个缓存数据D，首先查看本机缓存，如果没有相应的数据或者数据的TTL到期，则首先对D的URL进行hash，再向CM机进行请求，CM机查看网内集群缓存索引表；如果索引表中存在对应的表项，则取出相应的GROUP＿ID和SPE＿ID，根据这两个值定位到存储D的主机的物理位置。

（3）客户端请求相应的组ID，考虑到某些缓存请求数目非常大，特定i组的所有主机一般对分散索引值[?m／n?i，?m／n?（i＋1）－1]范围内的缓存数据全部缓存。特殊情况下，特定缓存存储在特定的主机上，此时SPE＿ID就存储该主机的物理信息。相反，如果没有，就将SPE＿ID设为NULL。这样做有利于负载均衡。对于客户端请求D时，如果SPE＿ID为NULL，则随机请求该组内的任意一台主机，此时某台主机命中的概率为1（?m／n?i）。如果该主机命中，则返回给请求的客户端，否则再向集群缓存层请求数据。

2．1．4CM机工作机理

一方面，CM机接收客户请求，根据用户请求URL的哈希值和存储的索引表反馈用户存储节点的物理位置；另一方面，CM机要根据当前系统总体的访问请求情况，监视着所有客户机的运行状况，对整个系统的拓扑结构进行及时地更新。

2．2集群缓存层

如果用户在网内集群缓存层获取不到数据的话，就会向集群缓存层进行请求。和网内集群缓存层类似，集群缓存层采用分散式路由方式索引数据。这一点与缓冲阵列缓存模型也很类似。只不过缓冲阵列缓存模型存在总体控制器，通过总体控制器来协调索引数据。对于集群缓存层来讲，去除了这一控制器，由其中一台机来负责，这个机具有特定标识，例如IP值最小。如果这台机失效的话，马上调整为下一个具有标识的机器。

当用户向集群缓存层请求数据的时候，首先会向标识机进行请求，标识机根据用户请求缓存数据的索引值，查询相应的索引映射表，直接定位到对应的服务器，从而返回客户数据。该系统维护一个特定成员的列表，该列表监视着对所有阵列节点发出的缓存数据请求，以便确定成员的状态，如果请求不成功，则本地节点会将该节点标记为寿命期内不可用。以后请求不会转发给该节点，直到下一次的查询到来为止。

集群缓存层通过自动调整控制机，通过控制机的自动迁移，有效地预防了单点故障，增强系统的健壮性。

3几种分布式缓存模型的对比

本节将在用户请求的平均响应时间、缓存命中率以及系统整体性能方面对ICP缓存模型、缓冲阵列缓存模型和双层集群缓存模型进行对比和分析。这三个系统的内部主机系统的数量都设为m，主机的数目为n。

3．1用户请求的平均响应时间

用户请求的平均响应时间主要从以下这个公式来考虑：

Tm＝Ti＋ψTd＋（1－ψ）（Tb＋Ts）＋Tt （1）

在式（1）中，Ti为查询一个缓存信息所需的平均时间， Td为本机获取一个缓存所需要的平均时间，Tb为到上级缓存乃至原始服务器获取请求的响应所需的平均时间，Ts为在缓存中保存一个响应信息所需的平均时间，Tt为发送响应所需要的平均时间。

在这三种模型中，假设Td、Tt、Ts这三个变量相同，由于查询一个缓存信息所需要的平均时间主要是考虑本机里缓存的平均时间，且主要与本机缓存的存储查询算法有关，因此只考虑Tb即可。设Tclp为双层集群缓存模型用户请求的平均响应时间，Tarr为缓冲阵列缓存模型用户请求的平均响应时间， Ticp为ICP缓存模型用户请求的平均响应时间。

3．1．1ICP缓存模型

对于ICP缓存模型，总体的主机数目为n，假设建立了k层查询，如图1所示，考虑缓存存储的极端最差情况，缓存存储在第一层的主主机上，则需要遍历所有的主机，设一台主机查询的时间是Te，则：

Tb＝nTe（2）

取平均情况：

对于缓冲阵列缓存模型，由于总体控制器通过散列路由能够直接定位到缓存的信息，所以查询的时间为：

Tarrb＝Te（4）

3．1．3双层集群缓存模型

考虑双层集群缓存模型，首先查询网内集群缓存层，如果没有命中的话，再次查询集群缓存层，设网内集群命中概率为λ，则求得：

Tbclp＝λTl＋（1－λ）Te（5）

很明显，网内集群缓存层的单位查询时间Tl＜Te，推得：

Tbclp＜Tbarr＜Tbicp （6）

由总体的相应时间T＝C＋Tb，C是一个常数，由式（6）推得：

Tclp＜Tarr＜Ticp （7）

所以对比ICP缓存模型和缓冲阵列缓存模型，双层集群缓存模型的用户请求的平均响应时间最短。

3．2系统的整体处理开销

3．2．1缓冲阵列缓存模型

考虑缓冲阵列缓存模型的系统开销，首先查询CM机，这时的开销由于请求转发的消息少，可以忽略。考虑CM机的查询结果定位到缓存阵列中的其中一台机器M中，设s为一台机响应一个请求或应答一个请求的平均开销。分析两种情况：

（1）缓存存在M中， 则开销为2s；

（2）缓存不在M中，则需要向原始的服务器请求，并响应，因此总的开销为4s。

设Sarr为缓冲阵列缓存模型系统的系统开销，综上两种情况，则：

3．2．2双层集群缓存模型

考虑双层集群缓存系统模型的开销，类似缓冲阵列缓存模型，则推出网内集群缓存层的系统开销为

Stc＝2slcplc（9）

“集群”缓存层的系统开销为：

由式（15）， （16）推出

Sclp＜Sarr＜Sicp（17）

所以，对比ICP缓存模型和缓冲阵列缓存模型，双层集群缓存模型的整体处理开销最小。

4实验

为了测试系统的性能，本文采用最新的Wisconsin Proxy Benchmark2．0 平台进行模拟测试。测试结果如图5所示。

经过模拟实验可以看出，双层集群缓存模型比其余的两个系统整体的命中率提高4～7个百分点左右。

5结束语

分析了现有的两种典型的分布式缓存架构，提出了一种新的双层集群缓存架构。该系统充分利用内部用户访问资源的相似性和局部性，通过网内集群缓存和集群缓存的双层架构，加强双层集群的协调合作，增强了系统的稳定性和扩展性，充分利用了相邻节点现有资源，优化了缓存索引思路，在一定程度上提高了缓存命中率，降低了整体的系统开销。

参考文献：

[1] 姜彩萍，李子木，杨凤杰． 集中管理式Web缓存系统及性能分析． 微型计算机系统，2004，8（25）：1－2．

[2] 贺琛，陈肇雄，黄河燕． Web缓存技术综述． 微型计算机系统， 2004，5（25）：3－7．

[3] 林永旺，张大江，刘波． 一个基于集中管理的协作式Web 缓存 系统． 计算机研究与发展，2001，18（1）：1－5，12．

[4] MESSAOUD S，YOUSSEF H． An analytical model for the per－ formance evaluation of stack－based Web cache replacement al－ gorithms[J]． International Journal of Communication Systems，20－ 10，1（23）：10－18．

[5] 赵银春，付关友，朱征宇． 基于Web浏览内容和行为相结合的用 户兴趣挖掘． 计算机工程，2005，31（13）：1－2．

[6] 蒋在帆，王斌． 基于用户行为分析的个人信息检索研究． 中文信 息学报，2011，25（5）：3－5，12．

[7] TANG Ke，MEI Yi，YAO Xin． Memetic algorithm with extendedneIghborhood search for capacitated arc routing problems[J]． IE－ EE Transactions on Evolutionary computation，2009，9（13）：2－7．

[8] CHANG Chengyue，CHEN Ming－syan． Web cache replacement by integrating caching and prefetching[C]／／ Proceedings of the El－ eventh International Conference on Information and KnowledgeManagement． 2002，9．

[9] BENEVENUTO，Fabrício，DUARTE，et al． Web cache replaceme－ nt policies： Properties， limitations and implications [C]／／． Procee－ dings Third Latin American Web Congress． 2005：197－201．

[10] NEGM K A，AL－ALY M． Design of a remote controlled cach－ing proxy system ： architecture， algorithm and implementation[C]／／ World Scientific and Engineering Academy and Society． Stevens Point Wisconsin，USA： 2005：3－6．

[11] KHALED，ANEGM E． Distributed Proxy Cache Cluster Optim－ization Simulation System． WSEAS Transactions on Computers．2004，3： 1161－1166．