Redis 集群实现原理探讨

redis集群

Redis 集群是一个 distribute、fault-tolerant 的 Redis 实现,主要设计目标是达到线性可扩展性、可用性、数据一致性。

线性拓展 官方推荐最大的节点数量为 1000,由于 Cluster 架构中无 Proxy 层,Master 与 Slave 之间使用异步 replication。

数据一致性 客户端容忍一定程度的数据丢失,集群尽可能保存 Client write 操作的数据,保证数据一致性。

可用性 Redis 集群通过 partition 来提供一定程度的可用性,当集群中的一部分节点失效或者无法进行通讯时,集群仍可以继续提供服务。这里有两点补充:

  • 只要集群中大多数 Master 可达、且失效的 Master 至少有一个 Slave 可达,即集群非 Fail 状态,集群都是可用的,如下图:
    redis集群
  • Redis 集群的 replicas migration 机制可以将拥有多个 Slave 的 Master 的某个 Slave,迁移到没有 Slave 的 Master 下,即 Slave 分布相对平衡,确保 Master 都有一定数量的 Slave 备份。
Redis 集群设计   总体架构  

redis框架

集群节点属性 集群中每个 Master node 负责存储数据、集群状态,包括 slots 与 nodes 对应关系。Master nodes 能够自动发现其他 nodes,检测 failure 节点,当某个 Master 节点失效时,集群能将核实的 Slave 提升为 Master。下图是节点的关联信息,节点定时会将这些信息发送给其他节点:

1fc2412b7429e4ab5d8704fcd39520815ea2727b 10.9.42.37:6103 master - 0 1494082584680 9 connected 10923-13652
08e70bb3edd7d3cabda7a2ab220f2f3610db38cd 10.9.33.204:6202 slave ad1334bd09ee73fdeb7b8f16194550fc2bf3a038 0 1494082586686 8 connected
edaafc250f616e9e12c5182f0322445ea9a89085 10.9.33.204:6203 slave 1fc2412b7429e4ab5d8704fcd39520815ea2727b 0 1494082586184 9 connected
06cd6f24caf98a1c1df0862eadac2b05254f909d 10.9.33.204:6201 slave d458c22ccced2f29358b6e6814a206d08285374e 0 1494082584179 7 connected
3892b7fb410a4d6339364dbdda2ebc666ffee843 10.9.42.37:6203 slave 73f7d44c03ada58bf5adaeb340359e2c043ecfa0 0 1494082582679 12 connected
73f7d44c03ada58bf5adaeb340359e2c043ecfa0 10.9.33.204:6103 master - 0 1494082585181 3 connected 13653-16383
4004a64211bea5050a8f46b8436564d40380cd60 10.9.33.204:6101 master - 0 1494082583678 1 connected 2731-5460
d458c22ccced2f29358b6e6814a206d08285374e 10.9.42.37:6101 master - 0 1494082588189 7 connected 0-2730
f8868d59c0f3d935d3dbe35601506039520f7107 10.9.42.37:6201 slave 4004a64211bea5050a8f46b8436564d40380cd60 0 1494082587187 10 connected
45ba0d6fc3d48a43ff72e10bcc17d2d8b2592cdf 10.9.33.204:6102 master - 0 1494082583179 2 connected 8192-10922
007d7e17bfd26a3c1e21992bb5b656a92eb65686 10.9.42.37:6202 slave 45ba0d6fc3d48a43ff72e10bcc17d2d8b2592cdf 0 1494082588189 11 connected
ad1334bd09ee73fdeb7b8f16194550fc2bf3a038 10.9.42.37:6102 myself,master - 0 0 8 connected 5461-8191

从左至右分别是:节点 ID、IP 地址和端口,节点角色标志、最后发送 ping 时间、最后接收到 pong 时间、连接状态、节点负责处理的 hash slot。集群可以自动识别出 ip/port 的变化,并通过 Gossip(最终一致性,分布式服务数据同步算法)协议广播给其他节点知道。Gossip 也称“病毒感染算法”、“谣言传播算法”(附录一)。

