浅谈超节点P2P网络中有效的缓存方法

　　P2P是英文Peer-to-Peer（对等）的简称，又被称为“点对点”。“对等”技术，是一种网络新技术，依赖网络中参与者的计算能力和带宽，而不是把依赖都聚集在较少的几台服务器上。P2P还是英文Point to Point （点对点）的简称。它是术语，意思是在你自己的同时，自己的电脑还要继续做主机上传，这种方式，人越多速度越快但缺点是对硬盘损伤比较大（在写的同时还要读），还有对内存占用较多，影响整机速度。

在P2P软件中，每个用户就是一个节点，数据传输通过节点进行，不需要很多的中央服务器，但为了保证数据传输质量，P2P软件会自动分析每个节点的硬件资源，让有较大带宽和高速计算机担任它的“超级节点”。一定数量的超级节点，数千万的小节点，共同组成了P2P网络，这个用户越多就越强大的奇异的P2P网络。

为了解决上述问题，本文提出了使用文件价值来决定缓存替换的对象，同时在缓存替换之前使用阈值选择缓存文件的策略。这种缓存策略使得系统只缓存价值较大的热点文件，从而通过提高命中率有效地降低了网络流量负载。

　1 超节点P2P系统

　　1.1 体系结构

在广域网中存在大量的节点服务器，这些节点服务器通过P2P路由机制自组织成一个虚拟的P2P网络。在这个虚拟的P2P网络中，各节点服务器之间以无结构的P2P的形式连接，所有的服务器具有相同的能力和责任，任意两台服务器之间能够相互通信，并且所有的通信都是对等的。系统通过这些服务器为用户提供服务，这些节点服务器被称为超节点，而用户节点被称为普通节点。

超节点具有管理组内普通节点、向用户返回查询结果和转发的功能。普通节点和超节点之间则以传统的C/S模式连接在一起，并且每个超节点与若干个普通节点形成组。每个超节点都要维护以下信息表：

(1)本地信息表：保存本地共享资源的索引表。

(2)快捷兴趣信息表：保存与本节点有快捷链接的兴趣相似的超节点信息。该表由(interest，fag，num，address)组成，其中interest代表节点查询的兴趣，fag是快捷链接建立的标志，取值为0或1(建立快捷链接)，num代表查询成功的次数，初始值为0，address代表快捷链接的节点位置。

1.2 超节点间的资源搜索策略

本文采用一种新的搜索策略，该搜索策略可以根据超节点的共享兴趣，逐步在具有相似兴趣的超节点之间建立直接的快捷链接[4]。为了进一步提高查询效率，利用缓存存放访问频率较高的快捷链接。

1.2.1 快捷链接的建立

P2P直接将人们联系起来，让人们通过互联网直接交互。P2P使得网络上的沟通变得容易、更直接共享和交互，真正地消除中间商。P2P就是人可以直接连接到其他用户的计算机、交换文件，而不是像过去那样连接到服务器去浏览与。P2P另一个重要特点是改变互联网现在的以大网站为中心的状态、重返"非中心化"，并把权力交还给用户。 P2P看起来似乎很新，但是正如B2C、B2B是将现实世界中很平常的东西移植到互联网上一样，P2P并不是什么新东西。在现实生活中我们每天都按照P2P模式面对面地或者通过电话交流和沟通。

即使从网络看，P2P也不是新概念，P2P是互联网整体架构的基础。互联网基本的协议TCP/IP并没有客户机和服务器的概念，所有的设备都是通讯的平等的一端。在十年之前，所有的互联网上的系统都同时具有服务器和客户机的功能。当然，后来发展的那些架构在TCP/IP之上的软件的确采用了客户机/服务器的结构：浏览器和Web服务器，邮件客户端和邮件服务器。但是，对于服务器来说，它们之间仍然是对等联网的。以email为例，互联网上并没有一个巨大的、的邮件服务器来处理所有的email，而是对等联网的邮件服务器相互协作把email传送到相应的服务器上去。另外用户之间email则一直对等的联络渠道。

　1.2.2 快捷链接的缓存

当本地快捷兴趣信息表建立后，将快捷链接按照num值的大小进行排队。如果某个快捷链接的num值(说明它经常被使用)，就把它放在缓存中，当节点进行搜索时首先调用缓存的快捷链接。其他没被缓存的链接按num值的大小在快捷兴趣信息表中排队，num值大的排在上面，其他依次类推。同时每个超节点的快捷兴趣信息表可以自我调整，以适应网络的变化。当一个快捷链接的超节点离开网络、或长时间不使用、或命中率很低时，应及时调整它的num值以及存放的位置，直到把该快捷链接去除。

　1.3 超节点P2P系统中的对象定位

当普通节点P0发出查询请求时：

(1)P0首先查询本地缓存，若命中则查询结束；否则转到(2)。

