一种基于节点信息复制与查询热点的
Chord 改进算法
钟评1，胡彧2**
作者简介：钟评，(1985-)，男，硕士研究生，主要从事分布式搜索方面研究。
通信联系人：胡彧，（1968 -），女，教授，主要方向为智能信息处理与智能控制等. E-mail: huyutyut@163.com
5 （1. 太原理工大学计算机科学与技术学院，太原 030024；
2. 太原理工大学测控技术研究所，太原 030024）
摘要：Chord 算法的改进一般是通过改善其路由表结构或者修改其查询算法。由于修改路由
表结构的方法在降低平均查询跳数与时间的同时通常增加了路由表长度，使得Chord 在维护
时占用更多的带宽且改善效果并不理想。本文通过分析Chord 在查询过程中的路由特点，提
10 出一种基于节点信息复制和查询热点的改进算法CH-Chord，并通过仿真实验证明该算法在
减少平均查询跳数与查询时间的同时并没有增加Chord 稳定时的维护消耗。
关键词：Chord 算法；节点信息复制；分布式哈希表；对等网
 0 引言
对等网搜索作为一种覆盖网技术，根据节点的拓扑是否具有结构性，可分为结构化搜索
和非结构化搜索。Chord 是一种结构化搜索方式，即通过分布式哈希表（DHT）技术，将查
询的关键字Key 与节点标识(id)使用相容哈希[1]散列在同一地址空间中。同时，Chord 采用
35 了路由(finger)表的查询方式，使得每个节点在只需维护少量的节点信息的同时可以进行高效
的查询。
Chord 查询算法的改进一般是通过改进finger 表结构或改变路由查询的方法实现。通过
改进finger 表结构的方法通常在降低平均查询时间和平均查询跳数的同时增加了路由表长
度（即维护的消耗）。因为finger 表的长度越长，则Chord 节点维护的消耗越大。实际上，
40 限制Chord 普及的主要原因就是Chord 的节点维护信息过大。文献[2]证明了在Chord 中路
由表长度、平均查询跳数、平均查询时间三者不能同时降低。文献[3]采用斐波那契数构造
finger 表得到一组改进的Chord 算法，查询时间降低为0.72log2N,但是路由表长度变为了
 1.44log2N-2，并且没有考虑查询方式的改善。在查询方式的改变方面，文献[4]与文献[5]采
用了并行查询的方法，降低了平均查询时间。
45 本文分析了Chord 的查询特征，并针对该特征提出一种基于路由热点问题与节点信息复
制的改进算法，并证明了该算法能够在不增加节点消耗的情况下减少平均路由长度与路由时
间。并将该算法与并行查询的方法结合，进一步降低了查询路由时间与路由长度。
1 Chord 原理
1.1 Chord 结构
50 Chord 是一个简单的由各个节点首尾相连形成的单向环形结构，如图1 所示。图中前缀
N 表示节点，前缀K 表示查询关键字。在该环中每一个节点按照节点标识符(id)由小到大排
列，id 可以通过对节点信息使用相容哈希函数得到。通常情况下，Chord 不直接储存具体的
资源，而是储存这些资源对应的路由信息，如该资源实际存放的节点ip 地址和端口信息等。
这些信息储存在其对应关键字key 通过相容哈希函数散列后得到的id 之后的第一个节点上。
55 查询时则通过查询关键字散列后的得到的结果(key 值)确定节点位置。所有查询关键字的信
息储存在大于散列值key 的第一个节点，即散列值的后继(successor)中。这样的储存方式使
得每一个查询的信息直接与其储存位置相联系。
图1 Chord 结构
60
1.2 路由表结构
Chord 中节点除了维护其后继节点的信息外，还维护一张路由(finger)表，传统的Chord
中finger 表采用以2i 作为第i 个指向的方法，即对于m 位id 空间的Chord 环，每一个节点
拥有长度为m 的finger 表项，其中i>=0。如图2 对于id=8 的节点N8，其finger 表第i 项为
65 N8+2i 的直接后继，即finger 指向id 大于等于N8+2i 的第一个节点。在进行查询时节点向距
离查询的key 值最接近但不大于的那个finger 项所指向的节点发起查询，之后再由下一节点
通过自身finger 表继续之前操作直到查询结束。
 图2 Chord 路由表查询过程
70
以图2 节点N8 的查询为例，若N8 查询key 值为21<key<=32，则直接通过finger 表中
第5 项（i 从0 开始，i=4 时)N8+16 得到指向的节点N32，若查询的key 值为key>42，则通
过访问finger 表最后一项指向的N42 的finger 进行下一跳查找。标准的Chord 最大查询跳数
可以通过这样的方式推导得到：假设查询节点距离发起的节点m，且 2i < m <2 i+1，则经过
75 第一跳后路由节点与查询节点距离为 m-2i <2i ，由此可知查询必然在i 跳内结束，因此其查
询效率为log2N[3]。
Chord 在运行时各个节点仅关注两个问题：查询的路由以及finger 表和后继节点的维护，
其中后者往往更加复杂。对于Chord，只要其后继节点正常，其路由查询就能继续下去，因
此后继节点的维护比finger 表更加频繁，每一个节点在加入时都要通过一个well known 节
80 点引导得到其前驱与后继节点，并通知这些节点进行修改。同时为了防止节点失效，每一个
节点往往拥有数个后继节点。对于finger 表和后继的维护，通常调用fix_finger()和
fix_succssor()过程，即每隔一定时间内对finger 表各指向节点进行一次检查确保finger 指向
正确。
2 改进的Chord 算法
85 2.1 Chord 查询的路由特点
考虑以下两种查询时的路由情况：一是对热点问题的查询，即不同的节点对同一个key
发起查询；二是虽然查询的key 虽然不同，但是这些key 所对应的结果储存在同一节点上。
以上两种情况的查询，本质上是不同的查询发起节点对同一个节点发起查询。以图2 为例，
假设图中的各节点分别对节点N51 发起查询，将每个节点的查询路径以树状的方式表示则
90 得到图3 的结果：
 N51
