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

http://www.eetchina.com/ART88004091966752772c33040a200603no.HTM

本文首先从P2P的定义出发，介绍了结构化P2P与非结构化P2P的区别以及结构化P2P的核心技术DHT。而后，本文深入介绍了几种主流的DHT算法与协议并对每种协议进行了讨论。文章的最后展望了DHT在未来的发展趋势。

对等网络(Peer-to-Peer，简称P2P)是目前非常热门的应用，自1999年以来，P2P的研究一直是国外知名学府(如美国麻省理工学院，加州大学伯克利分校和莱斯大学等)以及知名企业的研发机构(如微软，诺基亚的研究院)关注的重点。它甚至被美国《财富》杂志称为改变因特网发展的四大新技术之一，被认为是代表无线宽带互联网未来的关键技术。

作为一项新兴的技术，目前学术界对P2P在技术层面上的定义尚未统一。Keith W. Ross (Polytechnic University)和Dan Rubenstein(Columbia University)在[9]中提到了对P2P系统的3个基本定义：

相比中央服务器而言有明显的自治性(Autonomy)。

利用网络边缘的资源，如存储/计算能力和信息资源。

网络边缘的资源处在动态的变化中(新的资源加入，已有的资源消失)。

自治性的要求使得P2P系统不再需要特定的中央管理机制，所有节点之间拥有对等的关系。这一方面为系统带来了自组织、容错性好、可扩展性强等优点；另一方面也提出了新的问题：如何在没有集中管理机制的情况下实现系统的自组织和自管理？

定义2，3中分布性和动态性的特点使得上述问题的实现具有更大的难度。在分布式系统中，过多过快的信息交互可能消耗大量的网络资源；而为了实时反映系统的变化，又要求节点及时获得更新信息，这就需要在节点之间进行通信。

为了解决这一对矛盾，已经有许多P2P的框架和协议被提出来并得到了很好的应用。

结构化与非结构化P2P

依照节点信息存储与搜索方式的不同，诸多P2P协议可以分为2大类：结构化(Structured)的与非结构化(Unstructured)的系统。

非结构化P2P系统

在非结构化的系统中，每个节点存储自身的信息或信息的索引(如指针和IP地址)。当用户需要在P2P系统中获取信息时，他们预先并不知道这些信息(如某个文件)会在那个节点上存储。因此，在非结构化P2P系统中，信息搜索的算法难免带有一定的盲目性，例如最简单的泛洪式查找(类似于广播)和扩展环查找(从最近的n个节点开始，层层转发直到找到目标或超出了跳数的上限为止)。

一些典型的应用采用了一些优化的办法。如在Gnutella中，采用了等级制的组成结构：节点被分成超级节点(Super Node)和普通节点。普通节点必须依附于超级节点，每个超级节点作为一个独立的域管理者，负责处理域内的查询操作。在查找的过程中，查询首先在域内进行，失败后才会扩展到超级节点之间。

非结构化系统的优点在于实现结构简单：无须中央服务器，节点之间完全平等，网络的层次是单一的，而且节点之间无需维护拓扑信息。

结构化P2P系统

在结构化P2P系统中，每个节点只存储特定的信息或特定信息的索引。当用户需要在P2P系统中获取信息时，他们必须知道这些信息(或索引)可能存在于那些节点中。由于用户预先知道应该搜索哪些节点，避免了非结构化P2P系统中使用的泛洪式查找，因此提高了信息搜索的效率。

但是，结构化P2P也引入了新的问题：

首先，既然信息是分布存储的，那么如何将信息分布存储在重叠网中的节点上？

其次，由于节点动态的加入和离开重叠网，如何将拓扑的变更信息通知其它节点？

DHT的引入基本解决了上述问题，因此自从DHT协议出现以后，结构化P2P的应用得到了快速的发展。目前已经有很多较为成熟的DHT协议被提出并且得到了应用。其中比较有代表性的有：缓冲阵列路由协议(CARP)；一致性哈希；Chord；内容寻址网络；Pastry。

DHT简介

DHT使用分布式哈希算法来解决结构化的分布式存储问题。分布式哈希算法的核心思想是通过将存储对象的特征(关键字)经过哈希运算，得到键值(Hash Key)，对象的分布存储依据键值来进行。具体来讲，大致有以下步骤：

对存储对象的关键字进行哈希运算，得到键值。这样就将所有的对象映射到了一个具体的数值范围中。

重叠网中的每个节点负责数值范围中的特定段落。例如，节点A负责存储键值从8000到8999的对象；而节点B负责7000~7999的对象。这样就将对象集合分布地存储在所有的节点中。

节点可以直接存储对象本身，如文件中的一个片段；也可以存储对象的索引，如该对象所在节点的IP地址。

结构化的分布式存储问题解决后，剩下的问题就是用户如何才能找到存储着目标信息的节点。在有着大量节点(如100万个)的P2P系统中，任何节点都不可能拥有全部的节点?键值?内容的对应关系；因此用户获得了键值之后，如何找到该键值对应的节点就被称为DHT的路由问题。DHT协议必须定义优化的查找(路由)算法来完成这一搜寻的工作。不同的DHT协议之间区别很大程度上就在于定义了不同的路由算法。

DHT的应用非常简洁—-API简单到只有一项输入和一项输出：

