Hash算法的應用場景

1. 請求的負載均衡
   Nginx的ip_hash策略可以在客戶端ip不發生變化的情況下，將其發出的請求始終路由到同一個目標服務器上，實現會話粘滯，避免處理session共享問題。

• 如果沒有ip_hash策略，可以通過維護一張映射表的方式來實現會話粘滯：

  • 映射表存儲的是客戶端ip或者session與具體目標服務器的映射關系 <ip,server>

    • 缺點：
      1. 客戶端很多的情況下，映射表非常大，浪費內存空間
      2. 客戶端上下線、目標服務器上下線都會導致重新維護映射表，維護成本大

  • 如果使用Hash算法，可以對ip或者session計算hash值，hash值與服務器數量進行取模運算，得到的值就是當前請求應該被路由到的服務器編號。由此，同一個ip發送過來的請求就可以路由到同一個目標服務器，實現會話粘滯。

2. 分布式存儲
   有 Redis1、Redis2、Redis3 三臺Redis服務器，可以針對key進行hash處理 Hash(key)%3 = index 使用余數鎖定存儲的具體服務器節點。

普通Hash算法存在的問題

以ip_hash為例，假定用戶ip固定不變，當后端服務器有一個宕機，數量由3變為2，那么之前所有用戶的求模都需要重新計算。
如果在生產環境中，后臺服務器有很多臺，客戶端也有很多個，出現這種問題的影響是很大的。服務器的擴縮容都會出現這樣的問題，大量的用戶請求被路由到其他的目標服務器處理，用戶在原來服務器的會話都將丟失。

普通Hash算法：

// 定義客戶端IP
String[] clients = {"192.168.31.121", "192.168.3.21", "192.168.1.11"};// 定義服務器數量
int server = 5;// hash(ip) % server數量 = index
for (String client : clients) {int hashCode = Math.abs(client.hashCode());int index = hashCode % server;System.out.println("客戶端：\t" + client + "\t 分配到了服務器 " + (index + 1) + " 上");
}

一致性Hash算法的思路

1. 首先有一條直線，直線開頭和結尾分別定為1和2³²-1,這相當于一個地址
2. 對于這樣一條直線，首尾相連構成一個閉環，這樣的圓環稱為Hash環
3. 把服務器IP或者主機名求Hash值然后對應到Hash環上，針對客戶端IP求Hash值，對應到環上的某個位置，然后按照順時針的方向找最近的服務器節點

• 縮容
  假設將節點3下線，原來路由到3的客戶端請求重新路由到節點4，對于其他客戶端沒有影響，只是這一小部分受到影響
  請求的遷移量達到了最小，這樣的算法對于分布式集群來說非常合適，避免了大量請求轉移。

• 擴容
  新增節點5之后，原來路由到節點3的部分客戶端路由到了節點5上，對于其他客戶端沒有影響，只是這一小部分受到影響

代碼如下：

// 定義服務器IP
String[] servers = {"192.168.31.121", "192.168.3.21", "192.168.1.11", "12.168.31.121", "192.138.3.21", "192.68.1.11"};
// 定義客戶端IP
String[] clients = {"12.16.31.121", "12.18.3.1", "19.16.1.11"};
// 計算服務器的Hash，并放到排序的Map中
SortedMap<Integer,String> hashServerMap = new TreeMap<>();
for (String server : servers) {int hashCode = Math.abs(server.hashCode());hashServerMap.put(hashCode,server);
}
// 求客戶端IP的Hash，取出對應的服務器
for (String client : clients) {int clientHash = Math.abs(client.hashCode());SortedMap<Integer, String> tailedMap = hashServerMap.tailMap(clientHash);// 取出Hash環上的第一臺服務器Integer firstKey;if (tailedMap.isEmpty()){firstKey = hashServerMap.firstKey();}else {firstKey = tailedMap.firstKey();}System.out.println("客戶端IP\t"+ client +"\t被路由到了服務器\t" + hashServerMap.get(firstKey));
}

存在的問題及解決方法

如上所述，每一臺服務器負責一段，一致性Hash算法對于節點的增加都只需要重定位環空間的一小部分數據，具有較好的容錯性和可擴展性。

1. 一致性Hash算法在服務節點太少時，容易因節點分部不均勻造成數據傾斜問題。例如只有兩臺服務器，這兩臺服務器在環上的分部十分靠近，導致某個節點只負責非常小的一段，大量的請求落在了另外一個節點上，導致數據傾斜。
2. 為了解決這種方法，一致性Hash算法引入了虛擬節點機制，即對每一個服務節點計算多個Hash，每個計算結果都放置一個此服務節點，稱為虛擬節點。具體做法可以在服務器IP或者主機名后增加編號來實現，例如 “節點1的ip#1” “節點1的ip#2” “節點1的ip#3”……形成多個虛擬節點，當客戶端被路由到虛擬節點的時候其實是被路由到該虛擬節點所對應的真實節點。

代碼如下：

// 定義服務器IP
String[] servers = {"192.168.31.121", "192.168.3.21", "192.168.1.11", "12.168.31.121", "192.138.3.21", "192.68.1.11"};
// 定義客戶端IP
String[] clients = {"12.16.31.121", "12.18.3.1", "19.16.1.11"};SortedMap<Integer, String> serverHash = new TreeMap<>();int virtualNodeCount = 3;
// 開始計算服務器的Hash
for (String server : servers) {int hash = Math.abs(server.hashCode());serverHash.put(hash, server);// 設置虛擬節點for (int i = 0; i < virtualNodeCount; i++) {int virtualNodeHash = Math.abs((server + "#" + i).hashCode());serverHash.put(virtualNodeHash, "虛擬節點" + i + "映射過來的請求：" + server);}
}System.out.println(serverHash.size());
// 計算客戶端請求的服務器Hash
for (String client : clients) {int clientHash = Math.abs(client.hashCode());SortedMap<Integer, String> tailedMap = serverHash.tailMap(clientHash);if (tailedMap.isEmpty()) {Integer firstKey = serverHash.firstKey();System.out.println("客戶端：" + client + "\t\t路由到了 \t" + serverHash.get(firstKey));} else {Integer firstKey = tailedMap.firstKey();System.out.println("客戶端：" + client + "\t\t路由到了 \t" + serverHash.get(firstKey));}
}