N42 N48
N8 N38
N32 N14
N1 N21
图3 各节点查询N51 上信息的路径
图中节点N51 看作树根，所有子节点到N51 的连线表示该子节点查询N51 所储存key
95 的路由路径，从图中可以看到，几乎所有节点在查询路由的过程中都经过了N51 的前一个
节点N48。如图3 中N14 的查询路径为N14 ->N48(N14+32)->N51，N21 的查询路径为
N21->N38(N21+16)->N48(N38+8)->N51。同时对于节点N38 与N21，由于N21 的第一跳为
N38，其后续从N38 至N51 跳的路径则与N38 本身访问N51 时相同。由图3 可以得出Chord
的路由查询特点，在对同一节点进行查询时，被查询节点之前的数个节点往往会被频繁访问，
100 因为这些节点在查询路径所生成的树中所处的位置离根最近。考虑在真实的网络环境中，节
点数目通常上千，查询也更加频繁，发起的查询往往会频繁地访问被查询节点之前的数个节
点。造成这种特点的原因是因为Chord 的finger 表是指数的增长方式，因此在查询时，每一
跳节点间的跨度会逐渐减少。使得在最后一跳之前的数个节点总是会被频繁地访问。
2.2 Chord 中节点的复制储存
105 Chord 在实际运行中，如果某一个节点异常失效，则其节点上所储存的信息将会丢失。
为了维持Chord 不因为异常情况而出错，通常采用将节点中的信息复制其到后继节点上的办
法。这样Chord 仅在节点其后继同时异常失效的情况下才会产生错误，如果后继节点不只一
个，则可将节点信息复制在其后的数个节点上，则大大降低了Chord 因节点异常失效产生错
误的可能性。
110 2.3 基于节点信息复制和查询热点的Chord 改进算法CH-Chord
由以上Chord 查询特点以及Chord 中节点复制储存机制可以得到如下改进思想，如果将
节点的复制信息储存在其后继节点的方法变为储存在节点的前驱节点中，在进行Chord 查询
时，查询仍然按照原本的方法进行，但只需查询找到拥有查询key 对应的信息或复制信息的
节点便完成查询。通过这样的改进，降低了查询跳数与路由时间。
115 上述将整个节点信息进行复制的方法适用于所有查询。进一步考虑路由热点的情况，假
设Chord 中许多节点对同一关键字key 发起查询，如果在其路由的路径中的某一节点N 多
次被访问，则可以将该关键字的查询结果复制到该节点N 上，则其后N 到key 所在节点的
路由过程可以省去。本论文使用比较简单的方法实现这个办法，当一个查询找到拥有被查询
信息的节点（原本的节点或复制的信息）时，则将该信息使用RCP 发送到上一跳的节点，
120 这样，如果上一跳节点不再被同一key 的查询访问，则该信息停止复制。这样的方法使得热
点访问的信息得以扩散而非热点信息则不会。
在储存结构上，每个节点在拥有原本所储存的信息的表的同时拥有一张用于储存复制节
 点信息的表，两者分开储存以便于维护，分别记为mylist 与copylist。节点的复制方法是通
过改造Chord 原有的RCP 调用，使其返回访问后继节点的储存信息。由于每个节点在加入
以及运行时都会在一125 定时间内调用fix_succssors()过程向后继节点发送RCP 调用以维护自身
的后继表。通过修改RCP 调用可以使其返回访问节点储存的信息，由于实际的Chord 信息
存储的是所查询资源真实存放位置的一条记录，因此每个节点所储存的信息量不会太大，对
于储存信息较多的节点，可以通过多次的fix_succssors()过程得到完整的节点储存信息。通
过这种方法可以在不增加额外的节点间访问的情况下得到后继节点的储存信息。
130 在以上改进的基础上可以得到基于复制与查询热点的Chord 查询算法CH-Chord，查询
算法分为三部分，fix_succssors()过程原本作用为维护节点后继，通过改造后用以得到复制信
息。lookup()过程为查询发起节点查询过程，next_handler()为RCP 访问的节点所调用的句柄：
fix_succssor()
for each succssors
135 call doRCP (getinfo_handler , succssor) //向自身后继发送信息以维护后继表，同时返
回复制信息
copylist.insert( receiveRCP) //将得到的复制信息添加到自身copylist 中
…… // 原本fix_succssor() 的内容
end for
140
look_up()
while not finished //查询没有结束
lasthopinfo <-- nexthopinfo //保存上一跳信息
nexthopinfo <-- result.next //从上一跳返回结果得到下一跳信息
145 call doRCP ( next_handler , nexthopinfo ,lasthopinfo,key) //向下一跳发送RPC
result <-- receiveRCP () //RCP 返回结果
finished <-- result.done
end while
150 next_hander(lasthopinfo ,key)
学术论文网Tag：代写论文 代写代发论文 代发论文 职称论文发表