iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 24
0
Software Development

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

Day 24 - Data Partitioning - Distributed Hash Table and Consistent Hashing - CHORD(上)

前言

昨天提到說明了

  • DHT便是將傳統的Hash Bucket變成一個個實體的Node

  • Consistent Hashing是將Key與Node都一起Hash到同一個Hash Space,並將Data存到最近的Node裡面。

    • 最主要解決的就是 Monotonicity 特性
    • 加入與刪除一個Node並不需要重新分配所有的Data

舉例:

  • 將Key Hash到[0,1]內的一個值
  • 將Node Hash一樣到[0,1]內的一個值
  • 將Data存到往右邊看最近的Node

  • 也因此,當我們將一個新的Node N4加入,我們不需要重新分配Data,而是只需要更新[N2,N4]範圍內的Data會重新分配到N4中

以上就是 Consistent Hashing 的精神
但是目前這樣的做法有一個小問題,那就是對於[N3,1]之間的Data應該存在哪呢?

一種很直觀的方法就是將[0,1]區間變成一個 環狀

CHORD 演算法就是基於這樣的一個環狀Hash Space設計自己的Routing方法。

CHORD

簡介

CHORD是一個由MIT在2001年發表的一種DHT演算法。

作為一個Library,提供DHT給上層的 authenticationcachingreplicationnaming 等應用。
而CHORD的興起在於他非常簡單就可以實作。

開源網址在這裡: https://github.com/sit/dht/
裡面還包含了很多其餘相關的open source project,例如Merkle Tree

實作

Hash

基於 Consistent Hashing 的想法,

  • Hash Space為一個m-bit的ID-Space,串聯成一個環
  • 一般使用 SHA-1 作為Hash Function
  • SHA-1(IP address) 得到 NodeID
  • SHA-1(Key) 得到KeyID

如下圖所示,Keys與Nodes都會在同一個環上,我們將Data存入順時鐘方向最接近的Node上面。

幾個重點

  • 例如: K10的Data存入Node N14
  • Hash Function可以做到平均分散資料的儲存
    • 每一個Node儲存**O(K/N)**個Key
    • 因此當有Node的增加或是移除時,只需要移動**O(K/N)**個Keys

Lookup(Key)

1. Basic CHORD

每一個Node只會記錄兩個Neighbors

  1. 下一個Node => Successor
  2. 前一個Node => Predecessor

當一個Client連上某個Node希望找尋某個Data時,
若是該Node沒有該Data,便將請求傳遞給Successor

舉例:

上面的m=7,就是假設Hash出來的ID為一個7bits的ID
一般採用SHA-1會是 160its

此種方法的缺點也很直觀,就是Worst Case會繞整個環一圈
因此時間複雜度會是O(N)

有沒有方法可以改善呢?

2. CHORD with Finger Table

  • Define

我們改成每一個Node可以記錄m個Neighbors,形成一個Finger Table來做Lookup,

定義:
Finger i 指向 n+2^i i=0~m-1 共m個點,
而n是目前的Node

如下圖舉例:

對於Node n12來說,其Finger Table定義如下
m=7, n=12

Finger i ID 該ID對應到的Node
i=0 12+2^0=13 N32
i=1 12+2^1=14 N32
i=2 12+2^2=16 N32
i=3 12+2^3=20 N32
i=4 12+2^4=28 N32
i=5 12+2^5=44 N60
i=6 12+2^6=76 N80
  • Lookup 方法

當Node記錄了上面的Finger Table,在搜尋目標Data時,就可以將原本的O(N)降為O(lgN)。

如下圖

  1. Client連上Node N12要尋找Key Hash出來為100的Data
  2. N12沒有,因此從他認識的Neighbors問起
  3. 透過Finger Table知道,最接近ID=100的,為自己記錄的ID=76對應的Node N80
  4. 因此N12->N80將請求傳遞給N80
  5. N80也沒有,但是透過Finger Table知道ID=100的資料跟自己有記錄的ID=99很接近,應該都是屬於Node N110的
  6. N80->N110將請求傳遞給N110,而N110回應有Data
  7. 一路傳回來後Client就知道要連上Node N110來下載資料

這樣的Routing法可以將複雜度降到O(lgN)

為什麼呢?以下粗淺不專業的類比一下
從ID用m-bit表示
Finger Table記錄的m個Node是每次增加2^i
你可以發現他每次都會嘗試找最接近的,而且是以2的次方在接近
就變成與二分搜的概念一樣
當然也就是O(lgN)
這個幾乎也是所有DHT演算法降時間複雜度的手段

小結

以上就是DHT CHORD的Lookup介紹,明天會來介紹CHORD如何處理Data Partitioning與DHT的另外一個難題,也就是新增與刪除一個Node,如何重新分配那O(K/N)的Node。

Reference:

  • TU Dresde System Engineering I&II - P2P Network

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

尚未有邦友留言

立即登入留言