2020-07-31

分布式系统简介

1. 分布式系统理论基础
2. 分布式系统的一致性协议
3. 参考

1. 分布式系统理论基础

CAP定理，又被称作布鲁尔定理（Brewer’s theorem），民间又称帽子定理，是加州大学伯克利大学埃里克·布鲁尔在2000年的PODC(分布式计算原理研讨会)上提出的一个猜想，随后在2002年，MIT的赛斯·吉尔伯特和南希·林奇发表了布鲁尔猜想的证明，使之成为一个定理。CAP的概念如下：

Consistency(一致性)：对于每次读取，都会返回最新的修改，或者错误；
Availability(可用性)：每次请求都会有响应，但不保证该响应是最新的修改；
Partition tolerance(分区容错性)：在服务节点之间的消息出现丢失或者延迟的情况下，系统任然可以工作。

在分区的服务架构下，分区容错性是最基本需要保证的，所以当分区的各个服务之间网络发生问题时，我们有两种选择：

不响应操作，降低可用性，以保证一致性；
响应请求，以保证可用性，但会出现不一致的风险；

所以CAP理论表明：在服务存在网络分区的情况下，只能在一致性和可用性上二选一。

**ACID**理论，是1983年，Andreas Reuters和Theo Härder提出的概念，是专门为数据库管理系统提出的理论，每个数据库的事务操作都应该满足的特性，ACID的特性如下：

Atomicity(原子性)：将一个事务的多个操作看成一个单元，需保证全部成功，或者全部失败，不会存在其他状态。即如果事务的执行过程中出现失败，需将系统回滚到事务执行前的状态。
Consistency(一致性)：对数据库的写入操作必须符合所有规则，例如：约束、触发器、级联回滚等，防止非法的事务导致数据库崩溃。
Isolation(隔离性)：隔离的目标是为了并发控制，对于并发执行的事务，隔离可确保其和顺序执行的事务有相同的状态迁移。
Durability(持久性)：事务成功提交后，无论什么情况，对应数据的修改也必须成功提交。

**BASE**理论的提出，是对CAP的C和A的一个权衡，它的理念和传统数据库事务ACID的特性是相反的，它不需要强一致性，是现代大型高可用的分布式系统的基本设计理论，BASE特性要求如下：

Basically Available(基本可用)：和CAP的A类似，保证基本的读写操作尽可能可用，但不保证一致性，即写操作在冲突后可能会失败，读操作获取的不一定是最新的数据。
Soft state(软状态)：系统不要求一直保持强一致状态；
Eventually consistent(最终一致性)：对于数据的修改，系统在某一时刻后达到一致性要求；

BASE英文的“碱”的意思，和ACID在英文中“酸”的意思，基于此有了酸碱平衡的结论，简单来说是在不同的场景下，可以分别利用ACID和BASE来解决分布式服务化系统的一致性问题。

2. 分布式系统的一致性协议

对于一般的分布式服务的最终一致性和可用性是我们基本采用的策略，那下面介绍分布式事务常用的一些策略和标准。

2PC-两阶段提交协议

两阶段提交协议2PC(Two-phase commit protocol)是一种分布式协调算法，可以用来协调分布式系统中所有参与者在进行事务提交时保持一致性，要么全部提交，要么全部终止。2PC是XA标准所采用的协议，X/Open XA(eXtended Architecture)标准是X/Open在1991为了分布式事务处理DTP(Distributed Transaction Processing)所提出的。后来XA标准被合入The Open Group(国际开放标准组织)。

分布式系统中，当一个事务跨越多个节点时，由于存在网络分区的原因，无法真正知道这些节点的操作是否成功或失败。为了保证事务的ACID特性，需要引入一个Coordinator协调者，分布式事务的其他节点都是Participants参与者。两阶段提交的过程如下：

准备阶段Commit request(or voting) Phase

Coordinator向所有Participant发送提交请求的查询，参与者对提交进行评估，如果通过的话，会写undo log(撤销日志)和redo log(重做日志)，然后锁定资源，执行事务，但并不提交，最后回复确认给Coordinator。
提交阶段Commit(or completion) Phase

如果所有Participants都确认成功：Coordinator向所有的Participant发起提交指令；所有Participant提交之前未提交的事务，释放锁定资源，回复确认；Coordinator收到所有确认后，提交完成；

