引入
在業務開發中，我們常把資料持久化到資料庫中。如果需要讀取這些資料，除了直接從資料庫中讀取外，為了減輕資料庫的通路壓力以及提高通路速度，我們更多地引入緩存來對資料進行存取。讀取資料的過程一般為：
圖1：加入緩存的資料讀取過程
對于分布式緩存，不同機器上存儲不同對象的資料。為了實作這些緩存機器的負載均衡，可以使用式子1來定位對象緩存的存儲機器：
m = hash(o) mod n ——式子1
其中，
o
為對象的名稱，
n
為機器的數量，
m
為機器的編号，
hash
為一hash函數。圖2中的負載均衡器（load balancer）正是使用式子1來将用戶端對不同對象的請求分派到不同的機器上執行，例如，對于對象o，經過式子1的計算，得到
m
的值為3，那麼所有對對象o的讀取和存儲的請求都被發往機器3執行。
圖2：如何利用Hash取模實作負載均衡
式子1在大部分時候都可以工作得很好，然而，當機器需要擴容或者機器出現當機的情況下，事情就比較棘手了。
當機器擴容，需要增加一台緩存機器時，負載均衡器使用的式子變成：
m = hash(o) mod (n + 1) ——式子2
當機器當機，機器數量減少一台時，負載均衡器使用的式子變成：
m = hash(o) mod (n - 1) ——式子3
我們以機器擴容的情況為例，說明簡單的取模方法會導緻什麼問題。假設機器由3台變成4台，對象o1由式子1計算得到的m值為2，由式子2計算得到的m值卻可能為0，1，2，3（一個 3t + 2的整數對4取模，其值可能為0，1，2，3，讀者可以自行驗證），大約有75%（3/4)的可能性出現緩存通路不命中的現象。随着機器叢集規模的擴大，這個比例線性上升。當99台機器再加入1台機器時，不命中的機率是99%（99/100）。這樣的結果顯然是不能接受的，因為這會導緻資料庫通路的壓力陡增，嚴重情況，還可能導緻資料庫當機。
一緻性hash算法正是為了解決此類問題的方法，它可以保證當機器增加或者減少時，對緩存通路命中的機率影響減至很小。下面我們來詳細說一下一緻性hash算法的具體過程。
一緻性Hash環
一緻性hash算法通過一個叫作一緻性hash環的資料結構實作。這個環的起點是0，終點是2^32 - 1，并且起點與終點連接配接，環的中間的整數按逆時針分布，故這個環的整數分布範圍是[0, 2^32-1]，如下圖3所示：
圖3：一緻性Hash環
将對象放置到Hash環
假設現在我們有4個對象，分别為o1，o2，o3，o4，使用hash函數計算這4個對象的hash值（範圍為0 ~ 2^32-1）:
hash(o1) = m1
hash(o2) = m2
hash(o3) = m3
hash(o4) = m4
把m1，m2，m3，m4這4個值放置到hash環上，得到如下圖4：
圖4：放置了對象的一緻性Hash環
将機器放置到Hash環
使用同樣的hash函數，我們将機器也放置到hash環上。假設我們有三台緩存機器，分别為 c1，c2，c3，使用hash函數計算這3台機器的hash值：
hash(c1) = t1
hash(c2) = t2
hash(c3) = t3
把t1，t2，t3 這3個值放置到hash環上，得到如下圖5：
圖5：放置了機器的一緻性Hash環
為對象選擇機器
将對象和機器都放置到同一個hash環後，在hash環上順時針查找距離這個對象的hash值最近的機器，即是這個對象所屬的機器。
例如，對于對象o2，順序針找到最近的機器是c1，故機器c1會緩存對象o2。而機器c2則緩存o3，o4，機器c3則緩存對象o1。
圖6：在一緻性Hash環上為對象選擇機器
處理機器增減的情況
對于線上的業務，增加或者減少一台機器的部署是常有的事情。
例如，增加機器c4的部署并将機器c4加入到hash環的機器c3與c2之間。這時，隻有機器c3與c4之間的對象需要重新配置設定新的機器。對于我們的例子，隻有對象o4被重新配置設定到了c4，其他對象仍在原有機器上。如圖7所示：
圖7：增加機器後的一緻性Hash環的結構
如上文前面所述，使用簡單的求模方法，當新添加機器後會導緻大部分緩存失效的情況，使用一緻性hash算法後這種情況則會得到大大的改善。前面提到3台機器變成4台機器後，緩存命中率隻有25%（不命中率75%）。而使用一緻性hash算法，理想情況下緩存命中率則有75%，而且，随着機器規模的增加，命中率會進一步提高，99台機器增加一台後，命中率達到99%，這大大減輕了增加緩存機器帶來的資料庫通路的壓力。
再例如，将機器c1下線（當然，也有可能是機器c1當機），這時，隻有原有被配置設定到機器c1對象需要被重新配置設定到新的機器。對于我們的例子，隻有對象o2被重新配置設定到機器c3，其他對象仍在原有機器上。如圖8所示：
圖8：減少機器後的一緻性Hash環的結構
虛拟節點
上面提到的過程基本上就是一緻性hash的基本原理了，不過還有一個小小的問題。新加入的機器c4隻分擔了機器c2的負載，機器c1與c3的負載并沒有因為機器c4的加入而減少負載壓力。如果4台機器的性能是一樣的，那麼這種結果并不是我們想要的。
為此，我們引入虛拟節點來解決負載不均衡的問題。
将每台實體機器虛拟為一組虛拟機器，将虛拟機器放置到hash環上，如果需要确定對象的機器，先确定對象的虛拟機器，再由虛拟機器确定實體機器。
說得有點複雜，其實過程也很簡單。
還是使用上面的例子，假如開始時存在緩存機器c1，c2，c3，對于每個緩存機器，都有3個虛拟節點對應，其一緻性hash環結構如圖9所示：
圖9：機器c1，c2，c3的一緻性Hash環結構
假設對于對象o1，其對應的虛拟節點為c11，而虛拟節點c11對象緩存機器c1，故對象o1被配置設定到機器c1中。
新加入緩存機器c4，其對應的虛拟節點為c41，c42，c43，将這三個虛拟節點添加到hash環中，得到的hash環結構如圖10所示：
圖10：機器c1，c2，c3，c4的一緻性Hash環結構
新加入的緩存機器c4對應一組虛拟節點c41，c42，c43，加入到hash環後，影響的虛拟節點包括c31，c22，c11（順時針查找到第一個節點），而這3個虛拟節點分别對應機器c3，c2，c1。即新加入的一台機器，同時影響到原有的3台機器。理想情況下，新加入的機器平等地分擔了原有機器的負載，這正是虛拟節點帶來的好處。而且新加入機器c4後，隻影響25%（1/4）對象配置設定，也就是說，命中率仍然有75%，這跟沒有使用虛拟節點的一緻性hash算法得到的結果是相同的。
總結
一緻性hash算法解決了分布式環境下機器增加或者減少時，簡單的取模運算無法擷取較高命中率的問題。通過虛拟節點的使用，一緻性hash算法可以均勻分擔機器的負載，使得這一算法更具現實的意義。正因如此，一緻性hash算法被廣泛應用于分布式系統中。
參考資料
-
- https://en.wikipedia.org/wiki/Consistent_hashing
- https://www.codeproject.com/articles/56138/consistent-hashing
- 《大型網站技術架構——核心原理與安全分析》，李智慧著，電子工業出版社