為了提升數(shù)據(jù)的讀寫速度，我們一般會引入緩存，如果數(shù)據(jù)量很大，一個節(jié)點的緩存容納不下，那么就會采用多節(jié)點，也就是分布式緩存。具體做法是在節(jié)點前面加一個 Proxy 層，由 Proxy 層統(tǒng)一接收來自客戶端的讀寫請求，然后將請求轉(zhuǎn)發(fā)給某個節(jié)點。

但這就產(chǎn)生了一個問題，既然有多個節(jié)點（比如上圖有 A、B、C 三個節(jié)點，每個節(jié)點存放不同的 KV 數(shù)據(jù)），那么寫數(shù)據(jù)的時候應(yīng)該寫到哪一個節(jié)點呢？讀數(shù)據(jù)，又應(yīng)該從哪一個節(jié)點去讀呢？

維度考量

對于任何一個分布式存儲系統(tǒng)，在存儲數(shù)據(jù)時，我們通常都會從數(shù)據(jù)均勻、數(shù)據(jù)穩(wěn)定和節(jié)點異構(gòu)性這三個維度來考量。

數(shù)據(jù)均勻

不同節(jié)點中存儲的數(shù)據(jù)要盡量均勻，不能因數(shù)據(jù)傾斜導(dǎo)致某些節(jié)點存儲壓力過大，而其它節(jié)點卻幾乎沒什么數(shù)據(jù)。比如有 4 個相同配置的節(jié)點要存儲 100G 的數(shù)據(jù)，那么理想狀態(tài)就是讓每個節(jié)點存儲 25G 的數(shù)據(jù)。

此外用戶訪問也要做到均勻，避免出現(xiàn)某些節(jié)點的訪問量很大，但其它節(jié)點卻無人問津的情況。比如要處理 1000 個請求，理想狀態(tài)就是讓每個節(jié)點處理 250 個請求。

當(dāng)然這是非常理想的情況，實際情況下，只要每個節(jié)點之間相差不太大即可。

數(shù)據(jù)穩(wěn)定

當(dāng)存儲節(jié)點出現(xiàn)故障需要移除、或者需要新增節(jié)點時，數(shù)據(jù)按照分布規(guī)則得到的結(jié)果應(yīng)該盡量保持穩(wěn)定，不要出現(xiàn)大范圍的數(shù)據(jù)遷移。

比如 4 個節(jié)點存儲 100G 數(shù)據(jù)，但現(xiàn)在其中一個節(jié)點掛掉了，那么只需要將掛掉的節(jié)點存儲的數(shù)據(jù)遷移到其它正常節(jié)點即可，而不需要大范圍對所有數(shù)據(jù)進(jìn)行遷移。當(dāng)然新增節(jié)點也是同理，要在盡可能小的范圍內(nèi)將數(shù)據(jù)遷移到擴(kuò)展的節(jié)點上。

節(jié)點異構(gòu)性

不同存儲節(jié)點的硬件配置可能差別很大，配置高的節(jié)點能存儲的數(shù)據(jù)量、單位時間處理的請求數(shù)，本身就高于配置低的節(jié)點。

如果這種硬件配置差別很大的節(jié)點，存儲的數(shù)據(jù)量、處理的請求數(shù)都差不多，那么反倒不均勻了。所以，一個好的數(shù)據(jù)分布算法應(yīng)該考慮節(jié)點異構(gòu)性。

當(dāng)然，除了上面這 3 個維度外，我們一般還會考慮隔離故障域、性能穩(wěn)定性等因素。

隔離故障域

用于保證數(shù)據(jù)的可用性和可靠性，比如我們通常通過備份來實現(xiàn)數(shù)據(jù)的可靠性。但如果每個數(shù)據(jù)及它的備份，被分布到了同一塊硬盤或節(jié)點上，就有點違背備份的初衷了。

所以一個好的數(shù)據(jù)分布算法，給每個數(shù)據(jù)映射的存儲節(jié)點應(yīng)該盡量在不同的故障域，比如不同機(jī)房、不同機(jī)架等。

性能穩(wěn)定性

數(shù)據(jù)存儲和查詢的效率要有保證，不能因為節(jié)點的添加或者移除，造成讀寫性能的嚴(yán)重下降。

了解完數(shù)據(jù)分布的設(shè)計原則后，再來看看主流的數(shù)據(jù)分布式方法，也就是哈希算法，以及基于哈希算法演進(jìn)出的一些算法。

