【Chord算法介绍】

Chrod算法是P2P中的四大算法之中的一个，是有MIT（麻省理工学院）于2001年提出，其它三大算法各自是：CAN，Pastry，Tapestry

 

1、Chord是什么？

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

Chord还能够被作为一个一致性哈希、分布式哈希（DHT）的实现。

 

2、覆盖网络（overlaynetwork）

覆盖网络是指这样一种网络：构建在其它网络之上、网络节点之间通过虚拟或逻辑连接在一起，比方云计算、分布式系统都是覆盖网络，由于其都构建于TCP/IP之上，且节点之间有联系。Chord也是构建于覆盖网络。

 

3、结构化与非结构化网络

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

 

 

结构化的P2P网络与非结构化恰好相反，我们觉得网络在逻辑上存在一个人为设计的结构，比方Chord假定网络是一个环，Kadelima则假定为一颗二叉树，全部的节点均为树的叶子节点。有了这些逻辑结构，就给我们资源查找引入了很多其它的算法和思路。

 

4、分布式哈希表（DHT）

DHT的主要想法是把网络上资源的存取像Hashtable一样，能够简单而高速地进行put、get，该思想的诞生主要是受第一代P2P（Napster）网络的影响。与一致性哈希相比，DHT更强调的是资源的存取，而无论资源是否是一致性的。与一致性哈希同样的是，DHT也仅仅是一个概念，详细细节留给各实现。

 

5、Chord实现原理

Chord通过把Node和Key映射到同样的空间而保证一致性哈希，为了保证哈希的非反复性，Chord选择SHA-1作为哈希函数，SHA-1会产生一个2160的空间，每项为一个16字节（160bit）的大整数。我们能够觉得这些整数首尾相连形成一个环，称之为Chord环。整数在Chord环上按大小顺时针排列，Node（机器的IP地址和Port）与Key（资源标识）都被哈希到Chord环上，这样我们就假定了整个P2P网络的状态为一个虚拟的环，因此我们说Chord是结构化的P2P网络。

 

以下有几个定义：

我们称Chord环上的每一个节点为标志符

假设某个Node映射到了某个标志符，则继续称该标准符为Node

按顺时针，节点前面的成为前继(predecessor),节点后面的成为后继（successor)；同理，第一个predecessor称之为直接前继，第一个successor称之为直接后继