iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 26
0
Software Development

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

Day 26 - Data Partitioning - Distributed Hash Table and Consistent Hashing - Kademlia

前言

前兩篇介紹的Distributed Hash Table的Hashing Space是對應到一個圓,今天我們要來介紹另一種對應到Tree Structure的演算法 - Kademlia

這個演算法也是廣為應用在P2P領域,如果你曾經用過Emule、BitTorrent (透露年紀) ,那麼他底層的Data Partitioning就是用Kademlia這個演算法。

Kademlia

CHORD一樣的是透過Hash Function將NodeID、Key對應到m-bit string,一般也是採SHA-1轉成160bits

但是Kademlia建立了一個Binary Tree,搭配0與1將每一個NodeID放在Tree的Leaf上。

如下圖所示:

  • 每一個Node儲存自己的NodeIP、NodePort
  • Data一樣放在距離最近的Node上,所以Node也會儲存自已手上有的(Key, Value)

CHORDㄧ樣,Kademlia也設計了一個自己Routing方法
先來看看什麼是 DistanceK-buckets

Distance - XOR

在這裡我們定義 Distance 就是兩個ID做XOR的結果

E.g.
NodeA = 2 = 0010
NodeB =14 = 1110
XOR(A,B) = 1100 = 12

我們定義這個 1100 = 12 就是他的Distance,我們等等會看到這個的意義

Neighbors - K-buckets

在Kademlia裡,每一個Node維護了K-buckets作為Routing Table

K-buckets 就是以 Distance 來做分層

  • Bucket i 裡面存 2^i ~ 2^(i+1)-1 距離範圍內的Nodes,i = 0~m-1 (m-bits)
  • K是一個可以調整的參數,表示每一個Bucket可以存多少個Neighbor Node資訊

E.g.

Bucket 0 存距離 0~1 之間範圍內的Nodes
Bucket 1 存距離 2~3 之間範圍內的Nodes
Bucket 2 存距離 4~7 之間範圍內的Nodes
...

直接看一個圖

對於Node 0010來說,Node 0000應該存在哪一個Bucket呢?

  • (Node 0010) XOR (Node 0000) = 0010 = 2

  • 應該放在放在k-bucket 1中因為距離是2~3之間,i=1

  • 而K就是每個Bucket可以存多少個Nodes

我們可以從另一個角度來看這個關係,其實他採用XOR就是在說明bits到第幾位開始不同

例如00110010是到最後一位才不同放在 Bucket0
例如0000/00010010是第二位開始不同,放在Bucket1
例如0100/0110/0101/01110010是第三位開始不同,放在Bucket2

他的Bucket距離區間( 2^i ~ 2^(i+1)-1 )從二進位來看就是第幾位開始不同

但是你會發現當i越大,比方說到Bucket159,他可能存的Node是在2^159 ~ 2^(160)-1之間,可能有超多Nodes,
所以才要用K-bucket,規定每個Bucket只能存K個,
距離越遠我可以用hops的方法去找去逼近到而不用全部記下來。

Lookup

直接從例子來看
假設 NodeID 0010 要尋找 NodeID 1110

核心思想就是每一次找都找最接近的

比方說 NodeID 1110 應該是要在 NodeID 0010 [8,15]這個區間的Bucket,但是不在裡面。
但是 NodeID 1110 一定跟其他已經記錄在NodeID 0010 [8,15]這個區間的Neighbors Nodes比較近
因此先從[8,15]開始找

  1. NodeID 0010 XOR NodeID 1110 = 12 在 [8,15]區間

  2. 因為在自己的Bucket裡面沒有記錄NodeID 1110,因此發送訊息詢問有記錄的Nodes,比方說Node 1000Node 1010。一次詢問多少人也是可調參數,這邊假設可以從Bucket挑出最多2人詢問。

  3. 因此 NodeID 0010 -> Node 1000Node 1010 詢找NodeID 1110

  1. Node 1010 XOR NodeID 1110 發現 NodeID 1110 應該要在自己的 [4,7]區間,發現沒記錄。於是從Bucket [4,7]區間再挑出2人詢問

  2. Node 1010 -> Node 1100Node 1101 詢找NodeID 1110

  1. Node 1101 XOR NodeID 1110 發現 NodeID 1110 應該要在自己的 [2,3]區間,且的確有記錄他的資訊,因此回傳找到

小結

你可以發現尋找的過程中,他是不斷的一次跳到距離目標節點最近的Bucket裡面的 Neighbor Nodes 去詢問。
而他的換個角度看會發現,這個概念是一個bit一個bit去逼近target。

因為採用SHA-1 Hash成2進位表示,所以每次前進一個bit都可以視為除一次2(更正後)。

因此尋找的複雜度就像二分搜尋法那樣,為O(lgN)。

是一個很精妙的設計

Reference


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

尚未有邦友留言

立即登入留言