第32卷
Vo1．32
第 l9期
№ l9
计 算 机 工 程
Computer Engineering
2006年 lO月
October 2006
· 开发研究与设计技术 · 文章编号：loo 一3428(20o6)l _-0267-_03 文献标识码：A 中圈分类号：TP311
对等系统的数据定位
唐志福，邹恒明
(上海交通大学计算机系，上海 200240)
摘 要：数据定位是对等系统的核心问题，在诸多对等系统数据定位方法中，应用分布式哈希表接El进行数据定位的方法优点突出。论文
讨论了对等数据定位的常用方法以及用分布式哈希表接口进行对等数据定位的优点，对 4种实现了分布式哈希表的接口算法，即 CAN、
Chord、Pastry、Tapestry算法作了分析，并对这 4种算法的性能进行了比较。
关健词 ：对等；分布式哈希表 ；内容可定位网络；Chord；Pastry；Tapestry
Location of Data in Peer-·to-·Peer System
TANG Zhifu，ZOU Hengming
(Dept．of Computer,Shanghai Jiaotong University，Shanghai 200240)
IAbstract]Location of data is a heart problem in P2P field．Among many techniques of data location．distributed hash table(DHT)is most
advantageous．The paper discusses most of popular techniques of data loc ation and the benefits of DHT．It analyses the four algorithms of
implementing DH and compares their preferences．
[Key words|Peer—to—peer；Distributed hash table(DHT)；Content—addressable network(CAN)；Chord；Pas~；Tapestry
对等 (Peer—to-Peer)文件共享应用的成功激起了对等领
域的其他应用。对等系统的优点如没有集中的控制或者阶层
式组织和每个结点身份同等，使大家对对等技术产生了浓厚
的兴趣。在未来完全分布式的系统完全有可能成为大规模系
统组建方式。
数据定位是对等系统的核心问题。它研究如何在一个对
等系统以可扩展性方式定位数据，并且没有任何中心服务器
或层次组织作为辅助。它是任何对等系统的核心问题。目前
这个问题没有得到很好的解决。这个问题的解决思路是解决
其他对等系统难题的模式。
l数据定位
某一个数据提供者提供了一个数据x到这个系统中，譬
如 x是个文件。在这之后某个消费者想获得 X，一般是提供
者可能已经没有连接系统网络了。消费者如何找到 x的副本
的所在的主机位置呢?
第 1种技术是应用中心数据库建立文件名和存储该文件
的主机之间映射关系 (Mapping)。Napster⋯是采用了该技术 ，
低可靠性 (Reliability)和低扩展性(Scalability)是该技术的缺
点。这些缺点可能导致数据容易遭到攻击，系统脆弱。
第2种技术是为消费者广播文件x请求消息给所有邻居
结点。当结点收到这则请求消息，首先检查一下本地文件系
统。如果这个结点有X文件，它就来响应这个消息。否则它
会继续广播这则消息给它的邻居。同样它的邻居也完成这样
协议。Gnutella 。 是采用该种技术。而该技术不具有强扩展
性。因为系统带宽会被广播消息占据，而且计算资源也会因
处理请求消息而耗尽。
第 3种技术是第 2种技术的改进。为了减少广播请求消
息的消耗，研究者们把这些网络结点组织成一个层次状结构，
就像互连网的域名服务器 (DNS)一样。查找从最顶层开始，
沿循从一个结点到一个结点的前进指引，遍历一条向下通向
存储目标数据结点的路径。引导式的一条路径遍历的资源消
耗比广播式的资源消耗少得多。KaZaA、Grokster和MusicCity
Morpheus采用该技术。层次状结构方法的缺点是位于层状顶
层结点的负荷大，因此顶层结点使系统变得脆弱。
第4种技术为对称分布式数据定位。对称分布式数据定
位技术避免了以上技术的缺点。查询沿循从一个结点到一个
结点的指引直到找到存储该数据结点而展开。查询从任何一
个结点开始，每个结点只涉及系统中一小部分的查找路径。
因此在查询中没有一个结点会消耗过多的资源。该技术具有
强扩展性、结点维护信息少，并且容易高效率覆盖网络。
2分布式哈希表
哈希表(DHT)接口是分布式数据定位算法的重要基础，
一 个分布式哈希表只要实现一个操作：lookup(key)，该操作
返回一个结点的标识 (如 IP地址)，返回的标识结点存储键
值对应的数据。下面是一个应用DHT接口的简单例子：提供
者结点需要把文件的全局唯一名字通过哈希函数如SHA—l转
换成一个数字键值，然后调用函数 lookup(key)，提供者结点
发送这个文件，将文件存储到返回结点中。读该文件的结点
需要获得文件名，转换成它的键值，调用 lookup(key)，然后
向返回结点请求该文件副本。
为了实现分布式哈希表，数据定位算法必须解决如下问
题：建立负载平衡的键值和主机的映射关系，推进键值查询
到适当主机，建立一个路由表。
3分布式哈希表算法
3．1 CAN
CAN[2,31使用了d维笛卡儿积坐标空问来实现DHT接口。
作者筲介：唐志福(1976一)，男，硕士生，主研方向：高可靠软
件研究 ，分布式系统研究 ；邹恒明 ，教授
收穑日捆：2005一l1一O3 E·mail：zftang@sjtu．edu．cn
一 267—
维普资讯
第32卷第 19期
Nil 19
计算机工程
Computer Engineering
2006 年 10 月
October 2006
·开发研究与设计技术· 文章蝙号 10()(←3428(2006)1弘-o267-Ø3 文献标识码 A 中图分类号 TP311
对等系统的数据定位
唐志裙，邹恒明
(上海交通大学计算机系，上海 2∞240)
摘要:数据定位是对等系统的核心问题，在诸多对等系统数据定位方法中，应用分布式哈希表接口进行数据定位的方法优点突出。论文
讨论了对等数据定位的常用方法以及用分布式哈希表接口进行对等数据定位的优点，对 4 种实现了分布式哈希表的接口算法， IlP CAN、
Chord、 Pastry 、 Tapestry 算法作了分析，并对这 4 种算法的性能进行了比较。
关键词:对等;分布式哈希表;内容可定位网络 Chord; Pastry; Tapestry
Location ofData in Peer-to-Peer System
TANG Zhifu, ZOU Hengming
(Dept. ofComputer, Shanghai Jiaotong University, Shanghai 200240)
(Abstract> Location of data is a heart problem in P2P tìeld. Among many techniques of data location, distributed hash table (DHT) is most
advantageous. The paper discusses most of popular techniques of data location and the benefits of DHT. It anaJyses 由e four algorithms of
implementing DHT. and compares their preferences.
(Key words) Peer-to-peer; Distributed hash table (DHT); Content-addressable network (CAN); Chord; Pastry; Tapestry
对等(Peer-to-Peer) 文件共享应用的成功激起了对等领
域的其他应用。对等系统的优点如没有集中的控制或者阶层
式组织和每个结点身份同等，使大家对对等技术产生了浓厚
的兴趣。在未来完全分布式的系统完全有可能成为大规模系
统组建方式。
数据定位是对等系统的核心问题。它研究如何在一个对
等系统以可扩展性方式定位数据，并且没有任何中心服务器
或层次组织作为辅助。它是任何对等系统的核心问题。目前
这个问题没有得到很好的解决。这个问题的解决思路是解决
其他对等系统难题的模式。
1 数据定位
某一个数据提供者提供了一个数据 X 到这个系统中，譬
如 X 是个文件。在这之后某个消费者想获得 X ，一般是提供
者可能已经没有连接系统网络了。消费者如何找到 X 的副本
的所在的主机位置呢?
第 l 种技术是应用中心数据库建立文件名和存储该文件
的主机之间映射关系 (Mapping) 0 Napsterl川是采用了该技术，
低可靠性 (ReIiabiI ity) 和低扩展性(Scalability)是该技术的缺
点。这些缺点可能导致数据容易遭到攻击，系统脆弱。
第 2 种技术是为消费者广播文件 X请求消息给所有邻居
结点。当结点收到这则请求消息，首先检查一下本地文件系
统。如果这个结点有 X 文件，它就来响应这个消息。否则它
会继续广播这则消息给它的邻居。同样它的邻居也完成这样
协议。 GnuteIIall ， 2 1是采用该种技术。而该技术不具有强扩展
性。因为系统带宽会被广播消息占据，而且计算资源也会因
处理请求消息而耗尽。
第 3 种技术是第 2 种技术的改进。为了减少广播请求消
息的消耗，研究者们把这些网络结点组织成一个层次状结构，
就像互连网的域名服务器 (DNS) 一样。查找从最顶层开始，
沿循从一个结点到一个结点的前进指引，遍历一条向下通向
存储目标数据结点的路径。引导式的一条路径遍历的资源消
耗比广播式的资源消耗少得多。KaZaA、 Grokster 和 MusicCity
Morpheus 采用该技术。层次状结构方法的缺点是位于层状顶
层结点的负荷大，因此顶层结点使系统变得脆弱。
第 4 种技术为对称分布式数据定位。对称分布式数据定
位技术避免了以上技术的缺点。查询沿循从一个结点到一个
结点的指引直到找到存储该数据结点而展开。查询从任何一
个结点开始，每个结点只涉及系统中一小部分的查找路径。
因此在查询中没有一个结点会消耗过多的资源。该技术具有
强扩展性、结点维护信息少，并且容易高效率覆盖网络c
2 分布式啥希表
哈希表(DHT)接口是分布式数据定位算法的重要基础，
一个分布式哈希表只要实现一个操作 Iookup(key) ，该操作
返回一个结点的标识(如 IP 地址) ，返回的标识结点存储键
值对应的数据。下面是一个应用 DHT 接口的简单例子:提供
者结点需要把文件的全局唯一名字通过哈希函数如 SHA-I 转
换成一个数字键值，然后调用函数 Iookup(key) ，提供者结点
发送这个文件，将文件存储到返回结点中。读该文件的结点
需要获得文件名，转换成它的键值，调用 Iookup(key) ，然后
向返回结点请求该文件副本。
为了实现分布式哈希衰，数据定位算法必须解决如下问
题:建立负载平衡的键值和主机的映射关系，推进键值查询
到适当主机，建立一个路由表。
3 分布式哈希表算法
CAN
CANI2 ， 3J使用了 d维笛卡儿积坐标空间来实现 DHT接口。
作者简介:唐志福(1976一)，男，硕士生，主研方向:高可靠软
件研究，分布式系统研究;邹恒明，教授
收稿日..: 2005-11-03 E-mail: zftang@
一267一
这个坐标空间被划分为数个超长方形，这些超长方形称为区
域。每个结点都对应一个区域而且用它所在区域的边缘作为
ID。一个键值映射到一个坐标空间点，它存储在该点所在区
域的主机上。图 1(a)表示了一个 2维【0，1】×【0，l1 CAN有 6个
结点。每个结点负责维护存储有邻居结点信息的路由表。邻
居结点具有d一1个坐标值。
I ， ■ II)5 0 5．1 1)
0 5_】25 0 7 1 0 5】
■
■ (0 75【_
0 0()5 0 51 【】5 00 75 0 51-
■
图 1 DHT按 13
查询操作沿几乎是直线的路径从消息查询发起结点到键
值存储结点来推进一个数据定位查询消息。接收到数据定位
消息，结点把消息推进给它的最近邻居结点，直至找到存储
该键值的结点。图 1(b)显示了查询键值(0．8，0．9)的路径。每个
结点维护 D(d)个状态 ，并且这个查询成本为 O(d N )。如果
d：O(1ogN)，CAN的查询次数及存储空间需要是最优的。
当新结点加入到系统时，新的结点首先要在这个坐标空
间里选择一个随机点 P，然后要求一个已经在网络中的结点
找到区域包含点P的结点 n，结点 n把这个区域分开两半，
把一半分配给新结点。新结点很容易初始化它的路由表，因
为除结点n本身外，结点n的邻居也就是新结点的邻居。一
旦加入这个网络，新结点应该向它的邻居结点报告它的存在 ，
以便邻居结点更新它们的路由表。
当一个结点要离开系统时，这个结点把它的区域给其中
一 个邻居。如果两个区域合并成了有效区域，那么这两个区
域就变成一个更大区域。如果不能，邻居结点就会临时处理
这两个区域，如果该邻居结点失败，CAN实现一个协议，这
个协议让最小区域的邻居来处理这个事情。一个潜在的问题
是，在结点处理大量区域合并操作过程中，如果多次失败可
能导致这个坐标空间有很多碎片。为了处理这个问题，CAN
潜在地运行一个特别算法实现结点重排。这个算法尽量把能
够合并成一个有效区域的区域分配给同一个结点，然后把这
些区域合并。
CAN 采用了两种技术来减少数据查询定位的延迟：(1)
结点接收到一个查询，它会以前进幅度与网络延迟时间比值
最大的方式来推进这个消息给邻居结点。(2)多实现。使用多
坐标空间比较数据查询延迟。在每个坐标空间里每个结点分
配给不同的区域。为了推进一个查询消息，选择最小数据定
位延迟空间实现来推进消息。
为了达到负载的平衡，CAN采用统一分配空间。在结点
加入系统操作时，结点在分裂它的区域前要检查一下它的邻
居结点。如果邻居结点有更大区域，则由这个更大区域的邻
居结点来分裂它的区域。
3．2 Chord
Chord 。 在一维空间分配 ID给键值和结点。存储键值 K
的结点称为 K的后续结点，后续结点的 ID是最靠近 K的。
Chord查找时间复杂度为 O(1og^ D，N为结点数。Chord
一 268一
中每个结点拥有保存 log N条记录的指针表。结点的指针表
包含从本身开始第半圆数个结点IP，第 1／4圆数个结点IP和
第2的n次方分之一圆数个结点 IP。如图2所示，一个Chord
查找键值 54的路径，从结点 8开始。每个箭头代表查询的推
进，通过结点指针表项，结点 8推进查询到结点 42；因为结
点 42是结点 8的第半圆数个结点，下一个是第 l／4圆数个结
点 51。这个例子中结点 8的指针表储存着结点 41、51、56
信息。
N
图2Chord的查找路径
一 个结点把键值 K查找消息推进到它的指针表中 ID最
大且比键值 K小结点。指针表的 2的次方结构确保了结点总
是能把查询消息最少推进剩余 ID 空间一半的距离。因此
Chord查询使用了 O(1og D^条消息。
新结点 n如何确定自己在 Chord系统中位置，Chord通
过如下方法实现：为了这个新结点能正确地加入这个系统，
系统需要做的是更新它的和它前键结点的后续列表。新结点
通过请求其他已存在的结点来查找将分配结点 n的 ID。即使
在有相似 ID的结点同时加入系统中，Chord也能确保其正确
性。更新的结点和已经存在的结点指针表只要蕴式地进行，
因为它只是在性能上要求的，不是正确性上要求的。新的结
点同时必须获得它存储键值的所有相关的数据。后继关系确
保所有键值都可以从新结点的后续结点获得。
随机性保证了 Chord键值和结点 ID初步统一地分布在
ID空间里，确保结点间负载平衡。Chord对存储在结点的键
值空间片通过虚拟结点来控制。在 Chord系统中的每个物理
结点有多份虚拟结点 ID，增加虚拟 ID会增加结点存储键值
的数量。Chord能够路由一个消息可以在低查询延迟时间的
路径上进行；它是通过充分利用存在许多指针表记录更容易
把查询推进到 目的结点。每个这样的记录都有显著的代价(查
询延迟时间)和益处 (在 ID空间的进度)。
3．3 Pastry
Pastry 每个结点都有一个随机选定的 ID，概念上它表
明了结点在标识圈内的位置。Pastry路由键值消息到一个活
跃结点，这个结点的 ID数字和这个键值很相似。ID空间的
位数是 2 的倍数。其中 b是一个算法的参数，一般 b为 4，
ID空间的位数就 128。
Pastry使用一个基于前缀推进机制。每个结点 n维护一
个叶子集合 L，该集合中有ILl／2个最靠近结点 n的且比 n小
的结点，有ILl／2个最靠近结点 n的且比 n大的结点。叶子集
合的正确性是消息正确推进的唯一要求；除1~lLI／2个 ID邻近
的结点同时失败，否则数据定位消息就能正确推进。叶子结
合在概念上和 Chord的后继列表相似。
为了优化消息的推进性能，Pastry维护一个指向分布在
ID空间其他结点的路由表。这个路由表是一个I log^N『行，每
维普资讯
这个坐标空间被划分为数个超长方形，这些超长方形称为区
域。每个结点都对应一个区域而且用它所在区域的边缘作为
ID。一个键值映射到一个坐标空间点，它存储在该点所在区
域的主机上。图 l(a)表示了一个 2 维[O ， I]X 凹， I]CAN 有 6 个
结点。每个结点负责维护存储有邻居结点信息的路由表。邻
居结点具有 d-1 个坐标值。
(0, 1)
keyo:o!∞kup(() U储在结卓 ，气!.!)
(1. 1)
)
• • (O,.!) ,05 ,!.!)
. )
• iO吨0.• 0105} ( ,0 ←一←→←一 5)-)，~
•
•
•
•
() () 从结点 (日启功 !ookup(O 8 ， )路径
(a) ) ku (
圄 1 DHT 接口
查询操作沿几乎是直线的路径从消息查询发起结点到键
值存储结点来推进一个数据定位查询消息。接收到数据定位
消息，结点把消息推进给它的最近邻居结点，直至找到存储
该键值的结点。图 l(b)显示了查询键值( ，)的路径。每个
结点维护。(d)个状态，并且这个查询成本为 O(d*N1/d )。如果
d = O(logN) , CAN 的查询次数及存储空间需要是最优的。
当新结点加入到系统时，新的结点首先要在这个坐标空
间里选择一个随机点 P，然后要求一个已经在网络中的结点
找到区域包含点 P 的结点 n，结点 n 把这个区域分开两半，
把一半分配给新结点。新结点很容易初始化它的路由表，因
为除结点 n 本身外，结点 n 的邻居也就是新结点的邻居。一
旦加入这个网络，新结点应该向它的邻居结点报告它的存在，
以便邻居结点更新它们的路由表。
当一个结点耍离开系统时，这个结点把它的区域给其中
一个邻居。如果两个区域合并成了有效区域，那么这两个区
域就变成一个更大区域。如果不能，邻居结点就会l临时处理
这两个区域，如果该邻居结点失败， CAN 实现一个协议，这
个协议让最小区域的邻居来处理这个事情。一个潜在的问题
是，在结点处理大量区域合并操作过程中，如果多次失败可
能导致这个坐标空间有很多碎片。为了处理这个问题， CAN
潜在地运行一个特别算法实现结点重排。这个算法尽量把能
够合并成一个有效区域的区域分配给同一个结点，然后把这
些区域合并。
CAN 采用了两种技术来减少数据查询定位的延迟(1)
结点接收到一个查询，它会以前进幅度与网络延迟时间比值
最大的方式来推进这个消息给邻居结点。 (2)多实现。使用多
坐标空间比较数据查询延迟。在每个坐标空间里每个结点分
配给不同的区域。为了推进一个查询消息，选择最小数据定
位延迟空间实现来推进消息。
为了达到负载的平衡， CAN 采用统一分配空间。在结点
加入系统操作时，结点在分裂它的区域前耍检查一下它的邻
居结点。如果邻居结点有更大区域，则由这个更大区域的邻
居结点来分裂它的区域。
Chord
Chordl3 .4 1在一维空间分配 ID 给键值和结点。存储键值 K
的结点称为 K 的后续结点，后续结点的 ID 是最靠近 K 的。
Chord 查找时间复杂度为 O(log N), N 为结点数。 Chord
-268一
中每个结点拥有保存 10g N 条记录的指针表。结点的指针表
包含从本身开始第半圆数个结点 IP ，第1/4 圆数个结点 IP 和
第 2 的 n 次方分之一圆数个结点 IP。如图 2 所示，一个 Chord
查找键值 54 的路径，从结点 8 开始。每个箭头代表查询的推
进，通过结点指针表项，结点 8 推进查询到结点 42; 因为结
点 42 是结点 8 的第半圆数个结点，下一个是第1/4 圆数个结
点 51 。这个例子中结点 8 的指针表储存着结点 42 、 51 、 56
信息。
N21
1'138
N32
圄 2 Chord 的查找路径
一个结点把键值 K 查找消息推进到它的指针表中 ID 最
大且比键值 K 小结点。指针表的 2 的次方结构确保了结点总
是能把查询消息最少推进剩余 ID 空间一半的距离。因此
Chord 查询使用了。(log N)条消息。
新结点 n 如何确定自己在 Chord 系统中位置， Chord 通
过如下方法实现:为了这个新结点能正确地加入这个系统，
系统需要做的是更新它的和它前键结点的后续列表。新结点
通过请求其他己存在的结点来查找将分配结点 n 的 ID。即使
在有相似 ID 的结点同时加入系统中， Chord 也能确保其正确
性。更新的结点和已经存在的结点指针表只要蕴式地进行，
因为它只是在性能上要求的，不是正确性上要求的。新的结
点同时必须获得它存储键值的所有相关的数据。后继关系确
保所有键值都可以从新结点的后续结点获得。
随机性保证了 Chord 键值和结点 ID 初步统一地分布在
ID 空间里，确保结点问负载平衡。 Chord 对存储在结点的键
值空间片通过虚拟结点来控制。在 Chord 系统中的每个物理
结点有多份虚拟结点 ID，增加虚拟 ID 会增加结点存储键值
的数量。 Chord 能够路由一个消息可以在低查询延迟时间的
路径上进行;它是通过充分利用存在许多指针表记录更容易
把查询推进到目的结点。每个这样的记录都有显著的代价(查
询延迟时间)和益处(在 ID 空间的进度)。
Pastry
Pastry[2-4 1每个结点都有一个随机选定的 ID，概念上它表
明了结点在标识圈内的位置。 Pastry 路由键值消息到一个活
跃结点，这个结点的 ID 数字和这个键值很相似。 ID 空间的
位数是?的倍数。其中 b 是一个算法的参数，一般 b 为 4 ，
ID 空间的位数就 128 。
Pastry 使用一个基于前缀推进机制。每个结点 n 维护一
个叶子集合 L ， 该集合中有ILI/2 个最靠近结点 n 的且比 n 小
的结点，有ILI/2 个最靠近结点 n 的且比 n 大的结点。叶子集
合的正确性是消息正确推进的唯一要求;除非ILI/2 个 ID 邻近
的结点同时失败，否则数据定位消息就能正确推进。叶子结
合在概念上和 Chord 的后继列表相似。
为了优化消息的推进性能， Pastry 维护一个指向分布在
ID 空间其他结点的路由表。这个路由表是一个 rlog，b巾，每
行有 2 D_1个项。结点n路由表的第 i行的每个项指向 ID的前
i位和结点 n相同的结点，并且它的第 i+1位是不同的 (最
多有2D_1种可能)。如图3所示，假设b=2，结点ID空间8
位，结点 10233102的叶子集合；路由表和邻居结点的结构图。
所有数据都是 4的倍数，路由表顶行是第 0行，每行的阴影
单元格表示当前结点 ID对应的位，在路 由表中每一项结点
ID都是用特定形式(10233102共享前缀一共享前缀的下一位
一 剩下位)来描述的。
Nodeld l0233l02
Leaf set SMALLER LAR旺 R
l 0233033 l023302l l0233 l20 l0233 I22
1023300I l 0233000 l 0233230 l 0233232
Routine table
一 0—22l2l0 ] —2—230l 203 —3一l203203
l—l一30l 233 l一2—230203 l一3—02l022
l 0—3203 l l一32l03 l 3—23302
l02—0—0230 lO2_l—l302 l02—2—2302
l 023_0—322 l023_l一000 l023_2一l2l
l0233-0—0l l0233-2—32
l02331-2．0
NeighbOrhOod set
l302l022 l 0200230 Il30l 233 3l30l233
02 2l 2l02 2230l203 3l 203203 332l332l
图3结点10233102的叶子集合，路由表和邻居结合结枸
给定叶子集合和路由表，结点 n推进查询消息：如果要
找的键值存储在叶子集合中的结点，查询消息就推进到给这
个结点。一般来说 ，直到查询消息推进到 ID较靠近键值的结
点时才会发生这样情况。在这种情况下，查询消息会被推进
到路由表中 ID和结点 n具有较长共同前缀的结点。
结点 n无法到达的结点项可能会从路由表中丢失，在该
种情况下结点n推进一个查询消息给 ID的共同前缀和结点n
一 样长的结点，并且这个结点的ID数字上更靠近键值。这样
的结点一定在 n的叶子集合中，除非这个查询已经到达数字
上和这个键值更相近 ID的结点或者到达了它的直接邻居。
如果路由表和叶子集合都正确，预期的 Pastry路由一个
键值到正确的结点的路由数至多为I log h N I。因为每步路由
j 』
结点和键值问的共同位数就增加一位。最后查询消息接触到
叶子集合只需要一步。
Pastry有个加入操作协议，它沿着出发结点或者 ID 空
间的最靠近结点到新结点路径获得信息来建立路由表和叶子
集合。这个方法简化了新结点的叶子集合正确性的维护，然
后蕴式地建立路由表，就像在 Chord一样。结点离开时也使
用这个方法。当一个结点企图到达一个不存在的结点和无法
到达的结点，那么就要马上更新叶子集合结点，和更新路由
表信息。
3．4 Tapestry
Tapestry,1 5]是 Plaxtonet等人开发的基于数据定位机制 j
像所有其他的数据定位机制一样，Tapestry映射结点与键值
标识成数字串，并且通过一次增加一位共同位来推进数据定
位到正确的结点。详见文献【5】。
4性能比较
表 1是 4种算法的性能对照表。Node state行标识每个
结点被多少个其他结点所知。Lookup和 Join行表明为每个
操作需要多少条消息。～ 是系统的总结点数，d是 CAN 的
维数。
表 1各个算法代价比较
CAN Chord Pastry Tapestry
Node state d Iog N Iog N log N
Lookup d*N log N log N log N
Join d*N +d*log(N) Log!N Log N Log—N
操作代价：表 1总结了主要操作的代价。Chord，Pastry和
Tapestry几乎一致；不管系统大小 CAN 的路由表大小为常
数，但是查询代价 CAN比其他系统增加得更快。
查询延迟时间：Pastry，CAN，和 Tapestry都有一个启
发式选择路由表中的指向系统中附近结点路径，减少了查询
的延迟时间。
恶意结点：Pastry使用安全证书来证明结点的身份 过
将抵制恶意结点。但代价就是信任一个认证机构。本文描述
的算法都有潜能执行交叉检测来监测因为恶意或错误导致的
不正确路由，因此在推进路由消息时，核实ID空间是否有进
度是可以做到的。数据的权限是要通过加密保证的。
总之， 4种对等数据定位算法优点和缺点反映了设计者
对不同问题考虑的优先性。这些算法扩展性强，查找延迟时
间短，扩展地处理结点的接入和分离，结点路由表维护信息
少以及负载平衡处理得好。在适当的场合采用适合的算法，
DHT将会在国际互联网应用上很有价值。
参考文献
1 Balazinskam．A Scalable Peer—to—Peer Architecture for Intentional
Resource Discovery[C]．Proc．of lnt．Cone on Pervasive Computing．
Zurich．Switzerland．2o02—08．
2 Dabek F．Wide—area Cooperative Storage with CFS[C]．Proc．of the
1 8 ACM Symposium on Operating Systems Principles．200 1—1 0
3 Hildrum．Distributed Object Location in a Dynamic Network[C]．Proc
of the 14 ACM Syrup．on Parallel Algorithms and Architectures．
2002—08．
4 Malkhi D A Scalable and Dynamic Emulation of the Butterfly[C]
Proceedings of the 2 1 Annual ACM Symposium on Principles of
Distributed Computing，2002—07．
5 Maymounkov．A Pee~to—Peer Information System Based on the XOR
Metric[C】．Proc．of the 1 International Workshop on Peer．to．Peer
Systems．2002．05．
一 269-一
维普资讯
行有 2b_1 个项。结点 n 路由表的第 i 行的每个项指向 ID 的前
I 位和结点 n 相同的结点，并且它的第 i+1 位是不同的(最
多有 2b_1 种可能)。如图 3 所示，假设 b=2，结点 ID 空间 8
位，结点 10233102 的叶子集合;路由表和邻居结点的结构图。
所有数据都是 4 的倍数，路由表顶行是第 O 行，每行的阴影
单元格表示当前结点 ID 对应的位，在路由表中每一项结点
ID 都是用特定形式(1 0233102 共享前缀一共享前缀的下一位
一剩下位)来描述的。
Node!d 10233102
Leaf set SMALLER I LARæR
Routing tablc
回 3 结点 10233102 的叶子集合，路由袭和邻居结合结构
给定叶子集合和路由表，结点 n 推进查询消息:如果要
找的键值存储在叶子集合中的结点，查询消息就推进到给这
个结点。一般来说，直到查询消息推进到 ID 较靠近键值的结
点时才会发生这样情况。在这种情况下，查询消息会被推进
到路由表中 ID 和结点 n 具有较长共同前缀的结点。
结点 n 无法到达的结点项可能会从路由表中丢失，在该
种情况下结点 n 推进一个查询消息给 ID 的共同前缀和结点 n
一样长的结点，并且这个结点的 ID 数字上更靠近键值。这样
的结点一定在 n 的叶子集合中，除非这个查询已经到达数字
上和这个键值更相近 ID 的结点或者到达了它的直接邻居。
如果路由表和叶子集合都正确，预期的 Pastry 路由一个
键值到正确的结点的路由数至多为 IIOg岁儿因为每步路由
结点和键值间的共同位数就增加一位。最后查询消息接触到
叶子集合只需要一步o
Pastry 有个加入操作协议，它捂着出发结点或者 ID 空
间的最靠近结点到新结点路径获得信息来建立路由表和叶子
集合。这个方法简化了新结点的叶子集合正确性的维护，然
后蕴式地建立路由表，就像在 Chord 一样。结点离开时也使
用这个方法。当一个结点企图到达一个不存在的结点和无法
到达的结点，那么就要马上更新叶子集合结点，和更新路由
表信息。
3 .4 Tapestry
Tapestryl51是 P1axtonet 等人开发的基于数据定位机制[-l]士
像所有其他的数据定位机制一样， Tapestry 映射结点与键值
标识成数字串，并且通过 4次增加一位共同位来推进数据定
位到正确的结点。详见文献[5] 。
4 性能比较
表 l 是 4 种算法的性能对照表。 Node state 行标识每个
结点被多少个其他结点所知。 Lookup 和 Join 行表明为每个
操作需要多少条消息。 N 是系统的总结点数 ， d 是 CAN 的
维数。
表 1 各个算法代价比tl
CAN Chord Pastrv Tapestry
Node state d log N log N log N
Lookup d*N"d 10g N 10gN 10gN
Join d*N l/d+d*log(N) Log'N Log-N Log-N
操作代价:表 l 总结了主要操作的代价。 Chord， Pastry 和
Tapestry 几乎一致;不管系统大小 CAN 的路由表大小为常
数，但是查询代价 CAN 比其他系统增加得更快。
查询延迟时间 Pastry ， CAN，和 Tapestry 都有一个启
发式选择路由表中的指向系统中附近结点路径，减少了李询
的延迟时间。
恶意结点 Pastry 使用安全证书来证明结点的身份 达
将抵制恶意结点。但代价就是信任一个认证机构。本文描述
的算法都有潜能执行交叉检测来监测因为恶意或错误导致的
不正确路由，因此在推进路由消息时，核实 ID 空间是否有进
度是可以做到的。数据的权限是要通过加密保证的。
总之 4 种对等数据定位算法优点和缺点反映了设计者
对不同问题考虑的优先性。这些算法扩展性强，查找延迟时
间短，扩展地处理结点的接入和分离，结点路由表维护信息
少以及负载平衡处理得好。在适当的场合采用适合的算法，
DHT 将会在国际互联网应用上很有价值。
参考文献
I Balazinskam. A Scalable Peer-to-Peer Architecture for !ntentional
Resource Discovery[C]. Proc. of !nt. Con f. on Pervasive Computing.
Zurich , Switzerland电 2002-08.
2 Dabek F. Wide-area Cooperative Storage with CFS[C]. Proc. of the
181h ACM Symposium on Operating Systems Principles , 200 1-1 0
3 Hildrum. Distributed Object Location in a Dynamic Network[C]. Proc
。f the 141h ACM Symp. on Parallel Algorithms and Architectures.
2002-08
4 Malkhi D. A Scalable and Dynamic Emulation of the Buttertly[C]
Proceedings of the 21 1h Annual ACM Symposiu日1 on Principles of
Distributed Computing, 2002-07
5 Maymounkov. A Peer-to-Peer !nformation System Based on the XOR
Metric[C]. Proc. of the 1 '1 !ntemational Workshop on Peer-to-Peer
Systems, 2002-05
-269-一