哈希

通過對 key 進(jìn)行哈希，然后再用哈希值對節(jié)點個數(shù)取模，即可尋址到對應(yīng)的服務(wù)器。

比如查詢名為 key-01 的 key，計算公式是 hash("key-01") % 3 ，經(jīng)過計算尋址到了編號為 0 的服務(wù)器節(jié)點 A，如下圖所示。

不難發(fā)現(xiàn)，哈希算法非常簡單直觀，如果選擇一個好的哈希函數(shù)，是可以讓數(shù)據(jù)均勻分布的。但哈希算法有一個致命的缺點，就是它無法滿足節(jié)點動態(tài)變化。比如節(jié)點數(shù)量發(fā)生變化，基于新的節(jié)點數(shù)量來執(zhí)行哈希算法的時候，就會出現(xiàn)路由尋址失敗的情況，Proxy 無法尋址到之前的服務(wù)器節(jié)點。

想象一下，假如 3 個節(jié)點不能滿足業(yè)務(wù)需要了，我們增加了一個節(jié)點，節(jié)點的數(shù)量從 3 變成 4。那么之前的 hash("key-01") % 3 = 0，就變成了 hash("key-01") % 4 = X。

因為取模運算發(fā)生了變化，所以這個 X 大概率不是 0（假設(shè) X 為 1），這時再查詢，就會找不到數(shù)據(jù)了。因為 key-01 對應(yīng)的數(shù)據(jù)，存儲在節(jié)點 A 上，而不是節(jié)點 B。

同樣的道理，如果我們需要下線 1 個服務(wù)器節(jié)點，也會存在類似的可能查詢不到數(shù)據(jù)的問題。

而解決這個問題的辦法在于我們要遷移數(shù)據(jù)，基于新的計算公式 hash("key-01") % 4，來重新對數(shù)據(jù)和節(jié)點做映射。但需要注意的是，數(shù)據(jù)的遷移成本是非常高的，對于 3 節(jié)點 KV 存儲，如果我們增加 1 個節(jié)點，變?yōu)?4 節(jié)點集群，則需要遷移 75% 的數(shù)據(jù)。

所以哈希算法適用于節(jié)點配置相同，并且節(jié)點數(shù)量固定的場景。如果節(jié)點會動態(tài)變化，那么應(yīng)該選擇一致性哈希算法。

一致性哈希

一致性哈希也是基于哈希實現(xiàn)的，哈希算法是對節(jié)點的數(shù)量進(jìn)行取模運算，而一致性哈希算法是對 2^32 進(jìn)行取模運算。想象一下，一致性哈希算法將整個哈希值空間組織成一個虛擬的圓環(huán)，也就是哈希環(huán)：

哈希環(huán)的空間按順時針方向組織，圓環(huán)的正上方的點代表 0，0 右側(cè)的第一個點代表 1，以此類推，2、3、4、5、6……直到 2^32-1。

在一致性哈希中，你可以通過執(zhí)行哈希算法，將節(jié)點映射到哈希環(huán)上。比如選擇節(jié)點的主機(jī)名作為參數(shù)執(zhí)行哈希再取模，那么就能確定每個節(jié)點在哈希環(huán)上的位置了。

當(dāng)需要對指定 key 的值進(jìn)行讀寫的時候，可以通過下面兩步進(jìn)行尋址：

• 首先，對 key 進(jìn)行哈希再取模，并確定此 key 在環(huán)上的位置。
• 然后，從該位置沿著哈希環(huán)順時針行走，遇到的第一個節(jié)點就是 key 對應(yīng)的節(jié)點。

我們舉個例子，假設(shè) key-01、key-02、key-03 三個 key，經(jīng)過哈希取模后，在哈希環(huán)中的位置如下：

根據(jù)一致性哈希算法，key-01 尋址到節(jié)點 B，key-02 尋址到節(jié)點 A，key-03 尋址到節(jié)點 C。如果只考慮數(shù)據(jù)分布的話，那么一致性哈希算法和哈希算法差別不太大，但一致性哈希解決了節(jié)點變化帶來的數(shù)據(jù)遷移問題。

假設(shè)，現(xiàn)在有一個節(jié)點故障了（比如節(jié)點 C）：

