1. Paxos算法
Paxos算法是 Leslie Lamport（莱斯利·兰伯特）在 1990 年提出的一种分布式系统共识算法。也是第一个被证明完备的共识算法（前提是不存在恶意节点）。
1.1 简介
Paxos算法是第一个被证明完备的分布式系统共识算法。共识算法的作用是让分布式系统中的多个节点之间对某个提案（Proposal）达成一致的看法。提案的含义在分布式系统中十分宽泛，像哪一个节点是Leader节点、多个事件发生的顺序等等都可以是一个提案。
当时提出的Paxos算法主要包括两个部分：
- Basic-Paxos算法：描述的是多节点之间如何就某个值（提案Value）达成共识。
- Multi-Paxos算法：描述的是执行多个Basic Paxos实例，就一系列值达成共识。Multi-Paxos说白了就是执行多次Basic Paxos ，核心还是Basic Paxos。
由于Paxos算法在国际上被公认的非常难以理解和实现，因此有人不断尝试简化这一算法，到了2013年 才诞生了一个比Paxos算法更易理解和实现的共识算法--Raft算法（下文提及）。更具体一点来说，Raft是Multi-Paxos的一个变种，其简化了Multi-Paxos的思想，变的更容易被理解以及工程实现。
针对没有恶意节点的情况，除了Raft算法之外，当前最常用的一些共识算法比如ZAB协议、Fast Paxos算法都是基于Paxos算法改进的。
在分布式系统中应对潜在恶意节点的攻击，区块链技术通常采用工作量证明（PoW，Proof-of-Work）和权益证明（PoS，Proof-of-Stake）等共识算法作为核心防御机制。以以太坊为例，这个全球第二大区块链平台在2022年完成了具有里程碑意义的共识机制转型——通过"合并"（The Merge）升级，其底层协议从能源消耗较高的工作量证明机制，正式切换为更节能环保的权益证明机制。这次技术跃迁不仅大幅降低了网络能耗，也为区块链的可扩展性提升开辟了新路径。
区块链系统使用的共识算法需要解决的核心问题是拜占庭将军问题，这和我们日常接触到的ZooKeeper、Ectd、Consul等分布式中间件不太一样。
1.2 Basic Paxos算法
Basic Paxos算法中存在3个重要角色：
1.提议者（Proposer）：也可以叫做协调者（coordinator），提议者负责接收客户端的请求并发起提案。提案信息通常包括提案编号（coodinator），提议者负责接收客户端的请求并发起提案。
2.接受者（Accepter）：也可以叫做投票员（voter），负责对提议者的提案进行投票，同时需要记住自己的投票历史；
3.学习者（Learner）：如果有超过半数接受者就某个提议达成了共识，那么学习者就需要接受这个提议，并就该提议做出运算，然后将运算结果返回给客户端。
为了减少实现该算法所需的节点数，一个节点可以身兼多个身份。并且，一个提案被选定，需要被半数以上的Accepter接受。这样的话，Basic Paxos算法还具备容错性，在少于一半的节点出现故障时，集群仍能够正常工作。
1.3 Multi Paxos 思想
Basic Paxos算法仅能够就单个值达成共识，为了能够对一系列的值达成共识，我们需要用到Multi Paxos思想。
Multi-Paxos只是一种思想，这种思想的核心就是通过多个Basic Paxos实例就一系列值达成共识。也就是说，Basic Paxos是Multi-Paxos思想的核心，Multi-Paxos就是多执行几次Basic Paxos。
由于兰伯特提到的 Multi-Paxos 思想缺少代码实现的必要细节(比如怎么选举领导者)，所以在理解和实现上比较困难。
不过，也不需要担心，我们并不需要自己实现基于 Multi-Paxos 思想的共识算法，业界已经有了比较出名的实现。像 Raft 算法就是 Multi-Paxos 的一个变种，其简化了 Multi-Paxos 的思想，变得更容易被理解以及工程实现，实际项目中可以优先考虑 Raft 算法。
2. Raft算法
2.1 简介
当今的数据中心和应用程序在高度动态的环境中运行，为了应对高度动态的环境，它们通过额外的服务器进行横向扩展，并且根据需求进行扩展和收缩。同时，服务器和网络故障也很常见。
因此，系统必须在正常操作期间处理服务器的上下线，它们必须对变故作出反应并在几秒钟内自适应，对客户来说，明显的中断通常是不可接受的。
幸运的是，分布式共识可以帮助应对这些挑战。
2.1.1 拜占庭将军
在介绍共识算法之前，先介绍一个简化版拜占庭将军的例子来帮助理解共识算法。
假设多位拜占庭将军中没有叛军，信使的信息可靠但有可能被暗杀的情况下，将军们如何达成是否要进攻的一致性决定？
解决方案大致可以理解成：在所有将军中选出一个大将军，用来做出所有决定。
举例如下：假如现在一共有 3 个将军 A，B 和 C，每个将军都有一个随机时间的倒计时器，例如A倒计时最先结束，这个将军就把自己当成大将军候选人，然后派信使传递选举投票的信息给将军 B 和 C，如果将军 B 和 C 还没有把自己当作候选人（自己的倒计时还没有结束），并且没有把选举票投给其他人，它们就会把票投给将军 A，信使回到将军 A 时，将军 A 知道自己收到了足够的票数，成为大将军。在有了大将军之后，是否需要进攻就由大将军 A 决定，然后再去派信使通知另外两个将军，自己已经成为了大将军。如果一段时间还没收到将军 B 和 C 的回复（信使可能会被暗杀），那就再重派一个信使，直到收到回复。
2.1.2 共识算法
共识是可容错系统中的一个基本问题：即使面对故障。服务器也要在共享状态上达成一致。
共识算法允许一组节点像一个整体一样工作，即使其中的一些节点出现故障也能够继续工作下去，其正确性主要是源于复制状态机的特性：一组server的状态机计算相同状态的副本，即使有一部分的server宕机了，它们也能够正常运行。
上图是复制状态机架构
一般通过使用复制日志来实现复制状态机。每个server存储着一份包括命令序列的日志文件，状态机会按照顺序执行这些命令，因为每个日志包含相同的命令，并且顺序也相同，所以每个状态机处理相同的命令序列。由于状态机是确定性的，所以处理相同的状态，得到相同的输出。
因此共识算法的工作就是保持复制日志的一致性。服务器上的共识模块从客户端接受命令并将它们添加到日志中。它与服务器上的共识模块通信，以确保即使某些服务器发生故障。每个日志最终包含相同顺序请求。一旦命令被正确的复制，它们就被称为已提交。每个服务器的状态机按照日志顺序处理已提交的命令，并将输出返回给客户端，因此这些服务器形成了一个单一的高度可靠的状态机。
适用于于实际系统的共识算法通常具有以下特性：
- 安全：确保在非拜占庭条件下的安全性，包括网络延迟、分区、包丢失、复制和重新排序。
- 高可用：只要大多数服务器都是可操作的，并且可以互相通信，也可以与客户端进行通信那么这些服务器就可以看做完全功能可用的。因此一个典型的由五台服务器组成的集群可以容忍两台服务器端故障。假设服务器因停止而发生故障；它们稍后可能会从稳定存储上的状态中恢复并重新加入集群。
- 一致性不依赖时序。错误的时钟和极端的消息延迟，在最坏的情况下也只会造成可用性问题，而不会产生一致性问题。
- 在集群中大部分服务器响应，命令就可以完成，不会被少数运行缓慢地服务器来影响整体系统性能。
2.2 基础
2.2.1 节点类型
一个Raft集群包括若干服务器，以典型的5服务器集群举例。在任意的时间，每个服务器一定会处于以下三个状态中的某一个：
- Leader：负责发起心跳，响应客户端，创建日志，同步日志。
- Candidate：Leader选举过程中的临时角色，由Follower转化而来，发起投票参与竞选。
- Follower：接受Leader的心跳和日志同步数据，投票给Candidate。
在正常情况下，只有一个服务器是Leader，剩下的服务器是Follower。Follower是被动的，它们不会发送任何请求，只是相应来自Leader和Candidate的请求。
2.2.2 任期
raft算法将时间划分为任意长度的任期（term），任期将用连续的数字表示，看做当前term号 。
每一个任期的开始都是一次选举，在选举开始时，一个或多个Candidate会尝试成为Leader。如果一个Candidate赢得了选举，它就会在该任期内担任Leader。如果没有选出Leader，将会开启另一个任期，并立刻开始下一次选举。raft算法保证在给定的一个任期最少要有一个Leader。
每个节点都会存储当前的term号，当服务器之间进行通讯的时候会交换当前的term号；如果有服务器发现自己的rerm号比别人小，那么它会更新到较大的term值。如果一个Candidate或者Leader发现自己过期了，它会立即退化成Follower。如果一台服务器收到的请求的term号是过期的，那么它会拒绝此次请求。
2.2.3 日志
- entry：每一个事件成为entry，只有Leader能够创建entry 。entry的内容为<term,index,cmd>其中cmd是可以应用到状态机的操作。
- log：由entry组成的数组，每一个entry都有一个自己在log中的index。只有Leader才可以改变其他节点的Log。entry总是先被Leader添加到自己的数组中，然后再发起共识请求，获得同意后才会被Leader提交给状态机。Follower只能从Leader获取新日志和当前的commitIndex，然后把对应的entry应用到自己的状态机中。
2.3 领导人选举
raft使用心跳机制来触发leader的选举。
如果一台服务器能够收到来自Leader或者Candidate的有效信息，那么它会一直保持为Follower状态，并且刷新自己的electionElapsed，重新计时。
Leader会向所有的follower周期性的发送心跳来保证自己的Leader地位。如果一个Follower在一个周期内没有收到心跳信息，就叫做选举超时，然后它就会认为此时没有可用的Leader，并且开始进行一次选举选出新的Leader。
为了开始新的选举，Follower会自增自己的term号并且转换状态为Candidate。然后他会向所有节点发起RequestVoteRPC请求，Candidate的状态会持续到以下情况发生：
- 赢得选举
- 其他节点赢得选举
- 一轮选举结束，无人胜出
赢得选举的条件是：一个Candidate在一个任期内收到了来自集群内的多数选票（超过一半），就可以成为Leader。
在Candidate等待选票的时候，它可能收到其他节点 声明自己是Leader的心跳，此时有两种情况：
- 该Leader的term号大于等于自己的term号，说明对方已经成为Leader，则自己退化为Follower。
- 该Leader的term号小于自己的term号，那么会拒绝请求并让该节点更新term。
由于可能同一时刻出现多个Candidate，导致没有Candidate获得大多数选票，如果没有其他手段来重新分配选票的话，那么可能会无限重复下去。
raft使用了随机的选举超时时间来避免上述情况。每一个Candidate在发起选举后，都会随机化一个新的选举超时时间，这种机制使得各个服务器能够分散开来，在大多数情况下只有一个服务器会率先超时；它会在其他服务器超时之前赢得选举。
2.4 日志复制
一旦选出了Leader，它就开始接受客户端的请求。每一个客户端的请求都包含一条需要被复制状态机（Replicated State Machine）执行的命令。
Leader 收到客户端请求后，会生成一个 entry，包含<index,term,cmd>，再将这个 entry 添加到自己的日志末尾后，向所有的节点广播该 entry，要求其他服务器复制这条 entry。
如果 Follower 接受该 entry，则会将 entry 添加到自己的日志后面，同时返回给 Leader 同意。
如果 Leader 收到了多数的成功响应，Leader 会将这个 entry 应用到自己的状态机中，之后可以称这个 entry 是 committed 的，并且向客户端返回执行结果。
raft 保证以下两个性质：
- 在两个日志里，有两个 entry 拥有相同的 index 和 term，那么它们一定有相同的 cmd
- 在两个日志里，有两个 entry 拥有相同的 index 和 term，那么它们前面的 entry 也一定相同
通过“仅有 Leader 可以生成 entry”来保证第一个性质，第二个性质需要一致性检查来进行保证。
一般情况下，Leader 和 Follower 的日志保持一致，然后，Leader 的崩溃会导致日志不一样，这样一致性检查会产生失败。Leader 通过强制 Follower 复制自己的日志来处理日志的不一致。这就意味着，在 Follower 上的冲突日志会被领导者的日志覆盖。
Leader 给每一个Follower 维护了一个 nextIndex，它表示 Leader 将要发送给该追随者的下一条日志条目的索引。当一个 Leader 开始掌权时，它会将 nextIndex 初始化为它的最新的日志条目索引数+1。如果一个 Follower 的日志和 Leader 的不一致，AppendEntries 一致性检查会在下一次 AppendEntries RPC 时返回失败。在失败之后，Leader 会将 nextIndex 递减然后重试 AppendEntries RPC。最终 nextIndex 会达到一个 Leader 和 Follower 日志一致的地方。这时，AppendEntries 会返回成功，Follower 中冲突的日志条目都被移除了，并且添加所缺少的上了 Leader 的日志条目。一旦 AppendEntries 返回成功，Follower 和 Leader 的日志就一致了，这样的状态会保持到该任期结束。
2.5 安全性
2.5.1 选举限制
Leader 需要保证自己存储全部已经提交的日志条目。这样才可以使日志条目只有一个流向：从 Leader 流向 Follower，Leader 永远不会覆盖已经存在的日志条目。
每个 Candidate 发送 RequestVoteRPC 时，都会带上最后一个 entry 的信息。所有节点收到投票信息时，会对该 entry 进行比较，如果发现自己的更新，则拒绝投票给该 Candidate。
2.5.2 节点崩溃
如果 Leader 崩溃，集群中的节点在 electionTimeout 时间内没有收到 Leader 的心跳信息就会触发新一轮的选主，在选主期间整个集群对外是不可用的。
如果 Follower 和 Candidate 崩溃，处理方式会简单很多。之后发送给它的 RequestVoteRPC 和 AppendEntriesRPC 会失败。由于 raft 的所有请求都是幂等的，所以失败的话会无限的重试。如果崩溃恢复后，就可以收到新的请求，然后选择追加或者拒绝 entry。
在编程中一个幂等操作的特点是其任意多次执行所产生的影响均与一次执行的影响相同。
2.5.3 时间性与可用性
raft 的要求之一就是安全性不依赖于时间：系统不能仅仅因为一些事件发生的比预想的快一些或者慢一些就产生错误。为了保证上述要求，最好能满足以下的时间条件：
broadcastTime << electionTimeout << MTBF
broadcastTime：向其他节点并发发送消息的平均响应时间；electionTimeout：选举超时时间；MTBF(mean time between failures)：单台机器的平均健康时间
broadcastTime应该比electionTimeout小一个数量级，为的是使Leader能够持续发送心跳信息（heartbeat）来阻止Follower开始选举；
electionTimeout也要比MTBF小几个数量级，为的是使得系统稳定运行。当Leader崩溃时，大约会在整个electionTimeout的时间内不可用；我们希望这种情况仅占全部时间的很小一部分。
由于broadcastTime和MTBF是由系统决定的属性，因此需要决定electionTimeout的时间。
一般来说，broadcastTime 一般为 0.5～20ms，electionTimeout 可以设置为 10～500ms，MTBF 一般为一两个月。