一致性Hash算法背景

一致性哈希算法在1997年由麻省理工学院的Karger等人在解决分布式Cache中提出的，设计目标是为了解决因特网中的热点(Hot spot)问题，初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题，使得DHT可以在P2P环境中真正得到应用。

原理

基本概念

一致性哈希算法（Consistent Hashing）最早在论文《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》中被提出。简单来说，一致性哈希将整个哈希值空间组织成一个虚拟的圆环，如假设某哈希函数H的值空间为0-2^32-1（即哈希值是一个32位无符号整形），整个哈希空间环如下：

整个空间按顺时针方向组织。0和232-1在零点中方向重合。

在集群服务器确定以后，将各个服务器使用Hash函数进行一个哈希计算，哈希计算可以选择服务器的ip地址或者主机名等关键字进行哈希，这样就完成了节点在hash环上的位置分配，假设集群有四台服务器，最终效果如下：

服务器分配

接下来，每台服务器在hash环上的位置分配完成后，在客户端对缓存key进行同样函数的hash运算，得出hash值，同样得到环上的一个位置，从这个位置顺时针找到最近的一个服务器节点，比如遍历所有节点位置和key位置差值取最小值，这样就完成了路由。

例如我们有Object A、Object B、Object C、Object D四个数据对象，经过哈希计算后，在环空间上的位置如下：

负载均衡

根据一致性哈希算法，数据A会被定为到Node A上，B被定为到Node B上，C被定为到Node C上，D被定为到Node D上。

容错性和拓展性

上篇博客提到了简单哈希的缺点，当服务器宕机、扩容、缩容时，容错性和扩展性差，那么一致性hash的容错性和拓展性如何呢？

接着上图讨论，现假设Node C不幸宕机，可以看到此时对象A、B、D不会受到影响，只有C对象被重定位到Node D。一般的，在一致性哈希算法中，如果一台服务器不可用，则受影响的数据仅仅是此服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间数据，其它不会受到影响。

下面考虑另外一种情况，如果在系统中增加一台服务器Node X，如下图所示：

扩容情况

此时对象Object A、B、D不受影响，只有对象C需要重定位到新的Node X 。一般的，在一致性哈希算法中，如果增加一台服务器，则受影响的数据仅仅是新服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间数据，其它数据也不会受到影响。

综上所述，一致性哈希算法对于节点的增减都只需重定位环空间中的一小部分数据，具有较好的容错性和可扩展性。

数据倾斜问题

一致性hash算法的缺陷是它无法控制节点分布的均匀性，因为hash的结果并不一定均匀分布在环上对称的位置，极端的情况，举个例子，现在有A、B、C三个服务器节点，hash的结果紧挨在一起，那么根据一致性hash，一定是极少量的key会访问到从0点开始顺时针数到的第二、三个节点，绝大部分key都会访问到顺时针数到的第一个节点。如下图：

不均匀分布

hash(key)运算结果落在A和B之间的请求会访问到B服务器，hash(key)运算结果落在B和C之间的请求会访问到C服务器，而hash(key)落在A和C之间的请求会访问到A服务器。这样A的压力不言而喻。

解决方案

虚拟节点

为了解决这种数据倾斜问题，一致性哈希算法引入了虚拟节点机制

简单来说就是将一台服务器加上编号尾缀进行哈希，每台服务器就会有多个结果

虚拟节点

同时数据定位算法不变，只是多了一步虚拟节点到实际节点的映射，例如定位到“Node A#1”、“Node A#2”、“Node A#3”三个虚拟节点的数据均定位到Node A上。这样就解决了服务节点少时数据倾斜的问题。在实际应用中，通常将虚拟节点数设置为32甚至更大，因此即使很少的服务节点也能做到相对均匀的数据分布。

良好的分布式cahce系统中的一致性hash算法应该满足以下几个方面：

平衡性(Balance)

平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。

单调性(Monotonicity)

