一致性Hash的應(yīng)用場景
我們先假設(shè)一種場景，有一個應(yīng)用的請求量非常大，在服務(wù)端有若干臺緩存服務(wù)器，這些緩存服務(wù)器記錄了各用戶請求的緩存數(shù)據(jù)（當(dāng)然這樣做的目的我想大家應(yīng)該清楚）。怎樣將這么多的請求按照一定的規(guī)則分發(fā)到不同的緩存服務(wù)器就顯得非常關(guān)鍵。
一種簡單的調(diào)度規(guī)則是通過求余的方式將請求關(guān)聯(lián)到某一臺服務(wù)器，比如說有10臺服務(wù)器，那么通過請求的hash值對10求余就關(guān)聯(lián)到了其中的一臺服務(wù)器?？雌饋磉@種方法還ok，但是運行中的服務(wù)器難免有掛掉的風(fēng)險，或者任務(wù)分發(fā)后服務(wù)器的負載仍然很大致使我們不得不增加服務(wù)器，遇到這樣類似的情況，如果我們還是通過上述方法進行調(diào)度的話就會打亂原來的請求映射，比如請求A之前關(guān)聯(lián)的是服務(wù)器1001，當(dāng)服務(wù)器數(shù)量發(fā)生改變之后，通過求余，很可能A就關(guān)聯(lián)到了其他的服務(wù)器，而這是我們不能接受的，我們希望的是服務(wù)器的增減盡量不影響用戶之前的緩存映射。怎么辦？一致性Hash就能夠較好的解決這個問題。
一致性Hash的原理
整體來看，有兩個基本空間，用戶空間和服務(wù)空間，我們的目的是將這兩個空間關(guān)聯(lián)起來，這里我們引入hash空間，將用戶空間和服務(wù)空間都映射到hash空間，這樣兩者就關(guān)聯(lián)起來了。將服務(wù)器映射到hash空間，按照hash值由小到大順時針排列，并且首尾相連，形成一個環(huán)形。當(dāng)用戶請求過來的時候，也將其映射到hash空間上，然后將其關(guān)聯(lián)到順時針最近的服務(wù)器即可。但有一個問題是，比如說當(dāng)其中一個服務(wù)器節(jié)掛掉時，按照這個規(guī)則，盡管之前關(guān)聯(lián)到其他服務(wù)器的請求的關(guān)聯(lián)性不會發(fā)生改變，但關(guān)聯(lián)到該服務(wù)器的請求就全部關(guān)聯(lián)到了另一臺服務(wù)器。這樣勢必會增大后者的負載，不甚合理。
換一種方式，現(xiàn)在我們不直接將服務(wù)器映射到hash空間，而是基于每一臺服務(wù)器虛擬出諸多虛擬服務(wù)器（100臺或者更多），我們將這些虛擬服務(wù)器映射到hash空間，這樣歸屬不同服務(wù)器的各虛擬服務(wù)器就交織在hash空間中，當(dāng)請求過來時先關(guān)聯(lián)到某個虛擬服務(wù)器，然后再將虛擬服務(wù)器關(guān)聯(lián)到其所屬的真實服務(wù)器。當(dāng)其中的一臺服務(wù)器掛掉時，之前歸屬到這臺服務(wù)器的請求就可能關(guān)聯(lián)到其他任意服務(wù)器，這樣就實現(xiàn)了負載均衡，即所謂的一致性hash。
代碼示例
首先定義服務(wù)器節(jié)點：
public static class Node{
String name;
String ip;
public Node(String name, String ip){
this.name = name;
this.ip = ip;
}
public String toString(){
return this.name+"-"+this.ip;
}
}
然后是測試類：（這里有兩個關(guān)鍵點，一個是hash環(huán)的管理，另一個是hash函數(shù)的選取。本實例用的是murmur哈希）
public class Shard<Node> {
private static TreeMap<Long, Node> nodes;//虛擬主機hash環(huán)
private static TreeMap<Long, Node> treeKey;//客戶機主機映射
private List<Node> mNodes = new ArrayList<Node>();//實體主機列表
private final Integer vNodes = 100;//一個實體對應(yīng)虛擬主機個數(shù)
public Shard(List<Node> mNodes){
this.mNodes = mNodes;
init();
}
//main函數(shù)
public static void main(String[] args){
Node n1 = new Node("n1", "172.16.226.111");
Node n2 = new Node("n2", "172.16.226.112");
Node n3 = new Node("n3", "172.16.226.113");
Node n4 = new Node("n4", "172.16.226.114");
List<Node> nodes = new ArrayList<Node>();
nodes.add(n1);
nodes.add(n2);
nodes.add(n3);
nodes.add(n4);
Shard<Node> shardN = new Shard<Node>(nodes);
System.out.println("添加客戶端，一開始有4個主機，分別為n1,n2,n3,n4,每個主機有100個虛擬主機：");
shardN.keyToNode("1111號客戶端");
shardN.keyToNode("1112號客戶端");
shardN.keyToNode("1113號客戶端");
shardN.keyToNode("1114號客戶端");
shardN.keyToNode("1115號客戶端");
shardN.keyToNode("1116號客戶端");
shardN.keyToNode("1117號客戶端");
shardN.keyToNode("1118號客戶端");
shardN.keyToNode("1119號客戶端");
shardN.deleteNode(n2);//刪除節(jié)點n2
Node n5 = new Node("n3", "172.16.226.115");
shardN.addNode(n5);//增加節(jié)點n5
}
//構(gòu)建hash環(huán)
public void init (){
nodes = new TreeMap<Long, Node>();
treeKey = new TreeMap<Long, Node>();
for(Node n : mNodes){
for(Integer i=0;i<vNodes;i++){
nodes.put(hash("SHARD-"+n.name+"-NODE-"+i), n);
}
}
}
//刪除節(jié)點
public void deleteNode(Node node){
System.out.println("刪除節(jié)點："+node);
for(int i=0;i<vNodes;i++){
Long key = hash("SHARD-"+node.name+"-NODE-"+i);
//nodes.remove(key);
SortedMap<Long,Node> headNodes = nodes.headMap(key);
SortedMap<Long,Node> tailNodes = nodes.tailMap(key);
SortedMap<Long,Node> betweenNodes;
if(headNodes.size() == 0){
betweenNodes = treeKey.tailMap(tailNodes.lastKey());
}else{
betweenNodes = treeKey.subMap(headNodes.lastKey(), key);
}
nodes.remove(tailNodes.firstKey());
tailNodes.remove(tailNodes.firstKey());
Iterator iterator = betweenNodes.keySet().iterator();
while(iterator.hasNext()){
Long keytemp = (Long)iterator.next();
if(tailNodes.size() == 0){
treeKey.put(keytemp, headNodes.get(headNodes.firstKey()));
System.out.println(keytemp + "連接轉(zhuǎn)移到->" + headNodes.get(headNodes.firstKey()));
}else{
treeKey.put(keytemp, tailNodes.get(tailNodes.firstKey()));
System.out.println(keytemp + "連接轉(zhuǎn)移到->" + tailNodes.get(tailNodes.firstKey()));
}
}
}
}
//增加節(jié)點
public void addNode(Node node){
System.out.println("增加節(jié)點："+node);
for(int i=0;i<vNodes;i++){
Long key = hash("SHARD-"+node.name+"-NODE-"+i);
SortedMap<Long,Node> headNodes = nodes.headMap(key);
SortedMap<Long,Node> tailNodes = nodes.tailMap(key);
SortedMap<Long,Node> betweenNodes;
if(headNodes.size() == 0){
betweenNodes = treeKey.tailMap(nodes.lastKey());
}else{
betweenNodes = treeKey.subMap(headNodes.lastKey(), key);
}
nodes.put(key, node);
Iterator iterator = betweenNodes.keySet().iterator();
while(iterator.hasNext()){
Long keytemp = (Long)iterator.next();
System.out.println(keytemp + "連接轉(zhuǎn)移到->" + node);
}
}
}
//將請求關(guān)聯(lián)到服務(wù)器
public void keyToNode(String key){
SortedMap<Long, Node> tail = nodes.tailMap(hash(key));
if(tail.size() == 0){
treeKey.put(hash(key), nodes.get(nodes.firstKey()));
System.out.println(key+"（hash："+hash(key)+"）連接到主機->"+nodes.get(nodes.firstKey()));
return;
}
treeKey.put(hash(key), tail.get(tail.firstKey()));
System.out.println(key+"（hash："+hash(key)+"）連接到主機->"+tail.get(tail.firstKey()));
}
//murmur Hash
private static Long hash(String key) {
ByteBuffer buf = ByteBuffer.wrap(key.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);
// for big-endian version, do this first:
// finish.position(8-buf.remaining());
finish.put(buf).rewind();
h ^= finish.getLong();
h *= m;
}
h ^= h >>> r;
h *= m;
h ^= h >>> r;
buf.order(byteOrder);
return h;
}
}
參考文章
應(yīng)用于負載均衡的一致性哈希及java實現(xiàn)——haitao111313
一致性哈希算法與Java實現(xiàn)
Hash函數(shù)概覽
一致性哈希算法（用于解決服務(wù)器均衡問題）——caigen1988
