[[423969]]

0. 為什么寫(xiě)本文

有個(gè)朋友是做分布式存儲(chǔ)的，有一次聊天他問(wèn)我一些問(wèn)題：什么是一致性哈希?一般如何實(shí)現(xiàn)?有什么優(yōu)點(diǎn)?

對(duì)于這個(gè)問(wèn)題，我的腦海中只是閃現(xiàn)幾個(gè)詞匯：md5、hash函數(shù)、哈希環(huán)。

在我看來(lái)，哈希就是一種算法。一句話概括就是：把無(wú)限的數(shù)據(jù)映射到有限的集合中的一種算法。

朋友說(shuō)：你這段話很官方，但是等于沒(méi)說(shuō)。

哈哈，身為某廠高級(jí)開(kāi)發(fā)工程師的我，此刻無(wú)地自容。慚愧、慚愧，請(qǐng)?jiān)试S我做一個(gè)悲傷的表情。

1. 哈希

對(duì)于哈希，日常開(kāi)發(fā)中在很多場(chǎng)景都會(huì)用到，比如：

1. md5 之類的哈希函數(shù)
2. 分庫(kù)、分表時(shí)，使用某個(gè)字段的 hash 值對(duì)固定數(shù)值取模，來(lái)確定對(duì)應(yīng)庫(kù)表
3. 一個(gè)大量數(shù)據(jù)的集合，根據(jù)某個(gè)字段作為拆分鍵，對(duì)數(shù)據(jù)進(jìn)行打散處理
4. PHP的 HashTable、Go的 map、Python 的 dict 等數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)
5. Redis 分片時(shí)使用 crc16 對(duì)key進(jìn)行哈希，然后對(duì) 16384 取模來(lái)確定分片
6. 等等 ......

除上面場(chǎng)景，還有很多地方會(huì)用到 hash，而他們都是哈希的一種實(shí)現(xiàn)方式。

hash函數(shù)

1.1 哈希碰撞

無(wú)限個(gè)原始數(shù)據(jù)在經(jīng)過(guò)Hash函數(shù)運(yùn)算之后，得到的哈希結(jié)果會(huì)有一定的概率相同。那么，這些不同的原始數(shù)據(jù)得到相同哈希值的情況，就是哈希碰撞。

例如下圖所示：c、d在經(jīng)過(guò)某個(gè)哈希函數(shù)計(jì)算之后得到相同的哈希值10，那么c、d 就發(fā)生了哈希碰撞。

哈希碰撞

需要了解的：

哈希碰撞無(wú)法避免 (因?yàn)楣＝Y(jié)果值域是有限的，原始數(shù)據(jù)是無(wú)限的)

哈希值域越大，碰撞概率一般越低

好的哈希函數(shù)除了運(yùn)算速度外，還需要盡量小的哈希碰撞概率

1.2 針對(duì)哈希碰撞的兩種方案

在出現(xiàn)哈希碰撞情況下常用的方案有：

1. 開(kāi)放地址法
2. 拉鏈法

開(kāi)放地址法一般不常使用，讀者可以自行查閱相關(guān)資料。

拉鏈法則在很多場(chǎng)景、甚至開(kāi)源系統(tǒng)都會(huì)用到。

例如：PHP的 HashTable(PHP5使用雙向鏈表、PHP7使用數(shù)組)、以及Go的map底層實(shí)現(xiàn)。

拉鏈法

如圖所示，c、d的哈希結(jié)果都為10，在存儲(chǔ)的時(shí)候使用鏈表來(lái)把他們串在一起(就像拉了一條鎖鏈一樣)。

其中，bucket 為在某一時(shí)刻大小固定的數(shù)組，下標(biāo)為哈希值對(duì)固定數(shù)值取模之后得到。bucket 的大小一般會(huì)在某種臨界狀態(tài)下進(jìn)行自動(dòng)的擴(kuò)容、縮容。

查找的時(shí)候，根據(jù)計(jì)算的哈希值先定位到bucket對(duì)應(yīng)位置，然后再遍歷鏈表查找對(duì)應(yīng)數(shù)據(jù)。

注意：

原始數(shù)據(jù)經(jīng)過(guò)Hash計(jì)算一般會(huì)得到比較大的哈希值，此時(shí)需用哈希值對(duì)bucket大小取模來(lái)確定數(shù)據(jù)存儲(chǔ)位置

理想情況下，不會(huì)有哈希碰撞，數(shù)值落在bucket的不同位置，查找時(shí)間復(fù)雜度為 O(1)

糟糕情況下，數(shù)據(jù)全部哈希碰撞，數(shù)值都落在bucket同一個(gè)位置，查找時(shí)間復(fù)雜度為 O(n)

1.3 為什么用哈希