如果有Participants确认失败：Coordinator向所有的Participant发起终止指令，每个Participant通过undo log执行撤销操作，释放锁定资源，回复确认；Coordinator收到所有确认后，撤销完成；

两段提交协议的能够顺利执行有以下假设前提，所有节点(协调者和参与者)：

每个节点对于Write-Ahead日志具有稳定的存储；
没有节点会永远宕机；
Write-Ahead永远不会再宕机中丢失或者损坏；
任何两个节点之间都可以通信；

但现实中2PC顺利执行的假设前提不可能得到保证。

2PC本身有以下几个问题：

一个阻塞协议；参与者在回复准备成功后，其资源是锁定状态，直到接收到协调者的提交或撤销指令。
单点问题；如果协调者宕机，参与者只能一直锁定资源，直到协调者恢复。常用的解决方案是协调者采用主备方案，宕机后备机拉起，然后接替主机的工作，通过Query 各Participant的状态，决定阶段2是提交还是中止。
不一致问题；如果在Commit阶段，Coordinator只发送了一部分Commit协议就宕机了，那么会导致所有的Participants出现数据不一致的问题。
协调者和参与者都在提交阶段宕机，这样协调者恢复后，或者拉起新的协调者都无法知道参与者有没有进行提交，只能等待所有参与者回复提交确认，协调者和参与者可能会卡死在这，只能等到所有节点的恢复。

2PC通过Commit Request阶段来保证了事务不会因为逻辑失败而带来的不一致性问题。但是不能解决因为网络分区带来的超时，宕机等系统异常所导致的不一致性问题。

3PC-三阶段提交协议

(Three-phase commit protocol)是对2PC的改进，对故障的具有更好的恢复能力。最早提出在1982年Skeen发表的A Quorum-Based Commit Protocol论文中。

为了解决协调者和参与者在Commit Request/Commit Phase同时宕机所带来阻塞的问题，3PC引入了一个新的阶段：Prepared to commit，以及超时处理机制。

准备阶段Commit request(or voting) Phase

Coordinator向所有Participant发送提交请求的查询，参与者对提交进行评估，如果通过的话，回复Yes，否则No；

此阶段有节点宕机，恢复后终止事务处理；
预提交阶段Prepared to commit Phase

Coordinator收到所有Participant阶段1回复同意后，发送Prepared to Commit请求，Participant收到Prepared请求后，写undo log(撤销日志)和redo log(重做日志)，然后锁定资源，执行事务，但并不提交，回复success给Coordinator。

此阶段如果Coordinator在发送Prepared to commit前宕机，恢复后终止事务处理；如果发送了部分Prepared to commit请求后宕机，按照论文的描述有一个仲裁的过程；
提交阶段Commit(or completion) Phase

如果所有Participants都Prepared to Commit成功：Coordinator向所有的Participant发起提交指令；所有Participant提交之前未提交的事务，释放锁定资源，回复确认；Coordinator收到所有确认后，提交完成；

此阶段有节点宕机，恢复后继续事务的提交；

相对2PC，其实3PC是在最开始加入了一个询问阶段，大大降低了锁定资源的情况，询问通过后其实走的就是2PC的流程，只不过后面的两个阶段3PC都引入的超时处理逻辑，不会由于单点故障造成资源的锁定。

3PC是一个非阻塞协议，不会永久的锁定资源，能够在单点故障后继续达成一致。相对于2PC引入的一个缺点就是至少需要3RTTS才能完成提交操作，这会潜在的增加事务的延迟。

TCC(Try-Confirm-Cancel)

TCC(Try-Confirm-Cancel)的概念，最早是由Pat Helland于2007年发表的一篇名为<Life beyond Distributed Transactions:an Apostate’s Opinion>的论文提出。在该论文中，TCC还是以Tentative-Confirmation-Cancellation作为名称；参考文章的介绍：TCC是 [Atomikos]提出的概念。

引用：国内最早关于TCC的报道，应该是InfoQ上对阿里程立博士的一篇采访。经过程博士的这一次传道之后，TCC在国内逐渐被大家广为了解并接受。相应的实现方案和开源框架也先后被发布出来，ByteTCC就是其中之一。

TCC协议的实现如下：

