Understanding Chord

http://blog.csdn.net/sparkliang/article/details/5679926
P2P（peer-to-peer）系统面临的一个根本问题就是如何有效的定位到存储特定数据项的节点。

本文提出了Chord，一个分布式查询协议来解决这个问题。Chord专为一种操作提供支持：给定一个key，它将key映射到对应的节点上。基于Chord，通过把key和每个data item（数据项）关联起来，并把该key/data item对存储到key映射到的节点上，很容易就可以实现数据定位。Chord可以有效的适应节点加入、离开系统，并且可以在系统持续变动的状态下应答查询。

实际上Chord协议仅支持一种操作：把一个给定的key映射到一个节点（node）上。 依据基于Chord协议的应用而定，目标节点可能负责存储关联到key的一组数据。Chord使用了一致性hash算法[11]（consistent hashing）的变体把Chord网络中的节点关联到特定而唯一的key上。一致性hash算法可以解决负载平衡（load balance）问题，因为它能保证系统中的每个节点都能接收到数量相当的key，并且当节点加入、离开系统时，减少数据的迁移。【译注：实际上一致性hash算法可以保证：当节点离开时，仅需要迁移离开节点上的数据；当节点加入时，仅将加入节点的后继节点的部分数据迁移到新节点上；而不涉及到其它的节点和数据，这在理论上已经是最小化的数据迁移了】

在以前对一致性hash算法的研究中，都假设每个节点都关注系统中的大多数节点，因此难以扩展应用到有很多节点的大规模系统中。相反，在Chord系统中，节点仅需要路由信息（routing information），关注少数其它节点。因为路由表是分布式的，一个节点执行查询时，需要和少数的其它节点通讯，稳定状态下，在一个有N个节点的系统中，每个节点仅需要维护O(logN)的节点信息，并且执行查询时仅需要和其它节点交互O(logN)的信息。当有节点加入、离开系统时，为了维护路由信息，Chord保证系统中节点之间的交互消息不会超过O(logN*logN)个。

Chord简单有效，将key传递到目的节点仅需要路由O(logN)个节点。为了实现有效的路由，每个节点仅需要维护系统中O(logN)个节点的信息，并且在路由信息过期时，性能会优雅降级。这在实际中是很重要的，因为节点会随意的加入、离开系统，很难维持在O(logN) 的事件状态一致性。Chord协议中，每个节点仅有部分数据正确就能保证查询路由的正确性（尽管会变慢）。Chord具有简单的算法，能在动态的环境中维护路由信息。

3 系统模型

通过处理下面的这些难题，Chord简化了P2P系统和应用的设计：
负载均衡（Load balance） ：Chord像一个分布式hash函数，最终将key散布在所有的节点上，这就在一定程度上提供了的天然的负载均衡能力。
去中心化（Decentralization） ：Chord是完全分布式的，没有哪个节点是更重要的，这增强了健壮性，并使得Chord适合于松散组织的P2P应用。
可扩展性（Scalability） ：Chord查询的复杂度随着节点数目N的log级别而增加（注：即O(logN)），因此适合应用在大规模系统中，并且不需要调整参数来达到这种可扩展性。
可用性（Availability） ：Chord会自动调整内部表来反映新近加入节点和节点失效的情况，确保除了底层网络的严重失效外，负责key的节点总是可以查询到。这甚至在系统处于一个持续改变的状态时也是正确的。
灵活的命名规则（Flexible naming） ：Chord对于要查找的key的结构没有施加任何的限制：Chord的key空间是扁平的（flat）。这就给应用程序与极大的灵活性来决定如何将他们自己的名字映射到Chord的key空间中。
Chord软件采取library的方式与使用它的客户端和服务端程序连接。应用程序和Chord主要在两个方面交互。1 Chord提供一个lookup(key)算法，返回负责key（存储key以及与key关联的数据）的节点的IP地址（注：即节点必要的信息）。2 每个节点上的Chord通知应用程序该节点所负责的key的变动。这允许应用程序执行一些操作，例如，在一个新节点加入时移动相应的数据到新节点上。

下面就是一些Chord可以提供良好基础的应用例子：
时间共享存储（Time-Shared Storage） ，用于断续连接的节点。如果希望一些数据总是可用的，但是他们的机器只能是偶尔可用，那么当机器可用时，他们可以相互存储其它人的数据，反过来，他们的数据也存储在了另外的机器上【译注：这样当他们的机器不可用时，也可以从其它活动的机器上取得数据】。数据的名字可以用作key，在任何时候定位负责存储的（活动的）Chord节点。这里有很多问题和协同镜像应用是相同的，尽管这里的焦点是可用性而不是负载均衡。

