简述

分布式数据库是以集群的方式部署了多节点，把全量数据根据一定的数据路由规则将数据分散到不同的集群节点上，利用异地多机房多节点的集群能力使得分布式服务具有高可用、可扩展、可容灾的服务能力。

数据路由规则

路由算法

一般而言，数据路由方式有 哈希 、 顺序 两种。

由于Redis中是使用哈希算法相关内容，这里着重分析哈希取模算法、一致性哈希算法和虚拟槽等。

哈希取模算法

节点扩容、收缩对哈希取模路由的数据分布有很大影响,因为路由计算公式hash(key) % N中N为集群的节点数量发生了变化，因此所有的数据路由需要全部重新计算，因此对历史数据会产生几乎颠覆性的推翻和重算，如下：

一致性哈希算法

通过哈希取模算法可以看到，在集群节点发生扩容、收缩等变更时，对其算法的冲击是较为致命的。对于分布式环境下，业务量增加、大促备战进行扩容或业务调整、物理机异常收缩节点是很常见的操作，因此哈希算法的稳定性、一致性就显得尤为重要，它应该能再满足扩容、收缩需求基础上尽可能少的对数据路由特别是历史数据路由计算产生影响。

良好的分布式cahce系统中的哈希算法应该满足以下几个方面：  一致性哈希算法原理

• 平衡性(Balance)
  平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。
• 单调性(Monotonicity)
  单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲区加入到系统中，那么哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲区中去，而不会被映射到旧的缓冲集合中的其他缓冲区。简单的哈希算法往往不能满足单调性的要求，如最简单的线性哈希：x = (ax + b) mod (P)，在上式中，P表示全部缓冲的大小。不难看出，当缓冲大小发生变化时(从P1到P2)，原来所有的哈希结果均会发生变化，从而不满足单调性的要求。哈希结果的变化意味着当缓冲空间发生变化时，所有的映射关系需要在系统内全部更新。而在P2P系统内，缓冲的变化等价于Peer加入或退出系统，这一情况在P2P系统中会频繁发生，因此会带来极大计算和传输负荷。单调性就是要求哈希算法能够应对这种情况。
• 分散性(Spread)
  在分布式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。
• 负载(Load)
  负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。
• 平滑性(Smoothness)
  平滑性是指缓存服务器的数目平滑改变和缓存对象的平滑改变是一致的。

根据以上所述，引申出一致性哈希算法的概念，实现思路如下：

• 先构建一个范围在0~2³²-1（32位的无符号整数）的哈希环，在0和2³²-1位置处重合。
  
  网络异常，图片无法展示

  |
• 计算所有集群节点的hash值，将集群节点均匀分布在哈希环上
  
  网络异常，图片无法展示

  |
• 业务数据读写时，根据数据键key计算hash值，然后顺时针找到第一个大于等于该哈希值且已分布在哈希环上的节点

一致性哈希算法在扩容、收缩时存在负载不均衡的问题，一般通过扩容、收缩2倍数量节点进行调整。在集群节点较少时也容易由于哈希分布不均匀导致数据倾斜问题。

虚拟槽

为了进一步解决一致性哈希算法中负载不均衡、少节点数据倾斜的问题，一般采用虚拟槽来进行改进，Redis Cluster便是采用这种方式进行集群节点管理的。

如上图，引入虚拟槽的概念后，可以不考虑具体实际集群节点的数量，而可以人为定义虚拟槽的数量，只需要将集群节点与虚拟槽的槽位范围进行映射绑定即可，相当于在业务数据和集群节点之间增加了一层代理缓冲映射区，实现了集群节点和业务数据的解耦，在扩容和收缩集群节点时只需要操作这个虚拟槽的映射关系即可。

以上分别介绍了哈希取模算法、一致性哈希算法和虚拟槽的概念，下面总结下演变过程和对比

以上为数据分区路由规则的概述，数据分区是分布式数据库存储的核心，无论是MySQL分库分表、还是Redis Cluster集群或其他数据的分布式存储场景都会使用到。

集群通信