筆者以前接手過(guò)一個(gè)項(xiàng)目，每天數(shù)據(jù)量2億多條，這些數(shù)據(jù)需要落盤(pán)。建表的話，如果存在一張表里面，那將會(huì)是一個(gè)災(zāi)難。當(dāng)時(shí)筆者建了10張表，使用用戶uid對(duì)10取模來(lái)確定當(dāng)前數(shù)據(jù)落在哪一張表里面。

取模

其中，uid%10 相當(dāng)于hash算法，這樣的話就把2億多條的數(shù)量分拆在不同的表里面，減少了單表數(shù)據(jù)量，好處的話：可以提升查詢速度、數(shù)據(jù)在同步時(shí)效率提升等等。

在這種情況之下，使用哈希對(duì)大量數(shù)據(jù)進(jìn)行拆分再合適不過(guò)了。

1.4 普通哈希的缺點(diǎn)

優(yōu)點(diǎn)說(shuō)了一堆，那么接下來(lái)說(shuō)一下不好的地方。

假設(shè)有這樣一種場(chǎng)景：原來(lái)使用了10張表存儲(chǔ)數(shù)據(jù)，完全沒(méi)有問(wèn)題。突然有一天，業(yè)務(wù)要求現(xiàn)在使用20張表或者5張表存儲(chǔ)數(shù)據(jù)，那該怎么辦?

由于表的個(gè)數(shù)發(fā)生變化，此時(shí)的hash函數(shù) uid%10 就應(yīng)該變?yōu)?uid%20 或者 uid%5。

此時(shí)老的數(shù)據(jù)就需要進(jìn)行處理，怎么辦?rehash!

對(duì)全量數(shù)據(jù)進(jìn)行rehash，使用新的hash函數(shù)重新計(jì)算所有數(shù)據(jù)，再把這些數(shù)據(jù)存儲(chǔ)在新的表中。

實(shí)際開(kāi)發(fā)中出現(xiàn) rehash 的場(chǎng)景會(huì)非常多，所以就需要提前做一些預(yù)案。

如果數(shù)據(jù)量非常大的話，一般有兩種方案：

1. 停服維護(hù)，在維護(hù)期間進(jìn)行數(shù)據(jù) rehash 遷移
2. 異步遷移，寫(xiě)數(shù)據(jù)的時(shí)候，使用新的哈希函數(shù)確認(rèn)落在哪一張表里面。查詢的時(shí)候，如果發(fā)現(xiàn)數(shù)據(jù)沒(méi)有遷移完成，則需要同時(shí)使用多個(gè)hash函數(shù)，從多張表中讀取數(shù)據(jù)(假設(shè)還牽扯分頁(yè)，則會(huì)更加麻煩)。在提供服務(wù)的同時(shí)，對(duì)老數(shù)據(jù)進(jìn)行rehash遷移。

方案1需要停服，這就要看產(chǎn)品、公司業(yè)務(wù)是否允許。允許的情況之下，是最優(yōu)方案。

方案2不停服進(jìn)行遷移，相當(dāng)于邊開(kāi)飛機(jī)邊換輪胎。風(fēng)險(xiǎn)高、邏輯處理復(fù)雜。

還有就是，對(duì)于數(shù)據(jù)量大的情況之下，rehash可能會(huì)是個(gè)漫長(zhǎng)的過(guò)程

那么，有沒(méi)有其他好的解決辦法呢?

辦法是有，解決問(wèn)題的角度從遷移全量數(shù)據(jù)變成了遷移部分?jǐn)?shù)據(jù)。它就是：一致性哈希。

2. 一致性哈希

維基百科告訴我們：

一致哈希 是一種特殊的哈希算法。在使用一致哈希算法后，哈希表槽位數(shù)(大小)的改變平均只需要對(duì)K/n 個(gè)關(guān)鍵字重新映射，其中 K是關(guān)鍵字的數(shù)量，n是槽位數(shù)量。然而在傳統(tǒng)的哈希表中，添加或刪除一個(gè)槽位的幾乎需要對(duì)所有關(guān)鍵字進(jìn)行重新映射。

一致哈希由MIT的Karger及其合作者提出，現(xiàn)在這一思想已經(jīng)擴(kuò)展到其它領(lǐng)域。在這篇1997年發(fā)表的學(xué)術(shù)論文中介紹了“一致哈希”如何應(yīng)用于用戶易變的分布式Web服務(wù)中。哈希表中的每一個(gè)代表分布式系統(tǒng)中一個(gè)節(jié)點(diǎn)，在系統(tǒng)添加或刪除節(jié)點(diǎn)只需要移動(dòng) K/n項(xiàng)。

一致哈希也可用于實(shí)現(xiàn)健壯緩存來(lái)減少大型Web應(yīng)用中系統(tǒng)部分失效帶來(lái)的負(fù)面影響。

