一緻性Hash原理及應用
一、背景
在業務開發中，我們常把資料持久化到資料庫中。如果需要讀取這些資料，除了直接從資料庫中讀取外，為了減輕資料庫的通路壓力以及提高通路速度，我們更多地引入緩存來對資料進行存取。對于隻有單個緩存伺服器來說我們可以直接定位，那麼對于分布式情境下，我們又該如何處理呢？
二、引入
我們在使用Redis的時候，為了保證Redis的高可用，提高Redis的讀寫性能，最簡單的方式我們會做主從複制，組成Master-Master或者Master-Slave的形式，或者搭建Redis叢集，進行資料的讀寫分離，類似于資料庫的主從複制和讀寫分離。當我們的系統更加龐大，業務更加繁雜時，類似資料庫一樣，隻通過讀寫分離也無法滿足需求，這時我們可能需要分布式緩存：
IndexFor方法 (此處是位運算，跟取模的結果一樣) 是為了确定目前元素在數組上的位置，再去定位在連結清單上的位置，跟目前場景一樣為了定位，而我們要找的資料的key可能是字元串類型，我們可以通過取hash值再取模的方式來存取。那麼新的問題來了，如果我們其中的一台伺服器宕掉了或要添加新的伺服器，這個時候會發生什麼呢
三、原理
我們發現，使用取模的方式如1 mod 4 = 3, 2 mod 4 = 2...，如果我們加入一台伺服器，之前存儲在第3台伺服器上的資料現在取數都被分發到 1 mod 5 = 4 第4台伺服器上，結果就是找不到資料，如果這時候有大量的請求過來會全部去讀取資料庫，造成的結果就是緩存雪崩，對資料庫會帶來災難行的後果。為了解決這些問題，一緻性Hash算法出現了。
一緻性Hash算法也是通過取模來完成，不過它不再是對例如伺服器的數量來取模，而是對2^32 取模。算法原理即先構造一個2^32的整數環，根據伺服器節點名稱(或IP)的Hash值将伺服器節點放在這個環上，然後根據資料的key值計算得到起哈希值，接着在環上順時針查找距離這個key的Hash值最近的伺服器節點，完成key到伺服器的映射:
按照以上的假設，如果我們B節點宕掉了，按照規則B到A之間的資料會按照順時針去尋找下一個離它最近的節點，受影響的也隻有也隻會是此環空間中的一台伺服器的資料，增加一台伺服器同理。
四、問題
一緻性基本解決了以上問題，但是又暴露出另外一個問題---資料傾斜，即當服務節點過少而分部不均導緻大量的資料集中到其中一個節點，為了解決這種問題，一緻性Hash算法引入了虛拟節點機制，即将一個實體節點拆分為多個虛拟節點，并且同一個實體節點盡量均勻分布在Hash環上。
五、無虛拟節點代碼實作
public class ConsistentHashTest { static List<ServerNode> serverNodes= new ArrayList<ServerNode>(); // 真實機器節點 static class ServerNode{ private String nodeName; private long nodeHash; public ServerNode(String nodeName, long nodeHash) { super(); this.nodeName = nodeName; this.nodeHash = nodeHash; } public String getNodeName() { return nodeName; } public void setNodeName(String serverNodeName) { this.nodeName = serverNodeName; } public long getNodeHash() { return nodeHash; } public void setNodeHash(long serverNodeHash) { this.nodeHash = serverNodeHash; } } public long hash(String key){ int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } //得到應當路由到的伺服器結點 public ServerNode getServerNode(String key){ long hash = hash(key); for(ServerNode node: serverNodes){ //已排序，第一次找到大于這個節點即可 if(node.getNodeHash() > hash){ return node; } } //沒找到則在最後，依賴的即第一個 return serverNodes.get(0); } //添加伺服器節點 public void addServerNode(String serverNodeName){ long serverNodeHash = hash(serverNodeName); ServerNode serverNode = new ServerNode(serverNodeName,serverNodeHash); serverNodes.add(serverNode); //将serverNodes進行排序 Collections.sort(serverNodes, new Comparator<ServerNode>() { @Override public int compare(ServerNode node1, ServerNode node2) { if(node1.getNodeHash() < node2.getNodeHash()){ return -1; } return 1; } }); } //删除伺服器節點 public void deleteServerNode(String serverName){ for(ServerNode node: serverNodes){ if(serverName.equals(node.getNodeName())){ serverNodes.remove(node); return; } } } public static void main(String[] args){ ConsistentHashTest cht = new ConsistentHashTest(); //添加一系列的伺服器節點 String[] servers = {"10.0.0.20", "10.0.0.21","10.0.0.22", "10.0.0.23"}; for(String server: servers){ cht.addServerNode(server); } //列印輸出一下伺服器節點 System.out.println("所有的伺服器節點資訊如下："); for(ServerNode node: serverNodes){ System.out.println(node.getNodeName()+":"+node.getNodeHash()); } //看看下面的用戶端節點會被路由到哪個伺服器節點 String[] nodes = {"a.png", "b.png", "c.png"}; System.out.println("此時，各個用戶端的路由情況如下："); for(String node:nodes){ ServerNode serverNode = cht.getServerNode(node); System.out.println(node + "路由到" + serverNode.getNodeName()+","+serverNode.getNodeHash()); } //删除節點，發現所有用戶端都在23上，然後就删除23節點 cht.deleteServerNode("10.0.0.20"); System.out.println("删除20節點後，再看看同樣的用戶端的路由情況，如下："); for(String node:nodes){ ServerNode serverNode = cht.getServerNode(node); System.out.println(node + "路由到" + serverNode.getNodeName()+","+serverNode.getNodeHash()); } //删除20節點沒有影響，然後就删除23節點 cht.deleteServerNode("10.0.0.23"); System.out.println("删除23節點後，再看看同樣的用戶端的路由情況，如下："); for(String node:nodes){ ServerNode serverNode = cht.getServerNode(node); System.out.println(node + "路由到" + serverNode.getNodeName()+","+serverNode.getNodeHash()); } } 參考資料：
https://blog.csdn.net/u010412719/article/details/53863219