一致性哈希算法及Java实现

1.为什么需要一致性哈希？
在分布式服务集群中如MemCache（一个内存中存在的Hashmap），需要提供存储元素object的路由算法，来计算其应该所在的服务器位置。假设服务器集群是一个数组int[n-1] （n为服务器个数） ,如果使用这样的hash算法：
路由到的服务器的数组位置：index = hash(object) / n;
当增加一个节点或者减少一个节点时，会导致大量元素路由的服务器位置改变，导致请求object落空。
2.一致性哈希算法
一致性哈希的基本原理就是在一个hash环上（如范围0-2^32-1）计算服务器节点的hash值，如果一个object要寻找应该路由的服务器节点，则计算其hash值，并在环上顺时针查找离它最近的节点。如图：

一致性hash规则.png

如果删除节点Cache B,则影响的是CacheA-CacheB之间的key，将会路由至 Cache C ,如object4.

删除一个节点.png
如果增加一个节点Cache D,则原来一部分路由到Cache C的节点将会路由到Cache D,如object2
增加一个节点.png
可以看出在节点发生变化时一致性哈希相对传统的哈希取模可以减少object重新路由的概率，但是上述哈希分配仍然存在各个节点所分配的object不均匀的问题。
3.虚拟节点
如果让一个物理节点在hash环上代表尽可能多的分散均匀的hash值，那么object在各个物理节点的分配将会更加均匀，如图：
虚拟节点.png
虚拟节点与物理节点的对应关系如下：
虚拟节点的关系映射.png

下图横轴表示需要为每台福利服务器扩展的虚拟节点个数，纵轴表示的是实际物理服务器个数数。可以看出，物理服务器很少，需要更大的虚拟节点；反之物理服务器比较多，虚拟节点就可以少一些。比如有10台物理服务器，那么差不多需要为每台服务器增加100~200个虚拟节点才可以达到真正的负载均衡。

4.代码实现
存在两个问题，一是选取怎样的hash算法才能够使得数据分布均匀，二是如何快速查找距离最近的服务器节点是哪个？
（1）String重写的hashCode()方法在一致性Hash算法上的分布不好，KETAMA_HASH是默认的MemCache推荐的一致性Hash算法，而FNV1_32_HASH算法的效率就会高一些。
（2）这是一个排序问题，采用红黑树时间复杂度为O(LogN),Java中有对应的实现TreeMap,并且TreeMap本身提供了一个tailMap(K fromKey)方法，支持从红黑树中查找比fromKey大的值的集合，但并不需要遍历整个数据结构。

有虚拟节点的版本实现：

public interface HashFunction {
    //hash函数
    Integer hash(String key);
}

public class HashFunctionImpl implements HashFunction {
    //FNV1_32_HASH算法
    @Override
    public Integer hash(String key) {

        final int p = 16777619;
        int hash = (int)2166136261L;
        for (int i = 0; i < key.length(); i++)
            hash = (hash ^ key.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;
    }
}

// 物理机节点模拟类，保存节点的IP、名称、端口等信息
public class Node {

    private String ip;// IP
    private String name;// 名称

    public Node(String ip, String name) {
        this.ip = ip;
        this.name = name;
    }

    public String getIp() {
        return ip;
    }

    public void setIp(String ip) {
        this.ip = ip;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }
}


public class ConsistentHash {

    private final HashFunction hashFunction;// hash 函数接口
    private final int numberOfReplicas;// 每个机器节点关联的虚拟节点个数
    private final SortedMap<Integer,Node> circle = new TreeMap<>();// 环形虚拟节点

    /**
     *
     * @param hashFunction
     *            hash 函数接口
     * @param numberOfReplicas
     *            每个机器节点关联的虚拟节点个数
     * @param nodes
     *            真实机器节点
     */
    public ConsistentHash(HashFunction hashFunction, int numberOfReplicas, Collection<Node> nodes) {
        this.hashFunction = hashFunction;
        this.numberOfReplicas = numberOfReplicas;

        for (Node node : nodes) {
            add(node);
        }
    }

    /**
     * 增加真实机器节点
     *
     * @param node
     */
    public void add(Node node) {
        for (int i = 0; i < this.numberOfReplicas; i++) {
            circle.put(this.hashFunction.hash(node.getIp() + i), node);
        }
    }

    /**
     * 删除真实机器节点
     *
     * @param node
     */
    public void remove(Node node) {
        for (int i = 0; i < this.numberOfReplicas; i++) {
            circle.remove(this.hashFunction.hash(node.getIp() + i));
        }
    }

    /**
     * 取得真实机器节点
     *
     * @param key
     * @return
     */
    public Node get(String key) {
        if (circle.isEmpty()) {
            return null;
        }

        Integer hash = hashFunction.hash(key);
        if (!circle.containsKey(hash)) {
            SortedMap<Integer,Node> tailMap = circle.tailMap(hash);// 沿环的顺时针找到一个虚拟节点
            hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
        }

        return circle.get(hash); // 返回该虚拟节点对应的真实机器节点的信息
    }
}

public class ConHashTest {
    private static final String IP_PREFIX = "192.168.1.";// 机器节点IP前缀
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<String, Integer>();// 每台真实机器节点上保存的记录条数
        HashFunction hashFunction = new HashFunctionImpl();
        //真实物理节点
        List<Node> realNodes = new ArrayList<>();
        for (int i = 1; i <= 10; i++) {
            map.put(IP_PREFIX + i, 0);// 每台真实机器节点上保存的记录条数初始为0

            Node node = new Node(IP_PREFIX + i, "node" + i);
            realNodes.add(node);
        }


        ConsistentHash consistentHash = new ConsistentHash(hashFunction,100,realNodes);
        // 将10000条记录尽可能均匀的存储到10台机器节点
        for (int i = 0; i < 10000; i++) {
            // 产生随机一个字符串当做一条记录，可以是其它更复杂的业务对象,比如随机字符串相当于对象的业务唯一标识
            String data = UUID.randomUUID().toString() + i;
            // 通过记录找到真实机器节点
            Node node = consistentHash.get(data);
            // 这里可以通过其它工具将记录存储真实机器节点上，比如MemoryCache等
            // ...
            // 每台真实机器节点上保存的记录条数加1
            map.put(node.getIp(), map.get(node.getIp()) + 1);
        }

        // 打印每台真实机器节点保存的记录条数
        for (int i = 1; i <= 10; i++) {
            System.out.println(IP_PREFIX + i + "节点记录条数：" + map.get("192.168.1." + i));
        }
    }

}

参考资料：
https://cloud.tencent.com/developer/article/1084801
https://www.codeproject.com/Articles/56138/Consistent-hashing
http://sundoctor.iteye.com/blog/2104321
一致性哈希论文