Redis系列目录
 
redis系列之——分布式锁
 redis系列之——缓存穿透、缓存击穿、缓存雪崩
 redis系列之——Redis为什么这么快？
 redis系列之——数据持久化（RDB和AOF）
 redis系列之——一致性hash算法
 redis系列之——高可用（主从、哨兵、集群）
 redis系列之——事物及乐观锁
 redis系列之——数据类型geospatial：你隔壁有没有老王？
 redis系列之——数据类型bitmaps：今天你签到了吗？
 布隆过滤器是个啥！
 
一致性hash算法你了解吗？什么时候使用？解决什么问题？redis集群模式使用了一致性hash算法了吗？
 
 
数据分片（sharding）
 
分布式数据存储时，经常要考虑数据分片，避免将大量的数据放在单表或单库中，造成查询等操作的耗时过长。比如，存储订单数据时使用三个mysql库（编号0,1,2），当一条订单数据过来时，对订单id求hash后与机器数量取模，hash(orderId) % 3，假如得到的结果是2，则这条数据会存储到编号为2的mysql中。分表分库存储时，根据数据库的主键或唯一键做hash，然后跟数据库机器的数量取模，从而决定该条数据放在哪个库中。
 
根据机器数量取模就会存在一个问题，当机器不够用需要扩容或机器宕机，机器的数量就会发生变化，造成数据的命中率下降，所以之前的数据就需要重新hash做一次sharding。这种操作会导致服务在一定的时间不可用，而且每次扩缩容都会存在这个问题。
 
一致性hash
 
一致性hash算法主要应用于分布式存储系统中，可以有效地解决分布式存储结构下普通余数Hash算法带来的伸缩性差的问题，可以保证在动态增加和删除节点的情况下尽量有多的请求命中原来的机器节点。
 
Hash环
 
一致性Hash算法也是使用取模的方法，只是，刚才描述的取模法是对服务器的数量进行取模，而一致性Hash算法是对2^ 32-1取模，什么意思呢简单来说，一致性Hash算法将整个Hash值控件组织成一个虚拟的圆环，如假设某哈希函数H的值空间为0-2^32-1取模（即哈希值是一个32位无符号整型），整个哈希环如下：
 
 
整个空间按顺时针方向组织，圆环的正上方的点代表0，0点右侧的第一个点代表1，以此类推，2、3、4、5、6……直到2^ 32-1，也就是说0点左侧的第一个点代表2^ 32-1， 0和2^ 32-1在零点中方向重合，我们把这个由2^32个点组成的圆环称为Hash环。
 
下一步将各个服务器使用Hash进行一个哈希，具体可以选择服务器的主机名（考虑到ip变动，不要使用ip）作为关键字进行哈希，这样每台机器就能确定其在哈希环上的位置，这里假设将上文中三个master节点的IP地址哈希后在环空间的位置如下：
 
 
下面将三条key-value数据也放到环上：将数据key使用相同的函数Hash计算出哈希值，并确定此数据在环上的位置。将数据从所在位置顺时针找第一台遇到的服务器节点，这个节点就是该key存储的服务器！
 
例如我们有a、b、c三个key，经过哈希计算后，在环空间上的位置如下：key-a存储在node1，key-b存储在node2，key-c存储在node3。
 
 
容错性和可扩展性
 
现假设Node 2不幸宕机，可以看到此时对象key-a和key-c不会受到影响，只有key-b被重定位到Node 3。一般的，在一致性Hash算法中，如果一台服务器不可用，则受影响的数据仅仅是此服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器，如下图中Node 2与Node 1之间的数据，图中受影响的是key-2）之间数据，其它不会受到影响。
 
同样的，如果集群中新增一个node 4，受影响的数据是node 1和node 4之间的数据，其他的数据是不受影响的。
 
 
综上所述，一致性Hash算法对于节点的增减都只需重定位环空间中的一小部分数据，具有较好的容错性和可扩展性。
 
数据倾斜
 
