前言

前面都是在聊資料做備份放到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 Table與Hash 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 Function的Monotonicity特性。

如果用傳統的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 Table 與 Consistent Hashing 的介紹。

明後天將會介紹兩個常見的DHT演算法，CHORD與Kademlia。

Reference:

• TU Dresden - System Engineering I&II
• 每天进步一点点——五分钟理解一致性哈希算法(consistent hashing)