1. 全栈程序员必看首页

一致性Hash算法以及java实现「建议收藏」

全栈程序员-用户IM • • 未分类

一致性Hash算法以及java实现「建议收藏」目前我们很多时候都是在做分布式系统，但是我们需把客户端的请求均匀的分布到N个服务器中，一般我们可以考虑通过Object的HashCodeHash%N，通过取余，将客户端的请求分布到不同的的服务端。但是在分布式集群中我们通常需要添加或删除服务器，所以通过取余是不行的。一致性Hash就是为了解决这个问题。　　ConsistentHashing一致性Hash的原理　　1、环型Hash空间…

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

目前我们很多时候都是在做分布式系统，但是我们需把客户端的请求均匀的分布到N个服务器中，一般我们可以考虑通过Object的HashCodeHash%N，通过取余，将客户端的请求分布到不同的的服务端。但是在分布式集群中我们通常需要添加或删除服务器，所以通过取余是不行的。一致性Hash就是为了解决这个问题。

　　Consistent Hashing 一致性Hash的原理

　　1、环型Hash空间

　　根据常用的Hash，是将key哈希到一个长为2^32的桶中，即0～2^32-1的数字空间，最后通过首尾相连，我们可以想象成一个闭合的圆。如图：

　　一致性Hash算法以及java实现「建议收藏」

　　2、把数据通过一定的Hash算法处理后，映射到环上

　　例如：我们有Object1、Object2、Object3、Object4，通过Hash算法求出值如下：

　　　　Hash(Object1) = key1;

　　　　Hash(Object2) = key2;

　　　　Hash(Object3) = key3;

　　　　Hash(Object4) = key4;

　　一致性Hash算法以及java实现「建议收藏」

　　3、将机器信息通过hash算法映射到环上

　　　　一般情况下是对机器的信息通过计算hash，然后以顺时针方向计算，将对象信息存储在相应的位置。

　　　　一致性Hash算法以及java实现「建议收藏」

　　4、虚拟节点

　　　　上面是Hash算法的特性，但是Hash算法缺少一个平衡性。

　　　　Hash算法的平衡行就是为了尽可能使分配到每个数据桶里面的节点是均衡的，一个简单的例子：我们有3个分布式服务器，在大量客户端访问时，通过Hash算法，使得他们能在每个服务器均匀的访问。所以这里引入了“虚拟节点”节点，从而保证数据节点均衡。

　　　　“虚拟节点”就是真实节点的复制品，一个真实的节点对应多个“虚拟节点”，这样使得我们的节点能尽可能的在环形Hash空间均匀分布，这样我们再根据虚拟节点找到真实节点，从而保证每个真实节点上分配到的请求是均衡的。

　　　　一致性Hash算法以及java实现「建议收藏」

　　具体的代码实现如下：

import java.util.LinkedList;
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;

public class ConsistencyHashing {

    // 虚拟节点的个数
    private static final int VIRTUAL_NUM = 5;

    // 虚拟节点分配，key是hash值，value是虚拟节点服务器名称
    private static SortedMap<Integer, String> shards = new TreeMap<Integer, String>();

    // 真实节点列表
    private static List<String> realNodes = new LinkedList<String>();

    //模拟初始服务器
    private static String[] servers = { "192.168.1.1", "192.168.1.2", "192.168.1.3", "192.168.1.5", "192.168.1.6" };

    static {
        for (String server : servers) {
            realNodes.add(server);
            System.out.println("真实节点[" + server + "] 被添加");
            for (int i = 0; i < VIRTUAL_NUM; i++) {
                String virtualNode = server + "&&VN" + i;
                int hash = getHash(virtualNode);
                shards.put(hash, virtualNode);
                System.out.println("虚拟节点[" + virtualNode + "] hash:" + hash + "，被添加");
            }
        }
    }

    /**
     * 获取被分配的节点名
     * 
     * @param node
     * @return
     */
    public static String getServer(String node) {
        int hash = getHash(node);
        Integer key = null;
        SortedMap<Integer, String> subMap = shards.tailMap(hash);
        if (subMap.isEmpty()) {
            key = shards.lastKey();
        } else {
            key = subMap.firstKey();
        }
        String virtualNode = shards.get(key);
        return virtualNode.substring(0, virtualNode.indexOf("&&"));
    }

    /**
     * 添加节点
     * 
     * @param node
     */
    public static void addNode(String node) {
        if (!realNodes.contains(node)) {
            realNodes.add(node);
            System.out.println("真实节点[" + node + "] 上线添加");
            for (int i = 0; i < VIRTUAL_NUM; i++) {
                String virtualNode = node + "&&VN" + i;
                int hash = getHash(virtualNode);
                shards.put(hash, virtualNode);
                System.out.println("虚拟节点[" + virtualNode + "] hash:" + hash + "，被添加");
            }
        }
    }

