用 rust 手擼一致性 hash 算法

背景

隨着互聯網規模的發展，單機服務已無法滿足業務的需求，分佈式架構應運而生。在分佈式環境下，需要多機協同作業，如何保證數據在分佈式環境下的一致性就成爲了亟需解決的問題，一致性 hash 就是爲了在多機環境下最大限度保證數據的一致性。

原理

在多機環境下，通常使用 (hash % N) 的方式，將數據映射到 N 臺服務器上。首先進行 hash 計算再與 N 臺機器取模，得到要轉發的具體機器。運算結束後，請求和機器的綁定關係就確定了，一旦集羣節點數發生變化，所有計算的結果都將失效，這對於分佈式緩存類的服務是無法接受的，這將導致請求直達 DB 且要大量更新緩存，給集羣帶來巨大壓力。

一致性 hash 的創新點是將節點的分配和數據的分配互相分離，拆分成兩個獨立的過程，數據和節點不通過 hash 直接關聯，這樣數據和節點就相互獨立了，節點的變化不會影響到整個分佈式系統，只需要局部的更新緩存即可。

一致性 hash 如何解耦數據和節點的關係呢？

創建一個哈希環，計算機器 (使用機器的屬性如 ip、端口等) 的 hash 值，將機器 “分佈” 於環上
當請求到達後，對請求計算 hash 值，並沿着哈希環順時針遍歷，將遍歷到的第一個節點作爲本次請求的轉發節點
當集羣中的機器發生增、減時，由於請求沒有和機器 "靜態綁定"，只需要計算請求的 hash 並沿着環順時針找到第一個節點即可。這種方式將請求和機器由 "靜態綁定" 轉爲 "動態綁定"，避免了整個集羣的 hash 失效，只會影響集羣的局部。

進一步優化：引入虛擬節點

將機器映射到哈希環上雖然解決了請求和機器硬綁定的問題，但還是會有負載不均衡的問題，出現 “數據傾斜”，爲了解決這個問題，引出了虛擬節點的解決方案：

爲每個真實的物理機器虛擬出 N 個虛擬節點
將虛擬節點映射到哈希環上，使得環上的節點更隨機和均勻
請求先匹配虛擬節點再由虛擬節點匹配到真實的節點

假設現在 node3 掛掉了，如果沒有虛擬節點，node3 上的請求將全部轉移到 node4 節點上，勢必給 node4 帶來巨大壓力，容易導致 node4 掛掉，node4 掛掉後 node3、node4 的請求將打到 node5 上，node5 更容易掛掉，從而引發 “雪崩效應”，導致整個集羣掛掉。

加入虛擬節點後，如果 node3 掛掉了，node3 上的請求將配給 node2 和 node5，分攤了這部分壓力，提升了集羣的健壯性，同時也提升了整個集羣應對請求的 “數據均衡” 的能力。

虛擬節點越多，請求到達各個節點的數量越均衡！

應用場景

負載均衡
分佈式緩存，如 redis
分佈式存儲，如 hdfs,mongo,clickhouse 等
分佈式計算，如 flink,spark 等

使用 rust 實現一致性 hash 算法

一致性 hash 有兩個重要的組成：節點和環，分別抽象成數據結構如下所示：

// 主機節點

#[derive(Debug, Clone)]

struct MachineNode {

    host: &'static str,

    ip: &'static str,

    port: u16,

}

// 爲MachineNode添加字符串轉換

impl ToString for MachineNode {

    fn to_string(&self) -> String {

        self.ip.to_string() + &self.port.to_string()

    }

}

// 環

#[derive(Debug)]

struct Ring<T: Clone + Debug + ToString> {

    // 每臺主機的虛擬節點數

    machine_virtual_node_num: usize,

    // 用於保存環上的數據

    datas: BTreeMap<u64, T>,

}

接着實現一個通用的計算 hash 值的函數:

// hash函數