Keys 分布模型 集群的键空间被分割为 16384 个 slots(即 hash 槽),slot 是数据映射的基本单位,即集群的最大节点数量是 16384(官方推荐最大节点数量为 1000 个左右)。集群中的每个 Master 节点负责处理 16384 个 hash 槽其中的一部分,当集群处于“stable”状态时(无 slots 在节点间迁移),任意一个 hash slot 只会被单个 node 所服务。以下是键映射到 hash 槽的算法:

HASH_SLOT = CRC16(key) mod 16384

Redis 集群是在多个 Redis 节点之间进行数据共享,它不支持“multi-key”操作(即执行的命令需要在多个 Redis 节点之间移动数据,比如 Set 类型的并集、交集等(除非这些 key 属于同一个 node),即 Cluster 不能进行跨 Nodes 操作。如下:

10.9.42.37:6102> smembers set1
-> Redirected to slot [3037] located at 10.9.33.204:6101
1) "d"
2) "b"
3) "g"
4) "c"
5) "a"
6) "f"
7) "e"
(1.08s)
10.9.33.204:6101> smembers set2
-> Redirected to slot [15294] located at 10.9.33.204:6103
1) "b"
2) "c"
3) "f"
4) "g"
5) "h"
6) "i"
7) "a"
10.9.33.204:6103> sunion set1 set2
(error) CROSSSLOT Keys in request don't hash to the same slot

Redis 为了兼容 multi-key 操作,提供了 **“hash tags”** 操作,每个 key 可以包含自定义的“tags”,在存储的时候根据 tags 计算此 key 应该映射到哪个 node 上。通过“hash tags”可以强制某些 keys 被保存到同一个节点上,便于进行“multi key”操作。基本上如果关键字包含“{…}”,那么在 {和} 之间的字符串被 hash,然而可能有多个匹配的 {或} 该算法由以下规则规定:如果 key 包含{,在{的右边有一个},并在第一次出现{与第一次出现}之间有一个或者多个字符串,那么就作为 key 进行 hash。例如,{user1000}.following 和 {user1000}.followed 就在同一个 hash slot;foo{}{bar} 整个字符被 hash,foo{{bar}},{bar 被 hash;foo{bar}{zap},bar 被 hash。如下所示:

10.9.33.204:6103> set {user1000}.following 1000
10.9.33.204:6101> set {user1000}.followed 1000
10.9.33.204:6101> keys *
4) {user1000}.following
6) {user1000}.followed

特殊说明一点,在 ==resharding== 期间,原来同一个 slot 的 keys 被迁移到不同的 node 中,multi-key 操作可能不可用。

数据一致性保证 Redis 集群尽可能保证数据的强一致性,但在特定条件下会丢失数据,原因有两点:异步 replication 机制以及 network partition。

Master 以及对应的 Slaves 之间使用异步的机制,在节点 failover 后,新的 Master 将会最终替代其他的 replicas:

write命令提交到Master,Master执行完毕后向Client返回“OK”,但由于一部分replication,此时数据还没传播给Slave;如果此时Master不可达的时间超过阀值,此时集群将触发对应的slave选举为新的Master,此时没有replication同步到slave的数据将丢失。

在 network partition 时,总有一个窗口期(node timeout)可能会导致数据丢失:

由于网络分区,此时master不可达,且Client与Master处于一个分区,且此时集群处于“OK”。此时Failover机制,将其中一个Slave提升为新的Master,等待网络分区消除后,老的Master再次可达,此时节点被切换为Slave,而在这段期间,处于网络分区期间,Client仍然将write提交到老的Master,因为该Master被认为是仍然有效的。当老的Master再次加入集群,被切换成Slave后,这些数据将永远丢失。

网络分区

