Chord算法研究 LeeRinji

前言

我们需要一种能在P2P网络高速定位资源的的算法，一个很具有代表性的例子是BT下载的过程：在对等用户拿到种子文件的时候，首先会联系 tracker 服务器，然后加入用户集群，并在用户集群中寻找自己所需的内容，最后与拥有内容的对等用户进行联系。用户通常不关心资源是怎样存储的，因此实际上算法需要提供的的API就简单到仅有set、get。

在历史中有三种比较典型的模型来解决这个问题：

  • Napster：使用一个中心服务器接收所有的查询，服务器告知去哪下载其所需要的数据。存在的问题是中心服务器单点失效导致整个网络瘫痪。
  • Gnutella：使用消息洪泛（message flooding）来定位数据。一个消息被发到用户集群内每一个节点，直到找到其需要的数据为止。存在的问题是消息数与节点数成线性关系，导致网络负载较重。
  • SN 型：超级节点（Super Node），SN 保存网络中节点的索引信息，这一点和中心服务器类型一样，但是网内有多个 SN，其索引信息会在这些 SN 中进行传播，所以整个系统的崩溃几率就会小很多。尽管如此，网络还是有崩溃的可能。

Chord 算法是MIT（麻省理工学院）提出的一种基于 DHT（分布式哈希）技术的结构化 P2P 路由协议，具有完全分布式、负载均衡、可用性及可扩展性好、命名方式灵活等特点。本文主要对 Chord 算法展开分析。

简述

Chord是最简单、最精确的环形P2P模型。“Chord”这个单词在英文中是指“弦”，在分布式系统中指“带弦环”，在P2P领域则指基于带弦环拓扑结构的分布式散列表(DHT)或者构建与其上的P2P网络。尽管MIT和UC Berkeley的研究早在2001年之前就开发了Chord及其应用系统，但有关Chord的正式论文[Stoica et al.， 2001]发表在计算机通信领域著名会议ACM SIGCOMM’01 上，其它刊物和会议后来也有刊登Chord的论文的，如[Stoica et al.， 2003]。Chord是结构化的P2P领域最著名的理论模型，到2006年已经被引用超过3000次。能够说，凡是研究过P2P的人，没有不知道Chord的。

Chord是一个算法，也是一个协议。作为一个算法，Chord可以从数学的角度严格证明其正确性和收敛性；作为一个协议，Chord详细定义了每个环节的消息类型。当然，Chord之所以受追捧，还有一个主要原因就是Chord足够简单，千行左右的代码就足以实现一个完整的Chord。

Chord还可以被作为一个一致性哈希、分布式哈希的实现。Chord这样的DHT的实现。本质上是在一致性哈希的基础上，添加了Finger表这样的高速路由信息，通过在节点上保存整个网络的部分信息，让节点的查找/路由以$O(\log N)$的代价实现，适合大型p2p网络。

概念

覆盖网络

构建在其他网络之上、网络节点之间通过虚拟或逻辑连接在一起，比如云计算、分布式系统都是覆盖网络，因为其都构建于TCP/IP之上，且节点之间有联系。Chord也是构建于覆盖网络。

非结构化网络

非结构化的P2P网络是指网络节点之间不存在组织关系，节点之间完全是对等的，比如前面提到的第一代P2P网络Napster，这类网络结构清晰、简单，但查找没有多大的优化余地，经常采用全局或分区泛洪查找，查找时间长、且结果难以保证（有可能在找到前就超时）。

结构化网络

结构化的P2P网络与非结构化恰好相反，我们认为网络在逻辑上存在一个人为设计的结构，比如Chord假定网络是一个环。有了这些逻辑结构，就给我们资源查找引入了更多的算法和思路。

分布式哈希表（DHT）

DHT的主要想法是把网络上资源的存取像Hashtable一样，可以简单而快速地进行put、get，该思想的诞生主要是受第一代P2P（Napster）网络的影响。与一致性哈希相比，DHT更强调的是资源的存取，而不管资源是否是一致性的。

原理

