Raft/Paxos 类协议与分布式事务

作者： yifan 原文来源：https://tidb.net/blog/d2fa3088

Raft/Paxos 类协议与分布式事务都有两个阶段，很容易被人所混淆。实际上，这两者在使用中有关联，但场景却有所不同。大部分介绍材料，都过于学术化，描述过于复杂，让大多数人看了后似懂非懂，导致现实中很多同学对这两者本身，以及两者的区别，也一直处于似懂非懂的状态。本小文试图用最简单、最简短的语言，对这两者及区分进行说明。

一、Raft/Paxos 类协议

1. 原理：也可以称为一种算法，主要用于分布式节点之间关于某项决策保证一致性，决策的原则就是少数服从多数。跳过复杂乏味的算法过程描述，直接举例说明：

2. 举例：

3. 要解决的问题：

4. 一群朋友决定一起聚餐，互相见不了面，只能通过发短信交流，需要依少数服从多数的原则决策去哪个饭店。

本来如果这几个人都坐在一个屋子里，通过提议举手的方式，是很容易形成决策的（相当于是单机模式的一致性保证）。但现在是几个人见不了面，只能两两通信（相当于分布式），每个人都不能同时看到其它所有人的意见，但又不能把意见都给到同一个中心节点（这相当于又成了单机模式），在完全对等的模式下，难度是可想而知的。

 **Raft/Paxos解决方案** ：

Raft/Paxos 采用了分布式架构通用的两阶段方案。首先，需要区分提案者（提出饭店提议）与决策者（参与投票决策）的身份，并对人的角色依此划分，物理上一个人可以同时担任两个角色，但逻辑上是完全不同的两个独立角色。在本例中，假定所有人都是提案者，所有人都是决策者。假设共有 5 个人，编号为 1 号提案者，2 号提案者，3 号提案者，4 号提案者，5 号提案者；1 号决策者，2 号决策者，3 号决策者，4 号决策者，5 号决策者。大家注意，逻辑上应该将这 10 个角色当成 10 个不同的人。

首先是两阶段的第一阶段，称为提案权准备阶段。提案者通过向决策者发短信争取提案权，获得提案权的条件是得到多数同意。注意该阶段提案者只是争取提案权，并不向决策者发出具体的饭馆决策提议。提案者在该阶段发送的申请短信中包括一个按时间递增的顺序号，比如 1、2、3、4……，决策者只会接受比已接受 顺序号更大 的提案权申请。

现在，1 号提案者发出[t1, NULL]的提案权申请，5 个决策者中有 3 个收到了（假设是 1、2、3 号决策者），另外两个（4、5 号决策者）因为网络问题没收到，而这 3 个决策者之前还没有收到任何其它提案权申请，因此，3 个决策者向 1 号提案者发出接受其提案权申请的短信；

1 号提案者得到 3 个以上的同意提案权申请回复，根据规则，他可以进入第二阶段，发送饭馆提议的短信了；

在 1 号提案者发出序号为 t1 的提案权申请后不久，3 号提案者发出自己的提案权申请[t2, NULL]，即短信顺序号为 t2，5 个决策者中 2、3、4 号决策者收到了，1、5 号决策者信息丢失。其中 4 号决策者还没有收到任何提案权申请，于是向 3 号提案者发出接受其提案权申请的短信；2、3 号决策者已经有一个接受的提案权申请[t1, NULL]，但序号为 t1 比新序号 t2 小，因此，2，3 号决策者也向 3 号提案者发出接受其提案权申请的短信；

3 号提案者也得到 3 个以上的同意提案权申请回复，根据规则，他也可以进入第二阶段，发送饭馆提议的短信了。

现在进入第二阶段，称为提案决议阶段，该阶段第一阶段得到提案权的提案者向决策者发送具体的饭馆提议短信，在本例中是 1 号、3 号提案者。获得饭馆提议接受的条件也是得到多数同意；现在，决策者这次只接受 大于或者等于 已有提案权顺序号的短信提案。

1 号提案者现在开始发送饭馆提案短信，其中要带上一步同意了的提案顺序号 t1，如[t1, 烤串]，这次是确定向上一步与其达成一致的 1、2、3 号决策者发送；1 号决策者目前最近的提案权顺序号仍然是 t1，因此，它向 1 号提案者返同意吃烤串提议的短信；但 2、3 号决策者目前最新的提案权号是[t2，NULL]，t2 大于 t1，因此，2、3 号决策者拒绝 1 号提案者的饭馆提议；

1 号提案者只得到 1 个同意回复，没有超过半数，因此需要回到第一阶段，重新发送提案权申请；

在 1 号提案者重新发出提案权申请之前，3 号提案者向 2、3、4 号决策者（第一阶段达成同意的决策者）也发出了正式的饭馆提案短信，也带了上一步同意了的提案顺序号 t2，如[t2, 涮肉]；2、3、4 号决策者最新的提案权号正好都是 t2，因此，2、3、4 号决策者向 3 号提案者发出同意涮肉提议的短信；

