【分布式】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 {

    @Override
    public 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
     */
    @Override
    public 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);
    }

    @Override
    public IConsistentHashing add(Node node) {
        // 初始化虚拟节点
        for (int i = 0; i < virtualNum; i++) {
            int nodeKey = hash.hash(node.toString() + "-" + i);
            nodeMap.put(nodeKey, node);
        }

        return this;
    }

    @Override
    public IConsistentHashing remove(Node node) {
        // 移除虚拟节点
        // 其实这里有一个问题,如果存在 hash 冲突,直接移除会不会不够严谨?
        for (int i = 0; i < virtualNum; i++) {
            int nodeKey = hash.hash(node.toString() + "-" + i);
            nodeMap.remove(nodeKey);
        }

        return this;
    }

    @Override
    public Map<Integer, Node> nodeMap() {
        return Collections.unmodifiableMap(this.nodeMap);
    }

}

完整代码

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

完整代码参见 github

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

参考资料

consistent-hashing-redis

consistent-hash-algorithm

ConsistentHash

一致性hash的JAVA实现

原文 

https://segmentfault.com/a/1190000022981101

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » 【分布式】load balance 03-一致性哈希算法 java 实现

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址