一缩麸、一般算法：
對對象先hash然后對redis數量取模铸磅，如果結果是0就存在0的節(jié)點上。
1杭朱、2同上阅仔，假設有0-3四個redis節(jié)點、20個數據：
進行取模后分布如下：
現在因為壓力過大需要擴容弧械，增加一臺redis4八酒、第五個節(jié)點：
現在只有4個節(jié)點還能夠命中。命中率是：4/20 = 20%,命中率極其低下刃唐。（redis肯定是不會這樣用的）
二羞迷、redis使用的consistent hashing(一致性hash算法)
1、環(huán)形hash空間：
把對象映射到0-2^32-1的空間里画饥。
2衔瓮、把數據通過一定的hash算法處理后映射到環(huán)上
現在假設有4個對象：object1-object4，將四個對象hash后映射到環(huán)形空間中：
3抖甘、把chche映射到hash空間
（基本思想就是講對象和cache都映射到同一hash數值空間中热鞍，并且使用相同的hash算法，可以使用cache的ip地址或者其他因子）,假設現在有三個cache：
4、機器的刪除與添加
每個key順時針往下走薇宠，找到的第一個cache節(jié)點就是存儲位置：
現在移除一個cacheB節(jié)點偷办、這時候key4將找不到cache，key4繼續(xù)使用一致性hash算法運算后算出最新的cacheC昼接，以后存儲與讀取都將在cacheC上：
移除節(jié)點后的影響范圍在該節(jié)點逆時針計算到遇到的第一個cache節(jié)點之間的數據節(jié)點爽篷。
現在看一下增加一個節(jié)點：
影響范圍為：添加節(jié)點逆時針遇到的第一個cache節(jié)點之間的數據節(jié)點悴晰。
5慢睡、平衡性
根據上面的圖解分析，一致性哈希算法滿足了單調性和負載均衡的特性以及一般hash算法的分散性铡溪，但這還并不能當做其被廣泛應用的原由漂辐，因為還缺少了平衡性。下面將分析一致性哈希算法是如何滿足平衡性的棕硫。
hash算法是不保證平衡的髓涯，如上面只部署了NODE1和NODE3的情況（NODE2被刪除的圖），object1存儲到了NODE1中哈扮，而object2纬纪、object3、object4都存儲到了NODE3中滑肉，這樣NODE3節(jié)點由于承擔了NODE2節(jié)點的數據包各，所以NODE3節(jié)點的負載會變高，NODE3節(jié)點很容易也宕機靶庙，這樣依次下去可能造成整個集群都掛了问畅。
在一致性哈希算法中，為了盡可能的滿足平衡性六荒，其引入了虛擬節(jié)點护姆。“虛擬節(jié)點”（ virtual node ）是實際節(jié)點（機器）在 hash 空間的復制品（replica）掏击，一實際個節(jié)點（機器）對應了若干個“虛擬節(jié)點”卵皂，這個對應個數也成為“復制個數”，“虛擬節(jié)點”在 hash 空間中以hash值排列砚亭。即把想象在這個環(huán)上有很多“虛擬節(jié)點”灯变，數據的存儲是沿著環(huán)的順時針方向找一個虛擬節(jié)點，每個虛擬節(jié)點都會關聯到一個真實節(jié)點钠惩。
圖中的A1柒凉、A2、B1篓跛、B2膝捞、C1、C2、D1蔬咬、D2都是虛擬節(jié)點鲤遥，機器A負載存儲A1、A2的數據林艘，機器B負載存儲B1盖奈、B2的數據，機器C負載存儲C1狐援、C2的數據钢坦。由于這些虛擬節(jié)點數量很多，均勻分布啥酱，因此不會造成“雪崩”現象爹凹。
使用虛擬節(jié)點的思想，為每個物理節(jié)點（服務器）在圓上分配100～200個點镶殷。這樣就能抑制分布不均勻禾酱，最大限度地減小服務器增減時的緩存重新分布。用戶數據映射在虛擬節(jié)點上绘趋，就表示用戶數據真正存儲位置是在該虛擬節(jié)點代表的實際物理服務器上颤陶。
下面有一個圖描述了需要為每臺物理服務器增加的虛擬節(jié)點。
x軸表示的是需要為每臺物理服務器擴展的虛擬節(jié)點倍數(scale)陷遮，y軸是實際物理服務器數滓走，可以看出，當物理服務器的數量很小時拷呆，需要更大的虛擬節(jié)點闲坎，反之則需要更少的節(jié)點，從圖上可以看出茬斧，在物理服務器有10臺時腰懂，差不多需要為每臺服務器增加100~200個虛擬節(jié)點才能達到真正的負載均衡。
簡單的java代碼實現：
class ConsistentHash<T> {
/**
* 哈希函數
*/
private final HashFunction hashFunction;
/**
* 虛擬節(jié)點數 项秉， 越大分布越均衡绣溜，但越大，在初始化和變更的時候效率差一點娄蔼。 測試中怖喻，設置200基本就均衡了。
*/
private final int numberOfReplicas;
/**
* 環(huán)形Hash空間
*/
private final SortedMap<Integer, T> circle = new TreeMap<Integer, T>();
/**
* @param hashFunction
* 岁诉，哈希函數
* @param numberOfReplicas
* 锚沸，虛擬服務器系數
* @param nodes
* ，服務器節(jié)點
*/
public ConsistentHash(HashFunction hashFunction, int numberOfReplicas,
Collection<T> nodes) {
this.hashFunction = hashFunction;
this.numberOfReplicas = numberOfReplicas;
for (T node : nodes) {
this.addNode(node);
}
}
/**
* 添加物理節(jié)點涕癣，每個node 會產生numberOfReplicas個虛擬節(jié)點哗蜈，這些虛擬節(jié)點對應的實際節(jié)點是node
*/
public void addNode(T node) {
for (int i = 0; i < numberOfReplicas; i++) {
int hashValue = hashFunction.hash(node.toString() + i);
circle.put(hashValue, node);
}
}
/**移除物理節(jié)點，將node產生的numberOfReplicas個虛擬節(jié)點全部移除
* @param node
*/
public void removeNode(T node) {
for (int i = 0; i < numberOfReplicas; i++) {
int hashValue = hashFunction.hash(node.toString() + i);
circle.remove(hashValue);
}
}
/**
* 得到映射的物理節(jié)點
*
* @param key
* @return
*/
public T getNode(Object key) {
if (circle.isEmpty()) {
return null;
}
int hashValue = hashFunction.hash(key);
// System.out.println("key---" + key + " : hash---" + hash);
if (!circle.containsKey(hashValue)) {
// 返回鍵大于或等于hash的node，即沿環(huán)的順時針找到一個虛擬節(jié)點
SortedMap<Integer, T> tailMap = circle.tailMap(hashValue);
// System.out.println(tailMap);
// System.out.println(circle.firstKey());
hashValue = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
}
// System.out.println("hash---: " + hash);
return circle.get(hashValue);
}
static class HashFunction {
/**
* MurMurHash算法距潘，是非加密HASH算法炼列，性能很高，
* 比傳統的CRC32,MD5音比，SHA-1（這兩個算法都是加密HASH算法俭尖，復雜度本身就很高，帶來的性能上的損害也不可避免）
* 等HASH算法要快很多洞翩，而且據說這個算法的碰撞率很低. http://murmurhash.googlepages.com/
*/
int hash(Object key) {
ByteBuffer buf = ByteBuffer.wrap(key.toString().getBytes());
int seed = 0x1234ABCD;
ByteOrder byteOrder = buf.order();
buf.order(ByteOrder.LITTLE_ENDIAN);
long m = 0xc6a4a7935bd1e995L;
int r = 47;
long h = seed ^ (buf.remaining() * m);
long k;
while (buf.remaining() >= 8) {
k = buf.getLong();
k *= m;
k ^= k >>> r;
k *= m;
h ^= k;
h *= m;
}
if (buf.remaining() > 0) {
ByteBuffer finish = ByteBuffer.allocate(8).order(
ByteOrder.LITTLE_ENDIAN);
finish.put(buf).rewind();
h ^= finish.getLong();
h *= m;
}
h ^= h >>> r;
h *= m;
h ^= h >>> r;
buf.order(byteOrder);
return (int) h;
}
}
}
public class Test {
public static void main(String[] args) {
HashSet<String> serverNode = new HashSet<String>();
serverNode.add("127.1.1.1#A");
serverNode.add("127.2.2.2#B");
serverNode.add("127.3.3.3#C");
serverNode.add("127.4.4.4#D");
Map<String, Integer> serverNodeMap = new HashMap<String, Integer>();
ConsistentHash<String> consistentHash = new ConsistentHash<String>(
new HashFunction(), 200, serverNode);
int count = 50000;
for (int i = 0; i < count; i++) {
String serverNodeName = consistentHash.getNode(i);
// System.out.println(i + " 映射到物理節(jié)點---" + serverNodeName);
if (serverNodeMap.containsKey(serverNodeName)) {
serverNodeMap.put(serverNodeName,
serverNodeMap.get(serverNodeName) + 1);
} else {
serverNodeMap.put(serverNodeName, 1);
}
}
// System.out.println(serverNodeMap);
showServer(serverNodeMap);
serverNodeMap.clear();
consistentHash.removeNode("127.1.1.1#A");
System.out.println("-------------------- remove 127.1.1.1#A");
for (int i = 0; i < count; i++) {
String serverNodeName = consistentHash.getNode(i);
// System.out.println(i + " 映射到物理節(jié)點---" + serverNodeName);
if (serverNodeMap.containsKey(serverNodeName)) {
serverNodeMap.put(serverNodeName,
serverNodeMap.get(serverNodeName) + 1);
} else {
serverNodeMap.put(serverNodeName, 1);
}
}
showServer(serverNodeMap);
serverNodeMap.clear();
consistentHash.addNode("127.5.5.5#E");
System.out.println("-------------------- add 127.5.5.5#E");
for (int i = 0; i < count; i++) {
String serverNodeName = consistentHash.getNode(i);
// System.out.println(i + " 映射到物理節(jié)點---" + serverNodeName);
if (serverNodeMap.containsKey(serverNodeName)) {
serverNodeMap.put(serverNodeName,
serverNodeMap.get(serverNodeName) + 1);
} else {
serverNodeMap.put(serverNodeName, 1);
}
}
showServer(serverNodeMap);
serverNodeMap.clear();
consistentHash.addNode("127.6.6.6#F");
System.out.println("-------------------- add 127.6.6.6#F");
count *= 2;
System.out.println("-------------------- 業(yè)務量加倍");
for (int i = 0; i < count; i++) {
String serverNodeName = consistentHash.getNode(i);
// System.out.println(i + " 映射到物理節(jié)點---" + serverNodeName);
if (serverNodeMap.containsKey(serverNodeName)) {
serverNodeMap.put(serverNodeName,
serverNodeMap.get(serverNodeName) + 1);
} else {
serverNodeMap.put(serverNodeName, 1);
}
}
showServer(serverNodeMap);
}
/**
* 服務器運行狀態(tài)
*
* @param map
*/
public static void showServer(Map<String, Integer> map) {
for (Entry<String, Integer> m : map.entrySet()) {
System.out.println(m.getKey() + ", 存儲數據量 " + m.getValue());
}
}
運行結果：
127.4.4.4#D, 存儲數據量 13177
127.2.2.2#B, 存儲數據量 11834
127.3.3.3#C, 存儲數據量 12827
127.1.1.1#A, 存儲數據量 12162
-------------------- remove 127.1.1.1#A
127.4.4.4#D, 存儲數據量 17696
127.2.2.2#B, 存儲數據量 15114
127.3.3.3#C, 存儲數據量 17190
-------------------- add 127.5.5.5#E
127.4.4.4#D, 存儲數據量 12154
127.2.2.2#B, 存儲數據量 11878
127.3.3.3#C, 存儲數據量 12908
127.5.5.5#E, 存儲數據量 13060
-------------------- add 127.6.6.6#F
-------------------- 業(yè)務量加倍
127.4.4.4#D, 存儲數據量 18420
127.2.2.2#B, 存儲數據量 20197
127.6.6.6#F, 存儲數據量 21015
127.5.5.5#E, 存儲數據量 19038
127.3.3.3#C, 存儲數據量 21330
6稽犁、缺陷
一致性hash存在數據不一致問題：分析如下步驟
- NODE2 存儲Key2 = 100
- 此時NODE2掛了，key2 = 200 會落到object2內
- NODE2再次恢復菱农，但NODE2 key2 = 100缭付，而object2 key2 = 200，數據不一致循未。
