HSCM：P2P网络中的热点缓存机制

龙海建 王博 陈剑勇

（深圳大学，计算机与软件学院，深圳 518060）

摘要：本文首先阐述P2P系统低效的搜索和路由机制以及就该问题所提出的缓存机制的弊端，继而根据网络中关键字分布普遍存在着热点的现象，提出基于节点行为的热点缓存机制（Hot Spots Caching Mechanism，HSCM）。通过对Chord算法的仿真显示，该机制的应用可以有效地减少热点请求的响应时间和所需的通信量，明显提高了P2P系统的性能。

关键词：热点缓存；对等网络；哈希表

HSCM：Caching Mechanism in the P2P Network

Long Haijian，Wang Bo，Chen Jianyong

（College of Computer and Software Engineering，Shenzhen University，Shenzhen，518060）

Abstract： The traditional P2P applications consume a lot of network bandwidth resource because a large number of communicating messages are transmitted continuously on the network to maintain the P2P overlay network.Based on the hot spots principle in the network，we propose a simple and effective caching mechanism called Hot Spots Caching Mechanism（HSCM）which stores the key and IP address of the responsible node of the key.With this method，the query node can get the latest information of the key.HSCM can be implemented to most of the structured P2P algorithms in a distributed environment to reduce the communicating message and the time delay.We implement the HSCM to the Chord algorithm to evaluate the performance of the HSCM.Our simulation results shows that the HSCM can significantly reduce the traffic of communicating message with the small cache space in every hop.

Key words： Peer to Peer（P2P），Distributed Hash Table（DHT），Hot Spots Caching Mechanism（HSCM）

1 引言

随着网络的发展和个人计算机性能的提升，作为一种新兴的互联网技术，P2P突破了传统C/S的限制和瓶颈，成为当今热门的研究对象。网络上的资源虽然丰富，但较为分散，因此如何快速而准确地查找到资源节点，是结构化P2P网络搜索协议的重心所在。

在结构化P2P网络中，目前应用最广的是DHT技术，它以索引的形式记录所有的资源。整个网络所有资源的索引可以形成了一张大的哈希表，而每个节点按照一定的规则各维护一张小哈希表，特定的资源由特定的节点管理。每个节点需要维护具有特定联系的邻居节点列表。这样在网络中查找特定资源就只需要在一张哈希表中查找对应的关键字索引即可。在本文中，我们把Key的后继节点称为目标节点，把存储含有Key文件的节点称为资源节点。

过去的理论根据覆盖网的网络拓扑结构和路由策略的不同，建立的不同的搜索协议，解决了在分布式环境中如何快速而准确找到目标节点的问题。但是为了找到目标节点，查询消息在覆盖网中需要经过O（log2N）或O（dN1/d）步路由。这就导致了大量的查询信息和节点路由表维护信息在网络中多次转发，占据了网络的大量带宽资源，增加底层网络的通信量和增加查询的延迟。本文提出基于Chord协议的热点缓存机制，明显减少维护P2P网络所消耗的带宽资源。

2 基于Chord协议的热点缓存机制

2.1 关键字热点分布

网络中热点关键字分布规律即关键词的流行程度往往符合Zipf_like分布，我们系统中模拟的查询关键字序列的分布情况如图3-1所示：查询关键字序列是由符合Zipf_like分布的函数产生。其中，函数Maxint（x）是求不大于x的最大正整数。参数c是常量，在我们的实验中取c=10，000。参数d可以调节关键字的分布情况，叫做关键字分布因子。Gauss是高斯函数产生的双精度的高斯随机数，这些随机数服从标准正态分布。

2.2 算法步骤

我们依据前面介绍的热点关键字的分布情况，从发起查询节点入手（简称发起节点），提出热点缓存机制HSCM，在不增加网络开销的前提下，通过给节点增加一个热点缓存，来减少P2P系统网络开销的目的。HSCM对Chord算法改进的具体细节如下（节点Nk中的下标k是节点的实际地址的哈希值，即节点的ID，后面的Nx、Ny等也一样）：

在我们的系统中，Key关键字列表，即<key，values>按照Chord的方法发布在目标节点上，用Nk表示。（Nk是Successor（key））。节点Nk的地址为<IP（k），Port（k）>。若发起节点Nx查询key成功，会在自己的缓存中存放目标节点地址，即<Key，IP（k），Port（k）>。

