再学Paxos算法

= 1442

本文出自:【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算法的流程图。

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可以在多个值上达成一致,看下面这个图就明白了。

image

这里的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)

发表评论