Chord算法是DHT(Distributed Hash Table)的一种经典实现，以下从网上无节操盗了一段介绍性文字：

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看成一个分布式散列表，那么它只支持结构化P2P最简单的功能：将节点和数据对象映射到覆盖网中。Chord基于安全的一致性散列函数来分配节点ID和对象ID。在一个有N个节点的网路中，每个Chord节点保存O(logN)个其他节点的信息，查询数据对象需要的覆盖网络的路由跳数也是O(logN)，当节点离开或者加入网络时，为了维持网络结构，保持自适应性所需要的的消息数在O(log2N)。作为分布式的散列表，Chord具有几乎最优的路由效率，确定性的对象查询，负载均衡，高可扩展性以及良好的容错性与自适应性；但最重要的一点是：Chord简单，优美，这是它最为经典的直接原因。

Chord的开源实现主要有两个，一个是单机版的jchord，另一个是集群形式的open chord项目。以下描述都是参考开源项目代码展开的。

在单个线程里，Chord环类似是一个内存数据结构。Chord环的节点上可以存储数据，也可以起服务，这取决于你利用Chord来做什么。以下的实现主要侧重于新建Chord环，并可以增加节点，在增加节点的过程中，按照Chord的算法描述，怎么样影响相关节点，怎么维护Finger表内容。

首先，Chord类维护ChordNode的一个List，createNode方法根据nodeId创建一个新的ChordNode，为其生成好NodeKey，为所有的ChordNode排好序（TreeMap）。

ChordNode表示环上的节点，包含这些元素：

nodeId, ChordKey,successor, predecessor和 FingerTable。

根据nodeId在生成ChordKey，即环上的位置，然后赋予后继和前继（顺时针方向为向后）。

FingerTable维护的是m个，m为所选hash函数的hash值位数（比如选择SHA1，m等于hash位数160，即hash环最大值为2160-1），index为key+2i，i取0, 1, … ,m-1。对于小型p2p网络来说，m的取值还是比较大的，导致节点的finger表冗余度可能会有90%以上（可能前50个值都指向N1，后100个都指向N2，最后的10个指向N5），不过这部分冗余倒不会对查找/路由性能带来什么明显影响。

FingerTable可以形象理解为，以本节点出发，将整个环切为m份，切的方式是按2的等比增长切，即1，2，4，8，…，2159，每个index值为finger表里的一条记录的key，选择该index值为起点顺时针最近的后继节点作为该finger项的value。如此的话，每个环上的节点都维护了一张全局的二分节点路由表。

然后，在建立新的Chord哈希环的时候，

1. 生成Chord，并创建若干个节点。每个节点在创建的时候，都相当于以自身为第一个节点创建了环。

2. 把创建好的节点逐个加入到某个节点的环上，加入过程只会影响某几个节点

     2.1 在指定的节点N0上join新节点Nk。join过程是借助已有节点N0的finger表为新的节点Nk找到后继Nsuc =N0.findSuccessor(Nk.key)，此时Nk的前继为null

     2.2  确认新节点Nk与后继节点Nsuc的相互关系。需要注意的是，这个确认过程指的是待确认节点的后继是不是现在的后继，以及，后继节点的前继

             会不会因待确认节点的加入而更新。

             因为可能后继节点Nsuc和新节点Nk之间还有节点Nbet，则需要更新Nk的后继节点为Nbet，且后继节点Nsuc和原前继之间加入了Nk之后，

             原前继的后继要改变。

     2.3  确认刚刚的后继节点Nsuc的原前继节点Npre =Nsuc.getPre()的后继节点。因后继节点Nsuc的原前继节点Npre可能会因为新节点Nk的加入

             而改变其后继节点。

            2.2和2.3都是确认过程，只是基于的点不一样，可以体会一下，思路是一样的。

3. 刷新每个节点的finger表。该过程可以理解为，在各个节点都更新了各自的前继和后继节点之后，每个节点再把自己的finger表过一遍，更新某些后继节点。

