Chord：一个用于互联网应用的可扩展的P2P查询服务

Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications
《Chord：一个用于互联网应用的可扩展的P2P查询服务》

目录
1主要观点和解决的问题 2
2关键技术 2
2.1简介 2
2.2相关工作 2
2.3系统模型 3
2.4The Base Chord Protocol 4
2.5并行操作和故障 7
2.6 Simulation and Experimental Results 9
3 论文的主要贡献 10
4思考 11


1主要观点和解决的问题
P2P应用的基本问题是如何定位存有特定数据的节点，Chord是解决该问题的一种分布式查找协议。Chord能够提供仅对于单个操作的支持：提供一个Key，这个Key可映射到这个节点。这样，在Chord的上层，数据的位置就很容易通过关联每个数据项的一个Key来实现。并且在节点存储key/data 项目对，以便于key的映射。
此外即使在节点加入和离开频繁的变化的系统里，chord也能很好的调节。作者通过理论分析、模拟、实验来展现Chord的可扩展性，低代价。
2关键技术
2.1简介
P2P的优点有：系统内的节点是平等的关系，冗余存储、认证、性能、选择最近的服务节点、分层命名等。但其缺点也同样明显，P2P的核心的操作是寻找特定数据的节点的位置，因此本文的主要贡献在于如何在一个动态变化的P2P系统内精确的定位每一个含有特定数据的节点。
Chord直接利用key-node的操作，利用一致性哈希进行彼此的映射关系。一致性哈希可以保证每个节点拥有独立的key值，而且在节点离开和加入时只需要对key值做很小的移动。
在Chord中，每个Chord节点需要关于其他节点的“路由信息”，在一个N个节点的系统中，每个节点只需要维护O(log N)个节点的路由信息。离开和加入的信息交换不会超过O(log )。
Chord区别于其他的peer-to-peer查询协议有三个特点：简单性，可证明正确性，可证明的表现性。
2.2相关工作
在P2P流行的今天，与Chord协议相关的工作主要有：
(1)DNS:该协议反应的是IP-主机的对应，而Chord不需要特定的主机；
(2)Freenet P2P storage system：该协议具有自动调节节点的加入和离开的功能；
(3)Ohaha系统：该协议具有与Chord类似的hash算法；
(4)Globe 系统：类似于DNS的一种协议系统。
此外还有Plaxton、CAN等。
2.3系统模型
Chord简化了peer-to-peer系统的设计和实现，是基于解决以下的几个问题：
负载均衡：Chord以分布式哈希函数的行为在每个节点上平均散布keys，这可以提供一定程度的自然负载平衡。
分散化：Chord是一个完全分布式的。没有节点比其他的节点更重要。这提高了健壮性，也使Chord 更适于松散组织性的peer-to-peer的应用。
可扩展性：Chord查询的花费是随着日志中的节点数目而增长的，所以大的系统也是行得通的。实现这一比例不需要调整参数。
有效性：Chord自动地调整它的内在的表，去反映新加入的节点和错误的节点，确保禁止在基础网络上的主要错误，节点负责一个key能够被找到。
灵活的命名：在体系中Chord对于所查询的keys的放置是没有限制的。Chord的key-space是平坦的。这提供大量的灵活的应用，对于映射自己的名字倒Chord key。
Chord软件采用C/S结构，提供IP-key的密钥算法，同时在节点变动的情况下的key值对应问题。提供了认证、缓存、复制、友好命名等，可以轻易对对key值进行加密处理，应用程序可以通过keys值进行数据传输。
以下是Chord可提供的一些基础功能：
(1)合作镜像:类似于SVN的东西，可用于版本控制；
(2)时间共享存储：可将数据先存在他人的服务器上，以后进行读取，强调可用性，而不是负载均衡。
(3)分布式索引：可以搜索符合关键字的机器的集合，类似于模糊查询。
(4)大型组合搜索：加密密钥进行key到机器的映射。
图1指出了Chord软件的三层架构，文件系统提供灵活的命名，Block Store提供对Block存储、缓存、复制的操作。