可以看到，key-01 和 key-02 不會受到影響，只有 key-03 的尋址被重定位到 A。一般來說，在一致性哈希算法中，如果某個節(jié)點宕機(jī)不可用了，那么受影響的數(shù)據(jù)僅僅是故障節(jié)點和前一節(jié)點之間的數(shù)據(jù)。

比如當(dāng)節(jié)點 C 宕機(jī)了，受影響的數(shù)據(jù)是節(jié)點 B 和節(jié)點 C 之間的數(shù)據(jù)（例如 key-03），尋址到其它哈希環(huán)空間的數(shù)據(jù)（例如 key-01），不會受到影響。

如果此時集群不能滿足業(yè)務(wù)的需求，需要擴(kuò)容一個節(jié)點 D 呢？

可以看到 key-01、key-02 不受影響，只有 key-03 的尋址被重定位到新節(jié)點 D。一般而言，在一致性哈希算法中，如果增加一個節(jié)點，受影響的數(shù)據(jù)僅僅是新節(jié)點和前一節(jié)點之間的數(shù)據(jù)，其它數(shù)據(jù)也不會受到影響。

使用一致性哈希的話，對于 3 節(jié)點 KV 存儲，如果我們增加 1 個節(jié)點，變?yōu)?4 節(jié)點集群，則只需要遷移 24.3% 的數(shù)據(jù)。遷移的數(shù)據(jù)量僅為使用哈希算法時的三分之一，從而大大提升效率。

總的來說，使用了一致性哈希算法后，擴(kuò)容或縮容的時候，都只需要重定位環(huán)空間中的一小部分?jǐn)?shù)據(jù)。所以一致性哈希算法是對哈希算法的改進(jìn)，在采用哈希方式確定數(shù)據(jù)存儲位置的基礎(chǔ)上，又增加了一層哈希，也就是在數(shù)據(jù)存儲前先對存儲節(jié)點進(jìn)行哈希，具有較好的容錯性和可擴(kuò)展性。

一致性哈希比較適合節(jié)點配置相同、但規(guī)模會發(fā)生變化的場景。

我們用 Python 簡單實現(xiàn)一下一致性哈希：

from typing import Union, List
import hashlib
import bisect

class ConsistentHash:

    def __init__(self,
                 nodes: List[str] = None,
                 ring_max_len=2 ** 32):
        # 哈希環(huán)的最大長度
        self.ring_max_len = ring_max_len
        # 節(jié)點在哈希環(huán)上的索引（有序）
        self.node_indexes = []
        # '節(jié)點在哈希環(huán)上的索引' 到 '節(jié)點' 的映射
        self.nodes_mapping = {}

        if nodes:
            for node in nodes:
                self.add_node(node)

    def get_index(self, item: Union[str, bytes]):
        """
        獲取節(jié)點或者 key 在哈希環(huán)上的索引
        """
        if type(item) is str:
            item = item.encode("utf-8")
        md5 = hashlib.md5()
        md5.update(item)
        # md5.hexdigest() 會返回 16 進(jìn)制字符串，將其轉(zhuǎn)成整數(shù)
        # 然后是取模，如果 n 是 2 的冪次方，那么 m % n 等價于 m & (n - 1)
        # 所以字典的容量一般都是 2 的冪次方，就是為了將取模優(yōu)化成按位與
        return int(md5.hexdigest(), 16) & (self.ring_max_len - 1)

    def add_node(self, node):
        """
        node 可以是節(jié)點的信息，比如一個字典
        但這里為了方便，node 就表示節(jié)點名稱
        """
        node_index = self.get_index(node)
        # 節(jié)點索引是有序的，新增時使用 bisect 可將復(fù)雜度優(yōu)化為 logN
        bisect.insort(self.node_indexes, node_index)
        self.nodes_mapping[node_index] = node
        print(f"節(jié)點 {node} 被添加至哈希環(huán), 索引為 {node_index}")

    def remove_node(self, node):
        # 移除節(jié)點
        node_index = self.get_index(node)
        self.node_indexes.remove(node_index)
        self.nodes_mapping.pop(node_index)
        print(f"節(jié)點 {node} 從哈希環(huán)中被移除")

    def get_node(self, key):
        """
        判斷 key 應(yīng)該被存在哪一個 node 中
        """
        key_index = self.get_index(key)
        # node_indexes 里面存儲了所有節(jié)點在哈希環(huán)的索引
        # 所以只需要遍歷即可
        for node_index in self.node_indexes:
            if node_index >= key_index:
                break
        else:
            node_index = self.node_indexes[0]
        # 如果節(jié)點索引大于等于 key 的索引，那么就找到了指定節(jié)點
        # 如果遍歷結(jié)束還沒有找到，說明 key 的索引大于最后一個節(jié)點的索引
        # 這樣的話，該 key 應(yīng)該存在第一個節(jié)點

        node = self.nodes_mapping[node_index]
        # todo：連接指定節(jié)點，存儲 key 和 value
        print(f"key `{key}` 存在了節(jié)點 `{node}` 上")


