一莲祸、前言
這次我們來(lái)討論下redis cluster依賴(lài)的一個(gè)核心的算法赂韵，一致性哈希算法。我們都知道税产，redis cluster能夠做到動(dòng)態(tài)地?cái)U(kuò)容，在擴(kuò)容的過(guò)程中如何保證數(shù)據(jù)的遷移盡可能地型当馈辟拷？
如果采用傳統(tǒng)的hash(object)%N算法，那么在有機(jī)器添加或者刪除后阐斜，幾乎所有數(shù)據(jù)都要做一次大的遷移衫冻，這是我們不希望看到的結(jié)果，那么一致性哈希是如何解決這個(gè)問(wèn)題的谒出。
二羽杰、標(biāo)準(zhǔn)
一致性hash算法提出了在動(dòng)態(tài)變化的Cache環(huán)境中渡紫，判定哈希算法好壞的四個(gè)定義：
1.平衡性(Balance)：平衡性是指哈希的結(jié)果能夠盡可能分布到所有的緩沖中去，這樣可以使得所有的緩沖空間都得到利用考赛。很多哈希算法都能夠滿足這一條件。
2.單調(diào)性(Monotonicity)：?jiǎn)握{(diào)性是指如果已經(jīng)有一些內(nèi)容通過(guò)哈希分派到了相應(yīng)的緩沖中莉测，又有新的緩沖加入到系統(tǒng)中颜骤。哈希的結(jié)果應(yīng)能夠保證原有已分配的內(nèi)容可以被映射到原有的或者新的緩沖中去，而不會(huì)被映射到舊的緩沖集合中的其他緩沖區(qū)捣卤。
3.分散性(Spread)：在分布式環(huán)境中忍抽，終端有可能看不到所有的緩沖，而是只能看到其中的一部分董朝。當(dāng)終端希望通過(guò)哈希過(guò)程將內(nèi)容映射到緩沖上時(shí)鸠项，由于不同終端所見(jiàn)的緩沖范圍有可能不同，從而導(dǎo)致哈希的結(jié)果不一致子姜，最終的結(jié)果是相同的內(nèi)容被不同的終端映射到不同的緩沖區(qū)中祟绊。這種情況顯然是應(yīng)該避免的，因?yàn)樗鼘?dǎo)致相同內(nèi)容被存儲(chǔ)到不同緩沖中去哥捕，降低了系統(tǒng)存儲(chǔ)的效率牧抽。分散性的定義就是上述情況發(fā)生的嚴(yán)重程度。好的哈希算法應(yīng)能夠盡量避免不一致的情況發(fā)生遥赚，也就是盡量降低分散性扬舒。
4.負(fù)載(Load)：負(fù)載問(wèn)題實(shí)際上是從另一個(gè)角度看待分散性問(wèn)題。既然不同的終端可能將相同的內(nèi)容映射到不同的緩沖區(qū)中凫佛，那么對(duì)于一個(gè)特定的緩沖區(qū)而言讲坎，也可能被不同的用戶映射為不同 的內(nèi)容。與分散性一樣愧薛，這種情況也是應(yīng)當(dāng)避免的晨炕，因此好的哈希算法應(yīng)能夠盡量降低緩沖的負(fù)荷。
三厚满、圖解
一致性哈希圖解
這篇文章介紹得很清楚府瞄，所以這里就不再重復(fù)了。這里只提一點(diǎn)：
虛擬結(jié)點(diǎn)的作用：
物理結(jié)點(diǎn)普遍的數(shù)量不會(huì)很多碘箍，如果直接以物理結(jié)點(diǎn)作為hash遵馆，很有可能數(shù)據(jù)分布會(huì)很不均勻，因此這里引入虛擬結(jié)點(diǎn)希望把結(jié)點(diǎn)的數(shù)據(jù)增加丰榴，最終達(dá)到一個(gè)盡可能平衡的狀態(tài)货邓。
- 那么實(shí)際redis的虛擬結(jié)點(diǎn)復(fù)制數(shù)量是多少？如何定義一個(gè)合理的復(fù)制數(shù)量
- 新增結(jié)點(diǎn)的時(shí)候如何把這個(gè)新的結(jié)點(diǎn)信息同步到各個(gè)客戶端四濒？這里又會(huì)涉及到數(shù)據(jù)同步的問(wèn)題换况，客戶端同步到新結(jié)點(diǎn)的數(shù)據(jù)职辨，但是redis的key還沒(méi)進(jìn)行遷移，怎么辦戈二？
四舒裤、源碼
HashFunction.java
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
/*
* 實(shí)現(xiàn)一致性哈希算法中使用的哈希函數(shù),使用MD5算法來(lái)保證一致性哈希的平衡性
*/
public class HashFunction {
private MessageDigest md5 = null;
public long hash(String key) {
if (md5 == null) {
try {
md5 = MessageDigest.getInstance("MD5");
} catch (NoSuchAlgorithmException e) {
throw new IllegalStateException("no md5 algrithm found");
}
}
md5.reset();
md5.update(key.getBytes());
byte[] bKey = md5.digest();
//具體的哈希函數(shù)實(shí)現(xiàn)細(xì)節(jié)--每個(gè)字節(jié) & 0xFF 再移位
long result = ((long) (bKey[3] & 0xFF) << 24)
| ((long) (bKey[2] & 0xFF) << 16
| ((long) (bKey[1] & 0xFF) << 8) | (long) (bKey[0] & 0xFF));
return result & 0xffffffffL;
}
}
ConsistentHash.java
import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.SortedMap;
import java.util.SortedSet;
import java.util.TreeMap;
import java.util.TreeSet;
public class ConsistentHash<T> {
private final HashFunction hashFunction;
private final int numberOfReplicas;// 節(jié)點(diǎn)的復(fù)制因子,實(shí)際節(jié)點(diǎn)個(gè)數(shù) * numberOfReplicas =
// 虛擬節(jié)點(diǎn)個(gè)數(shù)
private final SortedMap<Long, T> circle = new TreeMap<Long, T>();// 存儲(chǔ)虛擬節(jié)點(diǎn)的hash值到真實(shí)節(jié)點(diǎn)的映射
public ConsistentHash(HashFunction hashFunction, int numberOfReplicas,
Collection<T> nodes) {
this.hashFunction = hashFunction;
this.numberOfReplicas = numberOfReplicas;
for (T node : nodes)
add(node);
}
public void add(T node) {
for (int i = 0; i < numberOfReplicas; i++)
// 對(duì)于一個(gè)實(shí)際機(jī)器節(jié)點(diǎn) node, 對(duì)應(yīng) numberOfReplicas 個(gè)虛擬節(jié)點(diǎn)
/*
* 不同的虛擬節(jié)點(diǎn)(i不同)有不同的hash值,但都對(duì)應(yīng)同一個(gè)實(shí)際機(jī)器node
* 虛擬node一般是均衡分布在環(huán)上的,數(shù)據(jù)存儲(chǔ)在順時(shí)針?lè)较虻奶摂Mnode上
*/
circle.put(hashFunction.hash(node.toString() + i), node);
}
public void remove(T node) {
for (int i = 0; i < numberOfReplicas; i++)
circle.remove(hashFunction.hash(node.toString() + i));
}
/*
* 獲得一個(gè)最近的順時(shí)針節(jié)點(diǎn),根據(jù)給定的key 取Hash
* 然后再取得順時(shí)針?lè)较蛏献罱囊粋€(gè)虛擬節(jié)點(diǎn)對(duì)應(yīng)的實(shí)際節(jié)點(diǎn)
* 再?gòu)膶?shí)際節(jié)點(diǎn)中取得 數(shù)據(jù)
*/
public T get(Object key) {
if (circle.isEmpty())
return null;
long hash = hashFunction.hash((String) key);// node 用String來(lái)表示,獲得node在哈希環(huán)中的hashCode
if (!circle.containsKey(hash)) {//數(shù)據(jù)映射在兩臺(tái)虛擬機(jī)器所在環(huán)之間,就需要按順時(shí)針?lè)较驅(qū)ふ覚C(jī)器
SortedMap<Long, T> tailMap = circle.tailMap(hash);
hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
}
return circle.get(hash);
}
public long getSize() {
return circle.size();
}
/*
* 查看MD5算法生成的hashCode值---表示整個(gè)哈希環(huán)中各個(gè)虛擬節(jié)點(diǎn)位置
*/
public void testBalance(){
Set<Long> sets = circle.keySet();//獲得TreeMap中所有的Key
SortedSet<Long> sortedSets= new TreeSet<Long>(sets);//將獲得的Key集合排序
for(Long hashCode : sortedSets){
System.out.println(hashCode);
}
System.out.println("----each location 's distance are follows: ----");
/*
* 查看用MD5算法生成的long hashCode 相鄰兩個(gè)hashCode的差值
*/
Iterator<Long> it = sortedSets.iterator();
Iterator<Long> it2 = sortedSets.iterator();
if(it2.hasNext())
it2.next();
long keyPre, keyAfter;
while(it.hasNext() && it2.hasNext()){
keyPre = it.next();
keyAfter = it2.next();
System.out.println(keyAfter - keyPre);
}
}
public static void main(String[] args) {
Set<String> nodes = new HashSet<String>();
nodes.add("A");
nodes.add("B");
nodes.add("C");
ConsistentHash<String> consistentHash = new ConsistentHash<String>(new HashFunction(), 10, nodes);
consistentHash.add("D");
System.out.println("hash circle size: " + consistentHash.getSize());
System.out.println("location of each node are follows: ");
consistentHash.testBalance();
//刪除結(jié)點(diǎn)，rehash
consistentHash.remove("D");
consistentHash.testBalance();
}
}
邏輯很簡(jiǎn)單觉吭，核心關(guān)注幾點(diǎn)：
- hash算法的實(shí)現(xiàn)
- 虛擬結(jié)點(diǎn)的數(shù)量如何維護(hù)
circle - 一個(gè)key如何定義存放在哪個(gè)虛擬結(jié)點(diǎn)腾供？
public T get(Object key)，取順時(shí)針最近的結(jié)點(diǎn) - 虛擬結(jié)點(diǎn)和物理結(jié)點(diǎn)如何映射鲜滩？
circle.put(hashFunction.hash(node.toString() + i), node);其中i是第i個(gè)虛擬結(jié)點(diǎn)
五伴鳖、總結(jié)
后面把redis的核心源碼撈出來(lái)好好讀讀，盡量對(duì)redis和redis cluster有一個(gè)更深刻的認(rèn)識(shí)徙硅。
參考文獻(xiàn)
源碼分析
https://www.cnblogs.com/hapjin/p/4737207.html
圖解
https://blog.csdn.net/cywosp/article/details/23397179
