分佈式經典結構
如圖所示的結構, 當前端接收到請求時, 通過計算key的哈希值, 將哈希值模3, 然後分佈到不同的後端服務器上
但是, 這樣的結構當添加或減少後端服務器時就暴露了問題, 每次添加或減少後端服務器, 放在服務器中的所有數據都要全部重新計算哈希, 將哈希值摸新的臺數, 重新添加. 如此, 數據遷移的成本太高了, 由此引出了一致性哈希
一致性哈希
前端服務端結構不變, 以下都是後端服務器.
假設哈希函數計算出的值在 0-2^64 範圍內, 將其想想成一個環, 如下:
將服務器打在這個環上, 那麼服務器也要有一個哈希值, 通過服務器唯一的標誌來計算(ip, mac, hostname等), 如下:
當請求到來時, 計算請求的哈希值, 哈希值定會打在這個環上, 然後將請求發給順時針找到的第一個服務器, 如下:
也就是找到比請求哈希值大的第一臺服務器.
實現這個結構後, 若是向服務器中添加一臺, 只要找到原本負責這個區域的服務器, 然後將應該負責區域的數據拿過來並從原服務器中刪除即可, 如下:
刪除一臺服務器也是同樣的道理
如此一來, 數據的遷移成本確實減少了, 但是新的問題出現的, 數據的均衡性得不到保證, 因為哈希函數計算出的哈希值是隨機的, 所以很可能出現兩臺服務器分佈不均的情況:
這時, 大部分數據都是S1負責, 而S2只負責少部分數據, 即使恰巧分佈均勻,S1和S2正好打在環的兩端, 但是新加一臺服務器也勢必會破壞均衡:
這樣肯定是不行的, 那麼如何解決這個問題呢?
這個問題是什麼導致的呢? 是因為哈希函數所導致的, 哈希函數是當數據量大的時候, 可以保證均勻的分佈, 但是當數據量小的時候並不能保證, 那就讓數據量大就好了.
我們給每臺服務器分配1萬個虛擬節點, 令虛擬節點分佈到環上, 服務器負責的區域是這1萬個虛擬節點負責區域的總和, 這樣計算哈希的時候就保證了數據量, 即保證其哈希值會均勻分佈到環上, 問題解決.
以上, 就是一致性哈希的簡單介紹!!!
閱讀更多 牛牛的編程之路 的文章
