一致性hash算法

标签: hash  算法

散列(hash)在我看来就是一个数组,而与数组不同的点在于数组是按顺序写入的,而hash是按照一定的hash算法确定元素在数组中的位置的。hash最难的问题在于会有冲突出现,如果两个object根据相应的hash算法得出的值一样便产生了hash冲突。在所有解决hash冲突的方法中,我最欣赏的是链式解决法,即将hash到同一位置的元素用链表连接。当然还有其它几种处理hash冲突的算法,比如建立公共溢出区间、开放地址法(往前一个位置或者后一个位置添加)、再hash法。在jdk1.8的ConcurrentHashMap中处理hash冲突的算法应该是非常经典的了。首先首先链式存储法,当链式存储法存储数据超过一定阈值后将数据转为红黑树存储。有兴趣可以去看看源码哦!

以上讲的hash是将顺序存储的数组。而一致性hash算法将数组首尾相连,构成一个环向数组。那么环向数组有什么好处呢?一致性hash算法目前用处最大的地方在于分布式服务或者存储。假设在一个环山均匀分布着若干个点,这些点分别映射相应的服务器,那么当一个请求过来时,根据相应的key值总能将请求映射到环上,而我们按照一定的顺序,将被映射到环上的请求匹配一个服务进行处理,这样便达成了分布式的运算处理。如图,我们顺时针处理的话,就是第四个节点处理key的请求了。

这里写图片描述

以上一致性hash的实现只满足了单调性与负载均衡和一般hash算法具备的分散性特征,但缺少了平衡性,因此不足以被大规模集群利用。而在对一致性hash加入了虚拟节点后,便较好的解决此类问题。所谓虚拟节点是指节点指向的机器只是一个位置,而在该位置上可以拥有多台真实机器,具体选择那一台机器就看算法如何实现了。虚拟节点可以让一台机器对应多个虚拟节点,也可以让一个虚拟节点对应多个机器。这样多对多的一种实现,可以较大程度的保证平衡性。

这里写图片描述

基本原理讲明白了,我们试着用java实现一个简单的一致性hash。

import java.nio.ByteBuffer;
import java.nio.ByteOrder;
import java.util.ArrayList;
import java.util.List;
import java.util.Map.Entry;
import java.util.TreeMap;

public class ConsistantHash {

    private final int NUMBER = 15;

    TreeMap<Long, Node> treemap = new TreeMap<Long, Node>();

    public static ConsistantHash getInstance(){

        return InstanceHolder.consistantHash;
    }

    public Machine chooseMachine(String key) {

        Entry<Long, Node> en = treemap.ceilingEntry(hash(key));
        if(en == null) {

            System.out.print("Virtual Machine " + treemap.firstEntry().getKey() + " dealing with job " );
            return treemap.firstEntry().getValue().chooseMachine(key);
        }
        long sequence = treemap.tailMap(hash(key)).firstKey();
        Node node = treemap.get(sequence);
        System.out.print("Virtual Machine " + sequence + " dealing with job " );
        return node.chooseMachine(key); 
    }

    public void addMachine(final String ip, final String name) {

        Machine m = new Machine(ip, name);
        if(treemap.containsKey(hash(m.toString()))) {

            treemap.get(hash(m.toString())).addMachine(m);

        } else {

            Node nodes = new Node();
            nodes.addMachine(m);
            treemap.put(hash(m.toString()), nodes);
        }
    }

    private long hash(String key) {

        ByteBuffer buf = ByteBuffer.wrap(key.getBytes());  
        int seed = 0x1234ABCD;  

        ByteOrder byteOrder = buf.order();  
        buf.order(ByteOrder.LITTLE_ENDIAN);  

        long m = 0xc6a4a7935bd1e995L;  
        int r = 47;  

        long h = seed ^ (buf.remaining() * m);  

        long k;  
        while (buf.remaining() >= 8) {  
            k = buf.getLong();  

            k *= m;  
            k ^= k >>> r;  
            k *= m;  

            h ^= k;  
            h *= m;  
        }  

        if (buf.remaining() > 0) {  
            ByteBuffer finish = ByteBuffer.allocate(8).order(ByteOrder.LITTLE_ENDIAN);  
            // for big-endian version, do this first:  
            // finish.position(8-buf.remaining());  
            finish.put(buf).rewind();  
            h ^= finish.getLong();  
            h *= m;  
        }  

        h ^= h >>> r;  
        h *= m;  
        h ^= h >>> r;  

        buf.order(byteOrder);  
        return h & NUMBER;  

    }

    static class InstanceHolder{

        final static ConsistantHash consistantHash = new ConsistantHash();
    }

    class Node{

        List<Machine> machine = new ArrayList<Machine>();

        public void addMachine(Machine m) {

            machine.add(m);
        }

        public Machine chooseMachine(String key){

            return machine.get((int) (hash(key) & (machine.size() - 1)));
        }

        public String toString(){

            StringBuilder sb = new StringBuilder();
            machine.forEach(v->sb.append(v.toString()));
            return sb.toString();
        }
    }

    final class Machine{

        final String ip;
        final String name;

        public Machine(String ip, String name) {
            super();
            this.ip = ip;
            this.name = name;
        }
        public String getIp() {
            return ip;
        }
        public String getName() {
            return name;
        }

