Chord加密算法

2022-10-28

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网络中找到存有特定数据的节点。