大家好，我是藍胖子，想起之前學算法的時候，常常只知表面，不得精髓，這個算法到底有哪些應(yīng)用場景，如何應(yīng)用在工作中，后來隨著工作的深入，一些不懂的問題才慢慢被抽絲剝繭分解出來。

今天我們就來看看工作和面試中經(jīng)常被點名的算法，一致性hash算法，并且我會介紹它在實際的應(yīng)用場景并用代碼實現(xiàn)出來。

原理介紹

首先我們來看看一致性hash的定義和算法思想，一致性hash算法有別于傳統(tǒng)hash算法，例如我們有3個節(jié)點，現(xiàn)在要考慮某個key值落到哪個節(jié)點上，傳統(tǒng)hash算法是將key通過hash函數(shù)后通過節(jié)點數(shù)量進行取模運算得到需要落到的節(jié)點序號。

nodeIdx := hashFunc(key)%len(nodes)

傳統(tǒng)hash算法在節(jié)點數(shù)量變化時基本上會導(dǎo)致大量舊數(shù)據(jù)經(jīng)過hash得到的節(jié)點序號失效， 而一致性hash算法則能夠保證只有少部分舊數(shù)據(jù)需要重新改變需要落到的節(jié)點，其余數(shù)據(jù)依然能夠保證節(jié)點擴容后，hash計算得到的節(jié)點序號和之前一致。

一致性hash算法假設(shè)了一個很大的數(shù)字空間，比如2的32次方， 節(jié)點信息會被映射到這個數(shù)字空間的某個數(shù)字上，當我們需要看某個key落到哪個節(jié)點上時，也需要將key進行hash計算得到某個數(shù)字，接著就是找到在這個超大數(shù)字空間內(nèi)，第一個大于該數(shù)字的節(jié)點。如果沒有大于該數(shù)字的節(jié)點，則將第一個節(jié)點作為key需要落到的節(jié)點。

這樣就等效于整個數(shù)字空間構(gòu)成了一個環(huán)形結(jié)構(gòu)，尋找key需要落到的節(jié)點上時，則是從key開始順時針尋找第一個節(jié)點。

用下面的示意圖來表示這個過程會更好理解

我們假設(shè)有3個節(jié)點A1,B1,C1, 這三個節(jié)點的信息(比如主機名，ip等信息)經(jīng)過hash運算后得到了3個數(shù)字，A1對應(yīng)10000，B1對應(yīng)12000，C1 對應(yīng)30000，現(xiàn)在需要看某個key需要落到哪個節(jié)點上，就應(yīng)該這樣來看。

注意這里的節(jié)點我是拿服務(wù)器來舉例，實際上，節(jié)點也可以是表，某個key可以看出是表中的某一行，而一致性性hash算法的目的則是看某一行數(shù)據(jù)應(yīng)該落到哪個表中，總之你可以發(fā)揮你的想象將算法中的事物進行代替抽象，算法的思想終究是不變的。

當某個key經(jīng)過hash計算后，得到數(shù)字9000，那么在順時針尋找到第一個大于它的節(jié)點則是節(jié)點A1,如果key經(jīng)過hash計算后，得到數(shù)字11000，那么尋找到的第一個大于它的節(jié)點則是節(jié)點B1。 注意一種特殊情況，如果key經(jīng)過hash計算得到的數(shù)字是40000，那么此時沒有任何一個節(jié)點是大于這個數(shù)字的，這種情況，正如上圖所示，一致性hash算法的數(shù)組空間是環(huán)形結(jié)構(gòu)，這樣key會落到第一個節(jié)點A1上。

這個只是最初版本的一致性hash，它會在節(jié)點數(shù)量較少時，出現(xiàn)分配數(shù)據(jù)不均勻的情況，比如可能會出現(xiàn)下面的場景

所有的節(jié)點都偏向了一側(cè)，這樣將會有大量數(shù)據(jù)落到A1 節(jié)點，造成數(shù)據(jù)分配不均勻。

所以一致性hash算法的改進版本提出虛擬節(jié)點的概念，通過引入節(jié)點的副本來讓整個hash環(huán)上的節(jié)點數(shù)量多起來。

這里假設(shè)引入的副本是一個，那么參與分配的key的節(jié)點在hash環(huán)上則是6個，6個節(jié)點會讓對hash環(huán)的分配更加均勻，注意虛擬節(jié)點在實際環(huán)境中并不存在，比如這里虛擬節(jié)點A2和實際的節(jié)點A1指向的其實都是同一個實際環(huán)境中的節(jié)點。

應(yīng)用場景

在了解了一致性hash算法的原理后，我們再來看看它的一些適用場景，這樣能夠明白算法的目的，不至于紙上談兵。

