一致性hash的歷史

【Consistent Hashing算法】早在 1997 年就在論文 Consistent hashing and random trees 中被提出教寂，目前在 cache 系統(tǒng)中應(yīng)用越來越廣泛巧娱；

一致性hash的目的

一致性哈希算法是分布式系統(tǒng)中常用的算法攻冷，一致性哈希算法解決了普通余數(shù)Hash算法伸縮性差的問題，可以保證在上線征椒、下線服務(wù)器的情況下盡量有多的請求命中原來路由到的服務(wù)器榜苫。

問題背景

業(yè)務(wù)開發(fā)中近迁，我們常把數(shù)據(jù)持久化到數(shù)據(jù)庫中代嗤，如果需要讀取這些數(shù)據(jù)，除了直接從數(shù)據(jù)庫中讀取外炕淮，為了減輕數(shù)據(jù)庫的訪問壓力以及提高訪問速度拆火，更多地引入緩存來對數(shù)據(jù)進行存取。

分布式緩存

分布式緩存涂圆，不同機器上存儲不同對象的數(shù)據(jù)们镜。為了實現(xiàn)這些緩存機器的負載均衡，一般就會存在兩種Hash算法進行均勻分配數(shù)據(jù)節(jié)點存儲：普通Hash算法

普通的Hash算法的

Hash取模做法的缺陷

一個Redis集群中润歉，如果我們把一條數(shù)據(jù)經(jīng)過Hash憎账，然后再根據(jù)集群節(jié)點數(shù)取模得出應(yīng)該放在哪個節(jié)點，這種做法的缺陷在于：擴容(增加一個節(jié)點)之后卡辰，有大量緩存失效。

普通Hash的案例分析

比如你有 N 個 cache 服務(wù)器（后面簡稱 cache ）邪意，那么如何將一個對象 object 映射到 N 個 cache 上呢九妈，你很可能會采用類似下面的通用方法計算 object 的 hash 值，然后均勻的映射到到 N 個 cache 雾鬼；

hash(object)%N 

一切都運行正常萌朱，再考慮如下的兩種情況；

• 一個 cache 服務(wù)器 m down 掉了（在實際應(yīng)用中必須要考慮這種情況）策菜，這樣所有映射到 cache m 的對象都會失效晶疼，怎么辦，需要把 cache m 從 cache 中移除又憨，這時候 cache 是 N-1 臺翠霍，映射公式變成了 hash(object)%(N-1) ；

• 由于訪問加重蠢莺，需要添加 cache 寒匙，這時候 cache 是 N+1 臺，映射公式變成了 hash(object)%(N+1) 躏将；

• 這意味著突然之間幾乎所有的 cache 都失效了锄弱。對于服務(wù)器而言考蕾，這是一場災難，洪水般的訪問都會直接沖向后臺服務(wù)器会宪；（造成緩存雪崩機制）

image

一致性Hash算法

一致性hash算法正是為了解決此類問題的方法肖卧，它可以保證當機器增加或者減少時，對緩存訪問命中的概率影響減至很小掸鹅。下面我們來詳細說一下一致性hash算法的具體過程塞帐。

• 一致性hash算法通過一個叫作一致性hash環(huán)的數(shù)據(jù)結(jié)構(gòu)實現(xiàn)。這個環(huán)的起點是0河劝，終點是2^32 - 1壁榕，并且起點與終點連接，環(huán)的中間的整數(shù)按逆時針分布赎瞎，故這個環(huán)的整數(shù)分布范圍是[0, 2^32-1]

• 整個哈希值空間組織成一個虛擬的圓環(huán)牌里，將節(jié)點的IP地址或主機名作為關(guān)鍵字進行哈希計算，得出的結(jié)果作為節(jié)點在環(huán)上的位置务甥。數(shù)據(jù)經(jīng)過hash后按順時針方向找到最近一個節(jié)點存放牡辽，如圖data的hash位置，應(yīng)該存放在node2敞临。

image

• 相比Hash取模态辛，一致性Hash算法的優(yōu)點就是擴容后影響的緩存數(shù)據(jù)較少，如果是n個節(jié)點擴容到n+1個的話挺尿，影響的緩存數(shù)是0~1/n奏黑，即最多讓一個節(jié)點的緩存失效。

• 他的缺點是编矾，緩存在每個節(jié)點上分布不均熟史，畢竟hash值隨機，那節(jié)點在環(huán)上的位置也隨機窄俏。

改良版一致性Hash算法

一致性Hash算法 + 虛擬節(jié)點

為了解決數(shù)據(jù)分布不均的問題蹂匹，我們引入虛擬節(jié)點的概念。我們對每一個服務(wù)節(jié)點計算多個哈希凹蜈，每個計算結(jié)果位置都放置一個此服務(wù)節(jié)點限寞，稱為虛擬節(jié)點。定位到虛擬節(jié)點的數(shù)據(jù)就存到該虛擬節(jié)點對應(yīng)的真實節(jié)點上仰坦，這樣數(shù)據(jù)分布就相對均勻了履植，虛擬節(jié)點數(shù)越多，分布越均勻悄晃。

引入“虛擬節(jié)點”后静尼，映射關(guān)系就從 { 對象 -> 節(jié)點 } 轉(zhuǎn)換到了 { 對象 -> 虛擬節(jié)點 } 。查詢物體所在 cache 時的映射關(guān)系

image

一般虛擬節(jié)點數(shù)32個以上，dubbo是160個鼠渺。

image

處理機器增減的情況

對于線上的業(yè)務(wù)鸭巴，增加或者減少一臺機器的部署是常有的事情。