在分布式存储中需要提供维护节点元数据信息的机制，所谓元数据是指节点负责哪些数据，是否出现故障等状态信息。
常见的元数据维护方式分为：集中式、P2P。

通信协议

Redis Cluster采用P2P的Gossip（流言）协议， Gossip协议工作原理就是节点彼此不断通信交换信息，一段时间后所有的节 点都会知道集群完整的信息，这种方式类似流言传播。

Redis Cluster节点Gossip协议通信过程：

• 集群中的每个节点都会单独开辟一个TCP通道，用于节点之间彼此通信，通信端口号在基础端口上加10000。
• 每个节点在固定周期内通过特定规则选择几个节点发送ping消息。
• 接收到ping消息的节点用pong消息作为响应。

消息类型

如上，一般分为ping消息、pong消息、meet消息、fail消息四种消息类型。

• meet消息 用于通知新节点加入。消息发送者通知接收者加入到当前集群，meet消息通信正常完成后，接收节点会加入到集群中并进行周期性的ping、pong消息交换。
• ping消息 集群内交换最频繁的消息，集群内每个节点每秒向多个其他节点发送ping消息，用于检测节点是否在线和交换彼此状态信息。ping消息发送封装了自身节点和部分其他节点的状态数据。
• pong消息 当接收到ping、meet消息时，作为响应消息回复给发送方确认消息正常通信。pong消息内部封装了自身状态数据。节点也可以向集群内广播自身的pong消息来通知整个集群对自身状态进行更新。
• fail消息 当节点判定集群内另一个节点下线时，会向集群内广播一个fail消息，其他节点接收到fail消息之后把对应节点更新为下线状态。

消息格式

消息格式分为消息头、消息体。
集群消息结构体如下：

union clusterMsgData {

   /* PING, MEET and PONG */

   struct {

       /* Array of N clusterMsgDataGossip structures */

       // 每条消息都包含两个 clusterMsgDataGossip 结构

       clusterMsgDataGossip gossip[1];

   } ping;

   /* FAIL */

   struct {

       clusterMsgDataFail about;

   } fail;

 /* 忽略其他消息类型 */

};

消息解析流程

消息成本

通过以上Gossip协议的通信方式来看

• 优点 是可以能够保持对集群节点信息的更新采集，能够较快响应异常
• 缺点 是由于是点对点通信，集群中节点间消息通信成本较高，且随着集群规模越大，成本呈指数级增长

针对消息通信成本较高影响网络负载的情况，Redis Cluster通过预设值进行自适应算法来调整

集群搭建

搭建集群工作需要以下三个步骤：

• [step-1] 准备节点
  这一步主要是配置好Redis Cluster各节点集群配置文件，具体操作流程这里不做赘述，可自行研究。
• [step-2] 节点握手 这一步主要是通过cluster meet {ip} {port}命令建立各节点之间的通信开始进行Gossip协议消息传递。此时通过cluster info命令查看cluster_state:fail节点集群状态仍然是失败，因为此步仅完成了集群节点通信，还需要进行槽位分配才可以使集群开始工作。这正如上面我们讲的Redis Cluster通过虚拟槽改进了一致性哈希算法。
• [step-3] 分配槽
  Redis Cluster中一共有16384个槽位，只有全部槽位都分配给节点后，集群才进入在线状态。
  Redis Cluster中计算槽位hash值采用了CRC16算法。

分配槽，其实就是建立集群节点与槽范围的映射关系，如下是一个分配槽位区间给集群节点的命令集案例：

redis-cli -h 127.0.0.1 -p 6379 cluster addslots {0...5461}

redis-cli -h 127.0.0.1 -p 6380 cluster addslots {5462...10922}

redis-cli -h 127.0.0.1 -p 6381 cluster addslots {10923...16383}

为什么有16384（2¹⁴）个槽位？

CRC16算法产生的hash值有16bit，该算法可以产生2¹⁶=65536个值。换句话说，值是分布在0~65535之间。为什么不mod(65536)，而选择mod(16384)呢

Redis作者回答了该问题 https://github.com/antirez/redis/issues/2576

