一致性哈希（Consistent Hashing）是一種特殊的哈希算法，主要用于解決分布式系統(tǒng)中節(jié)點(diǎn)動(dòng)態(tài)變化時(shí)的數(shù)據(jù)分布問題。它在保持?jǐn)?shù)據(jù)分布均勻的同時(shí)，盡量減少節(jié)點(diǎn)加入或離開時(shí)需要重新分配的數(shù)據(jù)量。一致性哈希算法在許多場(chǎng)景下都非常有用，例如在緩存系統(tǒng)、負(fù)載均衡器、數(shù)據(jù)庫(kù)分片等應(yīng)用中。
1.一致性哈希解決的問題
問題：
有一個(gè)鍵值對(duì)的集合，還有一些用于鍵值存儲(chǔ)的服務(wù)器例如 memcached，Redis，MySQL等等。在沒有全局存儲(chǔ)目錄的條件下，如何把Key發(fā)布到不同服務(wù)器上，然后可以找到它。
2. 那些一致性哈希算法
2.1 模N哈希
首先，選擇一個(gè)哈希函數(shù)來將鍵(字符串)映射為一個(gè)整數(shù)。這往往排除了像 SHA-1或 MD5這樣的加密算法，因?yàn)槠溆?jì)算成本較高。MurmurHash 以及 xxHash等非加密哈希函數(shù)都是不錯(cuò)的選擇。
如果您有 N 個(gè)服務(wù)器，您可以使用 hash 函數(shù)散列密鑰，并取得結(jié)果的整數(shù)模 N。server := serverList[hash(key) % N]
這種設(shè)置很容易解釋, 計(jì)算成本很低。如果 N 是2的冪，那么只需要比特掩碼即可。
圖片
但是，局限也是顯然的。模N哈希難以應(yīng)對(duì)服務(wù)器的數(shù)量變化。理想的哈希函數(shù)當(dāng)面臨添加或刪除一個(gè)服務(wù)器時(shí)，應(yīng)該只移動(dòng)1/n的鍵，不需要移動(dòng)的鍵不要移動(dòng)。
2.2 環(huán)哈希
環(huán)哈希（ring-based consistent hashing）的基本思想是，每個(gè)服務(wù)器被映射到一個(gè)具有哈希函數(shù)的圓上的一個(gè)點(diǎn)，可以把圓看作所有的整數(shù)0,1,2......2^32-1 的集合。要查找給定鍵的服務(wù)器，需要對(duì)該密鑰執(zhí)行散列并在圓上找到該點(diǎn)。然后向前掃描，直到找到任何服務(wù)器的第一個(gè)哈希值。實(shí)際上，每個(gè)服務(wù)器會(huì)在哈希環(huán)上出現(xiàn)多次。這些額外的點(diǎn)稱為“虛擬節(jié)點(diǎn)”或“ vnode”。這減少了服務(wù)器之間的負(fù)載差異。對(duì)于少量的 vnode，不同的服務(wù)器可以分配不同數(shù)量的鍵。
Ketama 是一個(gè) memcached 客戶段，它使用環(huán)哈希來跨服務(wù)器實(shí)例的鍵分布。一個(gè)ketama算法的go 語(yǔ)言參考實(shí)現(xiàn)如下：
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
}環(huán)哈希算法很簡(jiǎn)單。為了查看給定鍵存儲(chǔ)在哪個(gè)節(jié)點(diǎn)上，鍵被哈希為一個(gè)整數(shù)。搜索已排序的節(jié)點(diǎn)，以查找大于鍵哈希的最小節(jié)點(diǎn)，然后在映射中查找該節(jié)點(diǎn)哈希值，以確定它來自哪個(gè)節(jié)點(diǎn)。
圖片
但是，即便使用了環(huán)哈希算法，節(jié)點(diǎn)之間的負(fù)載分布仍然是不均勻的。例如，每臺(tái)服務(wù)器有100個(gè)副本 ，負(fù)載標(biāo)準(zhǔn)差約為10% 。桶大小的99% 置信區(qū)間是平均負(fù)載(即鍵總數(shù)/服務(wù)器數(shù)量)的0.76至1.28。這種可變性使容量規(guī)劃變得棘手。如果將每臺(tái)服務(wù)器的副本數(shù)量增加到1000個(gè)節(jié)點(diǎn)，標(biāo)準(zhǔn)差減少到3.2% ，而99% 的置信區(qū)間減少到0.92到1.09。這需要大量的內(nèi)存消耗。對(duì)于1000個(gè)節(jié)點(diǎn)，幾乎要4 MB 的數(shù)據(jù)，O (log n)搜索也會(huì)面臨大量的緩存未命中情況。
2.3 跳躍哈希
跳躍哈希（Jump Hashing）克服了環(huán)哈希的缺點(diǎn): 它沒有內(nèi)存開銷，實(shí)際上是完美的密鑰分發(fā)。桶的標(biāo)準(zhǔn)差為0.00000764% ，99%的置信區(qū)間為0.9999998至1.00000002。
跳躍哈希的go語(yǔ)言參考實(shí)現(xiàn)如下：
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?
}跳躍哈希也很快。循環(huán)執(zhí)行 O (ln n)次，比環(huán)哈希的 O (log n)二分查找快一個(gè)常量，甚至更快，計(jì)算完全在幾個(gè)寄存器中完成，不需要支付緩存未命中的開銷。該算法使用鍵的哈希值作為隨機(jī)數(shù)生成器的種子。然后，它使用隨機(jī)數(shù)字在桶列表中“跳轉(zhuǎn)”，最后的一個(gè)桶是結(jié)果。
圖片
跳躍哈希的主要限制是它只返回范圍為桶數(shù)量-1的整數(shù)，且不支持任意的桶名。如果使用環(huán)哈希，即使兩個(gè)不同的實(shí)例以不同的順序接收它們的服務(wù)器列表，得到的密鑰映射仍然是相同的。使用跳躍哈希的一個(gè)方法是提供一個(gè)節(jié)點(diǎn)編號(hào)，而不是服務(wù)器名稱。其次，它只能正確地添加和刪除范圍上端的節(jié)點(diǎn)，這意味著它不支持任意節(jié)點(diǎn)刪除。例如，不能使用它在 memcached 實(shí)例集中分發(fā)鍵，因?yàn)槠渲幸粋€(gè)實(shí)例可能會(huì)崩潰，而無法從可能的目的列表中刪除崩潰的節(jié)點(diǎn)。
環(huán)哈希提供了任意桶的添加和刪除能力，但代價(jià)是使用高內(nèi)存以減少負(fù)載差異。跳轉(zhuǎn)哈希提供了有效的完美負(fù)載分割，但是在更改節(jié)點(diǎn)計(jì)數(shù)時(shí)降低了靈活性。
2.4 多探測(cè)器一致性哈希
多探測(cè)器一致性哈希（Multi-Probe Consistent Hashing）的基本思想是，不要對(duì)節(jié)點(diǎn)進(jìn)行多次哈希處理，使內(nèi)存使用量增加，而是只對(duì)節(jié)點(diǎn)進(jìn)行一次哈希處理，但在查找時(shí)對(duì)鍵 進(jìn)行 k 次哈希處理，并返回所有查詢中最接近的節(jié)點(diǎn)。K 值由期望的方差決定。
一個(gè)多探測(cè)器一致性哈希算法的go 語(yǔ)言參考實(shí)現(xiàn)如下：
// 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]
}多探測(cè)器一致性哈希提供 O (n)空間(每個(gè)節(jié)點(diǎn)一個(gè)條目) ，以及 O (1)添加和刪除節(jié)點(diǎn)，局限時(shí)查找變慢了。
圖片
對(duì)于1.05的峰均比，這意味著負(fù)載最重的節(jié)點(diǎn)最多比平均值高5%)，k 為21。使用復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，可以得到從 O (k logn)到 O (k)的總查找成本。作為對(duì)比，要使環(huán)哈希的等效峰均比為1.05，每個(gè)節(jié)點(diǎn)需要700 ln n 副本。對(duì)于100個(gè)節(jié)點(diǎn)，這意味著超過一兆字節(jié)的內(nèi)存。
2.5 交會(huì)哈希
交會(huì)哈希（Rendezvous Hashing）也叫最高隨機(jī)權(quán)哈希，其基本思想是將節(jié)點(diǎn)和鍵在一起執(zhí)行哈希函數(shù)，并使用提供最高哈希值的節(jié)點(diǎn)。
圖片
其缺點(diǎn)是很難避免遍歷所有節(jié)點(diǎn)的 O (n)查找開銷。以下是來自go語(yǔ)言實(shí)現(xiàn)的查找示例：
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]
}即使交會(huì)哈希的查找復(fù)雜的是 O (n)，內(nèi)部循環(huán)也沒有那么昂貴。根據(jù)節(jié)點(diǎn)的數(shù)量，它可以很容易地實(shí)現(xiàn)“足夠快”。
2.6 磁懸浮哈希
磁懸浮哈希（Maglev Hashing）源自谷歌，其中一個(gè)主要目標(biāo)是與環(huán)哈?；蚪粫?huì)哈希相比，擁有較快查找速度和較低的內(nèi)存使用。該算法有效地生成了一個(gè)查找表，允許在恒定的時(shí)間內(nèi)查找節(jié)點(diǎn)。這樣做的兩個(gè)缺點(diǎn)是生成一個(gè)關(guān)于節(jié)點(diǎn)故障的新表的速度很慢，這也有效地限制了后端節(jié)點(diǎn)的最大數(shù)量。
圖片
磁懸浮哈希的另一個(gè)目標(biāo)是在添加和刪除節(jié)點(diǎn)時(shí)實(shí)現(xiàn)“最小干擾”，而不是優(yōu)化。對(duì)于磁懸浮哈希作為軟件負(fù)載平衡器的場(chǎng)景來說，這就足夠了。
磁懸浮哈希中關(guān)于構(gòu)造查找表的go語(yǔ)言參考實(shí)現(xiàn)如下：
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
}查找表實(shí)際上是節(jié)點(diǎn)的隨機(jī)排列。查找對(duì)鍵進(jìn)行哈希運(yùn)算，并檢查該位置的條目。這是帶有一個(gè)小常量的 O (1)復(fù)雜度，只是對(duì)鍵執(zhí)行哈希的時(shí)間。
主流的一致性哈希算法的對(duì)比如下：
圖片
3. 一致性哈希的典型應(yīng)用場(chǎng)景
一致性哈希算法一般應(yīng)用在分布式系統(tǒng)之中。在分布式系統(tǒng)中，機(jī)器節(jié)點(diǎn)和數(shù)據(jù)都很多，節(jié)點(diǎn)可能會(huì)頻繁地增加或故障宕機(jī)，導(dǎo)致數(shù)據(jù)無法取得。為了解決這個(gè)問題，出現(xiàn)了使用一致性哈希算法來規(guī)劃數(shù)據(jù)的存放節(jié)點(diǎn)的方法。
3.1 服務(wù)副本
分布式系統(tǒng)中的服務(wù)副本使用一致性哈希算法來為給定的鍵選擇輔助(或更多)節(jié)點(diǎn)。這可以是為了防止節(jié)點(diǎn)故障，也可以僅作為第二個(gè)節(jié)點(diǎn)進(jìn)行查詢以減少延遲。有些策略使用完整的節(jié)點(diǎn)復(fù)制，即每個(gè)服務(wù)器有兩個(gè)完整的副本，而其他策略則跨服務(wù)器復(fù)制鍵。
我們總是能夠以可預(yù)測(cè)的方式變更鍵或鍵的哈希，并執(zhí)行完整的第二次查找，但也需要注意在同一個(gè)節(jié)點(diǎn)上的副本鍵。
有些算法可以直接選擇多個(gè)節(jié)點(diǎn)進(jìn)行備份或復(fù)制。對(duì)于環(huán)哈希，使用傳遞到圓上的下一個(gè)節(jié)點(diǎn); 對(duì)于多探針一致性哈希，使用下一個(gè)最接近的節(jié)點(diǎn)。交會(huì)哈希采取下一個(gè)最高(或最低)的節(jié)點(diǎn)。跳躍哈希是有點(diǎn)棘手，但它也是可以做到的。
同樣，選擇復(fù)制策略也充滿了權(quán)衡。
3.2 加權(quán)主機(jī)
在添加具有不同權(quán)重的服務(wù)器方面，一致哈希算法的簡(jiǎn)單性和有效性各不相同。也就是說，將更多(或更少)負(fù)載發(fā)送到一個(gè)服務(wù)器，而不是發(fā)送給其他服務(wù)器。使用環(huán)哈希，可以按照所需的負(fù)載縮放副本的數(shù)量，但這會(huì)極大地增加內(nèi)存使用。
跳躍哈希 和 多探測(cè)器一致性哈希在使用和維持現(xiàn)有的性能保證方面更加棘手。雖然總是可以添加引用原始節(jié)點(diǎn)的第二個(gè)“影子”節(jié)點(diǎn)，但是當(dāng)負(fù)載倍數(shù)不是整數(shù)時(shí)，此方法將失效。一種方法是按一定數(shù)量縮放所有節(jié)點(diǎn)計(jì)數(shù)，但這會(huì)增加內(nèi)存和查找時(shí)間。
磁懸浮哈希通過改變表的構(gòu)造過程來獲得權(quán)重，這樣權(quán)重較大的節(jié)點(diǎn)可以更頻繁地在查找表中選擇條目。
加權(quán)交會(huì)哈希用于為交會(huì)哈希算法添加權(quán)重，即選擇按權(quán)重比例縮放的最高組合哈希。
3.3 負(fù)載均衡
使用一致性哈希進(jìn)行負(fù)載平衡是一個(gè)很有吸引力的想法。但根據(jù)算法的不同，這最終可能不會(huì)比隨機(jī)分配好，隨機(jī)分配會(huì)導(dǎo)致分布不平衡。
除了磁懸浮哈希之外，還有兩種一致哈希的負(fù)載平衡方法。
一個(gè)是基于有界負(fù)載的一致性哈希算法。由于鍵分布在服務(wù)器之間，因此會(huì)檢查負(fù)載，如果某個(gè)節(jié)點(diǎn)已經(jīng)負(fù)載過重，則跳過該節(jié)點(diǎn)。這種算法可以到 HAProxy 的復(fù)雜均衡器上，也可以作為一個(gè)獨(dú)立的軟件包使用。
對(duì)于選擇連接到哪些后端的客戶端而言，谷歌提出了一種稱為“確定性的子設(shè)置”的算法，在其SRE book 中有詳細(xì)信息。
4. 一句話小結(jié)
一致性哈希算法都在努力平衡鍵的分布、內(nèi)存使用、查找時(shí)間和構(gòu)建時(shí)間(包括節(jié)點(diǎn)添加和刪除成本)。只有權(quán)衡，沒有完美的一致性哈希算法。
