Redis分布式方案及一致性Hash算法精讲

为什么Redis需要分布式

高性能

我们知道Redis本身的QPS已经很高了，但是在一些并发量非常高的情况下，性能还是会受到影响的。这个时候我们希望更多的Redis服务来分摊压力，实现负载均衡。

高可用

如果只有一个Redis服务，一但服务发生了宕机，那么所有的客户端都无法访问，会对业务造成很大的影响。另外，如果硬件损坏了，那上面的所有数据也是无法恢复的，我们需要个备份。

可扩展

第三点是出于存储的考虑，因为redis所有的数据都放在内存中，如果数据量大，很容易收到硬件的限制。比如一台Redis只能存4G的容量，但是有8G的数据要存，所以只能放两台机器，这个就是横向扩展，水平分片。

Redis分布式方案

主从复制

跟Kafka、RocketMQ、MySQL、ZooKeeper一样，Redis支持集群的架构，集群的节点有主节点和从节点之分。主节点叫master，从节点叫slave。slave会通过复制的技术，自动同步master的数据。

Redis主从复制解决了数据备份和一部分性能的问题。但是没有解决高可用的问题，在一主一从或者一主多从的情况下，如果主服务器挂了，对外提供的服务就不可用了，需要手动把从服务器切换成主服务器，然后再把剩余节点设置为它的从节点，这个比较费时，还会造成一定时间的服务不可用。

Sentinel哨兵

从Redis2.8版本起，提供了一个稳定版本的Sentinel哨兵来解决高可用的问题，它的思路是启动奇数个Sentinel的服务来监控Redis服务器来保证服务的可用性。

启动Sentinel可用用脚本启动，它本质上只是一个运行在特殊模式之下的Redis。Sentinel通过info命令得到被监听Redis机器的master，slave等信息。

./redis-sentinel ../sentinel.conf
# 或者
./redis-server ../sentinel.conf --sentinel

为了保证监控服务器的可用性，我们会对Sentinel做集群部署，Sentinel既监控所有的Redis服务，Sentinel之间也相互监控。 Sentinel本身没有主从之分，地位是平等的，只有Redis服务节点有主从之分。

Sentinel通过Raft共识算法，实现Sentinel选举，选举出一个leader来，由leader完成故障转移。Raft算法的应用很广泛，比如加密货币BTB，Spring Cloud注册中心Consul也用到了Raft算法。Raft算法的核心思想是：先到先得，少数服从多数。Sentinel的Raft实现跟原生的算法是有所区别的，但是大体思想一致。 Raft算法演示：thesecretlivesofdata.com/raft/ 。

无论Jedis还是Spring Boot（2.x版本默认是Lettuce），都只需要配置全部的哨兵地址，由哨兵返回当前的master节点地址。

哨兵的不足：主从切换的过程中会丢失数据，因为只有一个master；只能单点写，没有解决水平扩容的问题。

Redis Cluster

Redis Cluster是在Redis 3.0的版本正式推出的，用来解决分布式的需求，同时也可以实现高可用，它是去中心化的，客户端可以连接到任意一个可用的节点。Redis Cluster可以看成是由多个Redis实例组成的数据集合。客户端不需要关注数据的子集到底存储在哪个节点，只需要关注这个集合整体。

下面就是一个三主三从 Redis Cluster架构：

Redis创建了16384个槽（slot），每个节点负责一定区间的slot。比如Node1负责0-5460，Node2负责5461-10922，Node3负责10923-16383。

对象分布到Redis节点的时候，首先是对Key用CRC16算法计算再%16384，得到一个slot的值，数据落到负责这个slot的Redis节点上。 查看Key属于哪个slot：

redis>cluster keyslot jack

key与slot的关系是永远不会变的，会变的只有slot和Redis节点的关系。

我们知道key通过CRC16算法取模后会分布在不同的节点，如果想让很多个key同时落在同一个节点怎么办呢，只需要在key里面加入{hash tag}即可。Redis在计算槽编号的时候只会获取{}之间的字符串进行槽编号计算，如下所示：

user{666}base=...
user{666}fin=...

主从切换过程：

当slave发现自己的master变成FAIL状态时，便尝试进行Failover，以期成为新的master。由于挂掉的master可能会有多个slave，从而存在多个slave竞争成为master节点的过程，其过程如下：