现在，1 号提案者开始重新发送提案权申请了（回到了第一阶段），比如这次顺序号为 t3，即[t3，NULL]，假设这回 1、2、3、4 号决策者收到了短信，新的顺序号 t3 比他们拥有的最新提案权顺序号（1 号是 t1，2、3、4 号都是 t2）都大，因此，得到了这 4 个决策者的同意；不过这次，1、2、3、4 号决策者在返回信息中，还带上了他们已经在第二阶段接受了的饭馆信息，1 号决策者说我上次已经同意了你的“烤串”提议，等待新的指示，而 2、3、4 号决策者返回的是新的 t2 顺序号决策“涮肉”；

1 号提案者再次进入第二阶段，这次不同的是，在发送饭馆提议时，他会用达成同意的顺序号 t3，加上之前已由 3 号达成的“涮肉”饭馆提议，即[t3，涮肉]（这是 paxos 协议的另一个约定，后续提案者会尽量选择之前最新已经达成的饭馆提案，以保证最终高效达成一致），自然，1、2、3、4 号决策者都接受了这个提议，1 号提案者的饭馆提议也多数通过，还是涮肉；

这中间自然还会有 2 号、4 号、5 号提案者的参与，情况会更繁杂，但规则是完全一致的，如此往复循环，最终会实现半数以上就某个饭馆达成一致，一次决策完成。

如上，就是 Raft/Paxos 类算法的整个过程。

二、分布式事务

1. 原理：主要用于实现对存储于多个分布节点上的数据进行读写，要么全部完成，要么全部失败，即操作的原子性保证。还是直接举例说明：

2. 举例：

3. 要解决的问题：

4. 仍然是上面的例子，现在，大家 5 个同学吃完了涮肉，需要付账了，大家决定：AA 付帐。但大家的钱存在 5 个不同的账户节点上，需要从这 5 个分布账户一起扣款，很明显，必须一起成功，或者一起失败；

5. 分布式事务解决方案：

6. 与 Paxos 相似，分布式事务也是采用了两个阶段来解决问题，这次，假设饭馆老板是提交者，向 5 个账户发出同时扣款的事务，即：

begin transaction

扣 1

扣 2

扣 3

扣 4

扣 5

end transaction

首先是两阶段的第一阶段，称为准备阶段，提交者（饭馆老板）向 5 个账户先发出扣款申请，目的是获得扣款权，以在第二阶段真正进行扣款操作。

饭馆老板先问第 1 个账户：可不可以扣款。如果第 1 个账户上没有其它有冲突的扣款申请或者更新的提交已进行，则上锁，并回复可以，否则则重试、等待或回滚；

紧接着问第 2 个账户，第 3 个账户 ……；

直到所有帐户都同意扣款，则进入第二个阶段；

两阶段第二阶段：对每个节点进行扣款提交动作，即 commit。

如上描述只是一个大致的流程，实际操作中还有很多复杂的细节，例如：冲突的检查首先乐观与悲观事务是不同的，而写写冲突、读写冲突的判断也有不同；上锁的动作可以是两阶段之前就独占资源，也可以是在一阶段通过写入一个锁列实现；数据真正在哪个阶段写入？等等很多，本文不多进行赘述。

需要注意的是，第一阶段中，当账户节点回复可以扣款时，饭馆老板对该节点的资源应该具有一定的控制权，即拒绝其它扣款者申请。比如吃饭时，在旁边便利点买了饮料，便利点老板也要用 AA 制度，通过分布式事务进行扣款。但这一过程的实现，对乐观事务与悲观事务是不一样的。

在乐观事务中，并不独占账户节点资源，可以用一个本节点锁列的设计，根据事务提交的时间顺序判断是否有冲突：即是否有时间在我后面的申请进行中或已提交？有则表示冲突。有冲突的直接拒绝，没冲突的接受申请，该节点则可进入第二阶段；

而在悲观事务中，则是饭馆或者便利店老板提出申请时，开始两阶段之前需要检查或锁定账户节点资源：先检查有没有别人已经加锁（对不同的 DB Server，与乐观事务不同，要有一个共同的地方保存锁信息），有则等待，没有则加锁，防止其它人占用资源。

可以看出，乐观事务中，如果事务原来冲突就很多（即很多不同扣款者向同一个账户节点资源提出申请），拒绝重试就会很多，自然效率受到影响，比如金融业务，就需要用悲观事务；但如果冲突不多，乐观事务都会优势大，因为它不会锁资源，对不冲突的操作直接正常进行，只有冲突时，才会拒绝重试。

还有一个重要问题，就是全局时间 TSO 的机制，分布式协议很多步骤都需要依据时间先后判断，因此，大家必须有一个全局一致的时间标准，即 TSO，这一点，本文不多赘述。

三、关于分布式数据库中的 Paxos 与分布式事务

很明显，Paxos 与分布式事务有相似之处，但并不相同。而在分布式数据库中，分布式事务是用来保证跨节点事务原子性的，而 Paxos 协议则是保证数据多副本一致性的。

这里要理解到，即使没有多副本，分布式事务一样是需要的；即使没有分布式事务，多副本一致性也是需要的。因此这两者有关联，但各自处理场景不同。

而 Paxos 在分布式数据库中多副本一致性，保证的到底是什么呢？大多数人会认为主要是保证有多数副本节点写入成功，而实际上，更重要的，其实是为了保证大量并发写入，在各个节点上的写入顺序是一致的，即必须严格保证各个副本节点，关于并发操作的写入顺序一致，这一点是需要注意的。