Chord算法研究 wu-kan

前言

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

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

  • 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
>

参考