    /**
     * 删除节点
     * 
     * @param node
     */
    public static void delNode(String node) {
        if (realNodes.contains(node)) {
            realNodes.remove(node);
            System.out.println("真实节点[" + node + "] 下线移除");
            for (int i = 0; i < VIRTUAL_NUM; i++) {
                String virtualNode = node + "&&VN" + i;
                int hash = getHash(virtualNode);
                shards.remove(hash);
                System.out.println("虚拟节点[" + virtualNode + "] hash:" + hash + "，被移除");
            }
        }
    }

    /**
     * FNV1_32_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;
    }

    public static void main(String[] args) {
        
        //模拟客户端的请求
        String[] nodes = { "127.0.0.1", "10.9.3.253", "192.168.10.1" };
        
        for (String node : nodes) {
            System.out.println("[" + node + "]的hash值为" + getHash(node) + ", 被路由到结点[" + getServer(node) + "]");
        }
        
        // 添加一个节点(模拟服务器上线)
        addNode("192.168.1.7");
        // 删除一个节点（模拟服务器下线）
        delNode("192.168.1.2");

        for (String node : nodes) {
            System.out.println("[" + node + "]的hash值为" + getHash(node) + ", 被路由到结点[" + getServer(node) + "]");
        }
    }
}

　测试结果：

　一致性Hash算法以及java实现「建议收藏」

　　从结果可以看出：服务器节点上线和下线并不会对我们服务有任何影响，除非所有的服务都下线。当之前映射的服务器下线，我们可以切换到和它Hash临近的服务节点上，保证服务的负载均衡。

       如果我们考虑每台服务器性能不一致，比如服务器内存有32G、16G、8G的，我们可以根据不同的服务器性能，分配不同的负载因子（就是上面程序的VIRTUAL_NUM）,这样我们是不是可以想到和Dubbo里面的负载因子是一致的。我们可以手动的调整每台服务器的负载因子，从而根据每个服务器性能，分配不同权重的客户端请求负载量 。

实现案例：

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;

public class ConsistencyHashingLoadFactor {

    // 真实节点列表
    private static List<Machine> realNodes = new ArrayList<Machine>();

    // 虚拟节点，key是Hash值，value是虚拟节点信息
    private static SortedMap<Integer, String> shards = new TreeMap<Integer, String>();

    static {
        realNodes.add(new Machine("192.168.1.1", LoadFactor.Memory8G));
        realNodes.add(new Machine("192.168.1.2", LoadFactor.Memory16G));
        realNodes.add(new Machine("192.168.1.3", LoadFactor.Memory32G));
        realNodes.add(new Machine("192.168.1.4", LoadFactor.Memory16G));
        for (Machine node : realNodes) {
            for (int i = 0; i < node.getMemory().getVrNum(); i++) {
                String server = node.getHost();
                String virtualNode = server + "&&VN" + i;
                int hash = getHash(virtualNode);
                shards.put(hash, virtualNode);
            }
        }
    }

    /**
     * 获取被分配的节点名
     * 
     * @param node
     * @return
     */
    public static Machine getServer(String node) {
        int hash = getHash(node);
        Integer key = null;
        SortedMap<Integer, String> subMap = shards.tailMap(hash);
        if (subMap.isEmpty()) {
            key = shards.lastKey();
        } else {
            key = subMap.firstKey();
        }
        String virtualNode = shards.get(key);
        String realNodeName = virtualNode.substring(0, virtualNode.indexOf("&&"));
        for (Machine machine : realNodes) {
            if (machine.getHost().equals(realNodeName)) {
                return machine;
            }
        }
        return null;
    }

    /**
     * 添加节点
     * 
     * @param node
     */
    public static void addNode(Machine node) {
        if (!realNodes.contains(node)) {
            realNodes.add(node);
            System.out.println("真实节点[" + node + "] 上线添加");
            for (int i = 0; i < node.getMemory().getVrNum(); i++) {
                String virtualNode = node.getHost() + "&&VN" + i;
                int hash = getHash(virtualNode);
                shards.put(hash, virtualNode);
                System.out.println("虚拟节点[" + virtualNode + "] hash:" + hash + "，被添加");
            }
        }
    }

    /**
     * 删除节点
     * 
     * @param node
     */
    public static void delNode(Machine node) {
        String host = node.getHost();
        Iterator<Machine> it = realNodes.iterator();
        while(it.hasNext()) {
            Machine machine = it.next();
            if(machine.getHost().equals(host)) {
                it.remove();
                System.out.println("真实节点[" + node + "] 下线移除");
                for (int i = 0; i < node.getMemory().getVrNum(); i++) {
                    String virtualNode = node.getHost() + "&&VN" + i;
                    int hash = getHash(virtualNode);
                    shards.remove(hash);
                    System.out.println("虚拟节点[" + virtualNode + "] hash:" + hash + "，被移除");
                }
            }
        }
    }

