哈希

Hash也稱散列、哈希，原理是把任意長度的字符串當作輸入，然後通過Hash算法變成固定長度輸出。Hash是一個映射的過程，因此是一定會產生衝突的，一般使用鏈地址法，開放尋址法等方法來解決hash衝突。

分佈式下的哈希

在分佈式的情景下，為了解決數據和請求的定向問題，我們也會常常使用到哈希算法。接下來，就會介紹幾種常常在分佈式環境下運用的hash算法。

普通哈希

哪怕是在分佈式的環境下，我們也可以使用最簡單的hash算法，通過設定好每台服務器對應的結果值，在請求或者數據進來時進行計算，將數據分別映射到相應的服務器上，由於計算規則是一致的，因此無論進行多少次的計算，數據的映射是不會進行變化的。

這種普通的哈希的方式優缺點分明，優點是實現簡單，清晰明瞭。缺點是由於分佈式系統中的節點充滿了不確定性，可能會縮容或者擴容或者節點宕機，如果在這些情況下，意味着哈希的映射將會發生變化，同時之前的那些映射的數據需要進行遷移，以便之後能夠正確的訪問。而這種方式的哈希在這種情況下產生的數據遷移量將會是非常巨大的。

上圖是一個普通的分佈式系統的哈希映射關係，3台服務器分別接受哈希值為0，1，2的請求（一般為計算%2的值）。

於是當我們新增一台服務器之後，原本3台服務器變成了4台，哈希映射需要隨之修改，大量的數據需要遷移。

一致性哈希

一致性哈希是為了解決之前説到的哈希造成的大量數據遷移的問題。

一致性哈希和普通哈希相比，同樣是有一定的映射關係的，但是不同的是，我們會在開始創建一個哈希環，在環上分佈着大量的節點值，一般的範圍為0 ~ 2^32-1

之後我們會根據一定的規則，將服務器節點落在環上，如下圖

之後的邏輯就比較簡單了，當請求發往服務器後，經過計算找到其在環上的對應位置，然後檢查該位置上是否有對應服務器節點，如果有就將請求轉發過去，如果沒有就沿着哈希環順時針尋找，直到找到節點位置。

這樣設計的好處是顯而易見的，如果我們需要新增或者刪除節點的時候，每次只會影響至多2個節點的數據，相比較之前的普通哈希，消耗顯然是更少的。並且當某些服務器因故障突然宕機的時候，請求也可以順延到下個節點進行處理。

節點分佈不均問題

一致性哈希的特點決定了如果節點分佈的不夠均勻會導致其中部分節點壓力過大，而部分節點有很多資源的空閒。如下圖

圖中的A，B節點顯然是不均衡的，請求會更多地發往A節點而B節點只能獲取A節點約1/3的請求。

於是一致性哈希往往會引入這麼一個概念：虛擬節點。儘管我們的服務器分佈不夠均勻，但是我們可以認為的創建一些虛擬節點，並且創建相應的映射，幫助虛擬節點把請求轉發到實際節點。

如圖，我們可以創建對應的虛擬節點A'，B'，然後把發往B'的請求轉發到B，A'的請求轉發到A，這樣就不會存在失衡的問題了。

哈希槽

哈希槽的典型是redis的分佈式實現。

redis的分佈式實現中，會在啟動集羣的時候確認所有的服務器數量，然後將數量為16384的哈希槽平均分配給所有的master服務器，然後所有的數據都會存放在指定的節點之中。

redis的哈希槽的實現和一致性哈希有相同之處，也有不同之處。最主要的原因是redis採用了不同的高可用策略。一致性哈希在服務器宕機時會把流量轉到下一個服務器，但是redis不同，redis的集羣模式會保證服務器節點擁有的主備模式。備份節點不會直接參與到哈希槽的分配中，但是當主節點宕機後，從節點會頂替主節點處理任務。

分佈式哈希表

分佈式哈希表（DHT）是一種分佈式的哈希手段。和一致性哈希不同的是，DHT不需要中心節點來分配數據的流向。他有自己的一套機制保證無論數據剛開始走的是哪一個服務器，都可以找到自己需要前往的正確服務器。

Kademlia算法

Kademlia算法是一種典型的分佈式的哈希表算法，多用於p2p網絡的構建，由Petar Maymounkov 和 David Mazieres共同創造。Kademlia論文源地址：Kademlia

分佈式環境下的哈希表的難點在於以下幾點：

分佈式環境下每個服務器不可能掌握所有服務器的情況，因此如何保證你的請求能在沒有中央節點定位的情況下找到對應的服務器是一大難點。
同樣由於分佈式環境的服務器的掌握信息有限，那麼服務器的加入和退出如何能夠被集羣知曉也是一大難點。

那麼我們來看Kademlia算法是如何解決這些問題的吧。