集群可用性 上述谈到多次集群状态的概念,那集群什么时候处于“OK”,什么时候处于“FAIL”,节点什么时候可用等,详见下面的解释:
== 当 NODE_TIMEOUT 时,触发 failover,此时集群仍然可用的前提是:“大分区”(相对发生网络分区的 Client-Master 小分区端而言)端必须持有大部份 Masters,且每个不可达的 Master 至少有一个 Slave 也在“大分区”端,且集群在小部分 Nodes 失效后仍然可以恢复有效性。== 举个例子:

集群有N个Master,且每个Master都有一个Slave,那么集群的可用性只能容忍一个Master节点被分区隔离,也就是说只有一个Master处于小分区端,当第二个Master节点被分区隔离之前扔保持可用性的概率为1-(1 /(N*2-1)),这里的意思是:当第一个节点失效后,剩余N*2-1节点,此时没有Slave的Master失效的概率为1 /(N*2-1)。比如有10个节点,每个Master有一个Slave,当2个nodes被隔离或失效后,集群可用性的概率是:1/(10*2-1)=5.26%,此时集群不再可用。

为了避免上述情况发生,Redis Cluster 提供了“replicas migration”机制,当 Master 节点发生 failover 后,集群会动态重新分配、平衡 Slaves 的分布,有效地提高了集群的可用性。

从节点选举逻辑

  • 节点是已下线 Master 对应的 Slave

  • FAIL 状态的 Master 负责的 hash slot 非空

  • 主从节点之间的 replication link 断线的时长不能超过NODE_TIMEOUT * REDIS_CLUSTER_SLAVE_VALIDITY_MULT

Nodes handshake Nodes 通过端口发送 Ping、Pong,除了 Ping 之外,节点会拒绝其他所有非本集群节点的 packets,一个节点注册成为集群的新成员有 2 中方法:

  • 通过“Cluster meet”指令引入,即将指定的 node 加入集群,集群将认为指定的 node 为“可信任”。

  • 当其他 nodes 通过 gossip 引入了新的 nodes,这些 nodes 也是被认为是“可信任的”。即:如果 A 信任 B,B 信任 C,且 B 向 A 传播关于 C 的信息,那么 A 也信任 C,并尝试连接 C。

重定向与 resharding  

MOVED 重定向 Client 可以将请求发给任意一个 Node,包含 Slaves,Node 解析命令,检查语法,multiple keys 是否在同一个 slot。如果当前 node 持有该 slot,那么命令直接执行并返回,否则当前 Node 向 Client 返回“MOVED”错误。

10.9.33.204:6101> keys *
1) test9
10.9.33.204:6101> get test9
value9
10.9.33.204:6101> get test8
(error) MOVED 905 10.9.42.37:6101

905 指 test8 对应的 slot,10.9.42.37:6101 指 slot 所在的 Node 的 ip:port,Client 根据返回信息,重定向至指定的 Node。若此过程中集群发生变更(配置调整、failover、resharding 等),原来返回到 Client 可能已失真,重新发送命令时,可能会再次发生 MOVED 错误。

Redis 集群提供集群模式的客户端,在跳转时会自动进行节点转向,以下是常用的:

Shell 终端:redis-cli -c -h 10.9.33.204 -p 6101,集群提示重定向至 Key 所在的 Slot:

10.9.33.204:6101> keys *
1) test9
10.9.33.204:6101> get test8
-> Redirected to slot [905] located at 10.9.42.37:6101
value8

Java:JedisCluster,需要配置集群信息,其他 API 如 Jedis 差异不大

<bean id="jedisClusterRaw" class="redis.clients.jedis.JedisCluster">
  <constructor-arg index="0">
    <set>
      <bean class="redis.clients.jedis.HostAndPort">
        <constructor-arg type="String" value="${redis.host1}"/>
        <constructor-arg type="int" value="${redis.port1}"/>
      </bean>
    </set>
  </constructor-arg>
  <constructor-arg index="1" ref="jedisPoolConfig" />
</bean>
private static String configLocation = "classpath*:config-spring.xml";
private static ApplicationContext ctx = new ClassPathXmlApplicationContext(configLocation);

