欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Java一个简单的一致性hash算法(带虚拟节点)

程序员文章站 2024-03-19 21:27:22
...

最近由于项目需要实现一个负载均衡的功能。考虑到以往的技术应用,准备参考Mycat的一致性hash算法,实现此功能。查阅网上资料和Mycat一致性hash算法的源码后,编写了一个简单的实现算法。

具体实现如下:

缓存实现参考:https://blog.csdn.net/weixin_35971547/article/details/89427914

import com.gccp.translate.getway.cache.LocalCache;
import com.google.common.collect.Maps;
import com.google.common.collect.Sets;
import com.google.common.hash.Hashing;
import org.apache.commons.lang3.StringUtils;
import org.springframework.beans.factory.annotation.Value;
import org.springframework.stereotype.Component;

import java.util.Objects;
import java.util.Set;
import java.util.SortedMap;
import java.util.stream.IntStream;

/**
 * @author hilbert.xu
 * @date 2019/4/20
 */
@Component
public class ConsistentHash {

    /**
     * 虚拟节点数
     */
    private static final int virtualNodeNum = 160;


    /**
     * 获取服务
     *
     * @param key 客户端请求ip
     */
    @SuppressWarnings("unchecked")
    public static String getServer(String key) {
        // 本地缓存,监听的可用服务 缓存实现参考:https://blog.csdn.net/weixin_35971547/article/details/89427914
        Object value = LocalCache.getInstance().getValue("servers");
        Set<String> servers = Objects.isNull(value) ? Sets.newHashSet() : (Set<String>) value;
        // 添加虚拟节点
        SortedMap<Integer, String> virtualNodes = Maps.newTreeMap();
        servers.stream().map(StringBuilder::new)
                .forEach(ips -> IntStream.range(0, virtualNodeNum)
                        .mapToObj(i -> ips.append("&&VN").append(i).toString()).forEach(virtualNodeName -> {
                            int hash = getHash(virtualNodeName);
                            virtualNodes.put(hash, virtualNodeName);
                        }));
        // 得到带路由的结点的Hash值
        int hash = getHash(key);
        // 得到大于该Hash值的所有Map
        SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);
        String virtualNode;
        if (subMap.isEmpty()) {
            //如果没有比该key的hash值大的,则从第一个node开始
            Integer i = virtualNodes.firstKey();
            //返回对应的服务器
            virtualNode = virtualNodes.get(i);
        } else {
            //第一个Key就是顺时针过去离node最近的那个结点
            Integer i = subMap.firstKey();
            //返回对应的服务器
            virtualNode = subMap.get(i);
        }
        //virtualNode虚拟节点名称要截取一下
        if (StringUtils.isNotBlank(virtualNode)) {
            return virtualNode.substring(0, virtualNode.indexOf("&&"));
        }
        return null;
    }

    /**
     * 使用FNV1_32_HASH算法计算服务器的Hash值
     */
    private static int getHash(String str) {
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (int i = 0; i < str.length(); i++) {
            hash = (hash ^ str.charAt(i)) * p;
        }
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;

        // 如果算出来的值为负数则取其绝对值
        if (hash < 0) {
            hash = Math.abs(hash);
        }
        return hash;
    }
}

实现比较简单,Hash计算算法网上查阅得到,基本可以满足需求。没有原理介绍,网上相关资料很多,有需求的童鞋可以自行查阅。欢迎大家讨论学习,希望对您有所帮助。

精进技术,与其死磕到底。