分布式和CAP讨论

CAP定理

简介

一个分布式系统，不可能同时满足CAP

• 一致性：在写操作之后，所有节点都返回最新的值。
• 可用性：所有节点收到请求，都必须给出响应。
• 分区容错性：无法保证所有节点同时更新，区间通信可能失败。

数据模型

• 分散式机制将元数据存储在部分或者所有节点上，不同节点之间进行不断的通信来维护元数据的变更和一致性
• 集中式是将集群元数据集中存储在外部节点或者中间件上

优缺点

• 集中式数据更新实效性好，但Zookeeper节点压力较高
• 分散式数据更新有一定滞后，但分散了请求压力

算法

• 分散式: Paxos、Raft 和 Gossip。(Paxos 和 Raft 等都需要全部节点或者大多数节点(超过一半)正常运行，整个集群才能稳定运行，而 Gossip 则不需要半数以上的节点运行)

etcd与raft协议

逐步补充

redis与gossip协议

gossip

Gossip 协议又称 epidemic 协议（epidemic protocol），是基于流行病传播方式的节点或者进程之间信息交换的协议，在P2P网络和分布式系统中应用广泛，它的方法论也特别简单：

x
在一个处于有界网络的集群里，如果每个节点都随机与其他节点交换特定信息，经过足够长的时间后，集群各个节点对该份信息的认知终将收敛到一致。

• 特定信息: 一般就是指集群状态、各节点的状态以及其他元数据等

• Gossip 协议的最大的好处是，即使集群节点的数量增加，每个节点的负载也不会增加很多，几乎是恒定的。这就允许 Redis Cluster 或者 Consul 集群管理的节点规模能横向扩展到数千个。

redis集群实现

集群示意图

关键组件

键分布模型

• 键空间被分割为 16384 槽（slot），事实上集群的最大节点数量是 16384 个。（然而建议最大节点数量设置在1000这个数量级上）
• 把键映射到哈希槽的算法： CRC16

键哈希标签

• 计算哈希槽可以实现哈希标签（hash tags）
• 只有在第一个 { 和它右边第一个 } 之间的内容会被用来计算哈希值
• 比如foo{bar}{zap} ，会用bar去计算哈希槽

集群节点属性

每个节点都有一个唯一的名字。节点名字是一个十六进制表示的160 bit 随机数。

节点会把它的ID保存在配置文件里，以后永远使用这个ID，只要这个节点配置文件没有被系统管理员删除掉。

每个节点都有其他相关信息是所有节点都知道的：

• 节点的 IP 地址和 TCP 端口号。
• 各种标识。
• 节点使用的哈希槽。
• 最近一次用集群连接发送 ping 包的时间。
• 最近一次在回复中收到一个 pong 包的时间。
• 最近一次标识节点失效的时间。
• 该节点的从节点个数。
• 如果该节点是从节点，会有主节点ID信息。（如果它是个主节点则该信息置为0000000…

使用 CLUSTER NODES 命令可以获得以上的一些信息

xxxxxxxxxx
$ redis-cli cluster nodes
d1861060fe6a534d42d8a19aeb36600e18785e04 127.0.0.1:6379 myself - 0 1318428930 1 connected 0-1364
3886e65cc906bfd9b1f7e7bde468726a052d1dae 127.0.0.1:6380 master - 1318428930 1318428931 2 connected 1365-2729
d289c575dcbc4bdd2931585fd4339089e461a27d 127.0.0.1:6381 master - 1318428931 1318428931 3 connected 2730-4095

集群拓扑结构

Redis 集群是一个网状结构，每个节点都通过 TCP 连接跟其他每个节点连接

在一个有 N 个节点的集群中，每个节点都有 N-1 个流出的 TCP 连接，和 N-1 个流入的连接。 这些 TCP 连接会永久保持，并不是按需创建的。

集群处理具体流程: Redis 集群规范

gossip协议消息类型(cluster.h)

/* Message types.
 *
 * Note that the PING, PONG and MEET messages are actually the same exact
 * kind of packet. PONG is the reply to ping, in the exact format as a PING,
 * while MEET is a special PING that forces the receiver to add the sender
 * as a node (if it is not already in the list). */
#define CLUSTERMSG_TYPE_PING 0          /* Ping */
#define CLUSTERMSG_TYPE_PONG 1          /* Pong (reply to Ping) */
#define CLUSTERMSG_TYPE_MEET 2          /* Meet "let's join" message */
#define CLUSTERMSG_TYPE_FAIL 3          /* Mark node xxx as failing */
#define CLUSTERMSG_TYPE_PUBLISH 4       /* Pub/Sub Publish propagation */
#define CLUSTERMSG_TYPE_FAILOVER_AUTH_REQUEST 5 /* May I failover? */
#define CLUSTERMSG_TYPE_FAILOVER_AUTH_ACK 6     /* Yes, you have my vote */
#define CLUSTERMSG_TYPE_UPDATE 7        /* Another node slots configuration */
#define CLUSTERMSG_TYPE_MFSTART 8       /* Pause clients for manual failover */
#define CLUSTERMSG_TYPE_MODULE 9        /* Module cluster API message. */
#define CLUSTERMSG_TYPE_PUBLISHSHARD 10 /* Pub/Sub Publish shard propagation */
#define CLUSTERMSG_TYPE_COUNT 11        /* Total number of message types. */

扩展到业务场景

CAP一般讨论分布式存储一致性问题。扩展到经典业务场景，比如分布式系统中，购买后发道具：购买成功后发放5个道具，用户查询领取情况，保证最终发放成功。

分布式系统中，调用可能出现的3种状态

解决方案

对于这个异步场景来说，应优先保证可用性和分区容错性，确保数据最终一致性即可

• 可用性：用户查询到不同节点，都需要有合理响应
• 分区容错性：发放道具可能失败
• 一致性：查询到所有成功领取的道具

解决

• 引入重试服务和订单号机制，分别确保最终成功和幂等性(不会重复执行)

参考

一万字详解 Redis Cluster Gossip 协议

Redis 集群规范

Redis 集群教程