private void testCluster() {
  JedisCluster jedisCluster = ctx.getBean("jedisClusterRaw", JedisCluster.class);
  String v = jedisCluster.get("test6");
  System.out.println("v:" + v);
}

ASK 重定向 ASK 重定向与 MOVED 重定向非常相似,两者最大的区别在于在 resharding 期间,当前的 Client 发送的命令暂时与指定的 Node 交互,在迁移期间,slot 原来的 keys 仍有可能在原来的节点上,所以 Client 的命令仍然先经过原来的节点,对于不存的节点,再到新的节点进行尝试获取,一旦完成 slot 的迁移,原来 slot 接收到 Client 命令请求,则节点向客户端返回 MOVED 转向。对比 ASK 重定向,MOVED 重定向指 hash slots 已经永久地被另一个 node 接管,后续 Client 的命令都是与该 Node 交互。ASK 是 Redis 集群非阻塞的表现,即 Redis 集群不会因 slot resharding 而导致整个集群不可用。

容错  

节点失效检测 跟大部份分布式框架一样,Redis Cluster 节点间通过持续的心跳来保持信息同步,不过 Redis Cluster 节点信息同步是内部实现的,不依赖第三方组件,如 zk。集群中的 nodes 持续交换 ping、pong 数据,消息协议使用 Gossip,这两种 packet 数据结构一样,它们之间通过 type 字段区分。

节点定时向其他节点发送 ping 命令,它会随机选择存储的其他集群节点的其中三个进行信息“广播”,例如广播的信息包含一项是节点是否被标记为 PFAIL/FAIL。PFAIL 表示“可能已失效”,是尚未完全确认的失效状态(即可能是某个节点或少数 Master 认为其不可达);FAIL 表示 Node 被集群大多数的 Masters 认定为失效(即大多数 Master 已认定为不可达,且不可达的时间已经超过配置的 NODE_TIMEOUT)。

当节点收到其他节点广播的信息,它会记录被其他节点标记为失效的节点。举个例子,如果节点被某个节点标记为 PFAIL,集群中大部份其他主节点也认为该节点进入了失效状态,那么该节点的状态会被标志为 FAIL。当节点被标志为 FAIL,这个节点已失效的信息会被广播至整个集群,所有集群中的节点都会将失效的节点标志为 FAIL。

集群失效检测 当某个 Master 或者 Slave 不能被大多数 Nodes 可达时,用于故障迁移并将合适 Slave 提升为 Master。当 Slave 提升未能成功,集群不能正常工作。即集群不能处理 Client 的命令的请求,当 Client 发出命令请求时,集群节点都将返回错误内容的 respone。

集群正常工作时,负责处理 16384 个 slots 的节点中,全部节点均正常。反之,若集群中有一部分 hash slot 不能正常使用,集群亦将停止工作,即集群进入了 FAIL 状态。对于集群进入 FAIL 状态,会有以下两种情况:

  • 至少有一个 hash slot 不可用。

  • 集群中大部份 Master 都进入了 PFAIL 状态。

上述为Redis集群原理概述,下面我们对比一下其他的Redis集群方案。 
Redis 集群方案对比   客户端分片  

image

  • 逻辑都是可控的,不依赖第三方分布式中间件

  • 静态的数据分片,需要增加或减少 Redis 实例的数量,需要手工调整分片的程序

  • 运维成本高,拓展需要手工操作

  • 跨系统、平台维护相同的分片逻辑成本高,例如一个终端是 PHP、另一个终端是 JAVA,需要实现两套不同的分片逻辑

Twemproxy  

image

  • Redis 客户端把请求发送到 Twemproxy,路由规则发送到正确的 Redis 实例

  • LVS 集群:实现 twemproxy 的负载均衡,提高 proxy 的可用性和扩容能力,使得 twemproxy 对应用透明

  • Sentinel 集群:检测 Redis 主从的存活状态,当 redis master 失效,把 slave 提升为新的 master

  • 支持无效 Redis 实例的自动删除

  • 减少客户端与 Redis 实例的连接数

