现有的P2P实现可以分为三种类型。它们分别是：基于目录服务器P2P，非结构化P2P和结构化P2P。基于目录服务器这一类
系统中设置目录服务器，用于保存用户节点的地址信息和该节点上共享文件的描述信息，文件本身是分散存贮在各个节点上的，实
际的文件传输也是在对等节点之间进行，目录服务器仅仅起到中介作用，为节点提供发布和查询文件索引服务。鉴于集中式目录服
务器不仅可能成为系统的瓶颈，而且还可能引发法律纠纷，因此出现了以Gnutella为代表的非结构化P2P系统，在这种P2P结构
中，文件索引信息不再由集中式的目录服务器存储和管理，而是分散到网络中，由节点自己保存，该类系统采用分布式的索引查找
策略，为了查找网络中的文件，节点要随机地维护网络中的其他一些节点作为邻居，以便通过邻居节点广播查询报文。非结构化
P2P系统中由于不存在目录服务器，所以没有单点瓶颈问题，不存在单一故障点。然而其缺点也是明显的：在网络中广播查询报文
加重了网络通信负担，其查询机制在系统规模扩大时不具有可扩展性。另外，由于查询报文被限制在特定的范围内，所以并不能保
证一定可以找到网络中存在的目的数据。上面介绍的两类P2P系统都缺乏有效的、可扩展的索引查找机制。为此，近年来许多研究
小组在设计可扩展的查找机制方面做了大量的研究工作，提出了Chord、Pastry、CAN和Tapestry等用于构建结构化P2P的分布式
哈希表系统（Distributed Hash Table，DHT）。DHT的主要思想是：首先，每条文件索引被表示成一个(K, V)对，K称为关键字，
可以是文件名（或文件的其他描述信息）的哈希值，V是实际存储文件的节点的IP地址（或节点的其他描述信息）。所有的文件索
引条目(即所有的（K, V）对)组成一张大的文件索引哈希表，只要输入目标文件的K值，就可以从这张表中查出所有存储该文件的节
点地址。然后，再将上面的大文件哈希表分割成很多局部小块，按照特定的规则把这些小块的局部哈希表分布到系统中的所有参与
节点上，使得每个节点负责维护其中的一块。这样，节点查询文件时，只要把查询报文路由到相应的节点即可（该节点维护的哈希
表分块中含有要查找的(K,V)对）。这里面有个很重要的问题，就是节点要按照一定的规则来分割整体的哈希表，进而也就决定了节
点要维护特定的邻居节点，以便路由能顺利进行。这个规则因具体系统的不同而不同，CAN，Chord，Pastry和Tapestry都有自己
的规则，也就呈现出不同的特性。基于分布式哈希表（DHT）的分布式检索和路由算法因为具有查找可确定性、简单性和分布性等
优点，正成为国际上结构化P2P网络研究和应用的热点。自2002年起，美国国家科学基金会（NSF）提供了1200万美元的资金启
动了一个为期5年的研究项目IRIS，该项目集中了MIT和UC Berkeley等5所著名高等院校的强大科研力量，为下一代大规模分布式应
用研制基于DHT的新型基础设施。
系统中设置目录服务器，用于保存用户节点的地址信息和该节点上共享文件的描述信息，文件本身是分散存贮在各个节点上的，实
际的文件传输也是在对等节点之间进行，目录服务器仅仅起到中介作用，为节点提供发布和查询文件索引服务。鉴于集中式目录服
务器不仅可能成为系统的瓶颈，而且还可能引发法律纠纷，因此出现了以Gnutella为代表的非结构化P2P系统，在这种P2P结构
中，文件索引信息不再由集中式的目录服务器存储和管理，而是分散到网络中，由节点自己保存，该类系统采用分布式的索引查找
策略，为了查找网络中的文件，节点要随机地维护网络中的其他一些节点作为邻居，以便通过邻居节点广播查询报文。非结构化
P2P系统中由于不存在目录服务器，所以没有单点瓶颈问题，不存在单一故障点。然而其缺点也是明显的：在网络中广播查询报文
加重了网络通信负担，其查询机制在系统规模扩大时不具有可扩展性。另外，由于查询报文被限制在特定的范围内，所以并不能保
证一定可以找到网络中存在的目的数据。上面介绍的两类P2P系统都缺乏有效的、可扩展的索引查找机制。为此，近年来许多研究
小组在设计可扩展的查找机制方面做了大量的研究工作，提出了Chord、Pastry、CAN和Tapestry等用于构建结构化P2P的分布式
哈希表系统（Distributed Hash Table，DHT）。DHT的主要思想是：首先，每条文件索引被表示成一个(K, V)对，K称为关键字，
可以是文件名（或文件的其他描述信息）的哈希值，V是实际存储文件的节点的IP地址（或节点的其他描述信息）。所有的文件索
引条目(即所有的（K, V）对)组成一张大的文件索引哈希表，只要输入目标文件的K值，就可以从这张表中查出所有存储该文件的节
点地址。然后，再将上面的大文件哈希表分割成很多局部小块，按照特定的规则把这些小块的局部哈希表分布到系统中的所有参与
节点上，使得每个节点负责维护其中的一块。这样，节点查询文件时，只要把查询报文路由到相应的节点即可（该节点维护的哈希
表分块中含有要查找的(K,V)对）。这里面有个很重要的问题，就是节点要按照一定的规则来分割整体的哈希表，进而也就决定了节
点要维护特定的邻居节点，以便路由能顺利进行。这个规则因具体系统的不同而不同，CAN，Chord，Pastry和Tapestry都有自己
的规则，也就呈现出不同的特性。基于分布式哈希表（DHT）的分布式检索和路由算法因为具有查找可确定性、简单性和分布性等
优点，正成为国际上结构化P2P网络研究和应用的热点。自2002年起，美国国家科学基金会（NSF）提供了1200万美元的资金启
动了一个为期5年的研究项目IRIS，该项目集中了MIT和UC Berkeley等5所著名高等院校的强大科研力量，为下一代大规模分布式应
用研制基于DHT的新型基础设施。
分布式哈希表在节点失效、遭受攻击和突发性高负载面前都能表现出很好的健壮性；它具有良好的可扩展性，能以较低系统开
销获得较大的系统规模；可以自我配置，不需要手工干预就可以自动把新加入节点合并到系统中；能提供简单灵活的接口，可以为
多个P2P应用同时使用。
销获得较大的系统规模；可以自我配置，不需要手工干预就可以自动把新加入节点合并到系统中；能提供简单灵活的接口，可以为
多个P2P应用同时使用。
1 Chord
Chord是UC Berkeley和MIT共同提出的一种分布式查找算法，目的是为了能在P2P网络中查找数据。给定一个关键字，Chord
可以有效地把该关键字映射到网络中某个节点上。因而在P2P网络中只要给每个数据V都赋予一个关键字K，就可以利用Chord在该
关键字映射的节点上存储或提取相应的(K, V)对。Chord的突出特点是算法简单，而且可扩展 － 查询过程的通信开销和节点维护的
状态随着系统总节点数增加成指数关系。Chord的路由性能优于CAN，而节点加入过程和维护开销又优于Tapestry和Pastry。
可以有效地把该关键字映射到网络中某个节点上。因而在P2P网络中只要给每个数据V都赋予一个关键字K，就可以利用Chord在该
关键字映射的节点上存储或提取相应的(K, V)对。Chord的突出特点是算法简单，而且可扩展 － 查询过程的通信开销和节点维护的
状态随着系统总节点数增加成指数关系。Chord的路由性能优于CAN，而节点加入过程和维护开销又优于Tapestry和Pastry。
Chord的设计:Chord中每个关键字和节点都分别拥有一个m比特的标识符。关键字标识符K通过哈希关键字本身得到，而节点
标识符N则通过哈希节点的IP地址得到。哈希函数可以选用SHA-1。所有节点按照其节点标识符从小到大（取模2m后）沿着顺时针
方向排列在一个逻辑的标识圆环上（称为Chord环）。Chord的映射规则是：关键字标识为K的(K, V)对存储在这样的节点上，该节
点的节点标识等于K或者在Chord环上紧跟在K之后，这个节点被称为K的后继节点，表示为successor(K)。因为标识符采用m位二
进制数表示，并且从0到2m－1顺序排列成一个圆圈，succesor(K)就是从K开始顺时针方向距离K最近的节点。
标识符N则通过哈希节点的IP地址得到。哈希函数可以选用SHA-1。所有节点按照其节点标识符从小到大（取模2m后）沿着顺时针
方向排列在一个逻辑的标识圆环上（称为Chord环）。Chord的映射规则是：关键字标识为K的(K, V)对存储在这样的节点上，该节
点的节点标识等于K或者在Chord环上紧跟在K之后，这个节点被称为K的后继节点，表示为successor(K)。因为标识符采用m位二
进制数表示，并且从0到2m－1顺序排列成一个圆圈，succesor(K)就是从K开始顺时针方向距离K最近的节点。
上图给出了一个m=6的Chord环，环中分布了10个节点，存储了5个关键字，节点标识前加上N而关键字前加上K以示区别。因为
successor(10)=14，所以关键字10存储到节点14上。同理，关键字24和30存储到节点32上，关键字38存储到节点38上，而关键
字54则存储到节点56上。当网络中的参与节点发生变动时，上面的映射规则仍然要成立。为此，当某节点n加入网络时，某些原来
分配给n的后继节点的关键字将分配给n。当节点n离开网络时，所有分配给它的关键字将重新分配给n的后继节点。除此之外，网络
中不会发生其他的变化。以上图为例，当标识为26的节点接入时，原有标识为32的节点负责的标识为24的关键字将转由新节点存
储。显然，为了能在系统中转发查询报文，每个节点要了解并维护chord环上相邻节点的标识和IP地址，并用这些信息构成自身的
路由表。有了这张表，Chord就可以在环上任意两点间进行寻路。
successor(10)=14，所以关键字10存储到节点14上。同理，关键字24和30存储到节点32上，关键字38存储到节点38上，而关键
字54则存储到节点56上。当网络中的参与节点发生变动时，上面的映射规则仍然要成立。为此，当某节点n加入网络时，某些原来
分配给n的后继节点的关键字将分配给n。当节点n离开网络时，所有分配给它的关键字将重新分配给n的后继节点。除此之外，网络
中不会发生其他的变化。以上图为例，当标识为26的节点接入时，原有标识为32的节点负责的标识为24的关键字将转由新节点存
储。显然，为了能在系统中转发查询报文，每个节点要了解并维护chord环上相邻节点的标识和IP地址，并用这些信息构成自身的
路由表。有了这张表，Chord就可以在环上任意两点间进行寻路。
Chord的路由：Chord中每个节点只要维护它在环上的后继节点的标识和IP地址就可以完成简单的查询过程。对特定关键字的
查询报文可以通过后继节点指针在圆环上传递，直到到达这样一个节点：关键字的标识落在该节点标识和它的后继节点标识之间，
这里的后继节点就是存储目标(K, V)对的节点。
查询报文可以通过后继节点指针在圆环上传递，直到到达这样一个节点：关键字的标识落在该节点标识和它的后继节点标识之间，
这里的后继节点就是存储目标(K, V)对的节点。
上图给出了一个示例，节点8发起的查找关键字54的请求，通过后继节点依次传递，最后定位到存储有关键字54的节点56。在
这种简单查询方式中，每个节点需要维护的状态信息很少，但查询速度太慢。若网络中有N个节点，查询的代价就为O（N）数量
级。因而在网络规模很大时，这样的速度是不能接受的。
这种简单查询方式中，每个节点需要维护的状态信息很少，但查询速度太慢。若网络中有N个节点，查询的代价就为O（N）数量
级。因而在网络规模很大时，这样的速度是不能接受的。
为了加快查询的速度，Chord使用扩展的查询算法。为此，每个节点需要维护一个路由表，称为指针表（finger table）。如果
关键字和节点标识符用m位二进制位数表示，那么指针表中最多含有m个表项。节点n的指针表中第i项是圆环上标识大于或等于
n+2i-1的第一个节点（比较是以2m为模进行的）。例如若s=successor(n+2i-1), 1≤i≤m，则称节点s为节点n的第i个指针，记为
n.finger[i]。n.finger[1]就是节点n的后继节点。指针表中每一项既包含相关节点的标识，又包含该节点的IP地址（和端口号）。
五个节点维护的CAN虚平面
关键字和节点标识符用m位二进制位数表示，那么指针表中最多含有m个表项。节点n的指针表中第i项是圆环上标识大于或等于
n+2i-1的第一个节点（比较是以2m为模进行的）。例如若s=successor(n+2i-1), 1≤i≤m，则称节点s为节点n的第i个指针，记为
n.finger[i]。n.finger[1]就是节点n的后继节点。指针表中每一项既包含相关节点的标识，又包含该节点的IP地址（和端口号）。
上图给出了节点8的指针表，例如节点14是环上紧接在(8+20) mod 26=9之后的第一个节点，所以节点8的第一个指针是节点14；同
理因为节点42是环上紧接在(8+25) mod 26=40之后的第一个节点，所以节点8的第6个指针是节点42。维护指针表使得每个节点只
需要知道网络中一小部分节点的信息，而且离它越近的节点，它就知道越多的信息。但是，对于任意一个关键字K，节点通常无法
根据自身的指针表确定的K的后继节点。例如，下图中的节点8就不能确定关键字34的后继节点，因为环上34的后继节点是38，而
节点38并没有出现在节点8的指针表中。
扩展的查询过程是：任何一个节点收到查询关键字K的请求时，首先检查关K是否落在该节点标识和它的后继节点标识之间，
如果是的话，这个后继节点就是存储目标(K, V)对的节点。否则，节点将查找它的指针表，找到表中节点标识符最大但不超过K的第
一个节点，并将这个查询请求转发给该节点。通过重复这个过程，最终可以定位到K的后继节点，即存储有目标(K, V)对的节点。
如果是的话，这个后继节点就是存储目标(K, V)对的节点。否则，节点将查找它的指针表，找到表中节点标识符最大但不超过K的第
一个节点，并将这个查询请求转发给该节点。通过重复这个过程，最终可以定位到K的后继节点，即存储有目标(K, V)对的节点。
节点加入和退出：为了应对系统的变化，每个节点都周期性地运行探测协议来检测新加入节点或失效节点，从而更新自己的指
针表和指向后继节点的指针。新节点n加入时，将通过系统中现有的节点来初始化自己的指针表。也就是说，新节点n将要求已知的
系统中某节点为它查找指针表中的各个表项。在其他节点运行探测协议后，新节点n将被反映到相关节点的指针表和后继节点指针
中。这时，系统中一部分关键字的后继节点也变为新节点n，因而先前的后继节点要将这部分关键字转移到新节点上。当节点n失效
时，所有指针表中包括n的节点都必须把它替换成n的后继节点。为了保证节点n的失效不影响系统中正在进行的查询过程，每个
Chord节点都维护一张包括r个最近后继节点的后继列表。如果某个节点注意到它的后继节点失效了，它就用其后继列表中第一个正
常节点替换失效节点。
针表和指向后继节点的指针。新节点n加入时，将通过系统中现有的节点来初始化自己的指针表。也就是说，新节点n将要求已知的
系统中某节点为它查找指针表中的各个表项。在其他节点运行探测协议后，新节点n将被反映到相关节点的指针表和后继节点指针
中。这时，系统中一部分关键字的后继节点也变为新节点n，因而先前的后继节点要将这部分关键字转移到新节点上。当节点n失效
时，所有指针表中包括n的节点都必须把它替换成n的后继节点。为了保证节点n的失效不影响系统中正在进行的查询过程，每个
Chord节点都维护一张包括r个最近后继节点的后继列表。如果某个节点注意到它的后继节点失效了，它就用其后继列表中第一个正
常节点替换失效节点。
2 Pastry
Microsoft研究院和Rice大学共同提出的Pastry是用于广域P2P应用的分布式查找和路由系统。Pastry系统中的每个节点都有一
个唯一的节点号（nodeId），每条消息都有一个关键字。Pastry可以把消息路由到nodeId和关键字在数值上最接近的那个节点。每
个Pastry节点维护节点号空间中和它直接相邻的邻居节点信息。当发生新节点加入、已有节点失效或恢复事件时，Pastry节点会通
知上层应用。Pastry是完全分布式的、可扩展的和自组织的，它能够自动应对节点加入、离开和失效。
个唯一的节点号（nodeId），每条消息都有一个关键字。Pastry可以把消息路由到nodeId和关键字在数值上最接近的那个节点。每
个Pastry节点维护节点号空间中和它直接相邻的邻居节点信息。当发生新节点加入、已有节点失效或恢复事件时，Pastry节点会通
知上层应用。Pastry是完全分布式的、可扩展的和自组织的，它能够自动应对节点加入、离开和失效。
Pastry的设计：Pastry是自组织的重叠网络，每个节点都被分配一个128位的nodeId。nodeId用于在圆形的节点空间中（从0
到2128－1）标识节点的位置，它是在节点加入系统时随机分配的，随机分配的结果是使得所有的nodeId在128位的节点号空间中
均匀分布。nodeId可以通过计算节点公钥或者IP地址的哈希函数值来获得。
到2128－1）标识节点的位置，它是在节点加入系统时随机分配的，随机分配的结果是使得所有的nodeId在128位的节点号空间中
均匀分布。nodeId可以通过计算节点公钥或者IP地址的哈希函数值来获得。
假设网络包含N个节点，Pastry可以把一个给定的关键字路由到nodeId和该关键字最接近的节点。即使同时发生节点失效，
Pastry也可以保证关键字送达目标节点，除非nodeId和关键字临近的节点中有|L|/2个同时失效（|L|是配置参数，典型值取16或
32）。为了进行路由，Pastry把nodeId和关键字表示为一串以2b为基的数，查询消息被路由到nodeId和关键字在数值上最接近的节
点。方法是：每个节点把查询消息转发给下一个节点时，要保证这个节点的nodeId和关键字的相同前缀至少要比当前节点的nodeId
和关键字的相同前缀长一个数位（即b个比特）。如果找不到这样的邻居节点，消息将转发给前缀长度相同但是节点号数值更接近
关键字的节点。为此，每个Pastry节点都需要维护状态表：一张路由表，一个邻居节点集和一个叶子节点集。
Pastry也可以保证关键字送达目标节点，除非nodeId和关键字临近的节点中有|L|/2个同时失效（|L|是配置参数，典型值取16或
32）。为了进行路由，Pastry把nodeId和关键字表示为一串以2b为基的数，查询消息被路由到nodeId和关键字在数值上最接近的节
点。方法是：每个节点把查询消息转发给下一个节点时，要保证这个节点的nodeId和关键字的相同前缀至少要比当前节点的nodeId
和关键字的相同前缀长一个数位（即b个比特）。如果找不到这样的邻居节点，消息将转发给前缀长度相同但是节点号数值更接近
关键字的节点。为此，每个Pastry节点都需要维护状态表：一张路由表，一个邻居节点集和一个叶子节点集。
nodeId为10233102的Pastry节点维护的状态示意图
上图给出了一个节点维护的数据示意图，b取值为2，所有的数均是4进制的。其中路由表的最上面一行是第0行。路由表中每
行的阴影项表示当前节点号中相应的数位。路由表中每项节点的nodeId表示格式是“相同前缀 ＋ 下一数位 ＋ nodeId的剩余
位”。图中没有列出相关节点的IP地址。
行的阴影项表示当前节点号中相应的数位。路由表中每项节点的nodeId表示格式是“相同前缀 ＋ 下一数位 ＋ nodeId的剩余
位”。图中没有列出相关节点的IP地址。
路由表每行包括2b-1个表项。第n行的2b-1个表项中，每个节点nodeId的前n个数位和当前节点nodeId的前n个数位相同，而第
n＋1个数位和当前节点不同。b的取值是路由表大小和任意两节点间需要的最大路由跳数之间的折衷。例如，当b取4而网络中有
106 个节点时，每个节点的路由表平均包括75个表项，预期的路由跳数是5。如果网络中有109个节点，则路由表平均会有105项，
而预期的路由步数也将增加到7。
n＋1个数位和当前节点不同。b的取值是路由表大小和任意两节点间需要的最大路由跳数之间的折衷。例如，当b取4而网络中有
106 个节点时，每个节点的路由表平均包括75个表项，预期的路由跳数是5。如果网络中有109个节点，则路由表平均会有105项，
而预期的路由步数也将增加到7。
叶子节点集维护的是nodeId和本节点最接近的节点，其中一半是nodeId大于当前节点的，另一半是nodeId小于当前节点的。
叶子节点集在路由时需要用到。邻居节点集维护按给定的评测指标距离本节点最近的节点，正常的路由过程并不使用邻居节点集，
它的主要作用是维护路由的本地性。通常这两个集合的大小分别为2b或者2×2b。
叶子节点集在路由时需要用到。邻居节点集维护按给定的评测指标距离本节点最近的节点，正常的路由过程并不使用邻居节点集，
它的主要作用是维护路由的本地性。通常这两个集合的大小分别为2b或者2×2b。
Pastry的路由过程是：节点收到一条查询消息时，首先检查该消息的关键字是否落在叶子节点集范围内。如果是，则直接把消
息转发给对应的节点，也就是叶子节点集中nodeId和关键字最接近的节点。如果关键字没有落在叶子节点集范围内，节点就会把消
息转发给路由表中的一个节点，该节点的nodeId和关键字的相同前缀至少要比当前节点的nodeId和关键字的相同前缀长一个数位。
如果路由表中相应的表项为空，或者表项中对应的节点不可达，这时候查询消息将被转发给前缀长度相同但是节点号数值更接近关
键字的节点。除非消息已经到达目的节点，否则这样的节点一定位于叶子节点集中。而且，只要叶子节点集中一半以上的节点不同
时失效，就一定可以找到满足要求的节点。很明显，路由的每一步都比上一步向目标节点前进了一步，因此路由过程总是收敛的。
息转发给对应的节点，也就是叶子节点集中nodeId和关键字最接近的节点。如果关键字没有落在叶子节点集范围内，节点就会把消
息转发给路由表中的一个节点，该节点的nodeId和关键字的相同前缀至少要比当前节点的nodeId和关键字的相同前缀长一个数位。
如果路由表中相应的表项为空，或者表项中对应的节点不可达，这时候查询消息将被转发给前缀长度相同但是节点号数值更接近关
键字的节点。除非消息已经到达目的节点，否则这样的节点一定位于叶子节点集中。而且，只要叶子节点集中一半以上的节点不同
时失效，就一定可以找到满足要求的节点。很明显，路由的每一步都比上一步向目标节点前进了一步，因此路由过程总是收敛的。
节点加入和退出
新节点加入时需要初始化自身的状态表，并通知其他节点自己已经加入系统。假定新加入节点的nodeId为X，同时假定X在加
入Pastry之前知道系统中和自己距离相近的节点A。新节点X首先请求A路由一条“加入”消息，消息的关键字就是X。这条消息最终
会到达nodeId和X最接近的节点Z。作为应答，节点A、节点Z以及从A到Z的路径上所有经过的节点都会把自己的状态表发送给节点
X。节点X利用这些信息初始化自己的状态表，然后节点X再通知其他节点它已经加入了系统。从交换的消息数量上说，节点加入操
作的复杂度为O（log2bN）。
入Pastry之前知道系统中和自己距离相近的节点A。新节点X首先请求A路由一条“加入”消息，消息的关键字就是X。这条消息最终
会到达nodeId和X最接近的节点Z。作为应答，节点A、节点Z以及从A到Z的路径上所有经过的节点都会把自己的状态表发送给节点
X。节点X利用这些信息初始化自己的状态表，然后节点X再通知其他节点它已经加入了系统。从交换的消息数量上说，节点加入操
作的复杂度为O（log2bN）。
Pastry中节点很可能失效或者突然离开系统。若nodeId空间中的相邻节点无法和某个节点通信时，就认为该节点失效了。一旦
节点检测出其叶子节点集L中的某个节点失效，它就会请求该集合中nodeId最大或最小的节点把其叶子节点集L’发送过来。（如果
失效节点的nodeId比当前节点的nodeId大，则用叶子集中nodeId最大的节点，反之则用nodeId最小的节点。）当前节点将从L’中
选择一个L中没有的活动节点来替代失效节点。如果节点检测出其路由表中某项对应的节点失效，它将从该项所在的路由表行中选
择另一个节点，要求该节点把路由表中对应位置的项发过来。如果当前节点的路由表中对应行已经没有可用节点了，那么当前节点
将从路由表的下一行中选择一个节点，这个过程将继续到当前节点能够得到一个替代失效节点的节点号，或者当前节点遍历了路由
表为止。节点也会周期性地和邻居节点集中的节点交换信息以检测这些节点是否仍在Pastry系统中，如果节点检测出其邻居节点集
中的某个节点失效，它将请求其他邻居节点把其邻居节点集发送过来并从中选择一个新的邻居节点替换失效节点。
节点检测出其叶子节点集L中的某个节点失效，它就会请求该集合中nodeId最大或最小的节点把其叶子节点集L’发送过来。（如果
失效节点的nodeId比当前节点的nodeId大，则用叶子集中nodeId最大的节点，反之则用nodeId最小的节点。）当前节点将从L’中
选择一个L中没有的活动节点来替代失效节点。如果节点检测出其路由表中某项对应的节点失效，它将从该项所在的路由表行中选
择另一个节点，要求该节点把路由表中对应位置的项发过来。如果当前节点的路由表中对应行已经没有可用节点了，那么当前节点
将从路由表的下一行中选择一个节点，这个过程将继续到当前节点能够得到一个替代失效节点的节点号，或者当前节点遍历了路由
表为止。节点也会周期性地和邻居节点集中的节点交换信息以检测这些节点是否仍在Pastry系统中，如果节点检测出其邻居节点集
中的某个节点失效，它将请求其他邻居节点把其邻居节点集发送过来并从中选择一个新的邻居节点替换失效节点。
3 CAN
UC Berkeley提出的CAN（Content Addressable Network，内容寻址网络）实现了文件索引和存放位置的有效映射，不需要
任何形式的中央控制点，节点只需要维护少量的控制状态而且状态数量独立于系统中的节点数量，具有完全自组织和分布式的结
构，并且有良好的可扩展性和容错性。
任何形式的中央控制点，节点只需要维护少量的控制状态而且状态数量独立于系统中的节点数量，具有完全自组织和分布式的结
构，并且有良好的可扩展性和容错性。
CAN的设计
CAN的设计基于虚拟的d维笛卡儿坐标空间，这个坐标空间完全是逻辑的，和任何物理坐标系统都没有关系。在任何时候，整
个坐标空间动态地分配给系统中的所有节点，每个节点负责维护独立的互不相交的一块区域。CAN中的节点自组织成一个代表这个
虚拟坐标空间的重叠网络（overlay network）。每个节点要了解并维护相邻区域中节点的IP地址,用这些邻居信息构成自身的坐标路
由表。有了这张表，CAN可以在坐标空间中任意两点间进行寻路。
个坐标空间动态地分配给系统中的所有节点，每个节点负责维护独立的互不相交的一块区域。CAN中的节点自组织成一个代表这个
虚拟坐标空间的重叠网络（overlay network）。每个节点要了解并维护相邻区域中节点的IP地址,用这些邻居信息构成自身的坐标路
由表。有了这张表，CAN可以在坐标空间中任意两点间进行寻路。
下图给出了一个2维的[0, 1]×[0, 1]的笛卡儿坐标空间划分成五个节点区域的情况。虚拟坐标空间采用下面的方法保存（K, V）
对。当保存（K1, V1）时，使用统一的哈希函数把关键字K1映射成坐标空间中的点P。那么这个值将被保存在该点所在区域的节点
中。当需要查询关键字K1对应的值时，任何节点都可以使用同样的哈希函数找到K1对应的点P，然后从该点对应的节点取出相应的
值V1。如果此节点不是发起查询请求的节点，CAN将负责将此查询请求转发到P所在区域的节点上。因此，有效的路由机制是CAN
中的一个关键问题。
对。当保存（K1, V1）时，使用统一的哈希函数把关键字K1映射成坐标空间中的点P。那么这个值将被保存在该点所在区域的节点
中。当需要查询关键字K1对应的值时，任何节点都可以使用同样的哈希函数找到K1对应的点P，然后从该点对应的节点取出相应的
值V1。如果此节点不是发起查询请求的节点，CAN将负责将此查询请求转发到P所在区域的节点上。因此，有效的路由机制是CAN
中的一个关键问题。
CAN的路由
CAN中的路由很简单，沿着坐标空间中从发起请求的点到目的点之间的一条路径转发即可。为此，每个CAN节点都要保存一
张坐标路由表，其中包括它的邻居节点的IP地址和其维护的虚拟坐标区域。两个节点互为邻居是指：在d维坐标空间中，两个节点
维护的区域在d－1维的坐标上有重叠而在剩下的一维坐标上相互邻接。例如，图2.6中D和E是邻接节点，而D和B就不是邻接节点,
因为D和B在X轴和Y轴上都邻接。每条CAN消息都包括目的点坐标。路由时节点只要朝着目标节点的方向把消息转发给自己的邻居
节点即可。下图给出了查找过程的一个简单的例子。
张坐标路由表，其中包括它的邻居节点的IP地址和其维护的虚拟坐标区域。两个节点互为邻居是指：在d维坐标空间中，两个节点
维护的区域在d－1维的坐标上有重叠而在剩下的一维坐标上相互邻接。例如，图2.6中D和E是邻接节点，而D和B就不是邻接节点,
因为D和B在X轴和Y轴上都邻接。每条CAN消息都包括目的点坐标。路由时节点只要朝着目标节点的方向把消息转发给自己的邻居
节点即可。下图给出了查找过程的一个简单的例子。
如果一个d维空间划分成n个相等的区域，那么平均路由长度是(d/4)(n1/d)，每个节点只需要维护2d个邻居节点的信息。这个结
果表明CAN的可扩展性很好，节点数增加时每个节点维护的状态信息不变，而路由长度只是以O（n1/d）的数量级增长。因为坐标
空间中两点之间可以有许多条不同的路径，所以单个节点的失效对CAN基本上没有太大的影响。遇到失效节点时，CAN会自动沿着
其他的路径进行路由。
果表明CAN的可扩展性很好，节点数增加时每个节点维护的状态信息不变，而路由长度只是以O（n1/d）的数量级增长。因为坐标
空间中两点之间可以有许多条不同的路径，所以单个节点的失效对CAN基本上没有太大的影响。遇到失效节点时，CAN会自动沿着
其他的路径进行路由。
节点加入和退出
因为整个CAN空间要分配给系统中现有的全部节点，当一个新的节点加入网络时必须得到自己的一块坐标空间。CAN通过分
割现有的节点区域实现这一过程。它把某个现有节点的区域分裂成同样大小的两块，自己保留其中的一块而另一块分给新加入的节
点。整个过程分为以下三步：
割现有的节点区域实现这一过程。它把某个现有节点的区域分裂成同样大小的两块，自己保留其中的一块而另一块分给新加入的节
点。整个过程分为以下三步：
1. 新节点首先找到一个已经在CAN中的节点。
2. 新节点使用CAN的路由机制找到一个区域将要被分割的节点。
3. 执行分割操作，然后原有区域的邻接区域必须被告知发生了分割，这样新节点才能被别的节点路由到。
当节点离开CAN时，必须保证它的区域被系统中剩余的节点接管，也即分配给其他仍然在系统中的节点。一般是由某个邻居节
点来接管这个区域和所有的索引数据（K，V）对。如果某个邻居节点负责的区域可以和离开节点负责的区域合并形成一个大的区
域，那么将由这个邻居节点执行合并操作。否则，该区域将交给其邻居节点中区域最小的节点负责。也就是说，这个节点将临时负
责两个区域。
点来接管这个区域和所有的索引数据（K，V）对。如果某个邻居节点负责的区域可以和离开节点负责的区域合并形成一个大的区
域，那么将由这个邻居节点执行合并操作。否则，该区域将交给其邻居节点中区域最小的节点负责。也就是说，这个节点将临时负
责两个区域。
正常情况下，每个节点向其所有邻居节点发送周期性的更新消息，消息中包括自身的区域范围、它的邻居列表以及这些邻居节
点负责的区域范围。如果多次没有接收到某个邻居的更新消息，那么节点就认为这个邻居失效了。这时，节点将启动接管机制，并
启动一个时钟。失效节点的每个邻居节点相互独立地执行该过程，每个时钟大小都和相应节点负责的区域面积成比例。如果时钟超
时，节点将向失效节点的所有邻居节点发送接管消息，该消息中包括它自己的区域面积信息。当某个节点接收到接管消息后，如果
它的区域面积比发出消息的节点大，那么它将取消接管操作。否则它将发出自己的取代消息。采用这种机制可以有效地选择面积最
小的邻居节点来接管失效节点。在特殊情况下，还有可能出现多个相邻的节点同时失效的情况。例如，节点检测到某个节点失效，
但是失效节点地邻居中超过一半可能都不可达。这时，如果让该节点接管失效节点地区域，就有可能导致CAN中状态不一致。所以
在这种情况下，CAN在执行修复操作之前，会搜索失效区域附近的节点，搜索逐步扩大直至获得足够的邻居状态，以便安全地开始
接管过程。
点负责的区域范围。如果多次没有接收到某个邻居的更新消息，那么节点就认为这个邻居失效了。这时，节点将启动接管机制，并
启动一个时钟。失效节点的每个邻居节点相互独立地执行该过程，每个时钟大小都和相应节点负责的区域面积成比例。如果时钟超
时，节点将向失效节点的所有邻居节点发送接管消息，该消息中包括它自己的区域面积信息。当某个节点接收到接管消息后，如果
它的区域面积比发出消息的节点大，那么它将取消接管操作。否则它将发出自己的取代消息。采用这种机制可以有效地选择面积最
小的邻居节点来接管失效节点。在特殊情况下，还有可能出现多个相邻的节点同时失效的情况。例如，节点检测到某个节点失效，
但是失效节点地邻居中超过一半可能都不可达。这时，如果让该节点接管失效节点地区域，就有可能导致CAN中状态不一致。所以
在这种情况下，CAN在执行修复操作之前，会搜索失效区域附近的节点，搜索逐步扩大直至获得足够的邻居状态，以便安全地开始
接管过程。
4 Tapestry
Tapestry是UC Berkeley提出的一种新型的P2P网络定位和路由算法。该算法可以对消息进行与位置无关的路由，把查询消息
传递到最近的存储有目标对象拷贝的节点。Tapestry具有自组织、容错和负载平衡等特点。每个Tapestry 节点只需维护O（log N）
大小的路由表信息，路由最多在O（log N）跳数内完成。
传递到最近的存储有目标对象拷贝的节点。Tapestry具有自组织、容错和负载平衡等特点。每个Tapestry 节点只需维护O（log N）
大小的路由表信息，路由最多在O（log N）跳数内完成。
Tapestry的设计
Tapestry从一个标识符空间中为每个节点随机分配一个节点标识符nodeID，对象也从同一个标识符空间中分配一个全局唯一
标识符GUID（globally unique identifier）。Tapestry使用SHA-1来产生标识符，使得nodeID和GUID均匀分布在标识符空间中。为
了讨论问题的方便，用Nid来表示节点N的标识符，用OG表示对象O的标识符。Tapestry目前使用160比特的标识符空间，标识符用
一个全局统一的进制表示（例如使用16进制，则标识符是一个40位的数字），所有的节点依据标识符自组织成一个重叠网络。
标识符GUID（globally unique identifier）。Tapestry使用SHA-1来产生标识符，使得nodeID和GUID均匀分布在标识符空间中。为
了讨论问题的方便，用Nid来表示节点N的标识符，用OG表示对象O的标识符。Tapestry目前使用160比特的标识符空间，标识符用
一个全局统一的进制表示（例如使用16进制，则标识符是一个40位的数字），所有的节点依据标识符自组织成一个重叠网络。
Tapestry动态地把每个标识符G映射到当前系统中一个节点上，该节点称为G的根节点，表示为GR。如果某节点的Nid＝G，则
这个节点就是G的根节点。为了转发查询消息，每个节点需要维护一个邻居映射表，每个表项包括一个邻居节点的标识符和IP地
址。往GR路由时，消息将沿着邻居指针向节点标识符在标识符空间中更接近G的节点转发（例如，匹配更大的前缀）。
这个节点就是G的根节点。为了转发查询消息，每个节点需要维护一个邻居映射表，每个表项包括一个邻居节点的标识符和IP地
址。往GR路由时，消息将沿着邻居指针向节点标识符在标识符空间中更接近G的节点转发（例如，匹配更大的前缀）。
Tapestry中的每个节点都保存有邻居映射表。邻居映射表可以用于把消息按照目的地址一位一位地向前传递，比如从
4***=>42**98=>42A*=>目的节点42AD（这里*表示通配符）。这种方式类似于IP分组转发过程中的最长前缀匹配。节点N的邻居映
射表分为多个级别，每个级别包含的邻居节点的数量等于标识符表示法的基数，而每个级别中邻居节点标识符和本节点标识符的相
同前缀都比前一级别多一个数位。也就是说，第j级邻居表的第i项是标识符以prefix(N, j-1) ＋ “i”为前缀而且离当前节点最近的邻
居节点。例如，节点325AE的邻居映射表中第4级第9项是系统中标识符以325 + “9” =3259为前缀的某个节点。
4***=>42**98=>42A*=>目的节点42AD（这里*表示通配符）。这种方式类似于IP分组转发过程中的最长前缀匹配。节点N的邻居映
射表分为多个级别，每个级别包含的邻居节点的数量等于标识符表示法的基数，而每个级别中邻居节点标识符和本节点标识符的相
同前缀都比前一级别多一个数位。也就是说，第j级邻居表的第i项是标识符以prefix(N, j-1) ＋ “i”为前缀而且离当前节点最近的邻
居节点。例如，节点325AE的邻居映射表中第4级第9项是系统中标识符以325 + “9” =3259为前缀的某个节点。
上图给出了一个节点的邻居指针实例，从图中可以看到第一级的邻居节点标识和本节点标识没有共同前缀，而第二级的邻居节点标
识都以4开头，即和本节点标识具有相同的一个数位的前缀。
识都以4开头，即和本节点标识具有相同的一个数位的前缀。
Tapestry采用的基本查找和路由机制：当一条查找消息到达传递过程中的第n个节点时，该节点和目的节点的共同前缀长度至
少大于n。为了进行转发，该节点将查找邻居映射表的第n+1级中和目的标识符下一数位相匹配的邻居节点。转发过程将在每个节点
中依次进行直到到达目的节点。这种方法可以保证路由至多经过logbN个节点就可以到达目的节点，这里N是节点标识符名字空间的
大小，而b是标识符使用的基数。同样，由于每个节点的邻居映射表的每个级别只需要保存b个表项，因此，邻居映射表的空间为
blogbN。
少大于n。为了进行转发，该节点将查找邻居映射表的第n+1级中和目的标识符下一数位相匹配的邻居节点。转发过程将在每个节点
中依次进行直到到达目的节点。这种方法可以保证路由至多经过logbN个节点就可以到达目的节点，这里N是节点标识符名字空间的
大小，而b是标识符使用的基数。同样，由于每个节点的邻居映射表的每个级别只需要保存b个表项，因此，邻居映射表的空间为
blogbN。
上图给出了Tapestry中一个查询消息转发的例子。图中节点标识符的基数是4，查询消息从5230发出，目的节点是42AD。
Tapestry中的节点在共享数据时被称为服务器，请求数据时被称为客户，转发消息时被称为路由器。也就是说每个节点可以同
时具有客户、服务器和路由器的功能。
时具有客户、服务器和路由器的功能。
服务器S通过向对象O（GUID为OG）的根节点OR定期的发送消息来报告S保存有对象O。在这条发布路径上的每个节点都保存
关于这个对象O的位置信息指针<OG, S>，这里的位置信息只是一个指向S的指针，而并不是对象O的拷贝。当多个都存有同一对象
拷贝的服务器分别向根结点发布消息时，路径上的每个节点按各个服务器离自己的网络时延递增的顺序保存这些位置指针列表。
关于这个对象O的位置信息指针<OG, S>，这里的位置信息只是一个指向S的指针，而并不是对象O的拷贝。当多个都存有同一对象
拷贝的服务器分别向根结点发布消息时，路径上的每个节点按各个服务器离自己的网络时延递增的顺序保存这些位置指针列表。
当需要定位一个对象O时，客户向对象O的根节点发出查询消息，查询消息转发路径上的每个节点都检查自己是否存有对象O
的位置指针，如果有，该节点直接把查询消息转发个服务器S，否则，消息将到达O的根节点，然后由根节点把查询消息转发给服务器。
的位置指针，如果有，该节点直接把查询消息转发个服务器S，否则，消息将到达O的根节点，然后由根节点把查询消息转发给服务器。
Tapestry有一个重要的特性是：查询消息可以被转发到距离客户最近的存有对象拷贝的服务器上。在Tapestry中，从两个临近节点
向同一个目的节点OR发出两条消息时，它们的转发路径很快就会交叉，这是因为路由过程的每一步都是使得下一个节点标识符和
OR具有更长的相同前缀；到根结点的路径只是目的标识符的函数，而不是消息发起节点标识符的函数；而且，路由过程中的下一跳
邻居节点是根据网络距离选择的，因而客户离服务器越近，那么查询路径碰到发布路径的速度就越快。也就是说，查询消息会被转
发到最近的服务器上。
向同一个目的节点OR发出两条消息时，它们的转发路径很快就会交叉，这是因为路由过程的每一步都是使得下一个节点标识符和
OR具有更长的相同前缀；到根结点的路径只是目的标识符的函数，而不是消息发起节点标识符的函数；而且，路由过程中的下一跳
邻居节点是根据网络距离选择的，因而客户离服务器越近，那么查询路径碰到发布路径的速度就越快。也就是说，查询消息会被转
发到最近的服务器上。
节点加入和退出：Tapestry的节点加入算法和Pastry类似。节点N在加入Tapestry网络之前，也需要知道一个已经在网络中的
节点G。然后N通过G发出路由自己的节点ID的请求，根据经过的节点的对应的邻居节点表构造自己的邻居节点表。构造过程中还需
要进行一些优化工作。构造完自己的数据结构后，节点N将通知网络中的其他节点自己已经加入网络。通知只针对在N的邻居映射
表中的主邻居节点和二级邻居节点进行。
节点G。然后N通过G发出路由自己的节点ID的请求，根据经过的节点的对应的邻居节点表构造自己的邻居节点表。构造过程中还需
要进行一些优化工作。构造完自己的数据结构后，节点N将通知网络中的其他节点自己已经加入网络。通知只针对在N的邻居映射
表中的主邻居节点和二级邻居节点进行。
Tapestry采用两种机制处理节点的退出。一种情况是节点从网络中自行消失（主要原因是节点失效），在这种情况下，它的邻
居可以检测到它已经退出网络并可以相应的调整路由表。另一种机制是节点在退出系统之前通过后向指针通过所有把它作为邻居的
节点，这些节点会相应调整路由表并通知对象服务器该节点已经退出网络。检测正常操作过程中的链路和服务器失效，可以使用
TCP连接超时机制。除此之外，每个Tapestry节点都使用后向指针周期性的发送“心跳”(heartbeats)UDP分组给把自己加入邻居
映射表的节点。每个节点都可以根据自己收到的心跳分组来决定自己的邻居映射表中是否有节点失效。在邻居节点表中，除了主邻
居节点（最近的邻居）之外，每个路由项还保存了两个备份的邻居节点，当检测到主邻居节点失效后，邻居节点表将顺序选择备份
邻居节点。
居可以检测到它已经退出网络并可以相应的调整路由表。另一种机制是节点在退出系统之前通过后向指针通过所有把它作为邻居的
节点，这些节点会相应调整路由表并通知对象服务器该节点已经退出网络。检测正常操作过程中的链路和服务器失效，可以使用
TCP连接超时机制。除此之外，每个Tapestry节点都使用后向指针周期性的发送“心跳”(heartbeats)UDP分组给把自己加入邻居
映射表的节点。每个节点都可以根据自己收到的心跳分组来决定自己的邻居映射表中是否有节点失效。在邻居节点表中，除了主邻
居节点（最近的邻居）之外，每个路由项还保存了两个备份的邻居节点，当检测到主邻居节点失效后，邻居节点表将顺序选择备份
邻居节点。
