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

转载自这里。2006.3.6
本文首先从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 [...]

[zz]P2P网络中的DHT分布式哈希结构

转载自这里
现有的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的新型基础设施。
分布式哈希表在节点失效、遭受攻击和突发性高负载面前都能表现出很好的健壮性；它具有良好的可扩展性，能以较低系统开销获得较大的系统规模；可以自我配置，不需要手工干预就可以自动把新加入节点合并到系统中；能提供简单灵活的接口，可以为多个P2P应用同时使用。
1 Chord
Chord是UC Berkeley和MIT共同提出的一种分布式查找算法，目的是为了能在P2P网络中查找数据。给定一个关键字，Chord可以有效地把该关键字映射到网络中某个节点上。因而在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最近的节点。

上图给出了一个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就可以在环上任意两点间进行寻路。
Chord的路由：Chord中每个节点只要维护它在环上的后继节点的标识和IP地址就可以完成简单的查询过程。对特定关键字的查询报文可以通过后继节点指针在圆环上传递，直到到达这样一个节点：关键字的标识落在该节点标识和它的后继节点标识之间，这里的后继节点就是存储目标(K, V)对的节点。
上图给出了一个示例，节点8发起的查找关键字54的请求，通过后继节点依次传递，最后定位到存储有关键字54的节点56。在这种简单查询方式中，每个节点需要维护的状态信息很少，但查询速度太慢。若网络中有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地址（和端口号）。

上图给出了节点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)对的节点。
节点加入和退出：为了应对系统的变化，每个节点都周期性地运行探测协议来检测新加入节点或失效节点，从而更新自己的指针表和指向后继节点的指针。新节点n加入时，将通过系统中现有的节点来初始化自己的指针表。也就是说，新节点n将要求已知的系统中某节点为它查找指针表中的各个表项。在其他节点运行探测协议后，新节点n将被反映到相关节点的指针表和后继节点指针中。这时，系统中一部分关键字的后继节点也变为新节点n，因而先前的后继节点要将这部分关键字转移到新节点上。当节点n失效时，所有指针表中包括n的节点都必须把它替换成n的后继节点。为了保证节点n的失效不影响系统中正在进行的查询过程，每个Chord节点都维护一张包括r个最近后继节点的后继列表。如果某个节点注意到它的后继节点失效了，它就用其后继列表中第一个正常节点替换失效节点。
2 Pastry
Microsoft研究院和Rice大学共同提出的Pastry是用于广域P2P应用的分布式查找和路由系统。Pastry系统中的每个节点都有一个唯一的节点号（nodeId），每条消息都有一个关键字。Pastry可以把消息路由到nodeId和关键字在数值上最接近的那个节点。每个Pastry节点维护节点号空间中和它直接相邻的邻居节点信息。当发生新节点加入、已有节点失效或恢复事件时，Pastry节点会通知上层应用。Pastry是完全分布式的、可扩展的和自组织的，它能够自动应对节点加入、离开和失效。
Pastry的设计：Pastry是自组织的重叠网络，每个节点都被分配一个128位的nodeId。nodeId用于在圆形的节点空间中（从0到2128－1）标识节点的位置，它是在节点加入系统时随机分配的，随机分配的结果是使得所有的nodeId在128位的节点号空间中均匀分布。nodeId可以通过计算节点公钥或者IP地址的哈希函数值来获得。
假设网络包含N个节点，Pastry可以把一个给定的关键字路由到nodeId和该关键字最接近的节点。即使同时发生节点失效，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地址。
路由表每行包括2b-1个表项。第n行的2b-1个表项中，每个节点nodeId的前n个数位和当前节点nodeId的前n个数位相同，而第n＋1个数位和当前节点不同。b的取值是路由表大小和任意两节点间需要的最大路由跳数之间的折衷。例如，当b取4而网络中有106 个节点时，每个节点的路由表平均包括75个表项，预期的路由跳数是5。如果网络中有109个节点，则路由表平均会有105项，而预期的路由步数也将增加到7。
叶子节点集维护的是nodeId和本节点最接近的节点，其中一半是nodeId大于当前节点的，另一半是nodeId小于当前节点的。叶子节点集在路由时需要用到。邻居节点集维护按给定的评测指标距离本节点最近的节点，正常的路由过程并不使用邻居节点集，它的主要作用是维护路由的本地性。通常这两个集合的大小分别为2b或者2×2b。
Pastry的路由过程是：节点收到一条查询消息时，首先检查该消息的关键字是否落在叶子节点集范围内。如果是，则直接把消息转发给对应的节点，也就是叶子节点集中nodeId和关键字最接近的节点。如果关键字没有落在叶子节点集范围内，节点就会把消息转发给路由表中的一个节点，该节点的nodeId和关键字的相同前缀至少要比当前节点的nodeId和关键字的相同前缀长一个数位。如果路由表中相应的表项为空，或者表项中对应的节点不可达，这时候查询消息将被转发给前缀长度相同但是节点号数值更接近关键字的节点。除非消息已经到达目的节点，否则这样的节点一定位于叶子节点集中。而且，只要叶子节点集中一半以上的节点不同时失效，就一定可以找到满足要求的节点。很明显，路由的每一步都比上一步向目标节点前进了一步，因此路由过程总是收敛的。
节点加入和退出
新节点加入时需要初始化自身的状态表，并通知其他节点自己已经加入系统。假定新加入节点的nodeId为X，同时假定X在加入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系统中，如果节点检测出其邻居节点集中的某个节点失效，它将请求其他邻居节点把其邻居节点集发送过来并从中选择一个新的邻居节点替换失效节点。
3 CAN
UC Berkeley提出的CAN（Content Addressable Network，内容寻址网络）实现了文件索引和存放位置的有效映射，不需要任何形式的中央控制点，节点只需要维护少量的控制状态而且状态数量独立于系统中的节点数量，具有完全自组织和分布式的结构，并且有良好的可扩展性和容错性。
CAN的设计
CAN的设计基于虚拟的d维笛卡儿坐标空间，这个坐标空间完全是逻辑的，和任何物理坐标系统都没有关系。在任何时候，整个坐标空间动态地分配给系统中的所有节点，每个节点负责维护独立的互不相交的一块区域。CAN中的节点自组织成一个代表这个虚拟坐标空间的重叠网络（overlay network）。每个节点要了解并维护相邻区域中节点的IP地址,用这些邻居信息构成自身的坐标路由表。有了这张表，CAN可以在坐标空间中任意两点间进行寻路。
下图给出了一个2维的[0, 1]×[0, 1]的笛卡儿坐标空间划分成五个节点区域的情况。虚拟坐标空间采用下面的方法保存（K, V）对。当保存（K1, V1）时，使用统一的哈希函数把关键字K1映射成坐标空间中的点P。那么这个值将被保存在该点所在区域的节点中。当需要查询关键字K1对应的值时，任何节点都可以使用同样的哈希函数找到K1对应的点P，然后从该点对应的节点取出相应的值V1。如果此节点不是发起查询请求的节点，CAN将负责将此查询请求转发到P所在区域的节点上。因此，有效的路由机制是CAN中的一个关键问题。

                          五个节点维护的CAN虚平面
