[[423969]]

0. 為什么寫本文

有個朋友是做分布式存儲的，有一次聊天他問我一些問題：什么是一致性哈希?一般如何實現?有什么優(yōu)點?

對于這個問題，我的腦海中只是閃現幾個詞匯：md5、hash函數、哈希環(huán)。

在我看來，哈希就是一種算法。一句話概括就是：把無限的數據映射到有限的集合中的一種算法。

朋友說：你這段話很官方，但是等于沒說。

哈哈，身為某廠高級開發(fā)工程師的我，此刻無地自容。慚愧、慚愧，請允許我做一個悲傷的表情。

1. 哈希

對于哈希，日常開發(fā)中在很多場景都會用到，比如：

1. md5 之類的哈希函數
2. 分庫、分表時，使用某個字段的 hash 值對固定數值取模，來確定對應庫表
3. 一個大量數據的集合，根據某個字段作為拆分鍵，對數據進行打散處理
4. PHP的 HashTable、Go的 map、Python 的 dict 等數據結構實現
5. Redis 分片時使用 crc16 對key進行哈希，然后對 16384 取模來確定分片
6. 等等 ......

除上面場景，還有很多地方會用到 hash，而他們都是哈希的一種實現方式。

hash函數

1.1 哈希碰撞

無限個原始數據在經過Hash函數運算之后，得到的哈希結果會有一定的概率相同。那么，這些不同的原始數據得到相同哈希值的情況，就是哈希碰撞。

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

哈希碰撞

需要了解的：

哈希碰撞無法避免 (因為哈希結果值域是有限的，原始數據是無限的)

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

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

1.2 針對哈希碰撞的兩種方案

在出現哈希碰撞情況下常用的方案有：

1. 開放地址法
2. 拉鏈法

開放地址法一般不常使用，讀者可以自行查閱相關資料。

拉鏈法則在很多場景、甚至開源系統(tǒng)都會用到。

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

拉鏈法

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

其中，bucket 為在某一時刻大小固定的數組，下標為哈希值對固定數值取模之后得到。bucket 的大小一般會在某種臨界狀態(tài)下進行自動的擴容、縮容。

查找的時候，根據計算的哈希值先定位到bucket對應位置，然后再遍歷鏈表查找對應數據。

注意：

原始數據經過Hash計算一般會得到比較大的哈希值，此時需用哈希值對bucket大小取模來確定數據存儲位置

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

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

1.3 為什么用哈希

筆者以前接手過一個項目，每天數據量2億多條，這些數據需要落盤。建表的話，如果存在一張表里面，那將會是一個災難。當時筆者建了10張表，使用用戶uid對10取模來確定當前數據落在哪一張表里面。

取模

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

在這種情況之下，使用哈希對大量數據進行拆分再合適不過了。

1.4 普通哈希的缺點

優(yōu)點說了一堆，那么接下來說一下不好的地方。

假設有這樣一種場景：原來使用了10張表存儲數據，完全沒有問題。突然有一天，業(yè)務要求現在使用20張表或者5張表存儲數據，那該怎么辦?

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

此時老的數據就需要進行處理，怎么辦?rehash!

對全量數據進行rehash，使用新的hash函數重新計算所有數據，再把這些數據存儲在新的表中。

實際開發(fā)中出現 rehash 的場景會非常多，所以就需要提前做一些預案。

如果數據量非常大的話，一般有兩種方案：

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

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

方案2不停服進行遷移，相當于邊開飛機邊換輪胎。風險高、邏輯處理復雜。

還有就是，對于數據量大的情況之下，rehash可能會是個漫長的過程

那么，有沒有其他好的解決辦法呢?

辦法是有，解決問題的角度從遷移全量數據變成了遷移部分數據。它就是：一致性哈希。

2. 一致性哈希

維基百科告訴我們：

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

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

一致哈希也可用于實現健壯緩存來減少大型Web應用中系統(tǒng)部分失效帶來的負面影響。

一致哈希的概念還被應用于分布式散列表(DHT)的設計。DHT使用一致哈希來劃分分布式系統(tǒng)的節(jié)點。所有關鍵字都可以通過一個連接所有節(jié)點的覆蓋網絡高效地定位到某個節(jié)點。

David Karger及其合作者列出了使得一致哈希在互聯網分布式緩存中非常有用的幾個特性：

• 冗余少
• 負載均衡
• 過渡平滑
• 存儲均衡
• 關鍵詞單調

2.1 實現方式 - 哈希環(huán)

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

當刪除一臺節(jié)點機器時，這臺機器上保存的所有對象都要移動到下一臺機器。

添加一臺機器到圓環(huán)邊上某個點時，這個點的下一臺機器需要將這個節(jié)點前對應的對象移動到新機器上。

更改對象在節(jié)點機器上的分布可以通過調整節(jié)點機器的位置來實現。

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

哈希環(huán)

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

對不同節(jié)點服務器的某些參數(mac地址、IP地址等)進行hash計算，用hash值對2^32取模，確定當前服務器落在環(huán)某一個節(jié)點上

數據存儲時，對指定的key進行hash計算，然后用hash值對2^32取模，確定數據落在環(huán)的哪一個節(jié)點上，得到環(huán)的節(jié)點值之后，順時針方向找到遇到的第一臺服務器，這臺服務器就是存儲當前數據的地方。

普通哈希環(huán)

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

那樣的話，可知：

• 數據D、E、A存儲在服務器1
• 數據B、C存儲在服務器2
• 沒有數據存儲在服務器3

2.2 場景復現

場景1(縮容)

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

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

場景2(擴容)

假設，在數據B、C之間添加服務器4，那么只需要遷移存儲在服務器2上的數據B到服務器4即可。

通過上面兩個場景可以看出，無論是擴容還是縮容，相對于傳統(tǒng)的hash方式，在發(fā)生擴、縮容時，只需要遷移一部分數據。大大簡化了數據的遷移量，也會大大降低發(fā)生問題的概率。

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

通過上面例子可以看出：

數據D、E、A存儲在服務器1

數據B、C存儲在服務器2

沒有數據存儲在服務器3

不知道你發(fā)現沒有：服務器3沒有存儲數據，服務器1卻存儲最多的數據，此時就發(fā)生了數據傾斜。

那么，有什么辦法來解決數據傾斜嗎?

辦法就是需要對負載策略進行優(yōu)化，引入虛擬服務器節(jié)點。

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

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

此時，服務器節(jié)點由原來的3個節(jié)點變?yōu)榱?個節(jié)點。

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

• 數據A存儲在服務器1-A
• 數據B存儲在服務器3-A
• 數據C存儲在服務器2-A
• 數據D存儲在服務器1-B
• 數據E存儲在服務器2-B

由于，上面的服務器節(jié)點為虛擬服務器節(jié)點，最終數據存儲在的真實位置：

• 數據A、D存儲在服務器1
• 數據C、E存儲在服務器2
• 數據 B 存儲在服務器3

由此可見，通過引入服務器虛擬節(jié)點，數據的存儲變得比較均衡。

3. 總結

通過一系列的場景分析，我們認識了哈希、哈希碰撞、哈希碰撞的解決辦法，并拋出了普通哈希存在的數據全量遷移問題。

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

實際場景中，面對不同的業(yè)務或許會有些許差異。但是，大致邏輯類似。