2.4The Base Chord Protocol
Chord解决的问题：如何寻找keys对应的定位，新节点如何加入系统，如何在离开的节点中恢复。但是这节介绍的模型并不能解决并发的加入和离开问题，第五章才会解决这个问题。
2.4.1概述
Chord协议的核心是，Chord提供快速分布式哈希函数计算，映射keys到节点。协议使用的连续哈希函数,连续哈希有几个很好的特性。高概率的散列函数平衡负载。同时，高概率的是当第N个节点加入（离开）网络，只需要O(1/N)的keys的小部分被移动到不一样的位置——这显然是最起码的需要去维持一个平衡的负载。
Chord通过对每个节点知道每个其他节点的需求的避免来提高了连续哈希的扩展性。在一个N个节点的网络，每个节点对其他节点维持的信息只是大概O( log N)，一个查询需要O( log N)的信息。
Chord必须在一个节点加入或者离开网络时更新路由信息，一个加入或者离开需要O( log 2 N)的信息。
2.4.2一致性哈希
连续哈希函数制定每个节点和Key为一个m-bit identifier，使用基本哈希函数。节点的标识符是由哈希散列法对节点的IP地址选择，而一个key标识符是由哈希散列法产生。标识符长度m，必须足够大，对于相同标识符可忽略在两个节点或keys产生可能的哈希散列。
连续哈希对节点分配keys：标识符排列在一个模2m的标识环。Keys的k被指定第一个节点的标识符，它等价于标识符k，或者接着标识符k在标识符空间内。那么这个节点被称为key k的successor node（继承节点），这里面记为successor(k)，如果标识符代表着从0到2m-1的一个环状，则successor(k)是从k开始的顺时针的第一个节点。
图2所示的为标识符环的m=3。这个环有三节点0、1、3。继承标识符1的是节点1，所以key1就位于节点1。同理，key2 就位于节点3，key6位于节点0。连续哈希目的是让节点以最小的中断进入和离开网络。

2.4.3可扩展的关键位置
在Chord协议中每个节点只需要知道它在环上的的后继节点。查询一个给定的标识符可以通过整环传送继任者指针，直到指针首先相遇一个继承标识符的节点，这就是查询所要映射的节点。部分的Chord协议在保持这些继承指针，从而确保所有查找正确解析。但是这个决策计划不够高效。表现在：它可能需要遍历所有的N个节点去找到合适的映射关系。为了改进这个问题，Chord维护了额外的路由信息。所维护的额外信息的正确性不重要，它只要完成维护继承信息的正确。
作者给出了包括Chord标识符和IP地址相关的节点。此外作者还给出了公式s=success（n+2k-1）mod 2m ，其中s是.Start的数，n是节点数，k是1到m，m是第n个节点维持路由表的最大的项目个数。
如表1所示：

这个规划有两个重要的特点。第一是每个节点存储只有一个小数目节点的信息，并且知道在标识符环上紧跟着的更多节点，而不是那些很远的节点。第二是一个节点finger table一般不会包括足够信息去决定继承的任意一个key值k。
如图示，节点1的finger table指向继承节点的标识符是分别是（1+20）mod 23 = 2，（1+21）mod 23 = 3，（1+22）mod 23 = 5。继承的标识符2的是节点3，所以这接着2的第一个节点，继承标识符3的是节点3。

在这部分的实验结果报告，作者研究并证明平均的查找时间是1/2 logN。
2.4.4加入节点
在一个动态的网络，节点能够在任何时间加入和离开。在实现这些操作在网络中的主要挑战是保持每个key的位置的能力。为了达到则会给目标，Chord需要维持两个不变量。
1.每个节点的继承是正确的维持。
2.对于每个key的k，节点的successor（k）对k负责。
为了更快的查找， finger table正确也是可取的。为了简化加入和离开机制，在Chord的每个节点维持一个predecessor pointer。一个节点的predecessor pointer包含节点的最近的前身的Chord标识符和IP地址，并且能沿着标识符环反时针方向前行。
作者对与这个证明，提出了当一个节点n加入网络时，Chord必须要执行三个任务。第一是初始化的前任和节点的finger为n。第二是更新已存在节点的finger和前身考虑增加节点n。第三是通知高层的软件便于高层能转换相关的节点n的负责的keys的状态。作者给出了三部分的实现方法和步骤。
2.5并行操作和故障
这部分作者在实践中Chord需要处理的节点加入系统同时，节点出现故障或自动离开。通过对前面所给出基本Chord算法的修改来处理这些情况。
(1)Stabilization 稳定
一个稳定的协议最基本的保持节点的前缀点的更新，确保正确和可查找。在加入节点影响Chord节点前，有关稳定的三种行为时：
常见情况是，查找的finger表是合理的。第二种亲光是后缀是正确的，但是finger是错误的，导致查询变慢。第三种情况是影响节点的后缀，或者新加入的节点密钥还没有导入，从而导致查找失败。
我们稳定的保证方式是通过对现有的节点的可达性，即使是在面对并发连接和信息丢失和重新排序的情况下。
图7显示了加入和稳定的伪代码。是对图6算法的更新。

