iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 25
0
Software Development

分散式系統 - 在分散的世界中保持一致系列 第 25

Day 25 - Data Partitioning - Distributed Hash Table and Consistent Hashing - CHORD(下)

前言

昨天介紹了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 jFinger 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的predecessorNode 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的基本介紹,包含了LookupNode加入
結合起來就可以成為一個提供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


上一篇
Day 24 - Data Partitioning - Distributed Hash Table and Consistent Hashing - CHORD(上)
下一篇
Day 26 - Data Partitioning - Distributed Hash Table and Consistent Hashing - Kademlia
系列文
分散式系統 - 在分散的世界中保持一致30

尚未有邦友留言

立即登入留言