轉(zhuǎn)載地址：http://blog.csdn.net/wuhuan_wp/article/details/7010071
一致性哈希算法是分布式系統(tǒng)中常用的算法茂装。比如少态，一個(gè)分布式的存儲(chǔ)系統(tǒng)彼妻，要將數(shù)據(jù)存儲(chǔ)到具體的節(jié)點(diǎn)上，如果采用普通的hash方法澳骤，將數(shù)據(jù)映射到具體的節(jié)點(diǎn)上为肮，如key%N肤京，key是數(shù)據(jù)的key茅特，N是機(jī)器節(jié)點(diǎn)數(shù)棋枕，如果有一個(gè)機(jī)器加入或退出這個(gè)集群，則所有的數(shù)據(jù)映射都無效了兵睛，如果是持久化存儲(chǔ)則要做數(shù)據(jù)遷移窥浪，如果是分布式緩存漾脂，則其他緩存就失效了。
因此笨鸡，引入了一致性哈希算法：
把數(shù)據(jù)用hash函數(shù)（如MD5）坦冠，映射到一個(gè)很大的空間里，如圖所示趟脂。數(shù)據(jù)的存儲(chǔ)時(shí)昔期，先得到一個(gè)hash值佛玄，對(duì)應(yīng)到這個(gè)環(huán)中的每個(gè)位置，如k1對(duì)應(yīng)到了圖中所示的位置般贼，然后沿順時(shí)針找到一個(gè)機(jī)器節(jié)點(diǎn)B哼蛆，將k1存儲(chǔ)到B這個(gè)節(jié)點(diǎn)中霞赫。
如果B節(jié)點(diǎn)宕機(jī)了，則B上的數(shù)據(jù)就會(huì)落到C節(jié)點(diǎn)上叠洗，如下圖所示：
這樣，只會(huì)影響C節(jié)點(diǎn)十艾，對(duì)其他的節(jié)點(diǎn)A忘嫉，D的數(shù)據(jù)不會(huì)造成影響禀倔。然而，這又會(huì)造成一個(gè)“雪崩”的情況，即C節(jié)點(diǎn)由于承擔(dān)了B節(jié)點(diǎn)的數(shù)據(jù)涎才，所以C節(jié)點(diǎn)的負(fù)載會(huì)變高耍铜，C節(jié)點(diǎn)很容易也宕機(jī)，這樣依次下去陡舅，這樣造成整個(gè)集群都掛了。
為此靶衍，引入了“虛擬節(jié)點(diǎn)”的概念：即把想象在這個(gè)環(huán)上有很多“虛擬節(jié)點(diǎn)”颅眶，數(shù)據(jù)的存儲(chǔ)是沿著環(huán)的順時(shí)針方向找一個(gè)虛擬節(jié)點(diǎn)田弥，每個(gè)虛擬節(jié)點(diǎn)都會(huì)關(guān)聯(lián)到一個(gè)真實(shí)節(jié)點(diǎn)偷厦，如下圖所使用：
圖中的A1、A2剖笙、B1辜妓、B2忌怎、C1榴啸、C2鸥印、D1坦报、D2都是虛擬節(jié)點(diǎn)片择，機(jī)器A負(fù)載存儲(chǔ)A1、A2的數(shù)據(jù)字管，機(jī)器B負(fù)載存儲(chǔ)B1啰挪、B2的數(shù)據(jù)，機(jī)器C負(fù)載存儲(chǔ)C1嘲叔、C2的數(shù)據(jù)亡呵。由于這些虛擬節(jié)點(diǎn)數(shù)量很多，均勻分布硫戈，因此不會(huì)造成“雪崩”現(xiàn)象锰什。
Java實(shí)現(xiàn)：
public class Shard{ // S類封裝了機(jī)器節(jié)點(diǎn)的信息 ，如name丁逝、password养涮、ip蛔趴、port等private TreeMapnodes; // 虛擬節(jié)點(diǎn)private Listshards; // 真實(shí)機(jī)器節(jié)點(diǎn)private final int NODE_NUM = 100; // 每個(gè)機(jī)器節(jié)點(diǎn)關(guān)聯(lián)的虛擬節(jié)點(diǎn)個(gè)數(shù)public Shard(Listshards) {super();this.shards = shards;init();}private void init() { // 初始化一致性hash環(huán)nodes = new TreeMap();for (int i = 0; i != shards.size(); ++i) { // 每個(gè)真實(shí)機(jī)器節(jié)點(diǎn)都需要關(guān)聯(lián)虛擬節(jié)點(diǎn)final S shardInfo = shards.get(i);for (int n = 0; n < NODE_NUM; n++)// 一個(gè)真實(shí)機(jī)器節(jié)點(diǎn)關(guān)聯(lián)NODE_NUM個(gè)虛擬節(jié)點(diǎn)nodes.put(hash("SHARD-" + i + "-NODE-" + n), shardInfo);}}public S getShardInfo(String key) {SortedMaptail = nodes.tailMap(hash(key)); // 沿環(huán)的順時(shí)針找到一個(gè)虛擬節(jié)點(diǎn)
if (tail.size() == 0) {
return nodes.get(nodes.firstKey());
}
return tail.get(tail.firstKey()); // 返回該虛擬節(jié)點(diǎn)對(duì)應(yīng)的真實(shí)機(jī)器節(jié)點(diǎn)的信息
}
/**
*? MurMurHash算法，是非加密HASH算法，性能很高搁凸，
*? 比傳統(tǒng)的CRC32,MD5进陡，SHA-1（這兩個(gè)算法都是加密HASH算法，復(fù)雜度本身就很高千劈，帶來的性能上的損害也不可避免）
*? 等HASH算法要快很多涡驮，而且據(jù)說這個(gè)算法的碰撞率很低.
*? http://murmurhash.googlepages.com/
*/
private 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;
}
}
