支持节点异常的Chord算法研究

袁 赟，张英杰

（1.湖南大学 计算机与通信学院，湖南 长沙 410082；2.邵阳学院 信息工程系，湖南 邵阳 422000）

支持节点异常的Chord算法研究

袁 赟1,2，张英杰1

（1.湖南大学 计算机与通信学院，湖南 长沙 410082；2.邵阳学院 信息工程系，湖南 邵阳 422000）

Chord算法是典型的分布式P2P协议，在资源定位和查找上具有优越的性能，但对于节点异常机制的处理不够完善.本文在研究Chord算法的基础上，改进了Chord算法对于节点异常机制的处理能力，能够有效支持节点的异常离开且不影响环上资源共享.实验证明本文算法在中小规模的集群应用中具有较好的性能.

P2P；Chord；分布式哈希；网络拓扑；网络协议

1 引言

P2P技术的核心思想是，在整个网络中由每一个参与网络的peer之间自由地提供资源和服务. P2P中的peer取代了中心服务器，构成分布式的网络，在此网络中的每一个参与者既是资源（服务和内容）提供者(Server)，又是资源（服务和内容）获取者(Client)[1]，它改变了原来的计算机网络结构的C/S或B/S结构，变得平民化，体现一种自由、平等、互联的思想.

在P2P技术中，最基本、最核心的问题是如何在网络中高效准确的定位资源节点，从而进行各种信息和数据交互.目前，P2P技术采用分布式哈希表(Distributed Hash Table，简称DHT)来实现完全分布式的结构化网络拓扑[2].

Chord项目是美国麻省理工学院(MIT)开展的P2P分布式系统项目之一[3].它的目标是提供一个适合于P 2P环境的分布式资源发现服务，它通过使用D H T技术使得对于一个发现指定对象的服务，每个节点只需要维护一个O(logN)长度的路由表. Chord的主要贡献是提出了一个分布式查找算法协议，该协议可将指定的关键字(Key)映射到对应的节点(Node).

与Chord算法类似的采用DHT技术的P 2P系统还有由加州大学伯克利分校提出的CAN[4]和由位于英国剑桥的微软研究院和莱斯(Rice)大学提出的Pastry[5].在节点数量非常大时，CAN的平均查询跳数要比Chord增加得更快，并且CAN查询过程中需要的运算量也要高于Chord.与Chord和CAN相比，Pastry引入了叶子节点和邻居节点集合的概念.在应用层能够及时准确地获得这两个集合的节点信息时，可以大大加快路由查找的速度，同时降低因路由引起的网络传输开销.不过在动态变化的P 2P网络中如何理想地做到这一点的确有很大的难度.

Chord算法在资源查询和服务发现中具有优越的性能，但由于Chord算法完全分布式的结构，使得Chord算法在实际的应用系统使用中具有一定的缺陷[6].在当前流行的各种P2P应用系统中，都不可避免的采用了结构化-半结构化的网路拓扑. Chord算法所采用的节点异常机制不能较好的支持节点异常后的环上数据维护及资源共享.在本文中，我们提出基于Chord的改进算法，在一定程度上改善了Chord算法对于网络不稳定时节点异常机制的管理和数据的备份，有效提高了Chord算法的性能，使得Chord算法更适合于大规模系统应用.

2 Chord工作原理概述

基于Chord算法的系统中，所有节点在逻辑上按照由标识符哈希出来的KEY的大小组成一个环（见图1），数据同样有标识符哈希后的KEY并且存放在和自己KEY最近的节点上.当在某一个节点上输入查询请求时，如果节点的KEY小于数据的KEY，则向该节点知道的下一个节点传递请求，下一个节点如果拥有该文件则返回结果，否则按前面的方式继续转发给下一个节点.其中每个Chord节点只需要知道关于部分节点和到达它们的路由信息（Finger表）.Chord路由查找过程有两个重要特性：每个节点都只需要知道一部分节点的信息，而且离它越近的节点，它就知道越多的关于它们上面的数据信息；每个节点的路由表只有部分节点的路由信息并且不能确定任意一个KEY的确切位置，只能知道下一跳的节点.图1所示为Chord节点维护的指向表，其中0、1、3的位置上有节点.每个节点上维护一张表，以顺时针方向，会在O(logN)内找到任何一个节点.

图1 Chord环及节点Finger表

Chord路由表具有如下特点：每个节点只保存很少的其它节点信息，并且根据计算s t a r t下标的算法（见表1），对离它越远的节点所知越少，也就是说指向表中节点的分布越来越疏，成指数式递增.Chord节点不能从自己的路由表中看出对象k的后继，只能查找到节点的后继.

表1 Chord节点n的路由表各项属性及其定义

3 支持节点异常的Chord算法

3.1 改进算法概述

在Chord算法的描述中，对于节点异常离开情况的办法是：每个节点定时更新后继，与此同时，每个节点在网络中查找Finger表中某一随机项的真正对应节点，来保证Finger表的最新.这里存在三个问题，一是节点后继和Finger表中对同一节点的路由当出现不一致的情况时，系统将不能正常工作；二是随机取Finger表中的某一项来更新，无法保证每一项都有公平相等的被取到的机会；三是在更新Finger表示需要调用find Succ ESS orBy KEY函数在系统中定位某一项对应的节点，因此即使在网络空闲的情况下，也会充斥的大量的查找后继的消息，这很容易导致网络拥塞.另外，在Chord的算法描述中，并没有提供实现数据冗余备份的细节.

