一致性哈希（Consistent Hashing）是一種特殊的哈希算法，主要用于解決分布式系統中節點動態變化時的數據分布問題。它在保持數據分布均勻的同時，盡量減少節點加入或離開時需要重新分配的數據量。一致性哈希算法在許多場景下都非常有用，例如在緩存系統、負載均衡器、數據庫分片等應用中。

1.一致性哈希解決的問題

問題：

有一個鍵值對的集合，還有一些用于鍵值存儲的服務器例如 memcached，Redis，MySQL等等。在沒有全局存儲目錄的條件下，如何把Key發布到不同服務器上，然后可以找到它。

2. 那些一致性哈希算法

2.1 模N哈希

首先，選擇一個哈希函數來將鍵(字符串)映射為一個整數。這往往排除了像 SHA-1或 MD5這樣的加密算法，因為其計算成本較高。MurmurHash 以及 xxHash等非加密哈希函數都是不錯的選擇。

如果您有 N 個服務器，您可以使用 hash 函數散列密鑰，并取得結果的整數模 N。server := serverList[hash(key) % N]

這種設置很容易解釋, 計算成本很低。如果 N 是2的冪，那么只需要比特掩碼即可。

圖片

但是，局限也是顯然的。模N哈希難以應對服務器的數量變化。理想的哈希函數當面臨添加或刪除一個服務器時，應該只移動1/n的鍵，不需要移動的鍵不要移動。

2.2 環哈希

環哈希（ring-based consistent hashing）的基本思想是，每個服務器被映射到一個具有哈希函數的圓上的一個點，可以把圓看作所有的整數0,1,2......2^32-1 的集合。要查找給定鍵的服務器，需要對該密鑰執行散列并在圓上找到該點。然后向前掃描，直到找到任何服務器的第一個哈希值。實際上，每個服務器會在哈希環上出現多次。這些額外的點稱為“虛擬節點”或“ vnode”。這減少了服務器之間的負載差異。對于少量的 vnode，不同的服務器可以分配不同數量的鍵。

Ketama 是一個 memcached 客戶段，它使用環哈希來跨服務器實例的鍵分布。一個ketama算法的go 語言參考實現如下：

func (c Continuum) Hash(thing string) string {

    if len(c.ring) == 0 {
        return ""
    }

    h := hashString(thing)

    var i uint
    switch c.hash {
    case HashFunc1:
        i = search(c.ring, h)
    case HashFunc2:
        i = uint(sort.Search(len(c.ring), func(i int) bool { return c.ring[i].point >= h }))
        if i >= uint(len(c.ring)) {
            i = 0
        }
    }

    return c.ring[i].bucket.Label
}

環哈希算法很簡單。為了查看給定鍵存儲在哪個節點上，鍵被哈希為一個整數。搜索已排序的節點，以查找大于鍵哈希的最小節點，然后在映射中查找該節點哈希值，以確定它來自哪個節點。

圖片

但是，即便使用了環哈希算法，節點之間的負載分布仍然是不均勻的。例如，每臺服務器有100個副本 ，負載標準差約為10% 。桶大小的99% 置信區間是平均負載(即鍵總數/服務器數量)的0.76至1.28。這種可變性使容量規劃變得棘手。如果將每臺服務器的副本數量增加到1000個節點，標準差減少到3.2% ，而99% 的置信區間減少到0.92到1.09。這需要大量的內存消耗。對于1000個節點，幾乎要4 MB 的數據，O (log n)搜索也會面臨大量的緩存未命中情況。

2.3 跳躍哈希

跳躍哈希（Jump Hashing）克服了環哈希的缺點: 它沒有內存開銷，實際上是完美的密鑰分發。桶的標準差為0.00000764% ，99%的置信區間為0.9999998至1.00000002。

跳躍哈希的go語言參考實現如下：

int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets) {
    int64_t b = --1, j = 0?
    while (j < num_buckets) {
        b = j?
        key = key * 2862933555777941757ULL + 1?
        j = (b + 1) * (double(1LL << 31) / double((key >> 33) + 1))?
    }
    return b?
}