異或運算

Kademlia使用到了異或來進行距離的計算。我們先來看看異或的定義。

異或的運算法則為：0⊕0=0，1⊕0=1，0⊕1=1，1⊕1=0（同為0，異為1）

然後我們來看看為什麼用異或來計算距離。

a⊕b = b⊕a // 異或符合交換律，a節點到b節點的距離和b節點到a結點的距離相同
a⊕b = 0    // 自己和自己的距離為0
a⊕b >= 0   // 兩個節點之間的距離大於0
a⊕b + b⊕c >= a⊕c // a到b再到c的距離大於等於直接到c的距離
複製代碼

根據上述的一些異或的規則，我們可以發現異或和距離的一些特性可以説是絕配，真的很佩服算法的作者能夠想到如此精巧的設計。

二叉樹的構建

確定了用異或來計算距離後，那麼具體集羣是如何構建並存儲信息使得可以查找到正確的信息呢？

Kademlia算法理論中每個集羣的節點都會存儲一部分節點的信息（不可能存儲所有節點的信息，因為效率會低，並且無法保證實時性）。

所有的節點會構建成一棵獨特的二叉樹如下圖：

首先把每個節點的id經過一定的哈希計算得到該節點的一串01字符串以表示其在樹中的位置，從高位開始，1則往左子樹走，0往右子樹走，直到結束。可以看出圖中的黑色節點的哈希值為0011

二叉樹的拆分

Kademlia的二叉樹中的每一個節點都可以根據自己的視角進行二叉樹的拆分

拆分規則是從根節點開始依次把不包含自己的子樹拆分出來，以此類推，最後只剩下自己。之前的二叉樹拆分如之前的圖。對於黑色節點來説，外部有拆分出了四個不包含自己的子樹。

K-bucket機制

在二叉樹拆分之後每一個拆分過後的子樹實際上對應的就是一個一個bucket，每個bucket對於當前節點的距離是不同的範圍，距離越遠，高位不同，因此異或結果差距越大（距離越遠）：

K-bucket	距離區間
0	[2^0, 2^1)
1	[2^1, 2^2)
2	[2^2, 2^3)
3	[2^3, 2^4)
4	[2^4, 2^5)

所以實際上每一個節點再進行拆分後只需要在對應的每個bucket中存儲一份該bucket的節點就可以遍歷整個二叉樹（集羣）。當然為了容錯，一般來説每個bucket的節點都會保留幾個，而不僅僅是一個。

節點查詢

大致瞭解了原理之後，我們回過頭來看每次請求是如何定位節點的。

首先一個請求進入集羣中的某個服務器。然後我們將請求帶着的目的地服務器的id和當前服務器的id計算兩者的距離。然後計算出了一個值，之後從服務器的bucket列表中尋找對應的bucket（即這個距離範圍對應的bucket）。我們的目標服務器就可以鎖定在了那個bucket的範圍之內，之後，在bucket中尋找距離該節點最近的K個服務節點（此參數可以自行設定大小），將請求重定向到這幾個節點。之後重複上述的步驟，如果該集羣中真的有目標節點，那麼就可以成功的返回。

基本的機制如此，當然在實際的環境中我們考慮到現實情況會對請求做超時處理，避免大量的節點間的查詢造成不必要的負載。

節點變動

一個新節點是想加入網絡，首先有一個前提條件：他需要有一個處於網絡中的節點的信息，然後才能開啟加入流程。

加入流程：

新節點A以之前就有的節點T為起點，將其加入自己的K-bucket中，並且生成一個自己的節點id
節點A項節點B進行請求，以自己的id為參數請求節點定位自己的位置
之後就是查詢結點的流程了，每一個路經的節點都會找到自己節點中存儲的距離節點最近的節點，然後A把這些節點放入自己的bucket中以完善自己的路由表。同時，這些路經節點也會把A節點放入自己的路由表中，以待後用。
等到大部分節點返回後，A的路由表建立完成，一些節點也已經將A節點加入自己的路由表。至此A節點加入網絡成功。

算法的參數

算法中我們用到的一些參數其實是可以自己定義的：

k-bucket中的k：定義了每一層bucket會存儲k個節點信息
每一次請求會向s個節點發送信息
id的長度也是可以自定義的，注意id的長度會決定二叉樹的高度

總結

分佈式系統中的哈希算法有很多種，實現不同，功能也不盡相同。對於一般的企業應用中，帶有中心節點的哈希算法是更為理想的選擇，因為意味着服務的可控可監測。而在類似於p2p和區塊鏈的環境下，具備中心節點的分佈式哈希算法是沒法接受的，因為p2p和區塊鏈的設計上是沒有中心節點的，也不會有節點能夠知道所有網絡中的節點信息，因此無中心節點的哈希算法在此可以大放異彩。