关于集群环境，除了搭建，还会有日常维护涉及的节点扩容、收缩等，这些比较偏运维不在此进行赘述，感兴趣可以继续探究，扩容、收缩原理可参考上述介绍。

集群路由

MOVED

在集群模式下，Redis接收任何键相关命令时首先计算键对应的槽，再 根据槽找出所对应的节点，如果节点是自身，则处理键命令；否则回复MOVED重定向错误，通知客户端请求正确的节点。这个过程称为MOVED重定向

注意：

• 使用redis-cli命令时，可以加入-c参数支持自动重定向，简化手动发起重定向操作
• 重定向会产生大量网络IO消耗，一般Redis Client会维护一个映射关系表，作为客户端本地副本来进行维护，通过前置查询本地映射副本来减少重定向的情况产生

ASK

Redis集群支持在线迁移槽（slot）和数据来完成水平伸缩，当slot对应的数据从 源节点 到 目标节点 迁移过程中，客户端需要做到智能识别，保证键命令可正常执行。例如当一个slot数据从源节点迁移到目标节点时，期间可能出现一部分数据在源节点，而另一部分在目标节点的情况

故障处理

故障发现

Redis通过ping/pong消息实现节点间通信用来交互节点间状态信息，故障发现流程也是基于此进行实现，故障判定有一套判定流程，这里主要区分为主观下线和客观下线。

主观下线

