我觉得学习Paxos/Raft的最大障碍并不是算法本身复杂，而是难以理解。就好像某些数学结论，证明过程不难，但是结论却很难从直观上去理解。本文就是希望能借助一个假想中的系统，逐步加强约束，引导到Paxos/Raft，希望能一定程度上解释“为啥要用共识算法”以及“不用共识算法会怎样”的问题。
本文结构在很大程度上参考了drdrxp阁下的一个PPT，他的微博主页上也有对应一篇很棒的关于Paxos的文章，这里表示感谢及一并推荐给大家。不过因为理解角度不同，本文很多地方有诸多差异，例如关于半同步复制为什么不可行，本文给出了另一种解释，另外这里没有讲Fast Paxos，但是多了关于Raft的内容，希望读者可以进行比较阅读：）
我们假想一个抢购手机的网络服务，因为这款手机的用户都比较发烧，所以一次只卖一个手机。在活动之前，系统会给每个用户分配一个E码作为唯一标识，抢购时间到达之后，所有用户通过客户端发送E码到服务器，服务器把手机分配给一个用户。
第一版设计我们使用单机服务器模式：搞一台主机作为服务器，当收到第一个请求后，保存这个用户的E码，并给客户端返回“抢购成功”，对于后续的所有请求，只要E码跟保存的不一样，一律返回“抢购失败”。
单机模式的缺陷大家都耳熟能详了，就是不能容忍节点发生故障。仅有的一台服务一旦故障，整个服务就不能用了，这个指的是可用性。还有一个批判的角度是容灾性，如果这台服务器的数据损坏了，我们将无从判断这台手机是否已经被卖给了某个用户。
大家都知道用户数据是非常重要的资产，万万不能丢，一定要备份。
所谓备份，就是定期把数据拷贝一份放在别的地方。还有一个概念叫异步复制，其实本质上差别不大，我们放在一起讨论。这里说异步，指的是最新的数据并不是与备份副本实时同步的。
备份能解决一部分数据容灾的问题。这里限定说“一部分”，是因为异步模式存在一个不同步的时间窗口。如果Master在(3)OK返回给客户端之后故障了，E的值将不能被复制到Slave。之后如果使用Slave数据来恢复服务，手机将再次被卖给另外一个人，也就是一致性被破坏了。
异步的不行，那同步的怎么样呢？
如图所示，Master收到请求后，先同步给Slave，Slave存盘后返回OK，然后Master再存盘并给客户端返回OK。
如果Slave故障了，我们把Master切换成单机模式继续提供服务。如果Master故障了，我们就把Slave切换成Master提供服务。因为是同步的，两种情况都不会产生数据丢失。
注意这里假设Slave在存完盘返回消息之前故障，也不算丢数据，因为此时Master并没有给客户端返回OK，所以手机是可以再卖给另一个人的，只需要在Slave恢复之后，Master再把新值同步过去就行了。
看上去就很完美了，可用性和一致性都能得到保证，只需要有一个负责任的工程师来盯着服务器，故障的时候切一下状态就行了。
问题就出在这个工程师身上。
我们必须要把工程师这个人也算成分布式系统的一部分，要考虑到人也会故障的（生病，意外，手机欠费失联，突然想去看看世界），而且通常管理员也是通过网络来运维管理，当服务器节点之前网络中断时，管理员也很可能无法访问某些节点。实际上我们完全可以把工程师看作集群里的一个故障检测程序来分析问题。
如图(A)，假如Admin节点离Master比较近，那么当他们一起故障时，Slave无法被提升成Master。同理(图B)，Admin跟Slave一起故障时，Master也无法切换成单机模式。
那我多搞几个Admin，分别跟Master/Slave部署在一起行不行？也是不行的，这样看起来Master/Slave不管谁故障了，另一个没故障的总有Admin来操作。但是假如发生了网络隔离，如果Admin判断对面故障了，贸然切换状态，可能会出现两都是Master同时提供服务，一致性被破坏。
还有一种打补丁的思路，就是引入一个仲裁者(图D)的角色，Master和Slave不断心跳上报状态，发现对面失联想切换状态时，也要向Meta申请。这样一来，当Master和Slave断开时，取决于谁跟Meta是连着的，以及谁能更快地把状态切换请求发给Meta。
不过这里的问题在于，如何保证Meta的高可用和容灾性呢？（禁止套娃）
回顾一下上面提到的各种方案，我们能发现一个有趣的现象：每次都是跪在系统中的特殊节点上面。比如仲裁者Meta，或者负责切换状态的Admin，还可以包括单机模式下的那个唯一单点。由于特殊节点的不可替代性，一旦故障了，牵一发动全身，整个系统就离挂掉不远了。
说明一下，这里从可用性来分析，我们不认为Master是特殊节点，因为Master和Slave是可以相互替代的。
从消除特殊节点的思路出发，我们把之前方案里的仲裁者Meta换成Slave，就得到了半同步复制模式。
具体来说，Master收到消息先本地持久化，然后同时同步给两个Slave，当其中任意一个Slave完成持久化并返回OK后，Master返回OK给客户端。
不难分析，任意一个Slave故障时，都不会影响服务。假如Master故障，则需要两个Slave挑一个出来当新的Master，此时可能只有一个Slave同步到数据，我们需要选择有数据的节点当Master。如果两个Slave都没数据，那任选一个就行。
这里的Slave其实同时承载了“仲裁节点”的角色，当Master和另一个Slave断连时，如果此Slave能连上Master，则支持Master继续提供服务，反之如果此Slave只能连到另一个Slave，那这两个Slave放弃旧Master选个新的出来。
如此这般，这个方案能很好地满足单节点故障时的可用性和一致性，而且规则简单，不需要人工介入就能自动完成。可惜它还是有缺陷的，前面我们其实只分析了单次故障的情形，如果连续多次故障，就不行了。
如图，Master本地写完E=1后故障了，Slave选出新的Master然后写入E=2，随后新Master也故障同时旧Master又活过来了，然后剩下的两个节点都有数据，还都不一样，你瞧瞧我，我瞧瞧你，不知道谁来当Master合适。
你可能想说，我们改下流程，写入时先在Slave持久化，OK返回给Master后再在Master持久化，这样是不是就行了？这样也是不行的，因为Slave可能在刚持久化之后就故障了，随后另外两个节点写入新值并再次故障，最后结果是一样的。
半同步复制还可以进一步打补丁，不过这里我们先放一放，来看一下另一个思路。
如果我们进一步消除节点的特殊性，即不再区分Master和Slave，可以得到另一个方案：客户端把请求同时发向3个节点，当其中2个节点返回OK后，就认为写入成功。
如图所示，Node1和Node2成功持久化了E=1并返回OK，之后Client2再尝试写入E=2时，最多只能写入Node3一个节点，因此无法成功写入，这样我们就保证了手机不可能被卖给2个人。
这里我们利用了“鸽巢原理”：client1和client2要想都写入成功，需要各收到2个OK，而每个节点都只会给第一个请求的客户端发送OK，也就是说总共只能发出去3个OK，因此只有一个客户端能写入成功。
这个规律也可以推广至更多数量的节点，只要规定要求写入的节点数大于一半，就只能写成功一个。
还有一种表述是，两个包含大多数成员的子集，一定至少有一个公共节点。这个性质十分重要，后面我们还会用到。
这个方案的问题在于，它能保证手机不被卖给多个人，但是保证不了手机一定能卖出去。比如3个节点收到的第一个请求分别来自不同的客户端，此时任何一个客户端都无法收集到足够数量的OK。
此外的矛盾之处在于：一方面，节点应该避免先后被多次写入来确保手机不被卖给多人；另一方面，节点又需要能“擦除”已经写入的数据来使得手机最终一定能被卖出。
不难发现，能被安全擦除的值，一定是没有成功写入大多数节点的，一旦写入了大多数节点，客户端就认为写入成功，如果再允许其他客户端写入成功，手机也就被卖给多个人了。
在多写模式下，不存在Master那样的特殊节点，最后手机卖给谁了，不取决于某一个节点，而是由集群中的大多数节点决定。
多写模式下应该如何去读取数据，DynamoDB和Cassandra所用的WRN模型给出了一个思路。所谓WRN，是指有N个节点的集群，写入时同时写入W个节点，读取时查询R个节点，当保证W+R>N时，同样根据“鸽巢原理”，我们能知道W和R一定至少有一个公共节点，因此先写入的值一定会被后面的读取“看到”。
大家都知道，DynamoDB和Cassandra都是最终一致性的。它们的弱一致性，主要体现在写入进行的过程中进行多次读取，可能有时能读到写入的数据，有时又读不到，根据读取所查询的节点不同而得到不同的结果。
此外，写入成功的值一定会被读到，不意味着读到的值一定写入成功或将要写入成功。假设客户端只写入了一个节点就故障了，数据仍然可能被其他客户端读取到。
WRN还给了我们一点提示，想要集群节点的两个子集有公共节点，不一定要取两个大多数节点，只需要加起一起数量大于N就行了。从高可用的角度来看，W和R分别取刚好超过一半节点通常是一个好选择，因为这样可以容忍最多不超过一半的节点故障。当然了，假如业务只关心写入请求的高可用，完全可以让W=1,R=N，此时只要连上一个节点就能写入，但是不同节点可能写入不同的值，需要在读的时候处理冲突，这就是典型的CAP理论中牺牲C来换取A了。
基于此我们有了改进思路：服务器端总是允许用新值覆盖旧值；客户端使用一种两阶段的流程，在写入之前先进行一轮读取，如果发现已经有值被写入了大多数节点，就说明手机已经被卖出去了，否则可以尝试写入新值。
很显然，与WRN类似，这个方案也有并发问题。当client2发起读取时，client1的写入还没有开始或者进行到一半，此时client2认为没有旧值被成功写入，于是发起写入，而在client2写入成功之前，client1也写入成功了，这样，手机又被卖给了两个人。
这个方案不能成功的原因是，第一阶段的读取的结果不能保持到第二阶段的写入，写入请求到达服务器时，前置条件已经不成立了。
一种可能的改进方法是使用某种锁机制，第一阶段读取时，把读过的节点上锁，第二阶段写入时再解锁。只是这么做的副作用也很显然，一旦上完锁之后客户端崩溃，或者与某些节点的网络断开，某些节点将没有机会被解锁。
我们要做的是把这个锁换成一种“活锁”。
在现实生活中有一个活锁的例子，就是拍卖。拍卖的时候，报价是不断上涨的，每当竞拍人给出一个报价时，之前所有更低的报价就失效了，同时产生了一个交易确认窗口期，如果没有人出更高报价，交易就会被确认。
Paxos的工作方式是类似的。每个客户端可以不断生成递增且互不重复的proposal id，写入分为读写两阶段，分别叫_prepare_和_accept_，如果两个阶段之间没有被更大的proposal id打断，写入就能成功。
Paxos把我们之前描述的抢手机的问题抽象为“多个节点共同确认一个值”的问题，把我们的服务器节点叫acceptor，客户端叫proposer，当一个proposer把值写入超过半数的acceptor后，这个值就被确认了。
Paxos的工作过程是，在读取阶段，需要写入数据的proposer向所有acceptor发送自己的proposal id，acceptor保证一旦返回自己的状态，便不再接受proposal id更小的请求了。
我们尝试站在proposer的视角，来推断其收到大多数acceptor回复后，可能遇到的3种情况：
在第二阶段，proposer把待写入的新值或旧值放在accept消息中发给所有的acceptor，再一次，当收到大多acceptor的返回消息后，该值就被确定了。如果在两个阶段之间插入了proposal id更大的prepare消息，写入将不会成功。这时proposer需要选择更大的proposal id并再次尝试两阶段写入。
这就是Paxos的基本过程了，其实是很容易理解的。
它能保证一致性的关键之处在于，两个阶段都要求得到大多数节点的确认，对于任意两个有潜在冲突可能的二阶段过程，我们假设proposal id较小的是X，另一个是Y。在X的accept阶段与之交互的acceptor集合和在Y的prepare阶段与之交互的acceptor集合，一定至少有一个公共节点，如果这个节点先收到X的accept，那么Y的prepare将会读到X所写入的值，反之如果这个节点先收到Y的prepare，那么X的accept一定不会成功。
考虑高可用和容灾能力的话，两个阶段都只需要大多数节点参与，因此Paxos能半数以下的节点故障或数据丢失。
之前我们介绍了，半同步复制模式还可以进一步优化，接下来就给出一个能真正解决问题的方案。
为了阐明Raft与Paxos之间的内在联系，这里我们引入一个简化版本的Raft算法，即只确定一个值的Raft，不妨叫Naive Raft。为了配合Raft中的术语，接下来我们把半同步复制中的Master改叫Leader，Slave改叫Follower。
回顾半同步复制不可行的场景，是在节点多次隔离或故障之后，剩余节点上存储的是不同的数据，无法判断谁的数据可能被确定了，也就无法决定谁去覆盖谁。
解决的方法也很简单，就是仿照Paxos，给不同的value定一个偏序的覆盖关系。由于半同步复制模型中，value总是由leader写入的，说白了就是要给不同的leader定一个覆盖顺序。
具体做法是这样的。每个节点存储一个整数term，表示选举轮次，初始时term都为0。当follower发现leader心跳超时，则会递增自己的term，并互相发消息投票选新leader。投票的限制条件是：
Naive Raft能保证一致性的关键，同样在于两个大多数节点集合有交集。其一是leader选举时所有给leader投票的节点集合，一个是数据复制是所有参与同步数据的节点集合。这二者有交集，意味着如果上一任leader确认了一个值，这个值必然会出现在下一任leader上，反之如果某一任leader选出时，节点上不存在一个value，那么上一任leader的数据复制将一定不能成功。
与Paxos类似，也是半数以上节点在线就能提供服务。
不难发现，这两个算法有很大程度上的相似性。比如Paxos中“只响应proposal id更大的请求”和Raft中“只给大于本地term的节点投票”，比如Paxos中“选择proposal id最大的数据写入”和Raft中“选择term最大的节点当leader”，比如二者都利用了大多数节点子集相交的性质……
这两者的对应关系是这样的。Raft的term和Paxos的proposal id本质上是一个东西，Raft leader选举等效于Paxos的prepare，Raft leader相当于完成了第一阶段prepare的Paxos proposer，Raft的数据复制对应于Paxos的第二阶段accept。
其中最不明显的对应关系是Raft leader选举和Paxos的prepare。Paxos的prepare阶段通过收集大多数acceptor的状态，来判断是否可能有value已经被确定，如果有则该value一定会接下来被accept。在Raft中，leader选举本质上也是一个读取过程，通过数据交换来判断是否可能有value在更小的term被确定，如果有则保证该value一定出现在下一任leader上。
另外，Paxos的第一阶段跟要写入的value是没有任何关系的，所以理论上prepare完全可以像Raft一样提前做了，等什么时候要写入的值来了，再做第二阶段。当然实际上不可行，因为多个proposer会互相覆盖，可以找一个proposer做完prepare，再不断给其他proposer发心跳阻止被覆盖，如此一来就更像Raft了。
还有一点，在我们的Native Raft中，第一任leader一开始就可以直接写入的，不需要第一阶段选举（注意真正的Raft不是这样，因为不在初始配置区分Leader/Follower，启动时也是需要选举的）。这是因为term 0是初始化配置，不可能有比term 0更早的写入，因此可以省掉第一阶段。同理在Paxos中，假如我们规定proposal id最小是0，那么对应proposal id为0的proposer也不用走第一阶段，直接写入就行。
不管是Paxos还是Raft，反复出现的一个要素是“大多数节点”，也就是所谓Quorum。Quorum的最重要的一个性质就是所有节点的两个Quorum一定至少有一个交集，共识算法就是在一个节点随时会挂或重启的极端不稳定的环境中，构建出这样一个稳定的交集来保证一致性。
实际上，关于Quorum的一切结论都来源于“两个Quorum必相交”这个性质。其实，“大多数”并不是Quorum的本质，“相交”才是。具体来说，共识算法两阶段所涉及的节点集合，必须要有交集。
基于这个认知，我们可以设置很多种不同的Quorum方案来适应不同场景，这里试举几例。
第一种是加权重。Quorum设置为Majority的一个重要理由是使得集群能承受最多数量的节点故障，不过假如因为某种原因节点故障的概率是不同的，我们就可以给节点赋予不同的权重，越是稳定的节点权重越大，Quorum则定义成超过总权重的一半，这么做同样可以保证相交。
第二种是考虑地理拓扑结构。比如6个节点分布在3个数据中心，如果使用Majority数据必须要复制到4个节点，需要跨数据中心。我们可以将两阶段的Quorum分别定义成“每个中心的至少一个节点”和“某个中心的全部节点”，也就是读取阶段必须读完每个中心，写入阶段必须写完单个中心的全部节点，写入时不用跨数据中心。
还有一种更泛化的方式是把所有节点放进一个矩阵，然后第一阶段要求完成任意一行，第二阶段要求完成任意一列。比如9个节点，按常规方法两阶段都需要完成5个节点，如果放入3x3的矩阵，那么两个阶段都是最少完成3节点就够了。
到目前为止，我们都只卖一台手机，也就是算法只用来确定一个值。实际场景中往往需要的是确定一系列的值，比如我们可能要卖100台手机。
最简单的做法就是同时运行100个Paxos实例，每个实例只卖一台手机。不过这也不符合现实场景的需要，比如100台手机一起卖，无法判断E码是不是被重复使用了。更常见的做法是顺序地依次运行100次，最后被确定的是一个连续的日志队列，记录每个手机的卖出记录。
如何保证“顺序依次运行”呢？我们可以把100台手机想象成100个待确定的“坑”，当proposer在尝试写入一条记录之前，需要找到第一个空闲的坑，并把这个坑之前待确认的坑都给确认了。
类似Basic Paxos，proposer准备写入一个value时，先生成proposal id放在prepare消息发送给所有acceptor，每个accetpor把自己本地100个坑位的情况回复给proposer。
当proposer收到大多数acceptor的回复后，假如此时收到的回复中，有数据的最大的坑位编号是i，则我们应该把数据写入i+1号坑位。不过，此时i号坑位可能并没有被确认（除非所有acceptor返回的i号坑位的状态是一样的），我们需要先用Basic Paxos的方法把i号确认了（也就是挑选其中proposal id最大的，发送accept并确保收到大多数accepter回复的OK），然后再次使用Basic Paxos的方法把自己的数据填入i+1号坑位。
有一点需要说明一下，待确认的坑位最多只可能有最大的那一个，因为按照流程如果i之前有未被确认的坑位，i这个位置根本不可能有数据。
接下来我们来看一下Multi-Paxos一个十分关键的优化。前面介绍，在写入一条记录时，可能需要两次Paxos过程，一次用来确认潜在的未完成的最后一条记录，一次用来写入新记录。实际上，第二次Paxos过程不用做全套，只用做第二阶段就行了。
怎么做到呢？我们先对proposal id做点小手脚，把proposal id改成递增的proposal id和坑位号的组合，即<proposal_id, index>，比较大小的时候先比较proposal id，再比较index，这样确认完i号坑，准备写i+1号坑时，就不用递增proposal id了，因为index加了1，起到了组合变大的效果。此时如果另一个proposer发过来更大的proposal id，仍然可以打断当前proposer，即<100,0>大于<99,42>。
接下来我们思考一下，第二轮Paxos里prepare阶段的目的是什么？是为了确保没有更小的proposal id可能确认i+1号坑位，而我们在accept第i号坑位时，已经成功地保证了这一点。（因为我们知道大多数acceptor已经不再接受小于<proposal_id, i+1>的请求了）。
同样的道理，这个proposer写完i+1号坑之后，可以继续直接accept i+2号坑位，i+3号坑位……直到其他proposer生成出更大的proposal id将其打断。
因此，在Multi-Paxos中，只要保证同一时刻只有一个proposer，就能做到一次prepare，然后不断进行accept，宏观上来看，写入一个值平均只需要一个阶段。至于如何保证同一时刻只有一个proposer，可以使用类似raft的心跳机制，只要当前工作的proposer能不断发出心跳，其他proposer就不会尝试写入数据。
Multi-Paxos还有一个优化是pipeline。经过前面的优化，虽然每次写入只需要一阶段RPC，但是连续的写入中完全串行的，前一轮发送accept，收集到多数回复OK确认后，下一轮才开始，即流程是“写入index1 -> 确认index1 -> 写入index2 -> 确认index2”，pipeline的过程就是前一条日志确认之前就开始下一条，即流程变成“写入index1 -> 写入index2 -> 确认index1 -> 确认index2”。
不过pipeline时要求两条日志是没什么关系的，如果后面的操作依赖前面完成后的结果，就不行了。而且，下一任proposer写入之前，待确认的日志可能就不止最后一条了，处理起来麻烦一些，这里就不展开了。
最后为了不标题党简单讲一下Raft。个人觉得Raft其实并不比Paxos容易理解，但是肯定比Paxos要易于实现，大体上可以认为Raft就是工程化之后的Multi-Paxos，二者类似图灵机和冯诺尹曼机的关系。
为啥Paxos不好实现呢？Google Chubby论文里也讲了很多了，主要原因就是Paxos本来就是偏理论的，没太考虑实现上的事情，更倾向于怎么让它更好证明。举个例子，Basic Paxos中第一阶段发出的proposal id如果过小，acceptor会直接抛弃消息，proposer在超时后增加proposal id并重试，当然此时可能还是过小。从工程化的视角出发，为了避免不必要的重试，让acceptor返回自己见过的最大proposal id显然是个好主意。而Paxos不这么干的原因也很简单：反正发消息也可能会丢失，而且不论怎样最终总能递增到一个合适的值，本质上是没有区别的。
Raft的重要特色就是工程化。这不仅在于其算法本身考虑到了很多实现层面的现实问题，例如节点长时间断连后如何快速追上进度，还在于它在达成共识日志的基础上实现了更为实用的复制状态机，并提供了几乎等同于伪代码程度的数据结构及算法描述。
我们还是把注意力聚焦在Raft算法如何生成达成共识的日志队列（Raft Log）。算法核心主要分成两个部分，Leader Election和Log Replication。
Raft节点在初始化时不指定角色，而是通过投票选举选出Leader，与Naive Raft类似，节点只会给term更大且含有更多日志的节点投票。因此，Leader Election也隐含了读取数据的过程，体现就是leader一定会出现在包含有最新已确认的日志的节点上。与之相比，Multi-Paxos的leader则没有这个限制，选leader只是为了减少冲突，不影响正确性。
在Log Replication阶段，Leader先把要追加的数据写入本地，然后再通过RPC同步给所有Follower，当收到大多数Follower的回复后，数据就写入成功了。与Multi-Paxos类似，只要不发生leader切换，整体上写入都是一阶段的。
相比于Multi-Paxos最大的差异是，Raft保证在每个节点上，如果第i个坑位的值是被确认的，那么第i个坑位之前的所有坑位就一定都是被确认的。也就是说，不用为每个坑位单独维护状态了，并且节点间通信的消息也简化了，大多数情况下只需要关心最后一个坑位。
有一种常见的质疑是说这个优化使得Raft无法“并行提交”。比如3个节点，写第一条记录时一个follower卡了一下，写第二条记录时另一个follower也卡住了，此时leader需要等其中一个follower把两条记录都补上，才能继续推进。而在Multi-Paxos中，是可以允许日志出现空洞的，即某一个follower可以把第一条记录先空着，直接确认第二条记录。不过，支持并行提交带来的优势是否值得为此付出的复杂度代价，也是个问题。况且，现实业务往往需要拿到全部日志再做决定，就说卖手机吧，如果之前的日志有空洞，就没法判断当前这个人是不是已经买过手机了。
Raft有个细节很多人都不理解，就是Raft中新leader选出来后，需要写一条空记录。实际上对照Multi-Paxos就清楚了，这无非就是Multi-Paxos中写入之前确认最后一条记录的过程嘛，只不过Multi-Paxos中是使用当前的proposal id去写旧值，在Raft里面，旧日志的Term无法改成新的，所以就用新Term提交一条空日志，这样顺带就把旧日志一并提交了。
本文就到此为止了，还有更多高级主题，比如config change什么的因为我也不懂就打住不讲了。啥时候搞懂了可以再写写，嘿嘿嘿。
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。