一致性哈希算法在1997年由麻省理工學院提出的一種分布式哈希(DHT)實現算法，設計目標是為了解決因特網中的熱點(Hot spot)問題，初衷和CARP十分類似。一致性哈希修正了CARP使用的簡 單哈希算法帶來的問題，使得分布式哈希(DHT)可以在P2P環境中真正得到應用。

一致性hash算法提出了在動態變化的Cache環境中，判定哈希算法好壞的四個定義：

1、平衡性(Balance)：平衡性是指哈希的結果能夠盡可能分布到所有的緩沖中去，這樣可以使得所有的緩沖空間都得到利用。很多哈希算法都能夠滿足這一條件。

2、單調性(Monotonicity)：單調性是指如果已經有一些內容通過哈希分派到了相應的緩沖中，又有新的緩沖加入到系統中。哈希的結果應能夠保證原有已分配的內容可以被映射到原有的或者新的緩沖中去，而不會被映射到舊的緩沖集合中的其他緩沖區。

3、分散性(Spread)：在分布式環境中，終端有可能看不到所有的緩沖，而是只能看到其中的一部分。當終端希望通過哈希過程將內容映射到緩沖上時，由于不同終端所見的緩沖范圍有可能不同，從而導致哈希的結果不一致，最終的結果是相同的內容被不同的終端映射到不同的緩沖區中。這種情況顯然是應該避免的，因為它導致相同內容被存儲到不同緩沖中去，降低了系統存儲的效率。分散性的定義就是上述情況發生的嚴重程度。好的哈希算法應能夠盡量避免不一致的情況發生，也就是盡量降低分散性。

4、負載(Load)：負載問題實際上是從另一個角度看待分散性問題。既然不同的終端可能將相同的內容映射到不同的緩沖區中，那么對于一個特定的緩沖區而言，也可能被不同的用戶映射為不同 的內容。與分散性一樣，這種情況也是應當避免的，因此好的哈希算法應能夠盡量降低緩沖的負荷。

在分布式集群中，對機器的添加刪除，或者機器故障后自動脫離集群這些操作是分布式集群管理最基本的功能。如果采用常用的hash(object)%N算法，那么在有機器添加或者刪除后，很多原有的數據就無法找到了，這樣嚴重的違反了單調性原則。接下來主要講解一下一致性哈希算法是如何設計的：

環形Hash空間

按照常用的hash算法來將對應的key哈希到一個具有2^32次方個桶的空間中，即0~(2^32)-1的數字空間中。現在我們可以將這些數字頭尾相連，想象成一個閉合的環形。如下圖   

把數據通過一定的hash算法處理后映射到環上

現在我們將object1、object2、object3、object4四個對象通過特定的Hash函數計算出對應的key值，然后散列到Hash環上。如下圖：

Hash(object1) = key1;

Hash(object2) = key2;

Hash(object3) = key3;

Hash(object4) = key4;  

將機器通過hash算法映射到環上

在采用一致性哈希算法的分布式集群中將新的機器加入，其原理是通過使用與對象存儲一樣的Hash算法將機器也映射到環中(一般情況下對機器的hash計算是采用機器的IP或者機器唯一的別名作為輸入值)，然后以順時針的方向計算，將所有對象存儲到離自己最近的機器中。

假設現在有NODE1，NODE2，NODE3三臺機器，通過Hash算法得到對應的KEY值，映射到環中，其示意圖如下：

Hash(NODE1) = KEY1;

Hash(NODE2) = KEY2;

Hash(NODE3) = KEY3;  

通過上圖可以看出對象與機器處于同一哈?？臻g中，這樣按順時針轉動object1存儲到了NODE1中，object3存儲到了NODE2中，object2、object4存儲到了NODE3中。在這樣的部署環境中，hash環是不會變更的，因此，通過算出對象的hash值就能快速的定位到對應的機器中，這樣就能找到對象真正的存儲位置了。

機器的刪除與添加

普通hash求余算法最為不妥的地方就是在有機器的添加或者刪除之后會照成大量的對象存儲位置失效，這樣就大大的不滿足單調性了。下面來分析一下一致性哈希算法是如何處理的。

1. 節點(機器)的刪除

以上面的分布為例，如果NODE2出現故障被刪除了，那么按照順時針遷移的方法，object3將會被遷移到NODE3中，這樣僅僅是object3的映射位置發生了變化，其它的對象沒有任何的改動。如下圖：  