(2)P0访问它所连接的超节点Pi，若在Pi中命中则由Pi将命中的内容返回给P0，查询结束；否则，由Pi在超节点间转发查询，具体过程是：①Pi发出资源搜索时，首先通过缓存中的快捷链接进行查询，若命中，则返回结果后结束；否则转②；②Pi向自己的快捷兴趣信息表中的快捷链接发出查询，若命中，则返回结果后结束；否则转(3)。

(3)Pi将查询请求转发给文档原来的存放站点，若命中，则返回结果后结束；否则发回错误。

　2 缓存策略

　2.1 缓存对象的选择

在传统的缓存策略中，当用户访问的文件不在离用户近的服务器上，那么不管该文件近是否被访问过，都将该文件缓存到近的服务器上。在实际应用中，这种缓存策略不能灵活地针对实际情况做实际的调整，有时候会降低缓存的命中率。为了克服这一缺点，本文使用阈值来选择缓存对象[5]。

在超节点P2P系统中，当文件和用户的数量足够大时，在短时间内将会有大量的文件被访问，而对于单个的文件来说，被访问的频率是不一样的。本文根据文件的被访问频率用阈值来将它们区分为热点文件和非热点文件。当一个文件的被访问频率超过设定的阈值时称为热点文件，否则为非热点文件。本文只缓存热点文件，这样能够有效地利用服务器的缓存空间，防止在缓存空间不足的情况下，文件副本在缓存空间频繁地替换而导致缓存的命中率下降。

为了提高缓存的作用，阈值的大小应根据实际情况来调整。可以根据缓存空间的大小和文件类型来设置阈值的大小。当缓存空间较大时，可以适当减小所有文件的阈值；当缓存空间较小时，应适当增大文件的阈值，使得缓存策略更关注那些较热的文件。同时，可以为更新较少的文件类型设置一个较小的阈值，这样文件将更容易被缓存；为更新较多的文件类型设置一个较大的阈值，那么该类型的文件就比较难于被缓存。

　2.2 缓存替换策略

本文提出了使用文件价值决定缓存替换对象的替换策略，该策略要求所有的节点都维护同一请求列表。请求列表中记录着该节点访问过的所有文件的基本信息。

当一个节点从服务器中成功地文件A，并判断其被访问的频率大于设定的阈值后，按照以下步骤进行缓存替换：

(1)如果节点的缓存空间足够容纳文件A，那么文件被缓存。否则转到(2)。

(2)比较文件A和缓存中候选文件的Costfile值。先与Costfile值的候选文件相比，若文件A的值小，则不进行缓存替换；若文件A的值大，则将Costfile值的候选文件从缓存中去除，然后判断缓存空间的大小，转到(1)。

　3 模拟实验和结果

为了验证缓存策略的实际性能，这里选取了一组Web Cache的访问日志作为工作负载并使用Trace-Driven的方法模拟实验。在实验中，为了进行性能比较，对LRU[6]和LFU[7]也进行了性能测试。

实验选取的Web Cache访问日志为学校网络中心的Web服务器在一天24小时内的日志记录。在每一条日志记录中包括的主要字段有：独立用户的IP地址、上网时刻、目的网站的域名、目的网站的IP地址、URL、访问文件的大小等。然后实验模拟了分布在广域网上的10台节点服务器。所有这些节点服务器按照P2P路由机制组成一个完全分布式无结构的P2P网络，并使用散列的方法把从日志中提取到的独立的用户均匀分布到这些服务器上去，同时假设用户在物理上距离自己所分配到的服务器近，然后用同样的方法把从日志中提取到的互不重复的URL所对应的文件均匀分布到这些服务器上去，假设每一个文件都位于自己所分配到的服务器上。这样，就把Web Cache的访问日志纪录映射到虚拟的超节点P2P网络中了。

缓存策略性能的好坏可以从缓存命中率和缓存字节命中率这两个方面来衡量。缓存命中率(Hit Ratio)表示从缓存得到服务的请求占总请求的百分比，缓存字节命中率(Byte Hit Ratio)表示从缓存得到服务的字节量占总请求字节量的百分比[8]。在实验中，只比较缓存空间在存储空间中所占比重小于一半的情况，因为缓存继续增加对提高性能而言效果不再明显。该缓存策略与传统缓存策略LRU和LFU的性能比较。

本文提出的缓存策略在性能上要好于传统的LRU和LFU。当缓存空间比较小时，本文提出的缓存策略表现出更突出的性能，随着缓存空间的逐渐增大，这三种方法所表现出的性能趋于相同。另外，阈值设置的大小也会影响缓存的命中率和字节命中率，因此，在实验过程中要根据缓存空间的大小和文件的类型及时调整阈值，以达到提高性能的目的。在参考文献[5]中的部分结论选择较为理想的，如1、2、3、4等较小的阈值，具体设置在此不做详细论述。

本文提出了一种有效且灵活的缓存策略，该策略使用文件价值来决定缓存替换的对象，同时在缓存替换之前使用阈值选择要缓存的文件，这使得系统只缓存价值较大的热点文件。使用Trace-Driven的方法模拟实验，并且将其与传统的LRU和LFU做了性能上的比较，验证了该缓存策略在性能上比传统的LRU和LFU要好。