总结来说，如上图，Nk的加入只会影响其后继节点Nx的前继节点选择，及Nx的前继节点Ny的后继节点选择，即这三个节点之间的互相指认可能会变化。

但前提是Nx和Ny必须是最接近Nk的直接前继和直接后继。如右侧图中在Ny前面，会不会有Nz更接近Nk，而应该是Nk的后继呢？答案是否定的。从原理角度看，Chord算法保证了这件事（Finger表和直接前/后继的定义有一定的特殊性）。另一方面，其实上面的图中的N0节点可能并不是处在那个位置。为了帮助理解，下面详细说明当N0在join这步为Nk第一次找后继的过程。

在第一次选择Nx的时候，是通过N0的findSuccessor(key)找的(即2.1步骤做的事)。

给定一个key位置，查找successor：

1.    判断key位置是否在本节点和本节点后继节点之间，如果是，那么就把本节点的后继节点返回。否则进入2。

2.    为该key找本节点最近的前继节点(不一定是本节点的直接后继节点)，利用本节点前继节点的findSuccessor方法来找该key的后继节点，即进入递归，回到1。

要注意的是找最近的前继节点这一步，依赖的是本节点的finger表，按finger表倒序找，找到那个节点满足finger节点在目标key位置和本节点之间，就ok。

从直观上理解，finger表里的倒序第一个点距离本节点的距离最多是半个环，即2m-1，倒序第二个的距离是2m-1+2m-2。也就是说，这种倒序找是很大范围的找，以这种方式找到节点再调用findSuccessor方法找key的后继，可以脑补一下这种扫环的方式。（为帮助理解，画了一个饼）

所以N0第一次帮Nk找的后继Nx，以及Nx本身的前驱Ny，它们这四个点之间的位置关系，其实出现情况很复杂，不一定像我上面画的那样分布，我画的图甚至可能是错的，比例也完全不是那样的。如何证明Nz的不存在性，相信在了解Chord数学原理后应该可以比较好地理解。

上述描述了Chord环的生成过程和新增节点详细实现。

集群版指节点之间可能是存在于local的一个JVM内的Chord网络，也可以是存在于多个JVM之间的remote的Chord网络。

如果是Remote情况下的话，对比上述实现，节点的join步骤会增加节点之间通信环节，整体实现思路是一致的，只是集群形式要处理的内容会更丰富些。

针对通信这点，Open chord提供chord node之间的几种通信协议：Local的话是在单个JVM内；Remote的话包括rmi和socket。

Open chord还提供了在每个节点上允许存储序列化后的java对象，实际上是在Chord算法基础上对节点的一种利用，在此不展开。

ChordImpl包含元素：

NodeImpl(localNode)，Entries，线程池，HashFunction，References，URL，ID

NodeImpl代表着Chord环上的节点，具备一些可以被远程节点调用的操作；

Entries是数据K,V对；

References里包括了一个前继，一串后继和数据Entries；

URL和ID是localNode的url和id；

findSuccessor(key)过程：

首先检查本节点有没有后继，如果没有，说明是唯一的环上的点，返回本节点就可以了。

然后检查key是不是在本节点和后继之间，如果是的话，返回后继节点。在这一步里，本来在返回后继之前，会进行一次ping来检查后继是否正常存活，不过这段被注释掉了。弥补的做法是返回后继过程中如果出异常，就认为后继节点联系不上，那么把它从reference表里删除，隐式效果就是后继list里会有新的后继节点占据list首位，所以继续递归findSuccessor(key)操作。

如果以上情况都不是，那么就找一个最接近该key的前继节点，调用那个节点的findSuccessor(key)递归查找，和单线程版里的实现是一致的。这个查找最接近该key的前继节点的过程具体是Refereces类的getClosestPrecedingNode(key)方法，不会检测存活性，是个同步方法，这个方法逻辑比较复杂。

多个create方法，最终使用createHelp()，作用是创建一个新的ring，前提是localURL和localID都已经设置好了。

