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個
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表過一遍，更新某些後繼節點。
<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+19y94cC0y7WjrMjnyc/NvKOsTmu1xLzTyOvWu7vh07DP7MbkuvO8zL3ateNOeLXEx7C8zL3atePRodTxo6y8sE54tcTHsLzMvdq14055tcS687zMvdq149Gh1PGjrLy01eLI/bj2vdq149auvOS1xLulz+DWuMjPv8nE3LvhseS7r6GjPC9wPgo8cD61q8ewzOHKx054us1OebHY0OvKx9fuvdO9/E5rtcTWsb3Tx7C8zLrN1rG907rzvMyho8jn09Ky4M281tDU2k55x7DD5qOsu+Gyu7vh09BOerj8vdO9/E5ro6y2+NOmuMPKx05rtcS687zMxNijv7TwsLjKx7fxtqi1xKGjtNPUrcDtvce2yL+0o6xDaG9yZMvjt6ixo9akwcvV4rz+ysKjqEZpbmdlcrHtus3Wsb3Tx7AvuvO8zLXEtqjS5dPQ0ru2qLXEzNjK4tDUo6mho8Ht0ru3vcPmo6zG5Mq1yc/D5rXEzbzW0LXETjC92rXjv8nE3LKisrvKx7Sm1NrEx7j2zrvWw6GjzqrBy7Dv1vrA7b3io6zPwsPmz+rPuMu1w/e1sU4w1Npqb2lu1eKyvc6qTmu12tK7tM7V0rrzvMy1xLn9s8yhozwvcD4KPHA+PGJyPgo8L3A+CjxwPjwvcD4KPHA+1Nq12tK7tM7RodTxTni1xMqxuvKjrMrHzai5/U4wtcRmaW5kU3VjY2Vzc29yKGtleSnV0rXEKLy0Mi4xsr3W6Nf2tcTKwimhozwvcD4KPHA+uPi2qNK7uPZrZXnOu9bDo6yy6dXSc3VjY2Vzc29yo7o8L3A+CjxwPjEuICAgIMXQts9rZXnOu9bDyse38dTasb692rXjus2xvr3ateO687zMvdq149auvOSjrMjnufvKx6OsxMfDtL7NsNGxvr3ateO1xLrzvMy92rXjt7W72KGjt/HU8r34yOsyoaM8L3A+CjxwPjIuICAgIM6quMNrZXnV0rG+vdq149fuvfy1xMewvMy92rXjKLK70ru2qMrHsb692rXjtcTWsb3TuvO8zL3ateMpo6zA+9PDsb692rXjx7C8zL3ateO1xGZpbmRTdWNjZXNzb3K3vbeowLTV0rjDa2V5tcS687zMvdq146OsvLS9+Mjrtd256aOsu9i1vTGhozwvcD4KPHA+0qrXotLitcTKx9XS1+69/LXEx7C8zL3atePV4tK7sr2jrNLAwLW1xMrHsb692rXjtcRmaW5nZXKx7aOssLRmaW5nZXKx7bW50PLV0qOs1dK1vcTHuPa92rXjwvrX42Zpbmdlcr3atePU2sS/seprZXnOu9bDus2xvr3atePWrrzko6y+zW9roaM8L3A+CjxwPrTT1rG528nPwO294qOsZmluZ2Vyse3A77XEtbnQ8rXa0ru49rXjvuDA67G+vdq147XEvuDA69futuDKx7DruPa7t6OsvLQyPHN1cD5tLTE8L3N1cD6jrLW50PK12rb+uPa1xL7gwOvKxzI8c3VwPm0tMTwvc3VwPiYjNDM7MjxzdXA+bS0yPC9zdXA+oaPSsr7NysfLtaOs1eLW1rW50PLV0srHuty087e2zqe1xNXSo6zS1NXi1ta3vcq91dK1vb3atePU2bX308NmaW5kU3VjY2Vzc29yt723qNXSa2V5tcS687zMo6y/ydLUxNSyudK7z8LV4tbWyai7t7XEt73KvaGjo6jOqrDv1vrA7b3io6y7rcHL0ru49rH9o6k8L3A+CjxpbWcgc3JjPQ=="http://www.2cto.com/uploadfile/Collfiles/20140530/20140530091608232.jpg" alt="\">
所以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網絡進行的操作列表：
CreateNode，創建多個節點Insert，插入數據到local網絡裡InsertNetwork，插入數據到remote網絡裡CrashNodes，消滅local網絡裡的若干個節點JoinNetwork，加入節點到remote網絡裡LeaveNetwork，離開remote網絡Remove，從local網絡裡刪除數據RemoveNetwork，從remote網絡裡刪除數據Retrieve，從local網絡裡獲取數據RetrieveNetwork，從remote網絡裡獲取數據ShowEntries，展示local網絡裡每個node的entryShowEntriesNetwork，展示remote網絡裡每個node的entryShowFingerTable，展示local網絡裡指定node的finger tableShowFingerTableNetwork，展示remote網絡裡指定node的finger tableShowNodes，展示local網絡裡所有nodesShowSuccessorList，展示local網絡裡指定node的後繼列表ShutdownNodes，關閉一系列nodesWait，阻塞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表。
