Chord算法實現詳細

背景

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算法原理介紹可以先了解下，本文側重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環最大值為2¹⁶⁰-1），index為key+2ⁱ，i取0, 1, … ,m-1。對於小型p2p網絡來說，m的取值還是比較大的，導致節點的finger表冗餘度可能會有90%以上（可能前50個值都指向N1，後100個都指向N2，最後的10個指向N5），不過這部分冗餘倒不會對查找/路由性能帶來什麼明顯影響。

FingerTable可以形象理解為，以本節點出發，將整個環切為m份，切的方式是按2的等比增長切，即1，2，4，8，…，2¹⁵⁹，每個index值為finger表裏的一條記錄的key，選擇該index值為起點順時針最近的後繼節點作為該finger項的value。如此的話，每個環上的節點都維護了一張全局的二分節點路由表。

然後，在建立新的Chord哈希環的時候，

1. 生成Chord，並創建若幹個節點。每個節點在創建的時候，都相當於以自身為第一個節點創建了環。

2. 把創建好的節點逐個加入到某個節點的環上，加入過程隻會影響某幾個節點

2.1 在指定的節點N₀上join新節點N_k。join過程是借助已有節點N₀的finger表為新的節點N_k找到後繼N_suc =N₀.findSuccessor(N_k.key)，此時N_k的前繼為null

2.2 確認新節點N_k與後繼節點N_suc的相互關係。需要注意的是，這個確認過程指的是待確認節點的後繼是不是現在的後繼，以及，後繼節點的前繼

會不會因待確認節點的加入而更新。

因為可能後繼節點N_suc和新節點N_k之間還有節點N_bet，則需要更新N_k的後繼節點為N_bet，且後繼節點N_suc和原前繼之間加入了N_k之後，

原前繼的後繼要改變。

2.3 確認剛剛的後繼節點N_suc的原前繼節點N_pre =N_suc.getPre()的後繼節點。因後繼節點N_suc的原前繼節點N_pre可能會因為新節點N_k的加入

而改變其後繼節點。

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表裏的倒序第一個點距離本節點的距離最多是半個環，即2^m-1，倒序第二個的距離是2^m-1+2^m-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表。

最後更新：2017-04-03 08:26:17