4 基础Chord协议

4.1 概述

Chord的核心就是提供了一个hash函数的快速的分布式计算，该hash函数把key映射到负责key的节点。Chord使用了一致性hash算法[11, 13]，它具有几个很好的性质。该hash函数能在很大概率上实现平衡负载（所有的节点接收到大概相同数量的key）。并且在很大概率上，当一个节点加入（或离开）网络时，仅有一小部分key会被移动到另外的位置——显然这是为了维持负载平衡所需的最小移动了。
通过避免让每个节点知道其它所有节点的信息，Chord提高了一致性hash算法的可扩展性。在Chord网络中，每个节点仅需要知道包含少量其它节点的路由信息（routing information）。因为这个路由信息是分布式的，一个节点需要通过和少数其它节点通信来解答hash函数【译注：完成hash查询】。在一个具有N个节点的网络中，每个节点只需要维持O(logN)的节点信息，并且一次查询只需要O(logN)的交互信息。
Chord必须在节点加入、离开网络时更新路由信息，一次加入或离开更新需要O(logN*logN)的交互信息量。

4.3 可扩展的key定位

少量的路由信息有助于在一个分布式的环境中实现一致性hash算法。每个节点仅需关注它在环上的后继节点。一个给定标识符identifier的查询可以在环上沿着后继进行，直到第一次遇到identifier的后继，它就是要查询的节点。Chord协议维护了这些后继指针，以保证能正确的解决每次查询。然而，这种解决方法是低效的：它可能需要遍历所有的节点来找到合适的映射。为了加速查找，Chord还维护了额外的路由信息，这些额外的信息并非为了正确性，当然只要后继的信息是正确的，它们的正确性就能得到保证。
和前面一样，设key和节点的标识符都是m-bit的。每个节点维护一个有m项（最多）的路由表，又称为finger table。节点n的第i个表项存储了节点s，并且s是在标识符环上距离n至少为2^(i-1)的第一个节点，即s=successor(n+2^(i-1)，其中1<= i <=m（所有的计算都基于模2^m）。我们称s为n的第i个finger，并标记为n.finger_t[i].node（见表1）【译注：为了不至于混淆finger和finger table，本文将原文中代表finger table的变量finger都改为finger_t】。finger table中的项包括相应节点的IP和端口信息。注意到节点n的第一个finger就是n在环上的后继，方便起见，我们经常称它为后继（successor）而不是第一个finger。

【译注：根据定义，Finger table中的第一个finger，即第一个大于等于finger_t[1].start的节点，就是节点n的后继，n.successor = n.finger_t[1].node】
该模式有两个重要的性质：第一，每个节点只需存储少量的其它节点信息，并且在标识符环上，它知道的距离较近的节点比较远的节点更多；第二，一个节点的finger table通常并不包括足够的信息来确定任意key的后继。比如图3中的节点3并不知道标识符1的后继，因为1的后继（节点1）并不在节点3的finger table中。
如果一个节点n不知道key k的后继，它会怎么做呢？如果n能够找到一个标识符比自己更接近k的节点t，t将会比n知道更多的k区域的信息【译注：上面的性质1】。因此n查找它的finger table找一个标识符在k前面并且最接近k的节点j，并问j它知道谁的标识符更接近k。通过重复这个过程，n就会知道越来越接近k的节点。

图3 (a)节点1的finger区间 (b)节点0,1,3和key1,2,6，finger table和key位置

// 委托节点n查找id的后继

n.find_successor(id)

   n’ = find_predecessor(id); // n的本地调用

   return n’.successor; // RPC查询得到的n’的后继

// 委托节点n查找id的前驱

n.find_predecessor(id)

   n’ = n;

   // 这里查找的是前驱，id不能在n’中，因此区间是前开后闭

   while(id NOT IN (n’, n’.successor]) // n’.successor由RPC查询得到

       n' = n’. closed_preceding_finger(id); // n’上的RPC

   return n’;

// 返回节点n的最接近id且在id之前的finger，都是本地调用

n.closed_preceding_finger(id)

   for i=m down to 1 // 从最大区间开始，每次迭代1/2递减

      if(finger_t[i].node IN (n, id)) then // 落在区间内则找到

         return finger_t[i].node;

   return n;