但由于需要依赖组件较多和 Redis 请求都需要经过代理,在这过程中会造成性能损失,Twemproxy 单节点的吞吐量对比 Redis 单实例,吞吐量要低不少,另外 Twemproxy 无法支持平滑支持 Redis 节点。

Codis  

image

  • 支持平滑增加 / 减少 Reids 实例

  • Codis Proxy:客户端连接的 Redis 代理服务

  • Codis Manager:Codis 的管理工具

  • Codis Redis:维护 Redis 分支,基于 2.8.13 开发

  • Zookeeper:存放数据路由表和 codis-proxy 节点的元信息

附几张 CodisManager 的使用截图:

概览 Dashboard

image

Slots 分布

image

Slot 迁移操作

image

当然 Codis 也有自身的一些缺陷,例如主从同步需要用户自身实现。

Redis Cluster  

Redis 集群根据上述说明,可以了解到,框架是采用 P2P 的模式,完全去中心化,数据存储模块和分布式的逻辑模块耦合在一起。这样带来的好处是部署非常简单,一体式部署,相对 Codis 而言,没有太多的其他概念、组件和依赖。但缺点也是比较明显,譬如分布式逻辑出现 bug,只能回滚重启整个集群。

同时,我们通过上述可以了解到,Redis 集群对协议进行了较大的修改,对客户端的交互升级不少,见上述“MOVED 重定向”的客户端实现。由于历史原因,历史的应用均使用传统的 Redis API,若业务更换 Redis Client,存在不少问题,例如升级工作、数据迁移及测试,所以业内暂未被大规模使用。

总结  

综上所述,回答了以下问题:

Redis 集群为了解决什么问题而存在的? 解决线性可扩展性。

Redis 集群诞生以前怎么解决这个问题? 客户端分片、代理协助分片 (Twemproxy)、查询路由、预分片、一致性哈希、客户端代理 / 转发等。

Redis 集群采用什么方式保证线性可扩展性、可用性、数据一致性? Hash 槽、查询路由、节点互联的混合模式。

Redis 集群化面临的问题是什么? Redis 集群本身要解决的是可伸缩问题,同时数据一致、集群可用等一系列问题。前者涉及到了节点的哈希槽的分配 (含重分配),节点的增删,主从关系指定与变更(含自动迁移) 这些具体的交互过程;后者则是故障发现,故障转移,选举过程等详细的过程。

Redis 集群实现的核心思想和思路是什么? 通过消息的交互(Gossip)实现去中心化 (指的是集群自身的实现,不是指数据),通过 Hash 槽分配,实现集群线性可拓展。

写在最后  
以上是在研究/使用Redis集群过程中的一点思考与总结,好记性不如烂笔头,多多积累,以开阔思路,更好解决工作中遇到的问题。
参考资料  

Redis 官网
CodisLabs

附录一  

Gossip 协议 Gossip 也称“病毒感染算法”、“谣言传播算法”,Redis 集群节点间使用 Gossip 协议交互。以下是 Gossip 算法的描述:

  • 在总数为 n+1 的人群中,被感染的人数初始化为 1,并向周围传播。(一个节点状态发生变化,并向邻近节点发送更新信息)
    image

  • 在每个周期内总有未被感染的人转变为被感染的人,方式为每个被感染的人随机感染 b 个人。(对于节点状态变化的信息随机发送给 b 个节点,下图 b 值为 2,Redis Cluster 中默认值为 3)
    image

  • 经过足够的时间,所有人都会被感染。(随着时间推移,信息能够传递到所有节点)
    image

对于 Redis Cluster 而言,node 首先需要知道集群中至少一个 seed node,此 node 向 seed 发送 ping 请求,接收到 seed 节点 pong 返回自身节点已知的所有 nodes 列表,然后与 node 解析返回的 nodes 列表并与之建立连接,同时也会向每个 nodes 发送 ping,并从 pong 结果中 merge 出全局的 nodes 列表,并与之逐步建立连接。另数据传输的方式也是类似,如上述 gossip 协议。