Paxos Consensus Algorithm

Table of Contents

1 拜占庭将军问题(Byzantine Generals Problem)

在了解分布式一致性算法前,先来认识一下由Leslie Lamport于1982年提出的分布式系统中的著名问题——拜占庭将军问题(Byzantine Generals Problem)。

拜占庭位于现在的土耳其的伊斯坦布尔,是东罗马帝国的首都。由于当时拜占庭罗马帝国国土辽阔,为了防御目的,因此每个军队都分隔很远,将军与将军之间只能靠信差传消息。在战争的时候,拜占庭军队内所有将军必需达成一致的共识,决定是否有赢的机会才去攻打敌人的阵营。但是,在军队内有可能存有叛徒和敌军的间谍,左右将军们的决定,扰乱整体军队的秩序,在进行共识时,结果并不代表大多数人的意见。这时候,在已知有成员不可靠的情况下,其余忠诚的将军在不受叛徒或间谍的影响下如何达成一致的协议,拜占庭问题就此形成。 拜占庭将军问题是对现实世界的模型化,由于硬件错误、网络拥塞或断开以及遭到恶意攻击,计算机和网络可能出现不可预料的行为。

通常,我们把 随意性故障称为拜占庭故障(Byzantine failure) ,这是最难处理的情况。

2 Paxos算法

Paxos算法是Lamport于1990年提出的基于消息交换的具有高度容错特性的分布式环境中的一致性算法。注:Paxos这个名字来源于Lamport在论文中虚构的一个岛屿名称。

2.1 问题描述

在分布式key-value存储系统中, 多个client可能同时对不同节点上的server进程提交修改请求,如何让所有server上key所关联的value值达成一致?

2.2 Paxos算法描述

Paxos算法把参与者分为下面几个角色:Proposer(提议者)、Acceptor(决策者)、Learner(最终决策学习者)。除此外,还有Client(产生议题者)。在具体实现中,往往每个server同时都是Proposer/Acceptor/Learner。

Proposer可以看作是Client的使者,Proposer带着Client的议题向Acceptor提议,让Acceptor来决策。经过两个过程(后文将介绍)后,如果有多数派个Acceptor最终接受了某议题,那么这个议题就被批准了。Learner学习被批准的议题。

Paxos算法描述如下:
第一个阶段:Prepare阶段。
(a) Proposer为议题选择一个编号 \(n\) (每个提议都有一个唯一的编号),去找Acceptor,想要它们初步接受(大多数Acceptor初步接受即可)。
(b) Acceptor收到议题后,检测编号 \(n\) ,如果 \(n\) 比当前Acceptor曾经“初步接受”过的议题的编号都要大,则“初步接受”这个编号为 \(n\) 的议题;反之,如果当前Acceptor曾经“初步接受”过比 \(n\) 大的议题,则拒绝这个编号为 \(n\) 的议题。也就是说,Acceptor能够保证,如果自己“初步接受”了编号为 \(n\) 的议题,则不会再“初步接受”编号比 \(n\) 小的议题。

第二个阶段:Accept阶段。
(a) 如果在第一个阶段,Proposer的议题得到了大多数Acceptor的初步接受。那么Proposer把这个议题的编号 \(n\) 和内容(比如“设置keyA的值为value1”)发送给Acceptor,想要它们“最终批准”(大多数Acceptor最终批准即可)。
(b) Acceptor收到Proposer发送的希望得到“最终批准”的编号为 \(n\) 的议题后,一般情况都会“最终批准”它,除非Acceptor曾经在第一个阶段“初步接受”过编号比 \(n\) 大的议题(比如它初步接受过编号为 \(n+1\) 的议题“设置keyA的值为value2”,这种情况下Acceptor会拒绝“最终批准”这个编号为 \(n\) 的议题“设置keyA的值为value1”)。

在第二个阶段中,如果大多数Acceptor最终批准了议题(如“设置keyA的值为value1”),则这个议题就被正式批准,可以被所有Learner学习。