跳躍哈希也很快。循環執行 O (ln n)次，比環哈希的 O (log n)二分查找快一個常量，甚至更快，計算完全在幾個寄存器中完成，不需要支付緩存未命中的開銷。該算法使用鍵的哈希值作為隨機數生成器的種子。然后，它使用隨機數字在桶列表中“跳轉”，最后的一個桶是結果。

圖片

跳躍哈希的主要限制是它只返回范圍為桶數量-1的整數，且不支持任意的桶名。如果使用環哈希，即使兩個不同的實例以不同的順序接收它們的服務器列表，得到的密鑰映射仍然是相同的。使用跳躍哈希的一個方法是提供一個節點編號，而不是服務器名稱。其次，它只能正確地添加和刪除范圍上端的節點，這意味著它不支持任意節點刪除。例如，不能使用它在 memcached 實例集中分發鍵，因為其中一個實例可能會崩潰，而無法從可能的目的列表中刪除崩潰的節點。

環哈希提供了任意桶的添加和刪除能力，但代價是使用高內存以減少負載差異。跳轉哈希提供了有效的完美負載分割，但是在更改節點計數時降低了靈活性。

2.4 多探測器一致性哈希

多探測器一致性哈希（Multi-Probe Consistent Hashing）的基本思想是，不要對節點進行多次哈希處理，使內存使用量增加，而是只對節點進行一次哈希處理，但在查找時對鍵 進行 k 次哈希處理，并返回所有查詢中最接近的節點。K 值由期望的方差決定。

一個多探測器一致性哈希算法的go 語言參考實現如下：

// Hash returns the bucket for a given key
func (m *Multi) Hash(key string) string {
    bkey := []byte(key)

    minDistance := uint64(math.MaxUint64)

    var minhash uint64

    h1 := m.hashf(bkey, m.seeds[0])
    h2 := m.hashf(bkey, m.seeds[1])

    for i := 0; i < m.k; i++ {
        hash := h1 + uint64(i)*h2
        prefix := (hash & m.prefixmask) >> m.prefixshift

        var node uint64
    FOUND:
        for {
            uints := m.bhashes[prefix]

            for _, v := range uints {
                if hash < v {
                    node = v
                    break FOUND
                }
            }

            prefix++
            if prefix == uint64(len(m.bhashes)) {
                prefix = 0
                // wrapped -- take the first node hash we can find
                for uints = nil; uints == nil; prefix++ {
                    uints = m.bhashes[prefix]
                }

                node = uints[0]
                break FOUND
            }
        }

        distance := node - hash
        if distance < minDistance {
            minDistance = distance
            minhash = node
        }
    }

    return m.bmap[minhash]
}

多探測器一致性哈希提供 O (n)空間(每個節點一個條目) ，以及 O (1)添加和刪除節點，局限時查找變慢了。

圖片

對于1.05的峰均比，這意味著負載最重的節點最多比平均值高5%)，k 為21。使用復雜的數據結構，可以得到從 O (k logn)到 O (k)的總查找成本。作為對比，要使環哈希的等效峰均比為1.05，每個節點需要700 ln n 副本。對于100個節點，這意味著超過一兆字節的內存。

2.5 交會哈希

交會哈希（Rendezvous Hashing）也叫最高隨機權哈希，其基本思想是將節點和鍵在一起執行哈希函數，并使用提供最高哈希值的節點。

圖片

其缺點是很難避免遍歷所有節點的 O (n)查找開銷。以下是來自go語言實現的查找示例：

func (r *Rendezvous) Lookup(k string) string {
    khash := r.hash(k)

    var midx int
    var mhash = xorshiftMult64(khash ^ r.nhash[0])

    for i, nhash := range r.nhash[1:] {
        if h := xorshiftMult64(khash ^ nhash); h > mhash {
            midx = i + 1
            mhash = h
        }
    }

    return r.nstr[midx]
}

即使交會哈希的查找復雜的是 O (n)，內部循環也沒有那么昂貴。根據節點的數量，它可以很容易地實現“足夠快”。

2.6 磁懸浮哈希

