再学Paxos算法

本文出自:【InTheWorld的博客】 （欢迎留言、交流）

Paxos算法应该是最著名的分布式一致性算法之一了。然而说起来令人汗颜，我对Paxos的算法的理解一直都是糊里糊涂的。国庆假期在看《SRE Google运维解密》，“分布式共识系统”(也就是Chubby)章节，也在强调Paxos算法。正好趁着这个机会，好好学习总结一下。

Paxos算法可以分为Basic Paxos和Multi-Paxos两种形式，它们的主要特点如下，为了对比起见，这里把它们列在一起了：

● Basic Paxos (“single decree”): 

• 一个或者多个服务器发起提议 
• 系统会在一个被选择的提议值上达成一致
• 只有一个提议值会被选择

● Multi-Paxos: 

• Multi-Paxos通过多回合的Basic Paxos算法在一列的值上形成一致，这一系列值相当于redo log，它的一致性等价于各服务器状态机的一致

当然他们的特点不止上面这些内容，更多的知识点还是要深入分析才能说明白。首先来看看Basic Paxos吧！

1. Basic Paxos

首先明确一下基本概念：

Proposal：提议 = 提议的值 + 提议编号；

Proposer：提议发起者；

Acceptor：提议接受者；

Learner：提议学习者；

这里先不管Learner，只研究Proposer和Acceptor相互作用的情况。

为了方便理解，我这里贴一张图，这幅图是Basic Paxos算法的流程图。

按照上图的流程顺序讨论一下Basic Paxos的过程；

1. 生成Proposal ID；生成proposal ID本身是有一些讲究的，Basic Paxos要求proposal ID是唯一的，并没有要求Proposal ID全局递增。但如果proposal ID本身是随机的UUID，它很大概率会在p1b阶段被acceptor否决掉。Basic Paxos是允许一个或者多个Proposer(s)的，而真正全局递增的id是有一定难度的，或者说如果实现了全局递增的id，那么Basic Paxos就只需要走accept流程了。所以一个比较现实的方式是使用近似递增且唯一的proposal ID生成方式。比如果使用maxRound + server ID的组合。这里的加号指的是高低位拼接，低位的server ID和本地递增的maxRound保证了唯一性。
2. 响应Prepare(n)；这里首先要做的是，必要时更新minProposal。此外根据minProposal和N的关系进行响应。这里有一些需要解释一下acceptors服务器中几个变量。其中minProposal就是该acceptor接收（不是接受哦）到的“最大Proposal ID“，这个minProposal的名称来自于一个ppt（见参考资料），应该是个笔误，但是不用在意名字，知道它的含义就好。acceptedProposal就是接受过的最大proposal ID。而acceptedValue就是接受过的最大proposal ID对应的值。当然，在Basic Paxos算法中，由于只有一个value最终会被选中，所以这里的“最大”其实意义不大。（这些值都是需要直接持久化的硬盘的，以保证故障之后可以恢复状态）。
3. 在响应Prepare(n)的另一种情况下，n <= minProposal。个人理解，n == minProposal的情况严格说来是不存在的。而n < minProposal的情况，acceptor需要否决掉这个Proposal，可以直接忽略掉这个提议。当然从优化角度讲，还是应该发送一个否决消息。
4. 在响应Prepare(n)的积极情况下(n > minProposal)，又有两种子情况。第一种是acceptor从来没有接受过提议，那么acceptedProposal和acceptedValue都是null；另一种情况是acceptor已经接受过Proposal，那么这两个值就不为空。这两种情况都是合理的，只是Promise()报文的内容不一样而已。
5. Proposer接收到多数机器的返回后，如果acceptedValue都是空的，那么就把自己想提议的值放进accept!()报文中；否者就要用最大Proposal ID对应的proposal value。这也印证了Basic Paxos只能在一个值上达成一致。

其他部分的过程，这里我就不再叙述了，微信团队有一篇比较细致的分享，链接我会附在blog后边，有兴趣可以看看。

2. Multi-Paxos

Basic Paxos只能在一个值上达成一致，这是很难满足实际应用场景的。所以我们需要Multi-Paxos算法，它可以实现在分布式系统在一系列值上达成一致。Multi-Paxos一般使用一个leader来统一发起Proposal，同时也只有leader可以发起Proposal。上半句其实并不严谨，因为Multi-Paxos实际上由两个状态组成，leader服务状态和leader选举状态。后一个状态这里我们先不探讨。

由于只有leader可以发起Proposal，所以在leader服务态，一切都会变得比较简单。简言之，Basic Paxos算法的prepare步骤变得不必要了，直接进入accept步骤。至于为什么Multi-Paxos可以在多个值上达成一致，看下面这个图就明白了。

这里的Accept!()报文和Accepted()报文都多了一个I，这个I就是值的序号。正如前文所说，这个W其实就是一条redo log，所有的redo log加一起，即可以在分布式系统实现状态机的一致。

熟悉或者了解Zookeeper的同学应该知道，ZXID的高位是Epoch ID，而低位就是一个递增的事务序号。这个ZXID其实和这里N和I的组合是差不多等价的。Multi-Paxos的其他内容，说实话我现在也还在学习中，这里就先打住了。

参考资料：

【1】http://www.infoq.com/cn/articles/wechat-paxosstore-paxos-algorithm-protocol

【2】https://ramcloud.stanford.edu/~ongaro/userstudy/paxos.pdf

【3】https://en.wikipedia.org/wiki/Paxos_(computer_science)