对等网络中主流分布式哈希算法比较分析

讨论

一致性哈希基本解决了在P2P环境中最为关键的问题——如何在动态的网络拓扑中分布存储和路由。每个节点仅需维护少量相邻节点的信息，并且在节点加入/退出系统时，仅有相关的少量节点参与到拓扑的维护中。所有这一切使得一致性哈希成为第一个实用的DHT算法。

但是一致性哈希的路由算法尚有不足之处。在查询过程中，查询消息要经过O(N)步(O(N)表示与N成正比关系，N代表系统内的节点总数) 才能到达被查询的节点。不难想象，当系统规模非常大时，节点数量可能超过百万，这样的查询效率显然难以满足使用的需要。换个角度来看，即使用户能够忍受漫长的时延，查询过程中产生的大量消息也会给网络带来不必要的负荷。

下文中讨论的几种DHT协议都对路由做出了优化，提出了各自的算法。

Chord协议

Chord在2001年由麻省理工学院提出(参见0)，其核心思想就是要解决在P2P应用中遇到的基本问题：如何在P2P网络中找到存有特定数据的节点。与前两种协议不同，Chord专门为P2P应用设计，因此考虑了在P2P应用中可能遇到的特殊问题，这些内容将在路由的部分进行讨论。

哈希算法

Chord使用一致性哈希作为哈希算法。在一致性哈希协议中并没有定义具体的算法，在Chord协议中将其规定为SHA-1。

路由算法

Chord在一致性哈希的基础上提供了优化的路由算法：

在Chord中，每个节点同样需要存储m个其他节点的信息，这些信息的集合被称为查询表(Finger Table)。一致性哈希中的节点同样具有这样的表格，但在Chord中，表格中的节点不再是直接相邻的节点，它们的间距(ID间隔)将成2i 的关系排列(i 表示表中的数组下标)。这样形成的节点之间路由关系实际上就是折半查找算法需要的排列关系。

在查询的过程中，查询节点将请求发送到与键值最接近的节点上。收到查询请求的节点如果发现自身存储了被查询的信息，可以直接回应查询节点 (这与一致性哈希完全相同)；如果被查询的信息不在本地，就根据查询表将请求转发到与键值最接近的节点上。这样的过程一直持续到找到相应的节点为止。不难看出，查询过程实际上就是折半查找的过程。

经过Chord的优化后，查询需要的跳数由O ( N)减少到O(log(N))。这样即使在大规模的P2P网络中(例如N＝100,000,000)，查询的跳数也仅为O(8)，每个节点仅需存储27个(log2100000000)其他节点的信息。

Chord还考虑到多个节点同时加入系统的情况并对节点加入/退出算法作了优化。

讨论

Chord算法本身具有如下优点：

负载平衡

这一优点来自于一致性哈希，也就是一致性哈希中提到的平衡性。所有的节点以同等的概率分担系统负荷，从而可以避免某些节点负载过大的情况。

分布性

Chord是纯分布式系统，节点之间完全平等并完成同样的工作。这使得Chord具有很高的鲁棒性，可以抵御DoS攻击。

可扩展性

Chord协议的开销随着系统规模(结点总数N)的增加而按照O(logN)的比例增加。因此Chord可以用于大规模的系统。

可用性

Chord协议要求节点根据网络的变化动态的更新查询表，因此能够及时恢复路由关系，使得查询可以可靠地进行。

命名的灵活性

Chord并未限制查询内容的结构，因此应用层可以灵活的将内容映射到键值空间而不受协议的限制。

Chord在CFS系统中得到了应用，具体的介绍可参见[8]

内容寻址网络(Content-Addressable Network，CAN)

CAN在2001年由加州大学伯克利分校提出(参见[3])。与Chord一样，CAN也是DHT的一个变种。

哈希算法

CAN的哈希算法与一致性哈希有所不同。Chord中，哈希得到的键值总是一维的，而在CAN中，哈希的结果由d维的笛卡尔空间来表示。d是一个由系统规模决定的常量。

路由算法

CAN的路由查询将在d维笛卡尔空间中进行。

在CAN中，每个节点自身的ID经由哈希后得到的d维向量。经过这样的映射后，整个P2P系统将被映射到一个d维笛卡尔空间中，每个节点的位置由其自身ID决定。CAN对邻居节点的定义并不要求成2i的关系排列，而是改为用在笛卡尔空间上相邻来表示：在d维笛卡尔空间中，2个节点的d维坐标中有d-1维是相等的，剩余的一维是相邻的节点称之为相邻节点。

CAN中的节点仅存储相邻节点表。由于在d维的空间中最多有2d个相邻的节点，因此节点的相邻节点表最多有2d个表项。