因此，本节对Chord的节点异常机制进行了改进.同时也提供了对于数据冗余备份机制的细节实现.对于节点异常离开的处理采用一个定时器.每个节点上的定时器会定时向后继询问其是否有响应.保证了一定的实时性，具有较高的反应时间.通过实验，可以折中计算出系统合适的询问间隔时间.数据冗余备份机制采用节点将数据复制备份在后继节点上的方法，这样若出现异常，数据仍在正确的节点上.

节点异常是提供灾难容错的处理机制.当节点发生异常（断电、断网等、宕机等），系统需要能及时发现并且自动更新，及时更新相关节点的后继和前驱.其中需要有一个机制，以防止当一个节点异常离开时，如何能发现异常并获取该节点上本身储存的信息.一个设想是每一个节点要另外建立维护一个succ ESS or-list后继表，以保存r(r>1)个succ ESS or.这样，当一个节点发生异常时，依然可以通过succ ESS or-list找到这个节点的succ ESS or，然后把环中断掉的部分接上即可.

3.2 节点异常机制算法描述

取r=O(logN)，即使节点失效概率为1/2，整个系统仍能正确定位.在节点加入环之后，开启使用一个定时器.该定时器20秒执行一次（具体时间要根据当前网络环境的稳定性测算最优值），执行任务如下：

向后继通信；

若收到后继发回的消息，则不处理；

若超时，则设置变量IF_SUCCESSOR_ACTIVE为false；

将后继的后继作为本节点的后继，更新相关前驱和后继；

执行stabilize()函数更新环状态；

执行fixFingers()函数更新节点Finger表；

执行update_others()函数更新其他节点信息；

将IF_SUCCESSOR_ACTIVE变量设为true.

更新结束.

此方法对于异常节点上的数据没有进行处理.解决方法就是将每个节点上数据都备份在后继上.优化后的算法如下：

向后继通信；

若收到后继发回的消息，则不处理；

若超时，则设置变量IF_SUCC ESS OR_ACTIVE为false；

将后继的后继作为本节点的后继，更新相关前驱和后继；

执行stabilize()函数更新环状态；

执行fixFingers()函数更新节点Finger表；

执行update_others()函数更新其他节点信息；

将IF_SUCCESSOR_ACTIVE变量设为true；

将后继的数据再备份到后继的后继上.

更新结束.

此处存在另一个问题，即若后继已异常离开，但前驱还未发现该节点异常的期间里，以及发现该节点异常离开后系统正在更新的这两个期间里，若要发生与该节点有关的路由和计算的情况时，该如何处理？

我们采用的保障机制为同步处理.将函数作为一个事务，避免函数进行过程中计算机又执行另外的函数.但更好的方式是采用消息队列的机制，构造一个消息队列缓冲池，是一个未来的研究方向.

4 实验

为了测试本文算法的有效性，我们利用java开发了一套局域网Chord共享系统，并在局域网内的若干台主机上进行网络测试.每个节点均运行在x86的PC上.

在测试中，选取节点20异常离开.在节点20突然失败离开之前，节点69的Finger表如图2.

图2 节点20失败前的节点69信息

节点20失败离开后，其前驱发现节点20异常后，则开启前文中描述的异常处理算法，更新系统中相关节点的节点信息.更新后节点69的信息如图3.

图3 节点20失败后的节点69信息

从图2和图3可以看出，节点20失败后，节点69的Finger表得到了及时的修正，以保证系统继续正常的路由转发.同时数据也得到了复制和恢复.节点20上的数据根据SHA-1的一致性哈希规则重新被分配在节点69和节点98上面.这也体现了数据冗余备份的作用.经过测试，节点反复的异常离开和加入，均没有出现宕机、单点等情况.

5 总结

Chord采用环状的拓扑结构，通过一致性哈希函数将节点、数据对象映射到系统节点上.每个Chord节点维护一个很小的路由表，后继关系是Chord定位的基础，路由表可以将定位路径长度缩短为O(logN)跳即可找到所需节点.本文在Chord算法基础上改进了其节点异常机制，并通过实验测试，能满足中小规模下的集群应用，提供文件检索和下载的服务.并验证了改进Chord算法良好的鲁棒性和稳定性.

〔1〕梁达明.P2P网络资源定位模型研究[D].杭州：浙江大学，2006.

〔2〕李振宇,谢高岗.基于DHT的P2P系统的负载均衡算法 [J].计算机研究与发展,2006,43(9): 1579-1585.

〔3〕Ion Stoica,Robert Morris,David Karger,M. Frans Kaashoek,Hari Balakrishnan.Chord:A Scalable Peertopeer Lookup Service for Internet Applications[A].IEEE/ACM Transactions on Networking [C].New York,NY,USA:IEEE eXpress,2001,11(1):17-32.

〔4〕Sylvia Ratnasamy,Paul Francis,Mark Handley, Richard Karp,Scott Shenker“A Scalable Content-Addressable Network”[A].SIGCOMM'01[C]. New York,NY,USA:ACM,2001:161-172.

〔5〕Antony Rowstron, Peter Druschel. Pastry: Scalable,decentralized object location and routing for large-scale peer-to-peer systems[A]. Proceedingsofthe IFIP/ACM International Conferenceon Distributed SystemsPlatforms Heidelberg[C].London,UK:Springer-Verlag, 2001:329-350.

〔6〕J.Cichon,K.Cichon,P.Kobylanski.Node Evaluation in the Chord P2P Systems[A].Fourth International Conference on Dependability of Computer Systems[C].New York,NY,USA: IEEE eXpress,2009:168-175.

TP393.02

A

1673-260X（2010）08-0024-03