本文的目的：
最新在看Group Replication(简称GR)的代码，从Codeship的Galera到MariaDB Galera Cluster/Percona XtrDB Cluster的多主集群技术，再到如今的GR; 分布式存储系统，尤其是分布式的RDBMS必然是未来的趋势。其中最本质和最难的一个问题就是一致性问题，一致性问题已经是如今分布式系统必须要面临的问题。从原子广播到Viewstamped Replication/Paxos/Raft… 查阅了很多分布式一致性的理论paper和工程技术，把觉得不错的资料翻译总结一下。
基本概念：
log: 代表对存储系统的一次操作记录，比如一条redolog日志或者binlog
message: 分布式系统中各个Server交互的单元
term: 一个任期的编号，就如美国总统的克林顿、小布什等不同任职区间
index: 在一个term内的序号，通常是连续递增的
slot: log序列中每一个log entry的全局位点
其实一致性算法的核心思想非常简单，可以这么简单(接地气)地理解:
1. 一群人(集群中的Server)对某个问题吵得不可开交，相持没有一个统一结论；
2. 过了很久... 大家都累了，意识到需要一位德高望重的领袖(Leader)，听取Leader的意见；
3. 于是不同阵营推举一位局部可以服众的侯选人(Leader Candidate)；
4. 给候选人5分钟拉票时间(timeout)，然后让其他人投票(Election)，我们姑且认为选举是公平公正的；
5. 最后选举出Leader了，虽然还是有些人不服，反正少数服从多数(多数派)；
6. 以后的事情，都由Leader来提建议，大多数人同意后就张榜公布，一旦公布的结论就不能更改了(不能干打脸的事情)；大家也就没什么异议了(少数人不服也只有忍~);
7. Leader当久了，难免有点权钱交易啊，这个时候可能被反腐了(Leader不可用); 可生活还得继续不是，需要重新选举一位Leader，这就重复前面的历史了...; 当然也有些Leader不是因为权钱交易挂的，有被和谐的，有被揭竿而起的... 反正就是下课了，总进不了世界杯领导压力大换个洋教头也行啊！
8. 哪能啊，上一届领导的烂账，肿么办？一个叫Raft的青年说：“先把屁股擦干净，否则老子不接这个烂摊子，我要有队伍的绝对控制权！” 于是Raft正式上任前，就带一帮人把旧账本理清楚了，也公示了，然后走马上任开启了属于自己的时代！
9. 当官都是肥差，像年轻的Raft青年这样NB哄哄，有的时候也没人鸟他...于是还是有些迫不及待的老油条，先占住Leader的坑，至于前任的烂帐本，上任后的三把火来烧呗！没错，这老司机就是Paxos...
10. 貌似这Paxos兄弟江湖口碑一般啊？唉，自古套路留人心，这些老司机有很多法宝，分分钟教你做人。所以，外面很多门(学)派(术)都在研究Paxos。
1. 背景
一致性是提供容错服务的关键部分，例如分布式强一致存储系统，非阻塞的原子广播、Paxos和Raft是三种常见的一致性算法。Paxos被学术界广泛地研究，Raft则在工程师层面非常受欢迎。
尽管学术界对Paxos情有独钟，但Raft却非常流行。工程师可以通过阅读几篇论文就可以理解Raft算法，然后实现Raft算法去解决一些实际的工程问题。算法实现的过程中要考虑通讯交互的次数，消息的数量和资源的占用率等等，综合权衡这些因素的同时还要保证有较好的系统性能。同时，算法的实现还要考虑算法理论和工程实践之间经常会遇到的一些问题。
为了克服这些障碍，Diego Ongaro和John Ousterhout发表了一种叫做Raft的新一致性算法，其设计的初衷是更易于理解、以及比Paxos更好的工程化实现等。尽管Raft算法给复杂的分布式系统带来了耳目一新的感觉，但其中大部分思想和Paxos算法的本质是相同的。例如，都会选择一个唯一的Leader来负责参与者能否就某个问题达成一致。
在这边文章中，我们将简要地介绍Paxos和Raft之间的异同。首先我们会讨论什么是一致性算法；然后我们会介绍如何实例化一个一致性算法来构建一个数据复制方案；最后我们介绍Leader是如何选举的，以及一致性算法的安全性和活性。
请记住，本文的目的不是深入讨论Paxos和Raft算法(Paxos算法的某些部分至今未理解透)，而仅仅是对两者的一个概要介绍。如果需要深入了解这两个算法的细节，请阅读参考论文1/2/3/4.
2. 分布式一致性
2.1 分布式系统的特征
安全性和活性是分布式系统具有的两个基本特性，因为安全性和活性是系统正确性的充分必要条件。安全性表示推导过程是正确的，即便有意外情况存在，这种意外也绝对不会发生，最终都会得到一个正确的结果。活性表示最终会得到一个结果，不会因为某种相持而让系统无法继续推演至得到结果(在有限的时间内得到一个结果)。从定义上可以这么理解：
安全性
只有被提议的值才可能被选定(不会选定一个未被提议的值)
只会选定唯一的一个值
在一个值真正被选定之前，不会被其它Server学习到
活性
最终一定有某些被提议的值被选定
一个被选定的值，最终一定会被其它Server学习到
2.2 决议的达成
在一致性算法中，目标是在多个Server之间就某个问题达成一致，活性体现为最终多个Server一定会就某个问题达成一致，不会一直僵持无果；安全性体现为不会有两个Server包含不同决议。
不幸的是，一个Server可能比其它Server执行得慢、可能Crash、可能停止处理一致性算法逻辑。消息可能延迟，乱序或者丢失。所有的这些因素导致实现一个一致性算法是非常复杂的，也很难保证在稳定的时间内得出正确的决议。虽然我们不能确切地知道一个分布式系统在哪个时刻达到”稳定”状态，但我们知道最终它一定会达到一个“稳定”状态。
一次决议达成包含两次通讯:
leader–(1)–>servers–(2)–>leader:
Leader发送一个想要达成一致性的提案给所有参与者，每一个收到这个提案的参与者回复一个ACK给Leader,表示他们已经接受这个提案。在Leader接收到多数派的ACK后，大家对这个提案就达成一致了。
值得注意的是，我们在上面的分析中忽略了两条消息：第一条是从发起者到Leader之间(发送希望达成一致的意向)，第二条是Leader发送给所有的参与者，通知针对某个提案已经达成一致。第二条消息可以通过下面两种方式避免：
一个Server可以把已经Accept的消息发送给其他所有Server
Leader可以在下一次发送其他提案时附带已经达成一致的消息编号
2.3 日志复制
为了实现复制，一般会启动多个一致性算法的实例，每一个实例对应复制日志中的一个log entry，复制日志通常被持久化到磁盘上。Leader可以并行多个一致性算法的实例来针对不同的log entry达成一致，通过这种方式可以提升性能。但是，并行的程度取决于硬件，网络和应用程序本身。
每一个Leader只对自己所在的任期负责，当Leader发生改变的时候，其对应的任期编号也随之递增:
2.4 Leader选举
无论Paxos算法还是Raft算法，最终都会产生一个Leader，所有其他正常的Server信任Leader来协调一致性的达成，一个任期内只有一个Leader.如果当前任期的Leader不可用，会触发选举一个新的Leader，新Leader的任期编号将大于当前任期编号(Term).
在Raft中，一个Server(Leader候选)发送一个“选举请求”给其他Server，期望在正式成为Leader之前得到多数派Server的响应。如果没有收到多数派Server的响应或者被告知已经有其他Server成为Leader，当前Server会在timeout后开启一次新的选举流程。在一个term内，任何Server只能为一个Leader候选投票。
Paxos没有明确定义Leader是如何产生的。为了简单起见，一般都使用基于等级的优先级，比如依据Server的ID(一个整数)。因此，在所有正常的服务器中，总是拥有最高等级或者最低等级的服务器变成Leader. 尽管这是一种简单直观的方案，也需要在两个任期之间划分间隔：
新任期 = 旧任期 + N(集群中的服务器数目)
Raft对选举流程加了一些限制：只有最新的Server才能被选举为Leader。基本上，这种机制保证了Leader拥有所有在上一个任期内达成一致的日志，Leader不需要从全局达成一致的日志中去学习那些它自身没有的日志。因此当一个Server成为Leader后，它可以立即对外服务，比如向其他Server发起一致性提案。
和Raft不同，Paxos允许任何Server被选举为Leader. 因此在Paxos中当一个Server成为Leader后，它需要首先向其它Server学习旧任期内已经达成一致的日志，然后才能对外提供服务。可以很明显地看出，这种灵活性带来了额外的复杂度。
如上图所示，在Raft中只有Server1和Server2可以被选举为Leader. 在Paxos中，所有Server都可以被选举为Leader.
2.5 安全性
源于分布式系统的异步特性，某个Server可能不时地故障并随时触发新一轮的选举。这意味着整个集群中的Server可能在某个时刻临时处于不同的任期(Term)内，但是他们最终都进入到相同的任期。
任何时候，如果一个Server收到一个来至旧任期内的消息，这意味着发送者要么是Leader，要么是旧任期内试图成为Leader的一个Server.这种情况下，接收端Server必须拒绝这个消息并通知发送端Server.
如果一个Server接收到一个任期编号大于其当前任期，这意味着已经有一个新Leader产生，接收端必须开始接收新Leader的“提案”.
值得注意的是，两种算法都需要严格地避免覆盖旧Leader已经达成一致的决议，因为这是明显不安全的。这是Raft和Paxos的核心差异之一，这一点上我们可以看到Raft算法的相对简单和直接。
正如前面提到过的一样，Raft在Leader选举的时候做出了一些限制，只有拥有最新一致决议的Server才能被选举为Leader:
Raft对比不同Server中最后一条log记录的Index和Term来决定是否拥有最新的决议。如果两条log的Term不相同，则Term较大者胜出。如果两条log的Term相同，则Index较大者胜出。
Leader只需要保证已经复制的log最终都会被收集到，它通过加入下面的限制来实现这一点：对于一个特定的slot， 当其尚未对index为”n-1”的提案达成一致之前，不会接受index为”n”的提案。
Leader会在当前log中包含上一个log的Term编号，接收端Server只会接收和上一个log匹配的log请求(同一个Term内Index编号连续)。否则，它会要求Leader发送自己尚不存在的log，以此类推“n-2”和“n-3”等等。
在Paxos中，任何一个Server都可能成为Leader，因此避免一个已经达成的决议被覆盖的任务相对复杂一些。新Leader首先必须找出其它Server都已经处理了哪些决议，然后再开始对外提供服务。
在Paxos算法中，当一个新Leader被选举出来后，有一个“准备”阶段必须执行。“准备”消息包含新的任期编号Term和slot编号“n”，“n”代表前面已经达成一致的决议序号。其他Server回复大于slot编号“n”的信息，这些信息被用于限制新Leader可以对这些slot提议的值。
2.6 活性
只要集群中Server多数派存活，就可以保证集群可以正常服务(选举和一致性达成流程都可以正常进行)[9].正如前面提到的活性定义，因为Raft和Paxos实际都会有一个Leader来对某一个提案负责，不会出现僵持无果的问题。
3. 结论
通过上面的分析我们了解了Raft和Paxos之间的异同，关键的不同之处在于Leader的选举和安全性的保证。Raft只允许拥有最新数据的Server变成Leader，而Paxos没有这个限制。这是Paxos的灵活性，当然这个灵活性也带来了额外的复杂度。
值得注意的是无论在Raft还是在Paxos中，Leade都很容易成为系统的瓶颈，因为所有的请求都会经过Leader。在有Leader的集群中，消息处理的时间复杂度为O(N)，而在无Leader的集群中，消息处理的时间复杂度为O(1).
已经有一些基于Paxos的协议支持多个Leader，比如：Mencius；另外还有一些基于Paxos的有序无冲突并行协议，例如：Egalitarian Paxos 和Generalized Paxos. 希望能够看到基于Raft协议的这种优化！
01 – Paxos made simple
02 – In Search of an Understandable Consensus Algorithm
03 – Desconstructing Paxos
04 – Yet Another Visit to Paxos
05 – Consensus in the presence of partial synchrony
06 – Failure Detection and Consensus in the Crash-Recovery Model
07 – Tuning paxos for high-throughput with batching and pipelining
08 – Introduction to Reliable and Secure Distributed Programming
09 – Lower Bounds for Asynchronous Consensus
10 – Mencius: Building Efficient Replicated State Machines for WANs
11 – There Is More Consensus in Egalitarian Parliaments
12 – Generalized Consensus and Paxos
閱讀更多 中國存儲 的文章