一致性Hash算法在服务节点太少时，容易因为节点分部不均匀而造成数据倾斜（被缓存的对象大部分集中缓存在某一台服务器上）问题，例如系统中只有两台服务器，此时必然造成大量数据集中到Node 2上，而只有极少量会定位到Node 1上。其环分布如下：
 
 
为了解决数据倾斜问题，一致性Hash算法引入了虚拟节点机制，即对每一个服务节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点。具体做法可以在主机名的后面增加编号来实现。例如上面的情况，可以为每台服务器计算三个虚拟节点，于是可以分别计算 “Node 1#1”、“Node 1#2”、“Node 1#3”、“Node 2#1”、“Node 2#2”、“Node 2#3”的哈希值，于是形成六个虚拟节点：
 
 
上图中虚拟节点node 1#1，node 1#2，node 1#3都属于真实节点node 1；虚拟节点node 2#1，node 2#2，node 2#3都属于真实节点node 2。
 
实际项目中使用
 
上来先说一个误区，**Redis 集群没有使用一致性hash, 而是引入了哈希槽slots的概念。**可以参考我的另一篇文章《redis系列之——高可用（主从、哨兵、集群）》。
 
我们说的一致性hash都不是缓存机器自身的功能，而是集群前置的代理或客户端实现的。而redis官方的集群是集群本身通过slots实现了数据分片。
 
redis集群时3.0版本才出现的，出现的比较晚，在集群模式出现之前，很多公司都做了自己的redis集群了。这些自研的redis集群的实现方式有多种，比如在redis的jedis客户端jar包就是实现了一致性hash算法（客户端模式），或者在redis集群前面加上一层前置代理如Twemproxy也实现了hash一致性算法（代理模式）。Twemproxy，是 Twitter 开源出来的 Redis 和 Memcached 代理，使用这种代理模式搭建的集群，我们的客户端连接只需要连接代理服务器即可，不用连接代理后面具体的redis机器。Twemproxy具体使用哪一种hash算法也是可以通过配置文件指定的。
 
完成，收工！
 
 
【传播知识，共享价值】，感谢小伙伴们的关注和支持，我是【诸葛小猿】，一个彷徨中奋斗的互联网民工！！！
 

目前我们很多时候都是在做分布式系统，但是我们需把客户端的请求均匀的分布到N个服务器中，一般我们可以考虑通过Object的HashCodeHash%N，通过取余，将客户端的请求分布到不同的的服务端。但是在分布式集群中我们通常需要添加或删除服务器，所以通过取余是不行的。一致性Hash就是为了解决这个问题。
 
　　Consistent Hashing 一致性Hash的原理
 
　　1、环型Hash空间
 
　　根据常用的Hash，是将key哈希到一个长为2^32的桶中，即0～2^32-1的数字空间，最后通过首尾相连，我们可以想象成一个闭合的圆。如图：
 
　　
 
　　2、把数据通过一定的Hash算法处理后，映射到环上
 
　　例如：我们有Object1、Object2、Object3、Object4，通过Hash算法求出值如下：
 
　　　　Hash(Object1) = key1;
 
　　　　Hash(Object2) = key2;
 
　　　　Hash(Object3) = key3;
 
　　　　Hash(Object4) = key4;
 
　　
 
　　3、将机器信息通过hash算法映射到环上
 
　　　　一般情况下是对机器的信息通过计算hash，然后以顺时针方向计算，将对象信息存储在相应的位置。
 
　　　　
 
　　4、虚拟节点
 
　　　　上面是Hash算法的特性，但是Hash算法缺少一个平衡性。
 
　　　　Hash算法的平衡行就是为了尽可能使分配到每个数据桶里面的节点是均衡的，一个简单的例子：我们有3个分布式服务器，在大量客户端访问时，通过Hash算法，使得他们能在每个服务器均匀的访问。所以这里引入了“虚拟节点”节点，从而保证数据节点均衡。
 
　　　　“虚拟节点”就是真实节点的复制品，一个真实的节点对应多个“虚拟节点”，这样使得我们的节点能尽可能的在环形Hash空间均匀分布，这样我们再根据虚拟节点找到真实节点，从而保证每个真实节点上分配到的请求是均衡的。
 
　　　　
 
　　具体的代码实现如下：
 
import java.util.LinkedList;
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;

public class ConsistencyHashing {

    // 虚拟节点的个数
    private static final int VIRTUAL_NUM = 5;

    // 虚拟节点分配，key是hash值，value是虚拟节点服务器名称
    private static SortedMap<Integer, String> shards = new TreeMap<Integer, String>();

