整理下分布式系统问题的答案(1)

分布式系统主要为了解决集中式系统的性能瓶颈，支持高并发及海量数据处理，需要做到高可扩展性、高可用、服务和存储无状态。

分布式系统中经常会出现网络故障、通信失败、数据不一致等问题，为此提出了 CAP 理论：一个分布式系统最多只能同时满足一致性（Consistency）、可用性（Availability）和分区容忍性（Partition Tolerance）这三项中的两项。

C：所有节点同时看到相同的数据
A：任何时候，读写都是成功的
P：当部分节点出现消息丢失或者分区故障时，分布式系统仍然能够继续运行

分布式系统中 P 基本是必需，所以 CAP 模型的应用的一般是 CP 或 AP 架构。

用反证法理解 CAP 最为简单与直接，假设分布式系统满足了分区容错，
client1 写入x=1成功 -> server1(x=1) <- client2读x=1

client3 写入x=1失败 -> server2(x=0) <- client4读x=0
为了提高一致性，就要回滚 server1 -> x = 0，降低了可用性；
为了提高可用性，就要降低对一致性的要求，server1 x=1,server2 x=0。

其他场景证明类似。

CAP 理论是绝对情况，工程上一般关注相对一致的情况下，提高系统的可用性，所以就有了对一致性和可用性的取舍。

ZooKeeper 就为了解决应用系统的协调和一致性问题的框架，属于 CP 架构，其核心算法就是 Zab，来保证一致性。

AP 架构放弃强一致性，保证分区容错和可用性，Base 理论就是从 AP 扩展而来；Spring Cloud 中的 Eureka 属于 AP 架构，Eureka 的各个节点平等，几个节点挂掉不影响正常节点的工作，只要还有一个 Eureka 节点，就能保证注册服务可用，但查到的信息可能不是最新的版本，不保证数据一致性。

放弃 CAP 理论中的强一致性，提出 Base 理论：
无法做到强一致性（Strong Consistency），但每个应用都可以根据自身的业务特点，采用适当的方式来使系统达到最终一致性（Eventual Consistency）。

Base 这个单词来自于，基本可用（Basically Available）、软状态（Soft State）和最终一致性（Eventually Consistent）。

Base 理论是从 CAP 发展而来、在分区和副本存在的前提下，通过系统设计方案，放弃强一致性，实现基本可用、最终一致。

先看保证一致性的两种机制：

1、Write All Read one，所有节点写成功才算成功，从任意一个节点读都是最新数据；

2、Quorum 机制，在 N 个副本中，一次更新成功的如果有 W 个，那么在读取数据时从大于 N－W 个副本中读取，这样就至少读到一个更新成功的数据。如，10 个副本，更新成功 5 个，只要读大于 10-5=5，即访问 6 个节点至少能读到一个最新的值。Paxos 算法就用到了此机制。

再看 Paxos 算法，它主要解决一致性问题，在分布式领域具有非常重要的地位。

逻辑上包含三类节点角色：

• Proposer 提案者，提出议案，议案即操作，被抽象为 value，如更新某值

• Acceptor 批准者，完全对等独立，Proposer 提出的 value 必须获得超过半数（N/2+1）的 Acceptor 批准后才能通过

• Learner 学习者，不参与选举，而是学习被批准的 value，至少读取 N/2+1 个 Accpetor，才能学习到一个通过的 value

选举过程是 Paxos 算法中最核心的内容，包含两个阶段：

阶段1、准备阶段
Proposer 生成全局唯一且递增的 ProposalID，向 Paxos 集群的所有机器发送 Prepare 请求，不携带 value，只携带 ProposalID

Acceptor 收到 Prepare 请求后，收到的 ProposalID 比之前已响应的所有提案的大

• 在本地持久化 ProposalID，可记为 Max_ProposalID；

• 回复请求，并带上已经 Accept 的提案中 ProposalID 最大的 value，如果此时还没有已经 Accept 的提案，则返回 value 为空；

• 做出承诺，不会 Accept 任何小于 Max_ProposalID 的提案。

否则，不回复或回复 Error

阶段2、选举阶段

Proposer 发送 Accept

Proposer 收集到一些 Prepare 回复，有 3 种情况：

• 若回复数量 > 一半的 Acceptor 数量，且所有回复的 value 都为空时，则 Porposer 发出 accept 请求，并带上自己指定的 value。

• 若回复数量 > 一半的 Acceptor 数量，且有的回复 value 不为空时，则 Porposer 发出 accept 请求，并带上回复中 ProposalID 最大的 value，作为自己的提案内容。

• 若回复数量 <= 一半的 Acceptor 数量时，则尝试更新生成更大的 ProposalID，再转到准备阶段执行。

Acceptor 应答 Accept 

Accpetor 收到 Accpet 请求后，判断：

• 若收到的 ProposalID >= Max_ProposalID，则回复提交成功，并持久化 ProposalID 和 value；

• 若收到的 ProposalID < Max_ProposalID，则不回复或者回复提交失败。

Proposer 统计投票 

经过一段时间后，Proposer 会收集到一些 Accept 回复提交成功的情况，比如：

• 当回复数量 > 一半的 Acceptor 数量时，则表示提交 value 成功，此时可以发一个广播给所有的 Proposer、Learner，通知它们已 commit 的 value；

• 当回复数量 <= 一半的 Acceptor 数量时，则尝试更新生成更大的 ProposalID，转到准备阶段执行。

• 当收到一条提交失败的回复时，则尝试更新生成更大的 ProposalID，也会转到准备阶段执行。

Zab(ZooKeeper Atomic Broadcast，ZooKeeper 原子广播协议) 是 ZooKeeper 保证事务一致性的协议，分为消息广播、崩溃恢复、数据同步阶段。Zab 协议是基于 Paxos 算法实现。

两者联系：

• 都存在一个 Leader 进程的角色，负责协调多个 Follower 进程的运行

• 都应用 Quorum 机制，Leader 进程都会等待超过半数的 Follower 做出正确的反馈后，才会将一个提案提交

• 在 Zab 协议中，Zxid 中通过 epoch 来代表当前 Leader 周期；在 Paxos 算法中叫 Ballot Number

区别：

• Paxos 是论文性质的理论，目的是设计一种通用的分布式一致性算法；而 Zab 协议是应用在 ZooKeeper 中对 Paxos 的实践，是一个为解决一致性特别设计的崩溃可恢复的原子消息广播算法。