Chord加密算法就是一种分割文件索引表的方法,它把这张文件索引分割成小块,每一块存放在某几个节点上。当要查询数据时,再通过一定的方式,连接某几个节点上的部分索引表,查找存放存放目标(KV)对索引表的节点,从而获取存放文件的节点地址。

Chord加密算法的实现

Chord协议运行的基础是一致性哈希函数,它把P2P网络中的每一个节点映射为一个哈希值。

Chord协议中的网络节点,都有惟一的一个160比特的节点标识,它是相应节点的IP地址及相关信息通过哈希函数得到。Chord协议把这些节点标识看作是一个圆形的命名空间,每一个节点在逻辑上有且仅有一个圆形的命名空间,每一个节点在逻辑上有且仅有一个前驱和后继。查询关键字的哈希值也映射到这个命名空间上。关键字j的后继(successor)定义如下,如果节点j存在,节点j就是关键字J的后继;否则它的后继是命名空间中比节点j大的第一个节点。在Chord协议中,最基本的操作是查找一个关键字的后继。

在这个网络中有3个节点,假设它们的标示为0,1,3。假设还有3个资源集合,它们的关键字通过哈希函数后的标识为1,2,6。它们的索引分别存储在各自的后继节点上,由于标示为1的节点存在,所以关键字1存放在节点1上;同理,关键字2和6分别存储在它们的后继节点3和0上。

Chord加密算法模型中,即使网络在动态变化时,只须改变少量的数据结构,就可以维护整体网络的一致性。当一个节点n离开时,原本在n上的索引对将转移到n的后继节点上:而当一个节点n加入时,原本n的后继节点上的索引对的一部分转移到n上。如上图中,如果节点3离开后,关键字2的索引将放在节点0上。

每个节点都维护一部分路由表,称为节点的Finger表。节点的Finger表共有log2n项(n为命名空间的大小),其中第i项存放着距离该节点长度为2f+1(0≤f≤0(log2n)的节点的后继信息。例如上图中,由于节点空间大小为8,每个节点维护3条路信息。节点0维护标示为1,2,4的后继节点信息。

节点的Finger表,以冗余的形式存储了所有资源的索引信息。另外,为了维护网络的动态性带来的变化,每个节点还冗余存放相邻节点的Finger表信息,这些节点被定义为该节点的邻居。

Chord加密算法的性能分析

Chord加密算法中,几乎所有的操作都是通过查找关键字K的后继完成的。当一个节点n不知道关键字K的后继时,它会在自己的Finge表中,查找一个比关键字K的后继小但是最接近的一个中间节点。它把查询消息传递给中间结点,这一过程被递归调用直到查询消息到达目标节点。

一般而言,查询过程在圆形命名空间上顺时针进行,每一次查询排出剩余的一半节点,所以hord加密算法是收敛的,查询的最大长度是0(log2n)。当一个节点n加入时,n通过查询距离自己2f+1(0≤f≤0(log2n)处的关键词初始化自己的Finge表,因此初始化一个节点的代价是0(log2n)。为了及时反映网络节点的变化,每个节点都定时发送查询更新自己的Finge表,这个过程被称之为节点的稳定化。

Chord加密算法的优点

虽然Chord加密算法的设计思想简单,但是有以下几个优势:

1、负载平衡

这一优点来自于一致性哈希,也就是一致性哈希中提到的平衡性。所有的节点以同等的概率分担系统负荷,从而可以避免某些节点负载过大的情况。

2、分布性

Chord是纯分布式系统,节点之间完全平等并完成同样的工作。这使得Chord具有很高的鲁棒性,可以抵御DoS攻击。

3、可扩展性

Chord协议的开销随着系统规模(结点总数N)的增加而按照O(logN)的比例增加。因此Chord可以用于大规模的系统。

4、可用性

Chord协议要求节点根据网络的变化动态的更新查询表,因此能够及时恢复路由关系,使得查询可以可靠地进行。

5、命名的灵活性

Chord并未限制查询内容的结构,因此应用层可以灵活的将内容映射到键值空间而不受协议的限制。

Chord加密算法的缺点

在Chord加密算法中,节点标识的分配是随机并且一致地,在关键字空间中,标识很接近的节点在物理网络上可能相聚很远。在数据的查询过程中,Chord加密算法采用跳数判断查询的代价,没有考虑网络延迟等因素,在逻辑上的最优路径花费的代价并非最优。在Chord网络稳定化的过程中,过多的消息发送占用了网络的带宽,影响网络的利用率。

Chord加密算法是国内外最新的研究热点,目前已取得一系列重要的成果,而且在实际工程中也得到广泛的应用。但Chord加密算法在语义查询、网络稳定性和安全方面还有待进一步研究。

小知识之Chord协议

Chord在2001年由麻省理工学院提出,其核心思想就是要解决在P2P应用中遇到的基本问题:如何在P2P网络中找到存有特定数据的节点。