一致哈希的概念還被應(yīng)用于分布式散列表(DHT)的設(shè)計(jì)。DHT使用一致哈希來(lái)劃分分布式系統(tǒng)的節(jié)點(diǎn)。所有關(guān)鍵字都可以通過(guò)一個(gè)連接所有節(jié)點(diǎn)的覆蓋網(wǎng)絡(luò)高效地定位到某個(gè)節(jié)點(diǎn)。

David Karger及其合作者列出了使得一致哈希在互聯(lián)網(wǎng)分布式緩存中非常有用的幾個(gè)特性：

• 冗余少
• 負(fù)載均衡
• 過(guò)渡平滑
• 存儲(chǔ)均衡
• 關(guān)鍵詞單調(diào)

2.1 實(shí)現(xiàn)方式 - 哈希環(huán)

一致哈希將每個(gè)對(duì)象映射到圓環(huán)邊上的一個(gè)點(diǎn)，系統(tǒng)再將可用的節(jié)點(diǎn)機(jī)器映射到圓環(huán)的不同位置。查找某個(gè)對(duì)象對(duì)應(yīng)的機(jī)器時(shí)，需要用一致哈希算法計(jì)算得到對(duì)象對(duì)應(yīng)圓環(huán)邊上位置，沿著圓環(huán)邊上查找直到遇到某個(gè)節(jié)點(diǎn)機(jī)器，這臺(tái)機(jī)器即為對(duì)象應(yīng)該保存的位置。

當(dāng)刪除一臺(tái)節(jié)點(diǎn)機(jī)器時(shí)，這臺(tái)機(jī)器上保存的所有對(duì)象都要移動(dòng)到下一臺(tái)機(jī)器。

添加一臺(tái)機(jī)器到圓環(huán)邊上某個(gè)點(diǎn)時(shí)，這個(gè)點(diǎn)的下一臺(tái)機(jī)器需要將這個(gè)節(jié)點(diǎn)前對(duì)應(yīng)的對(duì)象移動(dòng)到新機(jī)器上。

更改對(duì)象在節(jié)點(diǎn)機(jī)器上的分布可以通過(guò)調(diào)整節(jié)點(diǎn)機(jī)器的位置來(lái)實(shí)現(xiàn)。

假設(shè)有一個(gè)環(huán)形結(jié)構(gòu)，上面有很多節(jié)點(diǎn)，一般為 2的32次方。

哈希環(huán)

我們需要做的事情大致如下：

對(duì)不同節(jié)點(diǎn)服務(wù)器的某些參數(shù)(mac地址、IP地址等)進(jìn)行hash計(jì)算，用hash值對(duì)2^32取模，確定當(dāng)前服務(wù)器落在環(huán)某一個(gè)節(jié)點(diǎn)上

數(shù)據(jù)存儲(chǔ)時(shí)，對(duì)指定的key進(jìn)行hash計(jì)算，然后用hash值對(duì)2^32取模，確定數(shù)據(jù)落在環(huán)的哪一個(gè)節(jié)點(diǎn)上，得到環(huán)的節(jié)點(diǎn)值之后，順時(shí)針?lè)较蛘业接龅降牡谝慌_(tái)服務(wù)器，這臺(tái)服務(wù)器就是存儲(chǔ)當(dāng)前數(shù)據(jù)的地方。

普通哈希環(huán)

從圖中可以看到，有三臺(tái)服務(wù)器分別落在哈希環(huán)的不同節(jié)點(diǎn)位置。數(shù)據(jù)A、B、C、D、E也落在環(huán)的不同位置。根據(jù)一致性哈希要求，數(shù)據(jù)在計(jì)算得到自己的環(huán)中節(jié)點(diǎn)之后，順時(shí)針找到第一個(gè)服務(wù)器節(jié)點(diǎn)，那臺(tái)服務(wù)器就是數(shù)據(jù)的存儲(chǔ)位置。

那樣的話，可知：

• 數(shù)據(jù)D、E、A存儲(chǔ)在服務(wù)器1
• 數(shù)據(jù)B、C存儲(chǔ)在服務(wù)器2
• 沒(méi)有數(shù)據(jù)存儲(chǔ)在服務(wù)器3

2.2 場(chǎng)景復(fù)現(xiàn)

場(chǎng)景1(縮容)

假設(shè)，服務(wù)器2發(fā)生故障，存在上面的數(shù)據(jù)都需要遷移

那么，此時(shí)只需要遷移服務(wù)器1與服務(wù)器2之間的數(shù)據(jù)B、C到服務(wù)器3即可。

場(chǎng)景2(擴(kuò)容)

假設(shè)，在數(shù)據(jù)B、C之間添加服務(wù)器4，那么只需要遷移存儲(chǔ)在服務(wù)器2上的數(shù)據(jù)B到服務(wù)器4即可。