    // 真实节点列表
    private static List<String> realNodes = new LinkedList<String>();

    //模拟初始服务器
    private static String[] servers = { "192.168.1.1", "192.168.1.2", "192.168.1.3", "192.168.1.5", "192.168.1.6" };

    static {
        for (String server : servers) {
            realNodes.add(server);
            System.out.println("真实节点[" + server + "] 被添加");
            for (int i = 0; i < VIRTUAL_NUM; i++) {
                String virtualNode = server + "&&VN" + i;
                int hash = getHash(virtualNode);
                shards.put(hash, virtualNode);
                System.out.println("虚拟节点[" + virtualNode + "] hash:" + hash + "，被添加");
            }
        }
    }

    /**
     * 获取被分配的节点名
     * 
     * @param node
     * @return
     */
    public static String getServer(String node) {
        int hash = getHash(node);
        Integer key = null;
        SortedMap<Integer, String> subMap = shards.tailMap(hash);
        if (subMap.isEmpty()) {
            key = shards.lastKey();
        } else {
            key = subMap.firstKey();
        }
        String virtualNode = shards.get(key);
        return virtualNode.substring(0, virtualNode.indexOf("&&"));
    }

    /**
     * 添加节点
     * 
     * @param node
     */
    public static void addNode(String node) {
        if (!realNodes.contains(node)) {
            realNodes.add(node);
            System.out.println("真实节点[" + node + "] 上线添加");
            for (int i = 0; i < VIRTUAL_NUM; i++) {
                String virtualNode = node + "&&VN" + i;
                int hash = getHash(virtualNode);
                shards.put(hash, virtualNode);
                System.out.println("虚拟节点[" + virtualNode + "] hash:" + hash + "，被添加");
            }
        }
    }

    /**
     * 删除节点
     * 
     * @param node
     */
    public static void delNode(String node) {
        if (realNodes.contains(node)) {
            realNodes.remove(node);
            System.out.println("真实节点[" + node + "] 下线移除");
            for (int i = 0; i < VIRTUAL_NUM; i++) {
                String virtualNode = node + "&&VN" + i;
                int hash = getHash(virtualNode);
                shards.remove(hash);
                System.out.println("虚拟节点[" + virtualNode + "] hash:" + hash + "，被移除");
            }
        }
    }

    /**
     * FNV1_32_HASH算法
     */
    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;
    }

    public static void main(String[] args) {
        
        //模拟客户端的请求
        String[] nodes = { "127.0.0.1", "10.9.3.253", "192.168.10.1" };
        
        for (String node : nodes) {
            System.out.println("[" + node + "]的hash值为" + getHash(node) + ", 被路由到结点[" + getServer(node) + "]");
        }
        
        // 添加一个节点(模拟服务器上线)
        addNode("192.168.1.7");
        // 删除一个节点（模拟服务器下线）
        delNode("192.168.1.2");

        for (String node : nodes) {
            System.out.println("[" + node + "]的hash值为" + getHash(node) + ", 被路由到结点[" + getServer(node) + "]");
        }
    }
}
 
　测试结果：
 
　
 
　　从结果可以看出：服务器节点上线和下线并不会对我们服务有任何影响，除非所有的服务都下线。当之前映射的服务器下线，我们可以切换到和它Hash临近的服务节点上，保证服务的负载均衡。
 
       如果我们考虑每台服务器性能不一致，比如服务器内存有32G、16G、8G的，我们可以根据不同的服务器性能，分配不同的负载因子（就是上面程序的VIRTUAL_NUM）,这样我们是不是可以想到和Dubbo里面的负载因子是一致的。我们可以手动的调整每台服务器的负载因子，从而根据每个服务器性能，分配不同权重的客户端请求负载量 。
 
实现案例：
 
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;

public class ConsistencyHashingLoadFactor {

    // 真实节点列表
    private static List<Machine> realNodes = new ArrayList<Machine>();

    // 虚拟节点，key是Hash值，value是虚拟节点信息
    private static SortedMap<Integer, String> shards = new TreeMap<Integer, String>();

