一文搞懂負載均衡中的一致性哈希算法

算法設計 Java Memcached Nginx Redis Cassandra C語言 Lucene GitHub Google Hadoop HBase Java面經 2019-04-07

作者：徐靖峰
來源：https://www.cnkirito.moe/consistent-hash-lb/

一致性哈希算法在很多領域有應用，例如分佈式緩存領域的 MemCache，Redis，負載均衡領域的 Nginx，各類 RPC 框架。不同領域場景不同，需要顧及的因素也有所差異，本文主要討論在負載均衡中一致性哈希算法的設計。

在介紹一致性哈希算法之前，我將會介紹一些哈希算法，討論它們的區別和使用場景。也會給出一致性哈希算法的 Java 通用實現，可以直接引用，文末會給出 github 地址。

友情提示：閱讀本文前，最好對一致性哈希算法有所瞭解，例如你最好聽過一致性哈希環這個概念，我會在基本概念上縮短篇幅。

一致性哈希負載均衡介紹

負載均衡這個概念可以抽象為：從 n 個候選服務器中選擇一個進行通信的過程。負載均衡算法有多種多樣的實現方式：隨機、輪詢、最小負載優先等，其中也包括了今天的主角：一致性哈希負載均衡。一致性哈希負載均衡需要保證的是“相同的請求儘可能落到同一個服務器上”，注意這短短的一句描述，卻包含了相當大的信息量。“相同的請求” — 什麼是相同的請求？一般在使用一致性哈希負載均衡時，需要指定一個 key 用於 hash 計算，可能是：

請求方 IP
請求服務名稱，參數列表構成的串
用戶 ID

“儘可能” —為什麼不是一定？因為服務器可能發生上下線，所以少數服務器的變化不應該影響大多數的請求。這也呼應了算法名稱中的“一致性”。

同時，一個優秀的負載均衡算法還有一個隱性要求：流量儘可能均勻分佈。

綜上所述，我們可以概括出一致性哈希負載均衡算法的設計思路。

儘可能保證每個服務器節點均勻的分攤流量
儘可能保證服務器節點的上下線不影響流量的變更

哈希算法介紹

哈希算法是一致性哈希算法中重要的一個組成部分，你可以藉助 Java 中的 inthashCode()去理解它。說到哈希算法，你想到了什麼？Jdk 中的 hashCode、SHA-1、MD5，除了這些耳熟能詳的哈希算法，還存在很多其他實現，詳見 HASH 算法一覽。可以將他們分成三代：

第一代：SHA-1（1993），MD5（1992），CRC（1975），Lookup3（2006）
第二代：MurmurHash（2008）
第三代：CityHash， SpookyHash（2011）

這些都可以認為是廣義上的哈希算法，你可以在 wiki 百科中查看所有的哈希算法。當然還有一些哈希算法如：Ketama，專門為一致性哈希算法而設計。

既然有這麼多哈希算法，那必然會有人問：當我們在討論哈希算法時，我們再考慮哪些東西？我大概總結下有以下四點：

實現複雜程度
分佈均勻程度
哈希碰撞概率
性能

先聊聊性能，是不是性能越高就越好呢？你如果有看過我曾經的文章《該如何設計你的 PasswordEncoder?》，應該能瞭解到，在設計加密器這個場景下，慢 hash 算法反而有優勢；而在負載均衡這個場景下，安全性不是需要考慮的因素，所以性能自然是越高越好。

優秀的算法通常比較複雜，但不足以構成評價標準，有點黑貓白貓論，所以 2，3 兩點：分佈均勻程度，哈希碰撞概率成了主要考慮的因素。

我挑選了幾個值得介紹的哈希算法，重點介紹下。

MurmurHash 算法：高運算性能，低碰撞率，由 Austin Appleby 創建於 2008 年，現已應用到 Hadoop、libstdc++、nginx、libmemcached 等開源系統。2011 年 Appleby 被 Google 僱傭，隨後 Google 推出其變種的 CityHash 算法。官方只提供了 C 語言的實現版本。Java 界中 Redis，Memcached，Cassandra，HBase，Lucene 都在使用它。在 Java 的實現，Guava 的 Hashing 類裡有，上面提到的 Jedis，Cassandra 裡都有相關的 Util 類。
FNV 算法：全名為 Fowler-Noll-Vo 算法，是以三位發明人 Glenn Fowler，Landon Curt Noll，Phong Vo 的名字來命名的，最早在 1991 年提出。特點和用途：FNV 能快速 hash 大量數據並保持較小的衝突率，它的高度分散使它適用於 hash 一些非常相近的字符串，比如 URL，hostname，文件名，text，IP 地址等。
Ketama 算法：將它稱之為哈希算法其實不太準確，稱之為一致性哈希算法可能更為合適，其他的哈希算法有通用的一致性哈希算法實現，只不過是替換了哈希方式而已，但 Ketama 是一整套的流程，我們將在後面介紹。

