一致性Hash的原理是什么

本篇內(nèi)容主要講解“一致性Hash的原理是什么”，感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“一致性Hash的原理是什么”吧!

一、前言

在解決分布式系統(tǒng)中負(fù)載均衡的問(wèn)題時(shí)候可以使用Hash算法讓固定的一部分請(qǐng)求落到同一臺(tái)服務(wù)器上，這樣每臺(tái)服務(wù)器固定處理一部分請(qǐng)求（并維護(hù)這些請(qǐng)求的信息），起到負(fù)載均衡的作用。

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

二、一致性Hash概述

為了能直觀的理解一致性hash原理，這里結(jié)合一個(gè)簡(jiǎn)單的例子來(lái)講解，假設(shè)有4臺(tái)服務(wù)器，地址為ip1,ip2,ip3,ip4。

• 一致性hash是首先計(jì)算四個(gè)ip地址對(duì)應(yīng)的hash值
  hash(ip1),hash(ip2),hash(ip3),hash(ip3)，計(jì)算出來(lái)的hash值是0~最大正整數(shù)直接的一個(gè)值，這四個(gè)值在一致性hash環(huán)上呈現(xiàn)如下圖：

   

   

       

  image.png

• hash環(huán)上順時(shí)針從整數(shù)0開(kāi)始，一直到最大正整數(shù)，我們根據(jù)四個(gè)ip計(jì)算的hash值肯定會(huì)落到這個(gè)hash環(huán)上的某一個(gè)點(diǎn)，至此我們把服務(wù)器的四個(gè)ip映射到了一致性hash環(huán)

• 當(dāng)用戶在客戶端進(jìn)行請(qǐng)求時(shí)候，首先根據(jù)hash(用戶id)計(jì)算路由規(guī)則（hash值），然后看hash值落到了hash環(huán)的那個(gè)地方，根據(jù)hash值在hash環(huán)上的位置順時(shí)針找距離最近的ip作為路由ip.

   

   

       

  image.png

如上圖可知user1,user2的請(qǐng)求會(huì)落到服務(wù)器ip2進(jìn)行處理，User3的請(qǐng)求會(huì)落到服務(wù)器ip3進(jìn)行處理，user4的請(qǐng)求會(huì)落到服務(wù)器ip4進(jìn)行處理，user5,user6的請(qǐng)求會(huì)落到服務(wù)器ip1進(jìn)行處理。

下面考慮當(dāng)ip2的服務(wù)器掛了的時(shí)候會(huì)出現(xiàn)什么情況？
當(dāng)ip2的服務(wù)器掛了的時(shí)候，一致性hash環(huán)大致如下圖：

image.png

根據(jù)順時(shí)針規(guī)則可知user1,user2的請(qǐng)求會(huì)被服務(wù)器ip3進(jìn)行處理，而其它用戶的請(qǐng)求對(duì)應(yīng)的處理服務(wù)器不變，也就是只有之前被ip2處理的一部分用戶的映射關(guān)系被破壞了，并且其負(fù)責(zé)處理的請(qǐng)求被順時(shí)針下一個(gè)節(jié)點(diǎn)委托處理。

下面考慮當(dāng)新增機(jī)器的時(shí)候會(huì)出現(xiàn)什么情況？
當(dāng)新增一個(gè)ip5的服務(wù)器后，一致性hash環(huán)大致如下圖：

image.png

根據(jù)順時(shí)針規(guī)則可知之前user5的請(qǐng)求應(yīng)該被ip1服務(wù)器處理，現(xiàn)在被新增的ip5服務(wù)器處理，其他用戶的請(qǐng)求處理服務(wù)器不變，也就是新增的服務(wù)器順時(shí)針最近的服務(wù)器的一部分請(qǐng)求會(huì)被新增的服務(wù)器所替代。

三、一致性hash的特性

• 單調(diào)性(Monotonicity)，單調(diào)性是指如果已經(jīng)有一些請(qǐng)求通過(guò)哈希分派到了相應(yīng)的服務(wù)器進(jìn)行處理，又有新的服務(wù)器加入到系統(tǒng)中時(shí)候，應(yīng)保證原有的請(qǐng)求可以被映射到原有的或者新的服務(wù)器中去，而不會(huì)被映射到原來(lái)的其它服務(wù)器上去。 這個(gè)通過(guò)上面新增服務(wù)器ip5可以證明，新增ip5后，原來(lái)被ip1處理的user6現(xiàn)在還是被ip1處理，原來(lái)被ip1處理的user5現(xiàn)在被新增的ip5處理。

• 分散性(Spread)：分布式環(huán)境中，客戶端請(qǐng)求時(shí)候可能不知道所有服務(wù)器的存在，可能只知道其中一部分服務(wù)器，在客戶端看來(lái)他看到的部分服務(wù)器會(huì)形成一個(gè)完整的hash環(huán)。如果多個(gè)客戶端都把部分服務(wù)器作為一個(gè)完整hash環(huán)，那么可能會(huì)導(dǎo)致，同一個(gè)用戶的請(qǐng)求被路由到不同的服務(wù)器進(jìn)行處理。這種情況顯然是應(yīng)該避免的，因?yàn)樗荒鼙ＷC同一個(gè)用戶的請(qǐng)求落到同一個(gè)服務(wù)器。所謂分散性是指上述情況發(fā)生的嚴(yán)重程度。好的哈希算法應(yīng)盡量避免盡量降低分散性。 一致性hash具有很低的分散性

