Redis集群（Cluster）

Redis Cluster是一种服务器Sharding技术，Redis3.0以后版本正式提供支持。主从复制和哨兵机制保障了高可用。虽然多个Slave扩展了读的能力，但是写能力和存储能力是无法进行扩展，就只能是Master节点能够承载的上限。如果面对海量数据那么必然需要构建Master（主节点分片)之间的集群，同时必然需要吸收高可用（主从复制和哨兵机制）能力，即每个master分片节点还需要有slave节点，这是分布式系统中典型的纵向扩展（集群的分片技术）的体现。所以在Redis 3.0版本中对应的设计就是Redis Cluster。

复制复制复制Read/WriteRead/WriteRead/WriteReadOnlyReadOnlyReadOnlySlave3Master3Slave2Master2Slave1Master1Client1Client2Client3Client4

简单说RedisCluster有这些特点：

  1. Redis集群支持多个Master，每个Master又可以挂载多个Slave。
  2. Redis Cluster自带了Sentinel的故障转移机制内置了高可用的支持，所以无需再去使用哨兵功能。
  3. 客户端和Redis节点连接不不再需要连接集群中所有的节点，只需要任意连接集群中的一个可用节点即可。
  4. 哈希槽(Hash Slot)负责分配到各个物理服务节点，由对应的集群来负责维护节点、插槽和数据之间的关系。

Redis Cluster的设计目标是什么?

  • 高性能和线性可扩展性：可扩展至1000个节点。没有代理，集群节点间使用异步复制，没有归并操作(merge operations on values)。
  • 可接受的写入安全程度：系统尝试(采用best-effort方式)保留所有连接到master节点的client发起的写操作。通常会有一个小的时间窗，时间窗内的已确认写操作可能丢失(即，在发生FAILOVER之前的小段时间窗内的写操作可能在FAILOVER中丢失)。而在(网络)分区故障下，对少数派master的写入，发生写丢失的时间窗会很大。
  • 可用性：Redis Cluster在以下场景下集群总是可用：大部分master节点可用，并且对少部分不可用的master，每一个master至少有一个当前可用的slave。更进一步，通过使用replicas migration技术，当前没有slave的master会从当前拥有多个slave的master接受到一个新slave来确保可用性。

集群算法-分片-哈希槽(Hash Slot)

Redis集群的槽位Slot

Redis Cluster没有使用一致性hash，而是引入了哈希槽的概念。Redis Cluster中有16384(214)个哈希槽，每个key通过CRC16校验后对16383取模来决定放置哪个槽。Cluster中的每个节点负责一部分hash槽（hash slot）。比如集群中存在三个节点，则可能存在的一种分配如下：

  • 节点A包含0到5500号哈希槽；
  • 节点B包含5501到11000号哈希槽；
  • 节点C包含11001 到 16384号哈希槽。
每个Key都通过计算得到对应的Slot槽位复制复制复制0-55005501-1100011001-16384Slave3Master3Slave2Master2Slave1Master1HASH_SLOT = CRC16(key) mod 16380-16383

Redis集群的分片

使用Redis集群时会将存储的数据分散到多台Redis机器上，这称为分片。简单说就是集群中的每个Redis实例都被认为是整体数据的一个分片。为了找到给定key的分片，需要对key进行CRC16(key)算法处理并通过对总分片数量取模。然后使用确定性Hash函数，这意味着给定的key将多次始终映射到同一分片，也就可以推断将来读取特定key的位置。

分片和哈希槽的优势

这种结构很容易添加或者删除节点，比如有三个节点A，B，C：

  • 如果现在要添加一台节点D，则需要从节点A，B，C上得到部分槽位到D上。
  • 如果现在要移除节点A，那就需要把A的槽位转移到B和C上。然后把没有任何槽位的A移除即可。

由于从一个节点将哈希槽转移到另外的节点并不会停止服务，所以无论添加还是删除甚至改变某个节点的哈希槽的数量都不会造成集群的不可用。

三种Slot槽位映射解决方案

Hash取余分区

假设有3个节点，客户端每次读写操作都是根据公式（hash(key)/节点数）计算出Hash值，用来决定数据映射到哪一个节点上。

这样做的优点和缺点有：

  • 优点：只需要预估好数据并规划好节点，就能保证一段时间内的数据支撑。使用HASH算法让固定的一部分请求落到同一个节点上，这样每个节点就会固定处理一部分请求，起到负载均衡的作用。
  • 缺点：这样做有一个非常明显的缺点，那就是扩容和缩容非常麻烦。每次不管是扩容还是缩容只要节点数量变化，映射关系就必须要重新计算。再比如某个节点挂了，由于节点数量变化，则会导致HASH取余全部数据重新洗牌。
