vlambda博客
学习文章列表

理解一致性hash算法以及TreeMap简易实现示例

作者:niewj

来源:SegmentFault 思否




1. 算法说明


目的: 一致性hash算法的目的, 就是为了解决2个问题:


  1. hash算法中损毁节点对应的请求失败;
  2. 有节点损毁后, 请求落点不均匀问题;





2. 示例说明


一个hash环, 模拟节点数为1024个, 实际可用的节点有8个(比如线上实际的ip服务节点), 1024个模拟节点跟8个ip节点有均匀的映射关系;


我们模拟的环上有 1024 个虚拟节点, 真实可用的节点(可以想象为线上实际集群有8个可用ip供存储)


使用一致性hash使用方法:


  1. 环上的虚拟节点跟所有真实节点之间有个映射关系
       
         
         
       
    (1024个节点跟8个节点的映射, 用的是除8取模的对应关系,
       
         
         
       

    例如: 0, 8, 16, 24 都对应到node_0;
    1, 7, 15, 23都映射到node_1);
  2. 发一个请求字符串, 我们计算出hash值, 除 1024 取模;
  3. 将取模结果, 先映射到虚拟节点环上的点, 比如 "hello"的hashcode/1024 = 210
  4. 查询虚拟环和真实节点映射关系, 210对应的真实节点为 node_2; 于是, "hello" 就落到节点 node_2 上;
  5. 我们可以调用
    com.niewj.dsalg.ConsistentHashMock#dropBadNode("node_2") 来删除 node_2节点;
  6. 删除 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));
}}





点击左下角阅读原文,到  SegmentFault 思否社区  和文章作者展开更多互动和交流。

- END -