Chord加密算法就是一種分割文件索引表的方法，它把這張文件索引分割成小塊，每一塊存放在某幾個節(jié)點上。當(dāng)要查詢數(shù)據(jù)時，再通過一定的方式，連接某幾個節(jié)點上的部分索引表，查找存放存放目標(biāo)（KV）對索引表的節(jié)點，從而獲取存放文件的節(jié)點地址。

Chord加密算法的實現(xiàn)

Chord協(xié)議運行的基礎(chǔ)是一致性哈希函數(shù)，它把P2P網(wǎng)絡(luò)中的每一個節(jié)點映射為一個哈希值。

Chord協(xié)議中的網(wǎng)絡(luò)節(jié)點，都有惟一的一個160比特的節(jié)點標(biāo)識，它是相應(yīng)節(jié)點的IP地址及相關(guān)信息通過哈希函數(shù)得到。Chord協(xié)議把這些節(jié)點標(biāo)識看作是一個圓形的命名空間，每一個節(jié)點在邏輯上有且僅有一個圓形的命名空間，每一個節(jié)點在邏輯上有且僅有一個前驅(qū)和后繼。查詢關(guān)鍵字的哈希值也映射到這個命名空間上。關(guān)鍵字j的后繼（successor）定義如下，如果節(jié)點j存在，節(jié)點j就是關(guān)鍵字J的后繼；否則它的后繼是命名空間中比節(jié)點j大的第一個節(jié)點。在Chord協(xié)議中，最基本的操作是查找一個關(guān)鍵字的后繼。

在這個網(wǎng)絡(luò)中有3個節(jié)點，假設(shè)它們的標(biāo)示為0，1，3。假設(shè)還有3個資源集合，它們的關(guān)鍵字通過哈希函數(shù)后的標(biāo)識為1，2，6。它們的索引分別存儲在各自的后繼節(jié)點上，由于標(biāo)示為1的節(jié)點存在，所以關(guān)鍵字1存放在節(jié)點1上；同理，關(guān)鍵字2和6分別存儲在它們的后繼節(jié)點3和0上。

Chord加密算法模型中，即使網(wǎng)絡(luò)在動態(tài)變化時，只須改變少量的數(shù)據(jù)結(jié)構(gòu)，就可以維護整體網(wǎng)絡(luò)的一致性。當(dāng)一個節(jié)點n離開時，原本在n上的索引對將轉(zhuǎn)移到n的后繼節(jié)點上：而當(dāng)一個節(jié)點n加入時，原本n的后繼節(jié)點上的索引對的一部分轉(zhuǎn)移到n上。如上圖中，如果節(jié)點3離開后，關(guān)鍵字2的索引將放在節(jié)點0上。

每個節(jié)點都維護一部分路由表，稱為節(jié)點的Finger表。節(jié)點的Finger表共有l(wèi)og2n項（n為命名空間的大小），其中第i項存放著距離該節(jié)點長度為2f＋1（0≤f≤0（log2n）的節(jié)點的后繼信息。例如上圖中，由于節(jié)點空間大小為8，每個節(jié)點維護3條路信息。節(jié)點0維護標(biāo)示為1,2,4的后繼節(jié)點信息。

節(jié)點的Finger表，以冗余的形式存儲了所有資源的索引信息。另外，為了維護網(wǎng)絡(luò)的動態(tài)性帶來的變化，每個節(jié)點還冗余存放相鄰節(jié)點的Finger表信息，這些節(jié)點被定義為該節(jié)點的鄰居。

Chord加密算法的性能分析

Chord加密算法中，幾乎所有的操作都是通過查找關(guān)鍵字K的后繼完成的。當(dāng)一個節(jié)點n不知道關(guān)鍵字K的后繼時，它會在自己的Finge表中，查找一個比關(guān)鍵字K的后繼小但是最接近的一個中間節(jié)點。它把查詢消息傳遞給中間結(jié)點，這一過程被遞歸調(diào)用直到查詢消息到達目標(biāo)節(jié)點。

一般而言，查詢過程在圓形命名空間上順時針進行，每一次查詢排出剩余的一半節(jié)點，所以hord加密算法是收斂的，查詢的最大長度是0（log2n）。當(dāng)一個節(jié)點n加入時，n通過查詢距離自己2f＋1（0≤f≤0（log2n）處的關(guān)鍵詞初始化自己的Finge表，因此初始化一個節(jié)點的代價是0（log2n）。為了及時反映網(wǎng)絡(luò)節(jié)點的變化，每個節(jié)點都定時發(fā)送查詢更新自己的Finge表，這個過程被稱之為節(jié)點的穩(wěn)定化。

Chord加密算法的優(yōu)點

雖然Chord加密算法的設(shè)計思想簡單，但是有以下幾個優(yōu)勢：

1、負(fù)載平衡

這一優(yōu)點來自于一致性哈希，也就是一致性哈希中提到的平衡性。所有的節(jié)點以同等的概率分擔(dān)系統(tǒng)負(fù)荷，從而可以避免某些節(jié)點負(fù)載過大的情況。

2、分布性

Chord是純分布式系統(tǒng)，節(jié)點之間完全平等并完成同樣的工作。這使得Chord具有很高的魯棒性，可以抵御DoS攻擊。

3、可擴展性

Chord協(xié)議的開銷隨著系統(tǒng)規(guī)模(結(jié)點總數(shù)N)的增加而按照O(logN)的比例增加。因此Chord可以用于大規(guī)模的系統(tǒng)。

4、可用性

Chord協(xié)議要求節(jié)點根據(jù)網(wǎng)絡(luò)的變化動態(tài)的更新查詢表，因此能夠及時恢復(fù)路由關(guān)系，使得查詢可以可靠地進行。

5、命名的靈活性

Chord并未限制查詢內(nèi)容的結(jié)構(gòu)，因此應(yīng)用層可以靈活的將內(nèi)容映射到鍵值空間而不受協(xié)議的限制。

Chord加密算法的缺點

在Chord加密算法中，節(jié)點標(biāo)識的分配是隨機并且一致地，在關(guān)鍵字空間中，標(biāo)識很接近的節(jié)點在物理網(wǎng)絡(luò)上可能相聚很遠。在數(shù)據(jù)的查詢過程中，Chord加密算法采用跳數(shù)判斷查詢的代價，沒有考慮網(wǎng)絡(luò)延遲等因素，在邏輯上的最優(yōu)路徑花費的代價并非最優(yōu)。在Chord網(wǎng)絡(luò)穩(wěn)定化的過程中，過多的消息發(fā)送占用了網(wǎng)絡(luò)的帶寬，影響網(wǎng)絡(luò)的利用率。

Chord加密算法是國內(nèi)外最新的研究熱點，目前已取得一系列重要的成果，而且在實際工程中也得到廣泛的應(yīng)用。但Chord加密算法在語義查詢、網(wǎng)絡(luò)穩(wěn)定性和安全方面還有待進一步研究。

admin

收藏 海報分享