1. slave发现自己的master变成FAIL
2. 将自己记录的集群currentEpoch加1，并广播FAILOVER_AUTH_REQUEST信息
3. 其他节点收到该信息，只有master响应，判断请求者的合法性，并发送FAILOVER_AUTH_ACK，对每一个epoch只发送一次ack
4. 尝试failover的slave收集FAILOVER_AUTH_ACK
5. 超过半数后变成新的Master
6. 广播Pong消息通知其他集群节点 比如三个小的主从A,B,C组成的集群，A的master挂了，A的两个小弟发起选举，结果B的master投给A的小弟A1，C的master投给了A的小弟A2，这样就会发起第二次选举，选举轮次标记+1继续上面的流程。事实上从节点并不是在主节点一进入 FAIL 状态就马上尝试发起选举，而是有一定延迟，一定的延迟确保我们等待FAIL状态在集群中传播，slave如果立即尝试选举，其它masters或许尚未意识到FAIL状态，可能会拒绝投票。

Redis Cluster特点

1. 无中心结构。
2. 数据按照slot存储分布在多个节点，节点间数据共享，可动态调整数据分布。
3. 可扩展性，可线性扩展到1000个节点（官网推荐不超过1000个），节点可动态添加或删除。
4. 高可用性，部分节点不可用时，集群仍可用。通过增加Slave做standby数据副本，能够实现故障自动failover，节点之间通过gossip协议交换状态信息，用投票机制完成Slave到Master的角色提升。
5. 降低运维成本，提高系统的扩展性和可用性。

至此，三种Redis的分布式方案介绍完了，Redis Cluster既能实现主从的角色分配，又能够实现主从切换，相当于集成了Replication和Sentinel的功能。

Redis分片方案

一共有三种方案，第一种是在客户端实现相关的逻辑，例如用取模或者一致性哈希对key进行分片，查询和修改都先判断key的路由。

第二种是把分片处理的逻辑抽取出来，运行一个独立的代理服务，客户端连接到这个代理服务，代理服务做请求转发。

第三种是基于服务端实现的，就是上面介绍的Redis Cluster。

客户端

客户端我们以Jedis为例，Jedis有几种连接池，其中有一种支持分片，就是ShardedJedisPool。现在我们来做个实验，有两个Redis的节点，通过JedisShardInfo往里面set 100个key。

public class ShardingTest {
    public static void main(String[] args) {
        JedisPoolConfig poolConfig = new JedisPoolConfig();

        // Redis服务器
        JedisShardInfo shardInfo1 = new JedisShardInfo("127.0.0.1", 6379);
        JedisShardInfo shardInfo2 = new JedisShardInfo("192.168.8.205", 6379);

        // 连接池
        List<JedisShardInfo> infoList = Arrays.asList(shardInfo1, shardInfo2);
        ShardedJedisPool jedisPool = new ShardedJedisPool(poolConfig, infoList);

        ShardedJedis jedis = null;
        try {
            jedis = jedisPool.getResource();
            for (int i = 0; i < 100; i++) {
                jedis.set("k" + i, "" + i);
            }
            for (int i = 0; i < 100; i++) {
                Client client = jedis.getShard("k" + i).getClient();
                System.out.println("取到值：" + jedis.get("k" + i) + "，" + "当前key位于：" + client.getHost() + ":" + client.getPort());
            }
        } finally {
            if (jedis != null) {
                jedis.close();
            }
        }
    }
}

源码在：com/xhj/jedis/shard/ShardingTest.java

最后的结果通过dbsize命令发现，一台服务器有44个key，一台服务器有56个key。从结果可以发现确实是做到了负载均衡，那具体是怎么做到的呢？我们猜想是通过哈希取模，hash(key)%N，根据余数，决定映射到哪一个节点。这种方式比较简单，属于静态的分片规则，但是一但节点数量发生了变化（新增或者减少），由于取模N发生了变化，数据需要重新分布。为了解决这个问题，我们又有了一致性哈希算法，ShardedJedisPool实际上用的就是一致性哈希算法。

一致性哈希算法

接下来介绍一致性哈希算法，我们把所有的哈希值空间组织成一个虚拟的圆环（哈希环），整个空间按顺时针方向组织。因为是环形空间，0和2^32-1是重叠的。

假设我们有四台机器，我们先根据机器的名称或者IP计算哈希值，然后分布到哈希环中（粉色圆圈），如下图所示：

现在有四个请求要set或者get，我们对key进行哈希计算，得到哈希环中的位置（蓝色圆圈），沿哈希环顺时针找到的第一个Node，就是数据存储的节点。

新增节点5，只影响一部分数据

删除节点1，只影响一部分数据

一致性哈希算法解决了动态增减节点时，所有数据都需要重新分布的问题，它只会影响到下一个相邻的节点，对其他节点没有影响。但是这样的一致性算法还是有缺点，就是节点不一定是均匀的分布的，特别是在节点数比较少的情况下，这是节点1的压力很大，解决这个问题还需要引入虚拟节点。