用一句话简单描述就是:“Proposer提出议题,先争取大多数Acceptor的支持,超过一半支持时,则发送议题结果给所有Acceptor进行确认。” 其过程类似于 Two-phase commit protocol 。图 1 (摘自 Implementing Replicated Logs with Paxos)对Paxos总结得比较好。

paxos_basic_flow.png

Figure 1: Basic Paxos

参考:
Paxos Made Simple: http://research.microsoft.com/users/lamport/pubs/paxos-simple.pdf
Paxos Made Live - An Engineering Perspective: https://www.cs.utexas.edu/users/lorenzo/corsi/cs380d/papers/paper2-1.pdf
一步一步理解Paxos算法
MIT 6.824 Lab 3: Paxos-based Key/Value Service: http://nil.csail.mit.edu/6.824/2015/labs/lab-3.html
Distributed Systems - Concepts and Design, 5th Edition, 15.5.3 The Byzantine generals problem in a synchronous system
Distributed Systems - Concepts and Design, 5th Edition, 21.5.2 Chubby
Paxos算法细节详解(一)–通过现实世界描述算法:http://www.cnblogs.com/endsock/p/3480093.html
Distributed Systems: What is a simple explanation of the Paxos algorithm?: https://www.quora.com/Distributed-Systems-What-is-a-simple-explanation-of-the-Paxos-algorithm

2.2.1 没有错误发生时Paxos的消息交换过程

没有错误发生时Paxos的消息交换过程如图 2 (摘自Distributed Systems - Concepts and Design, 5th Edition, 21.5.2 Chubby)所示。

paxos_message_exchanges.jpg

Figure 2: Message exchanges in Paxos (in absence of failures)

2 中seq_number就是提议的编号,Promise表示“我承诺不会初步接受编号比 seq_number 小的议题”。

没有错误发生时Paxos的消息交换过程也可以表示为下面形式:

Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  |
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Prepare(1)
   |         |<---------X--X--X       |  |  Promise(1,{Va,Vb,Vc})
   |         X--------->|->|->|       |  |  Accept!(1,Vn)
   |         |<---------X--X--X------>|->|  Accepted(1,Vn)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |

Vn = highest of (Va,Vb,Vc)

2.2.2 有错误发生时Paxos达成一致的过程举例

下面内容摘自:Error cases in Basic Paxos (Wikipedia)
Message flow: Basic Paxos, failure of Acceptor

Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  |
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Prepare(1)
   |         |          |  |  !       |  |  !! FAIL !!
   |         |<---------X--X          |  |  Promise(1,{null,null})
   |         X--------->|->|          |  |  Accept!(1,V)
   |         |<---------X--X--------->|->|  Accepted(1,V)
   |<---------------------------------X--X  Response
   |         |          |  |          |  |

Message flow: Basic Paxos, failure of Proposer

Client  Proposer        Acceptor     Learner
   |      |             |  |  |       |  |
   X----->|             |  |  |       |  |  Request
   |      X------------>|->|->|       |  |  Prepare(1)
   |      |<------------X--X--X       |  |  Promise(1,{null, null, null})
   |      |             |  |  |       |  |
   |      |             |  |  |       |  |  !! Leader fails during broadcast !!
   |      X------------>|  |  |       |  |  Accept!(1,Va)
   |      !             |  |  |       |  |
   |         |          |  |  |       |  |  !! NEW LEADER !!
   |         X--------->|->|->|       |  |  Prepare(2)
   |         |<---------X--X--X       |  |  Promise(2,{null, null, null})
   |         X--------->|->|->|       |  |  Accept!(2,V)
   |         |<---------X--X--X------>|->|  Accepted(2,V)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |

3 Multi-Paxos

使用Paxos可以对一个值达成一致(比如keyA的值),如果系统中有很多值(比如还有keyB的值,keyC的值等等)需要达成一致,显然运行多个Paxos过程即可。不过,我们还可以使用Multi-Paxos对多个值达成一致。这里不介绍Multi-Paxos。


Author: cig01

Created: <2016-08-13 Sat 00:00>

Last updated: <2018-06-22 Fri 01:10>

Creator: Emacs 25.3.1 (Org mode 9.1.4)