以上三者都是最合適的一致性哈希算法的強力爭奪者。

一致性哈希算法實現

一致性哈希的概念我不做贅述，簡單介紹下這個負載均衡中的一致性哈希環。首先將服務器（ip+端口號）進行哈希，映射成環上的一個節點，在請求到來時，根據指定的 hash key 同樣映射到環上，並順時針選取最近的一個服務器節點進行請求（在本圖中，使用的是 userId 作為 hash key）。

當環上的服務器較少時，即使哈希算法選擇得當，依舊會遇到大量請求落到同一個節點的問題，為避免這樣的問題，大多數一致性哈希算法的實現度引入了虛擬節點的概念。

在上圖中，只有兩臺物理服務器節點：11.1.121.1 和 11.1.121.2，我們通過添加後綴的方式，克隆出了另外三份節點，使得環上的節點分佈的均勻。一般來說，物理節點越多，所需的虛擬節點就越少。

介紹完了一致性哈希換，我們便可以對負載均衡進行建模了：

下面直接給出通用的算法實現：

對上述的程序做簡單的解讀：

Server 是對服務器的抽象，一般是 ip+port 的形式。

public class Server {
 private String url;
}

Invocation 是對請求的抽象，包含一個用於 hash 的 key。

public class Invocation {
 private String hashKey;
}

使用 TreeMap 作為一致性哈希環的數據結構，ring.ceilingEntry 可以獲取環上最近的一個節點。在 buildConsistentHashRing 之中包含了構建一致性哈希環的過程，默認加入了 10 個虛擬節點。

計算方差，標準差的公式：

其中，HashStrategy 是下文中重點討論的一個內容，他是對 hash 算法的抽象，我們將會著重對比各種 hash 算法給測評結果帶來的差異性。

public interface HashStrategy {
 int getHashCode(String origin);
}

測評程序

前面我們已經明確了一個優秀的一致性哈希算法的設計思路。這一節我們給出實際的量化指標：假設 m 次請求打到 n 個候選服務器上

統計每個服務節點收到的流量，計算方差、標準差。測量流量分佈均勻情況，我們可以模擬 10000 個隨機請求，打到 100 個指定服務器，測試最後個節點的方差，標準差。
記錄 m 次請求落到的服務器節點，下線 20% 的服務器，重放流量，統計 m 次請求中落到跟原先相同服務器的概率。測量節點上下線的情況，我們可以模擬 10000 個隨機請求，打到 100 個指定服務器，之後下線 20 個服務器並重放流量，統計請求到相同服務器的比例。

不同哈希算法的實現及測評

最簡單、經典的 hashCode 實現：

public class JdkHashCodeStrategy implements HashStrategy {
 @Override
 public int getHashCode(String origin) {
 return origin.hashCode();
 }
}

FNV1_32_HASH 算法實現：

CRC 算法：

Ketama 算法：

MurmurHash 算法：

其中方差和標準差反映了均勻情況，越低越好，可以發現 MurmurHashStrategy，KetamaHashStrategy，FnvHashStrategy 都表現的不錯。

不變流量比例體現了服務器上下線對原有請求的影響程度，不變流量比例越高越高，可以發現 KetamaHashStrategy 和 MurmurHashStrategy 表現最為優秀。

我並沒有對小集群，小流量進行測試，樣本偏差性較大，僅從這個常見場景來看，MurmurHashStrategy 是一個不錯的選擇，多次測試後發現 FnvHashStrategy，KetamaHashStrategy，MurmurHashStrategy 差距不是很大。

至於性能測試，MurmurHash 也十分的高性能，我並沒有做測試（感興趣的同學可以對幾種 strategy 用 JMH 測評一下）,這裡我貼一下 MurmurHash 官方的測評數據：

OneAtATime - 354.163715 mb/sec
FNV - 443.668038 mb/sec
SuperFastHash - 985.335173 mb/sec
lookup3 - 988.080652 mb/sec
MurmurHash 1.0 - 1363.293480 mb/sec
MurmurHash 2.0 - 2056.885653 mb/sec