ch = ConsistentHash(nodes=["node1", "node2", "node3"])
"""
節(jié)點 node1 被添加至哈希環(huán), 索引為 2595155078
節(jié)點 node2 被添加至哈希環(huán), 索引為 3803043663
節(jié)點 node3 被添加至哈希環(huán), 索引為 385180855
"""
ch.get_node("S 老師四點下班")
ch.get_node("高老師總能分享出好東西")
ch.get_node("電烤??架")
"""
key `S 老師四點下班` 存在了節(jié)點 `node3` 上
key `高老師總能分享出好東西` 存在了節(jié)點 `node1` 上
key `電烤??架` 存在了節(jié)點 `node1` 上
"""

# 刪除節(jié)點
ch.remove_node("node3")
"""
節(jié)點 node3 從哈希環(huán)中被移除
"""
# 當(dāng)節(jié)點被刪除后，存儲位置發(fā)生變化
ch.get_node("S 老師四點下班")
"""
key `S 老師四點下班` 存在了節(jié)點 `node1` 上
"""

當(dāng)然啦，在節(jié)點被移除時，應(yīng)該自動進(jìn)行數(shù)據(jù)遷移。這里就不實現(xiàn)了，有興趣的話可以嘗試一下。

然后一致性哈希也有它的一些問題，比如讀寫可能集中在少數(shù)的節(jié)點上，導(dǎo)致有些節(jié)點高負(fù)載，有些節(jié)點低負(fù)載的情況。

從圖中可以看到，雖然有 3 個節(jié)點，但訪問請求主要集中在節(jié)點 A 上。當(dāng)然這個問題其實不大，我們可以設(shè)計一個好的哈希函數(shù)，讓節(jié)點均勻分布。

但一致性哈希還存在擊垮后繼節(jié)點的風(fēng)險，如果某個節(jié)點退出，那么該節(jié)點的后繼節(jié)點需要承擔(dān)該節(jié)點的所有負(fù)載。如果后繼節(jié)點承受不住，那么也可能出現(xiàn)故障，從而導(dǎo)致后繼節(jié)點的后繼節(jié)點也面臨同樣的問題，引發(fā)惡性循環(huán)。

那么如何解決后繼節(jié)點可能被壓垮的問題呢？針對這個問題，Google 提出了帶有限負(fù)載的一致性哈希算法。

帶有限負(fù)載的一致性哈希

帶有限負(fù)載的一致性哈希的核心原理是，給每個存儲節(jié)點設(shè)置一個存儲上限值，來控制存儲節(jié)點添加或移除造成的數(shù)據(jù)不均勻。

當(dāng)數(shù)據(jù)按照一致性哈希算法找到相應(yīng)的節(jié)點時，要先判斷該節(jié)點是否達(dá)到了存儲上限。如果已經(jīng)達(dá)到了上限，則需要繼續(xù)尋找該節(jié)點順時針方向之后的節(jié)點進(jìn)行存儲。

所以該算法相當(dāng)于在一致性哈希的基礎(chǔ)上，給節(jié)點增加了一些存儲上限，它的適用場景和一致性哈希是一樣的。目前在 Google、Vimeo 等公司的負(fù)載均衡項目中得到應(yīng)用。

當(dāng)然啦，無論是哈希、一致性哈希，還是帶有限負(fù)載的一致性哈希，它們的適用場景都要求節(jié)點的配置相同，換句話說就是沒有考慮節(jié)點異構(gòu)性的問題。如果存儲節(jié)點的硬件配置不同，那么采用上面算法實現(xiàn)的數(shù)據(jù)均勻分布，反倒變得不均勻了。

所以便引入了虛擬節(jié)點。

帶虛擬節(jié)點的一致性哈希

