《对等网络(P2P)中主流分布式哈希算法比较分析》由会员分享，可在线阅读，更多相关《对等网络(P2P)中主流分布式哈希算法比较分析（12页珍藏版）》请在金锄头文库上搜索。
1、对等网络(P2P)中主流分布式哈希算法比较分析关键词:P2P,对等网络,Peer-to-Peer,摘要：本文首先从P2P的定义出发，介绍了结构化P2P与非结构化P2P的区别以 及结构化P2P的核心技术DHT而后，本文深入介绍了几种主流的 DHT算法与协 议并对每种协议进行了讨论。文章的最后展望了 DHT在未来的发展趋势。对等网络(Peer-to-Peer，简称 P2P)是目前非常热门的应用，自1999年以来，P 2P的研究一直是国外知名学府(如美国麻省理工学院，加州大学伯克利分校和莱斯大学等)以及知名企业的研发机构(如微软，诺基亚的研究院)关注的重点。它 甚至被美国财富杂志称为改变因特网发展的
2、四大新技术之一， 被认为是代表 无线宽带互联网未来的关键技术。作为一项新兴的技术，目前学术界对P2P在技术层面上的定义尚未统一。KeithW. Ross (Polytechnic University)和 Dan Rubenstein(Columbia University)在9中提到了对P2P系统的3个基本定义：相比中央服务器而言有明显的自治性(Auto nomy)。利用网络边缘的资源，如存储/计算能力和信息资源。网络边缘的资源处在动态的变化中(新的资源加入，已有的资源消失)。自治性的要求使得P2P系统不再需要特定的中央管理机制，所有节点之间拥有对 等的关系。这一方面为系统带来了自组织、容错
3、性好、可扩展性强等优点；另一 方面也提出了新的问题：如何在没有集中管理机制的情况下实现系统的自组织和 自管理？定义 2，3中分布性和动态性的特点使得上述问题的实现具有更大的难度。在分 布式系统中，过多过快的信息交互可能消耗大量的网络资源； 而为了实时反映系 统的变化，又要求节点及时获得更新信息，这就需要在节点之间进行通信。为了解决这一对矛盾，已经有许多P2P的框架和协议被提出来并得到了很好的应 用。结构化与非结构化 P2P依照节点信息存储与搜索方式的不同，诸多P2P协议可以分为2大类：结构化(S tructured)的与非结构化(Unstructured)的系统。非结构化P2P系统在非结构化的
4、系统中，每个节点存储自身的信息或信息的索引 （ 如指针和 IP 地 址）。当用户需要在P2P系统中获取信息时，他们预先并不知道这些信息（如某个 文件）会在那个节点上存储。因此，在非结构化 P2P系统中，信息搜索的算法难 免带有一定的盲目性，例如最简单的泛洪式查找（类似于广播）和扩展环查找（从 最近的 n 个节点开始，层层转发直到找到目标或超出了跳数的上限为止 ）。一些典型的应用采用了一些优化的办法。如在 Gnutella 中，采用了等级制的组 成结构：节点被分成超级节点（Super Node）和普通节点。 普通节点必须依附于超 级节点， 每个超级节点作为一个独立的域管理者， 负责处理域内的查询
5、操作。 在 查找的过程中，查询首先在域内进行，失败后才会扩展到超级节点之间。非结构化系统的优点在于实现结构简单：无须中央服务器，节点之间完全平等， 网络的层次是单一的，而且节点之间无需维护拓扑信息。结构化P2P系统在结构化P2P系统中，每个节点只存储特定的信息或特定信息的索引。 当用户需 要在P2P系统中获取信息时，他们必须知道这些信息（或索引）可能存在于那些节 点中。由于用户预先知道应该搜索哪些节点， 避免了非结构化P2P系统中使用的 泛洪式查找，因此提高了信息搜索的效率。但是，结构化P2P也引入了新的问题：首先，既然信息是分布存储的， 那么如何将信息分布存储在重叠网中的节点上？ 其次，由于
6、节点动态的加入和离开重叠网，如何将拓扑的变更信息通知其它节点？DHT勺引入基本解决了上述问题，因此自从 DHT协议出现以后，结构化P2P的应 用得到了快速的发展。目前已经有很多较为成熟的 DHT*议被提出并且得到了应 用。其中比较有代表性的有：缓冲阵列路由协议（CARP） 一致性哈希；Chord; 内容寻址网络； Pastry 。DHT简介DHT使用分布式哈希算法来解决结构化的分布式存储问题。分布式哈希算法的核 心思想是通过将存储对象的特征（关键字）经过哈希运算，得到键值（Hash Key）， 对象的分布存储依据键值来进行。具体来讲，大致有以下步骤：对存储对象的关键字进行哈希运算， 得到键值。
7、 这样就将所有的对象映射到了一 个具体的数值范围中。重叠网中的每个节点负责数值范围中的特定段落。 例如，节点A负责存储键值从 8000到8999的对象；而节点B负责70007999的对象。这样就将对象集合分布 地存储在所有的节点中。节点可以直接存储对象本身，如文件中的一个片段；也可以存储对象的索引，如 该对象所在节点的IP地址。结构化的分布式存储问题解决后，剩下的问题就是用户如何才能找到存储着目标 信息的节点。在有着大量节点（如100万个）的P2P系统中，任何节点都不可能拥 有全部的节点?键值?内容的对应关系； 因此用户获得了键值之后，如何找到该键 值对应的节点就被称为DHT勺路由问题。DHT
8、协议必须定义优化的查找（路由）算 法来完成这一搜寻的工作。不同的DHT*议之间区别很大程度上就在于定义了不 同的路由算法。DHT勺应用非常简洁-API 简单到只有一项输入和一项输出：应用层将数据对象（文件、数据块或索引）通过哈希算法获得键值， 将该键值提交 给DHT后，返回结果就是键值所在节点的IP地址。图1（来自9）显示了这种应 用结构：在这样的支持下，可以开发多种P2P的应用程序，如网络存储与文件共享、即时 消息、音频/视频等。图2（来自9）显示了这种应用结构：Nodeld 10233102叶子集合校天110233033102330211023312010233122|1023300110
9、2330001023323010233232路由表-0-2212102-2-2301203-3-1203203r s1-1-3012331-2-2302031-3-02102210-0-3120310-1-32102210-3-23302102-04)230102-1-1302102-2-23023I1023-0-3221023-1-0001023-2-121 I31102330-01110233-2-32o102331-2-02邻居集合130210221020023011301233313012330221210222301203 13120320333213321图2 DHT应用的层次主流
10、DHT协议缓冲阵列路由协议（CARP Cache Array Routing Protocol）协议简介CARPI由微软公司的 Vi nod Valloppillil和宾西法尼亚大学的 Keith W. Ross在1997年提出的。该协议可以将URL空间映射到一个仅有松散关联关系的 Web cache服务器（在协议中称为“代理”，Proxy）阵列中。支持该协议的HTTP客户端可以根据要访问的URL智能选择目标代理。该协议解决了在代理阵列内分布存 储内容的问题，避免了内容的重复存储，提高了客户端访问时 Web Cache命中的 概率。哈希算法哈希使用的关键字有2个，一个是代理的标识符（每个代理均
11、有唯一的标识），另一个是URL本身。存储内容时，每个代理负责缓冲哈希键值最大的URL这样，当缓冲代理阵列发生少量变化时（新的代理加入或旧的代理退出），原有的URL还有可能仍然被映射到原来的代理上，仍可以按照原有的方式访问。路由算法客户端（HTTP浏览器）首先加载一个代理配置文件，该文件中存储了代理的标识 符和IP地址等用于哈希的关键参数。浏览器在访问网页时，可以根据URL和代理标识获得代理的位置信息（IP 地址），从而可以直接访问缓冲代理中的页面。讨论CARP勺哈希过程比较简单，路由查找更是简单到至多只有一跳(0(1)。但是 CA RP在P2P的应用环境中有一些致命的缺陷：每个节点必须知道其它
12、所有节点勺信息。 在大规模勺重叠网环境中， 由于可能存 在大量的(数百万)节点， 加之节点都是动态加入和退出网络， 因此这一条件几乎 不可能满足。在缓冲阵列发生较大变化时(这在 P2P网络中非常常见)，原有的URL和代理之间 的对应关系可能发生改变，从而使得原有的配置文件失效。一致性哈希(Con siste nt Hash)协议简介一致性哈希算法在 1 997年由麻省理工学院提出(参见 0)，设计目标是为了解决 因特网中的热点(Hot pot)问题，初衷和 CAR叶分类似。一致性哈希修正了 CAR P使用的简单哈希算法带来的问题，使得 DHT可以在P2P环境中真正得到应用。哈希算法一致性哈希提
13、出了在动态变化的 Cache环境中，哈希算法应该满足的4个适应条件：平衡性(Bala nee)平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去， 这样可以使得所有的 缓冲空间都得到利用。很多哈希算法都能够满足这一条件。单调性(Mo noton icity)单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中， 又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲 中去，而不会被映射到旧的缓冲集合中的其他缓冲区。简单的哈希算法往往不能满足单调性的要求，如最简单的线性哈希：x ax + b mod (P)在上式中，P表示全部缓冲的大小。不难看出，当缓冲大小发生变
14、化时(从P1到P2)，原来所有的哈希结果均会发生变化，从而不满足单调性的要求。哈希结果的变化意味着当缓冲空间发生变化时， 所有的映射关系需要在系统内全 部更新。而在P2P系统内，缓冲的变化等价于 Peer加入或退出系统，这一情况 在 P2P 系统中会频繁发生， 因此会带来极大计算和传输负荷。 单调性就是要求哈 希算法能够避免这一情况的发生。分散性(Spread) 在分布式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。 当终端希望通过哈希过程将内容映射到缓冲上时， 由于不同终端所见的缓冲范围 有可能不同， 从而导致哈希的结果不一致， 最终的结果是相同的内容被不同的终 端映射到不同
15、的缓冲区中。 这种情况显然是应该避免的， 因为它导致相同内容被 存储到不同缓冲中去， 降低了系统存储的效率。 分散性的定义就是上述情况发生 的严重程度。 好的哈希算法应能够尽量避免不一致的情况发生， 也就是尽量降低 分散性。负载（Load）负载问题实际上是从另一个角度看待分散性问题。 既然不同的终端可能将相同的 内容映射到不同的缓冲区中， 那么对于一个特定的缓冲区而言， 也可能被不同的 用户映射为不同的内容。 与分散性一样， 这种情况也是应当避免的， 因此好的哈 希算法应能够尽量降低缓冲的负荷。从表面上看，一致性哈希针对的是分布式缓冲的问题，但是如果将缓冲看作 P2P 系统中的Peer,将映射的内容看作各种共享的资源（数据，文件，媒体流等）, 就会发现两者实际上是在描述同一问题。路由算法 在一致性哈希算法中，每个节点（对应 P2P系统中的Peer）都有随机分配的ID。 在将内容映射到节点时，使用内容的关键字和节点的 ID 进行一致性哈希运算并 获得键值。一致性哈希要求键值和节点 ID 处于同一值域。最简单的键值和 ID 可以是一维的，比如从 0000到 9999的整数集合。根据键值存储内容