    static {
        realNodes.add(new Machine("192.168.1.1", LoadFactor.Memory8G));
        realNodes.add(new Machine("192.168.1.2", LoadFactor.Memory16G));
        realNodes.add(new Machine("192.168.1.3", LoadFactor.Memory32G));
        realNodes.add(new Machine("192.168.1.4", LoadFactor.Memory16G));
        for (Machine node : realNodes) {
            for (int i = 0; i < node.getMemory().getVrNum(); i++) {
                String server = node.getHost();
                String virtualNode = server + "&&VN" + i;
                int hash = getHash(virtualNode);
                shards.put(hash, virtualNode);
            }
        }
    }

    /**
     * 获取被分配的节点名
     * 
     * @param node
     * @return
     */
    public static Machine getServer(String node) {
        int hash = getHash(node);
        Integer key = null;
        SortedMap<Integer, String> subMap = shards.tailMap(hash);
        if (subMap.isEmpty()) {
            key = shards.lastKey();
        } else {
            key = subMap.firstKey();
        }
        String virtualNode = shards.get(key);
        String realNodeName = virtualNode.substring(0, virtualNode.indexOf("&&"));
        for (Machine machine : realNodes) {
            if (machine.getHost().equals(realNodeName)) {
                return machine;
            }
        }
        return null;
    }

    /**
     * 添加节点
     * 
     * @param node
     */
    public static void addNode(Machine node) {
        if (!realNodes.contains(node)) {
            realNodes.add(node);
            System.out.println("真实节点[" + node + "] 上线添加");
            for (int i = 0; i < node.getMemory().getVrNum(); i++) {
                String virtualNode = node.getHost() + "&&VN" + i;
                int hash = getHash(virtualNode);
                shards.put(hash, virtualNode);
                System.out.println("虚拟节点[" + virtualNode + "] hash:" + hash + "，被添加");
            }
        }
    }

    /**
     * 删除节点
     * 
     * @param node
     */
    public static void delNode(Machine node) {
        String host = node.getHost();
        Iterator<Machine> it = realNodes.iterator();
        while(it.hasNext()) {
            Machine machine = it.next();
            if(machine.getHost().equals(host)) {
                it.remove();
                System.out.println("真实节点[" + node + "] 下线移除");
                for (int i = 0; i < node.getMemory().getVrNum(); i++) {
                    String virtualNode = node.getHost() + "&&VN" + i;
                    int hash = getHash(virtualNode);
                    shards.remove(hash);
                    System.out.println("虚拟节点[" + virtualNode + "] hash:" + hash + "，被移除");
                }
            }
        }
    }

    /**
     * FNV1_32_HASH算法
     */
    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;
    }

    public static void main(String[] args) {

        // 模拟客户端的请求
        String[] nodes = { "127.0.0.1", "10.9.3.253", "192.168.10.1" };

        for (String node : nodes) {
            System.out.println("[" + node + "]的hash值为" + getHash(node) + ", 被路由到结点[" + getServer(node) + "]");
        }

        // 添加一个节点(模拟服务器上线)
        addNode(new Machine("192.168.1.7", LoadFactor.Memory16G));
        // 删除一个节点（模拟服务器下线）
        delNode(new Machine("192.168.1.1", LoadFactor.Memory8G));

        for (String node : nodes) {
            System.out.println("[" + node + "]的hash值为" + getHash(node) + ", 被路由到结点[" + getServer(node) + "]");
        }
    }
}

/**
 * 机器类
 * 
 * @author yangkuanjun
 *
 */
class Machine {

    private String host;

    private LoadFactor memory;

    public String getHost() {
        return host;
    }

    public void setHost(String host) {
        this.host = host;
    }

    public LoadFactor getMemory() {
        return memory;
    }

    public void setMemory(LoadFactor memory) {
        this.memory = memory;
    }

    public Machine(String host, LoadFactor memory) {
        super();
        this.host = host;
        this.memory = memory;
    }

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

/**
 * 负载因子
 * 
 * @author yangkuanjun
 *
 */
enum LoadFactor {

    Memory8G(5), Memory16G(10), Memory32G(20);

    private int vrNum;

    private LoadFactor(int vrNum) {
        this.vrNum = vrNum;
    }