create的过程是，把entries（存数据），references（引用node），localNode（为了通信）都初始化出来，然后调用createTasks操作，createTasks操作利用线程池，定时执行三种任务，分别是周期性稳固与后继的关系（StabilizeTask）、周期性更新finger表（FixFingerTask）、周期性检测前继节点健康情况（CheckPredecessorTask）。最后，调用localNode的acceptEntries方法接收其他node传来的处理entries的通信操作。

周期性稳固与后继的关系（StabilizeTask）：

检测后继节点的前继节点有没有因为本节点发送变化。在单线程实现版本里，这个很好了解，但是open chord里的实现没怎么看明白。

周期性更新finger表（FixFingerTask）：

采用生成随机数的方式，随机检测一个值对应的successor，如果这个节点不在references内部维护的内容（finger表或前继或后继列表）里，则增加该节点的引用

周期性检测前继节点健康情况（CheckPredecessorTask）：

从References里得到前继，不为空的话则进行一次ping操作。Ping其实什么也没做，但能返回不出异常的话，说明节点正常存活着。

多个join方法，最终调用joinHelp(bootstrapURL)方法，用于把本ChordNode加入到指定的URL的Chord ring里。前提是localURL和localID都已经设置好了。

join的过程是，把entries（存数据），references（引用node），localNode（为了通信）都初始化出来，然后通过Proxy.createConnection(localUrl,bootstrapUrl)来连接本节点和目标URL，Proxy类用于代表本节点外的其他nodes，有LocalThread，RMI，Socket三种实现，对应的是不同的通信协议。

连接完后返回一个远程node，然后调用远程node的findSuccessor方法找到本节点的后继。

然后调用远程node的notifyAndCopyEntries把它的前继、后继列表和entries引用都取过来，利用这个ref集合，首先建立本节点的前驱，即如果ref大小是1，那么说明ring里就两个node，那么后继也是本节点的前继；如果ref大于1，那么取出第一个节点，即后继的原前继，比较本节点是否在他俩之间，如果是的话，本节点的前继就是后继的原前继，否则后继节点是错误的，把ref里的第一个节点作为后继，调用notifyAndCopyEntries，循环上述步骤找出本节点的正确前继。这个过程中，会不断往references里添加节点，也解释了为什么reference里存的是一个后继list。

确定完前继和后继后，把entries的引用添加为本节点的entries，最后执行本节点的acceptEntries和createTasks方法（同create的最后两步）。

leave操作，关闭本节点线程池，并通知前继和后继，本节点要离开网络。然后让localNode断开连接，赋null。

Insert(key,data)，按照key的hash值在环上找到对应node，让node把这个序列化后的data和key以Entry的形式存起来。调用的是node的insertEntry方法。找node过程调用的是本节点的findSuccessor(key)方法。

Retrieve(key)，按照key的hash值在环上找到对应node，调用node的retrieveEntries方法得到一个entry的Set返回。找node过程调用的是本节点的findSuccessor(key)方法。

Remove(key,data)，按照key的hash值在环上找到对应node，调用的是node的removeEntry方法。找node过程调用的是本节点的findSuccessor(key)方法。

以上三种操作还配有异步方法，具体不展开。

把Chord放到集群环境里之后，除了对节点进行join来加入已有网络外，许多其他操作都会涉及类似的若干次通信，包括移除节点，展示节点Finger表等操作。

这些操作的实现，通过上述描述的新增节点，实现上应该很好理解。下面列举了open chord的命令行提供的对local或remote chord网络进行的操作列表：

local/单JVM下创建环例子：

下面简单总结我对Chord的理解。

Chord这种DHT的实现，本质上是在一致性哈希的基础上，增加了Finger表这种快速路由信息，通过在节点上保存整个网络的部分信息，让节点的查找/路由以O(logN)的代价实现，适合大型p2p网络。所以，我理解的Chord基本就等于一致性哈希+Finger表。