Try：尝试执行，主要是进行资源的检测和资源的预留;
Confirm：确认执行，不作任何业务检查，只使用Try阶段预留的资源，Confirm操作满足幂等性，Confirm失败后需要进行重试；
Cancel：取消执行，释放Try阶段预留的资源，和Confirm一样，Cancel操作也必须满足幂等性，失败后需要重试；

TCC协议本质上和2PC是相似的，Try对应于2PC的阶段1，Confirm-Cancel对应于2PC阶段2的提交和回滚操作。其实TCC和3PC的目的都是为了解决2PC的缺点，TCC有以下的优化：

协调者单点：由主业务方发起并完成这个业务活动。业务活动管理器也变成多点，引入集群。
同步阻塞：引入超时，超时后进行补偿，并且不会锁定整个资源，将资源转换为业务逻辑形式，粒度变小。
数据一致性：有了补偿机制之后，由业务活动管理器控制一致性

TCC事务机制相对于传统事务机制（X/Open XA Two-Phase-Commit），其特征在于它不依赖资源管理器(RM)对XA的支持，而是通过对（由业务系统提供的）业务逻辑的调度来实现分布式事务。

本地消息表

本地消息表也是一种分布式事务最终一致性的一种解决方案，最初是由ebay 2008年的发表于ACM Queue期刊的一篇论文；

这里以支付服务和会计服务为例简要的介绍一下本地消息表的一致性方案：用户在支付服务完成后，会调用会计服务的接口生成一条原始的会计凭证到数据库中，这个时候就会存在分布式事务的情况。

这时候就引入本地消息表和MQ来进行消息的可靠投递，以及定时任务对丢失的消息进行重复投递，如下图(引用出处)：

支付服务中引入一张消息表来记录支付消息，即用户支付成功后同时往这张消息表插入一条支付成功的消息，状态为“发送中”。注意支付逻辑和插入消息表的代码要包裹在一个事务里面，这里保证了本地事务的强一致性。要么同时成功，要么同时失败。
此时再向mq的PAY_QUEUE队列中投递一条支付消息，这条支付消息的内容跟保存在支付库消息表的消息内容一致。
mq接收到消息后，此时会计服务也监听到这条消息了，此时会计服务处理消费逻辑即开始生成会计凭证。
会计凭证生成后，再反向向mq投递一条消费成功的消息到ACC_QUEUE队列
同时支付服务又来监听这个会计服务消费成功的消息，当支付服务监听到这个消费成功的消息后，此时再将本地消息表的消息状态改为“已发送”。
经过前面5步后，整个业务就已经完成了。

本地信息表的实现成本相对较低，但是与业务耦合在一起，很难通用，且本地信息表基于数据库来做的，有磁盘IO，有性能瓶颈。

Gossip协议

Gossip协议是用来在计算机点对点间进行通信的一个协议，他的实现原理类型于流行病毒传播方式，因此也称之epidemic protocol病毒传播协议。Gossip在分布式系统中广泛使用，可以利用Gossip协议来确保将数据传播给所有节点，它是一个去中心化的协议，这是和上面介绍的一致性协议最大的区别。

在 Gossip 协议中，两个节点之间有三种通信方式：

push：节点 A 将数据 (key,value,version) 及对应的版本号推送给 B 节点，B 节点更新 A 中比自己新的数据；
pull：A 仅将数据 key, version 推送给 B，B 将本地比 A 新的数据（Key, value, version）推送给 A，A 更新本地；
push-pull：在pull的基础上，A再将本地比 B 新的数据推送给 B，B 则更新本地；

介绍Gossip协议类型前，先介绍Gossip采用SIR病毒模型将节点目标分为三类：

S: susceptible(易感染者)：即未感染者，在Gossip中表示节点没有更新；
I:infected(感染者)：表示节点已经更新，且在进行传播扩散；
R:removed(康复者)：表示节点已经更新，但已经不在进行传播扩散；

Gossip协议的类型有两种

SI model：只有S和I两种节点，一个节点会把所有的数据都跟其他节点共享，以便消除节点之间数据的任何不一致，它可以保证最终、完全的一致。
SIR model：节点间只会发送新的update，一段时间后该update会被标记removed不再进行传播扩散，所以SIR模式下，消息可以发送得更频繁，系统开销小，但是系统有一定的概率会不一致。