    public int getVrNum() {
        return vrNum;
    }

}
 
测试结果：
 
 
　　从运行结果可以看出：负载因子较大的被分配的概率就越大。

普通hash
 
定义
 
Hash函数：一般翻译做散列、杂凑，或音译为哈希，是把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值。
 碰撞（冲突）：如果两个关键字通过hash函数得到的值是一样的，就是碰撞或冲突。
 Hash表（散列表）：根据散列函数和冲突处理将一组关键字分配在连续的地址空间内，并以散列值记录在表中的存储位置，这种表成为散列表。
 
常用算法
 
直接寻址法：即取关键字或关键字的线性函数为散列地址：H(key)=key或H(key)=a*key+b;
 数字分析法：即分析一组数据后采用的方法：如人的出生年月为92-09-03则前三位重复的几率比较大，容易产生碰撞，所以应该采用后三位作为hash值好点
 平方取中法：取关键字平方的后几位。
 折叠法：把关键字分割成位数相同的几部分，最后一部分可以位数不同，然后取这几部分的叠加值
 随机数法：以关键值作为生成随机数的种子生成散列地址，通常适用于关键字长度不同的场合。
 除留余数法：取关键字被某个不大于散列表长度m的数p除后所得的余数为散列地址:H(key)=key%p(p<=m);不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生碰撞。
 
什么是一致性Hash算法
 
1. 为什么要使用Hash算法
 举个例子，我们在使用Redis的时候，为了保证Redis的高可用，提高Redis的读写性能，最简单的方式我们会做主从复制，，或者搭建Redis集群，进行数据的读写分离，当数据量很大的时候（标准可能不一样，要看Redis服务器容量）我们同样可以对Redis进行类似数据库的操作，就是分库分表。如图所示
 
 假若采用随机分配的方式，那么我们保存到一条数据都有可能存储在任何一组Redis中，如果我们需要查询某一条数据，由于我们不清楚数据保存在哪一个redis服务器中，因此需要遍历了所有的Redis服务器，这显然不是我们想要的结果。
 如果我们使用Hash的方式，每一张图片在进行分库的时候都可以定位到特定的服务器，示意图如下：
 
 上图中，假设我们查找的是”a.png”，由于有4台服务器（排除从库），因此公式为hash(a.png) % 4 = 2 ，可知定位到了第2号服务器，这样的话就不会遍历所有的服务器，大大提升了性能！
 
2. 使用Hash带来的问题
 上述的方式虽然提升了性能，我们不再需要对整个Redis服务器进行遍历！但是，使用上述Hash算法进行缓存时，会出现一些缺陷，主要体现在服务器数量变动的时候，所有缓存的位置都要发生改变！
 
试想一下，如果4台缓存服务器已经不能满足我们的缓存需求，那么我们应该怎么做呢？很简单，多增加几台缓存服务器不就行了！假设：我们增加了一台缓存服务器，那么缓存服务器的数量就由4台变成了5台。那么原本hash(a.png) % 4 = 2 的公式就变成了hash(a.png) % 5 = ？ ， 可想而知这个结果肯定不是2的，这种情况带来的结果就是当服务器数量变动时，所有缓存的位置都要发生改变！换句话说，当服务器数量发生改变时，所有缓存在一定时间内是失效的，当应用无法从缓存中获取数据时，则会向后端数据库请求数据！
 
同样的，假设4台缓存中突然有一台缓存服务器出现了故障，无法进行缓存，那么我们则需要将故障机器移除，但是如果移除了一台缓存服务器，那么缓存服务器数量从4台变为3台，也是会出现上述的问题！
 
所以，我们应该想办法不让这种情况发生，但是由于上述Hash算法本身的缘故，使用取模法进行缓存时，这种情况是无法避免的，为了解决这些问题，Hash一致性算法（一致性Hash算法）诞生了！
 
3. 一致性hash算法原理
 一致性Hash算法也是使用取模的方法，只是，刚才描述的取模法是对服务器的数量进行取模，而一致性Hash算法是对2^32取模，一致性Hash算法将整个哈希值空间组织成一个虚拟的圆环，将各个服务器使用Hash进行一个哈希，具体可以选择服务器的IP或主机名作为关键字进行哈希，这样每台机器就能确定其在哈希环上的位置，这里假设将上文中四台服务器使用IP地址哈希后在环空间的位置如下：
 
 
每次根据要缓存的key计算得到hash值，在hash环上顺时针查找距离最近的缓存服务器节点，
 