Node1引入了两个虚拟节点，Node2引入了两个虚拟节点，这时候的数据分布将是很均匀的。

一致性哈希算法在分布式系统中，负载均衡、分库分表都有所应用，跟LRU一样，是一个很基础的算法。那么在Java代码中我们是如何实现的，哈希环是一个什么数据结构？虚拟节点又怎么实现？

我们点开Jedis的源码，在redis.clients.util.Sharded.initialize()方法中，Redis的节点被放到了一颗红黑树TreeMap中。

private void initialize(List<S> shards) {
  //创建一颗红黑树
  nodes = new TreeMap<Long, S>();
  //for循环Redis节点
  for (int i = 0; i != shards.size(); ++i) {
    final S shardInfo = shards.get(i);
    //为每个节点创建160个虚拟节点，放入红黑树中
    if (shardInfo.getName() == null) for (int n = 0; n < 160 * shardInfo.getWeight(); n++) {
      //按名字hash
      nodes.put(this.algo.hash("SHARD-" + i + "-NODE-" + n), shardInfo);
    }
    else for (int n = 0; n < 160 * shardInfo.getWeight(); n++) {
      //按名字hash
      nodes.put(this.algo.hash(shardInfo.getName() + "*" + shardInfo.getWeight() + n), shardInfo);
    }
    //把redis节点信息放到map中
    resources.put(shardInfo, shardInfo.createResource());
  }
}

当我们有个key需要get或者set的时候，我们需要知道具体落在哪个节点。

public R getShard(String key) {
  //从resources里面拿出具体的节点
  return resources.get(getShardInfo(key));
}

public S getShardInfo(byte[] key) {
  //这里把key进行hash，然后从红黑树上摘下比该值大的第一个节点信息
  SortedMap<Long, S> tail = nodes.tailMap(algo.hash(key));
  if (tail.isEmpty()) {
    //没有比它大的了，直接从node中取出
    return nodes.get(nodes.firstKey());
  }
  //否则返回第一个比它大的节点信息
  return tail.get(tail.firstKey());
}

这里以Jedis的源码介绍一致性哈希算法，在别的使用场景中代码的写法也是大同小异的，在数据结构的选取上：

1. 最简单的实现是采用一个有序的list，每次从第0个元素开始查找，直到找到第一个比数据的hash值大的节点，则该数据属于该节点对应的服务器。时间复杂度为O(n)。
2. 采用二叉查找树，时间复杂度为O(log n)。

我们不能简单地使用二叉查找树，因为可能出现不平衡的情况。平衡二叉查找树有AVL树、红黑树等，这里使用红黑树，选用红黑树的原因有两点：

1. 红黑树主要的作用是用于存储有序的数据，这其实和第一种解决方案的思路又不谋而合了，但是它的效率非常高。
2. JDK里面提供了红黑树的代码实现TreeMap和TreeSet。

代理Proxy

使用ShardedJedisPool之类的客户端分片代码的优势是配置简单，不依赖其他中间件，分区的逻辑可以自己定，比较灵活，缺点就是不能实现动态的服务增减，每个客户端需要自行维护分片策略，存在重复代码。所以这时候我们的思路就是把分片的代码抽取出来，做成一个公共服务，所有的客户端都连接到这个代理层，由代理层来进行转发。

架构图如下所示，跟数据库分表分库中间件的Mycat的工作层次是一样的。典型的代理分区方案有Twitter开源的Twemproxy和国内的豌豆荚开源的Codis。

但是会有一些问题，出现故障不能自动转移，架构复杂，需要借助其他组件Zookeeper（或者etcd/本地文件），现在已经很少使用了，可以说是在Redis Cluster出现之前的一个过渡方案，所以这里不详细介绍了。

Redis Cluster

Redis Cluster上文已经介绍过了，天生的集成了数据分片功能，可以将数据分配到不同的实例上。这是最完美的Redis分布式方案。

因为key和slot的关系是永远不会变的，当新增了节点的时候，需要把原有的slot分配给新的节点负责，并且把相关的数据迁移过来。

添加一个新节点192.168.10.219:6378

redis-cli --cluster add-node 192.168.10.219:6378 192.168.10.219:6379

新增的节点没有哈希槽，不能分布数据，在原来的任意一个节点上执行：

redis-cli --cluster reshard 192.168.10.219:6379

输入需要分配的哈希槽的数量（比如500），和哈希槽的来源节点（可以输入all或者id）。

本文源码在：github.com/xuhaoj/redi… ，感谢大家的收看。