磁懸浮哈希（Maglev Hashing）源自谷歌，其中一個主要目標是與環哈希或交會哈希相比，擁有較快查找速度和較低的內存使用。該算法有效地生成了一個查找表，允許在恒定的時間內查找節點。這樣做的兩個缺點是生成一個關于節點故障的新表的速度很慢，這也有效地限制了后端節點的最大數量。

圖片

磁懸浮哈希的另一個目標是在添加和刪除節點時實現“最小干擾”，而不是優化。對于磁懸浮哈希作為軟件負載平衡器的場景來說，這就足夠了。

磁懸浮哈希中關于構造查找表的go語言參考實現如下：

func New(names []string, m uint64) *Table {
    offsets, skips := generateOffsetAndSkips(names, m)
    t := &Table{
        n:              len(names),
        skips:          skips,
        currentOffsets: offsets,
        originOffsets:  make([]uint64, len(names)),
        m:              m,
    }

    // save first currentOffsets to originOffsets, for reset
    copy(t.originOffsets, t.currentOffsets)
    t.lookup = t.populate(m, nil)

    return t
}

查找表實際上是節點的隨機排列。查找對鍵進行哈希運算，并檢查該位置的條目。這是帶有一個小常量的 O (1)復雜度，只是對鍵執行哈希的時間。

主流的一致性哈希算法的對比如下：

圖片

3. 一致性哈希的典型應用場景

一致性哈希算法一般應用在分布式系統之中。在分布式系統中，機器節點和數據都很多，節點可能會頻繁地增加或故障宕機，導致數據無法取得。為了解決這個問題，出現了使用一致性哈希算法來規劃數據的存放節點的方法。

3.1 服務副本

分布式系統中的服務副本使用一致性哈希算法來為給定的鍵選擇輔助(或更多)節點。這可以是為了防止節點故障，也可以僅作為第二個節點進行查詢以減少延遲。有些策略使用完整的節點復制，即每個服務器有兩個完整的副本，而其他策略則跨服務器復制鍵。

我們總是能夠以可預測的方式變更鍵或鍵的哈希，并執行完整的第二次查找，但也需要注意在同一個節點上的副本鍵。

有些算法可以直接選擇多個節點進行備份或復制。對于環哈希，使用傳遞到圓上的下一個節點; 對于多探針一致性哈希，使用下一個最接近的節點。交會哈希采取下一個最高(或最低)的節點。跳躍哈希是有點棘手，但它也是可以做到的。

同樣，選擇復制策略也充滿了權衡。

3.2 加權主機

在添加具有不同權重的服務器方面，一致哈希算法的簡單性和有效性各不相同。也就是說，將更多(或更少)負載發送到一個服務器，而不是發送給其他服務器。使用環哈希，可以按照所需的負載縮放副本的數量，但這會極大地增加內存使用。

跳躍哈希 和 多探測器一致性哈希在使用和維持現有的性能保證方面更加棘手。雖然總是可以添加引用原始節點的第二個“影子”節點，但是當負載倍數不是整數時，此方法將失效。一種方法是按一定數量縮放所有節點計數，但這會增加內存和查找時間。

磁懸浮哈希通過改變表的構造過程來獲得權重，這樣權重較大的節點可以更頻繁地在查找表中選擇條目。

加權交會哈希用于為交會哈希算法添加權重，即選擇按權重比例縮放的最高組合哈希。

3.3 負載均衡

使用一致性哈希進行負載平衡是一個很有吸引力的想法。但根據算法的不同，這最終可能不會比隨機分配好，隨機分配會導致分布不平衡。

除了磁懸浮哈希之外，還有兩種一致哈希的負載平衡方法。

一個是基于有界負載的一致性哈希算法。由于鍵分布在服務器之間，因此會檢查負載，如果某個節點已經負載過重，則跳過該節點。這種算法可以到 HAProxy 的復雜均衡器上，也可以作為一個獨立的軟件包使用。

對于選擇連接到哪些后端的客戶端而言，谷歌提出了一種稱為“確定性的子設置”的算法，在其SRE book 中有詳細信息。

4. 一句話小結

一致性哈希算法都在努力平衡鍵的分布、內存使用、查找時間和構建時間(包括節點添加和刪除成本)。只有權衡，沒有完美的一致性哈希算法。