一致性hash算法

一、算法介绍

在1997年由麻省理工学院提出的一种分布式哈希（DHT）实现算法，设计目标是为了解决因特网中的热点(Hot spot)问题

① 解决因特网中的热点问题；

② 基于分布式一致性算法，实现P2P架构；（无单点）

 

1.1 普通hash算法 

hash(object)%N算法；

如果有机器添加或者删除后，原有的数据就会找不到了；

 

1.2 分布式一致性hash算法 

环形空间，[ 0 , 2^32 - 1]；(将这些数字头尾相连，形成一个闭环)

 

 例如：

现在有NODE1，NODE2，NODE3三台机器，通过Hash算法得到对应的KEY值，映射到环中。

Hash(NODE1) = KEY1;
Hash(NODE2) = KEY2;
Hash(NODE3) = KEY3;

 

 

将object1、object2、object3、object4四个对象通过特定的Hash函数计算出对应的key值

Hash(object1) = key1；
Hash(object2) = key2；
Hash(object3) = key3；
Hash(object4) = key4；

 

这样按顺时针转动object1存储到了NODE1中；

object3存储到了NODE2中；

object2、object4存储到了NODE3中；

 

在这样的部署环境中，hash环是不会变更的，因此，通过算出对象的hash值就能快速的定位到对应的机器中，这样就能找到对象真正的存储位置了；

 

二、算法实现

 

2.1 ketama算法

 

    /**
     * 1.对所有50个节点，生成160个虚拟结点；
     * 2.每四个虚拟结点为一组；
     * 3.Md5是一个16字节长度的数组，将16字节的数组每四个字节一组，分别对应一个虚拟结点，这就是为什么上面把虚拟结点四个划分一组的原因；
     * 4.对于每四个字节，组成一个long值数值，做为这个虚拟节点的在环中的惟一key；
     *
     * @param nodes
     * @param algorithm
     * @param virtualNodeCount
     */
    public KetamaNodeLocator(List<Node> nodes, HashAlgorithm algorithm, int virtualNodeCount) {
        this.virtualNodeCount = virtualNodeCount;
        ketamaNodes = new TreeMap<Long, Node>();
        hashAlgorithm = algorithm;

        //构造一致性hash环
        for (Node node : nodes) {
            for (int i = 0; i < this.virtualNodeCount / 4; i++) {
                byte[] digest = hashAlgorithm.computeMd5(node.getName() + i);
                for (int h = 0; h < 4; h++) {
                    long m = hashAlgorithm.hash(digest, h);
                    ketamaNodes.put(m, node);
                }
            }
        }
    }

    /**
     *  返回hash对应的节点
     *
     * @param hash
     * @return
     */
    private Node getNodeForKey(long hash) {
        final Node node;
        Long key = hash;
        if (!ketamaNodes.containsKey(key)) {
            SortedMap<Long, Node> tailMap = ketamaNodes.tailMap(key);
            if (tailMap.isEmpty()) {
                key = ketamaNodes.firstKey();
            } else {
                key = tailMap.firstKey();
            }
        }
        node = ketamaNodes.get(key);
        return node;
    }

 

 

2.2 节点node1，划分为160个虚拟节点 

 

 

2.3 节点node2，划分为160个虚拟节点

 

 

 

2.4 获取key对应的节点

① key="mengka_bb";

② 获取16位的hash值，[ 0~4 , 5~8 , 9~12 , 13~16 ]

[ 0~4 ] = k1 (long值，2^32范围内)

③ treeMap.get(k1);

④ 返回key对应存储数据的node节点；

 

    /**
     *  节点个数
     */
    private static final Integer NODE_COUNT = 50;

    /**
     *  虚拟节点的个数
     */
    private static final Integer VIRTUAL_NODE_COUNT = 160;

    public static void main(String[] args){

        String key = "mengka_bb";

        //返回node列表，[node1,node50]
        List<Node> allNodes = NodeUtil.getNodes(NODE_COUNT);
        //获取ketamaLocator
        KetamaNodeLocator ketamaLocator = new KetamaNodeLocator(allNodes, HashAlgorithm.KETAMA_HASH, VIRTUAL_NODE_COUNT);

        //返回key对应的节点
        Node node = ketamaLocator.getPrimary(key);
        if (node != null) {
            System.out.println("-----------, node = "+node.getName());
        }
    }