fn hash<T: Hash>(val: &T) -> u64 {

    let mut hasher = DefaultHasher::new();

    val.hash(&mut hasher);

    hasher.finish() % 197

}

設置默認虛擬節點個數爲 10：

const DEFAULT_MACHINE_VIRTUAL_NODE_NUM: usize = 10;

接下來實現節點映射到環，和從環中刪除節點的方法：

fn new() -> Self {

        Self::with_virtual_node_num(DEFAULT_MACHINE_VIRTUAL_NODE_NUM)

}

fn with_virtual_node_num(num: usize) -> Self {

    Self {

        machine_virtual_node_num: num,

        datas: BTreeMap::new(),

    }

}

// 增加節點到環上

fn add(&mut self, node: &T) {

    // 將主機虛擬出machine_virtual_node_num個

    for i in 0..self.machine_virtual_node_num {

        let key = hash(&(node.to_string() + &i.to_string()));

        self.datas.insert(key, node.clone());

    }

}

// 批量添加到環

fn mult_add(&mut self, nodes: &[T]) {

    if !nodes.is_empty() {

        for node in nodes {

            self.add(node);

        }

    }

}

// 從環上移除節點

fn remove(&mut self, node: &T) {

    assert!(!self.datas.is_empty());

    for i in 0..self.machine_virtual_node_num {

        let key = hash(&(node.to_string() + &i.to_string()));

        self.datas.remove(&key);

    }

}

// 批量刪除

fn mult_remove(&mut self, nodes: &[T]) {

    if !nodes.is_empty() {

        for node in nodes {

            self.remove(node);

        }

    }

}

如何獲取節點呢？通過 hash 函數計算出 hash 值，並沿着環順時針查找，找到的第一個節點便是目標節點：

// 獲取節點

fn get(&self, key: u64) -> Option<&T> {

    if self.datas.is_empty() {

        return None;

    }

    let mut keys = self.datas.keys();

    println!("key:{key}");

    keys.find(|&k| k >= &key)

        .and_then(|k| self.datas.get(k))

        .or(keys.nth(0).and_then(|x| self.datas.get(x)))

}

如何知道請求應該轉發到哪臺機器呢？首先對請求計算 hash 值，並調用 get 方法即可：

// 獲取處理數據的機器

fn dispatch(&self, data: i32) -> Option<&T> {

    let key = hash(&data);

    self.get(key)

}

下面編寫測試用例，包含 4 臺機器，每臺機器虛擬爲兩個節點，並添加到哈希環上。並模擬請求數據應該被轉發給哪臺機器處理：

fn main() {

    let virtual_num = 2;

    let mut ring = Ring::with_virtual_node_num(virtual_num);

    let node1 = MachineNode {

        host: "bigdata1",

        ip: "192.168.0.29",

        port: 18088,

    };

    let node2 = MachineNode {

        host: "bigdata2",

        ip: "192.168.0.14",

        port: 28089,

    };

    let node3 = MachineNode {

        host: "bigdata3",

        ip: "192.168.0.22",

        port: 8088,

    };

    let node4 = MachineNode {

        host: "bigdata4",

        ip: "192.168.0.222",

        port: 8088,

    };

    ring.add(&node1);

    ring.add(&node2);

    ring.add(&node3);

    ring.add(&node4);

    println!("ring:{:#?}", ring);

    // 一個數據過來，通過dispatch方法獲取哪臺機器處理

    let quest = 123;

    let result = ring.dispatch(quest);

    println!("處理機器：{:#?}", result);

    let quest = 1234;

    let result = ring.dispatch(quest);

    println!("處理機器：{:#?}", result);

    let quest = 12345;

    let result = ring.dispatch(quest);

    println!("處理機器：{:#?}", result);

}

下面是輸出：

感興趣的童鞋可以增加或刪除部分節點，查看請求分佈的情況！

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/fdJLj4zT3KgR3qb7EpNh9Q

背景

原理

進一步優化：引入虛擬節點

應用場景

使用 rust 實現一致性 hash 算法

猜你喜歡