几个定义

  1. Chord通过把Node和Key映射到相同的空间而保证一致性哈希，我们可以认为这些整数首尾相连形成一个环，称之为Chord环。
  2. 称Chord环上的每个节点为标志符
  3. 如果某个Node映射到了某个标志符，则继续称该标准符为Node
  4. 按顺时针，节点前面的成为前继(predecessor)，节点后面的成为后继（successor）。每个节点都维护一个predecessor和successor列表，该列表的作用是能快速定位前继和后继，并能周期性检测前继和后继的健康状态
  5. 第一个predecessor称之为直接前继，第一个successor称之为直接后继
  6. 每个节点都维护一个Finger表，该表长度为m（m就是位数，在Chord中为160），该表的第$i$项存放节点$n$的第$n+2i-1\pmod{2m}$个successor$(1\le i\le m)$。就是说存放的successor是按$2$的倍增，之所以取模是因为最后的节点的successor是开始的几个节点，比如最大的一个节点的下一个节点定义为第一个节点。
  7. 资源Key存储在下面的Node上：沿Chord环，$hash(Node)>=hash(key)$的第一个Node.称这个Node为这个Key的successor。

查找过程

整数在Chord环上按大小顺时针排列，Node（机器的IP地址和Port）与Key（资源标识）都被哈希到Chord环上，这样我们就假定了整个P2P网络的状态为一个虚拟的环，因此我们说Chord是结构化的P2P网络。

Chord选择SHA-1作为哈希函数，SHA-1会产生一个$2^{160}$的空间，每项为一个16字节（160bit）的大整数。很显然，分布在Chord环上的Node数远远小于标志符数（$2^{160}$和宇宙原子总数是一个级别），这样Chord环上的Node就会很稀疏地分布在Chord环上，理论上应该是随机分布。当然，如果节点数量不多，分布很难做到均匀，可以考虑增加虚拟节点来增加其平衡性。如果在节点较多（比如大型的P2P网络有上百万的机器）就不必引入虚拟节点。

我们在查询资源Key时，只要找到Key的直接前继即可，于是转化为一个在Chord环上通过Node找Node的模型。在Chord环上任意标记个点作为Node集合，任意指定查寻终点Node T，从任意的Node N开始根据Chord查找算法都能找到节点T。假如我们把查找的步骤记录为路径，则Chord算法其实就是构造了一条较短的路径。而这样的路径一定存在，因为Chord本身是一个环，是连通图。Chord只是用类似于路径倍增的方法对已存在线性路径的改进，我们完全可以设计出其他的路径压缩算法。然而，Chord算法的另外一个优点是，其可以用较为优秀的复杂度来维护每个节点的后继节点，而其他的算法则很难保证这一点。

给定一个Key，按下面的步骤查找其对应的资源位于哪个节点，也就是查找该Key的successor：（假如查找是在节点n上进行）

  1. 查看Key的哈希是否落在节点n和其直接successor之间，若是结束查找，n的successor即为所找
  2. 在n的Finger表中，找出与hash(Key)距离最近且<hash(Key)的n的successor，该节点也是Finger表中最接近Key的predecessor，把查找请求转发到该节点
  3. 继续上述过程，直至找到Key对应的节点

收敛性

假如节点$n$的Finger表中的第$i$个successor与$Key$的距离最近，则满足：$Key$处在第$i$项与第$i+1$项中间。

不妨记第$i$项为$J=n+2i-1$，第$i+1$项为$P=n+2i$，即$J<hash(Key)<P$。可以推出节点$n$与$Key$的距离应该处在$n$与$J$和$P$的中间，即$2i-1<n - hash(Key)<2i$。而$J$与$Key$的距离不超过J与P的距离，即$J-hash(Key)\le P - J = 2i-1$

也就是说$J$与$Key$的距离，小于n与Key的距离，并且该距离小于$n$与$Key$距离的一半，这样我们就证明了，每次迭代与$Key$的距离都会按$2$的指数收敛（即折半）。

实现

限于老师给的的时间所限，我没有自己实现这一算法，不过在Github上已经有很多Chord算法的实现。我在这里选择了一个相对较为不错的实现(见参考部分)作为演示。

编译

$ make
g++ main.o init.o functions.o port.o nodeInformation.o helperClass.o -o prog -lcrypto -lpthread

使用

编译生成的prog是可执行文件，详细的使用说明可以参照其README.md文档或运行时输入help指令.

