栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

一致性hash算法Java实现

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

一致性hash算法Java实现

文章目录
  • 前言
  • 一、一致性hash是什么?
  • 二、构思
    • 1.通过测试来实现代码
    • 2.具体实现
    • 3.编写测试类
    • 4.分析测试结果
  • 总结


前言

因为项目上使用websocket时,session不能进行序列化,导致无法解决集群问题。所以考虑使用广播或者一致性hash来解决问题(最终还是选择通过mq广播,因为比较简单)。搜索很多帖子后发现很多博主实现的一致性hash算法,没有测试用例或者直接不能使用


一、一致性hash是什么?

详细解释不再赘述,网上特别多。简单理解就是集群情况下,增加或减少服务节点,最大限度的保证客户端访问的服务器不发生改变

二、构思 1.通过测试来实现代码

我们需要实现的功能

// 通过客户端IP获取调用到的服务器IP
private static void getServerIp(String clientIp) {
}
// 注册添加新的服务端IP
private static void registerServer(String serverIp) {
}
// 下线指定的服务器IP
private static void removeServer(String serverIp) {
}
2.具体实现

我们这里封装一个ConsistentHash对象来处理3个方法

import java.util.*;

public class ConsistentHash {
    // 虚拟节点数默认100,构建时可传参修改
    private int virtualNum = 100;
    // 物理节点集合,方便后续判断是否已经注册
    private final Set realNodes = new HashSet<>();
    // 物理节点与虚拟节点的对应关系存储(方便移除或下线服务器)
    private final Map> real2VirtualMap = new HashMap<>();
    // 排序存储结构红黑树,key是虚拟节点的hash值,value是物理节点
    private final SortedMap sortedMap = new TreeMap<>();

    public ConsistentHash() {
    }

    public ConsistentHash(int virtualNum) {
        this.virtualNum = virtualNum;
    }

    public void registerServer(String serverIp) {
        if(realNodes.contains(serverIp)){
            return;
        }
        realNodes.add(serverIp);
        // 根据物理节点生成指定个虚拟节点
        int i = 0;
        List virtualNodeList = new ArrayList<>();
        while (i < virtualNum) {
            String virtualName = serverIp + "-" + i;
            int hash = FNV1_32_HASH.getHash(virtualName);
            if (!sortedMap.containsKey(hash)) {
                this.sortedMap.put(hash, serverIp);
                virtualNodeList.add(hash);
                i++;
            }
        }
        // 物理节点与虚拟节点的对应关系存储(方便移除服务器)
        real2VirtualMap.put(serverIp, virtualNodeList);
    }

    public String getServerIpByClientIp(String clientIp) {
        int hash = FNV1_32_HASH.getHash(clientIp);
        SortedMap currentSortedMap = this.sortedMap.tailMap(hash);
        // 最后一个元素,返回第一个node
        if (currentSortedMap.isEmpty()) {
            return sortedMap.get(sortedMap.firstKey());
        }
        return currentSortedMap.get(currentSortedMap.firstKey());
    }

    public void removeServer(String serverIp) {
        realNodes.remove(serverIp);
        List keys = real2VirtualMap.get(serverIp);
        for (Integer key : keys) {
            sortedMap.remove(key);
        }
        real2VirtualMap.remove(serverIp);
    }
}

这个是里面用到的32位hash算法(复制来的)

public class FNV1_32_HASH {
    public 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;
    }
}
3.编写测试类

因为考虑到连接服务器数量过小的话,没有可比性,所以测试类上也花了一些功夫

package com.hjrpc;

import java.util.*;

public class TestMain {
    // 一致性hash对象
    private static final ConsistentHash consistentHash = new ConsistentHash();
    // 随机对象,方便后续生成随机IP
    private static final Random random = new Random();
    // 避免随机生成重复的IP
    private static final Set existIp = new HashSet<>();
    // 服务端IP前缀
    private static final String serverIpPrefix = "192.168.56.";
    // 客户端IP前缀
    private static final String clientIpPrefix = "192.168.1.";
    // 随机生成的服务端IP
    private static final List serverIps = getBatchRandomIps(5, serverIpPrefix);
    // 随机生成的客户端IP
    private static final List clientIps = getBatchRandomIps(20, clientIpPrefix);
    // 待打印的结果
    private static final Map printMap = new TreeMap<>();
    // 记录新增加的IP(方便打印)
    private static String newIp;
    // 记录移除的IP(方便打印)
    private static String removeIp;

    public static void main(String[] args) {
        // 注册所有服务
        serverIps.forEach(TestMain::registerServer);
        // 批量测试客户端获取IP
        batchTestClientGetAndPrint();
        // 重新获取2个IP进行注册
        getBatchRandomIps(1, serverIpPrefix).forEach(x -> {
            newIp = x;
            registerServer(x);
        });
        // 批量测试客户端获取IP
        batchTestClientGetAndPrint();
        // 随机下线2个IP并打印
        removeServer(1);
        // 批量测试客户端获取IP
        batchTestClientGetAndPrint();
        // 打印结果
        printResult();
    }