 根据一致性Hash算法，数据A会被定为到Node A上，B被定为到Node B上，C被定为到Node C上，D被定为到Node D上。
 
一致性Hash算法的容错性和可扩展性
 现假设Node C不幸宕机，可以看到此时对象A、B、D不会受到影响，只有C对象被重定位到Node D。一般的，在一致性Hash算法中，如果一台服务器不可用，则受影响的数据仅仅是此服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间数据，其它不会受到影响，如下所示：
 
 下面考虑另外一种情况，如果在系统中增加一台服务器Node X，如下图所示：
 

 此时对象Object A、B、D不受影响，只有对象C需要重定位到新的Node X ！一般的，在一致性Hash算法中，如果增加一台服务器，则受影响的数据仅仅是新服务器到其环空间中前一台服务器（即沿着逆时针方向行走遇到的第一台服务器）之间数据，其它数据也不会受到影响。
 
综上所述，一致性Hash算法对于节点的增减都只需重定位环空间中的一小部分数据，具有较好的容错性和可扩展性。
 
4. Hash环的数据倾斜问题
 一致性Hash算法在服务节点太少时，容易因为节点分部不均匀而造成数据倾斜（被缓存的对象大部分集中缓存在某一台服务器上）问题，例如系统中只有两台服务器，其环分布如下：
 
 此时必然造成大量数据集中到Node A上，而只有极少量会定位到Node B上。为了解决这种数据倾斜问题，一致性Hash算法引入了虚拟节点机制，即对每一个服务节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点。具体做法可以在服务器IP或主机名的后面增加编号来实现。
 例如上面的情况，可以为每台服务器计算三个虚拟节点，于是可以分别计算 “Node A#1”、“Node A#2”、“Node A#3”、“Node B#1”、“Node B#2”、“Node B#3”的哈希值，于是形成六个虚拟节点：
 
 同时数据定位算法不变，只是多了一步虚拟节点到实际节点的映射，例如定位到“Node A#1”、“Node A#2”、“Node A#3”三个虚拟节点的数据均定位到Node A上。这样就解决了服务节点少时数据倾斜的问题。在实际应用中，通常将虚拟节点数设置为32甚至更大，因此即使很少的服务节点也能做到相对均匀的数据分布。
 
总结
 
在分布式系统中一致性hash起着不可忽略的地位，无论是分布式缓存，还是分布式Rpc框架的负载均衡策略都有所使用。分布式系统每个节点都有可能失效，并且新的节点很可能动态的增加进来的情况，如何保证当系统的节点数目发生变化的时候，我们的系统仍然能够对外提供良好的服务，这是值得考虑的！
 
一致性哈希算法能尽可能减少了服务器数量变化所导致的缓存迁移。
 
consistent(一致性) hash算法能够在一定程度上改善缓存的雪崩问题，它能够在移除/添加一台缓 存服务器时，尽可能小的改变已存在的key映射关系，避免大量key的重新映射。
 
先构造一个长度为2 32次方的整数环（这个环被称为一致性Hash环），根据节点名称的Hash值（其分布为[0, 23 2次方-1]）将服务器节点放置在这个Hash环上，然后根据数据的Key值计算得到其Hash值（其分布也为[0, 2 32次方-1]），接着在Hash环上顺时针查找距离这个Key值的Hash值最近的服务器节点，完成Key到服务器的映射查找。
 
这种算法解决了普通余数Hash算法伸缩性差的问题，可以保证在上线、下线服务器的情况下尽量有多的请求命中原来路由到的服务器。

 
文章目录
 
前言
一、一致性Hash是什么？
二、使用步骤
1.一致性hash算法
ConsistentHashAlgorithm
   
   
2.初始化表结点，并映射到hash环
InitTableNodesToHashLoop
   
   
3.创建分表算法
ConsistentShardingAlgorithm
   
   
4.更改配置
  
总结

 
 
前言
 
前几篇文章主要介绍了Springboot+Sharding-JDBC在分库分表中的实践，那么在实际场景中，我们可能会有需求对已经分表的表节点进行扩容。那么在分表算法为求余的情况下，如果增加一个节点，会导致大部分已存在的数据多要进行迁移，工程量巨大。
 那除了求余分表算法外，还有其他算法能在缩扩容场景下更好的工作吗？！接下来我们一起看下一致性Hash算法在分库分表中的应用。
 
一、一致性Hash是什么？
 
 
 
一致性哈希算法在1997年由麻省理工学院提出，是一种特殊的哈希算法，目的是解决分布式缓存的问题。 在移除或者添加一个服务器时，能够尽可能小地改变已存在的服务请求与处理请求服务器之间的映射关系。一致性哈希解决了简单哈希算法在分布式哈希表( Distributed Hash Table，DHT) 中存在的动态伸缩等问题
 
 
一致性哈希算法将整个哈希值空间映射成一个虚拟的圆环，整个哈希空间的取值范围为0—$2^{32}$-1。整个空间按顺时针方向组织。0—$2^{32}$在零点中方向重合。接下来使用Hash算法对服务请求进行映射，将服务请求使用哈希算法算出对应的hash值，然后根据hash值的位置沿圆环顺时针查找，第一台遇到的服务器就是所对应的处理请求服务器。当增加一台新的服务器，受影响的数据仅仅是新添加的服务器到其环空间中前一台的服务器（也就是顺着逆时针方向遇到的第一台服务器）之间的数据，其他都不会受到影响。综上所述，一致性哈希算法对于节点的增减都只需重定位环空间中的一小部分数据，具有较好的容错性和可扩展性;
 
 
那么在分表应用中，如下图，我们先对table1、table2、table3、table4进行hash计算得到key1、key2、key3、key4并映射到范围为0—$2^{32}$-1的环中；加入此时我们是通过id进行分表操作，那么在存储时，我们先对id进行hash计算得出hahs值（hash(id1)），得到的值沿圆环顺时针查找遇到的第一个表节点，即是数据存储的真实表结点；接下来我们看下在Sharding-jdbc中的实际应用
 
 
二、使用步骤
 
1.一致性hash算法
 
ConsistentHashAlgorithm
 
public class ConsistentHashAlgorithm {


