本文由 dbaplus 社群授权转载。
Redis 是非常流行的缓存。在 Redis 升级到 3.0 版本后，升级到 集群 版本，被称之为 Redis Cluster 。在集群版本中，会将数据分成多份，被保存到多个 server 中，从而保证集群的水平扩展能力，加之每份数据保存多个副本，从而保证可用性，并且集群版本保证一定程度的 Write Safety。本文详细介绍 Redis Cluster 的实现细节，从而分析 Redis Cluster 的 Write Safety 的保证程度。
一、接口和架构
1、接口
Redis Cluster 的接口基本向前兼容，仍然是 key-value 类型。
2、架构
Redis Cluster 包含 server 和 client 两个组件。一个 Redis Cluster 可以包含多个 server，可以包含多个客户端。每个客户端可以连接任意的 server，读取写入数据。保存在 Redis Cluster 中的数据会被分成多份，分散地保存在多个 server 中，并且每一份数据也会保存多个副本。
二、实现
1、节点
在 Redis Cluster 中，数据会被保存到多个 Redis server 中，每个 Redis server 都是一个独立的进程，具有独立的 IP 和 Port，也被称之为一个 实例 ，或者叫做 节点（Node） 。Client 通过这个 IP 和 Port 连接到这个 Node。
每个节点都有个 node id ，node id 是一个全局唯一的标识，它是在集群创建时随机生成的。一个节点的 id 始终都不会变化的，但是 node 的 IP 和 port 是可以变化的。
2、Node table
一个 Redis Cluster 包含哪些节点，也就是这个集群包含哪些节点的 id，也就是 集群成员关系 ，这个信息被保存在一个表结构中，被称之为 node table 。node table 类似于:
node table 会在每个节点上都保存一份，Redis Cluster 通过 gossip 协议把 node table 复制到所有的节点。后面会继续讲述 node table 的复制。
3、集群成员关系变更
当添加一个节点或者删除一个节点时，只需要将命令发给集群中的任意一个节点，这个节点会修改本地的 node table，并且这个修改会最终复制到所有的节点上去。添加节点的命令是 CLUSTER MEET，删除节点的命令是 CLUSTER FORGET。
举例来说明：
打算搭建一个 3 个 master 节点的集群，当集群创建以前，所有 3 个节点的 node table 都只包含自己。给其中的一个节点 A 发送命令，CLUSTER MEET NodeB，节点 A 修改自己的 node table，将 NodeB 添加到自己的 node table 中，并且连接节点 B，把自己的 node table 发送给节点 B，节点 B 收到节点 A 发送过来的 node table，会更新自己的 node table，这时节点 B 就知道集群中还有节点 A 存在。
这时，给节点 A 再发送 CLUSTER MEET NodeC，节点 A 会把节点 C 添加到自己的 node table，并且把自己的 node table 复制给节点 B，节点 B 把接收到的 node table 更新自己的本地的 node table，从而知道节点 C 的加入。同样节点 A 会把自己的 node table 发给节点 C，节点 C 会更新自己本地的 node table，从而知道要加入的集群中已经存在节点 A 和节点 B。
4、槽
前面说过 Redis Cluster 会把数据分成多份，也就是把数据进行 分片 。Redis Cluster 中的每一份数据被称为 槽 （ Slot ）。Redis Cluster 将数据拆分成 16384 份，也就是说有 16384 个槽。
Redis Cluster 采用 哈希 （ Hash ）机制来拆分数据。首先，数据的 key 通过 CRC16 算法计算出一个哈希值。这个哈希值再对 16384 取余，这个余数就是槽位，被称为 hash slot 。具体的 CRC16 算法可以参看 Redis 官方文档。所有余数相同的 key 都在一个 slot 中，也就是说，一个 slot 其实就是一批 hash 余数相同的 key。
每个 hash slot 都会保存在 Redis Cluster 一个节点中。具体哪个 hash slot 被保存在哪个实例中，就形成了类似于一个 map 的数据结构，被称之为 hash slot map 。hash slot map 类似于：
与 node table 相同，hash slot map 也会在每个节点上都会保存一份，Redis Cluster 通过 gossip 协议把 hash slot map 复制到所有节点。同样，后面还会讲述 hash slot map 的复制。
《Redis 官方文档》Redis Cluster Specification, https://redis.io/topics/cluster-spec.
5、数据分片变更
要修改数据分片关系，可以连接任意一个节点，给这个节点发送 CLUSTER ADDSLOTS， CLUSTER SETSLOT， CLUSTER DELSLOT 命令，修改这个节点上的 hash slot map，该节点会把这个修改复制到所有其他节点，其他节点会用接收到的 hash slot map 更新自己的 hash slot map。
CLUSTER ADDSLOTS、CLUSTER DELSLOTS、CLUSTER SETSLOT 命令的使用如下：
CLUSTER ADDSLOTS 用来把多个 slot 分配給当前连接的节点。例如，连接到节点 A 执行：
这个命令会把 slot1、slot2、slot3 分配给节点 A。
CLUSTER DELSLOTS 用来把多个 slot 从当前连接的节点删除。例如，连接到节点 A 执行：
这个命令会把 slot1、slot2、slot3 从节点 A 上删除。
CLUSTER SETSLOT 用来把一个 slot 分配给指定的节点，可以不是当前连接的节点，另外这个命令还可以设定 MIGRATING 和 IMPORTING 两个状态，我们后面再讲。例如，连接到节点 A 执行：
这个命令会把 slot1 分配给节点 B。
6、Slave
一个 slot 会被保存多个副本，既一个 slot 会保存在多个节点上，也就是 slot 会复制到多个节点上。Redis Cluster 的复制是以节点为单位的，一个节点上的所有 slot 会采用相同的复制。
具体来说就是，其中一个节点会负责处理这个节点上所有 slot 的写操作，这个节点被称为 master ，而其余的节点被称为 slave 节点。一个 master 可以有多个 slave。在同一个节点上的所有 slot 的所有的写操作都会被从 master 节点异步复制到所有的 slave 节点。所以 slave 会具有与 master 相同的 slot。
通过 SLAVEOF 命令来设置 slave 节点。SLAVEOF 命令用来改变一个 slave 节点的复制设置。SLAVEOF 命令有两种格式：
SLAVEOF NO ONE
SLAVEOF host port
具体来讲，SLAVEOF NO ONE 命令会停止一个 slave 节点的复制，并且把这个 slave 节点变成 master 节点。SLAVEOF host port 命令会停止一个 slave 节点的复制，丢弃数据集，开始从 host 和 port 指定的新 master 节点复制。
master 和 slave 的关系会被记录在 hash slot table 中，相当于一个 slot 会映射到多个节点上，其中一个节点是 master，其他记录的节点是 slave。
加入了 master/slave 信息后的 hash slot map 类似于：
作为 hash slot map 的一部分，master/slave 信息也会通过 gossip 协议复制到集群中的每个节点。
7、Configuration
node table 和 hash slot map 这两个信息，被称之为 Configuration ，在其他的分布式系统中，也被称之为元数据。
前面我们讲过，hash slot map 和 node table 在每个节点都会保存一份，并且对这两个信息的任何改动，都会通过 gossip 协议 传播（propogate） 到所有的节点。本文我们就不继续展开 gossip 协议了，对 Redis Cluster 的 gossip 协议的实现感兴趣的同学可以参看 redis 的文档。
在某些分布式系统中，元数据被存储在一个单独的架构组件中的。Redis Cluster 并没有这样一个元数据存储的组件，而是把元数据分散的存储在所有的节点上。
hash slot map 和 node table 在集群创建时会被创建出来，并且会随着后续的集群变更（比如 failover 和扩容、缩容等运维操作，后面会讲述）而跟随着变更。变动会在一个 Node 上发起，通过 gossip 协议传播到所有其他的节点。这两个信息在所有节点都会保存，并且会最终达到一致。
8、集群创建
创建 Redis Cluster 时，首先要以 cluster 模式运行多个 redis server，redis server 运行起来后，这些 server 的 node id 就已经生成了。但是这些 redis server 并没有形成集群，也就是 server 彼此之间并不知道相互的存在。接下来运行 CLUSTER MEET 命令，让这些节点形成一个集群。但是这时集群仍然没有处于运行状态，需要分配 slot，通过 CLUSTER SLOTADD 命令把 slot 分配给具体的节点之后，集群就可以处理 client 的命令了。
9、客户端的读写操作
客户端要读取、写入数据时，虽然 client 可以连接任意 server，但是实际中，client 需要根据实际需求连接到 server 读取、写入数据。client 需要先根据 key 计算出 hash slot，连接到负责这个 hash slot 的节点进行读写操作。这样的话，client 就要需要知道 hash slot -> node 的映射关系，也就是需要知道 hash slot map。
前面讲过 hash slot map 被保存在 server 端的每个节点上。client 可以从任意节点获取 hash slot map，并且把它缓存到 client 本地，下次操作时根据本地缓存直接进行操作，但是需要处理缓存信息过期的问题，如果 client 发现 hash slot map 发生变化（即 client 读取写入数据时 server 回错误，接下来会详细讲述），会重新从 server 端获取新的 hash slot map。通过 hash slot map 可以判断某个 key 应该存在在哪个节点上，client 再连接这个节点进行读写操作。
10、MOVED Redirection
hash slot map 会发生变更，这些变更会复制到所有的节点，但是 gossip 保证的是最终复制到所有的节点，再加上 client 会缓存 hash slot map，client 可能会把某个 key 的请求发给错误的节点来处理。
错误的节点收到请求后，发现这个 key 不应该自己来处理，会给客户端返回 MOVED 的错误，在错误消息中，会告诉客户端，哪个节点应该负责这个 slot。Client 收到 MOVED 消息后，会向消息中指定的节点再次发送请求。
client 可以将 slot 的节点信息更新到本地缓存的 hash slot map 中，但是更好的方法是，重新获取完整的 hash slot map，替换本地的缓存。因为在大多数情况下，hash slot map 中的变更不仅仅只修改一个 slot。
虽然 client 按照 MOVED 消息中的节点信息重新发送请求，但是 client 仍然可能再次从新节点收到 MOVED 错误消息，因为上一个节点的 hash slot map 可能也不是最新的。但是因为 hash slot map 最终会在所有的节点上一致，所以 client 在几次收到 MOVED 错误后，最终会获取到最新的 hash slot map。
11、Failover、currentEpoch、lastVoteEpoch
当 master 发生故障宕机后，Redis Cluster 会选出一个 slave 来接替这个 master。
如果有多个 slave 存在，那么每个 slave 都可能都会发现 master 发生了宕机，并且试图把自己变成为 master，如果有多个 slave 成为 master，那么这些新 master 都会更新本地 hash slot map，把旧 master 负责的 slot 更新成自己，并且把自己对 hash slot map 的更新传播给其他的节点。这会导致 hash slot map 在节点间出现差异。
从而导致，因为所连接的节点不同，client 拿到不同的 hash slot map，对于同一个 slot，不同的 client 会连接不同的节点，最终导致节点上的数据出现差异。所以 failover 要保证，只有一个 slave 被选成新 master。
Redis Cluster 采用了类似 Raft 算法的技术来防止多个 slave 被选成 master。每个节点都会有叫做 currentEpoch、lastVoteEpoch 的两个值。在集群刚创建时，每个节点的 currentEpoch 都是 0。
当 slave 发现 master 宕机时，这个 slave 会增加 currentEpoch（即 currentEpoch++）。并且向所有的 master 发送 FAILOVER_AUTH_REQUEST 请求，请求中会携带自己 currentEpoch，master 收到 FAILOVER_AUTH_REQUEST，如果请求中的 currentEpoch 比自己的 currentEpoch 和 lastVoteEpoch 都大，则记录请求中的 currentEpoch 值到自己的 currentEpoch、lastVoteEpoch 中，并且回复 FAILOVER_AUTH_ACK 给 slave，回复中携带 master 的 currentEpoch。
所以可以看出，FAILOVER_AUTH_ACK 中的 Epoch 一定与 slave 的 currentEpoch 相同。Slave 从大多数的 master 收到 FAILOVER_AUTH_ACK 后，则成为 master。
上面的过程保证只有一个 slave 被选出，我们来举例说明。五个 master 的集群，master 节点分别是 A、B、C、D、E，A 节点有两个 slave，分别是 A1 和 A2。A 节点发生宕机，A1 增加自己的 currentEpoch=5(4+1)，A1 给所有的 master 发送 FAILOVER_AUTH_REQUEST，节点 B、C、D 收到 FAILOVER_AUTH_REQUEST，把自己的 currentEpoch 和 lastVoteEpoch 更新成 5，并且给 A1 回复 FAILOVER_AUTH_ACK，A1 赢得选举，成为新的 master。但是与此同时，A2 也发现 A 宕机，也试图选举成 master。A2 增加自己的 currentEpoch=5(4+1)，A2 给所有的 master 发送 FAILOVER_AUTH_REQUEST，但这时的 B、C、D 的 lastVoteEpoch 已经是 5,所以 B、C、D 不会给 A2 回复，E 还没有收到 A1 的请求，所以只有 E 会给 A2 回复，但是不能形成大多数，所以 A2 不能称为 master。
上面讲述的过程已经可以保证只有一个 master 被选出，但是除此之外，Redis Cluster 还做了一个优化，那就是 master 回复了一个请求后不会在给这个 master 的其他的 slave 发送回复。
12、Configuration epoch
failover 完成后，新 master 会修改 hash slot map，把相应的 slot 记录的节点改成自己，并且把这次对 hash slot map 的改动传播给其他节点。
虽然 currentEpoch 和 lastVoteEpoch 能保证每次 failover 只能有一个节点被选成新的 master，但是先后两次 failover，可能选出的两个不同的 master，但是他们对 hash slot map 的修改的传播却是异步，也就是后面一次 failover 的改动可能先于第一次 failover 的改动到达某个节点，从而导致节点间对 hash slot map 这个信息产生不一致。
Redis Cluster 通过 configEpoch 来解决这个问题。每个节点会保存一个 configEpoch 的值。相当于在 node table 中还会有一列数据叫 configEpoch，类似于下面的表：
每次 failover 完成后，新选出的 master 会用 currentEpoch 覆盖 configEpoch。Failover 的机制保证两次 failover 的新 master 一定是具有不同的 currentEpoch，并且后一次的 failover 的 currentEpoch 一定比前一次大。这样就可以保证，即便采用了 gossip 这样传播协议，仍然能够保证最后一次 failover 的 hash slot map 的变更会生效，也就是 configEpoch 更大的变更会生效，并且最终所有的节点上的 hash slot map 是一致的。
Slave 节点的 configEpoch 就是其 master 的 configEpoch。
由于 gossip 保证的 hash slot map 最终保持一致的，所以可能存在 slave 的 hash slot map 旧于 master，failover 不能基于旧的 hash slot map 基础上做变更，所以前面 failover 的过程中还需要补充一个规则要遵守：
在 FAILOVER_AUTH_REQUEST 中会携带 slave 节点的 configEpoch，如果这个 slave 的 configEpoch 比这个 slave 负责的所有 slot 的 master 的 configEpoch 中任意一个要小，则 master 不会给 slave 回复 FAILOVER_AUTH_ACK。
13、Resharding
在集群创建之后，我们还会有对 Redis cluster 做扩容、缩容、balancing 这样的运维需求，这些需求本质上都可以用 Resharding 操作解决，resharding 操作就是把 slot 在节点间重新的分布，把 slot 从一个节点转移到另外一个节点上。在 Redis Cluster 中，扩容需求实质上就是加入一个新的节点，再把一些 slot 分配到这个新节点上。
缩容需求实质上就是先把这个节点上的所有 slot 分配到其他节点上，再把这个节点从集群中移出。当节点间的流量不均衡时，我们有 balancing 这样的需求，balancing 就是把流量比较大的节点上的一些 slot 分配都流量比较少的节点上。
Resharding 操作可以是对整个 hash slot map 的调整，也就是可以包括对多个 slot 的 迁移（migration） ，迁移就是把一个 slot 从一个节点迁移到另外一个节点。一个 slot migration 操作包括前面讲的 hash slot map 变更，另外还包括 key 的迁移操作。要把一个 slot 迁移到另外的节点上，首先把这个 slot 上的所有的 key 迁移到这个节点，当把所有 key 都迁移完后，再进行 hash slot map 变更，当 hash slot map 变更完成，这次 slot migration 结束。
Redis Cluster 使用 CLUSTER SETSLOT 来设置迁移。举例说明，将 slot1 从节点 A 迁移到节点 B。分别对节点 A 和节点 B 执行下面的命令：
节点 A 上：CLUSTER SETSLOT 1 MIGRATING NODEB
节点 B 上：CLUSTER SETSLOT 1 IMPORTING NODEA
其中，MIGRATING 表示数据要从这个节点迁出，而 IMPORTING 表示数据要往这个节点迁入。
执行完这两个命令后，节点 A 中的 slot1 不在创建新的 key。一个叫做 redis-trib 的特殊的程序负责把所有的 key 从节点 A 迁移到节点 B。redis-trib 会执行下面的命令：
这个命令会返回 count 个 key，对于每个返回的 key，redis-trib 执行下面的命令：
这个命令会原子地把一个 key 从节点 A 迁移到节点 B。具体来说，MIGRATE 命令会连接目标节点，并发向目标节点发送这个 key，一旦目标节点收到这个 key，则从自己的数据库中删除这个 key，在这个过程中，节点 A 和节点 B 都会加锁。
在把所有的 key 迁移完后，再分别在两个节点上执行下面的命令：
把所有的 key 迁移完一般需要一些时间，也就是说在开始迁移后和完成迁移前，在这个窗口期内，key 的实际的分布，与 hash slot map 里记录的是不一致的，client 按照 hash slot map 访问 key，会出现错误。
Redis Cluster 通过 ASK redirection 来解决这个问题。按照 client 端的 hash slot map，slot1 的 key 一定会发给节点 A，节点 A 收到这个请求后，如果发现这个 key 已经迁移到节点 B 了，那么就会给 client 回复 ASK redirection，client 收到 ASK redirection 后，会向节点 b 先发送一个 ASKING 命令，之后在发送对这个 key 的请求。
14、Configuration 的实际存储
Hash slot map 和 node table 都是逻辑上的结构，他们在 Redis Cluster 中的实际存储结构稍有不同（详情看结尾参考资料 1、2、3、4）。
在节点的内存中，用两个变量来存储这两个信息：
myself 变量 ：myself 代表本节点，是一个 ClusterNode 类型的变量，这个变量中，包含本节点的 configEpoch，还包括 slaveof，如果是 slave 节点则在 slaveof 中记录着它的 master 节点，还包括一个 bitmap，代表这个节点负责的所有的 slot 的槽位值。这个 bitmap 有 2048 个 byte 组成，一总是 16384（2048*8）个 bit，每个 bit 代表一个 slot，bit 置 1，代表这个节点负责这个 slot；
cluster 变量 ：代表了所在集群的状态，它包含 currentEpoch、lastVoteEpoch 和 slots 数组，slots 数组的 index 代表了 slot，数组的每个成员都指向一个节点，是一个 ClusterNode 类型的变量，与 myself 变量的类型一样。
所有 Configuration 的更改都会被保存到磁盘中，具体来讲是保存到一个名字叫 node.conf 的文件中，这个文件是 Redis Cluster 负责写入的，不需要人工配置。
node.conf 按照节点维度进行保存。每一行对应一个节点，每行分别包含这些信息：id，ip:port，flag，slaveof，ping timestamp, pong timespamp，configEpoch，link status，slots。
所有的节点结束后，会在文件的最后保存 curruntEpoch 和 lastVoteEpoch 两个变量。其中 flag 字段是枚举类型，会指明这个节点是不是自己，节点类型是 master 还是 slave。
如果是 slave 节点，则会在 slaveof 字段记录其 master 节点的 id。如果是 master 节点，则在最后多一个 slots 字段，记录着这个节点负责着哪些 slot。Flags 字段还记录着其他非常重
要的状态，本文就不继续展开了。
同样，ping timestamp、pong timestmap、link staus 三个字段本文也不继续展开了。
具体的 node.conf 文件类似下面的例子：
节点启动时会读取 node.conf 文件，把里面的信息加载到 myself 和 cluster 两个变量中。Slot 信息会被转换成 bitmap 保存在 myself 变量中。并且 slot 信息还会逆向的转换成 slot 到节点的映射保存在 cluster 变量中。
hash slot map 变更或者 node table 变更，就是修改内存中的 myself 变量和 cluater 变量，并且每次变更都会把这两个变量序列化转化后保存到 node.conf 中。
15、查看 configuration
Redis Cluster 提供了两个命令来查看 configuration：
第一个是 CLUSTER SLOT 命令，用来展示 hash slot 维度的信息，CLUSTER SLOT 命令的展示如下：
第二个是 CLUSTER NODE 命令，用来展示 node table 维度的信息，CLUSTER NODE 命令的展示如下：
CLUSTER NODE 命令展示的结果与 node.conf 文件中的内容非常类似。每一行都代表一个节点，每一行都包含 node id, address:port, slaveof，flags, last ping sent, last pong received, configuration epoch, link state, slots 这些字段。
CLUSTER NODE、CLUSTER SLOT 两个命令可以连接到任意节点上执行，这两个命令都是读取的这个节点的本地信息，根据 gossip 的特性，存在这两个命令展示的不是最新的 configuration 的可能性。
16、Conflict
虽然前面讲的 failover 过程通过大多数 master 投票的方式保证只有一个 slave 选中，并且产生唯一的 configEpoch。但是 Resharding 的过程却没有经过大多数的 master 的投票。
执行 slot 迁移时，仅仅是在集群中所有 configEpoch 中最大的那个 configEpoch 的基础上，再加一而得到的。并且由于 Resharding 一般包括多个 slot 的迁移，Redis cluster 目前的做法是，在一次 resharding 过程中，所有的 slot 迁移使用的 configEpoch 都是第一个 slot 迁移时产生的那个 configEpoch。
而 failover 和 resharding 都会修改 hash slot map，如果在 resharding 的过程中发生了 failover，这就有可能导致对 hash slot map 的修改产生冲突。另外，手动 failover 也是不经过 master 投票的，也就是执行 CLUSTER FAILOVER 命令（带 TAKEOVER 参数）。
产生冲突就是指针对同一个 slot，slot 被修改成映射到不同的节点上，并且这些修改具有相同的 configEpoch。
为了解决这个问题，Redis cluster 需要存在一个冲突解决的机制。如果一个 master 发现相同的 configEpoch，则比较一下两个节点的 id，id 小的节点，把自己 currentEpoch 加一，作为自己的 configEpoch。
三、Write Safety
由于有冲突的存在，可能导致不同的节点上的 hash slot map 不一致，取决于连接的节点不同，一部分 client 可能会把某个 slot 的 key 写入到一个节点中，而另外一部分 client 会把同样 slot 的 key 写入到另外一个节点中。当冲突被解决后，其中一个节点上接受的写入会丢失。
另外，由于 master 和 slave 之间的数据复制是异步的，在 failover 时如果 slave 还没有收到最新的数据，就发生了 failover，那么这部分写入就会丢失。Redis cluster 在这方面做了一个优化，当一个 slave 发现 master 发生了宕机，它不会立即开始选举的过程，它会等待一个时间，这个时间计算公式如下：
这个计算公式中，
第一部分是一个固定 500 毫秒的时间，这是为了给 master 充分的时间，也发现节点宕机这个事实；
第二个是随机等待一段时间，这是为了尽量避免多个 slave 同时发现 master 宕机，然后同时开始选举，导致 master 被瓜分，从而导致所有的选举都不成功；
第三部分是 slave 的 rank，rank 主要取决于 slave 的复制进度，复制的数据越多，则 rank 越小，也就是越短的等待时间，越先开始选举，有更大的可能性被选成新的 master。但这仅仅是个优化，不能完全防止丢数据的可能。
参考资料
[1]https://github.com/redis/redis/blob/unstable/src/cluster.c
[2]https://github.com/redis/redis/blob/unstable/src/cluster.h
[3]https://github.com/redis/redis/blob/unstable/src/server.c
[4]https://github.com/redis/redis/blob/unstable/src/server.h
作者介绍：
陈东明，现任国美在线基础架构总监。曾任饿了么北京技术中心任架构组负责人，负责产品线架构设计及基础架构研发工作；曾任百度架构师，负责即时通讯产品的架构设计。具有丰富的大规模系统构建和基础架构研发经验，善于复杂业务需求下的大并发、分布式系统设计和持续优化。个人公众号：dongming_cdm。
原文链接：
拆解Redis Cluster，怎么实现“写安全”这个重要特性？
分布式云行业实践指南（2023）
业内首个分布式云行业实践方法论、工具箱。
评论