澳门新浦京娱乐游戏Java实现一致性Hash算法深入研究

澳门新浦京娱乐游戏 2

一致性Hash算法

至于一致性Hash算法,在笔者事情发生以前的博文中早就有多次关联了,MemCache超详细解读一文中”一致性Hash算法”部分,对于怎么要选拔一致性Hash算法和一致性Hash算法的算法原理做了详细的解读。

算法的切实原理这里再次贴上:

先构造二个长短为2 32
的整数环(那么些环被叫做一致性Hash环),依照节点名称的Hash值(其布满为[0,
2 32
-1])将服务器节点放置在此个Hash环上,然后依照数量的Key值总括得到其Hash值(其遍及也为[0,
2 32
-1]澳门新浦京娱乐游戏,),接着在Hash环上顺时针查找间距那一个Key值的Hash值方今的服务器节点,完毕Key到服务器的映射查找。

这种算法消除了常常余数Hash算法伸缩性差的题材,可以保险在上线、下线服务器的气象下全力以赴有多的央浼命中原本路由到的服务器。

人之常情,万事不恐怕白玉无瑕,一致性Hash算法比日常Hash算法更具有伸缩性,不过还要其算法达成也更是复杂,本文就来商量一下,怎么样运用Java代码达成一致性Hash算法。在始发早先,先对一致性Hash算法中的多少个中央难点进行部分商量。

数据布局的接受

一致性Hash算法最早要思谋的叁个标题是:布局出一个长短为2 32
的莫西干发型环,依照节点名称的Hash值将服务器节点放置在这里个Hash环上。