    /**
     * FNV1_32_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;
    }

    public static void main(String[] args) {

        // 模拟客户端的请求
        String[] nodes = { "127.0.0.1", "10.9.3.253", "192.168.10.1" };

        for (String node : nodes) {
            System.out.println("[" + node + "]的hash值为" + getHash(node) + ", 被路由到结点[" + getServer(node) + "]");
        }

        // 添加一个节点(模拟服务器上线)
        addNode(new Machine("192.168.1.7", LoadFactor.Memory16G));
        // 删除一个节点（模拟服务器下线）
        delNode(new Machine("192.168.1.1", LoadFactor.Memory8G));

        for (String node : nodes) {
            System.out.println("[" + node + "]的hash值为" + getHash(node) + ", 被路由到结点[" + getServer(node) + "]");
        }
    }
}

/**
 * 机器类
 * 
 * @author yangkuanjun
 *
 */
class Machine {

    private String host;

    private LoadFactor memory;

    public String getHost() {
        return host;
    }

    public void setHost(String host) {
        this.host = host;
    }

    public LoadFactor getMemory() {
        return memory;
    }

    public void setMemory(LoadFactor memory) {
        this.memory = memory;
    }

    public Machine(String host, LoadFactor memory) {
        super();
        this.host = host;
        this.memory = memory;
    }

    @Override
    public String toString() {
        return "Machine [host=" + host + ", memory=" + memory + "]";
    }
}

/**
 * 负载因子
 * 
 * @author yangkuanjun
 *
 */
enum LoadFactor {

    Memory8G(5), Memory16G(10), Memory32G(20);

    private int vrNum;

    private LoadFactor(int vrNum) {
        this.vrNum = vrNum;
    }

    public int getVrNum() {
        return vrNum;
    }

}

测试结果：

一致性Hash算法以及java实现「建议收藏」

　　从运行结果可以看出：负载因子较大的被分配的概率就越大。

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

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

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

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

赞 (0)
全栈程序员-用户IM全栈程序员-用户IM
0 0


相关推荐

  • Promise是什么？Promise怎么使用？回调地狱[通俗易懂]

    Promise是什么？Promise怎么使用？回调地狱[通俗易懂]

    Promise是什么？Promise怎么使用？回调地狱[通俗易懂]1、Promise的概念Promise是ES6提供的原生的类（构造函数），用来传递异步操作的消息。它代表了某个未来才会知道结果的事件（通常是一个异步操作）2、Promise的两个特点：1）、对象的状态不受外界影响。Promise有三种状态：Pending（进行中）、Resolved（已完成，又称Fulfilled）和Rejected（已失败）。2）、一旦状态改变，就不会再变状态改变，只有两种可能：从Pending变为Resolved和从Pending变为Reje

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年6月4日
  • c++多线程入门_c语言是单线程还是多线程

    c++多线程入门_c语言是单线程还是多线程

    c++多线程入门_c语言是单线程还是多线程多线程的优势线程创建更加快速线程间切换更加快速线程容易终止线程间通讯更快速C语言的多线程可以通过gcc编译器中的pthread实现。案例1:helloworld#include<stdio.h>#include<pthread.h>void*myfunc(void*args){printf(“helloworl…

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年10月21日
  • nmap命令大全[通俗易懂]

    nmap命令大全[通俗易懂]

    nmap命令大全[通俗易懂]扫描类型-sTTCPconnect()扫描：这是最基本的TCP扫描方式。connect()是一种系统调用，由操作系统提供，用来打开一个连接。如果目标端口有程序监听，connect()就会成功返回，否则这个端口是不可达的。这项技术最大的优点是，你勿需root权限。任何UNIX用户都可以自由使用这个系统调用。这种扫描很容易被检测到，在目标主机的日志中会记录大批的连接请求以及错误信息。-sSTCP同步扫描(TCPSYN)：因为不必全部打开一个TCP连接，所以这项技术通常称为半开扫描(half-ope

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年5月28日
  • idea2021永久激活注册码-激活码分享 idea

    idea2021永久激活注册码-激活码分享

    (idea2021永久激活注册码)最近有小伙伴私信我，问我这边有没有免费的intellijIdea的激活码，然后我将全栈君台教程分享给他了。激活成功之后他一直表示感谢，哈哈~IntelliJ2021最新激活注册码，破解教程可免费永久激活，亲测有效，下面是详细链接哦~https://javaforall.cn/100143.html…

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年3月28日
  • java 反编译器_JAVA编译器

    java 反编译器_JAVA编译器

    java 反编译器_JAVA编译器xjad反编译工具下载使用反编译时把class文件直接拖拽至工具内即可，如果反编译结果不对时把class文件重新去拿原始的不要编辑打开，或者放在一个文件夹内在试。反编译后的代码没有注释、注解等，反正能用得细心看看调整。点击下载工具http://a.xzfile.com/down2/XJadfanbinayi_downcc.zip…

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年8月19日
  • 利用JS跨域做一个简单的页面訪问统计系统

    利用JS跨域做一个简单的页面訪问统计系统

    利用JS跨域做一个简单的页面訪问统计系统

    全栈程序员-用户IM 全栈程序员-用户IM
    2021年12月8日

发表回复

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

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