通過(guò)上面兩個(gè)場(chǎng)景可以看出，無(wú)論是擴(kuò)容還是縮容，相對(duì)于傳統(tǒng)的hash方式，在發(fā)生擴(kuò)、縮容時(shí)，只需要遷移一部分?jǐn)?shù)據(jù)。大大簡(jiǎn)化了數(shù)據(jù)的遷移量，也會(huì)大大降低發(fā)生問(wèn)題的概率。

2.3 優(yōu)化版本的哈希環(huán)

通過(guò)上面例子可以看出：

數(shù)據(jù)D、E、A存儲(chǔ)在服務(wù)器1

數(shù)據(jù)B、C存儲(chǔ)在服務(wù)器2

沒(méi)有數(shù)據(jù)存儲(chǔ)在服務(wù)器3

不知道你發(fā)現(xiàn)沒(méi)有：服務(wù)器3沒(méi)有存儲(chǔ)數(shù)據(jù)，服務(wù)器1卻存儲(chǔ)最多的數(shù)據(jù)，此時(shí)就發(fā)生了數(shù)據(jù)傾斜。

那么，有什么辦法來(lái)解決數(shù)據(jù)傾斜嗎?

辦法就是需要對(duì)負(fù)載策略進(jìn)行優(yōu)化，引入虛擬服務(wù)器節(jié)點(diǎn)。

原來(lái)的一臺(tái)服務(wù)器，在哈希環(huán)上只能擁有一個(gè)節(jié)點(diǎn)。那么，此時(shí)我們對(duì)每一臺(tái)服務(wù)器進(jìn)行虛擬。例如：原來(lái)的服務(wù)器1，現(xiàn)在虛擬為2臺(tái)，服務(wù)器1-A、服務(wù)器1-B，此時(shí)這2臺(tái)虛擬服務(wù)器會(huì)在哈希環(huán)上擁有不同的2個(gè)節(jié)點(diǎn)(但是它們實(shí)際映射到同一臺(tái)真實(shí)的服務(wù)器上)。此時(shí)，哈希環(huán)就發(fā)生了變化。

具有虛擬節(jié)點(diǎn)的哈希環(huán)

此時(shí)，服務(wù)器節(jié)點(diǎn)由原來(lái)的3個(gè)節(jié)點(diǎn)變?yōu)榱?個(gè)節(jié)點(diǎn)。

根據(jù)一致性哈希要求，數(shù)據(jù)存儲(chǔ)的位置變?yōu)椋?/p>

• 數(shù)據(jù)A存儲(chǔ)在服務(wù)器1-A
• 數(shù)據(jù)B存儲(chǔ)在服務(wù)器3-A
• 數(shù)據(jù)C存儲(chǔ)在服務(wù)器2-A
• 數(shù)據(jù)D存儲(chǔ)在服務(wù)器1-B
• 數(shù)據(jù)E存儲(chǔ)在服務(wù)器2-B

由于，上面的服務(wù)器節(jié)點(diǎn)為虛擬服務(wù)器節(jié)點(diǎn)，最終數(shù)據(jù)存儲(chǔ)在的真實(shí)位置：

• 數(shù)據(jù)A、D存儲(chǔ)在服務(wù)器1
• 數(shù)據(jù)C、E存儲(chǔ)在服務(wù)器2
• 數(shù)據(jù) B 存儲(chǔ)在服務(wù)器3

由此可見(jiàn)，通過(guò)引入服務(wù)器虛擬節(jié)點(diǎn)，數(shù)據(jù)的存儲(chǔ)變得比較均衡。

3. 總結(jié)

通過(guò)一系列的場(chǎng)景分析，我們認(rèn)識(shí)了哈希、哈希碰撞、哈希碰撞的解決辦法，并拋出了普通哈希存在的數(shù)據(jù)全量遷移問(wèn)題。

同時(shí)，也找到了解決全量數(shù)據(jù)遷移的辦法——一致性哈希，通過(guò)對(duì)一致性哈希的認(rèn)識(shí)，了解到它所擁有的巨大潛力。但是，面對(duì)大數(shù)據(jù)量存儲(chǔ)的場(chǎng)景，可能會(huì)出現(xiàn)數(shù)據(jù)傾斜，造成某些服務(wù)器的高負(fù)載。在引入了服務(wù)器虛擬節(jié)點(diǎn)之后，對(duì)一致性哈希的負(fù)載進(jìn)行了優(yōu)化，從而達(dá)到了一種各個(gè)服務(wù)器均衡的狀態(tài)。

實(shí)際場(chǎng)景中，面對(duì)不同的業(yè)務(wù)或許會(huì)有些許差異。但是，大致邏輯類似。