使用一致性哈希讓數(shù)據(jù)均勻分布

作者：古明地覺 2023-12-05 14:44:01

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

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

維度考量

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

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

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

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

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

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

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

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

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

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

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

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

隔離故障域

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

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

性能穩(wěn)定性

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

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

哈希

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

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

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

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

因?yàn)槿∧＿\(yùn)算發(fā)生了變化，所以這個(gè) X 大概率不是 0（假設(shè) X 為 1），這時(shí)再查詢，就會(huì)找不到數(shù)據(jù)了。因?yàn)?nbsp;key-01 對(duì)應(yīng)的數(shù)據(jù)，存儲(chǔ)在節(jié)點(diǎn) A 上，而不是節(jié)點(diǎn) B。

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

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

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

一致性哈希

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

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

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

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

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

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

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

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

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

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

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

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

使用一致性哈希的話，對(duì)于 3 節(jié)點(diǎn) KV 存儲(chǔ)，如果我們?cè)黾?1 個(gè)節(jié)點(diǎn)，變?yōu)?4 節(jié)點(diǎn)集群，則只需要遷移 24.3% 的數(shù)據(jù)。遷移的數(shù)據(jù)量?jī)H為使用哈希算法時(shí)的三分之一，從而大大提升效率。

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

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

我們用 Python 簡(jiǎn)單實(shí)現(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)的最大長(zhǎng)度
        self.ring_max_len = ring_max_len
        # 節(jié)點(diǎn)在哈希環(huán)上的索引（有序）
        self.node_indexes = []
        # '節(jié)點(diǎn)在哈希環(huán)上的索引' 到 '節(jié)點(diǎn)' 的映射
        self.nodes_mapping = {}

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

小結(jié)

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

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

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

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

責(zé)任編輯：華軒來源：古明地覺的編程教室