Redis高可拓展-分片技术

0.前言

Redis提供主从复制和哨兵集群机制，搭建主从架构来保证高可用。
如果海量数据+高并发+高可用场景，该怎么办？
Redis cluster，主要是针对海量数据+高并发+高可用的场景。Redis cluster 支撑 N 个 Redis master node，每个 master node 都可以挂载多个 slave node。这样整个 Redis 就可以横向扩容了。如果你要支撑更大数据量的缓存，那就横向扩容更多的 master 节点，每个 master 节点就能存放更多的数据了。

1.Redis Cluster介绍

• 自动将数据进行分片，每个 master 上放一部分数据
• 提供内置的高可用支持，部分 master 不可用时，还是可以继续工作的

在 Redis cluster 架构下，每个 Redis 要放开两个端口号，比如一个是 6379，另外一个就是 加 1w 的端口号，比如 16379。
16379 端口号是用来进行节点间通信的，也就是 cluster bus 的东西，cluster bus 的通信，用来进行故障检测、配置更新、故障转移授权。cluster bus 用了另外一种二进制的协议， gossip 协议，用于节点间进行高效的数据交换，占用更少的网络带宽和处理时间。

2.节点间通信机制

基本通信机制

集群元数据的维护有两种方式：

• 集中式
• Gossip 协议

Redis cluster 节点间采用 gossip 协议进行通信。

集中式

集中式是将集群元数据（节点信息、故障等等）集中存储在某个节点上。集中式元数据集中存储的一个典型代表，就是大数据领域的 storm 。它是分布式的大数据实时计算引擎，是集中式的元数据存储的结构，底层基于 zookeeper（分布式协调的中间件）对所有元数据进行存储维护。

优缺点

优点：

• 元数据的读取和更新，时效性非常好，一旦元数据出现了变更，就立即更新到集中式的存储中，其它节点读取的时候就可以感知到；

缺点：

• 所有的元数据的更新压力全部集中在一个地方，可能会导致元数据的存储有压力。

Gossip协议

gossip 协议，所有节点都持有一份元数据，不同的节点如果出现了元数据的变更，就不断将元数据发送给其它的节点，让其它节点也进行元数据的变更。

优缺点

优点：

• 元数据的更新比较分散，不是集中在一个地方，更新请求会陆陆续续打到所有节点上去更新，降低了压力

缺点：

• 元数据的更新有延时，可能导致集群中的一些操作会有一些滞后

3.分布式选址算法

既然Redis部署了多个Cluster，那么必然涉及访问哪一个节点的问题，即分布式选址。

在动态变化的Cache环境中，判定哈希算法好坏的四个定义:

• 平衡性(Balance): 平衡性是指哈希的结果能够尽可能分布到所有的分片中去，这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。
• 单调性(Monotonicity): 单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。
• 分散性(Spread): 在分布式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。
• 负载(Load): 负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同 的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。

通常，有以下几种选址算法：

• hash 算法（大量缓存重建）
• 一致性 hash 算法（自动缓存迁移）+ 虚拟节点（自动负载均衡）
• Redis cluster 的 hash slot 算法

hash算法

对一个key，先计算hash数值，然后对节点数目取模，随后拿这个结果去访问对应的master。

局限性

但是，当某个master挂掉后，节点数目就要改变，导致大量的请求无法获得正确有效的数据，甚至缓存有宕机风险。

一致性hash算法

hash环解决单调性问题、虚拟节点解决不平衡问题。

为了解决传统hash的单调性问题，一致性hash引入了hash环的概念：

hash环

一致性 hash 算法将整个 hash 值空间组织成一个虚拟的圆环，整个空间按顺时针方向组织，下一步将各个 master 节点（使用服务器的 ip 或主机名）进行 hash。这样就能确定每个节点在其哈希环上的位置。
来了一个 key，首先计算 hash 值，并确定此数据在环上的位置，从此位置沿环顺时针“行走”，遇到的第一个 master 节点（顺时针第一个）就是 key 所在位置。

在一致性哈希算法中，如果一个节点挂了，受影响的数据仅仅是此节点到环空间前一个节点（沿着逆时针方向行走遇到的第一个节点）之间的数据，其它不受影响。增加一个节点也同理。
不平衡问题：
如果上图中master-2挂掉了，那么key-1、key-4、key-5都将打入master-3，造成缓存热点问题。

