一致性Hash演算法在分布式場景的應用

普通hash演算法在集群中的應用

Nginx ip_hash策略示意圖

下面是上面策略的簡單代碼實作，模擬出它是如何將客戶端請求分配到不同節點，而且還保證session的一致性，

package demo;

import java.util.ArrayList;
import java.util.List;

/**
 * 
 * @author qiu
 *
 */
public class HashUtils {

	public static void main(String[] args) {
          //模擬客戶端IP
		 List<String> clientList = new ArrayList<>();
		 clientList.add("10.20.12.1");
		 clientList.add("126.10.53.3");
		 clientList.add("101.0.2.4");

		 //定義服務器數量(編號對應0,1,2)
		 int serverCount = 3; 
		 
		 //路由計算
		 clientList.forEach( c-> {
			int hash = Math.abs(c.hashCode());  //hash值自定義
			int index = hash % serverCount; 
			System.out.println("客戶端:"+c+"被路由到編號為》》》》"+index+"的服務器"); 
		 });
		 
		
	}

}

print

客戶端:10.20.12.1被路由到編號為》》》》0的服務器
客戶端:126.10.53.3被路由到編號為》》》》1的服務器
客戶端:101.0.2.4被路由到編號為》》》》1的服務器

問題

以上hash演算法思想也存在一些問題，比如當服務器節點，擴容或宕機時由于服務器的節點改變，在重新求模運算時，會導致客戶端 落到和之前不同的節點服務器上，session會話就消失了，在真實環境中會有大量請求命中不到原來目標服務器上，

解決方案（一致性Hash演算法）

思想：
1.服務器節點定位
每臺服務器節點都會有主機名（這里就取節點服務器的ip地址）下圖中hash環中綠色的點就代表著節點服務器ip經過某個hash演算法后得到的一個整數，這個整數自然就會落到上面直線的區間中的某個位置，每個服務器節點都經過一次取值后落到下面hash環上，
2.客戶端請求處理定位
客戶端（它們也都有自己的IP地址）每一次請求經過hash演算法取值后也都會落到hash環上如下圖（藍色笑臉節點），定位到hash環上之后，客戶端就會路由到離自己節點最近的服務器節點上（注意：順勢針方向搜索）

3.客服端擴容和縮容
縮容
假設服務器3下線后，原來路由到3的客戶端，重新（它會去找離它最近的服務器節點4）路由到服務器4，對于其它客戶端沒有影響，只是一小部分受到影響（請求遷移達到最小，這樣的演算法對分布式集群來說非常適合，避免了大量請求遷移）

擴容

總結

由此可見以上一致性hash演算法解決了服務器節點擴容或宕機時避免大量請求遷移

問題

當服務器節點比較少時，容易因為節點分布不均勻而造成資料傾斜問題
節點1只負責一小段，大量請求落到節點2上，

代碼模擬

package demo;

import java.util.ArrayList;
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;

/**
 * 
 * @author qiu
 *
 */
public class HashUtils {

	public static void main(String[] args) {
		 
		 //初始化：把服務器節點IP的哈希值對應到哈希環上
		 List<String> tomcatServerList = new ArrayList<>();
		 tomcatServerList.add("10.20.12.1");
		 tomcatServerList.add("126.10.53.3");
		 tomcatServerList.add("101.0.2.4");
		 
		 //模擬hash環（有序）
		 SortedMap<Integer,String> hashServermap = new TreeMap<>(); 
		 
		 tomcatServerList.forEach( t-> {
			 //求出每一個ip的hash值，對應到hash環上，存盤hash值與ip的對應關系
				int serverHash = Math.abs(t.hashCode());  //hash值自定義
				hashServermap.put(serverHash, t);
			 });
		 
		 //針對客戶端IP求hash值
		 List<String> clientList = new ArrayList<>();
		 clientList.add("101.40.12.7");
		 clientList.add("226.30.53.6");
		 clientList.add("301.10.2.4");
		 
		 clientList.forEach(c->{
			 
			 int clientHash = Math.abs(c.hashCode());  //hash值自定義
			  //客戶端找到能夠處理當前請求的服務器（hash環上順時針最近）
			  //根據客戶端ip的hash值去找出哪一個服務器節點能夠處理
			 //tailMap方法回傳比當前key大的新集合
			 SortedMap<Integer,String> tailHashServermap =  hashServermap.tailMap(clientHash);
			 if (tailHashServermap.isEmpty()) {
				 //取hash環上的順時針第一臺服務器
				Integer firstKey =  hashServermap.firstKey();
				System.out.println("客戶端:"+c+"被路由到編號為》》》》"+hashServermap.get(firstKey)+"的服務器");
				
			 } else {
				    Integer firstKey =  tailHashServermap.firstKey();
					System.out.println("客戶端:"+c+"被路由到編號為》》》》"+hashServermap.get(firstKey)+"的服務器");
			 }
		 });
		
	}

}