应用层将数据对象(文件、数据块或索引)通过哈希算法获得键值，将该键值提交给DHT后，返回结果就是键值所在节点的IP地址。图1(来自[9])显示了这种应用结构：

图 1 DHT的应用结构

在这样的支持下，可以开发多种P2P的应用程序，如网络存储与文件共享、即时消息、音频/视频等。图2(来自[9])显示了这种应用结构：

图 2 DHT应用的层次

主流DHT协议

缓冲阵列路由协议(CARP，Cache Array Routing Protocol)

协议简介

CARP是由微软公司的Vinod Valloppillil和宾西法尼亚大学的Keith W. Ross在1997年提出的。该协议可以将URL空间映射到一个仅有松散关联关系的Web cache 服务器(在协议中称为“代理”，Proxy)阵列中。支持该协议的HTTP客户端可以根据要访问的URL智能选择目标代理。该协议解决了在代理阵列内分布存储内容的问题，避免了内容的重复存储，提高了客户端访问时Web Cache命中的概率。

哈希算法

哈希使用的关键字有2个，一个是代理的标识符(每个代理均有唯一的标识)，另一个是URL本身。存储内容时，每个代理负责缓冲哈希键值最大的URL。这样，当缓冲代理阵列发生少量变化时(新的代理加入或旧的代理退出)，原有的URL还有可能仍然被映射到原来的代理上，仍可以按照原有的方式访问。

路由算法

客户端(HTTP浏览器)首先加载一个代理配置文件，该文件中存储了代理的标识符和IP地址等用于哈希的关键参数。浏览器在访问网页时，可以根据URL和代理标识获得代理的位置信息(IP地址)，从而可以直接访问缓冲代理中的页面。

讨论

CARP的哈希过程比较简单，路由查找更是简单到至多只有一跳(O(1))。但是CARP在P2P的应用环境中有一些致命的缺陷：

每个节点必须知道其它所有节点的信息。在大规模的重叠网环境中，由于可能存在大量的(数百万)节点，加之节点都是动态加入和退出网络，因此这一条件几乎不可能满足。

在缓冲阵列发生较大变化时(这在P2P网络中非常常见)，原有的URL和代理之间的对应关系可能发生改变，从而使得原有的配置文件失效。

一致性哈希(Consistent Hash)

协议简介

一致性哈希算法在1997年由麻省理工学院提出(参见0)，设计目标是为了解决因特网中的热点(Hot pot)问题，初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题，使得DHT可以在P2P环境中真正得到应用。

哈希算法

一致性哈希提出了在动态变化的Cache环境中，哈希算法应该满足的4个适应条件：

平衡性(Balance)

平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。

单调性(Monotonicity)

单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。

简单的哈希算法往往不能满足单调性的要求，如最简单的线性哈希：

x → ax + b mod (P)

在上式中，P表示全部缓冲的大小。不难看出，当缓冲大小发生变化时(从P1到P2)，原来所有的哈希结果均会发生变化，从而不满足单调性的要求。

哈希结果的变化意味着当缓冲空间发生变化时，所有的映射关系需要在系统内全部更新。而在P2P系统内，缓冲的变化等价于Peer加入或退出系统，这一情况在P2P系统中会频繁发生，因此会带来极大计算和传输负荷。单调性就是要求哈希算法能够避免这一情况的发生。

分散性(Spread)

在分布式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。

负载(Load)

负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。

从表面上看，一致性哈希针对的是分布式缓冲的问题，但是如果将缓冲看作P2P系统中的Peer，将映射的内容看作各种共享的资源(数据，文件，媒体流等)，就会发现两者实际上是在描述同一问题。

路由算法

在一致性哈希算法中，每个节点(对应P2P系统中的Peer)都有随机分配的ID。在将内容映射到节点时，使用内容的关键字和节点的ID进行一致性哈希运算并获得键值。一致性哈希要求键值和节点ID处于同一值域。最简单的键值和ID可以是一维的，比如从0000到9999的整数集合。

根据键值存储内容时，内容将被存储到具有与其键值最接近的ID的节点上。例如键值为1001的内容，系统中有ID为1000，1010，1100的节点，该内容将被映射到1000节点。

为了构建查询所需的路由，一致性哈希要求每个节点存储其上行节点(ID值大于自身的节点中最小的)和下行节点(ID值小于自身的节点中最大的)的位置信息(IP地址)。当节点需要查找内容时，就可以根据内容的键值决定向上行或下行节点发起查询请求。收到查询请求的节点如果发现自己拥有被请求的目标，可以直接向发起查询请求的节点返回确认；如果发现不属于自身的范围，可以转发请求到自己的上行/下行节点。

为了维护上述路由信息，在节点加入/退出系统时，相邻的节点必须及时更新路由信息。这就要求节点不仅存储直接相连的下行节点位置信息，还要知道一定深度(n跳)的间接下行节点信息，并且动态地维护节点列表。当节点退出系统时，它的上行节点将尝试直接连接到最近的下行节点，连接成功后，从新的下行节点获得下行节点列表并更新自身的节点列表。同样的，当新的节点加入到系统中时，首先根据自身的ID找到下行节点并获得下行节点列表，然后要求上行节点修改其下行节点列表，这样就恢复了路由关系。