负载均衡之一致性哈希算法

说到负载均衡的hash算法,自然会联想起如下这样的算法hash(object)%nodeTotal而在集群中,机器的动态上下线是常见的情况,如果集群是无状态的,那么上述的算法没有问题.但是如果是缓存之类的集群,节点的动态上下线会导致几乎所有的key的重新映射,这样造成的影响是数据错乱,相同备份的数据同时存在于集群中的多个节点,造成内存空间的浪费为了解决上述的问题,一致性哈希算法就被…

大家好,又见面了,我是你们的朋友全栈君。

说到负载均衡的hash算法,自然会联想起如下这样的算法

hash(object)%nodeTotal

而在集群中,机器的动态上下线是常见的情况,如果集群是无状态的,那么上述的算法没有问题.但是如果是缓存之类的集群,节点的动态上下线会导致几乎所有的key的重新映射,这样造成的影响是数据错乱,相同备份的数据同时存在于集群中的多个节点,造成内存空间的浪费

为了解决上述的问题,一致性哈希算法就被提出了
一致性哈希算法的目标是对于K个请求,节点的上下线只会引起K/nodeTotal的key重新映射,而在节点稳定的时候,同一个key的每次请求映射都是一样的

一致性哈希算法实现原理如下
首先将node节点映射到一个圆上(圆的大小是2^32-1),然后将请求object映射到圆上,最后顺时针转动请求,转动的目的是让请求映射到node节点上

原理图如下
image

上述的算法在node2被删除的情况下回发生什么呢?

它会造成object3的请求映射到node3节点上,并且对于其他的请求没有发生变化,如图所示
image

如果添加了node4节点请求又会如何发生变化呢?

变化是object2倍映射到node4上,对于其他的请求没有变化
image

上述的一致性hash算法满足了单调性(单调性是指对于k个请求,n个node,当一个node上线或者下线时只会引起k/n个请求映射发生变化),上述算法看似完美,但还存在一个问题,比如
image
对于节点n1,n2.我们有request1,request2,request3,request4四个请求,而四个请求同时落在n2节点上,

为了更好的实现负载均衡,我们需要引入虚拟节点的概念,就是将一个节点虚拟化为多个节点将其中的请求落在N1上,入下图所示
这里写图片描述

下面是一致性哈希算法的java实现,这里的代码引自xxl-job,jobId就是相当于请求id

首先计算hash,hash在该算法中地位非常重要,它直接影响了node是否能均匀的落在圆上

private static long hash(String key) {
    // md5 byte
    MessageDigest md5;
    try {
        md5 = MessageDigest.getInstance("MD5");
    } catch (NoSuchAlgorithmException e) {
        throw new RuntimeException("MD5 not supported", e);
    }
    md5.reset();
    byte[] keyBytes = null;
    try {
        keyBytes = key.getBytes("UTF-8");
    } catch (UnsupportedEncodingException e) {
        throw new RuntimeException("Unknown string :" + key, e);
    }
    //System.out.println(keyBytes.length);
    md5.update(keyBytes);
    byte[] digest = md5.digest();
    //System.out.println(digest.length);
    // 
    long hashCode = ((long) (digest[3] & 0xFF) << 24)
            | ((long) (digest[2] & 0xFF) << 16)
            | ((long) (digest[1] & 0xFF) << 8)
            | (digest[0] & 0xFF);
    long truncateHashCode = hashCode & 0xffffffffL;
    return truncateHashCode;
}

下面是真正的请求路由,这里的jobId就是相当于requestId

public String route(int jobId, ArrayList<String> addressList) {
    //首先是将node定位到圆上,我们以 hash - address方式定位
    //因为后面需要获取离jobId最近node所以将数据放入到TreeMap中
    TreeMap<Long, String> addressRing = new TreeMap<Long, String>();
    for (String address : addressList) {
        //将每个node虚拟化为5个节点
        for (int i = 0; i < VIRTUAL_NODE_NUM; i++) {
            long addressHash = hash("SHARD-" + address + "-NODE-" + i);
            addressRing.put(addressHash, address);
        }
    }
    long jobHash = hash(String.valueOf(jobId));
    //这里是顺时针转动jobHash寻找node的策略,其实就是寻找node哈希值大于等于jobId哈希值的最近一个node
    SortedMap<Long, String> lastRing = addressRing.tailMap(jobHash);
    if (!lastRing.isEmpty()) {
        return lastRing.get(lastRing.firstKey());
    }
    //如果请求落在最大一组hash上,那么就返回第一个node
    return addressRing.firstEntry().getValue();
}

参考http://blog.csdn.net/cywosp/article/details/23397179

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/129634.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • mysql中的trace工具

    mysql中的trace工具

  • CSS加JS实现网页返回顶部功能

    CSS加JS实现网页返回顶部功能最近在设计自己的博客,前端页面在内容很多的时候往下拖动会有滚动条。通常我们都需要一个返回顶部的功能来实现快速来到网页顶部。当然实现方式不止一种,这里我采用的最实用的一种。使用CSS+Jquery方式代码量相对较少,容易理解。实现原理1.我们需要再DOM中添加自己的DIV,里面包含一个a标签,a标签里面包含两个img标签用于存放返回顶部的图片。2.添加必要的CSS样式3.然后…

  • java dom4j 添加节点_Java dom4j获取,添加,删除,查找,设置Element节点方法「建议收藏」

    java dom4j 添加节点_Java dom4j获取,添加,删除,查找,设置Element节点方法「建议收藏」Javadom4j获取,添加,删除,查找,设置Element节点方法1.获取文档的根节点.ElementrootElm=document.getRootElement();2.取得某节点的单个子节点.ElementmemberElm=root.element(“member”);//”member”是节点名3.取得节点的文字Stringtext=memberElm.getText()…

  • springboot+mockito测试controller层遇到的问题

    springboot+mockito测试controller层遇到的问题

  • matlab中矩阵的秩,matlab矩阵的秩

    matlab中矩阵的秩,matlab矩阵的秩如下所示为一方阵在matlab输入矩阵:A=[124;407913];2.2查阅matlabhelp可以知道,利用eig函数可以快速求解矩阵的特征值与特征……Matlab矩阵分析与处理_理学_高等教育_教育专区。1、单位矩阵,随机矩阵,零矩阵和对角阵2、产生5阶希尔伯特矩阵H和5阶帕斯卡矩阵P,且求其行列式的值Hh和Hp以及它们……结构数…

  • java heap space 什么意思_Java heap space 解决方法(转)

    java heap space 什么意思_Java heap space 解决方法(转)因为程序要从数据读取近10W行记录处理,当读到9W的时候就出现java.lang.OutOfMemoryError:Javaheapspace这样的错误。在网上一查可能是JAVA的堆栈设置太小的原因。跟据网上的答案大致有这两种解决方法:1、设置环境变量setJAVA_OPTS=-Xms32m-Xmx512m可以根据自己机器的内存进行更改,但本人测试这种方法并没有解决问题。可能是还有…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号