        @Override
        public int hashCode() {

            return this.toString().hashCode();
        }

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

结果展示
Virtual Machine 13 dealing with job Machine [ip=192.168.185.69, name=machine69]
Virtual Machine 8 dealing with job Machine [ip=192.168.185.64, name=machine64]
Virtual Machine 2 dealing with job Machine [ip=192.168.185.60, name=machine60]
Virtual Machine 13 dealing with job Machine [ip=192.168.185.69, name=machine69]
Virtual Machine 15 dealing with job Machine [ip=192.168.185.68, name=machine68]
Virtual Machine 1 dealing with job Machine [ip=192.168.185.62, name=machine62]
Virtual Machine 8 dealing with job Machine [ip=192.168.185.64, name=machine64]
Virtual Machine 1 dealing with job Machine [ip=192.168.185.62, name=machine62]
Virtual Machine 8 dealing with job Machine [ip=192.168.185.64, name=machine64]
Virtual Machine 15 dealing with job Machine [ip=192.168.185.68, name=machine68]

实验结果看出,可以实现一定的平衡性,不过还是有很多节点没有用到,应该是测试数量的问题。不过这里的代码存在的另一个问题是虚拟节点内部没有实现。这个问题有待继续思考。

版权声明:本文为u013735511原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/u013735511/article/details/71109442

智能推荐

php输出语句

php输出语句 常见的输出语句 echo(): 可以一次输出多个值,多个值之间用逗号分隔。echo是语言结构(language construct),而并不是真正的函数,因此不能作为表达式的一部分使用。 print(): 函数print()打印一个值(它的参数),如果字符串成功显示则返回true,否则返回false。 print_r(): 可以把字符串和数字简单地打印出来,而数组则以括起来的键和值...

工厂模式

简介 常见的实例化对象模式。 用工厂方法替代new操作的一种模式。 当我们使用new操作实例化对象时,调用构造函数完成初始化。若初始化仅是进行赋值等简单的操作,写入构造函数即可。但如果初始化时需要执行一长串复杂的代码,将多个工作装入一个方法,是不妥的。 创建实例与使用实例分离。将创建实例所需的大量初始化工作从基类的构造函数中分离出去。 简单工厂模式、工厂方法模式针对的是一个产品等级结构;而抽象工厂...

B1105 Spiral Matrix (画图)

B1105 Spiral Matrix (25分) //第一次只拿了21分 矩阵的长和宽,求最大因子,从sqrt(num)开始枚举. 每次循环一次,s++,t--,d--,r++ 测试点四运行超时,是因为输入一个数字的时候,需要直接输出这个数字。//1分 测试点二运行超时,最后一个数字不必再while循环一次,直接输出即可。//3分 最后一个测试点卡了好久/(ㄒoㄒ)/~~ 螺旋矩阵...

Java基础=>String,StringBuffer与StringBuilder的区别

字符串常量池 什么是字符串常量池? JVM为了减少字符串对象的重复创建,其维护了一块特殊的内存,这段内存被称为字符串常量池(存储在方法区中)。 具体实现 当代码中出现字符串时,JVM首先会对其进行检查。 如果字符串常量池中存在相同内容的字符串对象,如果有,则不再创建,直接返回这个对象的地址返回。 如果字符串常量池中不存在相同内容的字符串对象,则创建一个新的字符串对象并放入常量池,并返回新创建的字符...

java调用其他java项目的Https接口

项目中是这样的: 用户拿出二维码展示,让机器识别二维码, 机器调用开门的后台系统接口, 然后开门的后台系统接口需要调用管理系统的接口, 管理系统需要判断能不能开门.这两个系统是互相独立的.当时使用http调用是没有问题的.当时后来要求必须用https.废话不说,直接代码: 我的项目中调用的是 HttpsUtils.Get(utlStr) 这个接口 开门系统接口如下图:   管理系统的接口...

猜你喜欢

Hadoop1.2.1全分布式模式配置

一 集群规划 主机名            IP                               安装的软件 &nbs...

Go语言gin框架的安装

尝试安装了一下gin,把遇到的一些小问题来记录一下 安装步骤 首先来看看官方文档,链接点这里 可以看到安装步骤很简单,就一句话 在命令行中输入这句话运行等待就好。 问题来了,因为墙的问题,go get会很慢,所以命令行里面半天什么反应也没有,不要急,慢慢等着就会看到gin-gonic/gin这个目录出现 这个时候命令行还是没有结束,表示还在下一些东西。有的时候可能心急的人就停了(比如我),然后写个...

uni-app表单组件二

input(输入框) 属性名 类型 说明 平台差异 value String 输入框的初始内容 type String input 的类型 password Boolean(默认false) 是否是密码类型 placeholder String 输入框为空时占位符 placeholder-style String 指定 placeholder 的样式 placeholder-class Strin...

深入理解 JavaScript 代码执行机制

深入理解 JavaScript 代码执行机制 前言 本文仅为个人见解,如有错误的地方欢迎留言区探讨和指正。 1、餐前甜品 如下是一段 JavaScript 代码,如果你毫不犹豫的说出代码执行顺序。那么请直接滚动到底部,留下你的足迹,接受膜拜。如果还不是很确定,那么请往下继续查看。 2、磨刀不误砍柴工(了解浏览器原理) (1) 进程和线程 进程是cpu资源分配的最小单位(是能拥有资源和独立运行的最小...

Centos7下配置DRBD Cluster扩展节点

操作环境 CentOS Linux release 7.4.1708 (Core) DRBDADM_BUILDTAG=GIT-hash:\ ee126652638328b55dc6bff47d07d6161ab768db\ build\ by\ [email protected]\,\ 2018-07-30\ 22:23:07 DRBDADM_API_VERSION=2 DRBD_KERNEL_VER...