Java实现一致性Hash算法详情

2023-01-21 0 1,119

目录

1. 实现原理

将key映射到 2^32 - 1 的空间中,将这个数字的首尾相连,形成一个环

  • 计算节点(使用节点名称、编号、IP地址)的hash值,放置在环上
  • 计算key的hash值,放置在环上,顺时针寻找到的第一个节点,就是应选取的节点

Java实现一致性Hash算法详情

例如:p2、p4、p6三个节点,key11、key2、key27按照顺序映射到p2、p4、p6上面,假设新增一个节点p8在p6节点之后,这个时候只需要将key27从p6调整到p8就可以了;也就是说,每次新增删除节点时,只需要重新定位该节点附近的一小部分数据

2. 解决数据倾斜的问题

2.1 什么是数据倾斜?

如果服务器的节点过少,容易引起key的倾斜。例如上面的例子中p2、p4、p6分布在环的上半部分,下半部分是空的。那么映射到下半部分的key都会被分配给p2,key过度倾斜到了p2缓存间节点负载不均衡。

2.2 解决

为了解决这个问题,引入了虚拟节点的概念,一个真实的节点对应多个虚拟的节点,假设1个真实的节点对应3个虚拟节点,那么p1对应的就是p1-1、p1-2、p1-3

  • 计算虚拟节点的Hash值,放置在环上
  • 计算key的Hash值,在环上顺时针寻找到对应选取的虚拟节点,例如:p2-1,对应真实的节点p2

虚拟节点扩充了节点的数量,解决了节点较少的情况下数据倾斜的问题,而且代价非常小,只需要新增一个字典(Map)维护真实的节点与虚拟节点的映射关系就可以了

3. 代码实现

3.1 ConsistentHash

这里使用了泛型的方式来保存数据,可以根据不同的类型,获取到不同的节点存储

public class ConsistentHash<T> {

    //自定义hash方法
    private Hash<Object> hashMethod;

    //创建hash映射,虚拟节点映射真实节点
    private final Map<Integer, T> hashMap = new ConcurrentHashMap<>();

    //将所有的hash保存起来
    private List<Integer> keys = new ArrayList<>();

    //默认虚拟节点数量
    private final int replicas;

    public ConsistentHash() {
        this(3, Utils::rehash);
    }

    public ConsistentHash(int replicas, Hash<Object> hashMethod) {
        this.replicas = replicas;
        this.hashMethod = hashMethod;
    }

    @SafeVarargs
    public final void add(T... keys) {
        for (T key : keys) {
            //根据虚拟节点个数来计算虚拟节点
            for (int i = 0; i < this.replicas; i++) {
                //根据函数获取到对应的hash值
                int hash = this.hashMethod.hash(i + \":\" + key.toString());
                this.keys.add(hash);
                this.hashMap.put(hash, key);
            }
        }
        //排序,因为是一个环状结构
        Collections.sort(this.keys);
    }

    /**
     * 根据对应的key来获取到节点信息
     *
     * @param key
     * @return
     */
    public T get(Object key) {
        Objects.requireNonNull(key, \"key不能为空\");
        int hash = this.hashMethod.hash(key);
        //获取到对应的节点信息
        int idx = Utils.search(this.keys.size(), h -> this.keys.get(h) >= hash);
        //如果idx == this.keys.size() ,就代表需要取 this.keys.get(0); 因为是环状,所以需要使用 % 来进行处理
        return this.hashMap.get(this.keys.get(idx % this.keys.size()));
    }
}

3.2 Hash

这里定义了一个函数结构,用于自定计算hash值

@FunctionalInterface
public static interface Hash<T> {
    /**
     * 计算hash值
     *
     * @param t
     * @return int类型
     */
    int hash(T t);
}

3.3 Utils

由于hashcode采用的int类型进行存储,那么就需要考虑,hash是否超过了int最大存储,如果超过了那么存储的数字就是负数,会对获取节点造成影响,所以这里在取hash值时,采用了hashmap中获取到hashcode之后对其进行与操作,可以减少hash冲突,也可以避免负数的产生

public static class Utils {
		// int类型的最大数据
        static final int HASH_BITS = 0x7fffffff;

        /**
         * 通过二分查找法,定义数组索引位置
         *
         * @param len
         * @param f
         * @return
         */
        public static int search(int len, Function<Integer, Boolean> f) {
            int i = 0, j = len;
            //通过二分查找发来定为索引位置
            while (i < j) {
                //长度除于2
                int h = (i + j) >> 1;
                //调用函数,判断当前的索引值是否大于
                if (f.apply(h)) {
                    //向低半段进行遍历
                    j = h;
                } else {
                    //向高半段进行遍历
                    i = h + 1;
                }
            }
            return i;
        }
        /**
         * 将返回的hash能够平均的计算在 int类型之间
         *
         * @param o
         * @return
         */
        public static int rehash(Object o) {
            int h = o.hashCode();
            return (h ^ (h >>> 16)) & HASH_BITS;
        }
    }

3.4 main

下面是main方法进行测试,在后面新增了一个节点之后,只会调整 zs 数据到 109 节点,而且其他两个key的获取不会受到影响

public static void main(String[] args) {
        ConsistentHash<String> consistentHash = new ConsistentHash<>();
        consistentHash.add(\"192.168.2.106\", \"192.168.2.107\", \"192.168.2.108\");

        Map<String, Object> map = new HashMap<>();
        map.put(\"zs\", \"192.168.2.108\");
        map.put(\"999999\", \"192.168.2.106\");
        map.put(\"233333\", \"192.168.2.106\");

        map.forEach((k, v) -> {
            String node = consistentHash.get(k);
            if (!v.equals(node)) {
                throw new IllegalArgumentException(\"节点获取错误,key:\" + k + \",获取到的节点值为:\" + node);
            }
        });

        consistentHash.add(\"192.168.2.109\");
        map.put(\"zs\", \"192.168.2.109\");
        map.forEach((k, v) -> {
            String node = consistentHash.get(k);
            if (!v.equals(node)) {
                throw new IllegalArgumentException(\"节点获取错误,key:\" + k + \",获取到的节点值为:\" + node);
            }
        });
    }

:本文采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可, 转载请附上原文出处链接。
1、本站提供的源码不保证资源的完整性以及安全性,不附带任何技术服务!
2、本站提供的模板、软件工具等其他资源,均不包含技术服务,请大家谅解!
3、本站提供的资源仅供下载者参考学习,请勿用于任何商业用途,请24小时内删除!
4、如需商用,请购买正版,由于未及时购买正版发生的侵权行为,与本站无关。
5、本站部分资源存放于百度网盘或其他网盘中,请提前注册好百度网盘账号,下载安装百度网盘客户端或其他网盘客户端进行下载;
6、本站部分资源文件是经压缩后的,请下载后安装解压软件,推荐使用WinRAR和7-Zip解压软件。
7、如果本站提供的资源侵犯到了您的权益,请邮件联系: 442469558@qq.com 进行处理!

猪小侠源码-最新源码下载平台 Java教程 Java实现一致性Hash算法详情 http://www.20zxx.cn/464084/xuexijiaocheng/javajc.html

猪小侠源码,优质资源分享网

常见问题
  • 本站所有资源版权均属于原作者所有,均只能用于参考学习,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担
查看详情
  • 最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,建议提前注册好百度网盘账号,使用百度网盘客户端下载
查看详情

相关文章

官方客服团队

为您解决烦忧 - 24小时在线 专业服务