2. 節點(機器)的添加

如果往集群中添加一個新的節點NODE4，通過對應的哈希算法得到KEY4，并映射到環中，如下圖：  

通過按順時針遷移的規則，那么object2被遷移到了NODE4中，其它對象還保持這原有的存儲位置。通過對節點的添加和刪除的分析，一致性哈希算法在保持了單調性的同時，還是數據的遷移達到了最小，這樣的算法對分布式集群來說是非常合適的，避免了大量數據遷移，減小了服務器的的壓力。

平衡性

根據上面的圖解分析，一致性哈希算法滿足了單調性和負載均衡的特性以及一般hash算法的分散性，但這還并不能當做其被廣泛應用的原由，因為還缺少了平衡性。下面將分析一致性哈希算法是如何滿足平衡性的。hash算法是不保證平衡的，如上面只部署了NODE1和NODE3的情況(NODE2被刪除的圖)，object1存儲到了NODE1中，而object2、object3、object4都存儲到了NODE3中，這樣就照成了非常不平衡的狀態。在一致性哈希算法中，為了盡可能的滿足平衡性，其引入了虛擬節點。

——“虛擬節點”( virtual node )是實際節點(機器)在 hash 空間的復制品( replica )，一實際個節點(機器)對應了若干個“虛擬節點”，這個對應個數也成為“復制個數”，“虛擬節點”在 hash 空間中以hash值排列。

以上面只部署了NODE1和NODE3的情況(NODE2被刪除的圖)為例，之前的對象在機器上的分布很不均衡，現在我們以2個副本(復制個數)為例，這樣整個hash環中就存在了4個虛擬節點，***對象映射的關系圖如下： 

 

根據上圖可知對象的映射關系：object1->NODE1-1，object2->NODE1-2，object3->NODE3-2，object4->NODE3-1。通過虛擬節點的引入，對象的分布就比較均衡了。那么在實際操作中，正真的對象查詢是如何工作的呢?對象從hash到虛擬節點到實際節點的轉換如下圖： 

 

“虛擬節點”的hash計算可以采用對應節點的IP地址加數字后綴的方式。例如假設NODE1的IP地址為192.168.1.100。引入“虛擬節點”前，計算 cache A 的 hash 值：

Hash(“192.168.1.100”);

引入“虛擬節點”后，計算“虛擬節”點NODE1-1和NODE1-2的hash值：

Hash(“192.168.1.100#1”); // NODE1-1

Hash(“192.168.1.100#2”); // NODE1-2

Java實現： 

public class Shard<S> { // S類封裝了機器節點的信息 ，如name、password、ip、port等    
    private TreeMap<Long, S> nodes; // 虛擬節點    
    private List<S> shards; // 真實機器節點    
    private final int NODE_NUM = 100; // 每個機器節點關聯的虛擬節點個數    
    public Shard(List<S> shards) {   
        super();   
        this.shards = shards;   
        init();   
    }   
    private void init() { // 初始化一致性hash環    
        nodes = new TreeMap<Long, S>();   
        for (int i = 0; i != shards.size(); ++i) { // 每個真實機器節點都需要關聯虛擬節點    
            final S shardInfo = shards.get(i);   
            for (int n = 0; n < NODE_NUM; n++)   
                // 一個真實機器節點關聯NODE_NUM個虛擬節點    
                nodes.put(hash("SHARD-" + i + "-NODE-" + n), shardInfo);   
        }   
    }   
    public S getShardInfo(String key) {   
        SortedMap<Long, S> tail = nodes.tailMap(hash(key)); // 沿環的順時針找到一個虛擬節點    
        if (tail.size() == 0) {   
            return nodes.get(nodes.firstKey());   
        }   
        return tail.get(tail.firstKey()); // 返回該虛擬節點對應的真實機器節點的信息    
    }   
    /**  
     *  MurMurHash算法，是非加密HASH算法，性能很高，  
     *  比傳統的CRC32,MD5，SHA-1（這兩個算法都是加密HASH算法，復雜度本身就很高，帶來的性能上的損害也不可避免）  
     *  等HASH算法要快很多，而且據說這個算法的碰撞率很低.  
     *  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;   
    }   
}  

【本文為51CTO專欄作者“王森豐”的原創稿件，轉載請注明出處】