~~~ import java.security.MessageDigest; import java.security.NoSuchAlgorithmException; import java.util.Collection; import java.util.SortedMap; import java.util.TreeMap; /** * 一致性Hash算法 * * @param <T> 節點類型 */ public class ConsistentHash<T> { /** * Hash計算對象，用于自定義hash算法 */ HashFunc hashFunc; /** * 復制的節點個數 */ private final int numberOfReplicas; /** * 一致性Hash環 */ private final SortedMap<Long, T> circle = new TreeMap<>(); /** * 構造，使用Java默認的Hash算法 * @param numberOfReplicas 復制的節點個數，增加每個節點的復制節點有利于負載均衡 * @param nodes 節點對象 */ public ConsistentHash(int numberOfReplicas, Collection<T> nodes) { this.numberOfReplicas = numberOfReplicas; this.hashFunc = new HashFunc() { @Override public Long hash(Object key) { // return fnv1HashingAlg(key.toString()); return md5HashingAlg(key.toString()); } }; //初始化節點 for (T node : nodes) { add(node); } } /** * 構造 * @param hashFunc hash算法對象 * @param numberOfReplicas 復制的節點個數，增加每個節點的復制節點有利于負載均衡 * @param nodes 節點對象 */ public ConsistentHash(HashFunc hashFunc, int numberOfReplicas, Collection<T> nodes) { this.numberOfReplicas = numberOfReplicas; this.hashFunc = hashFunc; //初始化節點 for (T node : nodes) { add(node); } } /** * 增加節點<br> * 每增加一個節點，就會在閉環上增加給定復制節點數<br> * 例如復制節點數是2，則每調用此方法一次，增加兩個虛擬節點，這兩個節點指向同一Node * 由于hash算法會調用node的toString方法，故按照toString去重 * * @param node 節點對象 */ public void add(T node) { for (int i = 0; i < numberOfReplicas; i++) { circle.put(hashFunc.hash(node.toString() + i), node); } } /** * 移除節點的同時移除相應的虛擬節點 * * @param node 節點對象 */ public void remove(T node) { for (int i = 0; i < numberOfReplicas; i++) { circle.remove(hashFunc.hash(node.toString() + i)); } } /** * 獲得一個最近的順時針節點 * * @param key 為給定鍵取Hash，取得順時針方向上最近的一個虛擬節點對應的實際節點 * @return 節點對象 */ public T get(Object key) { if (circle.isEmpty()) { return null; } long hash = hashFunc.hash(key); if (!circle.containsKey(hash)) { SortedMap<Long, T> tailMap = circle.tailMap(hash); //返回此映射的部分視圖，其鍵大于等于 hash hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey(); } //正好命中 return circle.get(hash); } /** * 使用MD5算法 * @param key * @return */ private static long md5HashingAlg(String key) { MessageDigest md5 = null; try { md5 = MessageDigest.getInstance("MD5"); md5.reset(); md5.update(key.getBytes()); byte[] bKey = md5.digest(); long res = ((long) (bKey[3] & 0xFF) << 24) | ((long) (bKey[2] & 0xFF) << 16) | ((long) (bKey[1] & 0xFF) << 8)| (long) (bKey[0] & 0xFF); return res; } catch (NoSuchAlgorithmException e) { e.printStackTrace(); } return 0l; } /** * 使用FNV1hash算法 * @param key * @return */ private static long fnv1HashingAlg(String key) { final int p = 16777619; int hash = (int) 2166136261L; for (int i = 0; i < key.length(); i++) hash = (hash ^ key.charAt(i)) * p; hash += hash << 13; hash ^= hash >> 7; hash += hash << 3; hash ^= hash >> 17; hash += hash << 5; return hash; } /** * Hash算法對象，用于自定義hash算法 */ public interface HashFunc { public Long hash(Object key); } } ~~~ Consistent Hashing最大限度地抑制了hash鍵的重新分布。另外要取得比較好的負載均衡的效果，往往在服務器數量比較少的時候需要增加虛擬節點來保證服務器能均勻的分布在圓環上。因為使用一般的hash方法，服務器的映射地點的分布非常不均勻。使用虛擬節點的思想，為每個物理節點（服務器）在圓上分配100～200個點。這樣就能抑制分布不均勻，最大限度地減小服務器增減時的緩存重新分布。用戶數據映射在虛擬節點上，就表示用戶數據真正存儲位置是在該虛擬節點代表的實際物理服務器上