在查询的过程中，查询节点首先计算被查询内容的键值(d维向量)，然后在节点列表中查找在笛卡尔空间中与该键值最为接近的相邻节点，找到后向该节点发送查询请求(这一策略被称为贪婪策略)。查询请求中将携带被查询内容的键值。收到查询请求的节点如果发现自身存储了被查询的信息，可以直接回应查询节点(这与一致性哈希完全相同)；如果被查询的信息不在本地，就根据相邻节点表将请求转发到与键值最接近的节点上。这样的过程一直持续到找到相应的节点为止。在查询过程中，被查询节点到目标节点的笛卡尔空间距离单调地减少。

如果查询节点或转发节点发现邻居节点表中无法找到可用的下一跳节点，则采用非结构化P2P常用的扩展环搜索(Expanding Ring Search，使用无状态，受控的泛洪算法在重叠网中搜索)以找到合适的(符合贪婪策略)下一节点。

经过CAN的优化后，查询需要的跳数由O ( N)减少到均值为(d/4)(n1/d)的随机制，考虑到d为常数，这一值可以表示为O(n1/d)或O(dn1/d)。

讨论

CAN和Chord的主要区别在于路由算法不同。相比之下，在节点数量非常大时，CAN的平均查询跳数要比Chord增加得更快。而且 CAN查询过程中需要的运算量也要高于Chord。但CAN使用的d为预先设置的常量，因此并不假设系统节点数量。在节点总数动态变化范围很大的系统中， CAN的相邻节点表结构保持稳定，这在P2P的应用中也是很重要的优点。

Pastry

Pastry在2001年由位于英国剑桥的微软研究院和莱斯(Rice)大学提出(参见[4])。Pastry也是DHT的一个变种。

哈希算法

Pastry使用一致性哈希作为哈希算法。哈希所得的键值为一维(实际上使用的是128bit的整数空间)。Pastry也没有规定具体应该采用何种哈希算法。

路由算法

在Pastry协议中，每个节点都拥有一个128bit的标识(Node Id)。为了保证Node ID的唯一性，一般由节点的网络标识(如IP地址)经过哈希得到。

Pastry中的每个节点拥有一个路由表R(Routing table)，一个邻居节点集M(Neighborhood Set)和一个叶子节点集合L(Leaf set)，它们一起构成了节点的状态表。

路由表R共有logBN(B = 2b为系统参数，典型值为16，N表示系统的节点总数)行，每行包括B-1个表项，每个表项记录了一个邻居节点的信息(节点标识、IP地址、当前状态等)。这样就形成了拥有(B-1)logBN个条目的二维表格。路由表第n行的表项所记录的邻居节点的Node ID前n个数位和当前节点的前n个数位相同，而第n＋1个数位则分别取从0到B-1的值(除了与当前节点第n＋1数位的值)。这样形成的路由表很类似IP 路由中最长掩码匹配的算法。参数b(或B)大小非常关键：B过大则节点需要维护很大的路由表，可能超出节点的负载能力，但路由表大些可以存储更多的邻居节点，在转发时更为精确。平均每次路由查找需要的跳数在Pastry中计算的结果是logBN，因此B的选择反映了路由表大小和路由效率之间的折衷。

叶子节点集合L中存放的是在键值空间中与当前节点距离最近的|L|个节点的信息，其中一半节点标识大于当前节点，另一半节点标识小于当前节点。|L|的典型值为2b或者2*2b。

邻居节点集合M中存放的是在真实网络中与当前节点“距离”最近的|M|个节点的信息。“距离”的定义在Pastry中非常类似IP路由协议中对距离的定义，也就是考虑到转发跳数、传输路径带宽、QoS等综合因素后所得的转发开销(可以参见OSPF等路由协议)。Pastry并未提供距离信息的获取方法，而是假设应用层可以通过某种手段(人工配制或自动协商)得到信息并配置邻居节点集合。|M|的典型值为2b或者2*2b。

图 3给出了一个Pastry节点状态表的例子，该图来源于[4]。

在节点状态表中，节点本身的ID为10233102。叶子集合中有8项，每一项都代表一个当前节点已知的其他节点的信息。路由表共有4*8项，可以看出由上至下节点ID重合的位数(前缀)不断增加。邻居集合中的节点ID由于来源于应用层，一般没有规律性可循。

Pastry的路由过程如下：

首先，路由查询消息中将携带被查询对象ID(Object Id)，又称消息键值。当收到路由消息时，节点首先检查消息键值是否落在叶子节点集合的范围内。如果是，则直接把消息转发给叶子节点集合中节点标识和消息键值最接近的节点；否则就从路由表中根据最长前缀优先的原则选择一个节点作为路由目标，转发路由消息。如果不存在这样的节点，当前节点将会从其维护的所有邻居节点集合(包括路由表叶子集合及邻居集合中的节点)中选择一个距离消息键值最近的节点作为转发目标。

