一致性Hash的原理是什么

本篇內容主要講解“一致性Hash的原理是什么”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“一致性Hash的原理是什么”吧!

一、前言

在解決分布式系統中負載均衡的問題時候可以使用Hash算法讓固定的一部分請求落到同一臺服務器上，這樣每臺服務器固定處理一部分請求（并維護這些請求的信息），起到負載均衡的作用。

但是普通的余數hash（hash(比如用戶id)%服務器機器數）算法伸縮性很差，當新增或者下線服務器機器時候，用戶id與服務器的映射關系會大量失效。一致性hash則利用hash環對其進行了改進。

二、一致性Hash概述

為了能直觀的理解一致性hash原理，這里結合一個簡單的例子來講解，假設有4臺服務器，地址為ip1,ip2,ip3,ip4。

• 一致性hash是首先計算四個ip地址對應的hash值
  hash(ip1),hash(ip2),hash(ip3),hash(ip3)，計算出來的hash值是0~最大正整數直接的一個值，這四個值在一致性hash環上呈現如下圖：

   

   

       

  image.png

• hash環上順時針從整數0開始，一直到最大正整數，我們根據四個ip計算的hash值肯定會落到這個hash環上的某一個點，至此我們把服務器的四個ip映射到了一致性hash環

• 當用戶在客戶端進行請求時候，首先根據hash(用戶id)計算路由規則（hash值），然后看hash值落到了hash環的那個地方，根據hash值在hash環上的位置順時針找距離最近的ip作為路由ip.

   

   

       

  image.png

如上圖可知user1,user2的請求會落到服務器ip2進行處理，User3的請求會落到服務器ip3進行處理，user4的請求會落到服務器ip4進行處理，user5,user6的請求會落到服務器ip1進行處理。

下面考慮當ip2的服務器掛了的時候會出現什么情況？
當ip2的服務器掛了的時候，一致性hash環大致如下圖：

image.png

根據順時針規則可知user1,user2的請求會被服務器ip3進行處理，而其它用戶的請求對應的處理服務器不變，也就是只有之前被ip2處理的一部分用戶的映射關系被破壞了，并且其負責處理的請求被順時針下一個節點委托處理。

下面考慮當新增機器的時候會出現什么情況？
當新增一個ip5的服務器后，一致性hash環大致如下圖：

image.png

根據順時針規則可知之前user5的請求應該被ip1服務器處理，現在被新增的ip5服務器處理，其他用戶的請求處理服務器不變，也就是新增的服務器順時針最近的服務器的一部分請求會被新增的服務器所替代。

三、一致性hash的特性

• 單調性(Monotonicity)，單調性是指如果已經有一些請求通過哈希分派到了相應的服務器進行處理，又有新的服務器加入到系統中時候，應保證原有的請求可以被映射到原有的或者新的服務器中去，而不會被映射到原來的其它服務器上去。 這個通過上面新增服務器ip5可以證明，新增ip5后，原來被ip1處理的user6現在還是被ip1處理，原來被ip1處理的user5現在被新增的ip5處理。

• 分散性(Spread)：分布式環境中，客戶端請求時候可能不知道所有服務器的存在，可能只知道其中一部分服務器，在客戶端看來他看到的部分服務器會形成一個完整的hash環。如果多個客戶端都把部分服務器作為一個完整hash環，那么可能會導致，同一個用戶的請求被路由到不同的服務器進行處理。這種情況顯然是應該避免的，因為它不能保證同一個用戶的請求落到同一個服務器。所謂分散性是指上述情況發生的嚴重程度。好的哈希算法應盡量避免盡量降低分散性。 一致性hash具有很低的分散性

• 平衡性(Balance)：平衡性也就是說負載均衡，是指客戶端hash后的請求應該能夠分散到不同的服務器上去。一致性hash可以做到每個服務器都進行處理請求，但是不能保證每個服務器處理的請求的數量大致相同，如下圖

   

   

       

   

服務器ip1,ip2,ip3經過hash后落到了一致性hash環上，從圖中hash值分布可知ip1會負責處理大概80%的請求，而ip2和ip3則只會負責處理大概20%的請求，雖然三個機器都在處理請求，但是明顯每個機器的負載不均衡，這樣稱為一致性hash的傾斜，虛擬節點的出現就是為了解決這個問題。

五、虛擬節點

當服務器節點比較少的時候會出現上節所說的一致性hash傾斜的問題，一個解決方法是多加機器，但是加機器是有成本的，那么就加虛擬節點，比如上面三個機器，每個機器引入1個虛擬節點后的一致性hash環的圖如下：

image.png

其中ip1-1是ip1的虛擬節點，ip2-1是ip2的虛擬節點，ip3-1是ip3的虛擬節點。
可知當物理機器數目為M，虛擬節點為N的時候，實際hash環上節點個數為M*N。比如當客戶端計算的hash值處于ip2和ip3或者處于ip2-1和ip3-1之間時候使用ip3服務器進行處理。

六、均勻一致性hash

上節我們使用虛擬節點后的圖看起來比較均衡，但是如果生成虛擬節點的算法不夠好很可能會得到下面的環：

image.png

可知每個服務節點引入1個虛擬節點后，情況相比沒有引入前均衡性有所改善，但是并不均衡。

均衡的一致性hash應該是如下圖：

image.png

均勻一致性hash的目標是如果服務器有N臺，客戶端的hash值有M個，那么每個服務器應該處理大概M/N個用戶的。也就是每臺服務器負載盡量均衡

七、總結

在分布式系統中一致性hash起著不可忽略的地位，無論是分布式緩存，還是分布式Rpc框架的負載均衡策略都有所使用。

================================================================

服務端處理客戶端寫入請求的偽代碼：

public void handleWrite(WriteMessage wm){

    //從寫入消息中獲取key
    String key=wm.getKey();
    
    //計算實際處理該寫入消息的節點編號
    int handlerID=key.hashCode() % ClusterNodeNum;
    
    //判斷寫入消息是否由本服務器處理
    if(MyClusterID==handleID){
        
        //該寫入消息由本服務器處理，寫入磁盤
        writeMessage(wm);
    }else{
        //將寫入消息發送給對應的服務器處理
        sendMessage(handleID,wm);
    }
    
    //通知客戶端寫入成功
    sendtoClient("write success");

}

服務端處理客戶端讀取請求的偽代碼：

public void handleRead(ReadMessage rm){

    //從讀取消息中獲取key
    String key=rm.getKey();
    
    //計算實際處理該讀取消息的節點編號
    int handlerID=key.hashCode() % ClusterNodeNum;
    
    //用于存儲讀取的數據
    String readData="";
    
    //判斷讀取消息是否由本服務器處理
    if(MyClusterID==handleID){
        
        //該讀取消息由本服務器處理，寫入磁盤
        readData=readMessage(rm);
    }else{
        //將讀取消息發送給對應的服務器處理
        readData=readMessage(handleID,rm);
    }
    
    //通知客戶端讀取成功
    sendtoClient(readData);

}

客戶端調動服務器端的偽代碼：

public static void main(String[] args){

    Random rnd=new Random();
    
    //所有服務器列表
    String[] servers=new String[]("192.168.10.0","192.168.10.1","192.168.10.2","192.168.10.3","192.168.10.4");
    
    //隨機算法選擇一個服務器，進行負載均衡
    Client client = new Client(servers[rnd.nextInt(servers.length)]);

    //向服務器寫入數據
    client.write(new WriteMessage("key1","value1"));
    
    //從服務器讀取數據
    String value=client.read(new ReadMessage("key1"));
}

到此，相信大家對“一致性Hash的原理是什么”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！