【分布式】load balance 03-一致性哈希算法 java 实现

负载均衡系列专题

01-负载均衡基础知识

02-一致性 hash 原理

03-一致性哈希算法 java 实现

04-负载均衡算法 java 实现

本节我们来看一下如何实现一个一致性 hash 框架。

源码

普通 hash

我们首先定义一下 hash 接口，以及最简单的 jdk 实现：

• IHash

public interface IHash {
    /*** 计算 hash 值* @param text 文本* @return 结果* @since 0.0.1*/int hash(String text);}

• HashJdk.java

public class HashJdk implements IHash {
    @Overridepublic int hash(String text) {
    return text.hashCode();}}

Node 定义

用来定义一个节点：

此处省略了一些方法。

public class Node {
    /*** 节点名称* @since 0.0.1*/private String name;/*** 节点 ip* @since 0.0.1*/private String ip;public Node(String name, String ip) {
    this.name = name;this.ip = ip;}public Node(String ip) {
    this(ip, ip);}//Getter & Setter & toString()// equals && hashCode
}

核心实现

• IConsistentHashing.java

一致性 hash 的接口定义。

public interface IConsistentHashing {
    /*** 获取对应的节点* @param key key* @return 节点* @since 0.0.1*/Node get(final String key);/*** 添加节点* @param node 节点* @return this* @since 0.0.1*/IConsistentHashing add(final Node node);/*** 移除节点* @param node 节点* @return this* @since 0.0.1*/IConsistentHashing remove(final Node node);/*** 获取节点信息* @return 节点* @since 0.0.1*/Map<Integer, Node> nodeMap();}

• 默认实现

public class ConsistentHashing implements IConsistentHashing {
    /*** 虚拟节点数量* @since 0.0.1*/private final int virtualNum;/*** hash 策略* @since 0.0.1*/private final IHash hash;/*** node map 节点信息** key: 节点 hash* Node: 节点* @since 0.0.1*/private final TreeMap<Integer, Node> nodeMap = new TreeMap<>();public ConsistentHashing(int virtualNum, IHash hash) {
    this.virtualNum = virtualNum;this.hash = hash;}/*** 沿环的顺时针找到虚拟节点* @param key key* @return 结果* @since 0.0.1*/@Overridepublic Node get(String key) {
    final int hashCode = hash.hash(key);Integer target = hashCode;// 不包含时候的处理if (!nodeMap.containsKey(hashCode)) {
    target = nodeMap.ceilingKey(hashCode);if (target == null && !nodeMap.isEmpty()) {
    target = nodeMap.firstKey();}}return nodeMap.get(target);}@Overridepublic IConsistentHashing add(Node node) {
    // 初始化虚拟节点for (int i = 0; i < virtualNum; i++) {
    int nodeKey = hash.hash(node.toString() + "-" + i);nodeMap.put(nodeKey, node);}return this;}@Overridepublic IConsistentHashing remove(Node node) {
    // 移除虚拟节点// 其实这里有一个问题，如果存在 hash 冲突，直接移除会不会不够严谨？for (int i = 0; i < virtualNum; i++) {
    int nodeKey = hash.hash(node.toString() + "-" + i);nodeMap.remove(nodeKey);}return this;}@Overridepublic Map<Integer, Node> nodeMap() {
    return Collections.unmodifiableMap(this.nodeMap);}}

完整代码

其他还有一些引导类等辅助工具。

完整代码参见 github

参考资料

consistent-hashing-redis

consistent-hash-algorithm

ConsistentHash

一致性hash的JAVA实现