RedisClusterReadORWriteRedisRedisRedisClienthash(key)/3

一致性Hash算法分区

一致性Hash算法是麻省理工学院在1997年提出的，目的就是为了解决分布式缓存数据变动和映射问题。

使用一致性Hash方案目的是为了当服务器发生变动的时候，尽量减少影响客户端到服务器的映射关系。

一致性Hash环

一致性Hash算法必然有个Hash函数按照算法产生Hash值，这个算法所有可能产生的Hash值回构成一个全量集，这个集合可以成为一个Hash空间==[0,232-1]==,这是一个线性空间，但是在算法中，通过适当的逻辑控制将它首尾相连，这样它就成为了一个环形空间。

一致性Hash算法也是按照取模的方法，上面的Hash取余是对节点数量进行取模。而一致性Hash算法是对232取模。简单说就是一致性Hash算法将整个Hash值空间组织成一个闭环：假如某个Hash函数H的值空间为[0,232-1] (即Hash值是一个32位无符号整形)，整个Hash环如下图：

一致性哈希算法

整个空间按顺时针方向组织，圆环的正上方的点是0，这个点右侧第一个点代表1，以此类推，2，3，4…直到232-1。这个有232个点组成的圆环就称为Hash环。

服务器IP节点映射

将集群中的每个节点IP映射到Hash环上的某一个位置：具体可以使用节点的IP或者主机名作为关键字进行Hash，这样每个节点就能确定其在Hash环上的位置。

一致性Hash算法节点映射

key落到节点的规则

当需要存储一个KV键值对的时候，首先计算key的Hash值（hash(key)），将这个key使用相同的Hash函数计算出Hash值并确定此数据在Hash环上的位置，从此位置开始顺时针查找，查询到的第一个有效节点就是该key应该落到的位置。

一致性Hash方案的优点和缺点

优点：

  • 容错性：假设Hash环上某一个节点挂了，那个其余大部分节点不会收到影响，受到影响的仅仅只有挂掉的这个节点和这个节点之前的一个节点（Hash换上逆时针数第一个节点）之间的数据，且这些数据还会转移到下一个节点存储（挂掉的节点顺时针的下一个节点）。
  • 扩展性：当业务数据量增加后需要增加节点，受到影响的也仅仅只有增加的这个节点和它在Hash换上逆时针数第一个节点之间的数据，并不回导致所有数据全部洗牌。

缺点：

  • 数据倾斜问题：当Hash环中的节点太少的时候，容易因为节点分布不均匀从而造成数据倾斜（即有大部分数据都落在某一个节点上）问题。

哈希槽分区

哈希槽实际就是一个数组，数组[0,214-1]形成Hash Slot空间。一个集群只能由16384个槽位[0,214-1]。这些槽会分配给集群中的所有主节点，分配策略没有要求。集群会记录节点和槽的对应关系，解决了节点和槽的关系后，接下来就需要对Key求哈希值，然后对16384取模（HASH_SLOT = CRC6(key) mod 16384）。以槽为单位移动数据，因为槽的数目是固定的，处理起来比较容易，这样数据移动问题就解决了。

哈希槽的作用

主要解决均匀分配的问题，在数据和节点之间又加入了一层（哈希槽），用于管理数据和节点之间的关系，现在就相当于节点上放的是槽，槽里面放的是数据。

数据槽Redis

槽解决的是粒度问题，相当于把粒度变大了，这样便于数据移动。哈希解决的是映射问题，使用Key的哈希值来计算所在的槽，便于数据分配。

哈希槽计算

Redis集群中内置了16384个哈希槽，Redis会根据节点数量大致均等的将哈希槽映射到不同节点上。当写入数据时，Redis先对key使用CRC16算法算出一个结果，然后使用该结果对16384取模[CRC16(key) % 16384]，这样每个可以都会对应一个编号在[0,16384]之间的哈希槽，也就是映射到某一个节点上。

请求重定向

Redis集群采用去中心化的架构，集群的主节点各自负责一部分槽，客户端如何确定key到底会映射到哪个节点上呢？

