分布式事务乃分布式系统之基石，从单机程序到分布式系统，导致的最主要的问题还是在于分布式一致性问题，一致性分为强一致性和最终一致性，说到这两个概念，就需要提到CAP理论问题，CAP就是从一致性，可用，已经分区三个角度考量分布式方案的。按照这个理论，所有系统不可能同时具备CAP三个特性；对于强一致性来说，具备的是CA；对于最终一致性来说，一般是具备CP两个特性；强一致性的方案有2PC，3PC等，但是这些一般停留在理论阶段，真正使用的很少，因为缺陷实在是太多了。实战中，其实最多考虑的还是最终一致性事务方案，比如TCC，SOGA，消息队列等方案。
除了以上解决方案外，还有两个近些年来被广泛应用的重量级分布式解决方案不得不提，那就是Paxos和Raft。Paxos算法是莱斯利·兰伯特（Leslie Lamport）1990年提出的一种基于消息传递的一致性算法。莱斯利·兰伯特是近期图灵奖得主，79岁高龄的兰伯特对分布式系统领域的贡献是有目共睹的。他对分布式和并发系统的理论及实践，做出了重大贡献，尤其是他提出了诸多的概念，例如 ‘因果关系和逻辑时钟’、‘安全性和活性’、‘复制状态机’，还有‘顺序一致性’。
Paxos
谈到Paxos，就不得不提这篇“兼职议会” 的论文。此论文晦涩难懂，以至于这篇论文在TOCS 的编辑要求他进行整改，兰伯特把稿子投给 TOCS的编辑的回应是：“嗯，有点意思。当然，不是啥重要玩意。但值得发表，不过你得把希腊的那些内容去掉。”兰伯特有点不爽，怪罪编辑没有幽默感。这是可以理解的，认真的 “尬舞” 没有逗笑观众，没有迎来掌声，却引来了批评，换谁都要暴跳如雷。兰伯特就没有搭理编辑，论文也就没有发表。话说TOCS的编辑要求兰伯特做一点修改，加上些 TLA 证明也是无可厚非的，由于兰伯特固执的性格导致论文在1998年兰伯特做出让步进行修改才正式面世。其实在论文发表之前早已闻名遐迩，丝毫不掩盖这边论文的气质和其正确性。
后来，基于 Paxos 的研究越来越多，Lampson 就演绎了多种变形：AP：Abstract Paxos；BP：Byzantine Paxos；CP：Classic Paxos；DP：Disk Paxos。兰伯特自己也写了 Simple Paxos 和 Cheap Paxos。 工业界开始应用 Paxos，Google 的 Chubby，还有开源的 Zookeeper 都应用了 Paxos。Chubby 的开发者 Mike Burrows 说：“世上只有一种一致性算法，那就是Paxos。” 另一位亚马逊工程师曾经说：“世上有两种方法构造分布式系统。一种，你用 Paxos 即可。
拜占庭将军问题
拜占庭位于如今的土耳其的伊斯坦布尔，是东罗马帝国的首都。由于当时拜占庭罗马帝国国土辽阔，为了达到防御目的，每个军队都分隔很远，将军与将军之间只能靠信差传消息。在战争的时候，拜占庭军队内所有将军和副官必须达成一致的共识，决定是否有赢的机会才去攻打敌人的阵营。但是，在军队内有可能存有叛徒和敌军的间谍，左右将军们的决定又扰乱整体军队的秩序。在进行共识时，结果并不代表大多数人的意见。这时候，在已知有成员谋反的情况下，其余忠诚的将军在不受叛徒的影响下如何达成一致的协议，拜占庭问题就此形成。
拜占庭将军问题是一个协议问题，拜占庭帝国军队的将军们必须全体一致的决定是否攻击某一支敌军。问题是这些将军在地理上是分隔开来的，并且将军中存在叛徒。叛徒可以任意行动以达到以下目标：欺骗某些将军采取进攻行动；促成一个不是所有将军都同意的决定，如当将军们不希望进攻时促成进攻行动；或者迷惑某些将军，使他们无法做出决定。如果叛徒达到了这些目的之一，则任何攻击行动的结果都是注定要失败的，只有完全达成一致的努力才能获得胜利。
Paxos算法概述
Paxos算法有三个角色,Proposer：议案发起者；Acceptor：决策者，可以批准议案；Learner：最终决策的学习者。Paxos算法要解决的是有多个不同的议案被提出时，如何就最终的结果达成一致的问题，要解决这个问题，必须允许一个Acceptor接受多个议案，后接受的议案可以覆盖掉之前接受的议案。Paxos要实现的目标的是，一次选举必须要选定一个议案（不能出现所有议案都被拒绝的情况）；一次选举必须只选定一个议案（不能出现两个议案有不同的值，却都被选定的情况）；
整个算法的大致过程为：
- 第一阶段：Prepare阶段。Proposer向Acceptors发出Prepare请求，Acceptors针对收到的Prepare请求进行Promise承诺。
- 第二阶段：Accept阶段。Proposer收到多数Acceptors承诺的Promise后，向Acceptors发出Propose请求，Acceptors针对收到的Propose请求进行Accept处理。
- 第三阶段：Learn阶段。Proposer在收到多数Acceptors的Accept之后，标志着本次Accept成功，决议形成，将形成的决议发送给所有Learners。
Paxos算法流程中的每条消息描述如下：
- Prepare: Proposer生成全局唯一且递增的Proposal ID (可使用时间戳加Server ID)，向所有Acceptors发送Prepare请求，这里无需携带提案内容，只携带Proposal ID即可。
- Promise: Acceptors收到Prepare请求后，做出“两个承诺，一个应答”。
两个承诺：
- 不再接受Proposal ID小于等于（注意：这里是<= ）当前请求的Prepare请求。
- 不再接受Proposal ID小于（注意：这里是< ）当前请求的Propose请求。
一个应答： 不违背以前作出的承诺下，回复已经Accept过的提案中Proposal ID最大的那个提案的Value和Proposal ID，没有则返回空值。
- Propose: Proposer 收到多数Acceptors的Promise应答后，从应答中选择Proposal ID最大的提案的Value，作为本次要发起的提案。如果所有应答的提案Value均为空值，则可以自己随意决定提案Value。然后携带当前Proposal ID，向所有Acceptors发送Propose请求。
- Accept: Acceptor收到Propose请求后，在不违背自己之前作出的承诺下，接受并持久化当前Proposal ID和提案Value。
- Learn: Proposer收到多数Acceptors的Accept后，决议形成，将形成的决议发送给所有Learners。
Raft
在Raft协议诞生之前，Paxos几乎成了一致性协议的代名词。但是对于大多数人来说，Paxos算法太难以理解了，而且难以实现。因此斯坦福大学的两位教授Diego Ongaro和John Ousterhout决定设计一种更容易理解的一致性算法，最终在论文”In search of an Understandable Consensus Algorithm”中提出了Raft算法
复制状态机(replicated state machine)
Raft协议可以使得一个集群的服务器组成复制状态机，在详细了解Raft算法之前，我们先来了解一下什么是复制状态机。一个分布式的复制状态机系统由多个复制单元组成，每个复制单元均是一个状态机，它的状态保存在一组状态变量中，状态机的变量只能通过外部命令来改变。简单理解的话，可以想象成是一组服务器，每个服务器是一个状态机，服务器的运行状态只能通过一行行的命令来改变。每一个状态机存储一个包含一系列指令的日志，严格按照顺序逐条执行日志中的指令，如果所有的状态机都能按照相同的日志执行指令，那么它们最终将达到相同的状态。因此，在复制状态机模型下，只要保证了操作日志的一致性，我们就能保证该分布式系统状态的一致性。
Raft一致性算法
Raft有三种角色：leader、candidate、follower，正常运行的情况下，会有一个leader，其他全为follower，follower只会响应leader和candidate的请求，而客户端的请求则全部由leader处理，即使有客户端请求了一个follower也会将请求重定向到leader。candidate代表候选人，出现在选举leader阶段，选举成功后candidate将会成为新的leader。
集群刚启动时，所有节点都是follower，之后在time out信号的驱使下，follower会转变成candidate去拉取选票，获得大多数选票后就会成为leader，这时候如果其他候选人发现了新的leader已经诞生，就会自动转变为follower；而如果另一个time out信号发出时，还没有选举出leader，将会重新开始一次新的选举。可见，time out信号是促使角色转换得关键因素，类似于操作系统中得中断信号。
在Raft协议中，将时间分成了一些任意长度的时间片，称为term，term使用连续递增的编号的进行识别
term也起到了系统中逻辑时钟的作用，每一个server都存储了当前term编号，在server之间进行交流的时候就会带有该编号，如果一个server的编号小于另一个的，那么它会将自己的编号更新为较大的那一个；如果leader或者candidate发现自己的编号不是最新的了，就会自动转变为follower；如果接收到的请求的term编号小于自己的当前term将会拒绝执行。
server之间的交流是通过RPC进行的。只需要实现两种RPC就能构建一个基本的Raft集群：
- RequestVote RPC：它由选举过程中的candidate发起，用于拉取选票
- AppendEntries RPC：它由leader发起，用于复制日志或者发送心跳信号。
leader选举过程
Raft通过心跳机制发起leader选举。节点都是从follower状态开始的，如果收到了来自leader或candidate的RPC，那它就保持follower状态，避免争抢成为candidate。Leader会发送空的AppendEntries RPC作为心跳信号来确立自己的地位，如果follower一段时间(election timeout)没有收到心跳，它就会认为leader已经挂了，发起新的一轮选举。
选举发起后，一个follower会增加自己的当前term编号并转变为candidate。它会首先投自己一票，然后向其他所有节点并行发起RequestVote RPC，之后candidate状态将可能发生如下三种变化:
赢得选举,称为leader: 如果它在一个term内收到了大多数的选票，将会在接下的剩余term时间内称为leader，然后就可以通过发送心跳确立自己的地位。(每一个server在一个term内只能投一张选票，并且按照先到先得的原则投出) 其他server称为leader：在等待投票时，可能会收到其他server发出AppendEntries RPC心跳信号，说明其他leader已经产生了。这时通过比较自己的term编号和RPC过来的term编号，如果比对方大，说明leader的term过期了，就会拒绝该RPC,并继续保持候选人身份; 如果对方编号不比自己小,则承认对方的地位,转为follower. 选票被瓜分,选举失败: 如果没有candidate获取大多数选票, 则没有leader产生, candidate们等待超时后发起另一轮选举. 为了防止下一次选票还被瓜分,必须采取一些额外的措施, raft采用随机election timeout的机制防止选票被持续瓜分.通过将timeout随机设为一段区间上的某个值, 因此很大概率会有某个candidate率先超时然后赢得大部分选票.
日志复制过程
一旦leader被选举成功，就可以对客户端提供服务了。客户端提交每一条命令都会被按顺序记录到leader的日志中，每一条命令都包含term编号和顺序索引，然后向其他节点并行发送AppendEntries RPC用以复制命令(如果命令丢失会不断重发)，当复制成功也就是大多数节点成功复制后，leader就会提交命令，即执行该命令并且将执行结果返回客户端，raft保证已经提交的命令最终也会被其他节点成功执行。leader会保存有当前已经提交的最高日志编号。顺序性确保了相同日志索引处的命令是相同的，而且之前的命令也是相同的。当发送AppendEntries RPC时，会包含leader上一条刚处理过的命令，接收节点如果发现上一条命令不匹配，就会拒绝执行。
在这个过程中可能会出现一种特殊故障：如果leader崩溃了，它所记录的日志没有完全被复制，会造成日志不一致的情况，follower相比于当前的leader可能会丢失几条日志，也可能会额外多出几条日志，这种情况可能会持续几个term。
-
异常之leader提交之前崩溃 在Raft中，leader通过强制follower复制自己的日志来解决上述日志不一致的情形，那么冲突的日志将会被重写。为了让日志一致，先找到最新的一致的那条日志，然后把follower之后的日志全部删除，leader再把自己在那之后的日志一股脑推送给follower，这样就实现了一致。
-
异常之leader提交时宕机 Raft通过投票过程确保只有拥有全部已提交日志的candidate能成为leader。由于candidate为了拉选票需要通过RequestVote RPC联系其他节点，而之前提交的命令至少会存在于其中某一个节点上,因此只要candidate的日志至少和其他大部分节点的一样新就可以了, follower如果收到了不如自己新的candidate的RPC,就会将其丢弃.还可能会出现另外一个问题, 如果命令已经被复制到了大部分节点上,但是还没来的及提交就崩溃了,这样后来的leader应该完成之前term未完成的提交. Raft通过让leader统计当前term内还未提交的命令已经被复制的数量是否半数以上, 然后进行提交.
Ref
-
https://baike.baidu.com/item/%E6%8B%9C%E5%8D%A0%E5%BA%AD%E5%B0%86%E5%86%9B%E9%97%AE%E9%A2%98/265656?fr=aladdin
-
https://www.jianshu.com/p/729d511765f0
-
https://zhuanlan.zhihu.com/p/31780743
-
https://zhuanlan.zhihu.com/p/91288179