该算法从发起节点的cache开始查找，如果并未查找到即将查询信息按照Chord协议的方式传送到下一个节点进一步查询；中间节点如果在cache中找到相应记录，则对cache信息进行更新，新查询的热点关键字所代表的优先级设为最高，其余关键字查询优先级降一级；若中间节点并未查询成功，则将此查询按照Chord协议传送到下一个节点；至于目标节点收到查询请求之后，需要将步跳数的信息返回给发起节点，进行cache更新。

采用该方法，网络中含有关键字key文件的资源节点地址若有变更，Chord协议只会对目标节点Nk中的<KeyValue>进行更新。由于Nx的缓存中存放<Key，IP（k），Port（k）>，而不是<key，value>，可以确保后续发起节点所获得的<key，value>都是最新的。

热点缓存单元由HotSpot[]、Count[]两部分组成。HotSpot[i]是用来存放目标节点地址<Key，IP（k），Port（k）>，记录着热点关键字的索引信息所在的目标节点的地址。数组元素Count[i]的值是相关热点关键字的优先级，优先级越高的值越小，相反，值越大就表示优先级越低。

热点缓存中的信息是不断被更新的，初始的时候关键字的优先级取值为0，以后Cache中若有关键字被更新一次，该关键字的Count[i]的值为0，所有其它关键字的Count[i]的值就增加1.当缓存容量满了以后，我们采用最少使用替换算法（LRU）进行更新。也就是缓存中Count[i]值最大所对应的key被替换。新关键字进入缓存后优先级最高，其Count[i]设为0。

3 仿真与分析

为了验证我们上面所设计的HSCM的效果，我们将对Chord原系统和包含HSCM的改进系统进行模拟仿真，并统计查询的平均步跳数。我们仿真模拟平台是：Window XP+Peersim1.0.2+jDK 1.5.0_04。实验进行查询模拟时，网络中每个节点都会进行一次查询，在这个过程中会对每次查询的步跳数进行统计。为了得到准确的数据，我们每个仿真都会重复100次。每运行完一次后计算出一个平均值

然后在上次查询的基础上（缓存和节点信息是上次查询后的情况）再进行仿真。这样做是为了使系统先运行一段时间，使系统和网络都趋向稳定。我们对最后的25次运行结果进行统计求最终的平均值

这样得到的结果能比较准确地反映系统的实际性能。

为了对改进后的系统进行分析，我们设参数

作为衡量改进后系统性能好坏的标准。

以下是网络规模、缓存容量和热点分布比率综合变化时，使用HSCM的性能参数统计：通过图4-1可以看出，当缓存容量越大，网络规模大越时，热点缓存机制的作用越明显。

在上图中，分别是在d=50和d=100的情况下来统计在网络规模和缓存容量综合变化下的系统运行情况。由于后者的热点相对前者更集中，热点比率较高，因此其运行的情况比前者好。由此可见，HSCM在热点比例高，网络规模大，缓存容量大的情况下性能更优。

上述的仿真结果显示：HSCM机制不仅显著的加快了热点查询路由，而且具有好的扩展性。对于改进后的系统，首先，当网络中热点关键字越集中时，查询它的次数就越多，网络中存有关键字后继节点的地址信息也就越多，在缓存中命中的概率也越大，查询的平均步跳数也会更少。因此当热点越集中时，性能参数R就越大。能达到20%或更高，这意味着能减少20%或更多的查询信息量。其次，当网络规模越大时，所需要的中间转发次数越多，若关键字查询在中间节点命中（在缓存中查询到），就意味着就减少了越多的中间节点转发次数。因此，随着网络规模的扩大，性能参数R也会越大。根据这两点，可见改进后的系统不仅对热点关键字的查找有较好的性能而且具有高度的可扩展性。在大规模的应用中效果更好。

改进后系统增加的开销很小，相对传统的Chord算法，我们仅仅在节点处增加了一个热点关键字的缓存单元。这个开销完全由单个节点自己独立完成缓存的创建和更新，不需要主动的和其它节点进行交流信息。这样不会增加网络开销，容易实现。

5 结束语

本文结合现实生活中查询的热点现象，提出了一种简单高效的基于节点行为的热点缓存机制。模拟仿真表明这种缓存机制具有良好的可扩展性和高效的查询路由功能。适合于大规模的P2P网络应用。热点关键字缓存和动态的更新策略使缓存内容具有很高的命中率和一致性。在不增加网络开销的情况下，仅在网络节点处增加一个小容量的热点缓存单元，可以加快查询请求的响应、提高缓存命中率和减少查询请求的平均路由次数。由此有效地降低P2P系统对网络带宽资源的消耗。