虚拟节点

为了解决这种热点问题，一致性 hash 算法引入了虚拟节点机制，即对每一个节点计算多个 hash，每个计算结果位置都放置一个虚拟节点。这样就实现了数据的均匀分布，负载均衡。

如果，master-3机器节点挂了，则：

• key-3映射到v-2-2，即master-2
• key-4映射到v-1-1，即master-1

某个节点宕机之后，存储及流量压力并没有全部转移到某台机器上，而是分散到了多台节点上。解决了节点宕机可能存在的雪崩问题。
当物理节点多的时候，虚拟节点多，这个的雪崩可能就越小。

Redis hash slot算法

Redis-cluster没有使用一致性hash，而是引入了哈希槽的概念。

• Redis-cluster中有16384(即2的14次方）个哈希槽，每个key通过CRC16校验后对16384取模来决定放置哪个槽。Cluster中的每个节点负责一部分hash槽（hash slot）。
• Redis cluster 中每个 master 都会持有部分 slot，比如有 3 个 master，那么可能每个 master 持有 5000 多个 hash slot。
• hash slot 让 node 的增加和移除很简单，增加一个 master，就将其他 master 的 hash slot 移动部分过去，减少一个 master，就将它的 hash slot 移动到其他 master 上去。移动 hash slot 的成本是非常低的。
• 客户端的 api，可以对指定的数据，让他们走同一个 hash slot，通过 hash tag 来实现。

如果，master-2挂了，直接将master-2中的slot移动到master-1、master-3即可。

为何16384?

https://github.com/redis/redis/issues/2576

The reason is:

1. Normal heartbeat packets carry the full configuration of a node, that can be replaced in an idempotent way with the old in order to update an old config. This means they contain the slots configuration for a node, in raw form, that uses 2k of space with16k slots, but would use a prohibitive 8k of space using 65k slots.
2. At the same time it is unlikely that Redis Cluster would scale to more than 1000 mater nodes because of other design tradeoffs.

So 16k was in the right range to ensure enough slots per master with a max of 1000 maters, but a small enough number to propagate the slot configuration as a raw bitmap easily. Note that in small clusters the bitmap would be hard to compress because when N is small the bitmap would have slots/N bits set that is a large percentage of bits set.

主要基于两点考虑：

1. 消息大小考虑：尽管crc16能得到65535个值，但redis选择16384个slot，是因为16384的消息只占用了2k，而65535则需要8k。
2. 集群规模设计考虑：集群设计最多支持1000个分片，16384是相对比较好的选择，需要保证在最大集群规模下，slot均匀分布场景下，每个分片平均分到的slot不至于太小。

需要注意2个问题：

1. 为什么要传全量的slot状态？
   因为分布式场景，基于状态的设计更合理，状态的传播具有幂等性
2. 为什么不考虑压缩？
   集群规模较小的场景下，每个分片负责大量的slot，很难压缩。

4.Cluster高可用与主从切换

既然是集群，那master就会有宕机风险，如何检测？如何切换主从？
非常类似哨兵集群机制！

master宕机判断

• 如果一个节点认为另外一个节点宕机，那么就是 pfail ，主观宕机。如果多个节点都认为另外一个节点宕机了，那么就是 fail ，客观宕机，跟哨兵的原理几乎一样，sdown，odown。
• 在 cluster-node-timeout 内，某个节点一直没有返回 pong ，那么就被认为 pfail 。
• 如果一个节点认为某个节点 pfail 了，那么会在 gossip ping 消息中， ping 给其他节点，如果超过半数的节点都认为 pfail 了，那么就会变成 fail

slave过滤

• 对宕机的 master node，从其所有的 slave node 中，选择一个切换成 master node。
• 检查每个 slave node 与 master node 断开连接的时间，如果超过了 cluster-node-timeout * cluster-slave-validity-factor ，那么就没有资格切换成 master

slave选举

• 每个从节点，都根据自己对 master 复制数据的 offset，来设置一个选举时间，offset 越大（复制数据越多）的从节点，选举时间越靠前，优先进行选举。
• 所有的 master node 开始 slave 选举投票，给要进行选举的 slave 进行投票，如果大部分 master node （>= N/2 + 1） 都投票给了某个从节点，那么选举通过，那个从节点可以切换成 master。
• 从节点执行主备切换，从节点切换为主节点。