前言

昨天介紹了CHORD的兩種Lookup方法，
一個是不斷往下一個Successor詢問，
一個是利用儲存空間也就是Finger Table換取時間，以取對數的方法將時間複雜度降到O(lgN)。

今天我們將要介紹CHORD如何處理Nodes的加入與刪除，
重新分配會影響到的O(K/N)個(Key, Data)。

這邊小補充一下，
正因為每次有Nodes加入或是刪除除了會影響到Key重新分配外，
Finger Table也會受到影響，
而這個就必須對有影響的Node進行調整，會花上更多時間，
但是不幸的是，P2P網路上Node的加入移除是很頻繁的。

因此論文建議不需要頻繁的每次都更新Finger Table，
可以適度的選擇用Basic CHORD詢問Successors的方法，
Finger Table不需要是最新的也沒關係。

CHORD

Node 加入

主要分成了三個步驟

1. 建立新加入的Node的所有Finger Table Entries
2. 更新現有的Node的Finger Table
3. 將受影響到Key，重新分配他們到新加入的Node

回想下圖，N4的新加入

步驟一: 建立Finger Table

假設新加入的Node經過 Hash Function(SHA-1) 後是在 j的位置。

則

1. 先隨機挑一個Node n
2. 利用Node n尋找 j+2^0, j+2^1, ..., j+2^m-1 m個ID與對應的nodes
3. 將那些資訊建立成Node j的Finger Table

等於連上一個Node n 做m次Lookup
尋找j+2^0, j+2^1, ..., j+2^m-1 這幾個ID

步驟二: 更新現有的Node的Finger Table

Node j 的加入迫使有些舊有的 Node 之Finger Table
一部分的entries的ID必須重新應對指到 Node j 上

有哪些Node的Finger Table會受到影響呢？
答案就是
[pred(j)-2^i+1, j-2^i] i = 0~m-1 這些區間的Nodes都需要調整

用圖像說明:

舉例來說:
m = 6
j = 28，j的predecessor為Node 21

則區間為 [21-2^i+1, 28-2^i] i = 0~5

E.g.
i = 4: [21-2^4+1, 28-2^4] = [21-15, 28-16] = [6,12]

Node 8在這個區間內，
他的Finger Table裡面一定有entries的會落在N21-N32之間，在N28加入後必須重新指向N28，就需要調整。

而總共要調整的Node有 O(log N)

步驟三: 將受影響到Key，重新分配他們到新加入的Node

1. 延續上圖N21先聯絡原本的Successor也就是N32
2. 將N32裡面現在必須指向N28的Key全部copy到N28來
3. 然後N21將自己的Successor改為N28

如下圖:

以上就是Node新加入後的處理，而移除也是幾乎一樣的步驟，只是反過來做。

總結

以上就是CHORD的基本介紹，包含了Lookup與Node加入。
結合起來就可以成為一個提供DHT做Data Partitioning的Library供更上層的應用使用，比方說P2P、分散式儲存Ceph、Openstack Ceph等

Reference:
更完整詳細的介紹: https://www.cnblogs.com/gnuhpc/archive/2012/01/13/2321476.html
論文: https://pdos.csail.mit.edu/papers/chord:sigcomm01/chord_sigcomm.pdf
原始碼: https://github.com/sit/dht/tree/master/chord