帶虛擬節(jié)點的一致性哈希，核心思想是根據(jù)每個節(jié)點的性能，為每個節(jié)點劃分不同數(shù)量的虛擬節(jié)點，并將這些虛擬節(jié)點映射到哈希環(huán)中，然后再按照一致性哈希算法進(jìn)行數(shù)據(jù)映射和存儲。

比如三個節(jié)點 A、B、C，以節(jié)點 C 為基準(zhǔn)，節(jié)點 B 的性能是它的 2 倍，節(jié)點 A 是它的 3 倍。因此要給節(jié)點 C 添加 1 個虛擬節(jié)點，給節(jié)點 B 添加 2 個虛擬節(jié)點，給節(jié)點 A 添加 3 個虛擬節(jié)點。

節(jié)點 A 的虛擬節(jié)點是 A1、A2、A3，節(jié)點 B 的虛擬機(jī)節(jié)點是 B1、B2，節(jié)點 C 的虛擬節(jié)點是 C1。當(dāng)然虛擬節(jié)點的數(shù)量不一定是 1、2、3，也可以按照比例進(jìn)行增加。

總之通過增加虛擬節(jié)點，可以考慮到節(jié)點異構(gòu)性，讓性能高的節(jié)點多分配一些請求。

如果節(jié)點配置一樣，也可以使用該算法，只不過此時每個節(jié)點對應(yīng)的虛擬節(jié)點是一樣的。并且采用這種方式，可以有效避免節(jié)點傾斜的問題，不會出現(xiàn)大部分請求都打在同一節(jié)點的情況。

可以看出，帶虛擬節(jié)點的一致性哈希比較適合異構(gòu)節(jié)點、節(jié)點規(guī)模會發(fā)生變化的場景。

這種方法不僅解決了節(jié)點異構(gòu)性問題，還提高了系統(tǒng)的穩(wěn)定性。當(dāng)節(jié)點變化時，會有多個節(jié)點共同分擔(dān)系統(tǒng)的變化，因此穩(wěn)定性更高。

比如當(dāng)某個節(jié)點被移除時，對應(yīng)該節(jié)點的多個虛擬節(jié)點均會被移除。而這些虛擬節(jié)點按順時針方向的下一個虛擬節(jié)點，可能會對應(yīng)不同的物理節(jié)點，即這些不同的物理節(jié)點共同分擔(dān)了節(jié)點變化導(dǎo)致的壓力。

Memcached 便實現(xiàn)了該方法。

當(dāng)然，由于引入了虛擬節(jié)點，增加了節(jié)點規(guī)模，從而增加了節(jié)點的維護(hù)和管理的復(fù)雜度。比如新增一個節(jié)點或一個節(jié)點故障時，對應(yīng)到哈希環(huán)上則需要新增和刪除多個節(jié)點，數(shù)據(jù)的遷移等操作也會相應(yīng)的變復(fù)雜。

小結(jié)

一致性哈希是一種特殊的哈希算法，在使用一致性哈希算法后，節(jié)點增減變化時只影響到部分?jǐn)?shù)據(jù)的路由尋址，也就是說我們只要遷移部分?jǐn)?shù)據(jù)，就能實現(xiàn)集群的穩(wěn)定了。

當(dāng)某個節(jié)點退出時，會有壓垮后繼節(jié)點的風(fēng)險，因此可以給每個節(jié)點設(shè)置一個上限。如果所有節(jié)點都達(dá)到了上限怎么辦？說明你需要調(diào)整上限或增加節(jié)點了。

當(dāng)節(jié)點數(shù)較少時，可能會出現(xiàn)節(jié)點在哈希環(huán)上分布不均勻的情況，這樣每個節(jié)點實際占據(jù)環(huán)上的區(qū)間大小不一，最終導(dǎo)致業(yè)務(wù)對節(jié)點的訪問冷熱不均。此時我們可以通過引入更多的虛擬節(jié)點來解決這個問題，當(dāng)然通過虛擬節(jié)點也可以解決節(jié)點異構(gòu)性的問題。

總之節(jié)點數(shù)越多，使用哈希算法時，需要遷移的數(shù)據(jù)就越多；使用一致性哈希時，需要遷移的數(shù)據(jù)就越少。經(jīng)過測試，當(dāng)我們向 10 個節(jié)點組成的集群中增加節(jié)點時，如果使用了哈希算法，需要遷移高達(dá) 90.91% 的數(shù)據(jù)，使用一致性哈希的話，則只需要遷移 6.48% 的數(shù)據(jù)。