一、一般算法：
對對象先hash然后對redis數(shù)量取模，如果結(jié)果是0就存在0的節(jié)點上。
1、2同上，假設(shè)有0-3四個redis節(jié)點、20個數(shù)據(jù)：
進行取模后分布如下：
現(xiàn)在因為壓力過大需要擴容，增加一臺redis4、第五個節(jié)點：
現(xiàn)在只有4個節(jié)點還能夠命中。命中率是：4/20 = 20%,命中率極其低下。（redis肯定是不會這樣用的）
二、redis使用的consistent hashing(一致性hash算法)
1、環(huán)形hash空間：
把對象映射到0-2^32-1的空間里。
2、把數(shù)據(jù)通過一定的hash算法處理后映射到環(huán)上
現(xiàn)在假設(shè)有4個對象：object1-object4，將四個對象hash后映射到環(huán)形空間中：
3、把chche映射到hash空間
（基本思想就是講對象和cache都映射到同一hash數(shù)值空間中，并且使用相同的hash算法，可以使用cache的ip地址或者其他因子）,假設(shè)現(xiàn)在有三個cache：
4、機器的刪除與添加
每個key順時針往下走，找到的第一個cache節(jié)點就是存儲位置：
現(xiàn)在移除一個cacheB節(jié)點、這時候key4將找不到cache，key4繼續(xù)使用一致性hash算法運算后算出最新的cacheC，以后存儲與讀取都將在cacheC上：
移除節(jié)點后的影響范圍在該節(jié)點逆時針計算到遇到的第一個cache節(jié)點之間的數(shù)據(jù)節(jié)點。
現(xiàn)在看一下增加一個節(jié)點：
影響范圍為：添加節(jié)點逆時針遇到的第一個cache節(jié)點之間的數(shù)據(jù)節(jié)點。
5、平衡性
根據(jù)上面的圖解分析，一致性哈希算法滿足了單調(diào)性和負載均衡的特性以及一般hash算法的分散性，但這還并不能當做其被廣泛應(yīng)用的原由，因為還缺少了平衡性。下面將分析一致性哈希算法是如何滿足平衡性的。
hash算法是不保證平衡的，如上面只部署了NODE1和NODE3的情況（NODE2被刪除的圖），object1存儲到了NODE1中，而object2、object3、object4都存儲到了NODE3中，這樣NODE3節(jié)點由于承擔了NODE2節(jié)點的數(shù)據(jù)，所以NODE3節(jié)點的負載會變高，NODE3節(jié)點很容易也宕機，這樣依次下去可能造成整個集群都掛了。
在一致性哈希算法中，為了盡可能的滿足平衡性，其引入了虛擬節(jié)點?！疤摂M節(jié)點”（ virtual node ）是實際節(jié)點（機器）在 hash 空間的復(fù)制品（replica），一實際個節(jié)點（機器）對應(yīng)了若干個“虛擬節(jié)點”，這個對應(yīng)個數(shù)也成為“復(fù)制個數(shù)”，“虛擬節(jié)點”在 hash 空間中以hash值排列。即把想象在這個環(huán)上有很多“虛擬節(jié)點”，數(shù)據(jù)的存儲是沿著環(huán)的順時針方向找一個虛擬節(jié)點，每個虛擬節(jié)點都會關(guān)聯(lián)到一個真實節(jié)點。
圖中的A1、A2、B1、B2、C1、C2、D1、D2都是虛擬節(jié)點，機器A負載存儲A1、A2的數(shù)據(jù)，機器B負載存儲B1、B2的數(shù)據(jù)，機器C負載存儲C1、C2的數(shù)據(jù)。由于這些虛擬節(jié)點數(shù)量很多，均勻分布，因此不會造成“雪崩”現(xiàn)象。
使用虛擬節(jié)點的思想，為每個物理節(jié)點（服務(wù)器）在圓上分配100～200個點。這樣就能抑制分布不均勻，最大限度地減小服務(wù)器增減時的緩存重新分布。用戶數(shù)據(jù)映射在虛擬節(jié)點上，就表示用戶數(shù)據(jù)真正存儲位置是在該虛擬節(jié)點代表的實際物理服務(wù)器上。
下面有一個圖描述了需要為每臺物理服務(wù)器增加的虛擬節(jié)點。
x軸表示的是需要為每臺物理服務(wù)器擴展的虛擬節(jié)點倍數(shù)(scale)，y軸是實際物理服務(wù)器數(shù)，可以看出，當物理服務(wù)器的數(shù)量很小時，需要更大的虛擬節(jié)點，反之則需要更少的節(jié)點，從圖上可以看出，在物理服務(wù)器有10臺時，差不多需要為每臺服務(wù)器增加100~200個虛擬節(jié)點才能達到真正的負載均衡。
簡單的java代碼實現(xiàn)：
class ConsistentHash<T> {
/**
* 哈希函數(shù)
*/
private final HashFunction hashFunction;
/**
* 虛擬節(jié)點數(shù) ， 越大分布越均衡，但越大，在初始化和變更的時候效率差一點。 測試中，設(shè)置200基本就均衡了。
*/
private final int numberOfReplicas;
/**
* 環(huán)形Hash空間
*/
private final SortedMap<Integer, T> circle = new TreeMap<Integer, T>();
/**
* @param hashFunction
* ，哈希函數(shù)
* @param numberOfReplicas
* ，虛擬服務(wù)器系數(shù)
* @param nodes
* ，服務(wù)器節(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 會產(chǎn)生numberOfReplicas個虛擬節(jié)點，這些虛擬節(jié)點對應(yīng)的實際節(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產(chǎn)生的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算法，性能很高，
* 比傳統(tǒng)的CRC32,MD5，SHA-1（這兩個算法都是加密HASH算法，復(fù)雜度本身就很高，帶來的性能上的損害也不可避免）
* 等HASH算法要快很多，而且據(jù)說這個算法的碰撞率很低. 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è)務(wù)量加倍");
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);
}
/**
* 服務(wù)器運行狀態(tài)
*
* @param map
*/
public static void showServer(Map<String, Integer> map) {
for (Entry<String, Integer> m : map.entrySet()) {
System.out.println(m.getKey() + ", 存儲數(shù)據(jù)量 " + m.getValue());
}
}
運行結(jié)果：
127.4.4.4#D, 存儲數(shù)據(jù)量 13177
127.2.2.2#B, 存儲數(shù)據(jù)量 11834
127.3.3.3#C, 存儲數(shù)據(jù)量 12827
127.1.1.1#A, 存儲數(shù)據(jù)量 12162
-------------------- remove 127.1.1.1#A
127.4.4.4#D, 存儲數(shù)據(jù)量 17696
127.2.2.2#B, 存儲數(shù)據(jù)量 15114
127.3.3.3#C, 存儲數(shù)據(jù)量 17190
-------------------- add 127.5.5.5#E
127.4.4.4#D, 存儲數(shù)據(jù)量 12154
127.2.2.2#B, 存儲數(shù)據(jù)量 11878
127.3.3.3#C, 存儲數(shù)據(jù)量 12908
127.5.5.5#E, 存儲數(shù)據(jù)量 13060
-------------------- add 127.6.6.6#F
-------------------- 業(yè)務(wù)量加倍
127.4.4.4#D, 存儲數(shù)據(jù)量 18420
127.2.2.2#B, 存儲數(shù)據(jù)量 20197
127.6.6.6#F, 存儲數(shù)據(jù)量 21015
127.5.5.5#E, 存儲數(shù)據(jù)量 19038
127.3.3.3#C, 存儲數(shù)據(jù)量 21330
6、缺陷
一致性hash存在數(shù)據(jù)不一致問題：分析如下步驟
- NODE2 存儲Key2 = 100
- 此時NODE2掛了，key2 = 200 會落到object2內(nèi)
- NODE2再次恢復(fù)，但NODE2 key2 = 100，而object2 key2 = 200，數(shù)據(jù)不一致。