在集群模式下，节点对请求的处理过程如下：

  • 检查当前key是否存在当前NODE？
  • 通过crc16(key)/16384计算出Slot。
  • 查询负责该Slot的节点，得到节点指针。
  • 该指针与自身节点比较。
  • 若Slot不是由自身负责，则返回MOVED重定向。
  • 若Slot由自身负责，且key在Slot中，则返回该key对应结果。
  • 若key不存在此slot中，检查该slot是否正在迁出（MIGRATING）？
  • 若key正在迁出，返回ASK错误重定向客户端到迁移的目的服务器上
  • 若Slot未迁出，检查Slot是否导入中？
  • 若Slot导入中且有ASKING标记，则直接操作
  • 否则返回MOVED重定向

这个过程中有两点需要具体理解下：MOVED重定向和ASK重定向。

ASK与MOVED虽然都是对客户端的重定向控制，但是有着本质区别：

  • ASK重定向说明集群正在进行slot数据迁移，客户端无法知道什么时候迁移 完成，因此只能是临时性的重定向，客户端不会更新slots缓存
  • 但是MOVED重定向说明键对应的槽已经明确指定到新的节点，因此需要更新slots缓存

MOVED重定向

1.发送命令YESNO4.重定向发送命令客户端任意节点2.计算Slot和对应节点3.判断是否指向自身3.2执行命令3.1回复MOVED目标节点5.执行命令
  • Slot命中：直接执行命令并返回结果
  • Slot没有命中：即当前命令所请求的键不在当前请求的节点中，则当前节点会向客户端发送一个Moved重定向，客户端根据Moved重定向所包含的内容找到目标节点，再一次发送命令。

ASK 重定向

Ask重定向发生于集群伸缩时，集群伸缩会导致槽迁移，当我们去源节点访问时，此时数据已经可能已经迁移到了目标节点，使用Ask重定向来解决此种情况。

集群迁移。。。1.发送命令/2.回复ASK转向3.Asking/4.发送命令/5.返回结果节点2节点1客户端

Smart客户端

ASK和MOVED重定向机制使得客户端的实现更加复杂。使用Smart客户端（JedisCluster）来减低复杂性，追求更好的性能。客户端内部负责计算/维护键-> 槽 -> 节点映射，用于快速定位目标节点。

实现原理：

  • 从集群中选取一个可运行节点，使用Cluster Slots得到槽和节点的映射关系:

    127.0.0.1:6371> Cluster Slots
1) 1) (integer) 0
   2) (integer) 6826
   3) 1) "192.168.64.2"
      2) (integer) 6371
2) 1) (integer) 6827
   2) (integer) 10922
   3) 1) "192.168.64.2"
      2) (integer) 6372
3) 1) (integer) 10923
   2) (integer) 12287
   3) 1) "192.168.64.2"
      2) (integer) 6371
4) 1) (integer) 12288
   2) (integer) 16383
   3) 1) "192.168.64.2"
      2) (integer) 6373

  • 将上述映射关系存到本地，通过映射关系就可以直接对目标节点进行操作（CRC16(key) -> slot -> node），很好地避免了Moved重定向，并为每个节点创建JedisPool。

故障转移（Failover）

当一个Master节点宕机后，Redis集群如何进行故障转移呢？

当Slave发现自己的Master变为FAIL状态时，便尝试进行Failover，来成为新的Master。而因为宕机的Master可能会有多个Slave。Failover的过程需要经过类Raft协议的过程在整个集群内达到一致，其过程如下：

  1. Slave发现自己的Master变为FAIL。
  2. 将自己记录的集群currentEpoch加1，并广播Failover Request信息。
  3. 其他节点收到该信息，只有Master响应，判断请求者的合法性，并发送FAILOVER_AUTH_ACK，对每一个epoch只发送一次ack。
  4. 尝试Failover的Slave收集FAILOVER_AUTH_ACK。
  5. 超过半数后变成新Master。
  6. 广播Pong通知其他集群节点。

FailOver

相关问题

为什么Redis集群的最大槽数时16384？

作者在GitHub上是这样说的:

  1. 普通的心跳包携带节点的完整配置，可以使用旧配置以幂等方式替换，以更新旧配置。这意味着它们包含节点的槽配置，采用16k槽的原始形式使用2k的空间，但使用65k槽会使用8k空间。
  2. 同时，由于其他设计权衡，RedisCluster不太可能扩展到超过1000个主节点。

因此，16k位于正确的范围内，确保每个主节点具有足够的槽，并且最多具有1000个主节点，但数量足够少，可以轻松地将插槽配置作为原始位图传播。请注意，在小型集群中，位图很难压缩，因为当N很小时，位图将设置的slot/N位占很大的百分比。

