一文搞懂负载均衡中的一致性哈希算法
一致性哈希算法在很多領域有應用，例如分布式緩存領域的 MemCache，Redis，負載均衡領域的 Nginx，各類 RPC 框架。不同領域場景不同，需要顧及的因素也有所差異，本文主要討論在負載均衡中一致性哈希算法的設計。
在介紹一致性哈希算法之前，我將會介紹一些哈希算法，討論它們的區(qū)別和使用場景。也會給出一致性哈希算法的 Java 通用實現(xiàn)，可以直接引用，文末會給出 github 地址。
友情提示：閱讀本文前，最好對一致性哈希算法有所了解，例如你最好聽過一致性哈希環(huán)這個概念，我會在基本概念上縮短篇幅。
一致性哈希負載均衡介紹
負載均衡這個概念可以抽象為：從 n 個候選服務器中選擇一個進行通信的過程。負載均衡算法有多種多樣的實現(xiàn)方式：隨機、輪詢、最小負載優(yōu)先等，其中也包括了今天的主角：一致性哈希負載均衡。一致性哈希負載均衡需要保證的是“相同的請求盡可能落到同一個服務器上”，注意這短短的一句描述，卻包含了相當大的信息量。“相同的請求” — 什么是相同的請求？一般在使用一致性哈希負載均衡時，需要指定一個 key 用于 hash 計算，可能是：
請求方 IP
請求服務名稱，參數(shù)列表構成的串
用戶 ID
“盡可能” —為什么不是一定？因為服務器可能發(fā)生上下線，所以少數(shù)服務器的變化不應該影響大多數(shù)的請求。這也呼應了算法名稱中的“一致性”。
同時，一個優(yōu)秀的負載均衡算法還有一個隱性要求：流量盡可能均勻分布。
綜上所述，我們可以概括出一致性哈希負載均衡算法的設計思路。
-
盡可能保證每個服務器節(jié)點均勻的分攤流量
-
盡可能保證服務器節(jié)點的上下線不影響流量的變更
哈希算法介紹
哈希算法是一致性哈希算法中重要的一個組成部分，你可以借助 Java 中的 inthashCode()去理解它。 說到哈希算法，你想到了什么？Jdk 中的 hashCode、SHA-1、MD5，除了這些耳熟能詳?shù)墓Ｋ惴?#xff0c;還存在很多其他實現(xiàn)，詳見 HASH 算法一覽?？梢詫⑺麄兎殖扇?#xff1a;
-
第一代：SHA-1（1993），MD5（1992），CRC（1975），Lookup3（2006）
-
第二代：MurmurHash（2008）
-
第三代：CityHash， SpookyHash（2011）
這些都可以認為是廣義上的哈希算法，你可以在 wiki 百科 中查看所有的哈希算法。當然還有一些哈希算法如：Ketama，專門為一致性哈希算法而設計。
既然有這么多哈希算法，那必然會有人問：當我們在討論哈希算法時，我們再考慮哪些東西？我大概總結下有以下四點：
實現(xiàn)復雜程度
分布均勻程度
哈希碰撞概率
性能
先聊聊性能，是不是性能越高就越好呢？你如果有看過我曾經(jīng)的文章 《該如何設計你的 PasswordEncoder?》，應該能了解到，在設計加密器這個場景下，慢 hash 算法反而有優(yōu)勢；而在負載均衡這個場景下，安全性不是需要考慮的因素，所以性能自然是越高越好。
優(yōu)秀的算法通常比較復雜，但不足以構成評價標準，有點黑貓白貓論，所以 2，3 兩點：分布均勻程度，哈希碰撞概率成了主要考慮的因素。
我挑選了幾個值得介紹的哈希算法，重點介紹下。
MurmurHash 算法：高運算性能，低碰撞率，由 Austin Appleby 創(chuàng)建于 2008 年，現(xiàn)已應用到 Hadoop、libstdc++、nginx、libmemcached 等開源系統(tǒng)。2011 年 Appleby 被 Google 雇傭，隨后 Google 推出其變種的 CityHash 算法。官方只提供了 C 語言的實現(xiàn)版本。Java 界中 Redis，Memcached，Cassandra，HBase，Lucene 都在使用它。 在 Java 的實現(xiàn)，Guava 的 Hashing 類里有，上面提到的 Jedis，Cassandra 里都有相關的 Util 類。
FNV 算法：全名為 Fowler-Noll-Vo 算法，是以三位發(fā)明人 Glenn Fowler，Landon Curt Noll，Phong Vo 的名字來命名的，最早在 1991 年提出。 特點和用途：FNV 能快速 hash 大量數(shù)據(jù)并保持較小的沖突率，它的高度分散使它適用于 hash 一些非常相近的字符串，比如 URL，hostname，文件名，text，IP 地址等。
Ketama 算法：將它稱之為哈希算法其實不太準確，稱之為一致性哈希算法可能更為合適，其他的哈希算法有通用的一致性哈希算法實現(xiàn)，只不過是替換了哈希方式而已，但 Ketama 是一整套的流程，我們將在后面介紹。
以上三者都是最合適的一致性哈希算法的強力爭奪者。
一致性哈希算法實現(xiàn)
一致性哈希的概念我不做贅述，簡單介紹下這個負載均衡中的一致性哈希環(huán)。首先將服務器（ip+端口號）進行哈希，映射成環(huán)上的一個節(jié)點，在請求到來時，根據(jù)指定的 hash key 同樣映射到環(huán)上，并順時針選取最近的一個服務器節(jié)點進行請求（在本圖中，使用的是 userId 作為 hash key）。
當環(huán)上的服務器較少時，即使哈希算法選擇得當，依舊會遇到大量請求落到同一個節(jié)點的問題，為避免這樣的問題，大多數(shù)一致性哈希算法的實現(xiàn)度引入了虛擬節(jié)點的概念。
在上圖中，只有兩臺物理服務器節(jié)點：11.1.121.1 和 11.1.121.2，我們通過添加后綴的方式，克隆出了另外三份節(jié)點，使得環(huán)上的節(jié)點分布的均勻。一般來說，物理節(jié)點越多，所需的虛擬節(jié)點就越少。
介紹完了一致性哈希換，我們便可以對負載均衡進行建模了：
public interface LoadBalancer {Server select(List<Server> servers, Invocation invocation); }下面直接給出通用的算法實現(xiàn)：
public class ConsistentHashLoadBalancer implements LoadBalancer{private HashStrategy hashStrategy = new JdkHashCodeStrategy();private final static int VIRTUAL_NODE_SIZE = 10;private final static String VIRTUAL_NODE_SUFFIX = "&&";@Overridepublic Server select(List<Server> servers, Invocation invocation) {int invocationHashCode = hashStrategy.getHashCode(invocation.getHashKey());TreeMap<Integer, Server> ring = buildConsistentHashRing(servers);Server server = locate(ring, invocationHashCode);return server;}private Server locate(TreeMap<Integer, Server> ring, int invocationHashCode) {// 向右找到第一個 keyMap.Entry<Integer, Server> locateEntry = ring.ceilingEntry(invocationHashCode);if (locateEntry == null) {// 想象成一個環(huán)，超過尾部則取第一個 keylocateEntry = ring.firstEntry();}return locateEntry.getValue();}private TreeMap<Integer, Server> buildConsistentHashRing(List<Server> servers) {TreeMap<Integer, Server> virtualNodeRing = new TreeMap<>();for (Server server : servers) {for (int i = 0; i < VIRTUAL_NODE_SIZE; i++) {// 新增虛擬節(jié)點的方式如果有影響，也可以抽象出一個由物理節(jié)點擴展虛擬節(jié)點的類virtualNodeRing.put(hashStrategy.getHashCode(server.getUrl() + VIRTUAL_NODE_SUFFIX + i), server);}}return virtualNodeRing;}}對上述的程序做簡單的解讀：
Server 是對服務器的抽象，一般是 ip+port 的形式。
public class Server {private String url; }Invocation 是對請求的抽象，包含一個用于 hash 的 key。
public class Invocation {private String hashKey; }使用 TreeMap 作為一致性哈希環(huán)的數(shù)據(jù)結構， ring.ceilingEntry 可以獲取環(huán)上最近的一個節(jié)點。在 buildConsistentHashRing 之中包含了構建一致性哈希環(huán)的過程，默認加入了 10 個虛擬節(jié)點。
計算方差，標準差的公式：
public class StatisticsUtil {//方差s^2=[(x1-x)^2 +...(xn-x)^2]/npublic static double variance(Long[] x) {int m = x.length;double sum = 0;for (int i = 0; i < m; i++) {//求和sum += x[i];}double dAve = sum / m;//求平均值double dVar = 0;for (int i = 0; i < m; i++) {//求方差dVar += (x[i] - dAve) * (x[i] - dAve);}return dVar / m;}//標準差σ=sqrt(s^2)public static double standardDeviation(Long[] x) {int m = x.length;double sum = 0;for (int i = 0; i < m; i++) {//求和sum += x[i];}double dAve = sum / m;//求平均值double dVar = 0;for (int i = 0; i < m; i++) {//求方差dVar += (x[i] - dAve) * (x[i] - dAve);}return Math.sqrt(dVar / m);}}其中， HashStrategy 是下文中重點討論的一個內(nèi)容，他是對 hash 算法的抽象，我們將會著重對比各種 hash 算法給測評結果帶來的差異性。
public interface HashStrategy {int getHashCode(String origin); }測評程序
前面我們已經(jīng)明確了一個優(yōu)秀的一致性哈希算法的設計思路。這一節(jié)我們給出實際的量化指標：假設 m 次請求打到 n 個候選服務器上
-
統(tǒng)計每個服務節(jié)點收到的流量，計算方差、標準差。測量流量分布均勻情況，我們可以模擬 10000 個隨機請求，打到 100 個指定服務器，測試最后個節(jié)點的方差，標準差。
-
記錄 m 次請求落到的服務器節(jié)點，下線 20% 的服務器，重放流量，統(tǒng)計 m 次請求中落到跟原先相同服務器的概率。測量節(jié)點上下線的情況，我們可以模擬 10000 個隨機請求，打到 100 個指定服務器，之后下線 20 個服務器并重放流量，統(tǒng)計請求到相同服務器的比例。
不同哈希算法的實現(xiàn)及測評
最簡單、經(jīng)典的 hashCode 實現(xiàn)：
public class JdkHashCodeStrategy implements HashStrategy {@Overridepublic int getHashCode(String origin) {return origin.hashCode();} }FNV132HASH 算法實現(xiàn)：
public class FnvHashStrategy implements HashStrategy {private static final long FNV_32_INIT = 2166136261L;private static final int FNV_32_PRIME = 16777619;@Overridepublic int getHashCode(String origin) {final int p = FNV_32_PRIME;int hash = (int) FNV_32_INIT;for (int i = 0; i < origin.length(); i++)hash = (hash ^ origin.charAt(i)) * p;hash += hash << 13;hash ^= hash >> 7;hash += hash << 3;hash ^= hash >> 17;hash += hash << 5;hash = Math.abs(hash);return hash;} }CRC 算法：
public class CRCHashStrategy implements HashStrategy {@Overridepublic int getHashCode(String origin) {CRC32 crc32 = new CRC32();crc32.update(origin.getBytes());return (int) ((crc32.getValue() >> 16) & 0x7fff & 0xffffffffL);} }Ketama 算法：
public class KetamaHashStrategy implements HashStrategy {private static MessageDigest md5Digest;static {try {md5Digest = MessageDigest.getInstance("MD5");} catch (NoSuchAlgorithmException e) {throw new RuntimeException("MD5 not supported", e);}}@Overridepublic int getHashCode(String origin) {byte[] bKey = computeMd5(origin);long rv = ((long) (bKey[3] & 0xFF) << 24)| ((long) (bKey[2] & 0xFF) << 16)| ((long) (bKey[1] & 0xFF) << 8)| (bKey[0] & 0xFF);return (int) (rv & 0xffffffffL);}/*** Get the md5 of the given key.*/public static byte[] computeMd5(String k) {MessageDigest md5;try {md5 = (MessageDigest) md5Digest.clone();} catch (CloneNotSupportedException e) {throw new RuntimeException("clone of MD5 not supported", e);}md5.update(k.getBytes());return md5.digest();}}MurmurHash 算法：
public class MurmurHashStrategy implements HashStrategy {@Overridepublic int getHashCode(String origin) {ByteBuffer buf = ByteBuffer.wrap(origin.getBytes());int seed = 0x1234ABCD;ByteOrder byteOrder = buf.order();buf.order(ByteOrder.LITTLE_ENDIAN);long m = 0xc6a4a7935bd1e995L;int r = 47;long h = seed ^ (buf.remaining() * m);long k;while (buf.remaining() >= 8) {k = buf.getLong();k *= m;k ^= k >>> r;k *= m;h ^= k;h *= m;}if (buf.remaining() > 0) {ByteBuffer finish = ByteBuffer.allocate(8).order(ByteOrder.LITTLE_ENDIAN);// for big-endian version, do this first:// finish.position(8-buf.remaining());finish.put(buf).rewind();h ^= finish.getLong();h *= m;}h ^= h >>> r;h *= m;h ^= h >>> r;buf.order(byteOrder);return (int) (h & 0xffffffffL);} }測評結果：
| JdkHashCodeStrategy | 29574.08 | 171.97 | 0.6784 |
| CRCHashStrategy | 3013.02 | 54.89 | 0.7604 |
| FnvHashStrategy | 792.02 | 28.14 | 0.7892 |
| KetamaHashStrategy | 1147.08 | 33.86 | 0.80 |
| MurmurHashStrategy | 634.82 | 25.19 | 0.80 |
其中方差和標準差反映了均勻情況，越低越好，可以發(fā)現(xiàn) MurmurHashStrategy，KetamaHashStrategy，FnvHashStrategy 都表現(xiàn)的不錯，其中 MurmurHashStrategy 最為優(yōu)秀。
不變流量比例體現(xiàn)了服務器上下線對原有請求的影響程度，不變流量比例越高越高，可以發(fā)現(xiàn) KetamaHashStrategy 和 MurmurHashStrategy 表現(xiàn)最為優(yōu)秀。
我并沒有對小集群，小流量進行測試，樣本偏差性較大，僅從這個常見場景來看，MurmurHashStrategy 似乎是最優(yōu)的選擇。
至于性能測試，MurmurHash 也十分的高性能，我并沒有做測試（感興趣的同學可以對幾種 strategy 用 JMH 測評一下）,這里我貼一下 MurmurHash 官方的測評數(shù)據(jù)：
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擴大虛擬節(jié)點可以明顯降低方差和標準差，但虛擬節(jié)點的增加會加大內(nèi)存占用量以及計算量
Ketama 一致性哈希算法實現(xiàn)
Ketama 算法有其專門的配套實現(xiàn)方式
public class KetamaConsistentHashLoadBalancer implements LoadBalancer {private static MessageDigest md5Digest;static {try {md5Digest = MessageDigest.getInstance("MD5");} catch (NoSuchAlgorithmException e) {throw new RuntimeException("MD5 not supported", e);}}private final static int VIRTUAL_NODE_SIZE = 12;private final static String VIRTUAL_NODE_SUFFIX = "-";@Overridepublic Server select(List<Server> servers, Invocation invocation) {long invocationHashCode = getHashCode(invocation.getHashKey());TreeMap<Long, Server> ring = buildConsistentHashRing(servers);Server server = locate(ring, invocationHashCode);return server;}private Server locate(TreeMap<Long, Server> ring, Long invocationHashCode) {// 向右找到第一個 keyMap.Entry<Long, Server> locateEntry = ring.ceilingEntry(invocationHashCode);if (locateEntry == null) {// 想象成一個環(huán)，超過尾部則取第一個 keylocateEntry = ring.firstEntry();}return locateEntry.getValue();}private TreeMap<Long, Server> buildConsistentHashRing(List<Server> servers) {TreeMap<Long, Server> virtualNodeRing = new TreeMap<>();for (Server server : servers) {for (int i = 0; i < VIRTUAL_NODE_SIZE / 4; i++) {byte[] digest = computeMd5(server.getUrl() + VIRTUAL_NODE_SUFFIX + i);for (int h = 0; h < 4; h++) {Long k = ((long) (digest[3 + h * 4] & 0xFF) << 24)| ((long) (digest[2 + h * 4] & 0xFF) << 16)| ((long) (digest[1 + h * 4] & 0xFF) << 8)| (digest[h * 4] & 0xFF);virtualNodeRing.put(k, server);}}}return virtualNodeRing;}private long getHashCode(String origin) {byte[] bKey = computeMd5(origin);long rv = ((long) (bKey[3] & 0xFF) << 24)| ((long) (bKey[2] & 0xFF) << 16)| ((long) (bKey[1] & 0xFF) << 8)| (bKey[0] & 0xFF);return rv;}private static byte[] computeMd5(String k) {MessageDigest md5;try {md5 = (MessageDigest) md5Digest.clone();} catch (CloneNotSupportedException e) {throw new RuntimeException("clone of MD5 not supported", e);}md5.update(k.getBytes());return md5.digest();}}稍微不同的地方便在于：Ketama 將四個節(jié)點標為一組進行了虛擬節(jié)點的設置。
| KetamaConsistent HashLoadBalancer | 911.08 | 30.18 | 0.7936 |
實際結果并沒有太大的提升，可能和測試數(shù)據(jù)的樣本規(guī)模有關。
總結
優(yōu)秀的哈希算法和一致性哈希算法可以幫助我們在大多數(shù)場景下應用的高性能，高穩(wěn)定性，但在實際使用一致性哈希負載均衡的場景中，最好針對實際的集群規(guī)模和請求哈希方式進行壓測，力保流量均勻打到所有的機器上，這才是王道。
不僅僅是分布式緩存，負載均衡等等有限的場景，一致性哈希算法、哈希算法，尤其是后者，是一個用處很廣泛的常見算法，了解它的經(jīng)典實現(xiàn)是很有必要的，例如 MurmurHash，在 guava 中就有其 Java 實現(xiàn)，當需要高性能，分布均勻，碰撞概率小的哈希算法時，可以考慮使用它。
總結
以上是生活随笔為你收集整理的一文搞懂负载均衡中的一致性哈希算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 中国学霸本科生提出AI新算法：速度比肩A
- 下一篇： 老大难的分布式锁与幂等性问题，如何解决？