    //虚拟节点，key表示虚拟节点的hash值，value表示虚拟节点的名称
    @Getter
    private SortedMap<Long, String> virtualNodes = new TreeMap<>();

	//当节点的数目很少时，容易造成数据的分布不均，所以增加虚拟节点来平均数据分布
    //虚拟节点的数目；虚拟节点的生成主要是用来让数据尽量均匀分布
    //虚拟节点是真实节点的不同映射而已
    //比如真实节点user1的hash值为100，那么我们增加3个虚拟节点user1-1、user1-2、user1-3，分别计算出来的hash值可能就为200，345，500；通过这种方式来将节点分布均匀
    private static final int VIRTUAL_NODES = 3;


    public ConsistentHashAlgorithm() {
    }


    public ConsistentHashAlgorithm(SortedMap<Long, String> virtualTableNodes, Collection<String> tableNodes) {
        if (Objects.isNull(virtualTableNodes)) {
            virtualTableNodes = initNodesToHashLoop(tableNodes);
        }

        this.virtualNodes = virtualTableNodes;
    }

    public SortedMap<Long, String> initNodesToHashLoop(Collection<String> tableNodes) {
        SortedMap<Long, String> virtualTableNodes = new TreeMap<>();
        for (String node : tableNodes) {
            for (int i = 0; i < VIRTUAL_NODES; i++) {
                String s = String.valueOf(i);
                String virtualNodeName = node + "-VN" + s;
                long hash = getHash(virtualNodeName);
               
                virtualTableNodes.put(hash, virtualNodeName);
            }
        }

        return virtualTableNodes;
    }

    /**
     * 通过计算key的hash
     * 计算映射的表节点
     *
     * @param key
     * @return
     */
    public String getTableNode(String key) {
        String virtualNode = getVirtualTableNode(key);
        //虚拟节点名称截取后获取真实节点
        if (StringUtils.isNotBlank(virtualNode)) {
            return virtualNode.substring(0, virtualNode.indexOf("-"));
        }
        return null;
    }

    /**
     * 获取虚拟节点
     * @param key
     * @return
     */
    public String getVirtualTableNode(String key) {
        long hash = getHash(key);
        // 得到大于该Hash值的所有Map
        SortedMap<Long, String> subMap = virtualNodes.tailMap(hash);
        String virtualNode;
        if (subMap.isEmpty()) {
            //如果没有比该key的hash值大的，则从第一个node开始
            Long i = virtualNodes.firstKey();
            //返回对应的服务器
            virtualNode = virtualNodes.get(i);
        } else {
            //第一个Key就是顺时针过去离node最近的那个结点
            Long i = subMap.firstKey();
            //返回对应的服务器
            virtualNode = subMap.get(i);
        }

        return virtualNode;
    }

