背景
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个<index, ChordNode>，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
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
多个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
多个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
leave操作，关闭本节点线程池，并通知前继和后继，本节点要离开网络。然后让localNode断开连接，赋null。
数据存取操作
insert
Insert(key,data)，按照key的hash值在环上找到对应node，让node把这个序列化后的data和key以Entry的形式存起来。调用的是node的insertEntry方法。找node过程调用的是本节点的findSuccessor(key)方法。
retrieve
Retrieve(key)，按照key的hash值在环上找到对应node，调用node的retrieveEntries方法得到一个entry的Set返回。找node过程调用的是本节点的findSuccessor(key)方法。
remove
Remove(key,data)，按照key的hash值在环上找到对应node，调用的是node的removeEntry方法。找node过程调用的是本节点的findSuccessor(key)方法。
以上三种操作还配有异步方法，具体不展开。
命令行操作
把Chord放到集群环境里之后，除了对节点进行join来加入已有网络外，许多其他操作都会涉及类似的若干次通信，包括移除节点，展示节点Finger表等操作。
这些操作的实现，通过上述描述的新增节点，实现上应该很好理解。下面列举了open chord的命令行提供的对local或remote chord网络进行的操作列表：
- CreateNode，创建多个节点
- Insert，插入数据到local网络里
- InsertNetwork，插入数据到remote网络里
- CrashNodes，消灭local网络里的若干个节点
- JoinNetwork，加入节点到remote网络里
- LeaveNetwork，离开remote网络
- Remove，从local网络里删除数据
- RemoveNetwork，从remote网络里删除数据
- Retrieve，从local网络里获取数据
- RetrieveNetwork，从remote网络里获取数据
- ShowEntries，展示local网络里每个node的entry
- ShowEntriesNetwork，展示remote网络里每个node的entry
- ShowFingerTable，展示local网络里指定node的finger table
- ShowFingerTableNetwork，展示remote网络里指定node的finger table
- ShowNodes，展示local网络里所有nodes
- ShowSuccessorList，展示local网络里指定node的后继列表
- ShutdownNodes，关闭一系列nodes
- Wait，阻塞console一段时间
local/单JVM下创建环例子：
oc > create -names n1
Creating new chord network.
oc > show
Node list in the order as nodes are located on chord ring:
Node n1 with id 65 52 9C 8C
oc > help
For help with any command, type name of command plus '-h' or '-help'.
Parameters of commands are always passed to them in the format '-parametername parametervalue'.
Some parameters require no value, so only the parameter name has to be provided to the command.
Commands available from this console:
-----
insert, retrieveN, insertN, refs, cprotocol,
executeMacro, removeN, refsN, entriesN, create,
entries, retrieve, successors, wait, shutdown,
crash, exit, help, joinN, displaySystemOut,
show, remove, leaveN
-----
Note: Commands and parameters are case sensitive.
oc > create -names n2_n3 -bootstraps n1
Starting node with name 'n2' with bootstrap node 'n1'
Starting node with name 'n3' with bootstrap node 'n1'
oc > show
Node list in the order as nodes are located on chord ring:
Node n1 with id 65 52 9C 8C
Node n2 with id 9B 1A 3A B3
Node n3 with id 9C 47 20 AB
oc > refs -node n1
Retrieving node n1
Node: 65 52 9C 8C , oclocal://n1/
Finger table:9B 1A 3A B3 , oclocal://n2/ (0-157)
Successor List:9B 1A 3A B3 , oclocal://n2/9C 47 20 AB , oclocal://n3/
Predecessor: 9C 47 20 AB , oclocal://n3/
oc > create -names n22_b1_o1p3_o2_ooi1_onf8_jiow_09ni_90j0_jfn_n23_j902n_j9_noi32_n9_j92 -bootstraps n2_n3
Starting node with name 'n22' with bootstrap node 'n2'
Starting node with name 'b1' with bootstrap node 'n3'
Starting node with name 'o1p3' with bootstrap node 'n3'
Starting node with name 'o2' with bootstrap node 'n3'
Starting node with name 'ooi1' with bootstrap node 'n3'
Starting node with name 'onf8' with bootstrap node 'n3'
Starting node with name 'jiow' with bootstrap node 'n3'
Starting node with name '09ni' with bootstrap node 'n3'
Starting node with name '90j0' with bootstrap node 'n3'
Starting node with name 'jfn' with bootstrap node 'n3'
Starting node with name 'n23' with bootstrap node 'n3'
Starting node with name 'j902n' with bootstrap node 'n3'
Starting node with name 'j9' with bootstrap node 'n3'
Starting node with name 'noi32' with bootstrap node 'n3'
Starting node with name 'n9' with bootstrap node 'n3'
Starting node with name 'j92' with bootstrap node 'n3'
oc > refs -node n1
Retrieving node n1
Node: 65 52 9C 8C , oclocal://n1/
Finger table:9B 1A 3A B3 , oclocal://n2/ (0-157)BB 5B 1A 3D , oclocal://j902n/ (158)E7 9D 67 6A , oclocal://n23/ (159)
Successor List:9B 1A 3A B3 , oclocal://n2/9C 47 20 AB , oclocal://n3/
Predecessor: 5D FC 4C 35 , oclocal://o1p3/
oc > refs -node n23
Retrieving node n23
Node: E7 9D 67 6A , oclocal://n23/
Finger table:F8 FE D0 C3 , oclocal://n22/ (0-156)0E AF 2E B7 , oclocal://09ni/ (157)2C F2 8A 7F , oclocal://ooi1/ (158)9B 1A 3A B3 , oclocal://n2/ (159)
Successor List:F8 FE D0 C3 , oclocal://n22/F9 19 F3 7F , oclocal://b1/
Predecessor: CE 4B 77 E3 , oclocal://jfn/
oc > joinN
Creating new chord overlay network!
URL of created chord node ocsocket://10.65.17.185/.总结
下面简单总结我对Chord的理解。
Chord这种DHT的实现，本质上是在一致性哈希的基础上，增加了Finger表这种快速路由信息，通过在节点上保存整个网络的部分信息，让节点的查找/路由以O(logN)的代价实现，适合大型p2p网络。所以，我理解的Chord基本就等于一致性哈希+Finger表。
