一致性哈希算法（Consistent Hashing ）

一腊满、問題

分布式架構(gòu)中，無論是數(shù)據(jù)緩存還是持久化存儲培己，都需要考慮負載均衡的問題碳蛋，期望將對后臺的訪問或者數(shù)據(jù)存儲能夠盡可能地“平均”分發(fā)給每一個服務器節(jié)點。

為滿足上述需求省咨，最容易想到的一個辦法就是hash肃弟，假設有N個節(jié)點，根據(jù)hash(obj)%N的結(jié)果來判斷應該訪問哪一個節(jié)點零蓉。理論上笤受，如果能保證hash函數(shù)的隨機性，則能夠?qū)崿F(xiàn)負載均衡的需求敌蜂。然而箩兽，在實際情況中，節(jié)點具有不可預測的運行故障章喉，如果集群中的某個節(jié)點宕機汗贫，那么節(jié)點數(shù)量就從N變成了N-1，若使用hash(obj)%N的方法實現(xiàn)負載均衡秸脱，此時將有(N-1)/N的數(shù)據(jù)發(fā)生遷移（即有(N-1)/N的數(shù)據(jù)hash(obj)%N != hash(obj)%(N-1)落包，這個結(jié)論的推導文末會說明）。這將是一次規(guī)模很大的數(shù)據(jù)遷移撞反，幾乎之前所有的結(jié)果都將重新計算妥色。同時搪花，若集群規(guī)模不足以滿足需求遏片，需要擴充服務器節(jié)點時（節(jié)點數(shù)量從N變到N+1），也將發(fā)生類似問題撮竿。此時吮便，基本的散列取余的方法非常低效。

注：上述問題其實是不滿足hash函數(shù)的單調(diào)性幢踏，這是衡量hash函數(shù)好壞的一個指標髓需。具體請見一致性hash（consistent hashing）。

二房蝉、算法原理

2.1 算法簡析

一致性哈希算法在1997年由麻省理工學院的Karger等人提出僚匆，用以解決分布式Cache的負載均衡問題微渠。這是個能夠保證單調(diào)性的hash算法。對于有N個節(jié)點的集群咧擂，最常見的hash(obj)%N算法首先計算出數(shù)據(jù)對象的hashcode逞盆，然后映射到0~N-1的N點環(huán)形空間中。而Consistent Hashing則將對象映射到0~2³²-1的環(huán)形空間中松申，同時注意云芦，這里的對象包括服務器節(jié)點對象和數(shù)據(jù)對象。如下圖所示：

consistent hashing的映射空間

為什么選擇2³²這個數(shù)呢贸桶？因為hash算法所得結(jié)果一般是一個unsigned int類型舅逸。

因此，算法的步驟如下：

1. 計算節(jié)點的hashcode皇筛，并將其映射在[0, 2³²-1]環(huán)形空間中（hash(node)%2³²）琉历。
2. 計算數(shù)據(jù)對象的hashcode，并映射到[0, 2³²-1]環(huán)形空間中（hash(obj)%2³²）设联。
3. 在映射空間中善已，根據(jù)順時針方向，數(shù)據(jù)對象找到離其最近的節(jié)點离例，即為該數(shù)據(jù)的存儲（緩存）位置换团。

下圖形象地描述了算法的原理。

consistent hashing 算法原理

CacheA, CacheB, CacheC表示三個節(jié)點宫蛆，object1, object2, object3, object4表示四個數(shù)據(jù)對象艘包。根據(jù)圖中的映射結(jié)果，我們可以看出存儲的分布為：{CacheA: [object1]}, {CacheB: [object4]}, {CacheC: [object2, object3]}耀盗。

那么回到一開始的問題想虎，當節(jié)點增加或者減少時，Consistent Hashing算法是如何保證單調(diào)性的叛拷？

2.2 移除節(jié)點

假如此時CacheB節(jié)點宕機舌厨，從映射空間中移除。則根據(jù)順時針查找的原理忿薇，object4將發(fā)現(xiàn)離它最近的節(jié)點變成了了CacheC裙椭，此時數(shù)據(jù)分布變成了：{CacheA: [object1]}, {CacheC: [object2, object3, object4]}。

