一撵彻、前言

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

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

二支鸡、一致性Hash概述

為了能直觀的理解一致性hash原理阀趴，這里結(jié)合一個簡單的例子來講解，假設(shè)有4臺服務(wù)器苍匆，地址為ip1,ip2,ip3,ip4刘急。

一致性hash是首先計算四個ip地址對應(yīng)的hash值

hash(ip1),hash(ip2),hash(ip3),hash(ip3)，計算出來的hash值是0~最大正整數(shù)直接的一個值浸踩，這四個值在一致性hash環(huán)上呈現(xiàn)如下圖：

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

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

如上圖可知user1,user2的請求會落到服務(wù)器ip2進行處理另假，User3的請求會落到服務(wù)器ip3進行處理，user4的請求會落到服務(wù)器ip4進行處理怕犁，user5,user6的請求會落到服務(wù)器ip1進行處理边篮。

下面考慮當(dāng)ip2的服務(wù)器掛了的時候會出現(xiàn)什么情況？

當(dāng)ip2的服務(wù)器掛了的時候奏甫，一致性hash環(huán)大致如下圖：

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

下面考慮當(dāng)新增機器的時候會出現(xiàn)什么情況？

當(dāng)新增一個ip5的服務(wù)器后挠进，一致性hash環(huán)大致如下圖：

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

三、一致性hash的特性

單調(diào)性(Monotonicity)攘须，單調(diào)性是指如果已經(jīng)有一些請求通過哈希分派到了相應(yīng)的服務(wù)器進行處理漆撞，又有新的服務(wù)器加入到系統(tǒng)中時候殴泰，應(yīng)保證原有的請求可以被映射到原有的或者新的服務(wù)器中去，而不會被映射到原來的其它服務(wù)器上去浮驳。 這個通過上面新增服務(wù)器ip5可以證明悍汛，新增ip5后，原來被ip1處理的user6現(xiàn)在還是被ip1處理至会，原來被ip1處理的user5現(xiàn)在被新增的ip5處理离咐。

分散性(Spread)：分布式環(huán)境中，客戶端請求時候可能不知道所有服務(wù)器的存在奉件，可能只知道其中一部分服務(wù)器宵蛀，在客戶端看來他看到的部分服務(wù)器會形成一個完整的hash環(huán)。如果多個客戶端都把部分服務(wù)器作為一個完整hash環(huán)县貌，那么可能會導(dǎo)致术陶，同一個用戶的請求被路由到不同的服務(wù)器進行處理。這種情況顯然是應(yīng)該避免的煤痕，因為它不能保證同一個用戶的請求落到同一個服務(wù)器梧宫。所謂分散性是指上述情況發(fā)生的嚴重程度。好的哈希算法應(yīng)盡量避免盡量降低分散性摆碉。 一致性hash具有很低的分散性

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

服務(wù)器ip1,ip2,ip3經(jīng)過hash后落到了一致性hash環(huán)上，從圖中hash值分布可知ip1會負責(zé)處理大概80%的請求楞泼，而ip2和ip3則只會負責(zé)處理大概20%的請求驰徊，雖然三個機器都在處理請求，但是明顯每個機器的負載不均衡现拒，這樣稱為一致性hash的傾斜辣垒，虛擬節(jié)點的出現(xiàn)就是為了解決這個問題。如果想學(xué)習(xí)Java工程化印蔬、高性能及分布式、深入淺出脱衙。微服務(wù)侥猬、Spring，MyBatis捐韩，Netty源碼分析的朋友可以加Java進階群：582505643退唠，群里有阿里大牛直播講解技術(shù)，以及Java大型互聯(lián)網(wǎng)技術(shù)的視頻免費分享給大家荤胁。

四瞧预、虛擬節(jié)點

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

其中ip1-1是ip1的虛擬節(jié)點滩愁，ip2-1是ip2的虛擬節(jié)點躯喇，ip3-1是ip3的虛擬節(jié)點。

可知當(dāng)物理機器數(shù)目為M硝枉，虛擬節(jié)點為N的時候廉丽，實際hash環(huán)上節(jié)點個數(shù)為M*N。比如當(dāng)客戶端計算的hash值處于ip2和ip3或者處于ip2-1和ip3-1之間時候使用ip3服務(wù)器進行處理妻味。

五正压、均勻一致性hash

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

可知每個服務(wù)節(jié)點引入1個虛擬節(jié)點后责球，情況相比沒有引入前均衡性有所改善蔑匣，但是并不均衡。

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

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

六校套、總結(jié)

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

大家可以點擊加入群：【Java高級架構(gòu)進階群】 里面有Java高級大牛直播講解知識點 走的就是高端路線侨把，（如果你想跳槽換工作 但是技術(shù)又不夠 或者工作上遇到了瓶頸 ，我這里有一個JAVA的免費直播課程 妹孙，講的是高端的知識點基礎(chǔ)不好的誤入喲秋柄，只要你有1-5年的開發(fā)經(jīng)驗可以加群找我要課堂鏈接 注意：是免費的 沒有開發(fā)經(jīng)驗誤入哦）

點擊鏈接加入群聊【Java高級架構(gòu)進階群】：群地址

寫在最后：歡迎留言討論，加關(guān)注蠢正，持續(xù)更新：П省！嚣崭！