例如拦盹，增加機器c4的部署并將機器c4加入到hash環(huán)的機器c3與c2之間鹃祖。這時，只有機器c3與c4之間的對象需要重新分配新的機器普舆。對于我們的例子恬口，只有對象o4被重新分配到了c4，其他對象仍在原有機器上沼侣。

一致性Hash算法的實現(xiàn)原理

在業(yè)務(wù)開發(fā)中祖能，我們常把數(shù)據(jù)持久化到數(shù)據(jù)庫中。如果需要讀取這些數(shù)據(jù)蛾洛，除了直接從數(shù)據(jù)庫中讀取外养铸，為了減輕數(shù)據(jù)庫的訪問壓力以及提高訪問速度，我們更多地引入緩存來對數(shù)據(jù)進行存取轧膘。讀取數(shù)據(jù)的過程一般為：

Java代碼實現(xiàn)Hash算法的實現(xiàn)

用一個TreeMap來作為環(huán)钞螟，key為虛擬節(jié)點下標，value為真實節(jié)點的hash谎碍。個人感覺可以加一個Map<T, Set<Integer>>來維護真實節(jié)點-虛擬節(jié)點的關(guān)系鳞滨。

/**
 * 一致性Hash算法
 * 算法詳解：http://blog.csdn.net/sparkliang/article/details/5279393
 * 算法實現(xiàn)：https://weblogs.java.net/blog/2007/11/27/consistent-hashing
 * @author xiaoleilu
 *
 * @param <T>   節(jié)點類型
 */
public class ConsistentHash<T> implements Serializable{
    private static final long serialVersionUID = 1L;
    
    /** Hash計算對象，用于自定義hash算法 */
    Hash32<Object> hashFunc;
    /** 復制的節(jié)點個數(shù) */
    private final int numberOfReplicas;
    /** 一致性Hash環(huán) */
    private final SortedMap<Integer, T> circle = new TreeMap<>();
    
    /**
     * 構(gòu)造蟆淀，使用Java默認的Hash算法
     * @param numberOfReplicas 復制的節(jié)點個數(shù)拯啦，增加每個節(jié)點的復制節(jié)點有利于負載均衡
     * @param nodes 節(jié)點對象
     */
    public ConsistentHash(int numberOfReplicas, Collection<T> nodes) {
        this.numberOfReplicas = numberOfReplicas;
        this.hashFunc = key -> {
            //默認使用FNV1hash算法
            return HashUtil.fnvHash(key.toString());
        };
        //初始化節(jié)點
        for (T node : nodes) {
            add(node);
        }
    }

    /**
     * 構(gòu)造
     * @param hashFunc hash算法對象
     * @param numberOfReplicas 復制的節(jié)點個數(shù)，增加每個節(jié)點的復制節(jié)點有利于負載均衡
     * @param nodes 節(jié)點對象
     */
    public ConsistentHash(Hash32<Object> hashFunc, int numberOfReplicas, Collection<T> nodes) {
        this.numberOfReplicas = numberOfReplicas;
        this.hashFunc = hashFunc;
        //初始化節(jié)點
        for (T node : nodes) {
            add(node);
        }
    }

    /**
     * 增加節(jié)點<br>
     * 每增加一個節(jié)點熔任，就會在閉環(huán)上增加給定復制節(jié)點數(shù)<br>
     * 例如復制節(jié)點數(shù)是2褒链，則每調(diào)用此方法一次，增加兩個虛擬節(jié)點笋敞，這兩個節(jié)點指向同一Node
     * 由于hash算法會調(diào)用node的toString方法，故按照toString去重
     * @param node 節(jié)點對象
     */
    public void add(T node) {
        for (int i = 0; i < numberOfReplicas; i++) {
            circle.put(hashFunc.hash32(node.toString() + i), node);
        }
    }

    /**
     * 移除節(jié)點的同時移除相應(yīng)的虛擬節(jié)點
     * @param node 節(jié)點對象
     */
    public void remove(T node) {
        for (int i = 0; i < numberOfReplicas; i++) {
            circle.remove(hashFunc.hash32(node.toString() + i));
        }
    }

    /**
     * 獲得一個最近的順時針節(jié)點
     * @param key 為給定鍵取Hash荠瘪，取得順時針方向上最近的一個虛擬節(jié)點對應(yīng)的實際節(jié)點
     * @return 節(jié)點對象
     */
    public T get(Object key) {
        if (circle.isEmpty()) {
            return null;
        }
        int hash = hashFunc.hash32(key);
        if (false == circle.containsKey(hash)) {
            SortedMap<Integer, T> tailMap = circle.tailMap(hash);   //返回此映射的部分視圖夯巷，其鍵大于等于 hash
            hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
        }
        //正好命中
        return circle.get(hash);
    }
}

參考資料

• http://weblogs.java.net/blog/2007/11/27/consistent-hashing 上面有一個 java 版本的例子，可以參考哀墓。
• http://blog.csdn.net/mayongzhan/archive/2009/06/25/4298834.aspx 轉(zhuǎn)載了一個 PHP 版的實現(xiàn)代碼趁餐。
• http://www.codeproject.com/KB/recipes/lib-conhash.aspx C語言版本
  • http://portal.acm.org/citation.cfm?id=258660
• http://en.wikipedia.org/wiki/Consistent_hashing
• http://www.spiteful.com/2008/03/17/programmers-toolbox-part-3-consistent-hashing/
• http://weblogs.java.net/blog/2007/11/27/consistent-hashing
• http://tech.idv2.com/2008/07/24/memcached-004/
• http://blog.csdn.net/mayongzhan/archive/2009/06/25/4298834.aspx