移除節(jié)點

可以看出署浩，只有object4發(fā)生了數(shù)據(jù)遷移揉燃，或者說只有CacheB存儲的數(shù)據(jù)發(fā)生了遷移，而原本存儲在其他節(jié)點上的數(shù)據(jù)依然維持原來的分布筋栋。

2.3 增加節(jié)點

當擴容時炊汤，增加一個節(jié)點CacheD，根據(jù)計算，映射在如下的位置上抢腐，則object2發(fā)現(xiàn)離他最近的節(jié)點變成了CacheD姑曙，則數(shù)據(jù)分布發(fā)生變化：{CacheA: [object1]}, {CacheB: [object4]}, {CacheC: [object3]}, {CacheD: [object2]}。

增加節(jié)點

此時迈倍，只有object2從CacheC遷移到CacheD上渣磷，而其他數(shù)據(jù)依然維持原來的分布關系。

這就滿足了hash算法的單調(diào)性：
內(nèi)容通過hash算法分布到相應的節(jié)點中授瘦，若此時增加一個新節(jié)點醋界，則舊節(jié)點中的內(nèi)容要不就保持原來的分布關系，要不就分布到新增的節(jié)點中提完，而不會分布到其他的舊節(jié)點中形纺。

2.4 虛擬節(jié)點（Virtual nodes）

為了衡量算法的穩(wěn)定性，我們常惩叫溃考慮一下極端場景逐样。比如上面那張“移除節(jié)點”的圖，當節(jié)點的數(shù)量比較少時打肝，只有CacheA和CacheC脂新，CacheA節(jié)點只存儲一個數(shù)據(jù)，而CacheC卻存儲了3個數(shù)據(jù)粗梭，此時數(shù)據(jù)分布不均勻争便。

雖然是極端情況，但卻很具備現(xiàn)實意義断医，畢竟常見的集群規(guī)模與2³²比都是微不足道了滞乙，極有可能發(fā)生上述的數(shù)據(jù)分布不均勻的情況，或者說平衡性問題鉴嗤。

為此引入虛擬節(jié)點斩启。

虛擬節(jié)點

如上圖所示，CacheA2和CacheC2分別是CacheA1和CacheC1的虛擬節(jié)點醉锅，同樣映射到了[0, 2³²-1]圓環(huán)空間兔簇。此時，邏輯上的數(shù)據(jù)分布為：{CacheA1: [object2]}, {CacheA2: [object1]}, {CacheC1: [object3]}, {CacheC2: [object4]}硬耍。

要注意的是垄琐，虛擬節(jié)點之所以是虛擬的，是因為它們僅僅是邏輯上存在的默垄，數(shù)據(jù)存儲的物理位置是其對應的真實節(jié)點此虑。所以甚纲，物理上的數(shù)據(jù)分布為：{CacheA1: [object1, object2]}, {CacheC1: [object3, object4]}口锭。

對比引入虛擬節(jié)點之前的數(shù)據(jù)分布：{CacheA1: [object1, object2, object4]}, {CacheC1: [object3]}。可以發(fā)現(xiàn)鹃操，虛擬節(jié)點的引入改善了consistent hashing算法的平衡性韭寸。

如果要引入虛擬節(jié)點，則引入的數(shù)量應當如何選擇呢荆隘？

虛擬節(jié)點的引入數(shù)量

上圖橫軸為虛擬節(jié)點的倍數(shù)恩伺，縱軸為真實節(jié)點的個數(shù)。藍線表示為保證hash算法的平衡性椰拒，節(jié)點數(shù)量與虛擬節(jié)點副本倍數(shù)的關系晶渠。僅供參考。