Gossip的优点就是去中心化，扩展性好，容错性，一致性收敛，确定是消息冗余，消息的延迟。

Paxos协议

Paxos协议是图灵奖获得者Lamport在1990年提出的基于消息传递的共识算法。Paxos的提出是为了在分布式系统中对某个值达成一致。Paxos算法中有三种角色(可以有重叠)：

Proposers：提议者，负责提出提案(proposal)，提案(proposal)的内容为【N，V】，N表示提案编号，V表示提议value；
Acceptors：对Proposer提出的提案进行接受或者决绝；
Learners：学习被接受(chosen)的提案；

Paxos算法的流程分为两个阶段：

Prepare阶段：
- Proposer选择一个提案(proposal)，提案编号为N，然后向半数以上的Acceptor发送提案编号N的Prepare请求；
- 如果一个Acceptor收到一个编号N的Prepare请求，且N大于该Acceptor已经响应过的所有Prepare请求的提案编号，那么它会将它已经接受过的编号最大的提案（如果有的话）作为响应反馈给Proposer，同时该Acceptor承诺不再接受任何编号小于N的提案，表示接受该提案，否则为拒绝该提案；
Accept阶段：
- 如果Proposer收到半数以上Acceptor对其发出的编号为N的Prepare请求的响应。那么他就会发送提案【N，V】的Accept请求给半数以上的Acceptor，V就是Preapre极端收到的响应中编号最大的提案的value，如果响应中不包含任何提案，那么V就由Proposer自己决定。
- 如果Acceptor收到一个针对编号为N的提案的Accept请求，只要该Acceptor没有对编号大于N的Prepare请求做出过响应，它就接受该提案。

最后Acceptor在接受一个提案后，就会将该提案通知给所有Learner，进行同步；

为了解决Paxos算法活锁的问题，Multi-Paxos提出了所有的Proposer需要选择一个主Proposer也称之为Leader，由Leader来进行提案的发起；ZooKeeper使用的Zab也是Multi-Paxos的变形。

Raft协议

Raft协议是Diego和John在2013年发表的论文，Raft协议和Paxos的结果和效率是一致的，但Raft的目标是让共识协议更容易理解，就和它的论文标题一下。Raft相对于Paxos协议，是一个工程完备的协议，细化了实现的具体细节，所以在业界得到了更多的青睐；

Raft协议中同样有三种角色，也是同样可以重叠和转变：

Leader：负责处理所有客户端请求，当接收到写入请求时，本地处理后再同步至其他节点。
Follower：不发送任何请求，只是响应来自Leader和Candidate的请求。也不会处理Client的请求，而是将请求重定向到Leader节点进行处理
Candidate：当Follower节点长时间没有收到Leader节点发送的心跳时，则该节点的选举计时器会过期，同时自身状态会转变为Candidate，并发起新一轮的选举。

Raft协议将整个共识的过程分解成三个相对独立的子问题：Leader选举，Log复制，安全性；

Leader选举：Raft采用心跳机制来触发leader选举流程；
- 当集群启动时，所有节点初始化为Follower；
- 处于Follower状态的结点，如果一直能够收到leader或者Candidate，则维持在此状态，否者在一段超时时间(选举计时器超时)后，则认为Leader挂了，节点就会转换为Candidate状态，重置选举计时器并发起新一轮选举。
- 选举时发起选举的节点首先会将选票投给自己，并会向集群中其他节点发送选举请求。其它节点任期较小且都是Follower状态，所以节点选举请求后，就会将选票投出，重置选举计时器，并递增自身Term值。这样因为之前的Cadidate节点得到了集群中超过半数的票数，所以就变成了Leader节点。如果发送同时出现多个Cadidate节点可能导致无法获得半数以上的票数，则选举失败，等待重新发起选举；

Log复制：对于Client的请求，都是由Leader节点进行负责；
- 对于Client的更新操作，Leader首先会本地在Log中写入一条记录，然后将此条信息发送给集群中其他Follower节点；
- 当Follower节点记录收到消息后，会向Leader节点返回相应的响应消息；
- 当Leader收到半数以上Follower节点响应后，Leader将Client的更新请求进行提交，并返回执行给过给Client；然后通知所有Follower进行提交；针对未响应的Follower节点，在返回Client请求后，Leader会不定时的进行更新操作直到所有Follower都同步该Log的更新；