1，對于待存儲的海量數(shù)據(jù)，如何將它們分配到各個機器中去？---數(shù)據(jù)分片與路由
當(dāng)數(shù)據(jù)量很大時推掸，通過改善單機硬件資源的縱向擴充方式來存儲數(shù)據(jù)變得越來越不適用，而通過增加機器數(shù)目來獲得水平橫向擴展的方式則越來越流行谅畅。因此噪服，就有個問題粘优，如何將這些海量的數(shù)據(jù)分配到各個機器中雹顺？數(shù)據(jù)分布到各個機器存儲之后，又如何進行查找贩挣？這里主要記錄一致性Hash算法如何將數(shù)據(jù)分配到各個機器中去揽惹。
2搪搏，衡量一致性哈希算法好處的四個標(biāo)準(zhǔn)：
①平衡性：平衡性是指哈希的結(jié)果能夠盡可能分布到所有的緩沖中去疯溺，這樣可以使得所有的緩沖空間都得到利用囱嫩。②單調(diào)性：單調(diào)性是指如果已經(jīng)有一些數(shù)據(jù)通過哈希分配到了相應(yīng)的機器上漏设，又有新的機器加入到系統(tǒng)中。哈希的結(jié)果應(yīng)能夠保證原有已分配的內(nèi)容可以被映射到原有的或者新的機器中去鸳碧，而不會被映射到舊的機器集合中的其他機器上。
這里再解釋一下：就是原有的數(shù)據(jù)要么還是呆在它所在的機器上不動腾仅，要么被遷移到新的機器上套利，而不會遷移到舊的其他機器上。
③分散性：④負載：參考這里：blog.csdn.net/cywosp/article/details/23397179
3验辞，一致性哈希的原理：
由于一般的哈希函數(shù)返回一個int（32bit）型的hashCode受神。因此，可以將該哈希函數(shù)能夠返回的hashCode表示成一個范圍為0---（2^32）-1 環(huán)联四。
將機器的標(biāo)識（如：IP地址）作為哈希函數(shù)的Key映射到環(huán)上朝墩。如：
hash(Node1) =Key1 hash(Node2) = Key2收苏，借用一張圖如下：
同樣，數(shù)據(jù)也通過相同的哈希函數(shù)映射到環(huán)上秆乳。這樣屹堰，按照順時針方向肛冶，數(shù)據(jù)存放在它所在的順時針方向上的那個機器上。這就是一致性哈希算法分配數(shù)據(jù)的方式扯键！
4，JAVA實現(xiàn)一致性哈希算法的代碼分析：
?設(shè)計哈希函數(shù)
這里采用了MD5算法荣刑，主要是用來保證平衡性伦乔，即能夠?qū)C器均衡地映射到環(huán)上。貌似用Jdk中String類的hashCode并不能很好的保證平衡性评矩。
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
/** 實現(xiàn)一致性哈希算法中使用的哈希函數(shù),使用MD5算法來保證一致性哈希的平衡性*/
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ù)實現(xiàn)細節(jié)--每個字節(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;
}}
?實現(xiàn)一致性哈希算法：
為什么要引入虛擬機器節(jié)點？它的作用是什么阱飘？
引入虛擬機器節(jié)點斥杜，其目的就是為了解決數(shù)據(jù)分配不均衡的問題沥匈。因為蔗喂，在將實際的物理機器映射到環(huán)上時缰儿，有可能大部分機器都映射到環(huán)上的某一個部分(比如左半圓上)，而通過引入虛擬機器節(jié)點瞪浸，在進行機器hash映射時，不是映射具體機器对蒲，而是映射虛擬機器蹈矮，并保證虛擬機器對應(yīng)的物理機器是均衡的---每臺實際的機器對應(yīng)著相等數(shù)目的Virtual nodes。如下圖：
如何解決集群中添加或者刪除機器上需要遷移大量數(shù)據(jù)的問題鸣驱？
假設(shè)采用傳統(tǒng)的哈希取模法泛鸟，設(shè)有K臺物理機，H(key)=hash(key) mod K 即可實現(xiàn)數(shù)據(jù)分片踊东。但當(dāng)K變化時（如新增一臺機器）谈况，所有已經(jīng)映射好的數(shù)據(jù)都需要重新再映射。H(key)=hash(key) mod (K+1)递胧。
一致性哈希采用的做法如下：引入一個環(huán)的概念碑韵，如上面的第一個圖。先將機器映射到這個環(huán)上缎脾，再將數(shù)據(jù)也通過相同的哈希函數(shù)映射到這個環(huán)上祝闻，數(shù)據(jù)存儲在它順時針走向的那臺機器上。以環(huán)為中介，實現(xiàn)了數(shù)據(jù)與機器數(shù)目之間的解藕联喘。這樣华蜒，當(dāng)機器的數(shù)目變化時，只會影響到增加或刪除的那臺機器所在的環(huán)的鄰接機器的數(shù)據(jù)存儲豁遭，而其他機器上的數(shù)據(jù)不受影響叭喜。
在具體JAVA實現(xiàn)代碼中，定義了一個TreeMap<k, V>用來保存虛擬機器節(jié)點到實際的物理機器的映射蓖谢。機器以字符串形式來標(biāo)識捂蕴，故hash函數(shù)的參數(shù)為String
for (int i = 0; i < numberOfReplicas; i++)
// 對于一個實際機器節(jié)點 node, 對應(yīng) numberOfReplicas 個虛擬節(jié)點
/*
* 不同的虛擬節(jié)點(i不同)有不同的hash值,但都對應(yīng)同一個實際機器node
* 虛擬node一般是均衡分布在環(huán)上的,數(shù)據(jù)存儲在順時針方向的虛擬node上
*/
circle.put(hashFunction.hash(node.toString() + i), node);
而對于 數(shù)據(jù)的存儲而言，邏輯上是按順時針方向存儲在虛擬機器節(jié)點中闪幽，虛擬機器節(jié)點通過TreeMap知道它實際需要將數(shù)據(jù)存儲在哪臺物理機器上啥辨。此外，TreeMap中的Key是有序的盯腌，而環(huán)也是順時針有序的溉知，這樣才能當(dāng)數(shù)據(jù)被映射到兩臺虛擬機器之間的弧上時，通過TreeMap的 tailMap()來尋找順時針方向上的下一臺虛擬機腕够。
if (!circle.containsKey(hash)) {
//數(shù)據(jù)映射在兩臺虛擬機器所在環(huán)之間,就需要按順時針方向?qū)ふ覚C器
SortedMap<Long, T> tailMap = circle.tailMap(hash);
hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();}
完整代碼：
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é)點的復(fù)制因子,實際節(jié)點個數(shù) * numberOfReplicas =虛擬節(jié)點個數(shù)
private final SortedMap<Long, T> circle = new TreeMap<Long, T>();
// 存儲虛擬節(jié)點的hash值到真實節(jié)點的映射
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++)
// 對于一個實際機器節(jié)點 node, 對應(yīng) numberOfReplicas 個虛擬節(jié)點
/* * 不同的虛擬節(jié)點(i不同)有不同的hash值,但都對應(yīng)同一個實際機器node
* 虛擬node一般是均衡分布在環(huán)上的,數(shù)據(jù)存儲在順時針方向的虛擬node上
*/
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));
}
/*
* 獲得一個最近的順時針節(jié)點,根據(jù)給定的key 取Hash
* 然后再取得順時針方向上最近的一個虛擬節(jié)點對應(yīng)的實際節(jié)點
* 再從實際節(jié)點中取得 數(shù)據(jù)
*/
public T get(Object key) {
if (circle.isEmpty())
return null;
long hash = hashFunction.hash((String) key);
// node 用String來表示,獲得node在哈希環(huán)中的hashCode
if (!circle.containsKey(hash)) {
//數(shù)據(jù)映射在兩臺虛擬機器所在環(huán)之間,就需要按順時針方向?qū)ふ覚C器
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值---表示整個哈希環(huán)中各個虛擬節(jié)點位置
*/
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 相鄰兩個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(), 2, nodes);
consistentHash.add("D");
System.out.println("hash circle size: " + consistentHash.getSize());
System.out.println("location of each node are follows: ");
consistentHash.testBalance();
}
}