• 平衡性(Balance)：平衡性也就是說(shuō)負(fù)載均衡，是指客戶端hash后的請(qǐng)求應(yīng)該能夠分散到不同的服務(wù)器上去。一致性hash可以做到每個(gè)服務(wù)器都進(jìn)行處理請(qǐng)求，但是不能保證每個(gè)服務(wù)器處理的請(qǐng)求的數(shù)量大致相同，如下圖

   

   

       

   

服務(wù)器ip1,ip2,ip3經(jīng)過(guò)hash后落到了一致性hash環(huán)上，從圖中hash值分布可知ip1會(huì)負(fù)責(zé)處理大概80%的請(qǐng)求，而ip2和ip3則只會(huì)負(fù)責(zé)處理大概20%的請(qǐng)求，雖然三個(gè)機(jī)器都在處理請(qǐng)求，但是明顯每個(gè)機(jī)器的負(fù)載不均衡，這樣稱為一致性hash的傾斜，虛擬節(jié)點(diǎn)的出現(xiàn)就是為了解決這個(gè)問(wèn)題。

五、虛擬節(jié)點(diǎn)

當(dāng)服務(wù)器節(jié)點(diǎn)比較少的時(shí)候會(huì)出現(xiàn)上節(jié)所說(shuō)的一致性hash傾斜的問(wèn)題，一個(gè)解決方法是多加機(jī)器，但是加機(jī)器是有成本的，那么就加虛擬節(jié)點(diǎn)，比如上面三個(gè)機(jī)器，每個(gè)機(jī)器引入1個(gè)虛擬節(jié)點(diǎn)后的一致性hash環(huán)的圖如下：

image.png

其中ip1-1是ip1的虛擬節(jié)點(diǎn)，ip2-1是ip2的虛擬節(jié)點(diǎn)，ip3-1是ip3的虛擬節(jié)點(diǎn)。
可知當(dāng)物理機(jī)器數(shù)目為M，虛擬節(jié)點(diǎn)為N的時(shí)候，實(shí)際hash環(huán)上節(jié)點(diǎn)個(gè)數(shù)為M*N。比如當(dāng)客戶端計(jì)算的hash值處于ip2和ip3或者處于ip2-1和ip3-1之間時(shí)候使用ip3服務(wù)器進(jìn)行處理。

六、均勻一致性hash

上節(jié)我們使用虛擬節(jié)點(diǎn)后的圖看起來(lái)比較均衡，但是如果生成虛擬節(jié)點(diǎn)的算法不夠好很可能會(huì)得到下面的環(huán)：

image.png

可知每個(gè)服務(wù)節(jié)點(diǎn)引入1個(gè)虛擬節(jié)點(diǎn)后，情況相比沒(méi)有引入前均衡性有所改善，但是并不均衡。

均衡的一致性hash應(yīng)該是如下圖：

image.png

均勻一致性hash的目標(biāo)是如果服務(wù)器有N臺(tái)，客戶端的hash值有M個(gè)，那么每個(gè)服務(wù)器應(yīng)該處理大概M/N個(gè)用戶的。也就是每臺(tái)服務(wù)器負(fù)載盡量均衡

七、總結(jié)

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

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

服務(wù)端處理客戶端寫入請(qǐng)求的偽代碼：

public void handleWrite(WriteMessage wm){

    //從寫入消息中獲取key
    String key=wm.getKey();
    
    //計(jì)算實(shí)際處理該寫入消息的節(jié)點(diǎn)編號(hào)
    int handlerID=key.hashCode() % ClusterNodeNum;
    
    //判斷寫入消息是否由本服務(wù)器處理
    if(MyClusterID==handleID){
        
        //該寫入消息由本服務(wù)器處理，寫入磁盤
        writeMessage(wm);
    }else{
        //將寫入消息發(fā)送給對(duì)應(yīng)的服務(wù)器處理
        sendMessage(handleID,wm);
    }
    
    //通知客戶端寫入成功
    sendtoClient("write success");

}

服務(wù)端處理客戶端讀取請(qǐng)求的偽代碼：

public void handleRead(ReadMessage rm){

    //從讀取消息中獲取key
    String key=rm.getKey();
    
    //計(jì)算實(shí)際處理該讀取消息的節(jié)點(diǎn)編號(hào)
    int handlerID=key.hashCode() % ClusterNodeNum;
    
    //用于存儲(chǔ)讀取的數(shù)據(jù)
    String readData="";
    
    //判斷讀取消息是否由本服務(wù)器處理
    if(MyClusterID==handleID){
        
        //該讀取消息由本服務(wù)器處理，寫入磁盤
        readData=readMessage(rm);
    }else{
        //將讀取消息發(fā)送給對(duì)應(yīng)的服務(wù)器處理
        readData=readMessage(handleID,rm);
    }
    
    //通知客戶端讀取成功
    sendtoClient(readData);

}

客戶端調(diào)動(dòng)服務(wù)器端的偽代碼：

public static void main(String[] args){

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

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

到此，相信大家對(duì)“一致性Hash的原理是什么”有了更深的了解，不妨來(lái)實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！