圖解一致性哈希算法
本文轉(zhuǎn)載自微信公眾號(hào)「全棧修仙之路」，作者阿寶哥 。轉(zhuǎn)載本文請(qǐng)聯(lián)系全棧修仙之路公眾號(hào)。
要了解一致性哈希，首先我們必須了解傳統(tǒng)的哈希及其在大規(guī)模分布式系統(tǒng)中的局限性。簡(jiǎn)單地說，哈希就是一個(gè)鍵值對(duì)存儲(chǔ)，在給定鍵的情況下，可以非常高效地找到所關(guān)聯(lián)的值。假設(shè)我們要根據(jù)其郵政編碼查找城市中的街道名稱。一種最簡(jiǎn)單的實(shí)現(xiàn)方式是將此信息以哈希字典的形式進(jìn)行存儲(chǔ)
當(dāng)數(shù)據(jù)太大而無法存儲(chǔ)在一個(gè)節(jié)點(diǎn)或機(jī)器上時(shí)，問題變得更加有趣，系統(tǒng)中需要多個(gè)這樣的節(jié)點(diǎn)或機(jī)器來存儲(chǔ)它。比如，使用多個(gè) Web 緩存中間件的系統(tǒng)。那如何確定哪個(gè) key 存儲(chǔ)在哪個(gè)節(jié)點(diǎn)上?針對(duì)該問題，最簡(jiǎn)單的解決方案是使用哈希取模來確定。 給定一個(gè) key，先對(duì) key 進(jìn)行哈希運(yùn)算，將其除以系統(tǒng)中的節(jié)點(diǎn)數(shù)，然后將該 key 放入該節(jié)點(diǎn)。同樣，在獲取 key 時(shí)，對(duì) key 進(jìn)行哈希運(yùn)算，再除以節(jié)點(diǎn)數(shù)，然后轉(zhuǎn)到該節(jié)點(diǎn)并獲取值。上述過程對(duì)應(yīng)的哈希算法定義如下：
- node_number = hash(key) % N # 其中 N 為節(jié)點(diǎn)數(shù)。
下圖描繪了多節(jié)點(diǎn)系統(tǒng)中的傳統(tǒng)的哈希取模算法，基于該算法可以實(shí)現(xiàn)簡(jiǎn)單的負(fù)載均衡。
一、傳統(tǒng)哈希取模算法的局限性
下面我們來分析一下傳統(tǒng)的哈希及其在大規(guī)模分布式系統(tǒng)中的局限性。這里我們直接使用我之前所寫文章 布隆過濾器你值得擁有的開發(fā)利器 中定義的 SimpleHash 類，然后分別對(duì) semlinker、kakuqo 和 test 3 個(gè)鍵進(jìn)行哈希運(yùn)算并取余，具體代碼如下：
- public class SimpleHash {
- private int cap;
- private int seed;
- public SimpleHash(int cap, int seed) {
- this.cap = cap;
- this.seed = seed;
- }
- public int hash(String value) {
- int result = 0;
- int len = value.length();
- for (int i = 0; i < len; i++) {
- result = seed * result + value.charAt(i);
- }
- return (cap - 1) & result;
- }
- public static void main(String[] args) {
- SimpleHash simpleHash = new SimpleHash(2 << 12, 8);
- System.out.println("node_number=hash(\"semlinker\") % 3 -> " +
- simpleHash.hash("semlinker") % 3);
- System.out.println("node_number=hash(\"kakuqo\") % 3 -> " +
- simpleHash.hash("kakuqo") % 3);
- System.out.println("node_number=hash(\"test\") % 3 -> " +
- simpleHash.hash("test") % 3);
- }
- }
以上代碼成功運(yùn)行后，在控制臺(tái)會(huì)輸出以下結(jié)果：
- node_number=hash("semlinker") % 3 -> 1
- node_number=hash("kakuqo") % 3 -> 2
- node_number=hash("test") % 3 -> 0
基于以上的輸出結(jié)果，我們可以創(chuàng)建以下表格：
1.1 節(jié)點(diǎn)減少的場(chǎng)景
在分布式多節(jié)點(diǎn)系統(tǒng)中，出現(xiàn)故障很常見。任何節(jié)點(diǎn)都可能在沒有任何事先通知的情況下掛掉，針對(duì)這種情況我們期望系統(tǒng)只是出現(xiàn)性能降低，正常的功能不會(huì)受到影響。 對(duì)于原始示例，當(dāng)節(jié)點(diǎn)出現(xiàn)故障時(shí)會(huì)發(fā)生什么?原始示例中有的 3 個(gè)節(jié)點(diǎn)，假設(shè)其中 1 個(gè)節(jié)點(diǎn)出現(xiàn)故障，這時(shí)節(jié)點(diǎn)數(shù)發(fā)生了變化，節(jié)點(diǎn)個(gè)數(shù)從 3 減少為 2，此時(shí)表格的狀態(tài)發(fā)生了變化：
很明顯節(jié)點(diǎn)的減少會(huì)導(dǎo)致鍵與節(jié)點(diǎn)的映射關(guān)系發(fā)生變化，這個(gè)變化對(duì)于新的鍵來說并不會(huì)產(chǎn)生任何影響，但對(duì)于已有的鍵來說，將導(dǎo)致節(jié)點(diǎn)映射錯(cuò)誤，以 “semlinker” 為例，變化前系統(tǒng)有 3 個(gè)節(jié)點(diǎn)，該鍵對(duì)應(yīng)的節(jié)點(diǎn)編號(hào)為 1，當(dāng)出現(xiàn)故障時(shí)，節(jié)點(diǎn)數(shù)減少為 2 個(gè)，此時(shí)該鍵對(duì)應(yīng)的節(jié)點(diǎn)編號(hào)為 0。
1.2 節(jié)點(diǎn)增加的場(chǎng)景
在分布式多節(jié)點(diǎn)系統(tǒng)中，對(duì)于某些場(chǎng)景比如節(jié)日大促，就需要對(duì)服務(wù)節(jié)點(diǎn)進(jìn)行擴(kuò)容，以應(yīng)對(duì)突發(fā)的流量。 對(duì)于原始示例，當(dāng)增加節(jié)點(diǎn)會(huì)發(fā)生什么?原始示例中有的 3 個(gè)節(jié)點(diǎn)，假設(shè)進(jìn)行擴(kuò)容臨時(shí)增加了 1 個(gè)節(jié)點(diǎn)，這時(shí)節(jié)點(diǎn)數(shù)發(fā)生了變化，節(jié)點(diǎn)個(gè)數(shù)從 3 增加為 4 個(gè)，此時(shí)表格的狀態(tài)發(fā)生了變化：
很明顯節(jié)點(diǎn)的增加也會(huì)導(dǎo)致鍵與節(jié)點(diǎn)的映射關(guān)系發(fā)生變化，這個(gè)變化對(duì)于新的鍵來說并不會(huì)產(chǎn)生任何影響，但對(duì)于已有的鍵來說，將導(dǎo)致節(jié)點(diǎn)映射錯(cuò)誤，同樣以 “semlinker” 為例，變化前系統(tǒng)有 3 個(gè)節(jié)點(diǎn)，該鍵對(duì)應(yīng)的節(jié)點(diǎn)編號(hào)為 1，當(dāng)增加節(jié)點(diǎn)時(shí)，節(jié)點(diǎn)數(shù)增加為 4 個(gè)，此時(shí)該鍵對(duì)應(yīng)的節(jié)點(diǎn)編號(hào)為 2。
當(dāng)集群中節(jié)點(diǎn)的數(shù)量發(fā)生變化時(shí)，之前的映射規(guī)則就可能發(fā)生變化。如果集群中每個(gè)機(jī)器提供的服務(wù)沒有差別，這不會(huì)有什么影響。但對(duì)于分布式緩存這種的系統(tǒng)而言，映射規(guī)則失效就意味著之前緩存的失效，若同一時(shí)刻出現(xiàn)大量的緩存失效，則可能會(huì)出現(xiàn) “緩存雪崩”，這將會(huì)造成災(zāi)難性的后果。
要解決此問題，我們必須在其余節(jié)點(diǎn)上重新分配所有現(xiàn)有鍵，這可能是非常昂貴的操作，并且可能對(duì)正在運(yùn)行的系統(tǒng)產(chǎn)生不利影響。當(dāng)然除了重新分配所有現(xiàn)有鍵的方案之外，還有另一種更好的方案即使用一致性哈希算法。
二、一致性哈希算法
一致性哈希算法在 1997 年由麻省理工學(xué)院提出，是一種特殊的哈希算法，在移除或者添加一個(gè)服務(wù)器時(shí)，能夠盡可能小地改變已存在的服務(wù)請(qǐng)求與處理請(qǐng)求服務(wù)器之間的映射關(guān)系。一致性哈希解決了簡(jiǎn)單哈希算法在分布式哈希表(Distributed Hash Table，DHT)中存在的動(dòng)態(tài)伸縮等問題 。
2.1 一致性哈希算法優(yōu)點(diǎn)
- 可擴(kuò)展性。一致性哈希算法保證了增加或減少服務(wù)器時(shí)，數(shù)據(jù)存儲(chǔ)的改變最少，相比傳統(tǒng)哈希算法大大節(jié)省了數(shù)據(jù)移動(dòng)的開銷 。
- 更好地適應(yīng)數(shù)據(jù)的快速增長(zhǎng)。采用一致性哈希算法分布數(shù)據(jù)，當(dāng)數(shù)據(jù)不斷增長(zhǎng)時(shí)，部分虛擬節(jié)點(diǎn)中可能包含很多數(shù)據(jù)、造成數(shù)據(jù)在虛擬節(jié)點(diǎn)上分布不均衡，此時(shí)可以將包含數(shù)據(jù)多的虛擬節(jié)點(diǎn)分裂，這種分裂僅僅是將原有的虛擬節(jié)點(diǎn)一分為二、不需要對(duì)全部的數(shù)據(jù)進(jìn)行重新哈希和劃分。
虛擬節(jié)點(diǎn)分裂后，如果物理服務(wù)器的負(fù)載仍然不均衡，只需在服務(wù)器之間調(diào)整部分虛擬節(jié)點(diǎn)的存儲(chǔ)分布。這樣可以隨數(shù)據(jù)的增長(zhǎng)而動(dòng)態(tài)的擴(kuò)展物理服務(wù)器的數(shù)量，且代價(jià)遠(yuǎn)比傳統(tǒng)哈希算法重新分布所有數(shù)據(jù)要小很多。
2.2 一致性哈希算法與哈希算法的關(guān)系
一致性哈希算法是在哈希算法基礎(chǔ)上提出的，在動(dòng)態(tài)變化的分布式環(huán)境中，哈希算法應(yīng)該滿足的幾個(gè)條件：平衡性、單調(diào)性和分散性。
- 平衡性：是指 hash 的結(jié)果應(yīng)該平均分配到各個(gè)節(jié)點(diǎn)，這樣從算法上解決了負(fù)載均衡問題。
- 單調(diào)性：是指在新增或者刪減節(jié)點(diǎn)時(shí)，不影響系統(tǒng)正常運(yùn)行。
- 分散性：是指數(shù)據(jù)應(yīng)該分散地存放在分布式集群中的各個(gè)節(jié)點(diǎn)(節(jié)點(diǎn)自己可以有備份)，不必每個(gè)節(jié)點(diǎn)都存儲(chǔ)所有的數(shù)據(jù)。
三、一致性哈希算法原理
一致性哈希算法通過一個(gè)叫作一致性哈希環(huán)的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)。這個(gè)環(huán)的起點(diǎn)是 0，終點(diǎn)是 2^32 - 1，并且起點(diǎn)與終點(diǎn)連接，故這個(gè)環(huán)的整數(shù)分布范圍是 [0, 2^32-1]，如下圖所示：
3.1 將對(duì)象放置到哈希環(huán)
假設(shè)我們有 "semlinker"、"kakuqo"、"lolo"、"fer" 四個(gè)對(duì)象，分別簡(jiǎn)寫為 o1、o2、o3 和 o4，然后使用哈希函數(shù)計(jì)算這個(gè)對(duì)象的 hash 值，值的范圍是 [0, 2^32-1]：
圖中對(duì)象的映射關(guān)系如下：
- hash(o1) = k1; hash(o2) = k2;
- hash(o3) = k3; hash(o4) = k4;
3.2 將服務(wù)器放置到哈希環(huán)
接著使用同樣的哈希函數(shù)，我們將服務(wù)器也放置到哈希環(huán)上，可以選擇服務(wù)器的 IP 或主機(jī)名作為鍵進(jìn)行哈希，這樣每臺(tái)服務(wù)器就能確定其在哈希環(huán)上的位置。這里假設(shè)我們有 3 臺(tái)緩存服務(wù)器，分別為 cs1、cs2 和 cs3：
圖中服務(wù)器的映射關(guān)系如下：
- hash(cs1) = t1; hash(cs2) = t2; hash(cs3) = t3; # Cache Server
3.3 為對(duì)象選擇服務(wù)器
將對(duì)象和服務(wù)器都放置到同一個(gè)哈希環(huán)后，在哈希環(huán)上順時(shí)針查找距離這個(gè)對(duì)象的 hash 值最近的機(jī)器，即是這個(gè)對(duì)象所屬的機(jī)器。 以 o2 對(duì)象為例，順序針找到最近的機(jī)器是 cs2，故服務(wù)器 cs2 會(huì)緩存 o2 對(duì)象。而服務(wù)器 cs1 則緩存 o1，o3 對(duì)象，服務(wù)器 cs3 則緩存 o4 對(duì)象。
3.4 服務(wù)器增加的情況
假設(shè)由于業(yè)務(wù)需要，我們需要增加一臺(tái)服務(wù)器 cs4，經(jīng)過同樣的 hash 運(yùn)算，該服務(wù)器最終落于 t1 和 t2 服務(wù)器之間，具體如下圖所示：
圖片
對(duì)于上述的情況，只有 t1 和 t2 服務(wù)器之間的對(duì)象需要重新分配。在以上示例中只有 o3 對(duì)象需要重新分配，即它被重新到 cs4 服務(wù)器。在前面我們已經(jīng)分析過，如果使用簡(jiǎn)單的取模方法，當(dāng)新添加服務(wù)器時(shí)可能會(huì)導(dǎo)致大部分緩存失效，而使用一致性哈希算法后，這種情況得到了較大的改善，因?yàn)橹挥猩俨糠謱?duì)象需要重新分配。
3.5 服務(wù)器減少的情況
假設(shè) cs3 服務(wù)器出現(xiàn)故障導(dǎo)致服務(wù)下線，這時(shí)原本存儲(chǔ)于 cs3 服務(wù)器的對(duì)象 o4，需要被重新分配至 cs2 服務(wù)器，其它對(duì)象仍存儲(chǔ)在原有的機(jī)器上。
3.6 虛擬節(jié)點(diǎn)
到這里一致性哈希的基本原理已經(jīng)介紹完了，但對(duì)于新增服務(wù)器的情況還存在一些問題。新增的服務(wù)器 cs4 只分擔(dān)了 cs1 服務(wù)器的負(fù)載，服務(wù)器 cs2 和 cs3 并沒有因?yàn)?cs4 服務(wù)器的加入而減少負(fù)載壓力。如果 cs4 服務(wù)器的性能與原有服務(wù)器的性能一致甚至可能更高，那么這種結(jié)果并不是我們所期望的。
針對(duì)這個(gè)問題，我們可以通過引入虛擬節(jié)點(diǎn)來解決負(fù)載不均衡的問題。即將每臺(tái)物理服務(wù)器虛擬為一組虛擬服務(wù)器，將虛擬服務(wù)器放置到哈希環(huán)上，如果要確定對(duì)象的服務(wù)器，需先確定對(duì)象的虛擬服務(wù)器，再由虛擬服務(wù)器確定物理服務(wù)器。
圖中 o1 和 o2 表示對(duì)象，v1 ~ v6 表示虛擬服務(wù)器，s1 ~ s3 表示物理服務(wù)器。
四、一致性哈希算法實(shí)現(xiàn)
這里我們只介紹不帶虛擬節(jié)點(diǎn)的一致性哈希算法實(shí)現(xiàn)：
- import java.util.SortedMap;
- import java.util.TreeMap;
- public class ConsistentHashingWithoutVirtualNode {
- //待添加入Hash環(huán)的服務(wù)器列表
- private static String[] servers = {"192.168.0.1:8888", "192.168.0.2:8888",
- "192.168.0.3:8888"};
- //key表示服務(wù)器的hash值，value表示服務(wù)器
- private static SortedMap<Integer, String> sortedMap = new TreeMap<Integer, String>();
- //程序初始化，將所有的服務(wù)器放入sortedMap中
- static {
- for (int i = 0; i < servers.length; i++) {
- int hash = getHash(servers[i]);
- System.out.println("[" + servers[i] + "]加入集合中, 其Hash值為" + hash);
- sortedMap.put(hash, servers[i]);
- }
- }
- //得到應(yīng)當(dāng)路由到的結(jié)點(diǎn)
- private static String getServer(String key) {
- //得到該key的hash值
- int hash = getHash(key);
- //得到大于該Hash值的所有Map
- SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);
- if (subMap.isEmpty()) {
- //如果沒有比該key的hash值大的，則從第一個(gè)node開始
- Integer i = sortedMap.firstKey();
- //返回對(duì)應(yīng)的服務(wù)器
- return sortedMap.get(i);
- } else {
- //第一個(gè)Key就是順時(shí)針過去離node最近的那個(gè)結(jié)點(diǎn)
- Integer i = subMap.firstKey();
- //返回對(duì)應(yīng)的服務(wù)器
- return subMap.get(i);
- }
- }
- //使用FNV1_32_HASH算法計(jì)算服務(wù)器的Hash值
- private static int getHash(String str) {
- final int p = 16777619;
- int hash = (int) 2166136261L;
- for (int i = 0; i < str.length(); i++)
- hash = (hash ^ str.charAt(i)) * p;
- hash += hash << 13;
- hash ^= hash >> 7;
- hash += hash << 3;
- hash ^= hash >> 17;
- hash += hash << 5;
- // 如果算出來的值為負(fù)數(shù)則取其絕對(duì)值
- if (hash < 0)
- hash = Math.abs(hash);
- return hash;
- }
- public static void main(String[] args) {
- String[] keys = {"semlinker", "kakuqo", "fer"};
- for (int i = 0; i < keys.length; i++)
- System.out.println("[" + keys[i] + "]的hash值為" + getHash(keys[i])
- + ", 被路由到結(jié)點(diǎn)[" + getServer(keys[i]) + "]");
- }
- }
以上代碼成功運(yùn)行后，在控制臺(tái)會(huì)輸出以下結(jié)果：
- [192.168.0.1:8888]加入集合中, 其Hash值為1326271016
- [192.168.0.2:8888]加入集合中, 其Hash值為1132535844
- [192.168.0.3:8888]加入集合中, 其Hash值為115798597
- [semlinker]的hash值為1549041406, 被路由到結(jié)點(diǎn)[192.168.0.3:8888]
- [kakuqo]的hash值為463104755, 被路由到結(jié)點(diǎn)[192.168.0.2:8888]
- [fer]的hash值為1677150790, 被路由到結(jié)點(diǎn)[192.168.0.3:8888]
上面我們只介紹了不帶虛擬節(jié)點(diǎn)的一致性哈希算法實(shí)現(xiàn)，如果有的小伙伴對(duì)帶虛擬節(jié)點(diǎn)的一致性哈希算法感興趣，可以參考 一致性Hash(Consistent Hashing)原理剖析及Java實(shí)現(xiàn) 這篇文章。
五、總結(jié)
本文通過示例介紹了傳統(tǒng)的哈希取模算法在分布式系統(tǒng)中的局限性，進(jìn)而在針對(duì)該問題的解決方案中引出了一致性哈希算法。一致性哈希算法在 1997 年由麻省理工學(xué)院提出，是一種特殊的哈希算法，在移除或者添加一個(gè)服務(wù)器時(shí)，能夠盡可能小地改變已存在的服務(wù)請(qǐng)求與處理請(qǐng)求服務(wù)器之間的映射關(guān)系。在介紹完一致性哈希算法的作用和優(yōu)點(diǎn)等相關(guān)知識(shí)后，我們以圖解的形式生動(dòng)介紹了一致性哈希算法的原理，最后給出了不帶虛擬節(jié)點(diǎn)的一致性哈希算法的 Java 實(shí)現(xiàn)。
六、參考資源
百度百科 - 一致性哈希
知乎 - 面試必備：什么是一致性 Hash 算法
Leo - 一致性Hash-Consistent-Hashing 原理剖析
CSDN - 一致性Hash(Consistent Hashing)原理剖析及Java實(shí)現(xiàn)
Codeproject - consistent-hashing