CAN的路由
CAN中的路由很简单，沿着坐标空间中从发起请求的点到目的点之间的一条路径转发即可。为此，每个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空间要分配给系统中现有的全部节点，当一个新的节点加入网络时必须得到自己的一块坐标空间。CAN通过分割现有的节点区域实现这一过程。它把某个现有节点的区域分裂成同样大小的两块，自己保留其中的一块而另一块分给新加入的节点。整个过程分为以下三步：
1. 新节点首先找到一个已经在CAN中的节点。
2. 新节点使用CAN的路由机制找到一个区域将要被分割的节点。
3. 执行分割操作，然后原有区域的邻接区域必须被告知发生了分割，这样新节点才能被别的节点路由到。
当节点离开CAN时，必须保证它的区域被系统中剩余的节点接管，也即分配给其他仍然在系统中的节点。一般是由某个邻居节点来接管这个区域和所有的索引数据（K，V）对。如果某个邻居节点负责的区域可以和离开节点负责的区域合并形成一个大的区域，那么将由这个邻居节点执行合并操作。否则，该区域将交给其邻居节点中区域最小的节点负责。也就是说，这个节点将临时负责两个区域。
正常情况下，每个节点向其所有邻居节点发送周期性的更新消息，消息中包括自身的区域范围、它的邻居列表以及这些邻居节点负责的区域范围。如果多次没有接收到某个邻居的更新消息，那么节点就认为这个邻居失效了。这时，节点将启动接管机制，并启动一个时钟。失效节点的每个邻居节点相互独立地执行该过程，每个时钟大小都和相应节点负责的区域面积成比例。如果时钟超时，节点将向失效节点的所有邻居节点发送接管消息，该消息中包括它自己的区域面积信息。当某个节点接收到接管消息后，如果它的区域面积比发出消息的节点大，那么它将取消接管操作。否则它将发出自己的取代消息。采用这种机制可以有效地选择面积最小的邻居节点来接管失效节点。在特殊情况下，还有可能出现多个相邻的节点同时失效的情况。例如，节点检测到某个节点失效，但是失效节点地邻居中超过一半可能都不可达。这时，如果让该节点接管失效节点地区域，就有可能导致CAN中状态不一致。所以在这种情况下，CAN在执行修复操作之前，会搜索失效区域附近的节点，搜索逐步扩大直至获得足够的邻居状态，以便安全地开始接管过程。
4 Tapestry
Tapestry是UC Berkeley提出的一种新型的P2P网络定位和路由算法。该算法可以对消息进行与位置无关的路由，把查询消息传递到最近的存储有目标对象拷贝的节点。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位的数字），所有的节点依据标识符自组织成一个重叠网络。
Tapestry动态地把每个标识符G映射到当前系统中一个节点上，该节点称为G的根节点，表示为GR。如果某节点的Nid＝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开头，即和本节点标识具有相同的一个数位的前缀。
Tapestry采用的基本查找和路由机制：当一条查找消息到达传递过程中的第n个节点时，该节点和目的节点的共同前缀长度至少大于n。为了进行转发，该节点将查找邻居映射表的第n+1级中和目的标识符下一数位相匹配的邻居节点。转发过程将在每个节点中依次进行直到到达目的节点。这种方法可以保证路由至多经过logbN个节点就可以到达目的节点，这里N是节点标识符名字空间的大小，而b是标识符使用的基数。同样，由于每个节点的邻居映射表的每个级别只需要保存b个表项，因此，邻居映射表的空间为blogbN。 [...]