从leaderless到leader-based
在上篇Leaderless multi-Paxos Replicated State Machine中分析了leaderless multi-paxos的一些特点，包括支持client通过各个server并发提交（但是需要注意并发度大时，log index的选择很容易冲突）、每次提交执行一轮完整的single decree流程、每个paxos instance内要保证所有的提议ID必须唯一、冲突的发生导致提议可能在预提议阶段或提议阶段被拒绝、“空洞”的存在，等等。
leader-based multi-paxos是对leaderless方案的一种优化。由于log index的冲突原因在于client互相不知道对方的提议，所有的提议如果通过单一leader或少量leader进行，就不容易甚至不会冲突。并且，通过leader同样可以实现并行提交，只是对于leader的资源使用比leaderless更多。另一方面，leaderless方案中每个paxos instance需要预提议阶段，原因是在多个client同时像paxos instance提议情况下，需要学习可能选中的旧值，确保唯一性，但是在单一leader下，对于paxos instance的提议都可通过唯一leader进行，在单一leader工作时，无需预提议阶段（在leader transfer过程中仍然需要）。因此，在引入新的、可接受的代价下，leader-based方案能够保证并发度，减少冲突，减少消息数量。
优点:
- 冲突解决：leaderless方案中，log index在不同的server上生成，容易冲突，冲突既可能在预提议阶段发生，也可能在正式提议（accept）阶段发生，后者重试的代价更大（假设有算法可以满足各个server并发选择的log index冲突几率较小，这一定也是个分布式算法，执行代价也不可不计）。leader-based方案在一个leader lease内完全可通过本地原子计数器并发地为不同的paxos instance选择log index，不会冲突，且代价小。
- 预提议优化：leaderless方案中，每个paxos instance都要走完整个single decree流程，由于不知道其他server是否提交过新的提议，所以总是要通过预提议流程去确认。leader-based方案由于在自己的leader lease内所有提交都是通过自己，因此可以在lease内完全省去预提议流程，节省资源开销。
- 正确性：Leader-based multi paxos还有个好处是，即便出现brain split，大不了短期内退化成leaderless方案，不会对正确性有影响。
缺点：
- leader负载高：Leaderless方案中，大量client可以通过负载均衡选择向不同的server请求。leader-based方案，所有client只能向唯一的leader请求，对leader的网络带宽和cpu是个挑战。同时，无法像leaderless那样照顾到不同地理位置的client，减少延迟。也无法支持通过不同server读以提高读吞吐率（在线性一致性前提下）。
Leader-based方案的改进点
增加Leader的选择
leader机制大概存在两种：
- 在某个提议者提交成功后，接受提议的接受者之后一段时间内不再接受client请求（lease机制），使得之后的请求都route到提议者，提议者周期性地发送心跳消息给每个server以更新自己的lease（提议者心跳间隔要比lease短，且之前的多数接受者只接受当前leader的心跳），这是一种通过调整请求接受的策略达到自动选择leader的功能 [chubby做法]。（接受者只能接受一个leader的心跳，就能保证唯一leader）
- 通过single decree决议出一个leader，然后类似方案1的方式实现lease管理（这种leader也叫master）。
不管是那种实现方式，leader的产生都需要一个额外的预提议过程。
注：leader lease的语义：只要leader的lease不到期，其它server就不能成功向paxos提交。
提议ID的选择
leaderless方案中，采用了一个统一的、全局唯一、单调递增的ID生成方式（比如：local timestamp + ip，参考leaderless方案），实际上前文分析了每个paxos instance的提议ID之间并不需要保证不相同，在一个leader lease内针对各个log index的所有提议都可以使用同一个提议ID，如果提议被拒绝，反而表示存在其它leader也在提议，当前被拒绝leader可以放弃leader身份了，因此可以把提议ID的变化看成是一次leader角色的变化。
Log index的选择
leaderless方案中，由于要解决external causality问题，并且各自不知道其它server的client请求前提下，只能确保新的log index > 已提交的最大log index。多个server容易在log index选择上冲突（参考leaderless方案）。然而，leader-based方案只需要使用last_log_index + 1即可（不会冲突，也不需要向其它接受者询问，但是会引入“幽灵复现”问题）。
发起部分single decree
single decree比leaderless简单许多，只有唯一leader，直接正式提议（accept）即可，log index递增。
数据不一致的处理
在leaderless方案中曾提到由于“空洞”以及server crash、消息没收到等原因会导致server之间数据的不一致（leaderless数据不一致处理），需要通过“拉”（Pull）数据的方法进行确认更新。leaderless方案中，由于每个server都能并行请求，所以经常需要在多个server上“拉”数据，对于leader-based方案来说，所有的请求都通过leader执行，leader作为提议者知道哪些paxos instance是否提交成功，因此， leader对于自己处理过并已经commit的paxos instance不需要single decree去确认一致性（收不到足够多回复要不停重试），只要leader一直有效，不会出现数据不一致的情况。数据不一致的情况只会发生在leader crash导致的leader transfer后新leader的数据不一致，那么这时新leader只能采用leaderless的方法进行一致性确认与修复。首先，从某多数集合中查询最大log index作为end index（log index不需要已经commit）。然后，从已commit的下一个log index开始到end index，对每一个log index执行single decree流程。如果新leader在log上“落后”较多，延迟会比较大。
读写操作
leader-based方案的读写操作过程和leaderless方案大致相同（参考leaderless方案），但是可以进行若干优化。
读操作优化
leaderless方案不能直接从本地state machine读取数据的原因在于client支持从任意server提交指令，然而，server可能是“落后”的，为了防止stale data，必须进行一轮新的paxos。
对于leader-based方案来说，leader一定是up-to-date的，或者通过新执行一轮paxos达到up-to-date。
参考资料：
[1] Lamport, L. 2001. Paxos made simple.
[2] Tushar Chandra, Robert Griesemer, Joshua Redstone. 2007. Paxos Made Live - An Engineering Perspective.
[3] John Ousterhout and Diego Ongaro. 2013. Implementing Replicated Logs with Paxos.
[4] Diego Ongaro. 2014. Consensus: Bridging Theory And Practice.
[5] 郁白. 2015. 使用Multi-Paxos协议的日志同步与恢复.