iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 23
0

前言

前面都是在聊資料做備份放到replca servers後的各種資料一致性。

分散式系統還有另一個大主題,那就是如何分散資料到各個Node上。
這個需求最早出現在P2P的應用上,P2P網路一般是沒有Leader的,
原因也很簡單

  1. Single bottleneck
  2. Single point failure

也因此使用者想要下載的資料可能存在系統中的某個Node上,必須有一個方法找到該Node,並從他身上下載資料。

最簡單的方法就是使用廣播,但是效率可想而知很差,
因此最好在一開始就用某種規則將Data與Node做某種配對。

這樣當我要找某個特定資料時可以很快連線到該Node,或是連線到一個知道目標Node在哪的中繼Node。

Distributed Hash Table

Distributed Hash Table 的提出是1997年的MIT
《Consistent Hashing and Random Trees:Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》

想法:

  • 解決將「特定的Data」儲存(映射)到「特定的Node」
  • 當想要找尋資料的時候,可以找到該節點或是相連的中繼節點

從Hash Table到Distributed Hash Table(DHT)

看到上面的想法一定可以很快反應,這其實就是Hash Table嘛~

利用一個Hash TableHash Function負責映射Key與Data至Hash Bucket中。

  • Key經過Hash Function後算出Bucket位置,再將Data存進去。
  • 之後透過相同的Key可以在O(1)內得出Bucket位置。

而DHT的概念便是將上述的Bucket實體化成我們的Cache Node或是Storage Node。

  • Key經過Hash Function後算出Data應該存進哪個Node。
  • 因此流量請求與Data可以被分散至不同的Node上。

DHT 4個 Criterias

在論文裡面針對設計出來的DHT演算法,提供了四個指標

  1. Balance: Hash的結果要能夠讓Data平均分散到不同的Node上。這在很多的Hash Function都可以做到

  2. Monotonicity:

    1. 在初始化將Data經過Hash儲存到各個Node A、B、C 中的 A 後,
    2. 一個新的Node D 的加入,要嘛Data被重新Hash到原本的 NodeA 中或是新的 NodeD 中,不會被分配到B或是C。
  3. Spread: 因為是分散式的環境,Client對於目前全局的Node個數可能不是正確的,不同的Client得到的Node資訊可能不ㄧ樣。因此當Client要藉由DHT將Data儲存到節點上,可能會發生同樣的Data被儲存到不同的Node上。Spread就是這個情況的嚴重程度。

  4. Load: 換個角度說上面Spread情況可能也會導致,一個結點A被兩個Client1&2儲存了不同的Data1&2,但是其實Data1&2應該是要在兩個不同的Node上,只因為Client得到的Node資訊錯誤。這會導致節點A的Load增高,因為想要Data1&2的人都會去找他。

Consistent Hashing

另一個會面臨的問題就是如何處理,
當增加一個Node或是移除一個Node時,能夠保持Hash FunctionMonotonicity特性。

如果用傳統的Hash Function例如 mod Bucket個數,則多一個Bucket或是少一個,每一個Key的Hash都會改變。

h(k) mod m 
≠ h(k) mod (m+1) 
≠ h(k) mod (m-1)

解法就是利用Consistent Hashing

  • 定義一個Hash空間
  • 所有Key Hash出來的值都會落在此空間,且算法與Bucket個數(節點個數)無關
  • 將Node也進行Hash,因此Node也落在此Hash空間
  • 將Key對應的Data存在Hash Space裡面最靠近的Node。
    (節點與Key在同一個Hash Space)

Neighbors

每一個Bucket是一個Node
一組Nodes形成了一組分散式儲存。

在此P2P網路中,ClientA可能連上任何一個NodeA。
當Client要找DataC時,連上的那個NodeA要能夠幫ClientA定位到DataC所在的NodeC。

因此一種方法是所有的Node要記住

  1. 所有系統中Node的位置
  2. 他們各自存了什麼Data

這對Node來說是一個很大的負擔,也沒有必要。
一個更大的缺點是,當有新的Node加入或是移除時,勢必要更新所有Node裡面儲存的資訊,效率過低。

方法: 每一個Node只記住少部分的Node,也就是自己的Neighbors

因此如果ClientA連上NodeA要找DataC

  1. NodeA可以先問NodeB,NodeB沒有
  2. NodeB再問NodeC,NodeC回覆有
  3. NodeA將NodeC連線資訊回覆給ClientA
  4. ClientA連線NodeC下載DataC

因此DHT的設計很重要的就是可以減少這個詢問的過程,我們稱為 "Hops"

小提示:
白板題寫久了,這邊應該可以很快反應最佳解應該是O(lgn)採用類似二分搜的方法。

小結

回顧一下我們學到的

  • DHT

    • 要在一個Leaderless的P2P環境中找到Data所在的Node
    • 設計一個Hash Function可以同時映射Key與Node至一個一樣Hash Space
    • Data存在Hash Space中最近的Node
    • 盡量滿足4個Criterias
    • 希望Node尋找Data的Hops路徑最短
      • 基本上不同的DHT演算法差異就是在如何做Routing
    • Node要記錄多少Neighbors來幫助Routing
    • Routing過程是Leaderless的,避免Single Point Bottleneck/Failure
    • 可以處理Node的加入與移除
  • DHT Interface

    如同Cache一樣,DHT的設計目標就是Distributed Cache能夠找到資料,因此Interface如下:

    • Lookup(key) → value
    • Insert(key, data)
    • Key最好可以在不同的應用間通用,沒有一個硬性規定的語意(連Node都可以被Hash)
    • DHT 本質上是一個 Hash 演算法,不是資料儲存本身。因此大部分的分散式儲存都是建立在DHT上,如: OpenStack Swift、Ceph的CRUSH演算法。

在系統中的位置:

常見的應用:

以上就是 Distributed Hash TableConsistent Hashing 的介紹。

明後天將會介紹兩個常見的DHT演算法,CHORDKademlia

Reference:


上一篇
Day 22 - Zookeeper - Leader Election 與 Reverse Proxy 實作,使用Golang
下一篇
Day 24 - Data Partitioning - Distributed Hash Table and Consistent Hashing - CHORD(上)
系列文
分散式系統 - 在分散的世界中保持一致30

尚未有邦友留言

立即登入留言