单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲区加入到系统中，那么哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲区中去，而不会被映射到旧的缓冲集合中的其他缓冲区。简单的哈希算法往往不能满足单调性的要求，如最简单的线性哈希：x = (ax + b) mod (P)，在上式中，P表示全部缓冲的大小。不难看出，当缓冲大小发生变化时(从P1到P2)，原来所有的哈希结果均会发生变化，从而不满足单调性的要求。哈希结果的变化意味着当缓冲空间发生变化时，所有的映射关系需要在系统内全部更新。而在P2P系统内，缓冲的变化等价于Peer加入或退出系统，这一情况在P2P系统中会频繁发生，因此会带来极大计算和传输负荷。单调性就是要求哈希算法能够应对这种情况。

分散性(Spread)

在分布式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。

负载(Load)

负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。

平滑性(Smoothness)

平滑性是指缓存服务器的数目平滑改变和缓存对象的平滑改变是一致的。

一致性hash代码实现:

package com.ctrip.dcs;

import java.io.UnsupportedEncodingException;

import java.security.MessageDigest;

import java.security.NoSuchAlgorithmException;

import java.util.*;

public class ConsistencyHash {

    private TreeMap<Long,Object> nodes = null;

    //真实服务器节点信息

    private List<Object> shards = new ArrayList();

    //设置虚拟节点数目

    private int VIRTUAL_NUM = 4;

    /**

    * 初始化一致环

    */

    public void init() {

        shards.add("192.168.0.0-服务器0");

        shards.add("192.168.0.1-服务器1");

        shards.add("192.168.0.2-服务器2");

        shards.add("192.168.0.3-服务器3");

        shards.add("192.168.0.4-服务器4");

        nodes = new TreeMap<>();

        for(int i=0; i<shards.size(); i++) {

            Object shardInfo = shards.get(i);

            for(int j=0; j<VIRTUAL_NUM; j++) {

                nodes.put(hash(computeMd5("SHARD-" + i + "-NODE-" + j),j), shardInfo);

            }

        }

    }

    /**

    * 根据key的hash值取得服务器节点信息

    * @param hash

    * @return

    */

    public Object getShardInfo(long hash) {

        Long key = hash;

        SortedMap<Long, Object> tailMap=nodes.tailMap(key);

        if(tailMap.isEmpty()) {

            key = nodes.firstKey();

        } else {

            key = tailMap.firstKey();

        }

        return nodes.get(key);

    }

    /**

    * 打印圆环节点数据

    */

    public void printMap() {

        System.out.println(nodes);

    }

    /**

    * 根据2^32把节点分布到圆环上面。

    * @param digest

    * @param nTime

    * @return

    */

    public long hash(byte[] digest, int nTime) {

        long rv = ((long) (digest[3+nTime*4] & 0xFF) << 24)

                | ((long) (digest[2+nTime*4] & 0xFF) << 16)

                | ((long) (digest[1+nTime*4] & 0xFF) << 8)

                | (digest[0+nTime*4] & 0xFF);

        return rv & 0xffffffffL; /* Truncate to 32-bits */

    }

    /**

    * Get the md5 of the given key.

    * 计算MD5值

    */

    public byte[] computeMd5(String k) {

        MessageDigest md5;

        try {

            md5 = MessageDigest.getInstance("MD5");

        } catch (NoSuchAlgorithmException e) {

            throw new RuntimeException("MD5 not supported", e);

        }

        md5.reset();

        byte[] keyBytes = null;

        try {

            keyBytes = k.getBytes("UTF-8");

        } catch (UnsupportedEncodingException e) {

            throw new RuntimeException("Unknown string :" + k, e);

        }

        md5.update(keyBytes);

        return md5.digest();

    }

    public static void main(String[] args) {

        Random ran = new Random();

        ConsistencyHash hash = new ConsistencyHash();

        hash.init();

        hash.printMap();

        //循环50次，是为了取50个数来测试效果，当然也可以用其他任何的数据来测试

        for(int i=0; i<50; i++) {

            System.out.println(hash.getShardInfo(hash.hash(hash.computeMd5(String.valueOf(i)),ran.nextInt(hash.VIRTUAL_NUM))));

        }

    }

}

下篇博客介绍一下redis cluster的hash slot算法，介绍一下redis分片技术。