主观下线 [简单来讲就是，当 cluster-note-timeout 时间内某节点无法与另一 个节点顺利完成 ping/pong 消息通信时，则将该节点标记为 主观下线 状态，但是该判断仅仅是某节点自身认为的，由于分布式网络的复杂性还需要其他节点的共同判定才可以。

客观下线

通过Gossip消息传播，集群内节点不断收集到故障节点的下线报告。当 半数以上 持有槽的主节点都标记某个节点是主观下线时。触发 客观下线 流程

为什么必须是负责槽的主节点参与故障发现决策？
因为集群模式下 只有处理槽的主节点才负责读写请求和集群槽等关键信息维护，而从节点只 进行主节点数据和状态信息的复制

为什么半数以上处理槽的主节点？
必须半数以上是为了应对网络分区等原因造成的集群分割情况，被分割的小集群因为无法完成从主观下线到客观下线这一关键过程，从而防止小集群完成故障转移之后继续对外提供服务

故障恢复

故障节点变为客观下线后，如果下线节点是持有槽的主节点则需要在它 的从节点中选出一个替换它，从而保证集群的高可用。下线主节点的所有从节点承担故障恢复的义务，当从节点通过内部定时任务发现自身复制的主节点进入客观下线时，将会触发故障恢复流程。Redis Cluster集群故障异常的选主过程在raft一致性协议的基础上做了调整，想深入了解可以自行研究，后续也会开篇专门论述。

故障恢复流程步骤如下：

• [step-1]资格检查
  每个从节点都要检查最后与主节点断线时间，判断是否有资格替换故障的主节点。如果从节点与主节点断线时间超过cluster-node-time * cluster-slave-validity-factor，则当前从节点不具备故障转移资格。参数cluster-slave- validity-factor用于从节点的有效因子，默认为10。
• [step-2]准备选举时间
  
  网络异常，图片无法展示

  |
  
  当从节点符合故障转移资格后，更新触发故障选举的时间，只有到达该时间后才能执行后续流程，这里采用延迟触发机制，主要是通过对多个从节点使用不同的延迟选举时间来支持优先级问题。复制偏移量越大说明从节点延迟越低，那么它应该具有更高的优先级来替换故障主节点。
• [step-3]发起选举
  当从节点定时任务检测到达故障选举时间（failover_auth_time）到达 后，发起选举流程

• 更新配置纪元
  配置纪元的主要作用
  标示集群内每个主节点的不同版本和当前集群最大的版本。每次集群发生重要事件时，这里的重要事件指出现新的主节点（新加 入的或者由从节点转换而来），从节点竞争选举。都会递增集群全局的配置纪元并赋值给相关主节点，用于记录这一关键事件。主节点具有更大的配置纪元代表了更新的集群状态，因此当节点间进行ping/pong消息交换时，如出现slots等关键信息不一致时，以配置纪元更大 的一方为准，防止过时的消息状态污染集群
  
  应用场景
  新节点加入、槽节点映射冲突检测、从节点投票选举冲突检测
• 广播选举消息
  在集群内广播选举消息（FAILOVER_AUTH_REQUEST），并记录已发 送过消息的状态，保证该从节点在一个配置纪元内只能发起一次选举。消息内容如同ping消息只是将type类型变为FAILOVER_AUTH_REQUEST，当发起过投票后，再收到从节点的投票消息会进行拒绝，防止重复投票。

• [step-4]选举投票
  
  网络异常，图片无法展示

  |

注意 只有持有槽的主节点才会处理故障选举消息，而选举成功的规则是必须满足大于等于N/2+1张选票才可以选举成功，因此机器部署必须至少满足3台，上图示例是5个Master节点的集群选举过程。

• [step-5]替换主节点
  当从节点收集到足够的选票之后，触发替换主节点操作：

• 当前从节点取消复制变为主节点。
• 执行clusterDelSlot操作撤销故障主节点负责的槽，并执行clusterAddSlot把这些槽委派给自己
• 向集群广播自己的pong消息，通知集群内所有的节点当前从节点变为主节点并接管了故障主节点的槽信息

集群架构

如图，是一个比较常见的Redis集群架构，这里仅供参考。

• client 所有的客户端请求都会根据请求键Key进行slot值计算，然后路由到相应负责的分区master节点上进行请求命令处理
• 分区  或者这里也可以叫做集群节点，最少由一个master和一个slave构成，一般会选择一个主备在同机房，另外slave节点部署到另外一个机房，这样异地多机房的部署可以满足灾备要求。
• 集群 Redis集群是由多个集群节点<master,slave,slave>构建而成的

集群限制

• 批量操作支持有限 如mset、mget，目前只支持具有相同slot值的key执行批量操作。对于映射为不同slot值的key由于执行mget、mget等操作可能存在于多个节点上因此不被支持。

对于集群环境下的 mset、mget ，一般可以通过 pipeline 方式进行实现，即将 mset、mget 命令进行批量的 set、get 命令转换，这样就打破了 slot 值对 key 路由限制，批执行后聚合数据再返回，是一种在集群环境下曲线救国的方式

除此之外，这种因slot槽位不同导致无法执行的问题同样存在于lua脚本中，当试图通过lua脚本来原子地执行一系列命令时，对Key的读写也必须遵循这个要求

如果业务场景允许，可以通过给key增加 {} 强制指定key的路由节点进行数据存放，如命令 set/get {key}1 则强制指定key在第一个节点进行落库，便可进行操作

• 事务操作支持有限 同理只支持多key在同一节点上的事务操作，当多个key分布在不同的节点上时无法使用事务功能，可参考上述图例。
• 受字典表结构限制 key作为数据分区的唯一决策因子，值对象会根据Key进行数据分区存储，因此无法将一个大的键值对象如hash、list等映射到不同的节点。这部分的数据拆分需要上层应用根据业务场景进行拆分和规划设计，防止大Key产生带来不良影响。
• 不支持多数据库空间 单机下的Redis可以支持16个数据库，集群模式下只能使用一个数据库空间，即db0。
• 复制结构只支持一层 从节点只能复制主节点（主-从），不支持嵌套树状复制结构（主-从-从）。

总结

在互联网分布式服务场景下，我们要确保高并发、高性能、高可用三个指标的SLA，通过之前的文章分析可以看到Redis通过内存管理、数据结构、自适应算法、事件驱动模型等实现确保了它的高并发、高性能，通过主从复制、哨兵机制等实现确保了它的高可用，而本篇的Redis Cluster核心解决的是Redis分布式部署、服务伸缩等问题。

参考

《Redis设计与实现》

《Redis开发与运维》

https://www.cnblogs.com/youngdeng/p/12855424.html

https://www.cnblogs.com/williamjie/p/9477852.html 一致性哈希

https://www.cnblogs.com/breg/p/4024498.html 一致性哈希