post on 18 Jun 2019 about 6776words need 23min
CC BY 4.0 (除特别声明或转载文章外)
如果这篇博客帮助到你,可以请我喝一杯咖啡~
我们需要一种能在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表这样的高速路由信息,通过在节点上保存整个网络的部分信息,让节点的查找/路由以的代价实现,适合大型p2p网络。
构建在其他网络之上、网络节点之间通过虚拟或逻辑连接在一起,比如云计算、分布式系统都是覆盖网络,因为其都构建于TCP/IP之上,且节点之间有联系。Chord也是构建于覆盖网络。
非结构化的P2P网络是指网络节点之间不存在组织关系,节点之间完全是对等的,比如前面提到的第一代P2P网络Napster,这类网络结构清晰、简单,但查找没有多大的优化余地,经常采用全局或分区泛洪查找,查找时间长、且结果难以保证(有可能在找到前就超时)。
结构化的P2P网络与非结构化恰好相反,我们认为网络在逻辑上存在一个人为设计的结构,比如Chord假定网络是一个环。有了这些逻辑结构,就给我们资源查找引入了更多的算法和思路。
DHT的主要想法是把网络上资源的存取像Hashtable一样,可以简单而快速地进行put、get,该思想的诞生主要是受第一代P2P(Napster)网络的影响。与一致性哈希相比,DHT更强调的是资源的存取,而不管资源是否是一致性的。
整数在Chord环上按大小顺时针排列,Node(机器的IP地址和Port)与Key(资源标识)都被哈希到Chord环上,这样我们就假定了整个P2P网络的状态为一个虚拟的环,因此我们说Chord是结构化的P2P网络。
Chord选择
SHA-1
作为哈希函数,SHA-1
会产生一个的空间,每项为一个16字节(160bit)的大整数。很显然,分布在Chord环上的Node数远远小于标志符数(和宇宙原子总数是一个级别),这样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上进行)
假如节点的Finger表中的第个successor与的距离最近,则满足:处在第项与第项中间。
不妨记第项为,第项为,即。可以推出节点与的距离应该处在与和的中间,即。而与的距离不超过J与P的距离,即
也就是说与的距离,小于n与Key的距离,并且该距离小于与距离的一半,这样我们就证明了,每次迭代与的距离都会按的指数收敛(即折半)。
限于老师给的的时间所限,我没有自己实现这一算法,不过在Github上已经有很多Chord算法的实现。我在这里选择了一个相对较为不错的实现(见参考部分)作为演示。
1
2
$ make
g++ main.o init.o functions.o port.o nodeInformation.o helperClass.o -o prog -lcrypto -lpthread
编译生成的prog
是可执行文件,详细的使用说明可以参照其README.md
文档或运行时输入help
指令.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
$ ./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
>
Related posts