理解一致性hash算法以及TreeMap简易实现示例
作者：niewj
来源：SegmentFault 思否
1. 算法说明
目的: 一致性hash算法的目的, 就是为了解决2个问题:
-
hash算法中损毁节点对应的请求失败; -
有节点损毁后, 请求落点不均匀问题;
2. 示例说明
一个hash环, 模拟节点数为1024个, 实际可用的节点有8个(比如线上实际的ip服务节点), 1024个模拟节点跟8个ip节点有均匀的映射关系;
我们模拟的环上有 1024 个虚拟节点, 真实可用的节点(可以想象为线上实际集群有8个可用ip供存储)
使用一致性hash使用方法:
-
环上的虚拟节点跟所有真实节点之间有个映射关系 (1024个节点跟8个节点的映射, 用的是除8取模的对应关系,
例如: 0, 8, 16, 24 都对应到node_0;
1, 7, 15, 23都映射到node_1); -
发一个请求字符串, 我们计算出hash值, 除 1024 取模; -
将取模结果, 先映射到虚拟节点环上的点, 比如 "hello"的hashcode/1024 = 210 -
查询虚拟环和真实节点映射关系, 210对应的真实节点为 node_2; 于是, "hello" 就落到节点 node_2 上; -
我们可以调用 com.niewj.dsalg.ConsistentHashMock#dropBadNode("node_2") 来删除 node_2节点; -
删除 node_2 后, "hello"应该落在 211 上, 对应到环的真实映射, 是 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 {/*** 假设我们一共初始化有8个节点(可以是ip, 就理解为ip吧);* 把 1024个虚拟节点跟 8个资源节点相对应*/public static Map<Integer, String> realNodeMap = new HashMap<>();public static int V_NODES = 1024; // 假设我们的环上有1024个虚拟节点static TreeMap<Integer, String> 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++) {// 每个虚拟节点跟其取模的余数的 nodeMap 中的key相对应;// 下面删除虚拟节点的时候, 就可以根据取模规则来删除 TreeMap中的节点了;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.找到对应节点最近的key的节点值String realNode = virtualNodeMap.ceilingEntry(vnode).getValue();return realNode;}/*** 模拟删掉一个物理可用资源节点, 其他资源可以返回其他节点** @param nodeName*/public static void dropBadNode(String nodeName) {int nodek = -1;// 1. 遍历 nodeMap 找到故障节点 nodeName对应的key;for (Map.Entry<Integer, String> entry : realNodeMap.entrySet()) {if (nodeName.equalsIgnoreCase(entry.getValue())) {nodek = entry.getKey();break;}}if (nodek == -1) {System.err.println(nodeName + "在真实资源节点中无法找到, 放弃删除虚拟节点!");return;}// 2. 根据故障节点的 key, 对应删除所有 chMap中的虚拟节点Iterator<Map.Entry<Integer, String>> iter = virtualNodeMap.entrySet().iterator();while (iter.hasNext()) {Map.Entry<Integer, String> entry = iter.next();int key = entry.getKey();String value = entry.getValue();if (key % REAL_NODE_COUNT == nodek) {System.out.println("删除节点虚拟节点: [" + key + " = " + value + "]");iter.remove();}}}public static void main(String[] args) {// 1. 一个字符串请求(比如请求字符串存储到8个节点中的某个实际节点);String requestValue = "hello";// 2. 打印虚拟节点和真实节点的对应关系;System.out.println(virtualNodeMap);// 3. 核心: 传入请求信息, 返回实际调用的节点信息System.out.println(getRealServerNode(requestValue));// 4. 删除某个虚拟节点后System.out.println("==========删除 node_2 之后: ================");dropBadNode("node_2");System.out.println("===============删除之后的虚拟节点map: ===========");System.out.println(virtualNodeMap);System.out.println("==============删除之后, 获取节点的真正node节点对应者: ");System.out.println(getRealServerNode(requestValue));}}