解決方案（一致性Hash演算法+虛擬節點）

為了解決一致性Hash演算法中的資料傾斜問題，一致性hash演算法引入了虛擬節點機制，即對每一個服務器節點計算多個哈希，每個計算結果位置都放置一個此服務節點，稱為虛擬節點，當請求落到某個虛擬節點負責的段時，它就會去找真實節點，來處理請求，這樣就會讓請求處理的均勻了，
如下圖：分別對節點1和節點2計算三個虛擬節點：#1，#2，#3.

代碼模擬

package demo;

import java.util.ArrayList;
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;

/**
 * 
 * @author qiu
 *
 */
public class HashUtils {

	public static void main(String[] args) {
		 
		 //初始化：把服務器節點IP的哈希值對應到哈希環上
		 List<String> tomcatServerList = new ArrayList<>();
		 tomcatServerList.add("10.20.12.1");
		 tomcatServerList.add("126.10.53.3");
		 tomcatServerList.add("101.0.2.4");
		 
		 //模擬hash環（有序）
		 SortedMap<Integer,String> hashServermap = new TreeMap<>(); 
		 
		 
		 //定義針對每個真實服務器虛擬出來幾個節點
		 int virtaulCount = 3;
		 
		 
		 
		 
		 tomcatServerList.forEach( t-> {
			 //求出每一個ip的hash值，對應到hash環上，存盤hash值與ip的對應關系
				int serverHash = Math.abs(t.hashCode());  //hash值自定義
				hashServermap.put(serverHash, t);
				
				//處理虛擬節點
				for(int i=0;i<virtaulCount;i++) {
					
					int virtaulHash = Math.abs((t+"#"+i).hashCode());
					hashServermap.put(virtaulHash, "由虛擬節點轉換成的真實節點》》"+i+":"+t);
					
				}
			 });
		 
		 //針對客戶端IP求hash值
		 List<String> clientList = new ArrayList<>();
		 clientList.add("101.40.12.7");
		 clientList.add("226.30.53.6");
		 clientList.add("301.10.2.4");
		 
		 clientList.forEach(c->{
			 
			 int clientHash = Math.abs(c.hashCode());  //hash值自定義
			  //客戶端找到能夠處理當前請求的服務器（hash環上順時針最近）
			  //根據客戶端ip的hash值去找出哪一個服務器節點能夠處理
			 //tailMap方法回傳比當前key大的新集合
			 SortedMap<Integer,String> tailHashServermap =  hashServermap.tailMap(clientHash);
			 if (tailHashServermap.isEmpty()) {
				 //取hash環上的順時針第一臺服務器
				Integer firstKey =  hashServermap.firstKey();
				System.out.println("客戶端:"+c+"被路由到編號為》》》》"+hashServermap.get(firstKey)+"的服務器");
				
			 } else {
				    Integer firstKey =  tailHashServermap.firstKey();
					System.out.println("客戶端:"+c+"被路由到編號為》》》》"+hashServermap.get(firstKey)+"的服務器");
			 }
		 });
		
	}

}

print

客戶端:101.40.12.7被路由到編號為》》》》由虛擬節點轉換成的真實節點》》2:10.20.12.1的服務器
客戶端:226.30.53.6被路由到編號為》》》》由虛擬節點轉換成的真實節點》》2:101.0.2.4的服務器
客戶端:301.10.2.4被路由到編號為》》》》101.0.2.4的服務器

總結

由此可見一致性Hash演算法+虛擬節點可以解決資料傾斜問題