图7所示，显示了加入和稳定的伪代码。当节点n第一个开始，它就叫做 n.join(n′)，这个n′是任何已知的Chord节点。其中join 函数请求n′去寻找n直接继承。而join本身不会让剩下的网络知道n。
每个节点都周期性的运行stabilize算法。当一个节点n运行stabilize，它向继承的前任p询问n的继承，并决定p是否是n的继承的代替。Stabilize同时通知节点n的存在的你的继承，给与继承机会去改变他对n的前任。这个继承做这个仅仅当它知道没有比n更近的前任。作者对于这个给出了简单的例子。
一般来说，由于所花费的时间来调整fingers的时间是少于在网络规模扩大一
倍的时间，查找应继续采取为O(logN)跳。
(2) Failures and Replication 错误和复制
当一个节点n失败，包含n节点的finger表必须发现n的继承。另外，n的错误绝不允许扰乱使系统重达稳定过程的询问。
在错误回复的关键步骤是保持正确继承指针，从find_predecessor（只要继承指针正确的前任的称谓）能够是的进展只试用继承这个最坏的情况后。为了有助于完成这个步骤，每个Chord节点在Chord环上保持者一个它自己最近继承的success-list。
一个节点失败后，但在稳定未达到之前，其他节点可试图发送通过失败的节
点作为find-succseeor的部分来请求查找。
2.6 Simulation and Experimental Results
作者通过模拟评估Chord协议。该模拟器使用查找算法是文章第四部分的，使用的稳定算法是文章第五部分的。还报告了一些初步的实验结果来源于在互联网主机上运行即将可用的Chord为基础的系统。
2.6.1 Protocol Simulator
在Chord协议可以实现在一个迭代或递归类型。在迭代类型里，一个节点为解决一个查找开始了所有通信：它为信息从他们finger table询问一些列的节点，每次在Chord环移动到较近的想得到的继承。在递归类型里，每个中间节点转发一个请求到下一个节点，直到它到达了继承。该模拟器在一个迭代式类型实现协议。
2.6.2 Load Balance
首先考虑连续哈希散列对制定keys到节点的平均的能力。在一个有N个节点和K个keys的网络里，会分配keys到节点成为很紧密的N/K。
作者考虑的一个含有104个节点的网络，keys的总数在105到106个，是以105增加的。给出了20分钟的实验评估图。

从图(a)看出每个节点的keys数目表现出随着keys数目的线性增加数量很大
变化。这些变化的一个理由是节点标识符不会均匀地覆盖到标识符空间的每个项目上。作者认为连续哈希散列解决这个问题是通过把keys和虚拟节点联系起来，映射多个虚拟节点到每个真是节点。直观感觉，这将产生对所有标识符空间更统一的覆盖。作者对这个假设给出了相关证明，并认为增加虚拟节点在一个间接层可以显着提高负载平衡。作者认为这种增加可以很容易地在实践中居住。
2.6.3 Path Length
任何路由协议的性能在很大程度上取决于对任意两个节点之间的路径长度在网络。在Chord环境下，我们定义的数路径长度是在对查找操作过程中的大量节点的遍历。


正如所料，平均路径长度随着节点数量对数增加，显示了路径长度约为1/2 log2 N。图10（b）是对于具有212节点（k= 12）网络的路径长度PDF（The probability density function）。
3 论文的主要贡献
P2P 应用面临的一个基本问题是有效的定位那些存储有特定数据的节点。本文提出了“Chord”，一个解决该问题的分布式查找协议。Chord 为这样一个操作提供支持：给出一个key，chord将其映射到一个节点。基于Chord，只要把每个数据项与一个key关联起来，并把这一对key/data项存储在该key被映射到的节点上，数据定位问题就容易得到解决。Chord可以很好的适应节点加入和离开系统，在系统持续变化的时候可以应答查询。理论分析、仿真和实验结果表明Chord是scalable，每个节点的通信开销与维护的状态与Chord节点数目成对数关系。
Chord协议给出了一个有效的原型：给定一个key，它决定存储这个key的value的节点，并且运行很有效。在一个N个节点的稳定状态的网络中，每个节点仅维护到大约O(logN)个其他节点的路由信息。由于节点离开和加入引起的对路由信息的刷新仅需要O（log2N）个消息。
4思考
Chord的富有吸引力的特性包括它的简单性、在面临节点的并发加入和离开时也可证明的正确性和性能。当一个节点信息仅部分正确时，它可继续正确工作，虽然性能会有所下降。我们的理论分析、仿真和实验结果说明Chord随节点数目的增加是可扩展的，可以从大量并发节点失效和加入中恢复，在恢复过程中也可以正确响应大部分查询。
我们相信Chord将是大规模的分布式P2P应用的有价值的组成部分，这些应用诸如合作文件共享、time-shared available storage 系统、文档的分布式索引及服务发现和大规模分布式计算平台