    private static void printResult() {
        System.out.println("     客户端IP                服务端IP         add[" + String.format("%-14s", newIp)
                + "]    remove[" + String.format("%-14s", removeIp) + "]");
        printMap.values().forEach(System.out::println);
    }

    private static List getBatchRandomIps(Integer num, String ipPrefix) {
        List ips = new ArrayList<>();
        int i = 1;
        while (i <= num) {
            int randomCode = random.nextInt(255) + 1;
            if (!existIp.contains(randomCode)) {
                String ipString = ipPrefix + randomCode;
                ips.add(ipString);
                existIp.add(randomCode);
                i++;
            }
        }
        return ips;
    }

    private static void getAndPrintIp(String clientIp) {
        String serverIpByClientIp = consistentHash.getServerIpByClientIp(clientIp);
        String printStr = printMap.get(clientIp);
        if (printStr == null) {
            printStr = "[" + String.format("%-13s", clientIp) + "]  ===>  [" + String.format("%-14s", serverIpByClientIp) + "]";
        } else {
            printStr += "  ===>  [" + String.format("%-14s", serverIpByClientIp) + "]";
        }
        printMap.put(clientIp, printStr);
    }

    private static void registerServer(String serverIp) {
        consistentHash.registerServer(serverIp);
    }


    private static void removeServer(int num) {
        for (int i = 0; i < num; i++) {
            String serverIp = serverIps.get(random.nextInt(serverIps.size()));
            consistentHash.removeServer(serverIp);
            removeIp = serverIp;
        }
    }

    private static void batchTestClientGetAndPrint() {
        clientIps.forEach(TestMain::getAndPrintIp);
    }
}


4.分析测试结果
     客户端IP                服务端IP         add[192.168.56.193]    remove[192.168.56.124]
[192.168.1.112]  ===>  [192.168.56.65 ]  ===>  [192.168.56.65 ]  ===>  [192.168.56.65 ]
[192.168.1.14 ]  ===>  [192.168.56.62 ]  ===>  [192.168.56.62 ]  ===>  [192.168.56.62 ]
[192.168.1.154]  ===>  [192.168.56.65 ]  ===>  [192.168.56.65 ]  ===>  [192.168.56.65 ]
[192.168.1.160]  ===>  [192.168.56.113]  ===>  [192.168.56.113]  ===>  [192.168.56.113]
[192.168.1.162]  ===>  [192.168.56.62 ]  ===>  [192.168.56.62 ]  ===>  [192.168.56.62 ]
[192.168.1.172]  ===>  [192.168.56.130]  ===>  [192.168.56.130]  ===>  [192.168.56.130]
[192.168.1.176]  ===>  [192.168.56.62 ]  ===>  [192.168.56.62 ]  ===>  [192.168.56.62 ]
[192.168.1.180]  ===>  [192.168.56.130]  ===>  [192.168.56.130]  ===>  [192.168.56.130]
[192.168.1.219]  ===>  [192.168.56.62 ]  ===>  [192.168.56.62 ]  ===>  [192.168.56.62 ]
[192.168.1.223]  ===>  [192.168.56.65 ]  ===>  [192.168.56.193]  ===>  [192.168.56.193]
[192.168.1.229]  ===>  [192.168.56.65 ]  ===>  [192.168.56.65 ]  ===>  [192.168.56.65 ]
[192.168.1.243]  ===>  [192.168.56.124]  ===>  [192.168.56.124]  ===>  [192.168.56.193]
[192.168.1.245]  ===>  [192.168.56.130]  ===>  [192.168.56.130]  ===>  [192.168.56.130]
[192.168.1.35 ]  ===>  [192.168.56.113]  ===>  [192.168.56.113]  ===>  [192.168.56.113]
[192.168.1.38 ]  ===>  [192.168.56.65 ]  ===>  [192.168.56.65 ]  ===>  [192.168.56.65 ]
[192.168.1.64 ]  ===>  [192.168.56.130]  ===>  [192.168.56.130]  ===>  [192.168.56.130]
[192.168.1.75 ]  ===>  [192.168.56.113]  ===>  [192.168.56.113]  ===>  [192.168.56.113]
[192.168.1.91 ]  ===>  [192.168.56.65 ]  ===>  [192.168.56.193]  ===>  [192.168.56.193]
[192.168.1.96 ]  ===>  [192.168.56.62 ]  ===>  [192.168.56.62 ]  ===>  [192.168.56.62 ]
[192.168.1.98 ]  ===>  [192.168.56.62 ]  ===>  [192.168.56.193]  ===>  [192.168.56.193]
  • 新增IP:192.168.56.193后只有3台服务器调用发生变化
  • 删除IP:192.168.56.124后只有1台服务调用发生变化

总结

博主第一次写,如有不正确的地方,欢迎指出问题

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/979431.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号