除了解決平衡性問題燃观，節(jié)點的異構(gòu)性也能通過引入虛擬節(jié)點加以解決褒脯。異構(gòu)性通俗的講就是不同服務器節(jié)點的存儲、算力等性能是不一樣的缆毁，一個完美的hash算法是連節(jié)點的異構(gòu)性都能考慮進去的番川。根據(jù)每個節(jié)點的性能算出一個量化的權(quán)重，根據(jù)這個權(quán)重來計算這個節(jié)點引入虛擬節(jié)點的數(shù)量脊框。性能差的颁督，虛擬節(jié)點少點，分布的數(shù)據(jù)就少點浇雹，讓他放輕松沉御，別緊張。性能好的昭灵，就多整點嚷节，對著他干就對了。

三虎锚、代碼實現(xiàn)

使用Java實現(xiàn)Consistent hashing硫痰。

package cn.edu.njupt.qyz;

import java.util.Collection;
import java.util.SortedMap;
import java.util.TreeMap;

public class ConsistentHashing<T> {

    // hash函數(shù)
    private final HashFunction hashFunction;
    // 虛擬節(jié)點副本數(shù)
    private final int numberOfReplicas;
    // 映射圓環(huán)
    private final SortedMap<Integer, T> circle = new TreeMap<Integer, T>();

    // 構(gòu)造方法
    public ConsistentHashing(HashFunction hashFunction, int numberOfReplicas, Collection<T> nodes) {
        this.hashFunction = hashFunction;
        this.numberOfReplicas = numberOfReplicas;

        for (T node : nodes) {
            add(node);
        }
    }

    // 將服務器節(jié)點映射到圓環(huán)上，同時加入對應的虛擬節(jié)點
    public void add(T node) {
        for (int i = 0; i < numberOfReplicas; i++) {
            circle.put(hashFunction.hash(node.toString() + i), node);
        }
    }

    // 移除映射窜护，同時移除虛擬節(jié)點
    public void remove(T node) {
        for (int i = 0; i < numberOfReplicas; i++) {
            circle.remove(hashFunction.hash(node.toString() + i));
        }
    }
    // 根據(jù)傳入的obj找到對應的節(jié)點
    public T get(Object key) {
        if (circle.isEmpty()) {
            return null;
        }
        int hash = hashFunction.hash(key);
        if (!circle.containsKey(hash)) {
            // 從比obj的hashcode更大的Map中找效斑，即順時針方向找node
            SortedMap<Integer, T> tailMap = circle.tailMap(hash);
            // 環(huán)形空間，找到順時針方向第一個node柱徙，并將其hashcode賦值
            hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
        }
        // 返回找到的節(jié)點
        return circle.get(hash);
    }
}

代碼使用具有排序能力的的TreeMap實現(xiàn)環(huán)形映射結(jié)構(gòu)缓屠，首先將節(jié)點加入到TreeMap中，然后定義一個get方法护侮，根據(jù)傳入的key對象來查找對應的節(jié)點敌完。

四、總結(jié)

為了解決分布式架構(gòu)的負載均衡問題羊初，并保證hash算法的單調(diào)性滨溉，Consistent Hashing算法應運而生什湘。同時，為了保證算法的平衡性晦攒，引入虛擬節(jié)點以達到令數(shù)據(jù)均勻分布在各個節(jié)點的目的闽撤。本文介紹了Consistent Hashing算法的基本原理，并進行了代碼實現(xiàn)脯颜。

五哟旗、參考資料

1. Consistent Hashing算法
2. 一致性hash算法：jump Consistent hash（零內(nèi)存消耗，均勻栋操，快速闸餐，簡潔）
3. 一致性hash（consistent hashing）

推導

對hash(obj)%N的結(jié)果呈[0, N-1]循環(huán)，hash(obj)%(N-1)的結(jié)果為[0, N-2]的循環(huán)矾芙。N和N-1的最小公倍數(shù)為N(N-1)绎巨，則二者的結(jié)果每隔N(N-1)個數(shù)據(jù)發(fā)生一次重疊，而每次重疊有N-1個結(jié)果是相等的蠕啄，且有(N-1)²個結(jié)果不相等场勤，因此全部的數(shù)據(jù)中有(N-1)/N的不相等，將發(fā)生數(shù)據(jù)遷移歼跟『拖保可以參考下表。