复制
复制功能是让一台Redis服务器复制另一台服务器，也就是Master-Slave模式，通常用于实现读写分离。该功能有两种实现，分别对应2.8版本之前的老版本，和2.8（包括）之后的新版本。
2.8版本之前的实现
复制功能分为同步和命令传播两个操作。
- 同步：将从服务器的数据库更新至主服务器当前所处的数据库状态。
同步的步骤如下：
- 从服务器发送
SYNC命令。 - 主服务器收到
SYNC命令，执行BGSAVE在后台生成一个RDB文件，并用缓冲区记录从现在开始执行的所有写命令。 - 当RDB文件准备好时，把该文件发送给从服务器。
- 从服务器阻塞载入RDB文件（这段时间从服务器不能处理任何请求）。
- 主服务器把缓冲区里的命令发送给从服务器
- 命令传播：主服务器把写命令传播到从服务器，使得主从服务器的数据库状态一致。比如当主服务器执行
DEL key时，会异步的把该命令发送给从服务器，使两者状态最终一致。
缺点：如果从服务器中途短线，重连后需要重新执行一遍同步操作，效率较低（生产RDB文件需要耗费大量I/O、CPU资源）。
2.8及之后版本的实现
新版本使用PSYNC命令替代SYNC，该命令具有完整重同步和部分重同步两种模式。其中完整重同步的步骤跟旧版本的SYNC的命令类似不再赘述，下面主要讲部分重同步功能。
新版本的实现中，主从服务器分别维护一份复制偏移量，记录当前复制的进度。当主服务器向从服务器发送N个字节的数据时就把自己的偏移量加上N，当从服务器接收到N个字节的数据时就把自己的偏移量也加上N，如果主从服务器数据处于一致，那么它们的偏移量也是一致的。
如果从服务器出现了断开的状况，那么复制偏移量就会和主服务器不一致：
为了解决从服务器意外断开连接后能够快速恢复到跟主服务器一致的状态（之所以说快速是因为旧版本的实现效率太低），Redis使用了复制积压缓冲区来记录最近执行的写命令，以便在从服务器恢复连接后能通过缓冲区把丢失的写命令找回并发送到从服务器。该缓冲区是一个固定长度的先进先出队列，默认大小是1MB，当缓冲区大小不够时会将位于队首的元素抛弃，队列保存了一部分最近传播的写命令，每个字节的偏移量都会记录在内，其构造如图所示：
当从服务器断线重连后会发送自己的复制偏移量给主服务器，如果偏移量+1存在主服务器缓冲区中，那么主服务器会把这部分数据发送给从服务器；反之会执行完整重同步。
这里存在一个问题，从服务器重连后如何知道是否是之前的那台主服务器？
其实Redis在启动时会生成一个随机的服务器运行ID，当从服务器连接到主服务器后便会记下这个ID，下次连接时如果发现ID不能对应就会执行完整重同步。
在命令传播阶段，从服务器默认每秒向服务器发送心跳，并带上自己的复制偏移量，如果主服务器超过1秒没有收到心跳，说明网络出现了问题。此外如果主服务器发送的写命令意外丢失，那么主服务器通过心跳返回的偏移量就可以知道主从服务器状态不一致，然后通过复制挤压缓冲区补发缺失的命令，使两者再次一致。
Redis2.8版本之前没有这一机制，如果主服务器向从服务器发送的命令出现了丢失，两者都不会注意到。
Sentinel（哨兵）
上文介绍的复制功能可以把Master的读压力分散到其它Slave上，但是当Master发生故障后，需要手动把一台Slave提升为Master，客户端也很有可能需要修改连接地址如果你没有服务发现这样的基础设施的话，因为你不知道是哪一台Slave被提升为Master。
Redis提供了Sentinel来解决以上问题。它会监控所有的Redis节点，并提供故障转移机智，是一种高可用解决方案。其大致结构如图所示：
初始化Sentinel
通过以下命令启动Sentinel：
redis-sentinel /path/to/your/sentinel.config
//等价于
//redis-server /path/to/your/sentinel.config --sentinel
Sentinel本质是一个特殊的Redis服务器，因此初始化过程可以看作是初始化一台普通的Redis服务器，但在某些方面会有所区别，比如它不会使用数据库因而不会载入RDB或AOF文件。哨兵使用的命令表也很普通Redis服务器不同，它只支持7个命令：PING、SENTINEL、INFO、SUBSCRIBE、UNSUBSCRIBE、PSUBSCRIBE、PUNSUBSCRIBE。
启动后，服务器会初始化一个sentinelState结构的对象，保存了所有和哨兵功能相关的状态，其结构如下所示：
struct sentinelState {
//当前纪元，是个计数器，故障转移时会用到
uint64_t current_epoch;
//保存了当前sentinel监控的所有master
//键是master的名字，值是一个指向sentinelRedisInstance结构的指针
dict *masters;
//是否进入TILT模式
int tilt;
//目前正在执行的脚本数量
int running_scripts;
//进入TILT模式的时间
mstime_t tilt_start_time;
//最后一次执行时间处理器的时间
mstime_t previous_time;
//FIFO队列，包含所有需要执行的用户脚本
list *scripts_queue;
}
其中sentinelRedisInstance结构如下所示：
struct sentinelRedisInstance {
//实例的类型以及状态
int flags;
//实例的名字，master的名字在配置文件中配置，slave的名字由ip:port组成
char *name;
//运行ID
char * runid;
//配置纪元，是个计数器，故障转移时会用到
uint64_t config_epoch;
//实例的地址
sentinelAddr *addr;
//无响应多少毫秒后会被判断为主观下线
mstime_t down_after_period;
//判断实例为客观下线所需要的支持投票数
int quorum;
//在故障转移时可以同时对新的主服务器进行同步的从服务器数量
int parallel_syncs;
//刷新故障迁移状态的超时时间
mstime_t failover_timeout;
//从服务器，键是ip:port，值是一个指向sentinelRedisInstance结构的指针
dict *slaves;
//哨兵，键是ip:port，值是一个指向sentinelRedisInstance结构的指针
dict *sentinels;
//其它
...
}
上面的数据结构可以和下面的配置文件对应起来：
//sentinel.conf
//监控主服务器的名字为master1，地址是127.0.0.1，端口是6379
//判断实例为客观下线所需要的支持投票数是2
sentinel monitor master1 127.0.0.1 6379 2
//master1若在30000毫秒内无响应则判断为下线
sentinel down-after-milliseconds master1 30000
//master1发生故障后，它的从服务器同时只有1台能从新的master进行同步
sentinel parallel-syncs master1 1
//故障迁移超时时间900000毫秒
sentinel failover-timeout master1 900000
初始化完成后内存中会有如下所示的对象关系：
Sentinel的一些状态会持久化到配置文件中(sentinel.conf)，因此无需担心sentinel重启。
连接Master
初始化后sentinel会和每一个被监视的master创建两个连接，一个用于收发命令，一个用于订阅master的__sentinel__:hello频道。
连接建立后，sentinel会以10秒一次的频率向master发送INFO命令，通过返回值可以得到master的运行ID、角色（master/slave）以及所有slave（可以看作是服务发现）。
Sentinel会把slave关联到对应的master对象上：
连接Slave
通过master发现了所有slave之后，sentinel会建立和slave的连接，同样是每个slave两个连接。连接建立后同样会以10秒一次的频率向slave发送INFO命令，并且得到运行ID、master地址、复制偏移量等信息，记录到sentinelRedisInstance结构中。
连接Sentinel
上面提到Sentinel会和master和slave保持两个连接，一个用于收发命令，一个用于发布订阅指定的频道。Sentinel以2秒一次的频率通过第2个连接向所有监控的服务器发送以下格式的命令：
PUBLISH __sentinel__:hello "<sentinel_ip>,<sentinel_port>,<sentinel_runid>,<sentinel_epoch>,<master_name>,<master_ip>,<master_port>,<master_epoch>"
- 以sentinel开头的参数是sentinel本身的信息。
- 以master开头的参数是主服务器的信息，如果sentinel发送命令的对象是主服务器，那么就是该主服务器本身的信息；如果发送命令的对象是从服务器，那么就是该从服务器正在复制的主服务器的信息。
每一个sentinel既是__sentinel__:hello频道的发布者，同时也是订阅者。这种设计的作用是，当一个服务器被多个sentinel监控时，任意一个sentinel发送的消息都会被其它sentinel接收到。当其它sentinel接收到消息后就会发现新的sentinel，并且更新master对应的sentinelRedisInstance结构的sentinels属性，如下图所示：
通过这种方式，每个sentinel都知道它监控的某个master还在被哪些sentinel监控。
Sentinel会和其它sentinel建立1个连接，最终同一个master的所有sentinel互联。
判断下线
一个sentinel会以每秒1次的频率向所有建立连接的服务器发送PING命令，包括主从服务器和其它sentinel。如果在一段时间内（由配置的down-after-milliseconds指定）一直收到无效回复（有效回复有3种，+PONG、-LOADING、-MASTERDOWN，此外都是无效回复，没有回复也是无效回复）那么sentinel就会认为该实例已经下线，sentinel会修改该实例对应的sentinelRedisInstance结构的flags属性，将其标为主观下线（SDOWN，Subjectively Down）。
同一个master被多个sentinel监控时，因为每个sentinel的主观下线时长可能配置了不同的值，因此不同的sentinel对于同一个master的下线状态可能有不同的判断。
当sentinel认为一个master已经下线后，它会发送以下格式的命令询问该服务器的其它sentinel是否也认为该服务器已经下线：
SENTINEL is-master-down-by-addr <master_ip> <master_port> <sentinel_epoch> *
//e.g. SENTINEL is-master-down-by-addr 127.0.0.1 6379 0 *
当另一个sentinel接收并且检查master是否下线后会回复一条包含三个参数的消息：
1) <down_state> //1表示下线，0表示未下线
2) *
3) 0
如果得到的确认数量超过了配置的quorum的值，sentinel就会把master标为客观下线（ODOWN，Objectively Down）。
Sentinel仅会对master进行故障转移，如果是slave下线了，sentinel会把它标为SDOWN，并且不会询问其它的sentinel。
Leader选举
当一个master被标为客观下线时，监视这个服务器的各个sentinel会协商选举出一个leader，由leader执行故障转移。
我们假设有3个sentinel组成哨兵系统，为了选出leader，3个sentinel再次向其它两个sentinel发送命令，区别是这次会带上sentinel自己的运行ID，表示要求对方把自己设为leader：
SENTINEL is-master-down-by-addr <master_ip> <master_port> <sentinel_epoch> <sentinel_runid>
如果接收到命令的sentinel还没有设置过leader的话就会把接收到的sentinel设置为leader，并返回：
1) <down_state> //1表示下线，0表示未下线
2) <leader_runid>
3) <leader_epoch>
接收到回复的sentinel就可以知道有多少sentinel选举自己当leader，如果获得了半数以上（大于等于sentinel数量/2+1）的投票，那么就算选举成功。
在选举过程中有几个规则：
- 不论选举是否成功，所有sentinel的配置纪元都会自增一次。
- 在一个纪元里只能设置一次leader，设置的优先级是先到先得。
- 如果在给定时间内选举失败，那么会在一段时间后重新选举直到选出leader为止。
Leader选举算法请参考Raft算法。
故障转移
Leader会从下线主服务器的所有从服务器中选出一台并转换为主服务器，有以下几个筛选条件：
- slave处于在线状态。
- 最近5秒内回复过leader发出的
INFO命令（来保证leader和该slave最近成功进行过通讯）。 - slave与已经下线的master连接断开时间不超过
down-after-milliseconds * 10毫秒（确保slave没有过早和master断开连接，slave保存的数据是相对较新的）。
筛选完成后，如果没有可用的slave那么就终止此次故障转移，否则Leader会根据slave的优先级进行排序，选出优先级最高的slave。
Slave的优先级可以在配置文件中通过
slave-priority属性进行修改，默认是100，该值越低，优先级越高，如果设成0，那么永远不会被当选master。可以通过INFO命令查看slave的优先级。
如果有多个slave优先级相同，那么选出复制偏移量最大的slave；如果多个slave复制偏移量相同，那么选出运行ID最小的slave。
Slave被选中后，Leader会向它发送SLAVEOF no one命令，同时以1秒1次的频率发送INFO命令，观察slave的角色从slave变成master。此时leader就知道该slave已经提升为master。如果这一步超时了，就终止此次故障转移。
下一步，Leader向已下线master的其它slave发送SLAVEOF命令，让它们复制新的master。
最后一步，当已下线的master重新上线后，Leader会向它发送SLAVEOF命令让它成为新master的从服务器。
TILT模式
由于sentinel系统依赖机器时间，比如需要知道多长时间没有跟某个实例进行过通讯，因此一旦机器的时间功能发生错误，Redis就会进入TILT模式，直到正常运行超过30秒。在该模式下它不会执行任何操作，比如故障转移，当其它sentinel发来SENTINEL is-master-down-by-addr命令询问实例的在线状态时它会返回负值，告诉对方它的下线判断不再准确。
判定时间功能发生错误的依据是：sentinel定时器每100毫秒执行一次，如果两次时间差值是负值（时间出现了倒退）或者过大（超过了2秒），Redis就会进入TILT模式。
客户端处理流程
官方推荐的客户端处理流程是：
- 当客户端尝试连接到一个sentinel系统时，依次尝试连接sentinel实例，并发送
SENTINEL get-master-addr-by-name master-name命令获得master信息，如果连接sentinel失败或sentinel返回的master信息为null，那么继续连接下一个sentinel，直到成功获取master信息。 - 向master发送
ROLE命令确认该实例是master，否则重复步骤1。 - 客户端向sentinel订阅频道，当master被切换后可以收到新的master信息。
- 如果有读写分离的需求，那么可以通过
SENTINEL slaves master-name命令获取slave列表。
集群
相比上文提到的哨兵模式，集群模式主要提供了数据分片的功能，因为一台服务器总有物理容量的限制。分片功能支持把数据分散的存储在多台实例上，突破了单个节点的物理限制。
* 快速搭建集群
Linux上可以使用docker快速搭建一个有三个master节点的集群：
# 以下脚本须在linux中执行
# 因为docker的host模式问题，mac下需要安装linux虚拟机下面的脚本才能正常执行
# 创建3个redis-server
docker run --name redis1 --net=host -itd redis redis-server --port 6379 --cluster-enabled yes --cluster-node-timeout 60000
docker run --name redis2 --net=host -itd redis redis-server --port 6380 --cluster-enabled yes --cluster-node-timeout 60000
docker run --name redis3 --net=host -itd redis redis-server --port 6381 --cluster-enabled yes --cluster-node-timeout 60000
# 使用redis-trib工具启动集群
docker run --rm --net=host -it zvelo/redis-trib create 127.0.0.1:6379 127.0.0.1:6380 127.0.0.1:6381
启动
Redis服务器在启动时会通过cluster-enabled参数决定是否开启集群模式。集群模式跟普通单机模式用到的模块大部分都一样（如RDB模块），除此之外用到了一些集群专有的功能，比如serverCron方法会调用clusterCron发送Gossip消息、检查节点状态。
除了单机模式用到的redisServer结构体，集群模式下还会用到clusterNode、clusterLink、clusterState来存储集群的一些状态。
每个实例都有一个clusterState类型的对象来记录当前集群的状态：
typedef struct clusterState{
// 指向当前节点的指针
clusterNode *myself;
// 配置纪元
uint64_t currentEpoch;
// 集群的状态：上线还是下线
int state;
// 集群中至少处理一个槽的节点的数量
int size;
// 集群所有的节点（包含自己），字典的键是节点名字，值是节点对应的clusterNode对象
dict *nodes;
// 槽
// clusterNode *slots[16384];
} clusterState;
每个clusterState都存储了集群内所有节点的信息，如IP、角色等。下面是一个更直观的结构图：
握手
建立集群的第一步是握手。通过以下命令让远程实例加入当前实例所在的集群：
CLUSTER MEET <ip> <port>
# 当前实例 127.0.0.1 6379
# CLUSTER MEET 127.0.0.1 6380
# CLUSTER MEET 127.0.0.1 6381
# 以上三个节点形成集群
当实例A向实例B发送MEET消息并握手成功后，A会把B的信息以Gossip协议传播给集群中的其它节点，最终所有节点都会知道B的存在。
槽
集群模式下，整个数据库被划分为16384个槽，每个键占用其中的一个槽，每个节点可以处理0个或多个槽。只有当所有的槽都有节点在处理时，集群才处于上线状态。因此即使用CLUSTER MEET命令建立了集群，集群仍然处于下线状态。
使用以下命令分配槽：
CLUSTER ADDSLOTS <slot>
# 分配0-5槽
# CLUSTER ADDSLOTS 0 1 2 3 4 5
以上命令可以配合shell脚本分配全部的16384个槽。推荐使用redis-trib工具自动建立集群并分配槽。
clusterNode结构里使用一个unsigned char slots[2048]属性记录节点处理的槽。
2048 = 16384 / 8 , C语言中的
char占1个字节。
一个char类型变量占1个字节（8位），位如果是1则表示节点处理该槽，0表示不处理。其结构如下：
每个Redis节点除了记录自己处理的槽外也会记录其它节点处理的槽，这些状态以slots数组存储在clusterState结构体中，每个元素指向一个clusterNode结构体。在CLUSTER ADDSLOTS命令执行完毕后，节点会把自己的slots数组发送给其它的节点告诉他们处理槽的状态。
键
集群模式下，每个键都归属于一个槽，一个槽可以对应多个键。Redis使用CRC16算法将键映射到一个槽，算法如下：
CRC16(key) & 16383
可以通过以下命令查看键所属的槽：
CLUSTER KEYSLOT <key>
当节点计算出键属于哪个槽后，它会检查所属槽是不是自己负责处理，如果是，那么就执行客户端发来的命令；否则节点会查找处理该槽的节点并向客户端返回MOVED错误指引它转向正确的节点。
MOVED错误的格式为：
MOVED <slot> <ip>:<port>
客户端收到MOVED错误后会根据ip和端口信息转向目标节点并重新发送命令。
客户端也区分集群模式和单机模式。单机模式会直接打印出
MOVED错误而不会重定向。集群模式需要加上-c参数。
数据库
集群模式和单机模式下的数据库一个重要的区别是：集群模式只能使用0号数据库。
集群模式下的键值对以及过期时间的存储和普通模式下的一样。除此之外集群模式下的节点会用一个跳跃表存储槽和键的关系，用于对某些槽的键进行批量操作。跳跃表里的分值就是槽号，值就是键。下面是一个例子：
重新分片
当新增或移除节点时，需要对集群进行重新分片。我们使用redis-trib工具对集群进行在线重新分片操作，其主要步骤是：
- 向目标节点发送
CLUSTER SETSLOT <slot> IMPORTING <source_id>命令，让其做好准备。 - 向源节点发送
CLUSTER SETSLOT <slot> MIGRATING <target_id>命令，让其做好迁移的准备。 - 向源节点发送
CLUSTER GETKEYSINSLOT <slot> <count>命令，获得最多count个位于slot槽的键。 - 对于步骤3中返回的每一个键，向源节点发送一个
MIGRATE <target_ip> <target_port> <key_name> 0 <timeout>命令将选中的键原子地迁移到目标节点。 - 重复步骤3和4直到所有的键都已被迁移。
- 向集群中任意一个节点发送
CLUSTER SETSLOT <slot> NODE <target_id>命令，将slot指派给目标节点，这一消息随后会发送到所有的节点。 - 如果有多个slot需要迁移，那么继续对剩下的slot进行上面的操作。
ASK
在迁移过程中，当客户端访问源节点数据库的某个键时，源节点会先在自己的数据库中查找，如果没有找到则检查该键所属槽的迁移状态。slot的迁移状态在源节点和目标节点上各有一个clusterNode指针数组存储（importing_slots_from和migrating_slots_to），其结构如下：
如果发现该键所属的槽正在迁移，那么它会向客户端返回ASK <target_ip>:<target:port>指引向目标节点。客户端收到ASK命令后会向目标节点发送ASKING消息然后再重新执行之前发给源节点的命令。
ASKING命令的用处是打开客户端的REDIS_ADKING标志以让目标节点强制执行命令。如果按正常流程，此时槽还没有完成迁移，仍旧属于源节点，所以如果不打开特殊标志，目标节点会返回MOVED错误。
当命令执行完毕后，
REDIS_ASKING标志会被移除。这是一个一次性的标志，如果下一次客户端访问时迁移仍未完成，那么仍旧会出现上面ASK的流程。
* 例子
# 新增1个redis节点
docker run --name redis4 --net=host -itd redis redis-server --port 6382 --cluster-enabled yes --cluster-node-timeout 60000
# 使用redis-trib把新的节点加入到集群中
docker run --rm --net=host -it zvelo/redis-trib add-node 127.0.0.1:6382 127.0.0.1:6369
# 重新分片，分配1000个slot到新的节点上
# --from可以指定节点，为了均匀分配，可以使用all，从所有旧的节点上平均的取出一部分slot迁移到新的节点上
# --slots指定本次迁到新节点的slot数量
docker run --rm --net=host -it zvelo/redis-trib reshard --from all --to <new_node_id> --slots 1000 --yes 127.0.0.1:6379
复制
集群模式下节点也分为主节点和从节点，从节点复制主节点并在主节点下线时接替它继续处理请求。
通过向节点发送CLUSTER REPLICATE <master_id>让接收命令的节点成为主节点的从节点。从节点会把clusterState.myself.slaveof指向主节点对应的clusterNode结构体，关闭REDIS_NODE_MASTER标识并打开REDIS_NODE_SLAVE标识，表示节点已从主节点变成从节点。最后调用复制代码开始复制，这部分代码就是单机模式下的复制代码。
节点间的复制关系会通过消息发送给集群中的其它节点，最后所有节点都会了解到其它节点间的复制关系，并保存在对应的clusterNode结构体中。
故障转移
节点之间会定期向集群中其它节点发送PING消息检测在线状态，如果对方在一定时间内没有回复PONG消息，那么节点就会把对方标为疑似下线REDIS_NODE_PFAIL状态。各个节点之间会通过消息交换节点状态，当某个主节点收到其它主节点发来的下线报告时，会把该报告存在目标下线节点对应的clusterNode结构体的fail_reposts链表中。
如果在下线报告链表中有半数以上的主节点都认为某个主节点疑似下线，那么就把它标记为已下线，并向集群广播一条FAIL的消息，收到该消息的节点立刻也把该节点标记为已下线。
当下线主节点的一个从节点收到FAIL消息后就开始对下线主节点进行故障转移，步骤如下：
- 从节点会向集群广播一条
CLUSTERMSG_TYPE_FAILOVER_AUTH_REQUEST的消息，要求所有收到消息并有投票权（集群中负责处理slots的主节点才有投票权）的主节点向该从节点投票。 - 主节点收到投票请求后，如果在当前配置纪元尚未投票给其它节点，那么返回一条
CLUSTERMSG_TYPE_FAILOVER_AUTH_ACK消息投票支持。 - 如果获得半数以上主节点的支持票，那么从节点就当选为leader。
- Leader节点执行
SLAVEOF no one命令成为新的主节点，然后撤销所有对已下线主节点的slot，并把这些slot指派给自己。 - 新的主节点向集群广播一条
PONG消息，让其它节点意识它已经成为了主节点，并接管了下线节点处理的slot。下线主节点的其它从节点会调整为复制新的主节点。 - 下线的主节点重新上线后会成为新主节点的从节点。
参考/图片出处：
1. 机械工业出版社 -《Redis设计与实现》