    /**
     * 使用FNV1_32_HASH算法计算key的Hash值
     *
     * @param key
     * @return
     */
    public long getHash(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;
    }

}
 
2.初始化表结点，并映射到hash环
 
该步骤会在应用启动时初始化分表的表结点，提前进行hash计算
 
InitTableNodesToHashLoop
 
public class InitTableNodesToHashLoop {

    @Resource
    private ShardingDataSource shardingDataSource;

    @Getter
    private HashMap<String, SortedMap<Long, String>> tableVirtualNodes = new HashMap<>();

    @PostConstruct
    public void init() {
        try {
            ShardingRule rule = shardingDataSource.getRuntimeContext().getRule();
            Collection<TableRule> tableRules = rule.getTableRules();
            ConsistentHashAlgorithm consistentHashAlgorithm = new ConsistentHashAlgorithm();
            for (TableRule tableRule : tableRules) {
                String logicTable = tableRule.getLogicTable();

                tableVirtualNodes.put(logicTable,
                        consistentHashAlgorithm.initNodesToHashLoop(
                                tableRule.getActualDataNodes()
                                        .stream()
                                        .map(DataNode::getTableName)
                                        .collect(Collectors.toList()))
                );
            }
        } catch (Exception e) {
            log.error("分表节点初始化失败 {}", e);
        }
    }
}
 
3.创建分表算法
 
ConsistentShardingAlgorithm
 
public class ConsistentShardingAlgorithm
        implements PreciseShardingAlgorithm<Long>, RangeShardingAlgorithm<Long> {

    /**
     * 精确分片
     * 一致性hash算法
     */
    @Override
    public String doSharding(Collection<String> availableTargetNames, PreciseShardingValue<Long> shardingValue) {

		//获取已经初始化的分表节点
        InitTableNodesToHashLoop initTableNodesToHashLoop =
                SpringContextUtils.getBean(InitTableNodesToHashLoop.class);
        if (CollectionUtils.isEmpty(availableTargetNames)) {
            return shardingValue.getLogicTableName();
        }

        //这里主要为了兼容当联表查询时，如果两个表非关联表则
        //当对副表分表时shardingValue这里传递进来的依然是主表的名称，
        //但availableTargetNames中确是副表名称，所有这里要从availableTargetNames中匹配真实表
        ArrayList<String> availableTargetNameList = new ArrayList<>(availableTargetNames);
        String logicTableName = availableTargetNameList.get(0).replaceAll("[^(a-zA-Z_)]", "");
        SortedMap<Long, String> tableHashNode =
                initTableNodesToHashLoop.getTableVirtualNodes().get(logicTableName);

        ConsistentHashAlgorithm consistentHashAlgorithm = new ConsistentHashAlgorithm(tableHashNode,
                availableTargetNames);

        return consistentHashAlgorithm.getTableNode(String.valueOf(shardingValue.getValue()));
    }

    /**
     * 范围查询规则
     * 可以根据实际场景进行修改
     * Sharding.
     *
     * @param availableTargetNames available data sources or tables's names
     * @param shardingValue        sharding value
     * @return sharding results for data sources or tables's names
     */
    @Override
    public Collection<String> doSharding(Collection<String> availableTargetNames, RangeShardingValue<Long> shardingValue) {
        return availableTargetNames;
    }
}
 
4.更改配置
 
tables:
   t_user:  #t_user表
     key-generator-column-name: id  #主键
     actual-data-nodes: ds0.t_user${0..39}    #数据节点,均匀分布
     table-strategy:  #分表策略使用一致性hash算法
       standard:
         sharding-column: id
         precise-algorithm-class-name: com.none.sharding.infrastruc.shardingAlgorithm.ConsistentShardingAlgorithm
 
总结
 
以上即是一致性hash算法在分表分库中的实际应用；虽然一致性hash算法能在节点伸缩的时候尽量减少数据的迁移，但是当虚拟节点数量很多时依然会造成不少数据迁移，所以前期进行规划时一定要考虑虚拟节点的倍数设置。
 
Demo地址：Github