DHT资源搜索技术研究综述

DHT资源搜索技术研究综述 张一鸣, 李东升, 卢锡城 (国防科学技术大学 计算机学院 并行与分布处理国家重点实验室 , 长沙 410073) 摘 要: 资源搜索是大规模分布式应用的基础性关键技术之一。随着互联网的飞速发展，互联网资源的规 模巨大和动态性强等特点给资源搜索带来了巨大的挑战。DHT 资源搜索技术具有可扩展、延迟低、可靠性 高等优点，是一个新兴的研究领域。总体来看，在该领域已经开展了大量的研究工作，但各方面的发展并 不均衡，仍然具有若干需要解决的问题。本文对 DHT 资源搜索技术关键问题的研究现状进行了系统地介 绍与分析，并对未来的研究发展方向进行了探讨。 关键词: 分布式哈希表，资源搜索，对等网络 中图法分类号: TP393 1 引 言 随着计算技术与网络技术的广泛应用，互联网逐渐成为现代社会的重要信息基础设施[1,2]。互联网上 汇集了大量资源，包括计算资源、存储资源和信息资源等，资源搜索技术已成为互联网应用的基础性关键 技术之一。 传统的互联网应用通常采用客户端/服务器（C/S）的方式实现资源搜索，如图 1(a)所示，系统中存在 一个（或少数几个）中央服务器，资源所有者把资源（或资源信息）发布到服务器，资源请求节点到服务 器查找所需资源。文献[3]指出，随着互联网的飞速发展，互联网资源具有成长性（资源规模不断膨胀、资 源关联关系不断变化）、自治性（资源局部自治、自主决策）和多样性（资源属性存在广泛的差异）等三 个相互联系的自然特性，给资源搜索带来了巨大的挑战。由于不能适应上述特性，传统的基于 C/S 模式的 资源搜索方法逐渐成为互联网应用的性能瓶颈。 a) C/S 方式 b) P2P 方式 图 1 两种资源搜索方法示意图 另一方面，目前互联网上聚集了大量闲置的客户端资源，并且这些资源的数量和能力都在不断增长[4]。 据统计，目前全球连接到互联网的计算机已超过 4 亿台，互联网用户数量已超过 11 亿[5]。针对传统资源 搜索方法的不足以及日益增加的客户端资源，近年来人们提出基于 Peer-to-Peer（P2P）模式实现资源搜索。 与基于 C/S 模式的资源搜索方法相比，在基于 P2P 的资源搜索方法中各节点在逻辑上是对等的，每个节点 都可能成为其他节点的服务器，如图 1(b)所示，资源所有者把资源（或资源信息）发布到某（些）节点， 资源请求节点到相应节点查找所需资源。 根据系统中各节点的逻辑拓扑关系，采用 P2P 资源搜索技术的系统可以分为非结构化（Unstructured） P2P 系统和结构化（Structured）P2P 系统两大类[4]。在非结构化 P2P 系统中，节点间的逻辑拓扑关系通常 较为松散，具有较大的随意性，资源（或资源信息）的放置通常也与系统的拓扑结构无关。在结构化 P2P 系统中，节点间的逻辑拓扑关系通常由确定性的算法严格控制，资源（或资源信息）的放置也是由确定性 的算法发布到特定的节点上。由于采用结构化 P2P 系统通常基于分布式哈希表（Distributed Hash Table， DHT）进行构建，因此也称为 DHT 系统[6]。与非结构化 P2P 系统相比，DHT 系统具有可扩展性好、延迟 低、可靠性高等优点[7]。自从 21 世纪以来，随着 Internet 技术的飞速发展和互联网资源的日益增加，基于 DHT 的资源搜索技术（简称为 DHT 资源搜索技术）成为学术界的一个新兴的研究领域，受到越来越多的 研究者的关注，并且大量的研究成果发表在相关的高级别会议和期刊上。在该领域中存在着许多的研究问 题，有些问题已经得到了较深入的研究，而有些问题则处在研究的初步阶段。 Supported by the National Basic Research Program of China (973) under Grant No. 2005CB321801 (973 重点基础研究发展 计划基金); the National Natural Science Foundation of China under Grant No. 60673167, 60703072 (自然科学基金). 联系人: 张一鸣. Phone: 13973126047. E-mail: sdiris@gmail.com. 资源搜索通常可分为资源发布和资源查找两个阶段。假设在一个 DHT 系统中，节点 A 具有资源 X 并 想共享给其他节点，节点 B 需要查找资源 X，典型的资源发布和查找过程如图 2 所示。 图 2 资源发布和查找过程示例 （1）节点 A 首先通过某种哈希算法把资源 X 映射到 key 空间，即 K = Hash(X)，然后通过 DHT 层发 出一个目标为K 的消息，DHT 层把该消息路由至系统中负责K 的唯一节点（假设为节点 C）。 （2）节点 C 把自己的 IP 地址返回给节点 A。 （3）节点 A 进而把资源 X（或 X 的资源信息）发布到节点 C。 （4）与上面的资源发布过程类似，节点 B 通过哈希算法得到资源 X 的 key：K = Hash(X)，然后通过 DHT 层发出一个目标为 K 的消息，DHT 层把该消息路由至系统中负责 K 的唯一节点 C。 （5）节点 C 把资源 X（或 X 的资源信息）返回给节点 B。 针对上述资源搜索过程，可以把 DHT 资源搜索技术分为拓扑路由层和复杂查询层，如图 3 所示。 图 3 拓扑路由层和复杂查询层 （1）拓扑路由层：拓扑路由层通常基于某种静态拓扑图，为上层提供基本的拓扑维护和消息路由等 功能。拓扑维护是指在节点动态加入退出的情况下，采用分布式算法维护各节点的路由表，进而实现对系 统全局拓扑的动态维护。消息路由是指各中间节点根据消息的 key 和特定路由算法将其转发给下一跳邻居 节点，从而保证消息最终将路由至系统中负责该 key 的唯一节点。通常拓扑维护和消息路由是紧密相关的， 因此本文把它们作为一个整体进行介绍。 （2）复杂查询层：复杂查询层位于上层应用与拓扑路由层之间，其作用是基于拓扑路由层提供的基 本 DHT 功能，为上层应用提供各种复杂查询的支持，如区间查询、聚合查询、分组查询等。  区间查询是指查找属性值处于某一连续区间（或空间）内的资源。例如在网格信息服务中，搜索 符合条件“256M ≤ Memory ≤ 2G”的计算节点。  聚合查询是指对一组节点某属性聚合信息的查询，例如查询一组节点的 CPU 总数 （SUM(numCPUs)）、或一组节点的平均共享文件数（AVERAGE(numFiles)）等。  分组查询是指基于某种属性（如所属管理域或节点间延迟等）把节点分为多个组，进而使查询满 足某种与分组相关的要求。例如，如果节点按照节点间延迟进行分组，则可以限制查询仅在组内 进行，从而提高了系统性能。 除了资源搜索功能，一个典型的 DHT 系统还应包括适配下层网络、负载均衡和安全等功能[8]。适配 下层网络是指在构建 DHT 系统的时候考虑下层 IP 网络的延迟、抖动等情况，以获得更好的搜索性能；负 载均衡是指针对搜索请求分布不均匀、资源对象分布不均匀、以及各节点负责的名字空间大小分布不均匀 等问题，尽量使负载均衡地分布到各节点及节点间连接；而安全问题存在于 DHT 系统的各部分，主要包 括数据窃取、拒绝服务（DoS）攻击、身份欺骗、发布虚假资源等。在上述功能中，资源搜索是 DHT 系统 的核心组成部分，与其他功能相对独立[9]。本文将重点介绍DHT 资源搜索技术的最新研究成果。 2 拓扑构建与消息路由 本节首先概述在 DHT 系统中常见的几种静态拓扑图，然后介绍基于这些静态拓扑图进行构建的典型 DHT 系统的拓扑路由功能。 2.1 静态拓扑图 DHT 系统通常基于某种静态拓扑图进行构建。常见的静态拓扑图包括环、多维花环、立方体、Plaxton 图、蝶网、跳表、de Bruijn 图、Kautz 图等。 环是最简单的静态拓扑图。连续编号的 N 个节点 0, 1, … , N−1 由单向边（directed edges）连接构成线 性阵列，增加一条从节点 N−1 到节点 0 的连接即构成环。 通过将环推广到更高的维数，将得到多维花环（d-torus）[13]。一个 d 维 k 元花环由 N = kd 个节点组成， 每个节点由它的 d 元坐标向量来标识，如图 4(a)所示。d 维 2 元花环是一类非常重要的拓扑图，通常被称 为 d 维立方体[13]，如图 4(b)所示。通过把 d 维立方体各个顶点替换成含 d 个节点的环，将得到 d 维立方 体连接环（Cube-Connected-Cycle，CCC）[14]，如图 4(c)所示，CCC 拓扑可以看作立方体的变异（variation）。 a) 2 维 4 元花环 b) 3 维立方体 c) 3 维立方体连接环 CCC 图 4 花环、立方体和立方体连接环（Cube-Connected-Cycle） 在 Plaxton 图[16]中，每个节点的标识都是一个长度固定的 n 进制位串，可以通过 SHA-1 算法获得。 节点间根据标识后缀匹配（或前缀匹配）的方式进行连接：每个节点都是一个 Plaxton 树的根，树的第 i 层是所有最后 n −i 位标识与根节点相同的节点。图 5 是一个 Plaxton 图的例子。 B4F8 9098 7598 87CA 4598 1598 3E98 D598 0325 2BB8 图 5 Plaxton 图 图 6 (2,2)-蝶网 一个(k,r)-蝶网[24]包含 kn kr 个节点，其中 k 和 r 分别被称为蝶网的直径和基。节点标识的形式为 0 1 1( ... ; )kx x x i ，其中 i 表示节点所处的层数，0 1i k ， 0 1 10 , ,... 1kx x x r  。 1i k 时，节点 0 1 1( ... ; )kx x x i 到所有形如 0 1 2 1( ... ... ; 1)i i kx x x yx x i   的节点有一条边； 1i k 时，节点 0 1 1( ... ; )kx x x i 到所有形如 1 1( ... ;0)kyx x  的节点有一条边。图 6 是一个(2,2)-蝶网的示例。 跳表（skip list）[26]是一个有向链表结构，如图 7 所示，假设 2hi j  （j 为奇数），那么第 i 个节点 的高度为 h，有 h+1 个长链，其中第 k（0 ≤ k ≤ h）个长链指向自己后面第 2h 个节点。 图 7 跳表 de Bruijn 图 ( , )B d D [28]是一个有向图，其中每个节点的标识都是基为 d, 长度为 D的字符串。 ( , )B d D 中每个节点 1 2 Du u u u  都有 d 条出边：对任意 {0,1,2, , 1}d  ，u 有一条到 2 3 ... Dv u u u  的出边。图 8 给出了两个 Kautz 图示例 (2,1)B 和 (2,2)B 。 图 8 de Bruijn图 B(2,2)和 B(2,3) 图 9 Kautz 图K(2,1)和 K(2,2) Kautz 图 ( , )K d D [33]是一个有向图。对字符串 1 2 ... Da a a ，若 {0,1,2, , }ia d  ( 1 i D )且 1i ia a  (1 1i D  )，则称是基为 d、长度为 D 的 Kautz 串。Kautz 空间 ( , )KautzSpace d D 是指所有基 为 d、长度为 D 的 Kautz 串的集合。Kautz 图中每个节点的标识都是 Kautz 空间 ( , )KautzSpace d D 中的一个 Kautz 串。 ( , )K d D 中每个节点 1 2 Du u u u  都有 d 条出边：对任意 {0,1,2, , }d  且 Du ，u 有一条到 2 3 ... Dv u u u  的出边。图 9 给出了两个 Kautz 图示例 (2,1)K 和 (2,2)K 。 2.2 典型 DHT 系统 在 DHT 系统中，每个节点具有一个全局唯一的节点标识（nodeID），所有节点根据节点标识形成一个 构建于 Internet 之上的自组织的层叠网。为了实现消息路由，每个节点都维护了一个路由表，其中包含了 一些其他节点的层叠网标识和路由信息（即 IP 地址）。在消息的路由过程中，中间节点基于消息的 key 选 择邻居节点进行转发。DHT 系统性能评价的重要参数有节点度数、路由延迟和动态维护开销等[9]。节点 度数是指 DHT 中各节点的直接邻居数量，在有向图（directed graphs 或 digraphs）中通常为出度（出边邻 居数量）和入度（入边邻居数量）的和。路由延迟是指一次搜索在 P2P 系统中经过的逻辑跳步（hop）数。 动态维护开销是指节点加入或退出时为维护系统拓扑的一致性而产生的维护消息数量。 下面将对典型 DHT 系统的拓扑构建、消息路由以及性能参数进行概述。 Chord [10]．Chord 采用环作为其静态拓扑图，系统中每个节点和关键字的标识都是一个 m=160 位的 二进制串（即 0 到 2m−1 之间的整数），可以分别根据节点的 IP 地址或关键字名称通过 SHA-1 算法[11]获得。 所有节点根据标识符的大小顺时针构成一个环形的拓扑结构，如图 10 所示。与静态环相比，Chord 环上的 节点可能是不连续的。给定关键字Key，Chord 首先对其进行哈希，设 Hash(Key)=X，Chord 将通过一致性 哈希（consistent hashing）算法[12]，将 Key 发布到 X 在环上的后继节点（环中沿顺时针方向最近的节点） 上。环拓扑中每个节点都维护了其后继节点的路由信息，在环上沿后继节点总可以正确地到达任何目标节 点，但这种方法效率很低。因此 Chord 中每个节点都维护一个 finger 表（即路由表），finger 表至多有m 项， 节点 n 的 finger 表第 i 项是值 n+2i−1 在 Chord 环上的后继节点。资源搜索时，每个节点都通过查询 finger 表，将搜索请求转发到离 key 最近的节点上。图 10(a)给出了节点 8 的 finger 表。设 Hash(Key)=54，图 10(b) 给出了从节点 8 开始，对 Key 的搜索过程（消息最终停止于节点 56）。Chord 的节点度数为 O(log2N)，路 由延迟是 O(log2N)，平均路由延迟为 1/2log2N, 动态维护开销为 O(log22N)。 a)节点 N8 的 finger 表 b) K54 的搜索过程 图 10 Chord 的拓扑和路由 6 2 3 1 5 4 . (x, y) a)二维坐标空间中 CAN 节点 b)从节点 1 到目标点(x, y)的路由 图 11 CAN 的拓扑和路由 CAN [15]．CAN（Content Addressable Network）采用多维花环作为其静态拓扑结构。CAN 的基本思 想是构造一个虚拟的 d 维笛卡尔坐标空间，系统中的各个节点分别负责虚拟 d 维坐标空间中的一块区域， 所有节点负责整个 d 维坐标空间。每个资源对象映射到 d 维区域中的某一点，并发布到负责该区域的节点 上。CAN 中的节点根据它们负责的区域在坐标空间中的位置来建立邻居关系，负责相邻区域的节点互为邻 居。由于坐标空间是 d 维的，故每个节点有 2d 个邻居。如图 11(a)所示的 CAN 系统采取了 2 维的笛卡儿 坐标空间，整个虚拟坐标空间全部由系统中的 5 个节点负责，每个节点负责坐标空间中的部分区域。每个 资源对象有一个关键字，通过哈希函数对关键字进行哈希，进而将资源对象映射到 d 维空间中一点，资源 对象就发布到负责该点的节点上。消息路由时，每个节点根据目标节点的坐标位置，将路由消息转发给离 目标最近的邻居。例如图 11(b)给出了节点 1 到目标点(x, y)的路由过程。当节点加入或退出时，相关节点 负责的区间会进行拆分或合并。新节点加入时，首先通过哈希函数将新节点映射到虚拟空间中的一点，然 后将该点所在区域沿某一维拆分成两半，一半区域由新节点负责。CAN 使用后台的区域重分配方式来实现 负载平衡。CAN 的节点度数为 2d，平均路由延迟为 1/4dN1/ d，动态维护开销为 O(logdN)。 Cycloid [14]．由于 d 维立方体结构难于扩展，Cycloid 采用 CCC 结构作为静态拓扑。如图 4(c)所示， CCC 结构可以看作是顶点被环所代替的立方体结构。在 Cycloid 中每个节点以一个环上标号和一个立方体 标号共同标识。立方体标号相同的所有节点排列成一个小环，而所有小环又排序成一个大环。每一个节点 通过一个路由表和叶节点集来维持与系统其它节点的连接。路由表中包括一个立方体邻居和两个大环上邻 居。两个内部叶节点分别指向本地小环上紧邻的前驱节点和后继节点，它们与本节点有相同的立方体标号； 两个外部叶节点分别指向前驱环和后继环中具有最大环标号的节点。Cycloid 模拟 CCC 的路由算法，采用 逐位匹配（bit-correcting）的方式进行路由。节点加入时选择一个小环加入并调整相关节点的路由表，节 点退出与之类似。Cycloid的节点度数为 7，路由延迟是 O(logN)，动态维护开销为 O(logN)。 Tapestry [17]．Tapestry 基于 Plaxton图进行构建。针对 Plaxton图构建需要全局信息的问题，在 Tapestry 中各节点只需维护邻居节点信息。Tapestry 中节点和资源对象的标识都是 160 位的二进制值，使用基底为 b 的位串表示（如 b=16 时即是 16 进制位串）。Tapestry 中每个节点维护一个多层的路由表，路由表的层数 等于节点标识的长度，路由表中第 j 层节点标识的后 j−1 位与本节点标识的后 j−1 位相同；第 j 层共有 b 项， 第 i 项的第 j 位对应的标识为 i；如果系统中有多个节点标识满足路由表中某一项的条件，则选择延迟最小 的节点。图 12 给出了 Tapestry 中某节点路由表的示例（其中 b=8，节点标识长度为 4）。Tapestry 中每个资 源对象都根据其标识 ObjectID，发布到标识与 ObjectID 匹配最多位数的节点上。Tapestry 采用了 Plaxton 的基于后缀的消息路由方式：根据目标节点的标识进行路由，每经过一个中间节点，标识的匹配位数要增 加一位。例如在图5中，从节点0325 路由消息到目标节点4598，经过的中间节点为***8->**98->*598->4598。 Tapestry的节点度数为O(blogbN)，路由延迟和路由消息开销是O(logbN)，动态维护开销为 O(blogbN)。Tapestry 的后续版本 Chimera [18]采用了前缀匹配的方式进行拓扑构建和路由，但是其本质是相同的。 0642 x042 xx02 xxx0 1642 x142 xx12 xxx1 2642 x242 xx22 xxx2 3642 x342 xx32 xxx3 4642 x442 xx42 xxx4 5642 x542 xx52 xxx5 6642 x642 xx62 xxx6 7642 x742 xx72 xxx7 路由表的层数 1234 图 12 Tapestry 中节点 0642 的路由表 图 13 多层 SkipNet结构 Pastry [19]．Pastry 与 Tapestry 类似，也是基于 Plaxton 图进行构建。Pastry 采用了基于前缀匹配的方 式进行拓扑构建和路由。节点的路由状态表包括三个部分：路由表、邻居集、叶集，其中路由表与 Tapestry 路由表相似，而邻居集和叶集则是为了提高消息路由效率和实现与物理网络的拓扑匹配。邻居集中包含了 与本节点物理延迟最低的 M个节点，叶集中是与本节点标识逻辑距离最近的 L 个节点。与 Tapestry 类似， Pastry 的节点度数为 O(blogbN)，路由延迟和路由消息开销是 O(logbN)，动态维护开销为 O(b logbN)。在后 续研究中人们提出了 Pastry 的各种改进版本，如 MSPastry [20]、Bamboo [21]、OpenDHT [22]等。 Kademlia [23]．Kademlia 的与 Pastry 非常类似，但 Kademlia 中两个标识的距离值是用两者的异 或（XOR）值而不是它们的差值来衡量的；这样任意两节点间具有对称的距离。Kademlia 也提供了在多个 节点中选择邻居的能力，从而具有较好的容错性和自适应性。Kademlia 的性能特征与 Pastry 相似。 Ulysses [24]．Ulysses 基于蝶网进行构建。Ulysses 中节点标识的名字空间是 k 级平行的 k 维空间，每 个节点负责名字空间中的一块区域。节点加入时首先随机加入到某一级 k 维空间中，并拆分该空间中的区 域。Ulysses 节点间按照近似的 Butterfly 拓扑建立邻居关系，并扩展了 Butterfly 拓扑以取得更好的负载均 衡。在大概率情况下，Ulysses 的节点度数为 O(logN)，路由延迟及路由消息开销为 (log / log log )O N N 。 Viceroy [25]．Viceroy 也是基于蝶网的 DHT。Viceroy 首先将系统中所有节点组织成一个环，然后将节 点组织成多层。每个节点处于某一层中，同一层节点组织成双向链表，同时每个节点有 2 条到下一层中两 个随机选取节点的长链，1 条到上一层节点的连接。Viceroy中的消息路由可分为三个阶段：第一阶段是向 上路由到达某一上层中的节点；第二阶段是按照蝶网的路由方式到达目标节点所在的层；最后是在同一层 中按照双向链表的前后继进行路由。Viceroy 方法的设计和动态维护较为复杂，节点出度为 7，入度可能达 到 O(logN)，在大概率情况下路由延迟为 O(logN)，但在某些情况下可能会达到O(log2N)。 SkipNet [27]．SkipNet 基于跳表结构。SkipNet 采用了双重地址空间：名字（name）空间和数字 ID 空 间。节点名称和资源名称直接映射到名字空间，而它们的哈希值则映射到数字 ID 空间。如图 13 所示，所 有节点按照其名称的字典序排序，然后组织成类似于跳表的多层双向链表结构，总共约有 O(log2N)层，第 i 层有 2i 个环，其标识依次为 0,1,… , 2i−1。每个节点在第 i 层应加入以节点数字 ID 标识前 i 位字符串为标 识的环，例如，设 Hash(X) = 011，则 X 应依次加入第 0 层的根环，第 1 层的 0 环，第 2 层的 01 环，以及 第 3 层的 011 环。一个节点在加入的每个环中选择字典序最近的两个节点作为邻居。在消息路由过程中， 首先在第 0 层的根环寻找第一个数字 ID 标识与目标字符串前 1 位匹配的节点，然后在第 1 层的环寻找第 一个数字 ID 标识与目标字符串前 2 位匹配的节点，以此类推，直到到达一个与目标字符串距离最近的节 点为止，该节点即为消息的负责节点。SkipNet的节点度数、平均搜索延迟和动态维护开销均为 O(logN)。 Koorde [29]．Koorde 是第一个基于 de Bruijn 图的 DHT。此后，人们陆续提出了 D2B [30]、ODRI [31]、 Broose[32]等其他基于 de Bruijn 图的 DHT。Koorde 继承了 Chord 中的动态维护等机制，但 Koorde 的节点 邻居关系模拟了 de Bruijn 图。为了在一个节点稀疏分布（sparsely populated）的 Chord 环中嵌入 de Bruijn 图结构，Koorde 使用前继节点（predecessor）来模拟实际不存在的节点。节点 m的路由表中包括 2 个邻居： m的后继节点（successor），以及 2m的前继节点。Koorde 的消息路由是沿 Chord 环模拟 de Bruijn 图拓扑 进行的，可以证明，de Bruijn 图中的 1 跳步对应最多实际 Chord 环中的 3 跳步。Koorde 的节点度数为 2， 平均路由延迟为 O(logN)；扩展后其节点度数为O(logN)，平均路由延迟则减小为 O(logN / loglogN)。 D2B [30]．D2B 也是基于 de Bruijn 图拓扑，但其设计与Koorde 完全不同。D2B 中节点的标识是动态 产生，每个节点根据其标识建立近似的 de Bruijn 图拓扑。D2B 中消息路由算法也是模仿 de Bruijn 图中的 短路径路由进行。D2B 节点度数的期望值是常量，但各个节点的节点度数差异很大。在大概率情况下，D2B 的节点度数不超过 O(logN)，路由延迟为 O(logN)。 FissionE [34]．FissionE 是第一个基于 Kautz 图的 DHT。此后，人们陆续提出了 SKY [35]、Moore[36]、 Bake[37]等其他基于 Kautz 图的 DHT。FissionE 使用 Kautz 图 K(2, D)作为静态拓扑，每个节点的标识都是 一个基为 2 的 Kautz 串。对 FissionE 中的任一节点 1 2 Du u u u  ，其出边邻居为所有标识为 2 3 1D mv u u u q q   （0 ≤ m ≤ 2）的节点，如图 14 所示。当有新节点加入时，FissionE 首先寻找一个具有局部最短标识的节点， 然后把该节点拆分为两个节点并分别具有更长一位的标识。FissionE 中的路由过程与 Kautz 图中的路由过 程基本相同, 图 14 给出了从节点 012 到节点 102 的路由过程。FissionE 使用 Kautz_hash 命名算法为每个资 源生成 100 位的 Kautz 串作为其标识，资源被发布到节点标识为其标识前缀的唯一节点上。FissionE 的入 度为 2, 平均出度为 2，路由延迟不超过 2log2N，动态维护开销不超过 3log2N。 SKY [35]．FissionE 只能支持以 2 为基的 Kautz 图。为了支持以任意正整数(>1)为基的 Kautz 图，SKY 采用线图技术的边点变换思想[78]实现动态拓扑维护维护。如图 15 所示，在一个基于Kautz 图 K(3,2)的 SKY 系统中，当有新节点加入时，SKY 首先寻找一个具有局部最短标识的节点（例如节点 10），然后通过边点 变换（[01,10]变为 010，[21,10]变为 210，[31,10]变为 310）得到 3 个新节点，最后通过合并（010 和 210 合并为一个节点 010），使得 010 对应原节点 10，而 310 对应新节点。SKY 的路由算法和命名算法与 FissionE 类似。SKY 的节点度数为O(d)，路由延迟和动态维护开销不超过 O(logdN)。 012 101 121 21 010 021102 201 020 120 2021 2020 a) 0 (3, 2)G K . b) Topology after mergence. 图 14 FissionE 拓扑与路由 图 15 SKY 拓扑维护 有些 DHT 没有特定的静态拓扑图，而是通过把节点组织成多个组来实现动态维护和消息路由，如 Kelips [38]、OneHop [39]和 Accordion [40]等。 Kelips [38]．在 Kelips 中节点和资源的命名算法与 Chord 相同。Kelips 将 P2P 系统中节点分成 k 个组， 每个节点通过哈希函数分配到某一个组中。各资源对象也通过哈希函数发布到某一个组中，以使得各组中 的节点和资源对象分布均匀。各节点维护的路由表包括：(i) 同组中所有节点的视图；(ii) 其它各组中常量 个数节点的信息；(iii) 同一组节点上的全部资源对象的索引信息。Kelips 把搜索请求转发到相应的组中， 更新消息通过 gossip 来传播。Kelips 的路由延迟为 O(1)，但节点度数和维护开销为 O(N1/2)。 OneHop [39]．OneHop 的节点和资源命名算法与 Chord 相同。OneHop 把 ID 空间分成多个部分（slice）， 每个部分又被进一步分成多个单元（unit），每一个部分和单元都有一个头节点（leader）。节点的动态加入 退出通过部分和单元的头节点分发到系统中的所有节点。当一个节点加入时将通知其所在部分的头节点， 该头节点对一个周期内所有加入事件进行汇总后分发给所有部分的头节点，进而分发给所有单元的头节 点。单元头节点进而采用捎带（piggyback）的方式把信息分发到单元内所有节点。OneHop 的节点度数和 维护开销为 O(N)，路由延迟为 O(1)。 Accordion [40]．通常 DHT 的节点度数是预先设定的，节点度数越高，搜索延迟越小，但维护开销越 大。针对该问题，Accordion 提出动态调整节点度数以获得最优性能。在 Accordion 中允许上层应用指定一 个带宽预算（bandwidth budget），该预算和当前查询所占用带宽的差值即为可用于动态拓扑维护的带宽。 Accordion 基于小世界（small world）原理[41]，使用 1/x 分布来选择邻居节点：节点 A 选择与其距离为 x 的节点 B 作为邻居的概率为 1/x。Accordion 基于 Pareto 分布预测邻居节点失效，采用并行搜索和查询时获 得新邻居（learning from lookups）等技术得到给定带宽预算下的最优搜索性能：在节点度数为 O(logN)时 平均搜索延迟为 O(logN)，与 Chord 类似；在节点度数为 O(N)时平均搜索延迟为 O(1)，与 OneHop 类似。 3 复杂查询 DHT 的基本路由功能提供了精确匹配的资源查询能力：给定资源对象的关键字，能够确保在一定的延 迟内精确搜索到资源对象所在的节点。然而，随着 DHT 的广泛应用，很多应用都要求 DHT 能够提供更复 杂的查询能力，如区间查询、聚合查询和分组查询等。，本节将对常见的 DHT 复杂查询技术进行概述。 3.1 区间查询 目前关于 DHT 区间查询的研究可以分为两类[42]：有些研究基于现有 DHT 的拓扑路由层提供的功能 实现区间查询，通常称为分层（layered）区间查询技术；另一些研究则为实现区间查询设计了专门的拓扑 路由层，通常称为定制（customized）区间查询技术。 （1）分层区间查询技术 分层区间查询技术基于现有DHT实现区间查询，无需改变下层的拓扑路由设计。 Gupta 等人[43]基于 Chord 方法提出了概率性的单属性区间查询技术。这种技术通过位置敏感的哈希算 法（Locality Sensitive Hashing，LSH）[44]来获得属性值区间的标识，并根据 Chord 方法发布到节点上。 LSH 算法使得相似的区间能够在较大的概率下映射到 Chord 中相同或相近的节点上，但这种技术返回的搜 索结果只能在一定概率下符合搜索条件，不能确定性地返回满足搜索条件的所有资源对象。 Squid [45]基于 Chord 方法提供了多属性区间查询能力。Squid 采用 Hilbert 空间填充曲线（space-filling curve，SFC）[46]技术，将资源对象的多个属性值映射到一维数据环上的一点，然后通过 Chord 方法进行 资源发布。区间查询时 Squid 技术利用 SFC 的层次递归特性将搜索树嵌入到 Chord 中，但搜索树中的每一 步搜索都会引起 Chord 中的一次 DHT 路由，因此 Squid 中区间查询的延迟和消息开销较大。 Andrzejak 等人[47]基于 CAN 提出一种单属性区间查询方法。与 Squid 类似，此方法也采用 Hilbert SFC [46]技术，将一维属性值通过 SFC 技术反向映射到 CAN 中 d 维空间的一个区域。区间查询[l, u]时，首先 将搜索请求通过 CAN 路由发送到负责属性值(l+u)/2 的节点，然后从该节点开始向其周围与搜索相关的节 点进行有限的泛洪广播。Andrzejak 等人在研究中提出了三种泛洪策略：brute force 策略、受控泛洪和直接 受控泛洪（Directed Controlled Flooding, DCF），其中 DCF 策略具有较好的总体特性。但这种方法的区间查 询延迟随着搜索区间的增大而增加，并且只支持单属性搜索。 由于 SkipNet [27]采用了双重地址空间，并把节点名称和资源名称（例如 TopMusic.mp3）直接映射到 名字空间，因此可以通过在名字空间中按顺序搜索链表中的节点来支持单属性区间查询。SCRAP [48]基于 SkipNet 通过 Hilbert SFC 技术提供了多属性区间查询能力，其区间查询延迟为 O(logN+n)。 Armada [42]基于 FissionE [34]实现了多属性区间查询功能。Armada 通过基于多值分区树的维序命名算 法，使得属性值连续的资源对象能够获得相近的标识，从而发布到相同或相关的节点上。Armada 基于前 向路由树使得区间搜索过程与底层 FissionE 拓扑相匹配，并基于历史信息使得在属性值空间中分布不均匀 的资源对象尽量均衡地发布到各个节点上。无论搜索区间的大小或属性值个数的多少，Armada 都能确保 在一定的延迟内返回所有搜索结果。Armada 的平均搜索延迟小于 log2N（N 为系统中节点数目），最大搜 索延迟小于 2log2N，多属性区间搜索的平均消息开销分别约为和 log2N＋4n−4（n 为返回搜索结果的节点数 目）。然而，由于 Armada 基于历史信息对资源对象分布进行预测并构建前项路由树，其负载平衡性能较差。 PHT 方法[49]是可基于任意 DHT（包括常量度数 DHT）的通用区间查询技术。PHT 方法构建了一个 与底层 DHT 架构无关的前缀哈希树（Prefix Hash Tree）。前缀哈希树的结构与二叉树[52]非常相似，树中 的各节点存储了各个资源对象的 key（PHT 方法中假设资源对象都可用二进制串作为 key）。每个节点最多 存储 B 个 key，一旦树中某个节点存储的 key 的数目已超过阈值 B，则将该节点分裂成两个子节点。区间查 询时，首先通过 z-curve [50]将多维搜索空间转换成二进制串的集合，然后在前缀哈希树中进行由根向下的 搜索。然而，PHT 方法中前缀哈希树的高度与属性值的个数有关，同时前缀哈希树中搜索的每一步都需要 调用一次底层的 DHT 路由，区间查询延迟和消息开销都相当大，并且搜索延迟会随着整个搜索空间以及 具体搜索区间的增大而增加。 （2）定制区间查询技术 定制区间查询技术通常设计专门的 DHT 拓扑维护和路由算法，在分布的节点上实现分布式索引结构， 进而实现 DHT区间查询。 P-tree [51]方法在多个分布的节点之间建立类似于 B+-树[52]的 DHT 拓扑结构，每个节点维护分布式 B+-tree 索引树的一部分。P-tree 方法提供了单属性区间查询能力，平均节点度数为 O(dlogdN)，平均区间查 询延迟为 O(logdN)。RAQ 方法[53]中每个节点都是搜索空间中的一点，在搜索空间中建立类似传统数据库 中 R-tree [54]的索引树，通过索引树来组织 DHT 拓扑。索引树的每个叶节点都是 P2P 系统中的一个节点， 各节点维护了到索引树中所有其它子树的连接关系。 Mercury [55]、SWORD [56]和 MAAN [57]都采取了为每种属性维护一个 P2P 网络的方法来支持多属性 区间查询。Mercury 方法为每种属性建立一个环型的虚拟 hub，同一个 hub 中的全部节点形成一个环形的 P2P 网络。每个节点属于其中的某一个虚拟 hub，负责此虚拟 hub 中一段连续的属性值。Mercury 方法通过 动态随机采样节点负载，“邀请”轻负载节点加入到负载较大的虚拟 hub 中，以促进系统的负载均衡。 Mercury 方法有着较好的动态负载均衡特性，其节点度数为 O(k)（k 为常数），区间查询延迟为 O(1/klog2N+n) （n 为返回搜索结果的节点数目）。SWORD 在 PlanetLab [92]中提供多属性区间查询的信 息服务，每个节点参与多个 DHT 网络，每个 DHT 网络负责一个属性。MAAN 为每种属性在系统中构建 一个基于 Chord 方法的 P2P 网络。但 Mercury、SWORD 和 MAAN 中的多属性区间查询是通过单属性区 间查询来完成的，同一个资源对象需要在负责每个属性的 P2P 网络中都发布一次，搜索时只能依据某一个 属性值的搜索条件进行，不能同时利用搜索请求中对多个属性的限制条件。 由于在定制区间查询技术中，DHT 的拓扑构造和消息路由等通常都是为某种区间查询需求而专门设计 的，与具体的区间查询需求以及搜索空间中属性值的分布等都存在较紧密的相关性，因此其通用性较差， 难以同时支持其他复杂查询功能。 3.2 聚合查询 聚合查询是指对一组节点某（些）属性聚合信息（如 Count、Sum、Max、Average 和 Median 等）的 查询，在系统管理、数据共享和缓存、DNS 解析和组播树构建等应用中有重要作用[58]。 DASIS（distributed approximative system information service）[59]基于 Kademlia [23]实现了信息聚合。 在 DASIS 中，节点 b1b2… bk 负责所有标识为 b1b2… bk−1 的节点的信息聚合，然后把聚合信息发送给节点 b1b2… bkbk+1。DASIS 支持给定标识前缀对节点个数的查询，根据节点在标识空间的分布情况来选择新加入 节点的标识，进而获得较好的负载平衡特性。 CONE [60]主要研究了基于 Chord 实现 Max聚合的方法。假设节点标识为m 位字符串，则 CONE 维 护了一个 m+1 层的树，第 i 层（i = 1,2,… ,m）有 2i个点，标识为 a1a2… ai（aj = 0,1，0 ≤ j ≤ i）。第 0 层只有 一个点，标识为空。每个点维护树中同层的与其标识互补（例如标识 000 的互补标识为 001）的点的 IP 地 址（注意不是 DHT 逻辑地址），从而确定两点所代表的子树的 Max值，并聚合到上层以其标识为前缀的点。 这样，在第 0 层的根节点将得到全局的 Max 值。在 CONE 中 Max 聚合的平均查询延迟为 O(logN)，每次 查询最多产生O(m)个消息。 SOMO（Self-Organized Metadata Overlay）[61]可以基于任意 DHT 模拟各种数据结构（如链表、二进 制树、队列等）。其基本思想是：如果在某数据结构中对象 a 有一个指向对象 b 的指针，那么在 SOMO 中 对象 a 将对象 b 的 key 以及在 DHT 中负责对象 b 的节点 IP 地址。SOMO 进而基于树结构实现了信息 的聚合与分发。令树的分枝因子为 k，则信息聚合与分发的延迟都为 O(logkN)，树的维护开销为 O(logkN)。 Willow [62]基于 Kademlia [23]提供了 DHT 聚合查询功能。Willow 中的节点标识为 128 位。与 CONE 类似，Willow 维护了一个 129 层的树，树中节点的子树称为域。Willow 基于 Plaxton 路由[16]的层次特性 对域内节点进行聚合。Willow 通过 SQL 语句指定聚合查询，例如“SELECT MAX(maxload) AS maxload” 将通过树聚合所有节点的最大负载信息并记录在 maxload 变量中。Willow 提供了一种 zippering 机制，能 在 O(logN)时间内修复分区（disjoint）或损坏（broken）的树。 SDIMS [63]基于 Pastry [19]实现了 DHT 聚合查询功能。在 SDIMS 中，每个节点的本地属性信息以元 组(属性类型, 属性名称, 属性值)的形式保存，例如(configuration, numCPUs, 16)，或 (file stored, foo, myIPAddress)等。每个属性类型关联一种聚合函数。每个(属性类型, 属性名)对应一个聚合树，以 k = hash(属 性类型, 属性名)为根，按照 Pastry 的路由层次进行组织。针对不同属性的读写频率不同的情况，SDIMS 允许上层应用指定属性的更新策略，包括 Update-Local（只更新本地信息），Update-Up（沿聚合树更新至 根节点），以及 Update-All（更新所有节点），并且设计了相应的查询策略。由于在聚合层的重配置开销过 高，SDIMS 允许上层应用对重配置的频率进行设置。 由于规模巨大、动态性强等特点，DHT 系统通常仅支持所谓的尽力（best-effort）查询。文献[64]研究 了 DHT 聚合查询结果有效性的验证方法，通过一种称为单点验证（single site validity）的正确性条件，来 验证从一个单点失效概率较高的大规模网络返回的聚合结果。文献[65]提出，大多数 DHT 所采用的缓慢聚 合（lazy aggregate）是弱一致（weakly consistent）的，因此应用程序需要平衡一致性和性能或可扩展性的 矛盾，并能够管理聚合结果的时效性（timeliness or staleness）。 3.3 分组查询 关于分组查询的研究可以分为两类[66]：早期的研究通常基于某种特定属性（如所属管理域或节点间 延迟等）把节点分为多个组，近期一些研究则提出支持任意组的创建和查询。下面将分别进行介绍。 （1）管理域查询 传统 DHT是一种扁平（flat）的结构，而 DHT 下层的 IP 网络则是典型的层次化（hierarchical）结构， 并通过分级的管理域（administrative domain）进行组织。近年来研究者们提出在 DHT 中模拟分级域结构， 按照管理域层次进行所谓的“管理域查询”（domain-aware query）。管理域查询应满足如下两种属性[67]。 路径局部性（Path Locality）：从一个节点到另一个节点的路由应限制于两节点的最小公共域内。例如， 从节点 ymzhang.cs.nudt.edu.cn 到节点 dsli.pdl.nudt.edu.cn 的路由应在域 nudt.edu.cn 范围内，而从节点 ymzhang.cs.nudt.edu.cn 到节点 manager.sina.com.cn 的路由则应在域 cn 范围内。 路径收敛性（Path Convergence）：同一个域的不同节点到域外某节点的路由应在域内收敛于同一点。 例如，在图 16 左图中从域 dep1 到节点 110XX 的路由不满足路径收敛性，而在图 16 右图中的路由则满足 路径收敛性（收敛于域 dep1 中的节点 101XX）。 图 16 路径局部性与路径收敛性举例 满足路径局部性和收敛性的管理域查询具有如下优点[67]：  提高性能：由于同一管理域内的节点间通常具有较低的延迟，路径局部性保证路由被限制在可能 的最小域内，从而具有较高的性能。路径收敛性支持应用进行高效的缓存与组播。  可靠和安全：路径局部性保证同一个域内两个节点间的路由不会受到域外失效节点的影响或被域 外节点截获，从而提高了可靠性和安全性。 前文提到的 SkipNet [27]中所有节点按照其名称的字典序排序（如图 13 所示），在每个环中临近的节 点具有相近的字典位置。由于在 SkipNet 的路由过程中，消息从底向上依次在每一层的某个环中传递，从 而任意中间节点的字典位置都在起点和终点之间，进而所有中间节点都在起点和终点的最小公共域内。因 此，SkipNet中的路由满足路径局部性（但是不满足路径收敛性）。 Mislove 等人通过构建多个环在 DHT 中模拟管理域结构[68]。在每个最底层的域中所有节点构成一个 环，并且选择一个节点作为该域的 DHT 层“网关”，以参加更高层域所对应的环。以此类推，每个域都有 一个 DHT 层网关节点，负责在更高层的环中发布该域所对应的环的 ID，并在更高层环中转发域间消息。 由于完全模拟了分级管理域结构，显然在该 DHT 中的消息路由满足路径局部性和路径收敛性。但是，在 这种机制下每个域的 DHT 层网关节点容易成为性能的瓶颈。 Canon [69]基于 Chord [10]实现了管理域结构。在 Canon 中，最底层域内节点的连接关系与 Chord 完全 相同。对不同域，假设域 X1, X2和 Y 满足 X1Y、X2Y、X1X2=Y 以及 X1X2=，那么域 X1 的一个节 点 u 有一条到域X2 的节点 v 的连接当且仅当：(i)节点 v 在域 Y 中是距离 u 至少 2k (0 ≤ k < n)的最近的节点； (ii)节点v比任何域X1 中的其他节点都靠近节点 u。由于路由过程中总是使用逐渐增大的域所对应的环连接， 因此 Canon 中的消息路由满足路径局部性；给定目的消息 K，每个域中距离K 最近的后继节点正是 K 在该 域的收敛点，因此 Canon 中的消息路由满足路径收敛性。Canon 通过 DNS 服务器实现管理域的发现。 ADHT 基于 Pastry 实现了管理域结构[67]。在 ADHT 中，每个节点维护了针对所有节点的、与 Pastry 类似的一个路由表，以及针对该节点所参加的每级管理域的多个叶集合。在路由过程中，ADHT首先检查 在当前最低层域的路由表项中是否存在匹配更多位的节点，如果存在则路由至该节点，否则将路由至最低 层域所对应的叶集合中距离目标最近的节点。与 Canon 类似，ADHT 中的消息路由满足路径局部性和路径 收敛性。但是，由于大部分路由是基于叶节点进行的，因此 ADHT 的路由效率较低。ADHT 使用 DHT 的 put/get 接口实现管理域的发现：所有域 X 的节点把它们的地址 put 到负责 Hash(X)的节点，寻找域 X 的节 点则从负责 Hash(X)的节点 get 任意一个域 X 的节点。 除了上述关于管理域查询的研究，另一种已被广泛研究的分组查询是延迟相关的查询（locality-aware queries）[70~74]。这些研究的核心思想是测量某些节点间的网络延迟，进而把延迟低于某一阈值的节点组 织成一个组，组内连接与正常 DHT 连接相同，组间连接则通过超节点或采用某种分布式方式实现。限于 篇幅，不再赘述。 （2）任意组的创建和查询 上述方法都是在 DHT 中针对特定属性对节点进行分组。Diminished Chord（D-Chord）[75]对管理域的 概念进行扩展，在 Chord [10]的基础上支持任意组（group）的创建。例如，可以在一