負載均衡

首先來看下第一種應(yīng)用場景，在負載均衡中的應(yīng)用，拿memcache舉例，memcache的分布式架構(gòu)其實是依賴客戶端來實現(xiàn)的，客戶端將緩存key通過一致性hash算法計算需要緩存到哪臺后端服務(wù)器上。

而采用一致性hash的好處則是在擴縮容時，不會導(dǎo)致大面積的緩存失效。

如上圖所示，現(xiàn)在要將D1節(jié)點下掉，由于一致性hash算法路由節(jié)點是順時針的，那么只會影響到D1和A1之間的數(shù)據(jù)，這部分數(shù)據(jù)后續(xù)需要在B1節(jié)點上進行讀取，而其他節(jié)點上的數(shù)據(jù)則不會影響。

其實，從這里應(yīng)該能夠看出，一致性hash算法在負載均衡中一個極大的好處就是，對于有狀態(tài)的服務(wù)，能夠做到擴縮容節(jié)點時，影響面最小。

分庫分表

再來看看在分庫分表中的應(yīng)用，如果分表時采用傳統(tǒng)hash算法，當還想擴容表時，不得不面對對所有分表數(shù)據(jù)進行重新hash，重新寫入，這無論是對于磁盤io還是cpu都有極大的壓力，我們應(yīng)該在新增分表時盡量遷移少量的數(shù)據(jù)，減少影響面，這不正是一致性hash算法的功能嗎。

如上圖所示，現(xiàn)在新增了分表D1，那么會影響到之前D1到A1的之前的數(shù)據(jù)，這部分數(shù)據(jù)之前是存到E1這張表上的，現(xiàn)在要遷移到D1表，所以你可以看到新增一個分表只會設(shè)計兩張表部分數(shù)據(jù)的遷移，相比傳統(tǒng)hash的全量遷移，優(yōu)勢不言而喻。

代碼實現(xiàn)

現(xiàn)在我們來看下如何實現(xiàn)下這個算法。

我們需要將節(jié)點信息以及用戶key信息映射成一個數(shù)字，這里要用到hash函數(shù)，hash函數(shù)有很多，我們直接用一個，crc32的hash方式，這樣返回的數(shù)字剛好在2的32次方以內(nèi)。

func ChecksumIEEE(data []byte) uint32

同時我們需要一個映射結(jié)構(gòu)存儲節(jié)點在環(huán)上的hash key與節(jié)點信息，還需要一個有序列表存儲hash key，以便于查詢用戶key對應(yīng)的節(jié)點hash key是哪一個。

這里的代碼比較簡單，短短20多行即可。

package main ? ?import ( ? ? "fmt" ? ? "hash/crc32" ? ? ?"sort") ? ?func main() { ? ? ch := NewConsistentHash(3) ? ? ch.AddNodes("node1") ? ? ch.AddNodes("node2") ? ? ch.AddNodes("node3") ? ? fmt.Println(ch.GetNode("lanpangzi")) ? } ? ?type ConsistentHash struct { ? ? nodes ? ? ?map[uint32]string ? ? keys ? ? ? []uint32 ? ? replicates int ?} ? ?func NewConsistentHash(replicate int) *ConsistentHash { ? ? return &ConsistentHash{ ? ? ? ?nodes: ? ? ?make(map[uint32]string), ? ? ? ?keys: ? ? ? make([]uint32, 0), ? ? ? ?replicates: replicate, ? ? } ? } ?func (c *ConsistentHash) AddNodes(node string) { ? ? for i := 0; i <= c.replicates; i++ { ? ? ? ?nodename := fmt.Sprintf("%s#%d", node, i) ? ? ? ?hashKey := crc32.ChecksumIEEE([]byte(node)) ? ? ? ?c.nodes[hashKey] = nodename ? ? ? ?c.keys = append(c.keys, hashKey) ? ? } ? ? sort.Slice(c.keys, func(i, j int) bool { ? ? ? ?return c.keys[i] < c.keys[j] ? ? }) ? } ?func (c *ConsistentHash) GetNode(key string) string { ? ? hashKey := crc32.ChecksumIEEE([]byte(key)) ? ? nodekeyIndex := sort.Search(len(c.keys), func(i int) bool { ? ? ? ?return c.keys[i] >= hashKey ? ? }) ? ? if nodekeyIndex == len(c.keys) { ? ? ? ?nodekeyIndex = 0 ? ? } ? ? return c.nodes[c.keys[nodekeyIndex]] ? }

我們搞定了一致性hash算法，代碼實現(xiàn)并不難，關(guān)鍵是要搞懂算法的原理以及作用，這樣才能靈活運用。