简单说可以是：

  1. 如果槽位是65536，发送心跳信息的消息头达到8k，发送的体积过于庞大。在消息头中最占空间的是myslots[CLUSTER_SLOTS/8]：

    1. 当槽位是65538时，这里的大小是：65536/8/1024=8kb。
    2. 当槽位是16384时，这里的大小是：16384/8/1024=2kb。

    因为每秒钟，Redis节点需要发送一定数量的Ping消息作为心跳包，如果槽位是65536，那么这个ping消息的消息头就太大了。

  2. Redis的集群主节点数量基本不可能超过1000个：

    集群节点越多，心跳包的消息体内携带的数据就越多。如果节点超过1000个，也会造成网络拥堵。因此Redis作者不建议RedisCluster的节点数量超过1000个。那这样对于节点数在1000以内的RedisCluster集群，16384个槽位足够用了。没有必要扩展到65536个。

  3. 槽位越小，节点少的情况下，压缩比例高，容易传输：

    Redis主节点的配置信息中他所负责的哈希槽是通过一张bitmap的形式来保存的，在传输过程中会对bitmap进行压缩，但是如果bitmap的填充率slot/N（节点数）很高的话，bitmap的压缩率就很低。如果节点数少很少，而哈希槽数量很多的话，bitmap的压缩率就很低。

Redis集群不保证强一致性，这意味着在特定条件下，Redis集群可能会丢掉一些被系统到的写入命令。

官方文档

Redis集群在节点间使用的是异步复制，以及last FAILOVER wins隐含合并功能(implicit merge function)（不存在合并功能，而是总是认为最近一次FAILOVER的节点是最新的）。这意味着最后被选举出的Master所包含的数据最终会替代之前Master下的所有其他备份(Replicas/Slaves)节点包含的数据。当发生分区问题时，总是会有一个时间窗内会发生写入丢失。然而，对连接到多数派Master（majority of masters）的client，以及连接到少数派Master（mimority of masters）的client，这个时间窗是不同的。

相比较连接到少数master(minority of masters)的client，对连接到多数master(majority of masters)的client发起的写入，Redis集群会更努力地尝试将其保存。 下面的场景将会导致在主分区的master上，已经确认的写入在故障期间发生丢失：

  1. 写入请求达到Master，但是当Master执行完并回复Client时，写操作可能还没有通过异步复制传播到它的Slave。如果Master在写操作抵达Slave之前宕机了，并且Master无法触达(unreachable)的时间足够长而导致了Slave节点晋升，那么这个写操作就永远地丢失了。通常很难直接观察到，因为Master尝试回复Client(写入确认)和传播写操作到Slave通常几乎是同时发生。然而，这却是真实世界中的故障方式。（不考虑返回后宕机的场景，因为宕机导致的写入丢失，在单机版Redis上同样存在，这不是redis集群引入的目的及要解决的问题）
  2. 另一种理论上可能发生写入丢失的情况是：
    1. Master因为分区原因不可用（unreachable）
    2. 该Master被某个Slave替换(FAILOVER)
    3. 一段时间后，该Master重新可用，在该OldMaster变为Slave之前，一个Client通过过期的路由表对该节点进行写入。

上述第二种情况通常难以发生，因为：

  • 少数派Master(minority master)无法与多数派Master(majority master)通信达到一定的时间后，它将拒绝写入，并且当分区恢复后，该Master在重新与多数派Master建立连接后，还将保持拒绝写入状态一小段时间来感知集群配置变化。留给Client可写入的时间窗很小。
  • 发生这种错误还有一个前提是，Client一直都在使用过期的路由表（而实际上集群因为发生了FAILOVER，已有Slave发生了晋升）。

写入少数派Master(minority side of a partition)会有一个更长的时间窗会导致数据丢失。因为如果最终导致了FAILOVER，则写入少数派Master的数据将会被多数派一侧(majority side)覆盖（在少数派Master作为Slave重新接入集群后）。

如果要发生FAILOVER，Master必须至少在NODE_TIMEOUT时间内无法被多数masters(majority of maters)连接，因此如果分区在这一时间内被修复，则不会发生写入丢失。当分区持续时间超过NODE_TIMEOUT时，所有在这段时间内对少数派Master(minority side)的写入将会丢失。然而少数派一侧(minority side)将会在NODE_TIMEOUT时间之后如果还没有连上多数派一侧，则它会立即开始拒绝写入，因此对少数派master而言，存在一个进入不可用状态的最大时间窗。在这一时间窗之外，不会再有写入被接受或丢失。

参考文章