那么,整数环应该使用何种数据布局,技能使得运维时的时光复杂度最低?首先说惠氏(WYETH卡塔尔国(Karicare卡塔尔国些,关于时间复杂度,
听而不闻的年华复杂度与时光成效的涉嫌有如下的经历法规:

O(1) < O(log 2 N) < O(n) < O(N * log 2
N) < O(N 2 ) < O(N 3 ) < 2N < 3N <
N!

貌似的话,前两个效能相比较高,中间多少个救经引足,后多个很糟糕(只要N相当的大,这一个算法就动不了了)。OK,继续后边的话题,应该怎么着选拔数据构造,作者感到有以下二种有效的缓慢解决方案。

1、设计方案一:排序+List

自己想开的第一种思路是:算出全体待参与数据布局的节点名称的Hash值纳入三个数组中,然后利用某种排序算法将其从小到大进展排序,最终将排序后的数量放入List中,选取List并非数组是为着结点的强盛考虑。

其后,待路由的结点,只需求在List中找到第叁个Hash值比它大的服务器节点就足以了
,比方服务器节点的Hash值是[0,2,4,6,8,10],带路由的结点是7,只需求找到第三个比7大的整数,约等于8,正是我们最后要求路由过去的服务器节点。

假诺权且不思谋后面包车型地铁排序,那么这种技术方案的光阴复杂度:

(1)最佳的情况是首先次就找到,时间复杂度为O(1卡塔尔

(2)最坏的情形是最后叁次才找到,时间复杂度为O(N卡塔尔

平均下来时间复杂度为O(0.5N+0.5卡塔尔(قطر‎,忽视首项周详和常数,时间复杂度为O(N卡塔尔(قطر‎。

然则要是伪造到事情发生前的排序,笔者在英特网找了张图,提供了各样排序算法的时辰复杂度:

澳门新浦京娱乐游戏 1

看得出来,排序算法要么牢固不过日子复杂度高、要么时间复杂度低但不安宁,看起来最棒的联结排序法的时光复杂度依然有O(N
* logN卡塔尔,微微花费质量了部分。

2、建设方案二:遍历+List

既是排序操作比较耗质量,那么能还是一定要排序?能够的,所以越来越,有了第二种缓慢解决方案。

建设方案使用List不改变,可是能够应用遍历的艺术:

(1)服务器节点不排序,其Hash值全体一向归入一个List中

(2)带路由的节点,算出其Hash值,由于指明了”顺时针”,因而遍历List,比待路由的节点Hash值大的算出差值并记下,比待路由节点Hash值小的不经意

(3)算出装有的差值之后,最小的足够,正是最后须要路由过去的节点

在这里个算法中,看一下岁月复杂度:

1、最棒状态是只有三个服务器节点的Hash值大于带路由结点的Hash值,其时间复杂度是O(N卡塔尔(قطر‎+O(1State of Qatar=O(N+1卡塔尔,忽视常数项,即O(NState of Qatar

2、最坏情状是颇负服务器节点的Hash值都不唯有带路由结点的Hash值,其时间复杂度是O(N卡塔尔国+O(N卡塔尔(قطر‎=O(2NState of Qatar,忽视首项全面,即O(N卡塔尔

所以,总的时间复杂度就是O(NState of Qatar。其实算法仍为能够更加精雕细琢一些:给三个职责变量X,若是新的差值比原差值小,X替换为新的职位,不然X不改变。那样遍历就缩短了一轮,可是经过更正后的算法时间复杂度仍是O(N卡塔尔(قطر‎。

简单来讲,这些技术方案和消除方案一相对来讲,总体来看,就如更加好了一部分。

3、施工方案三:二叉查找树

抛开List这种数据布局,另一种数据构造则是运用 二叉查找树
。对于树不是很清楚的相爱的人能够简轻易单看一下这篇随笔树形构造。

人之常情咱们必须要难地使用二叉查找树,因为恐怕现身不平衡的情况。平衡二叉查找树有AVL树、红黑树等,这里运用红黑树,采用红黑树的由来有两点:

1、红黑树重要的功力是用以存款和储蓄有序的数目,那实则和率先种缓慢解决方案的思绪又不期而同了,不过它的频率超级高

2、JDK里面提供了红黑树的代码达成TreeMap和TreeSet

别的,以TreeMap为例,TreeMap自身提供了几个tailMap(K
fromKey卡塔尔(قطر‎方法,援救从红黑树中摸SobifromKey大的值的会面,但并没有必要遍历整个数据构造。

使用红黑树,能够使得寻找的小运复杂度收缩为O(logN卡塔尔,比地点三种减轻方案,效能大大提高。

为了求证这么些说法,小编做了二次测量试验,从大批量数量中追寻第叁个超越此中间值的不胜数据,比方10000数目就找第四个超越5000的数据(模拟平均的情形)。看一下O(NState of Qatar时间复杂度和O(logNState of Qatar时间复杂度运维功用的自己检查自纠:

50000 100000 500000 1000000 4000000
ArrayList 1ms 1ms 4ms 4ms 5ms
LinkedList 4ms 7ms 11ms 13ms 17ms
TreeMap 0ms 0ms 0ms 0ms 0ms

因为再大就内存溢出了,所以只测量试验到4000000数据。能够见到,数据检索的频率,TreeMap是大捷的,其实再附加数据测量检验也是同样的,红黑树的数据构造决定了别的二个抢先N的眇小数据,它都只须要两回至几十遍搜索就足以查到。

当然,分明一点,有利必有弊,根据本人其余三次测验获得的结论是,
为了保险红黑树,数据插入作用TreeMap在两种数据结构里面是最差的,且插入要慢上5~10倍

Hash值重新总结

服务器节点大家必然用字符串来代表,比方”192.168.1.1″、”192.168.1.2″,依照字符串获得其Hash值,那么其余四位命关天的主题材料就是Hash值要重复总括,那么些标题是本身在测量试验String的hashCode(State of Qatar方法的时候开掘的,无妨来看一下为什么要再一次总结Hash值:

/**
 * String的hashCode()方法运算结果查看
 * @author 五月的仓颉 http://www.cnblogs.com/xrq730/
 *
 */
public class StringHashCodeTest
{
    public static void main(String[] args)
    {
        System.out.println("192.168.0.0:111的哈希值:" + "192.168.0.0:1111".hashCode());
        System.out.println("192.168.0.1:111的哈希值:" + "192.168.0.1:1111".hashCode());
        System.out.println("192.168.0.2:111的哈希值:" + "192.168.0.2:1111".hashCode());
        System.out.println("192.168.0.3:111的哈希值:" + "192.168.0.3:1111".hashCode());
        System.out.println("192.168.0.4:111的哈希值:" + "192.168.0.4:1111".hashCode());
    }
}

我们在做集群的时候,集群点的IP以这种连接的款式存在是很平常的。看一下一周转结果为:

192.168.0.0:111的哈希值:1845870087
192.168.0.1:111的哈希值:1874499238
192.168.0.2:111的哈希值:1903128389
192.168.0.3:111的哈希值:1931757540
192.168.0.4:111的哈希值:1960386691

其一就难点大了,[0,2 32
-1]的间距之中,5个HashCode值却只布满在此么小小的三个间隔,什么概念?[0,2
32
-1]中有4294967297个数字,而大家的间隔唯有122516605,从概率学上讲那将产生97%待路由的服务器都被路由到”192.168.0.1″这一个集群点上,简直是糟糕透了!

除此以外还会有贰个不好的地点:规定的间隔是非负数,String的hashCode(State of Qatar方法却会时有产生负数(不相信用”192.168.1.0:1111″试试看就理解了)。可是这一个难题好化解,取相对值就是一种缓慢解决的主意。

综上,String重写的hashCode(State of Qatar方法在一致性Hash算法中绝非其它实用价值,得找个算法重新总计HashCode。这种重新计算Hash值的算法有相当多,比如CRC32_HASH、FNV1_32_HASH、KETAMA_HASH等,其中KETAMA_HASH是暗中同意的MemCache推荐的一致性Hash算法,用其余Hash算法也可以,例如FNV1_32_HASH算法的思忖效用就能高级中学一年级些。

一致性Hash算法实现版本1:不带设想节点

采用一致性Hash算法,即使增加了系统的紧缩性,可是也会有比异常的大可能率诱致负载遍布不均匀,消除办法正是利用
虚构节点代替真实节点 ,第二个代码版本,先来个大概的,不带虚构节点。

下边来看一下不带设想节点的一致性Hash算法的Java代码完毕:

/**
 * 不带虚拟节点的一致性Hash算法
 * @author 五月的仓颉http://www.cnblogs.com/xrq730/
 *
 */
public class ConsistentHashingWithoutVirtualNode
{
    /**
     * 待添加入Hash环的服务器列表
     */
    private static String[] servers = {"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111",
            "192.168.0.3:111", "192.168.0.4:111"};

    /**
     * key表示服务器的hash值,value表示服务器的名称
     */
    private static SortedMap<Integer, String> sortedMap = 
            new TreeMap<Integer, String>();

    /**
     * 程序初始化,将所有的服务器放入sortedMap中
     */
    static
    {
        for (int i = 0; i < servers.length; i++)
        {
            int hash = getHash(servers[i]);
            System.out.println("[" + servers[i] + "]加入集合中, 其Hash值为" + hash);
            sortedMap.put(hash, servers[i]);
        }
        System.out.println();
    }

    /**
     * 使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法,最终效果没区别 
     */
    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;
    }

    /**
     * 得到应当路由到的结点
     */
    private static String getServer(String node)
    {
        // 得到带路由的结点的Hash值
        int hash = getHash(node);
        // 得到大于该Hash值的所有Map
        SortedMap<Integer, String> subMap = 
                sortedMap.tailMap(hash);
        // 第一个Key就是顺时针过去离node最近的那个结点
        Integer i = subMap.firstKey();
        // 返回对应的服务器名称
        return subMap.get(i);
    }

    public static void main(String[] args)
    {
        String[] nodes = {"127.0.0.1:1111", "221.226.0.1:2222", "10.211.0.1:3333"};
        for (int i = 0; i < nodes.length; i++)
            System.out.println("[" + nodes[i] + "]的hash值为" + 
                    getHash(nodes[i]) + ", 被路由到结点[" + getServer(nodes[i]) + "]");
    }
}

可以运营一下看一下结果:

[192.168.0.0:111]加入集合中, 其Hash值为575774686
[192.168.0.1:111]加入集合中, 其Hash值为8518713
[192.168.0.2:111]加入集合中, 其Hash值为1361847097
[192.168.0.3:111]加入集合中, 其Hash值为1171828661
[192.168.0.4:111]加入集合中, 其Hash值为1764547046

[127.0.0.1:1111]的hash值为380278925, 被路由到结点[192.168.0.0:111]
[221.226.0.1:2222]的hash值为1493545632, 被路由到结点[192.168.0.4:111]
[10.211.0.1:3333]的hash值为1393836017, 被路由到结点[192.168.0.4:111]

看样子经过FNV1_32_HASH算法重新总括过后的Hash值,就比原本String的hashCode(State of Qatar方法好些个了。从运营结果来看,也从未难点,四个点路由到的都以顺时针离他们Hash值方今的那台服务器上。

利用虚构节点来修改一致性Hash算法

上面包车型客车一致性Hash算法完结,能够在一点都不小程度上减轻广大分布式情状下不好的路由算法招致系统伸缩性差的主题材料,可是会带给别的二个标题:负载不均。

譬喻有Hash环上有A、B、C多少个服务器节点,分别有九十多个央浼会被路由到对应服务器上。未来在A与B之间增添了二个节点D,那变成了原先会路由到B上的局地节点被路由到了D上,这样A、C上被路由到的伸手显著多于B、D上的,原本多个服务器节点上人均的载荷被打破了。
某种程度上来讲,那失去了负载均衡的意义,因为负载均衡的目标本身正是为着使得指标服务器均分所有的伸手

缓和那一个题指标不二等秘书技是引进设想节点,其行事原理是:
将四个大要节点拆分为多个虚构节点,並且同一个物理节点的虚拟节点尽量均匀分布在Hash环上
。采用如此的办法,就能够使得地缓解增加或收缩节点时候的负载不平均的标题。

有关叁个物理节点应该拆分为多少虚构节点,上边能够先看一张图:

澳门新浦京娱乐游戏 2

横轴表示需求为每台便利服务器扩张的杜撰节点倍数,纵轴代表的是实际上物理服务器数。能够看出,物理服务器比很少,供给越来越大的诬捏节点;反之物理服务器超级多,虚构节点就可以少一些。举例有10台物理服务器,那么基本上须求为每台服务器增添100~200个设想节点才足以达到确实的载重均衡。

一致性Hash算法实现版本2:带设想节点

在知情了接纳虚构节点来改过一致性Hash算法的理论底工之后,就能够尝尝开辟代码了。编制程序方面须要构思的题目是:

1、八个忠厚结点如何对应改为多个设想节点?

2、虚构节点找到后什么还原为真实结点?

那多个难点实际上有好多消除办法,笔者那边运用了一种简易的点子,给各类真实结点前边根据虚构节点加上后缀再取Hash值,比如”192.168.0.0:111″就把它形成”192.168.0.0:111&&VN0″到”192.168.0.0:111&&VN4″,VN正是Virtual
Node的缩写,还原的时候只须要起先截取字符串到”&&”的岗位就能够了。

上面来看一下带虚构节点的一致性Hash算法的Java代码落成:

/**
 * 带虚拟节点的一致性Hash算法
 * @author 五月的仓颉 http://www.cnblogs.com/xrq730/
 */
public class ConsistentHashingWithVirtualNode
{
    /**
     * 待添加入Hash环的服务器列表
     */
    private static String[] servers = {"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111",
            "192.168.0.3:111", "192.168.0.4:111"};

    /**
     * 真实结点列表,考虑到服务器上线、下线的场景,即添加、删除的场景会比较频繁,这里使用LinkedList会更好
     */
    private static List<String> realNodes = new LinkedList<String>();

    /**
     * 虚拟节点,key表示虚拟节点的hash值,value表示虚拟节点的名称
     */
    private static SortedMap<Integer, String> virtualNodes = 
            new TreeMap<Integer, String>();

    /**
     * 虚拟节点的数目,这里写死,为了演示需要,一个真实结点对应5个虚拟节点
     */
    private static final int VIRTUAL_NODES = 5;

    static
    {
        // 先把原始的服务器添加到真实结点列表中
        for (int i = 0; i < servers.length; i++)
            realNodes.add(servers[i]);

        // 再添加虚拟节点,遍历LinkedList使用foreach循环效率会比较高
        for (String str : realNodes)
        {
            for (int i = 0; i < VIRTUAL_NODES; i++)
            {
                String virtualNodeName = str + "&&VN" + String.valueOf(i);
                int hash = getHash(virtualNodeName);
                System.out.println("虚拟节点[" + virtualNodeName + "]被添加, hash值为" + hash);
                virtualNodes.put(hash, virtualNodeName);
            }
        }
        System.out.println();
    }

    /**
     * 使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法,最终效果没区别 
     */
    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;
    }

    /**
     * 得到应当路由到的结点
     */
    private static String getServer(String node)
    {
        // 得到带路由的结点的Hash值
        int hash = getHash(node);
        // 得到大于该Hash值的所有Map
        SortedMap<Integer, String> subMap = 
                virtualNodes.tailMap(hash);
        // 第一个Key就是顺时针过去离node最近的那个结点
        Integer i = subMap.firstKey();
        // 返回对应的虚拟节点名称,这里字符串稍微截取一下
        String virtualNode = subMap.get(i);
        return virtualNode.substring(0, virtualNode.indexOf("&&"));
    }

    public static void main(String[] args)
    {
        String[] nodes = {"127.0.0.1:1111", "221.226.0.1:2222", "10.211.0.1:3333"};
        for (int i = 0; i < nodes.length; i++)
            System.out.println("[" + nodes[i] + "]的hash值为" + 
                    getHash(nodes[i]) + ", 被路由到结点[" + getServer(nodes[i]) + "]");
    }
}

关怀一下运作结果:

虚拟节点[192.168.0.0:111&&VN0]被添加, hash值为1686427075
虚拟节点[192.168.0.0:111&&VN1]被添加, hash值为354859081
虚拟节点[192.168.0.0:111&&VN2]被添加, hash值为1306497370
虚拟节点[192.168.0.0:111&&VN3]被添加, hash值为817889914
虚拟节点[192.168.0.0:111&&VN4]被添加, hash值为396663629
虚拟节点[192.168.0.1:111&&VN0]被添加, hash值为1032739288
虚拟节点[192.168.0.1:111&&VN1]被添加, hash值为707592309
虚拟节点[192.168.0.1:111&&VN2]被添加, hash值为302114528
虚拟节点[192.168.0.1:111&&VN3]被添加, hash值为36526861
虚拟节点[192.168.0.1:111&&VN4]被添加, hash值为848442551
虚拟节点[192.168.0.2:111&&VN0]被添加, hash值为1452694222
虚拟节点[192.168.0.2:111&&VN1]被添加, hash值为2023612840
虚拟节点[192.168.0.2:111&&VN2]被添加, hash值为697907480
虚拟节点[192.168.0.2:111&&VN3]被添加, hash值为790847074
虚拟节点[192.168.0.2:111&&VN4]被添加, hash值为2010506136
虚拟节点[192.168.0.3:111&&VN0]被添加, hash值为891084251
虚拟节点[192.168.0.3:111&&VN1]被添加, hash值为1725031739
虚拟节点[192.168.0.3:111&&VN2]被添加, hash值为1127720370
虚拟节点[192.168.0.3:111&&VN3]被添加, hash值为676720500
虚拟节点[192.168.0.3:111&&VN4]被添加, hash值为2050578780
虚拟节点[192.168.0.4:111&&VN0]被添加, hash值为586921010
虚拟节点[192.168.0.4:111&&VN1]被添加, hash值为184078390
虚拟节点[192.168.0.4:111&&VN2]被添加, hash值为1331645117
虚拟节点[192.168.0.4:111&&VN3]被添加, hash值为918790803
虚拟节点[192.168.0.4:111&&VN4]被添加, hash值为1232193678

[127.0.0.1:1111]的hash值为380278925, 被路由到结点[192.168.0.0:111]
[221.226.0.1:2222]的hash值为1493545632, 被路由到结点[192.168.0.0:111]
[10.211.0.1:3333]的hash值为1393836017, 被路由到结点[192.168.0.2:111]

从代码运行结果看,每个点路由到的服务器都以Hash值顺时针离它近期的老大服务器节点,未有其余难点。

由此接纳伪造节点的主意,一个敬业结点不再固定在Hash换上的某部点,而是大大方方地分布在整整Hash环上,那样便是上线、下线服务器,也不会形成全体的载重不平衡。

后记

在写本文的时候,超级多文化小编也是边写边学,难免有过多写得不佳、明白得不深透的地点,而且代码全部也比较糙,未有思量到大概的各个气象。引玉之砖,一方面,写得非凡的地点,还望网络朋友朋友们指正;另一方面,后续小编也将由此投机的行事、学习不断完备上边的代码。

You can leave a response, or trackback from your own site.

Leave a Reply

网站地图xml地图