分布式协议Paxos学习笔记

分布式协议Paxos学习笔记

申明：本文大多数理解和部分图都是本人多standford关于Paxos的学习后，或是翻译或者整理，结合本人自己的理解写下的这篇文章。

最近几年分布式协议在数据库产品中飞速发展，各大公司都有基于特定场景相应的分布式数据产品出现，国内典型的包括腾讯的基于Paxos的PhxSQL，阿里的X-PaxosAliSQL，以及官方的Group Replication，还有percona 分支的基于Galera协议的PXC。因此，理解分布式协议尤其重要，深入的理解之后，才能知道它存在的适用场景，才能在合适的业务上充分发挥它的功能。

本文不讲解其他的分布式协议，包括zookeeper的ZAB协议，以及Paxos的简化版raft的协议，重在讲解分布式协议的始祖Paxos。文中对于Paxos的协议的理解，主要是结合本人在standford的视频课程中的一些学习心得，如果有错误的地方，还请批评指正

根据CAP协议，在设计系统时，我们知道CA，CP，AP我们只能选一样。当然，在大多数场景下，我们会选择AP（Available，Partition Tolerance ）。在MySQL Group Replication 问世以前，其实官方的版本也做不到强一致性。因为少了强一致性，因此给数据库产品带来了很多诟病。比如，master-slave之间数据有延迟，对于强一致性要求比较高的业务只能读master (比如支付业务部分场景)，虽然MySQL提供了semi-sync功能，但该功能也可能在出现网络问题，或者从库响应过慢等场景下降级为async。除了这些问题外，由于无法做到强一致性，很可能master发生故障是，导致数据还未同步到从库，从而导致数据永久丢失。

那么，paxos协议解决了上述哪些关键的问题：

Paxos协议在节点宕机恢复、消息无序或丢失、网络分化的场景下能保证决议的一致性。

首先，我们来对paxos进行一下分解：

Basic Paxos 可以简单的这么描述 :
1.一个或多个服务器可以同时发起提议（propose）。
2.系统必须同意一个被选中的值。
3.只有一个值被选中。

用一个美国竞选总统的案列来说明上述满足的条件。
1.一个或多个美国公民可以发起总统选举投票。
2. 投票委员会必须同意被选中的候选人当选总统。
3. 只能有一个候选人最终能被选中。

Basic Paxos需要满足的条件

Safety
1.只有一个值可能被选中。（不可能两个人同时在一次选举中被选为总统）。
2.服务器永远不会知道一个值被选中，除非它真的被选中（Proposer通过Accept返回值获得选中信息）。

Liveness
1.一些提议的值最终有一个会被选中 （某些提议的候选人中，最终会有一个当选为总统）。
2.如果一个值被选中，最终会被其他服务器知道 （如果一个候选人被当选为总统，美国公民最终会知道这个结果）。

也就是说，只有一个值被选中。而且这个值只有在被选中以后才能被其他服务器知晓。同时，被选中值的后必须是提议的候选值，一旦被选中，其他服务器最终会知道这个情况。

由此，我们看到，Paxos最终包含二个阶段：发起提议，接受提议值。这里，我们把发起提议的一方称之为 Proposers,把接受提议的一方称之为 Acceptors。

Proposers
1.主动：发起一个提议
2.处理来自用户的请求

Acceptors
1.被动：回应Proposers的请求
2.对Proposers的请求进行判定
3.存储被选中的值，存储决策过程的状态
4.希望知道哪个值被选中

我们首先来看看能否通过一次信息交互来完成提议被选中的情况：

red)的提议，又接受了S5(blue)的提议，产生了提议冲突的情况。如果通过一次信息交互，我们无法避免选中的值冲突的情况。
冲突2
S3先接受了S5(blue)的提议，又接受了S1(red)的提议。如果通过一次信息交互，我们无法避免选中的值冲突的情况。

从上述的分析我们可以看到，经过一次信息交互无法避免提议冲突的情况，这个集群中(S1,S2,S3,S4,S5)可能存在多个值被选中的情况。这违背了Paxos关于数据强一致性的要求(只有一个值被选中)。这样的集群在实际的生产环境中也没有太大的意义(在不同的数据库节点中，看到不一样的值)。因此，为了避免这种情况，需要多一次的信息交互来做提前检查，如果已经有数据被确定了，就不在更改。如果还没有值被选中，就使用当前的值作为选中的值。当然，这里存在提议冲突的情况的，如果提议出现了冲突，最后以哪个数据为准呢 ？我们可以通过版本来确定，每一个提议我们给一个版本号，当多个版本出现冲突时，我们可以选择一个大的版本号对应的提议，假设这里的版本号为编号。 我们可以为每个提议设定一个编号，同时编号满足：
1.每个提议都有一个唯一的编号
2.大编号的提议优先级比小编号的提议优先级更高
3.一个提议者可以选择一个新的提议编号，且新的提议编号比它曾见过或使用过的提议编号更大

我们可以这样来定义一个提议编号（Proposal Number):Round Number + Server Id。同时，每个服务器存储 maxRound : 到目前为止所见过的最大的 Round Number。Server Id在集群中每个机器上是唯一的，同时Round Number保持单调递增。这样，既保证了递增关系，同时也保证了每次提议编号唯一。

接下来我们定义如何产生一个新的 Proposal Number: Incr maxRound + Server Id。同时，我们要保证 maxRound 持久化到磁盘上，这样每次crash或者重启后，能保证 Proposal Number不会重复。

有了提议编号，我们继续看看Basic Paxos 如何通过两次交互解决上述冲突的问题 ：

1.Proposal 通过 RPCs广播提议编号。 【Prepare阶段】
1.找出被确定的值
2.阻止旧的，未完成的提议继续进行

2.Proposal 通过 RPCs广播进行进行数据存储。【Accept阶段】
1.请求 Acceptor接受特定的值