$ ./prog
Now listening at port number 39629
Type help to know more
> help
1) create : will create a DHT ring

2) join <ip> <port> : will join ring by connecting to main node having ip and port

3) printstate : will print successor， predecessor， fingerTable and Successor list

4) print : will print all keys and values present in that node

5) port : will display port number on which node is listening

6) port <number> : will change port number to mentioned number if that port is free

7) put <key> <value> : will put key and value to the node it belongs to

8) get <key> : will get value of mentioned key

> create
> printstate
Self 127.0.0.1 39629 112849222518968
Succ 127.0.0.1 39629 112849222518968
Pred 127.0.0.1 39629 112849222518968
Finger[1] 112849222518968 127.0.0.1 39629
Finger[2] 112849222518968 127.0.0.1 39629
Finger[3] 112849222518968 127.0.0.1 39629
Finger[4] 112849222518968 127.0.0.1 39629
Finger[5] 112849222518968 127.0.0.1 39629
Finger[6] 112849222518968 127.0.0.1 39629
Finger[7] 112849222518968 127.0.0.1 39629
Finger[8] 112849222518968 127.0.0.1 39629
Finger[9] 112849222518968 127.0.0.1 39629
Finger[10] 112849222518968 127.0.0.1 39629
Finger[11] 112849222518968 127.0.0.1 39629
Finger[12] 112849222518968 127.0.0.1 39629
Finger[13] 112849222518968 127.0.0.1 39629
Finger[14] 112849222518968 127.0.0.1 39629
Finger[15] 112849222518968 127.0.0.1 39629
Finger[16] 112849222518968 127.0.0.1 39629
Finger[17] 112849222518968 127.0.0.1 39629
Finger[18] 112849222518968 127.0.0.1 39629
Finger[19] 112849222518968 127.0.0.1 39629
Finger[20] 112849222518968 127.0.0.1 39629
Finger[21] 112849222518968 127.0.0.1 39629
Finger[22] 112849222518968 127.0.0.1 39629
Finger[23] 112849222518968 127.0.0.1 39629
Finger[24] 112849222518968 127.0.0.1 39629
Finger[25] 112849222518968 127.0.0.1 39629
Finger[26] 112849222518968 127.0.0.1 39629
Finger[27] 112849222518968 127.0.0.1 39629
Finger[28] 112849222518968 127.0.0.1 39629
Finger[29] 112849222518968 127.0.0.1 39629
Finger[30] 112849222518968 127.0.0.1 39629
Finger[31] 112849222518968 127.0.0.1 39629
Finger[32] 112849222518968 127.0.0.1 39629
Finger[33] 112849222518968 127.0.0.1 39629
Finger[34] 112849222518968 127.0.0.1 39629
Finger[35] 112849222518968 127.0.0.1 39629
Finger[36] 112849222518968 127.0.0.1 39629
Finger[37] 112849222518968 127.0.0.1 39629
Finger[38] 112849222518968 127.0.0.1 39629
Finger[39] 112849222518968 127.0.0.1 39629
Finger[40] 112849222518968 127.0.0.1 39629
Finger[41] 112849222518968 127.0.0.1 39629
Finger[42] 112849222518968 127.0.0.1 39629
Finger[43] 112849222518968 127.0.0.1 39629
Finger[44] 112849222518968 127.0.0.1 39629
Finger[45] 112849222518968 127.0.0.1 39629
Finger[46] 112849222518968 127.0.0.1 39629
Finger[47] 112849222518968 127.0.0.1 39629
Finger[48] 112849222518968 127.0.0.1 39629
Successor[1] 112849222518968 127.0.0.1 39629
Successor[2] 112849222518968 127.0.0.1 39629
Successor[3] 112849222518968 127.0.0.1 39629
Successor[4] 112849222518968 127.0.0.1 39629
Successor[5] 112849222518968 127.0.0.1 39629
Successor[6] 112849222518968 127.0.0.1 39629
Successor[7] 112849222518968 127.0.0.1 39629
Successor[8] 112849222518968 127.0.0.1 39629
Successor[9] 112849222518968 127.0.0.1 39629
Successor[10] 112849222518968 127.0.0.1 39629
>

参考