从上述过程中可以看出，每一步路由和上一步相比都更靠近目标节点，因此这个过程是收敛的。如果路由表不为空，每步路由至少能够增加一个前缀匹配数位，因此在路由表始终有效时，路由的步数至多为logBN。

讨论

Pastry的路由利用了成熟的最大掩码匹配算法，因此实现时可以利用很多现成的软件算法和硬件框架，可以获得很好的效率。

与Chord和CAN相比，Pastry引入了叶子节点和邻居节点集合的概念。在应用层能够及时准确地获得这两个集合的节点信息时，可以大大加快路由查找的速度，同时降低因路由引起的网络传输开销；不过在动态变化的P2P网络中如何理想地做到这一点的确有很大的难度。

Pastry的典型应用包括PAST(参见[5][6])和SCRIBE(参见[7])。

趋势分析

目前DHT算法的发展方向非常多，不断有新的改进算法被提出来。就笔者目前了解到的信息而言，至少有以下一些方向：

接近性(Proximity)

文中提到的DHT算法中，除了Pasrty以外，均未考虑重叠网络拓扑结构与真实的IP网络之间的重合关系。节点之间进行对等通信时，不会考虑优先选取距离自己最近的节点。这样就使得最终形成的重叠网结构混乱，效率低下。因此如何让节点获得并利用接近性信息就非常重要。

结构化

目前基于DHT的应用尚未大规模展开，很多工程上的细节问题尚待解决。例如：目前有很多种类的P2P应用，如文件存储和共享、电子邮件、流媒体等。这些应用在处理P2P路由算法、拓扑维护和信息检索上使用的方法均有很大差别，导致即使是同类的应用也无法实现互通。如何为各种P2P的应用抽象出一个通用的层次，也是目前研究的热点问题之一。

信息查询

基于分布式哈希表的查询是一种单关键字的精确匹配，尽管相对于非结构化系统它使得系统资源可被确定性地查询到，但它也极大地限制了查询的应用范围。目前有许多改进的结构化查询算法已经被提出来。

参考文献

David Karger, Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin, Rina Panigrahy “Consistent Hashing and Random Trees:Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web”. In Proceedings of the 29th Annual ACM Sym-posium on Theory of Computing (El Paso, TX, May 1997), pp. 654-663.

Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishnan_ “Chord: A Scalable Peertopeer Lookup Service for Internet Applications” SIGCOMM’01, August 2731, 2001, San Diego, California, USA.

Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, Scott Shenker “A Scalable Content-Addressable Network” SIGCOMM’01, August 27-31, 2001, San Diego, California, USA..

Antony Rowstron1 and Peter Druschel “Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems” Appears in Proc. of the 18th IFIP/ACM International Conference on Distributed Systems Platforms (Middleware 2001). Heidelberg, Germany, November 2001.

P. Druschel and A. Rowstron. PAST: A large-scale, persistent peer-to-peer storage utility. In Proc. HotOS VIII, Schloss Elmau, Germany, May 2001.

A. Rowstron and P. Druschel. Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility. In Proc. ACM SOSP’01, Banff, Canada, Oct. 2001.

A. Rowstron, A.-M. Kermarrec, P. Druschel, and M. Castro. Scribe: The design of a large-scale event notification infrastructure. Submitted for publication. June 2001. http://www.research.microsoft.com/ antr/SCRIBE/.

F. Dabek, M. F. Kaashoek, D. Karger, R. Morris, and I. Stoica. Wide-area cooperative storage with CFS. In Proc. ACM SOSP’01, Banff, Canada, Oct. 2001.

Keith W. Ross, Dan Rubenstein, “P2P Systems”

宁宁，“对等网络组通信机制的位置感知技术研究Research on Location-Aware Tech-nology in Peer-to-Peer Group Com-munication Mechanism”，申请清华大学工学硕士学位论文，May.2005.

李祖鹏，黄建华，唐辉，“基于P2P计算模式的自组织网络路由模型”，软件学报，1000-9825/2005/16(05)0916

胡进锋，郑纬民(清华大学计算机系高性能计算研究所，北京，100084)，“p2p系统结点信息收集算法 Node Collection Protocol in P2P Systems”

邹福泰，马范援(上海交通大学计算机科学与工程系)，“基于分布式哈希表的对等系统关键技术研究RESEARCH ON THE KEY TECHNIQUE OF PEER-TO-PEER SYSTEMS BASED ON DISTRIBUTED HASH TABLE”，申请上海交通大学博士学位论文，二零零四年十一月