理解一致性hash算法以及TreeMap簡易實現(xiàn)示例

作者：niewj

來源：SegmentFault 思否

1. 算法說明

目的: 一致性hash算法的目的, 就是為了解決2個問題:

1. hash算法中損毀節(jié)點對應(yīng)的請求失敗;
2. 有節(jié)點損毀后, 請求落點不均勻問題;

2. 示例說明

一個hash環(huán), 模擬節(jié)點數(shù)為1024個, 實際可用的節(jié)點有8個(比如線上實際的ip服務(wù)節(jié)點), 1024個模擬節(jié)點跟8個ip節(jié)點有均勻的映射關(guān)系;

我們模擬的環(huán)上有 1024 個虛擬節(jié)點, 真實可用的節(jié)點(可以想象為線上實際集群有8個可用ip供存儲)

使用一致性hash使用方法:

1. 環(huán)上的虛擬節(jié)點跟所有真實節(jié)點之間有個映射關(guān)系

   (1024個節(jié)點跟8個節(jié)點的映射, 用的是除8取模的對應(yīng)關(guān)系,

   
   例如: 0, 8, 16, 24 都對應(yīng)到node_0;
       1, 7, 15, 23都映射到node_1);

2. 發(fā)一個請求字符串, 我們計算出hash值, 除 1024 取模;
3. 將取模結(jié)果, 先映射到虛擬節(jié)點環(huán)上的點, 比如 "hello"的hashcode/1024 = 210
4. 查詢虛擬環(huán)和真實節(jié)點映射關(guān)系, 210對應(yīng)的真實節(jié)點為 node_2; 于是, "hello" 就落到節(jié)點 node_2 上;
5. 我們可以調(diào)用
   com.niewj.dsalg.ConsistentHashMock#dropBadNode("node_2") 來刪除 node_2節(jié)點;
6. 刪除 node_2 后, "hello"應(yīng)該落在 211 上, 對應(yīng)到環(huán)的真實映射, 是 node_3 , 于是, "hello"的請求就落到 node_3;
   這, 就是 一致性hash算法!

3. 算法代碼示例:

package com.niewj.dsalg;
import java.util.HashMap;import java.util.Iterator;import java.util.Map;import java.util.TreeMap;
/** * Created by niewj on 2020/8/14 18:40 */public class ConsistentHashMock {
    /**     * 假設(shè)我們一共初始化有8個節(jié)點(可以是ip, 就理解為ip吧);     * 把 1024個虛擬節(jié)點跟 8個資源節(jié)點相對應(yīng)     */    public static Map realNodeMap = new HashMap<>();    public static int V_NODES = 1024; // 假設(shè)我們的環(huán)上有1024個虛擬節(jié)點    static TreeMap virtualNodeMap = new TreeMap<>();    private static final Integer REAL_NODE_COUNT = 8;
    static {        realNodeMap.put(0, "node_0");        realNodeMap.put(1, "node_1");        realNodeMap.put(2, "node_2");        realNodeMap.put(3, "node_3");        realNodeMap.put(4, "node_4");        realNodeMap.put(5, "node_5");        realNodeMap.put(6, "node_6");        realNodeMap.put(7, "node_7");
        for (Integer i = 0; i < V_NODES; i++) {            // 每個虛擬節(jié)點跟其取模的余數(shù)的 nodeMap 中的key相對應(yīng);            // 下面刪除虛擬節(jié)點的時候, 就可以根據(jù)取模規(guī)則來刪除 TreeMap中的節(jié)點了;            virtualNodeMap.put(i, realNodeMap.get(i % REAL_NODE_COUNT));        }    }

    /**     * 輸入一個id     *     * @param value     * @return     */    public static String getRealServerNode(String value) {        // 1. 傳遞來一個字符串, 得到它的hash值        Integer vnode = value.hashCode() % 1024;        // 2.找到對應(yīng)節(jié)點最近的key的節(jié)點值        String realNode = virtualNodeMap.ceilingEntry(vnode).getValue();
        return realNode;    }
    /**     * 模擬刪掉一個物理可用資源節(jié)點, 其他資源可以返回其他節(jié)點     *     * @param nodeName     */    public static void dropBadNode(String nodeName) {        int nodek = -1;        // 1. 遍歷 nodeMap 找到故障節(jié)點 nodeName對應(yīng)的key;        for (Map.Entry entry : realNodeMap.entrySet()) {            if (nodeName.equalsIgnoreCase(entry.getValue())) {                nodek = entry.getKey();                break;            }        }        if (nodek == -1) {            System.err.println(nodeName + "在真實資源節(jié)點中無法找到, 放棄刪除虛擬節(jié)點!");            return;        }
        // 2. 根據(jù)故障節(jié)點的 key, 對應(yīng)刪除所有 chMap中的虛擬節(jié)點        Iterator> iter = virtualNodeMap.entrySet().iterator();        while (iter.hasNext()) {            Map.Entry entry = iter.next();            int key = entry.getKey();            String value = entry.getValue();            if (key % REAL_NODE_COUNT == nodek) {                System.out.println("刪除節(jié)點虛擬節(jié)點: [" + key + " = " + value + "]");                iter.remove();            }        }    }
    public static void main(String[] args) {        // 1. 一個字符串請求(比如請求字符串存儲到8個節(jié)點中的某個實際節(jié)點);        String requestValue = "hello";        // 2. 打印虛擬節(jié)點和真實節(jié)點的對應(yīng)關(guān)系;        System.out.println(virtualNodeMap);        // 3. 核心: 傳入請求信息, 返回實際調(diào)用的節(jié)點信息        System.out.println(getRealServerNode(requestValue));        // 4. 刪除某個虛擬節(jié)點后        System.out.println("==========刪除 node_2 之后: ================");        dropBadNode("node_2");        System.out.println("===============刪除之后的虛擬節(jié)點map: ===========");        System.out.println(virtualNodeMap);        System.out.println("==============刪除之后, 獲取節(jié)點的真正node節(jié)點對應(yīng)者: ");        System.out.println(getRealServerNode(requestValue));
    }}