我的编程空间,编程开发者的网络收藏夹
学习永远不晚

ava实现一致性Hash算法

短信预约 -IT技能 免费直播动态提醒
省份

北京

  • 北京
  • 上海
  • 天津
  • 重庆
  • 河北
  • 山东
  • 辽宁
  • 黑龙江
  • 吉林
  • 甘肃
  • 青海
  • 河南
  • 江苏
  • 湖北
  • 湖南
  • 江西
  • 浙江
  • 广东
  • 云南
  • 福建
  • 海南
  • 山西
  • 四川
  • 陕西
  • 贵州
  • 安徽
  • 广西
  • 内蒙
  • 西藏
  • 新疆
  • 宁夏
  • 兵团
手机号立即预约

请填写图片验证码后获取短信验证码

看不清楚,换张图片

免费获取短信验证码

ava实现一致性Hash算法

1. 实现原理

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

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

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

2. 解决数据倾斜的问题

什么是数据倾斜?

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

解决

为了解决这个问题,引入了虚拟节点的概念,一个真实的节点对应多个虚拟的节点
假设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);
    }

    
    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> {
    
    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;

        
        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;
        }

        
        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);
            }
        });
    }

到此这篇关于ava实现一致性Hash算法的文章就介绍到这了,更多相关Java hash算法内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

ava实现一致性Hash算法

下载Word文档到电脑,方便收藏和打印~

下载Word文档

猜你喜欢

ava实现一致性Hash算法

本文主要详细介绍了Java如何实现一致性Hash算法,其实现原理将key映射到 2^32 - 1 的空间中,将这个数字的首尾相连,形成一个环。想了解更多的同学,可以参考本文
2023-03-24

ava如何实现一致性Hash算法

这篇文章主要介绍了ava如何实现一致性Hash算法的相关知识,内容详细易懂,操作简单快捷,具有一定借鉴价值,相信大家阅读完这篇ava如何实现一致性Hash算法文章都会有所收获,下面我们一起来看看吧。1. 实现原理将key映射到 2^32 -
2023-07-05

聊聊一致性Hash算法代码实现

一致性hash算法常用于分布式缓存服务,把所有的服务节点进行hash,得到hash环上的位置。添加进服务的数据用同样的算法进行hash,然后从hash环上取得大于该hash值的第一个节点,如果没有大于该值的节点,那么就取整个环的第一个节点。

一致性 Hash 算法原理总结

一致性 Hash 算法是解决分布式缓存等问题的一种算法,本文介绍了一致性 Hash 算法的原理,并给出了一种实现和实际运用的案例。
Hash算法2024-12-02

什么是好的一致性 Hash 实现

看到微信群有人问 prd 用什么一致性 hash 算法好,就想起了这篇文章。这是以前做的测试。那么什么是好的一致性 hash 算法呢?除了性能还要考虑哪些因素呢?根据我自己的经验简单聊一下,有不正确的请大家指正。

不会一致性 Hash 算法,劝你简历别写搞过负载均衡

这两天看到技术群里,有小伙伴在讨论一致性hash算法的问题,正愁没啥写的题目就来了,那就简单介绍下它的原理。

怎么使用PHP实现分布算法之一致性哈希算法

这篇文章主要介绍怎么使用PHP实现分布算法之一致性哈希算法,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完!传统算法缺陷对于服务器分布,我们要考虑的东西有如下三点:数据平均分布,查找定位准确,降低宕机影响。传统算法一般是
2023-06-15

python的一致性算法hash_rin

下载地址:https://pypi.python.org/pypi/hash_ring/ 简单的说:如果你服务器部署多个redis,memechace想要客户端通过负载均衡的方式访问,就要用到这个hash_ring...........
2023-01-31

图解一致性哈希算法

要了解一致性哈希,首先我们必须了解传统的哈希及其在大规模分布式系统中的局限性。

基于Python如何实现Hash算法

本篇内容主要讲解“基于Python如何实现Hash算法”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“基于Python如何实现Hash算法”吧!1 前言Simhash的算法简单的来说就是,从海量文
2023-06-29

八分钟了解一致性算法 -- Raft算法

Raft算法是一种简洁而高效的分布式一致性算法,通过引入Leader选举和日志复制的机制,确保了分布式系统的共识和一致性。

算法之什么是一致性哈希?

一致性哈希是一种哈希算法,就是在移除或者增加一个结点时,能够尽可能小的改变已存在key的映射关系尽可能少的改变已有的映射关系,一般是沿着顺时针进行操作

阿里云二面:Zookeeper一致性算法

CAP理论指的是在一个分布式系统中,不可能同时满足Consistency(一致性)、Availablity(可用性)、Partition tolerance(分区容错性)这三个基本需求,最多只能满足其中的两项。

编程热搜

  • Python 学习之路 - Python
    一、安装Python34Windows在Python官网(https://www.python.org/downloads/)下载安装包并安装。Python的默认安装路径是:C:\Python34配置环境变量:【右键计算机】--》【属性】-
    Python 学习之路 - Python
  • chatgpt的中文全称是什么
    chatgpt的中文全称是生成型预训练变换模型。ChatGPT是什么ChatGPT是美国人工智能研究实验室OpenAI开发的一种全新聊天机器人模型,它能够通过学习和理解人类的语言来进行对话,还能根据聊天的上下文进行互动,并协助人类完成一系列
    chatgpt的中文全称是什么
  • C/C++中extern函数使用详解
  • C/C++可变参数的使用
    可变参数的使用方法远远不止以下几种,不过在C,C++中使用可变参数时要小心,在使用printf()等函数时传入的参数个数一定不能比前面的格式化字符串中的’%’符号个数少,否则会产生访问越界,运气不好的话还会导致程序崩溃
    C/C++可变参数的使用
  • css样式文件该放在哪里
  • php中数组下标必须是连续的吗
  • Python 3 教程
    Python 3 教程 Python 的 3.0 版本,常被称为 Python 3000,或简称 Py3k。相对于 Python 的早期版本,这是一个较大的升级。为了不带入过多的累赘,Python 3.0 在设计的时候没有考虑向下兼容。 Python
    Python 3 教程
  • Python pip包管理
    一、前言    在Python中, 安装第三方模块是通过 setuptools 这个工具完成的。 Python有两个封装了 setuptools的包管理工具: easy_install  和  pip , 目前官方推荐使用 pip。    
    Python pip包管理
  • ubuntu如何重新编译内核
  • 改善Java代码之慎用java动态编译

目录