简介
共识协议的技术变迁 – 既要“高”容错，又要“易”定序，还要“好”理解
- 共识协议面向有状态分布式系统的数据一致性与服务容错性这两大难题提供了近乎完美的解决方案.
- 分布式系统最朴实的目标是把一堆普通机器的计算/存储等能力整合到一起，然后整体上能够像一台超级机器一样对外提供可扩展的读写服务，设计原则上要实现即使其中的部分机器发生故障，系统整体服务不受影响。对于有状态的分布式系统而言，实现上述容错性目标的有效手段绕不开大名鼎鼎的复制状态机。。该模型的原理是为一个服务器集合里的每台服务器都维护着相同机制的确定有限状态机（DFSM，Determinate Finite State Machine），如果能够保障每个状态机输入的是完全一致的命令序列，那么这个集合中的每个状态机最终都可以以相同状态对外提供服务，同时也具备了容忍部分状态机故障的能力。显然，在复制状态机模型中，如何保证状态机之间数据一致的问题转换成了如何保证各台机器上日志序列一致的问题，这个成为了复制状态机模型最核心的挑战，而这，也正是共识协议神圣的职责。PS： 分布式系统一致性 ==> 日志序列一致性
一致性和共识算法
分布式共识问题和复制状态机
周志明：系统高可用和高可靠之间的矛盾，是由于增加机器数量反而降低了可用性带来的（节点可能会挂掉）。为缓解这个矛盾，在分布式系统里主流的数据复制方法，是以操作转移（Operation Transfer）为基础的。我们想要改变数据的状态，除了直接将目标状态赋予它之外，还有另一种常用的方法，就是通过某种操作，把源状态转换为目标状态。能够使用确定的操作，促使状态间产生确定的转移结果的计算模型，在计算机科学中被称为状态机（State Machine）。
- 状态机有一个特性：任何初始状态一样的状态机，如果执行的命令序列一样，那么最终达到的状态也一样。在这里我们可以这么理解这个特性，要让多台机器的最终状态一致，只要确保它们的初始状态和接收到的操作指令都是完全一致的就可以。无论这个操作指令是新增、修改、删除或者其他任何可能的程序行为，都可以理解为要将一连串的操作日志正确地广播给各个分布式节点。广播指令与指令执行期间，允许系统内部状态存在不一致的情况，也就是不要求所有节点的每一条指令都是同时开始、同步完成的，只要求在此期间的内部状态不能被外部观察到，且当操作指令序列执行完成的时候，所有节点的最终的状态是一致的。这种模型，就是状态机复制（State Machine Replication）。
- 在分布式环境下，考虑到网络分区现象是不可能消除的，而且可以不必去追求系统内所有节点在任何情况下的数据状态都一致，所以采用的是“少数服从多数”的原则。也就是说，一旦系统中超过半数的节点完成了状态的转换，就可以认为数据的变化已经被正确地存储在了系统当中。
根据这些讨论，我们需要设计出一种算法，能够让分布式系统内部可以暂时容忍存在不同的状态，但最终能够保证大多数节点的状态能够达成一致；同时，能够让分布式系统在外部看来，始终表现出整体一致的结果。这个让系统各节点不受局部的网络分区、机器崩溃、执行性能或者其他因素影响，能最终表现出整体一致的过程，就是各个节点的协商共识（Consensus）。这里需要注意的是，共识（Consensus）与一致性（Consistency）是有区别的：一致性指的是数据不同副本之间的差异，而共识是指达成一致性的方法与过程。
最难 paxos 和最易 raft ？日志 + 状态机 可以成为任何有意义的工程系统。比如 rocksdb，leveldb 等等 lsm 存储，它们数据先写 append log ，通过重放日志到达的系统状态一定是一致的。
《大数据经典论文解读》我们可以把一个数据库的写入操作，看成是一系列的顺序操作日志，也就是把对于数据库的写入，变成了一个状态机（而不是直接向一台或多态数据库发出cud指令）。而对于这个状态机的更新，我们需要保障高可用性和容错能力。这个需要我们对于某一个服务器上的日志追加写入，能够做到同步复制到多个服务器上。这样，在当前我们写入的节点挂掉的时候，我们的数据并不会丢失。为了避免单点故障，我们希望可以从多台服务器都能写入数据，但是又不能要求所有服务器都同步复制成功。前者，是为了确保某个服务器挂掉的时候，我们可以快速切换到另一台备用服务器；后者，是避免我们写入的时候，因为某一台服务器挂掉了就无法写入成功。所以，Paxos 这样的分布式共识算法的基本思路，就是这样几点：
- 日志追加写入的时候，只要能够半数的服务器完成同步复制就算写入成功了。
- 在有节点挂掉的时候，因为我们有多个服务器，所以系统可以自动切换恢复，而不是必须修复某一台服务器才能继续运行。
- 系统的数据需要有“一致性”，也就是不能因为网络延时、硬件故障，导致数据错乱，写入的数据读出来变了或者读不出来。
Paxos 算法的出发点，是为了达成分布式共识。状态机复制，只是分布式共识的一个特例，所以如果我们看原始的 Paxos 算法，去理解 Chubby 乃至 ZooKeeper 的实现，会有一个转化过程，不容易理解。而 Raft 算法，则是直接就从状态机复制的问题出发，算法和需要解决的问题直接对应。
关系
陈现麟：线性一致性是数据存储系统对外表现的一种形式，即好像只有一个数据副本，但是在实现数据一致性，实现容错的时候，我们需要共识算法的帮助。当然，这里要特别注意，我们通过共识算法，除了可以实现线性一致性，也可以实现顺序一致性等其他的数据一致性，共识算法是用来满足线性一致性的容错性的。同时，不使用共识算法，我们也可以实现数据的线性一致性，比如 ABD 和 SCD broadcast 之类的非共识算法，也可以实现线性一致性。
总而言之，我们通过共识算法，可以实现高可用的线性一致性，以及其他的一致性存储系统，在这种情况下，共识算法是手段，一致性是目的，先有共识算法，后有高可用的线性一致性系统。同时，不通过共识算法，我们也可以用其他的方法，来实现线性一致性等其他的一致性，在这种情况下，共识和一致性就没有关系了。不过，目前通过共识算法，来实现高可用的线性一致性模型，是一个最常见的选择。
事务和数据一致性是非常类似的，它们本质上都是期望它的一个完整操作是原子操作，研究的本质问题都是数据的一致性问题。只不过事务对一个完整操作的定义是，一个事务内，对一个或多个数据对象的一个或多个读写操作，它需要解决的是对多个数据对象操作的一致性问题；而数据一致性对一个完整操作的定义是，在多个数据副本上对一个数据对象的写操作，它要解决的是单个数据操作，复制到多个副本上的一致性问题。
两阶段提交
对于原子性来说，在分布式系统中，需要通过 2PC 或 3PC 之类的原子提交协议来实现。我们认为 2PC 或 3PC 之类的原子提交协议是共识协议。二阶段提交协议，不仅仅是协议，也是一种非常经典的思想。二阶段提交在达成提交操作共识的算法中应用广泛，比如 XA 协议、TCC、Paxos、Raft 等。在分布式系统中，为了让每个节点都能够感知到其他节点的情况，会进行多轮协商，“先搞清楚大家的想法再做决定”。所以不管是为了事务一致性，还是副本数据一致性，都有prepare 和 commit 的影子在。
- 如果没有 一个中心化的协调者 coordinator角色存在的话，每个节点都要与其它节点 进行两轮以上的通信。
- 如果有一个中心化的协调者coordinator角色，则由 coordinator 担任 “话事人”，每个participant 只需与coordinator 沟通即可（两轮以上）。网络中节点的数量和身份可以是提前确定好的，也或者干活前先推举一个“话事人”。
就好像连通n台服务器，要么两两都相连，要么大家都连在“交换机”上。协商的事情越复杂，人员构成越复杂，协商的次数、消息数量越多。协商2次 只是很理想的场景。
basic-paxos
每个Node 可以同时充当了两个角色：Proposer和Acceptor，在实现过程中， 两个角色在同一个进程里面。
| proposer | acceptor | 作用 | |
|---|---|---|---|
| prepare阶段 | proposer 生成全局唯一且自增的proposal id，广播propose 只广播proposal id即可，无需value |
Acceptor 收到 propose 后，做出“两个承诺，一个应答” 1. 不再应答 proposal id 小于等于当前请求的propose 2. 不再应答 proposal id 小于 当前请求的 accept 3. 若是符合应答条件，返回已经accept 过的提案中proposal id最大的那个 propose 的value 和 proposal id， 没有则返回空值 |
争取提议权，争取到了提议权才能在Accept阶段发起提议，否则需要重新争取 学习之前已经提议的值 |
| accept阶段 | 提案生成规则 1. 从acceptor 应答中选择proposalid 最大的value 作为本次的提案 2. 如果所有的应答的天value为空，则可以自己决定value |
在不违背“两个承诺”的情况下，持久化当前的proposal id和value | 使提议形成多数派，提议一旦形成多数派则决议达成，可以开始学习达成的决议 |
假设一个分布式系统有五个节点，分别是 S1、S2、S3、S4 和 S5；全部节点都同时扮演着提案节点和决策节点的角色。此时，有两个并发的请求希望将同一个值分别设定为 X（由 S1 作为提案节点提出）和 Y（由 S5 作为提案节点提出）；我们用 P 代表准备阶段、用 A 代表批准阶段，这时候可能发生下面四种情况。情况一：比如，S1 选定的提案 ID 是 3.1（全局唯一 ID 加上节点编号），先取得了多数派决策节点的 Promise 和 Accepted 应答；此时 S5 选定的提案 ID 是 4.5，发起 Prepare 请求，收到的多数派应答中至少会包含 1 个此前应答过 S1 的决策节点，假设是 S3。那么，S3 提供的 Promise 中，必将包含 S1 已设定好的值 X，S5 就必须无条件地用 X 代替 Y 作为自己提案的值。由此，整个系统对“取值为 X”这个事实达成了一致。PS： 这个图表示的特别好，其它情况就不一一列举了。这里的“设置值”不要类比成程序中变量赋值操作，应该类比成日志记录操作。
目前比较好的通俗解释，以贿选来描述 如何浅显易懂地解说 Paxos 的算法？ - GRAYLAMB的回答 - 知乎。想想tcp 握个手都很麻烦。
另一种表述
应用程序连接到任意一台服务器后提起状态修改请求（也可以是获得某个状态锁的请求），从图上看也就是服务器 1，会将这个请求发送给集群中其他服务器进行表决。如果某个服务器同时收到了另一个应用程序同样的修改请求，它可能会拒绝服务器 1 的表决，并且自己也发起一个同样的表决请求，那么其他服务器就会根据时间戳和服务器排序规则进行表决。表决结果会发送给其他所有服务器，最终发起表决的服务器也就是服务器 1，会根据收到的表决结果决定该修改请求是否可以执行，事实上，只有在收到多数表决同意的情况下才会决定执行。当有多个请求同时修改某个数据的情况下，服务器的表决机制保证只有一个请求会通过执行，从而保证了数据的一致性。
multi-paxos
共识协议的技术变迁 – 既要“高”容错，又要“易”定序，还要“好”理解Basic Paxos协议完美地解决了分布式系统中针对某一个值达成共识的问题，但是，实际的分布式系统显然不可能仅仅基于一个值的共识来运转。按照复制状态机模型的要求，我们是要解决日志序列一系列值的共识问题，直观地，我们可以反复地一轮一轮执行Basic Paxos，为日志序列中每一条日志达成共识，这个就是通常所谓的Multi Paxos。这里的所谓一轮一轮的轮号就是我们常说的Log ID，而前者提到的Proposal ID，则是我们常说的Epoch ID。对于采用Multi Paxos的有状态分布式系统而言，日志序列的Log ID必须是严格连续递增并且无空洞地应用到状态机，这个是Multi Paxos支持乱序提交所带来的约束限制，否则我们无法保证各状态机最终应用的命令序列是完全一致的。Proposal ID（Epoch ID）的全局唯一且单调递增的约束主要还是出于效率的考虑，Log ID的全局唯一且单调递增的约束则是出于正确性的考虑。
从Basic Paxos到Multi Paxos，这之间存在着巨大的鸿沟，实践中有着太多的挑战需要一一应对：LiveLock问题；CatchUp问题。
如果Basic Paxos中绝对公平意味着低效，那么不妨在Multi Paxos中引入选举并产生唯一Leader，只有当选为Leader才能够提议请求。这样的好处很明显，首先由唯一的Leader做Log ID分配，比较容易实现全局唯一且连续递增，解决了CatchUp问题； 其次，唯一的Leader提议不存在并发提议冲突问题，解决了LiveLock难题；。进一步地，本来PREPARE就是为了争夺提议权，现在既然只有Leader能够提议，就至少在Leader任职时间内就不必每个提议都要再走一遍PREPARE，这样大幅提升了形成决议的效率。
《分布式协议与算法实战》Multi-Paxos 是一种思想，不是算法，缺失实现算法的必须编程细节。而 Multi-Paxos 算法是一个统称，它是指基于 Multi-Paxos 思想，通过多个 Basic Paxos 实例实现一系列值的共识的算法（比如 Chubby 的 Multi-Paxos 实现、Raft 算法等）。Multi Paxos 对 Basic Paxos 的核心改进是，增加了“选主”的过程。
- 提案节点会通过定时轮询（心跳），确定当前网络中的所有节点里是否存在一个主提案节点；
- 一旦没有发现主节点存在，节点就会在心跳超时后使用 Basic Paxos 中定义的准备、批准的两轮网络交互过程，向所有其他节点广播自己希望竞选主节点的请求，希望整个分布式系统对“由我作为主节点”这件事情协商达成一致共识；
- 如果得到了决策节点中多数派的批准，便宣告竞选成功。
当选主完成之后，除非主节点失联会发起重新竞选，否则就只有主节点本身才能够提出提案。此时，无论哪个提案节点接收到客户端的操作请求，都会将请求转发给主节点来完成提案，而主节点提案的时候，也就无需再次经过准备过程，因为可以视作是经过选举时的那一次准备之后，后续的提案都是对相同提案 ID 的一连串的批准过程。
注意，二元组 (id, value) 已经变成了三元组 (id, i, value)，这是因为需要给主节点增加一个“任期编号”，这个编号必须是严格单调递增的，以应付主节点陷入网络分区后重新恢复，但另外一部分节点仍然有多数派，且已经完成了重新选主的情况，此时必须以任期编号大的主节点为准。
从整体来看，当节点有了选主机制的支持后，就可以进一步简化节点角色，不必区分提案节点、决策节点和记录节点了，可以统称为“节点”，节点只有主（Leader）和从（Follower）的区别。此时的协商共识的时序图如下：
在这个理解的基础上，我们换一个角度来重新思考“分布式系统中如何对某个值达成一致”这个问题，可以把它分为下面三个子问题来考虑：
- 如何选主（Leader Election），有paxos 就行， 当然会涉及到许多工程上的细节，比如心跳、随机超时、并行竞选等
- 如何把数据复制到各个节点上（Entity Replication），会涉及到网络分区、节点失联等
- 如何保证过程是安全的（Safety），选主的结果一定是有且只有唯一的一个主节点，不可能同时出现两个主节点；保证选主过程是一定可以在某个时刻能够结束的。
另一种表述：Basic Paxos达成一次决议至少需要两次网络来回，并发情况下可能需要更多，极端情况下甚至可能形成活锁，效率低下。Multi-Paxos选举一个Leader，提议由Leader发起，没有竞争，解决了活锁问题。提议都由Leader发起的情况下，Prepare阶段可以跳过，将两阶段变为一阶段，提高效率。Multi-Paxos并不假设唯一Leader，它允许多Leader并发提议，不影响安全性，极端情况下退化为Basic Paxos。Multi-Paxos与Basic Paxos的区别并不在于Multi（Basic Paxos也可以Multi），只是在同一Proposer连续提议时可以优化跳过Prepare直接进入Accept阶段。
Paxos 优化
当然啦，引入了Leader之后，Multi Paxos也是要处理好Leader切换前后的数据一致性问题，并且新的Leader如何填补日志空洞等难题也需要好好设计。问题还是不少。一直等到2007年，来自Google的工程师们通过《Paxos Made Live - An Engineering Perspective》一文，详细地介绍了他们在Chubby中落地Multi Paxos的最佳实践。这篇文章提到的Multi Paxos生产落地过程遇到的种种挑战：磁盘故障（disk corruption）；Master租约（master lease）；Master纪元（master epoch）/幽灵复现；共识组成员（group membership）；镜像快照（snapshots。
以 Chubby 的 Multi-Paxos 实现为例
- 主节点作为唯一提议者，这样就不存在多个提议者同时提交提案的情况，也就不存在提案冲突的情况
- 在 Chubby 中，主节点是通过执行 Basic Paxos 算法，进行投票选举产生的，并且在运行过程中，主节点会通过不断续租的方式来延长租期（Lease）。
- 在 Chubby 中实现了兰伯特提到的，“当领导者处于稳定状态时，省掉准备阶段，直接进入接受阶段”这个优化机制，减少非必须的协商步骤来提升性能。
- 在 Chubby 中，为了实现了强一致性，所有的读请求和写请求都由主节点来处理。也就是说，只要数据写入成功，之后所有的客户端读到的数据都是一致的。
减少 Paxos 算法的网络开销：对于原本是两阶段的 Prepare-Accept 的请求，我们可以在 Accept 请求里，带上下一次 Paxos 算法里的 Prepare 请求。因为所有的外部请求都会先到达 Master，然后由 Master 发起提案，所以这样的策略在实现上非常容易。而且因为请求都是从 Master 发起的，所以达成共识的过程中很少会有冲突，往往一个 Prepare-Accept 的过程，共识就已经达成了。这样，原先是两阶段的 Prepare-Accept，常常只要一个网络请求就已经完成了，我们的 Paxos 算法在大部分情况下，就变成一个一阶段就能完成的了。
Raft
Raft（一）：不会背叛的信使斯坦福大学在 2013 年发表的一篇论文《In Search of an Understandable Consensus Algorithm》。 中文版 Raft：寻找一种易于理解的一致性算法 论文大纲
- 复制状态机问题
- 讨论 Paxos 的优点和缺点
- 为了可理解性而采取的方法
- 阐述 Raft 一致性算法
- 评价 Raft 算法
论文提到，与 Paxos 不同，Raft的首要目标是可理解性，使用一些特别的技巧来提升它的可理解性
- Raft 算法则把问题拆分成了一个个独立的子问题（Raft 主要被分成了领导人选举，日志复制和安全三个模块），这些子问题都解决了，状态机复制的问题自然就解决了。我们只要能够理解和证明每一个子问题就够了，这个对于问题分而治之的办法，降低了理解问题的复杂度。首先是让系统里始终有一个 Leader，所有的数据写入，都是发送到 Leader。一方面，Leader 会在本地写入，另一方面，Leader 需要把对应的数据写入复制到其他的服务器上。这样，问题就变简单了，我们只需要确保两点，第一个是系统里始终有 Leader 可用；第二个，是基于 Leader 向其他节点复制数据，始终能确保一致性就好了。
- 因为 Leader 所在的服务器可能会挂掉，那么挂掉之后，我们需要尽快确认一个新 Leader，所以我们就需要解决第一个子问题，就是 Leader 选举问题。
- 我们需要保障分布式共识，所以 Leader 需要把日志复制到其他节点上，并且确保所有节点的日志始终是一致的。这个，就带来了第二个问题，也就是日志复制问题。
- 同时，在 Leader 挂掉，切换新 Leader 之后，我们会遇到一个挑战，新的 Leader 可能没有同步到最新的日志写入。而这可能会导致，新的 Leader 会尝试覆盖之前 Leader 已经写入的数据。这个问题就是我们需要解决的第三个问题，也就是“安全性”问题。
- Raft 算法加强了系统里的限制，使得问题在很多状态下被简化了。比如，Raft 算法是有一个强 Leader 的，而 Paxos 算法是无 Leader 或者弱 Leader 的。而因为有了强 Leader，Raft 算法就可以进一步地要求日志里面不能有空洞。使用随机化来简化 Raft 中领导人选举算法。
对应到代码上，深入剖析共识性算法Raft（PS： 总结的很好）Raft 算法中服务器节点之间的通信使用远程过程调用（RPC）。基本的一致性算法只需要两种 RPC：
- RequestVote RPC：请求投票 RPC，由 Candidate 在选举期间发起。
- AppendEntries RPC：附加条目 RPC，由 Leader 发起，用来复制日志和提供一种心跳机制。
Raft 和 Paxos
Raft 算法属于 Multi-Paxos 算法，它是在兰伯特 Multi-Paxos 思想的基础上，做了一些简化和限制，比如增加了日志必须是连续的，只支持领导者、跟随者和候选人三种状态，在理解和算法实现上都相对容易许多。Raft 算法是现在分布式系统开发首选的共识算法。绝大多数选用 Paxos 算法的系统（比如 Cubby、Spanner）都是在 Raft 算法发布前开发的，当时没得选；而全新的系统大多选择了 Raft 算法（比如 Etcd、Consul、CockroachDB）。Raft将整个共识过程分解为几个子问题：领导者选举、日志复制和安全性。整个 Raft 算法因此变得易理解、易论证、易实现，从而让分布式一致性协议可以较为简单地实现。
《In Search of an Understandable Consensus Algorithm》： In order to enhance understandability, Raft separates the key elements of consensus, such as leader election, log replication, and safety, and it enforces a stronger degree of coherency to reduce the number of states that must be considered.
《In Search of an Understandable Consensus Algorithm》单决策（Single-decree）Paxos 是晦涩且微妙的：它被划分为两个没有简单直观解释的阶段，并且难以独立理解。正因为如此，它不能很直观的让我们知道为什么单一决策协议能够工作。为多决策 Paxos 设计的规则又添加了额外的复杂性和精巧性。我们相信多决策问题能够分解为其它更直观的方式。PS： 现实问题是多决策的，paxos 单决策出现在 多决策之前，彼时是以单决策的视角来考虑问题（在单决策场景下，选主不是很重要），又简单的以为将单决策 组合起来就可以支持 多决策。
Raft与Multi-Paxos中相似的概念：
| raft | Multi-Paxos |
|---|---|
| leader | proposer |
| term | proposal id |
| log entry | proposal |
| log index | instance id |
| Leader选举，“随机超时+多数派”机制，仅允许拥有最新日志的节点当选为Leader | prepare 阶段 |
| 日志复制 | Accept阶段 |
Raft与Multi-Paxos的不同：
| raft | Multi-Paxos | |
|---|---|---|
| 领导者 | 强leader | 弱leader |
| 领导者选举权 | 具有已连续提交日志的副本 | 任意副本 |
| 日志复制 | 保证复制 | 允许空洞 |
| 日志提交 | 推进commit index | 异步的commit 消息 |
Raft 和 Paxos 最大的不同之处就在于 Raft 的强主/强领导特性：
- 在 Paxos 中，leader选举和基本的一致性协议是正交的：leader选举仅仅是性能优化的手段（省得七嘴八舌效率低），而且不是一致性所必须要求的，是可以随时被更换的。但是，这样就增加了多余的机制：Paxos 同时包含了针对基本一致性要求的两阶段提交协议和针对leader选举的独立的机制。
- 相比较而言，Raft 就直接将leader选举纳入到一致性算法中，并作为两阶段一致性的第一步，并且将尽可能多的功能集中到了leader身上。Leader是拥有最多信息的那个Proposer，Leader的标准就是整个分组的标准，不一致的地方统统以Leader为准。事实上，其余角色都指着Leader存活，成为了Leader的依附，更换Leader也就成为了一件非常慎重的事情，中间甚至会产生共识停服的窗口。强主」模式体现了Raft的「简单有效好实现」的设计理念，也直接支撑了其它如日志复制、一致性保障等模块的简化。
- 所有的日志流均是严格按顺序从Leader发送给Follower，这个共识组里面并不存在其它通信通道。
- Leader给Follower发送的每条日志X都包含有Leader记录的该Follower上一条消费的日志Y，在Follower这边收到Leader发送过来的日志X并准备接受之前，会检查本地记录的上一条日志是否是Y，如果不一致，那么一切以Leader为标准，Follower继续往前追溯，找到与Leader分叉点，消除掉本地分叉并坚决学习Leader的日志。
- 通过这个强主逻辑的设计，日志复制管理得到了质的简化，事实上消除了日志空洞的情形，也将更加方便拉平两个节点的最新日志。Multi Paxos支持提议的乱序提交，允许日志空洞存在，这个虽然是提供了协议的灵活性，并发性也更优，但是的确让协议变得更加的复杂，阻碍了协议的工业落地。
强Leader在工程中一般使用Leader Lease和Leader Stickiness来保证：
- Leader Lease：上一任Leader的Lease过期后，随机等待一段时间再发起Leader选举，保证新旧Leader的Lease不重叠。
- Leader Stickiness：Leader Lease未过期的Follower拒绝新的Leader选举请求。
Leader 选举
Raft协议比paxos的优点是 容易理解，容易实现。它强化了leader的地位，把整个协议可以清楚的分割成两个部分，并利用日志的连续性做了一些简化：
- Leader在时。leader来处理所有来自客户端的请求，由Leader向Follower同步日志 ==> 日志流动是单向的
- Leader挂掉了，选一个新Leader
- 在初始状态下，集群中所有的节点都是follower的状态。
- Raft 算法实现了随机超时时间的特性。也就是说，每个节点等待Leader节点心跳信息的超时时间间隔是随机的。等待超时时间最小的节点（以下称节点 A），它会最先因为没有等到Leader的心跳信息，发生超时。
- 这个时候，节点 A 就增加自己的任期编号，并推举自己为候选人，先给自己投上一张选票，然后向其他节点发送请求投票 RPC 消息，请它们选举自己为领导者。
- 如果其他节点接收到候选人 A 的请求投票 RPC 消息，在编号为 1 的这届任期内，也还没有进行过投票，那么它将把选票投给节点 A，并增加自己的任期编号。
- 如果候选人在选举超时时间内赢得了大多数的选票，那么它就会成为本届任期内新的领导者。节点 A 当选领导者后，他将周期性地发送心跳消息，通知其他服务器我是领导者，阻止跟随者发起新的选举，篡权。
在 Raft 算法中，约定了很多规则，主要有这样几点
- 领导者周期性地向所有跟随者发送心跳消息，通知大家我是领导者，阻止跟随者发起新的选举。
- 如果在指定时间内，跟随者没有接收到来自领导者的消息，那么它就认为当前没有领导者，推举自己为候选人，发起领导者选举。
- 在一次选举中，赢得大多数选票的候选人，将晋升为领导者。
- 在一个任期内，领导者一直都会是领导者，直到它自身出现问题（比如宕机），或者因为网络延迟，其他节点发起一轮新的选举。
- 在一次选举中，每一个服务器节点最多会对一个任期编号投出一张选票，并且按照“先来先服务”的原则进行投票。
- 日志完整性高的跟随者（也就是最后一条日志项对应的任期编号值更大，索引号更大），拒绝投票给日志完整性低的候选人。
- 如果一个候选人或者领导者，发现自己的任期编号比其他节点小，那么它会立即恢复成跟随者状态。
- 如果一个节点接收到一个包含较小的任期编号值的请求，那么它会直接拒绝这个请求。
在议会选举中，常出现未达到指定票数，选举无效，需要重新选举的情况。在 Raft 算法的选举中，也存在类似的问题，那它是如何处理选举无效的问题呢？其实，Raft 算法巧妙地使用随机选举超时时间的方法，把超时时间都分散开来，在大多数情况下只有一个服务器节点先发起选举，而不是同时发起选举，这样就能减少因选票瓜分导致选举失败的情况。如何避免候选人同时发起选举？
- 跟随者等待领导者心跳信息超时的时间间隔，是随机的；
- 如果候选人在一个随机时间间隔内，没有赢得过半票数，那么选举无效了，然后候选人发起新一轮的选举，也就是说，等待选举超时的时间间隔，是随机的。
小结：Raft 算法通过任期的概念来分隔时间，每个任期开始都会进行一次领导者选举。任期是一个递增的数字，每次选举都会增加。如果跟随者在“选举超时”之内没有收到领导者的心跳，它会将自己的任期号加一，并转变为候选者状态来发起一次领导者选举。候选者首先给自己投票，并向其他节点发送请求投票的 RPC。如果接收节点在当前任期内还没有投票，它会同意投票给请求者。如果候选者在一次选举中从集群的大多数节点获得了选票，它就会成为领导者。在此过程中生成的任期号用于节点之间的通信，以防止过时的信息导致错误。例如，如果节点收到任期号比自己小的请求，它会拒绝该请求。极端情况下集群可能会出现脑裂或网络问题，此时集群可能会被分割成几个互不通信的子集。不过由于Raft算法要求一个领导者必须拥有集群大多数节点的支持，这保证了即使在脑裂的情况下，最多只有一个子集能够选出一个有效的领导者。
日志复制
Leader，本质上是通过一个两阶段提交，来做到同步复制的。一方面，它会先把日志写在本地，同时也发送给 Follower，这个时候，日志还没有提交，也就没有实际生效。Follower 会返回 Leader，是否可以提交日志。当 Leader 接收到超过一半的 Follower 可以提交日志的响应之后，它会再次发送一个提交的请求给到 Follower，完成实际的日志提交，并把写入结果返回给客户端。因此，Raft 确保了即使在领导者崩溃或网络分区的情况下，也不会有数据丢失。任何被提交的日志条目都保证在后续的任期中也存在于任意新的领导者的日志中。PS：作为应用层的kafka可以削弱一致性（ISR协议，BookKeeper的Quorum协议），比如client发消息到主分区即可认为消息发送成功，但是infra层的raft leader+follower 全部写入ok再返回给client的。
简单来说，Raft 算法的特点就是 Strong Leader： a. 系统中必须存在且同一时刻只能有一个 Leader，只有 Leader 可以接受 Clients 发过来的请求； b. Leader 负责主动与所有 Followers 通信，负责将“提案”发送给所有 Followers，同时收集多数派的 Followers 应答； c. Leader 还需向所有 Followers 主动发送心跳维持领导地位（保持存在感）。
副本数据是以日志的形式存在的，日志是由日志项组成，日志项是一种数据格式，它主要包含用户指定的数据，也就是指令（Command），还包含一些附加信息，比如索引值（Log index）、任期编号（Term）。
- 指令：一条由客户端请求指定的、状态机需要执行的指令。你可以将指令理解成客户端指定的数据。
- 索引值：日志项对应的整数索引值。它其实就是用来标识日志项的，是一个连续的、单调递增的整数号码。
- 任期编号：创建这条日志项的领导者的任期编号。任期在 Raft 算法中充当逻辑时钟的作用，使得服务器节点可以查明一些过期的信息（比如过期的 Leader）。
- 接收到客户端请求后，领导者基于客户端请求中的指令，创建一个新日志项，并附加到本地日志中。
- 领导者通过日志复制 RPC，将新的日志项复制到其他的服务器。
- 当领导者将日志项，成功复制到大多数的服务器上的时候，领导者会将这条日志项应用到它的状态机中。
- 领导者将执行的结果返回给客户端。
- 当跟随者接收到心跳信息，或者新的日志复制 RPC 消息后，如果跟随者发现领导者已经提交了某条日志项，而它还没应用，那么跟随者就将这条日志项应用到本地的状态机中。
在实际环境中，复制日志的时候，你可能会遇到进程崩溃、服务器宕机等问题，这些问题会导致日志不一致。那么在这种情况下，Raft 算法是如何处理不一致日志，实现日志的一致的呢？
- 领导者通过日志复制 RPC 的一致性检查，找到跟随者节点上，与自己相同日志项的最大索引值。也就是说，这个索引值之前的日志，领导者和跟随者是一致的，之后的日志是不一致的了。
- 领导者强制跟随者更新覆盖的不一致日志项，实现日志的一致。
跟随者中的不一致日志项会被领导者的日志覆盖，而且领导者从来不会覆盖或者删除自己的日志。
类似的思路：The Google File System （二）：如何应对网络瓶颈？
ZAB
Paxos 算法有点过于复杂、实现难度也比较高，所以 ZooKeeper 在编程实现的时候将其简化成了一种叫做 ZAB 的算法（Zookeeper Atomic Broadcast， Zookeeper 原子广播）。
ZAB 算法的目的，同样是在多台服务器之间达成一致，保证这些服务器上存储的数据是一致的。ZAB 算法的主要特点在于：需要在这些服务器中选举一个 Leader，所有的写请求都必须提交给 Leader。由 Leader 服务器向其他服务器（Follower）发起 Propose，通知所有服务器：我们要完成一个写操作请求，大家检查自己的数据状态，是否有问题。如果所有 Follower 服务器都回复 Leader 服务器 ACK，即没有问题，那么 Leader 服务器会向所有 Follower 发送 Commit 命令，要求所有服务器完成写操作。这样包括 Leader 服务器在内的所有 ZooKeeper 集群服务器的数据，就都更新并保持一致了。如果有两个客户端程序同时请求修改同一个数据，因为必须要经过 Leader 的审核，而 Leader 只接受其中一个请求，数据也会保持一致。PS：怪不得带有广播二字
在实际应用中，客户端程序可以连接任意一个 Follower，进行数据读写操作。如果是写操作，那么这个请求会被这个 Follower 发送给 Leader，进行如上所述的处理；如果是读操作，因为所有服务器的数据都是一致的，那么这个 Follower 直接返回自己本地的数据给客户端就可以了。
其它
生活中面临的任何选择，最后都可以转换为一个问题：你想要什么（以及为此愿意牺牲什么）。任何不一致问题， 本质上都可以转换为一个一致问题。 一个队伍谁当老大 可以各不服气，但大家可以对“多票当选”取得一致，这就是所谓“民主”。你可以不尊重老大，但必须尊重价值观。而在basic-poxos 中，底层的“价值观”就是：谁的ProposerId 大谁的优先级更高。有了“优先级”/“价值观” 就可以让“无序”的世界变“有序”。