分布式系统中的一致性协议

在分布式系统中，分布式理论CAP中的P（分区容忍性）是必然存在的，所以需要在C（一致性）和A（可用性）之间进行取舍。而在很多系统中，引入分布式完全是为了解决单机的单点故障问题，引入分布式而使得系统变得高可用，所以很多系统放弃了C（一致性），是一个AP模型，为了保证数据的一致性，所以引入了下面一系列的理论与实现。

一致性模型

数据一致性可以简单分为三种类型（当然，如果细分的话，还有很多一致性模型，如：顺序一致性，FIFO一致性，会话一致性，单读一致性，单写一致性。。。）：

• 弱一致性：当写入一个新值后，读操作在数据副本上可能读出来，也可能读不出来。
• 最终一致性：当你写入一个新值后，有可能读不出来，但在某个时间窗口之后保证最终能读出来。
• 强一致性：新的数据一旦写入，在任意副本任意时刻都能读到新值。

总结：弱一致性和最终一致性一般来说是异步冗余的，而强一致性一般来说是同步冗余的，异步的通常意味着更好的性能，但也意味着更复杂的状态控制。同步意味着简单，但也意味着性能下降。

2PC

两阶段提交又称2PC，2PC是一个非常经典的强一致、中心化的原子提交协议，协议中有两类角色，1个协调者与N个参与者。

2PC分为两个阶段：

• 第一阶段：投票阶段。协调者发起一个投票，分别询问各个参与者是否接受。
• 第二阶段：提交/执行阶段。协调者根据上一个阶段中参与者的反馈，提交或回滚事务。如果参与者全部同意则提交事务，只要有一个参与者不同意就回滚事务。

优点：原理简单，实现方便。

缺点：

• 同步阻塞：执行过程中，所有参与节点都是事务阻塞型的。如果其中一个参与者执行超时或者挂了，那么其他参与者就必须回滚，白忙活了。
• 单点故障：由于协调者的重要性，一旦协调者发生故障。参与者会一直阻塞下去。尤其在第二阶段，协调者发生故障，那么所有的参与者还都处于锁定事务资源的状态中，而无法继续完成事务操作。
• 数据不一致：在第二阶段中，可能由于网络等原因只有部分参与者收到了commit请求后执行了commit操作，而其他参与者未收到commit请求而导致事务无法提交，这样就出现了数据的不一致。

3PC

三阶段提交协议（3PC）主要是为了解决两阶段提交协议的阻塞问题，3PC把2PC的投票阶段再次一分为二，这样三阶段提交就有CanCommit、PreCommit、DoCommit三个阶段。

• CanCommit阶段：只是询问所有参与者是否可以执行事务操作，并不在本阶段执行事务操作。相当于ping一下各个参与者，看网络是否畅通。
• PreCommit阶段：相当于两阶段提交中的第一阶段。
• DoCommit阶段：相当于两阶段提交中的第二阶段。

优点：相比两阶段提交，改善了单点故障和同步阻塞，这样如果有网络问题，第一阶段CanCommit就能立马发现，不像两阶段提交需要等到后面发现了再回滚。

缺点与2PC一样。

Paxos

Paxos将系统中的角色分为提议者(Proposer)，决策者(Acceptor)，和最终决策学习者(Learner):

• Proposer: 提出提案 (Proposal)。Proposal信息包括提案编号 (Proposal ID) 和提议的值 (Value)。
• Acceptor：参与决策，回应Proposers的提案。收到Proposal后可以接受提案，若Proposal获得多数Acceptors的接受，则称该Proposal被批准。
• Learner：不参与决策，从Proposers/Acceptors学习最新达成一致的提案（Value）。

Paxos协议流程划分为两个阶段：

• prepare阶段：Proposer选择一个提案编号n并将prepare请求发送给Acceptors，Acceptor收到prepare消息后，如果提案的编号大于它已经回复的所有prepare消息，则Acceptor将自己上次接受的提案回复给Proposer，并承诺不再回复小于n的提案；
• accept阶段：当一个Proposer收到了多数Acceptors对prepare的回复后，就进入批准阶段。它要向回复prepare请求的acceptors发送accept请求，在不违背自己向其他proposer的承诺的前提下，acceptor收到accept请求后即接受这个请求。

Zab

Zab（Zookeeper Atomic Broadcast，Zookeeper原子广播协议）：是为分布式协调服务Zookeeper专门设计的一种支持崩溃恢复的原子广播协议，是Zookeeper保证数据一致性的核心算法。Zab协议Zab借鉴了Paxos算法，但又不像Paxos那样，是一种通用的分布式一致性算法。

ZAB协议两种模式：消息广播和崩溃恢复，整个 Zookeeper 就是在这两个模式之间切换。 简而言之，当Leader服务可以正常使用，就进入消息广播模式，当Leader不可用时，则进入崩溃恢复模式。

消息广播（投票）

消息广播的过程实际上是一个简化的2PC提交过程：

1. 客户端发来的所有事务性请求（增删改）都会发送给Leader接收，Leader接收到消息请求后，将消息赋予一个全局唯一的64位自增id，叫做zxid，Leader通过先进先出队列将带有zxid的消息作为一个提案（proposal）分发给所有follower。
2. 当follower接收到proposal，先把proposal写到磁盘，写入成功以后再向leader回复一个ack。
3. 当Leader接收到Follower超过半数的成功ACk响应后，先提交自己本地的事务，然后向所有的follower发送commit命令。

通过以上三个步骤，就能够保持集群之间数据的一致性。实际上，在Leader和Follwer之间还有一个消息队列，用来解耦他们之间的耦合，避免同步，实现异步解耦。

崩溃恢复（选举）

当Leader挂掉不可用时，则进入崩溃恢复模式。

1. 每个Server会发出一个投票，第一次都是投自己，投票信息：（myid，ZXID）。
2. 收集来自各个服务器的投票，处理投票并重新投票，处理逻辑：优先比较ZXID，然后比较myid。
3. 统计投票，只要超过半数的机器接收到同样的投票信息，就可以确定leader，改变服务器状态。

为了使Leader挂了后系统能正常工作，需要解决以下两个问题：

• 已经被处理的消息不能丢：如果Leader在发送commit命令时挂了，导致只有部分Follower提交commit了，这样只需要选举zxid最大的为Leader，这样已经被处理的消息就不会丢失了。
• 被丢弃的消息不能再次出现：zxid是一个64位的数字，低32位是一个简单的计数器，高32位代表Leader周期epoch的编号，每选举一次epoch就会加1，计数清零，重新开始，基于这样的策略，假如Leader在事务还没提交就挂了，然后以Follower的身份连接上新的Leader之后，曾经的Leader服务器会根据自己服务器上最后被提交的ZXID和现在的Leader上的ZXID进行比对，比对结果要么回滚，要么和新的Leader进行同步。