天天看點

Chord算法實作詳細背景單線程版叢集版總結

是的一種經典實作,以下從網上無節操盜了一段介紹性文字:

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的開源實作主要有兩個,一個是單機版的,另一個是叢集形式的。以下描述都是參考開源項目代碼展開的。

在單個線程裡,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表過一遍,更新某些後繼節點。

Chord算法實作詳細背景單線程版叢集版總結

總結來說,如上圖,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的後繼,可以腦補一下這種掃環的方式。(為幫助了解,畫了一個餅)

Chord算法實作詳細背景單線程版叢集版總結

是以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算法基礎上對節點的一種利用,在此不展開。

把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一段時間

也就是說,叢集環境下,對Chord的操作會以指令行的方式,操作節點、擷取節點資訊,從實作原理上,類似上述那樣的實作步驟。

下面簡單總結我對Chord的了解。Chord這種DHT的實作,本質上是在一緻性哈希的基礎上,增加了Finger表這種快速路由資訊,通過在節點上儲存整個網絡的部分資訊,讓節點的查找/路由以O(logN)的代價實作,适合大型p2p網絡。是以,我了解的Chord基本就等于一緻性哈希+Finger表。

繼續閱讀