程序员们的团建——戏说Paxos

小白也能看得懂的BASIC PAXOS协议

团建游戏

组里有一段时间没有去团建了,勤政作为组里的“生活委员”,出谋划策,打算选一个晴好的周末,带着大伙去放松放松。活动聚焦在户外真人CS或者喝啤酒吃小龙虾二选一。为了统一组内的意见,达成共识,勤政召集了组内的5位大佬(博文宏达松阳郭哥爱东)共商大计。

大佬头像

不巧的是,大佬们吵得不可开交,最终还是没能确定去哪里团建。大佬们的意见如下:

  • 博文:去户外真人CS,1 vs 10

Drawing

  • 爱东:吃小龙虾,每种口味来一遍

Drawing

  • 宏达、松阳、爱东:随意吧,要不楼上打一架,谁赢听谁的

Drawing

勤政作为团建的组织者,当然不能放任这种情况不管,于是乎,他想到了一个游戏,通过玩游戏的方式,让他们能够统一意见,大佬们纷纷赞同。

游戏约定

勤政对大佬们说,玩这个游戏,需要事先遵守一些约定,如果不能遵守,那就相当于弃权啦。约定如下:

  • 只要超过半数的人同意去户外CS或者同意去吃小龙虾,那么少数服从多数,剩下的人需要遵从多数人的意愿
  • 每个人都要诚实,不能相互欺骗。如不能对博文说去户外CS,对爱东说去吃小龙虾,否则游戏没法玩了
  • 在游戏的过程中,不论对方给的诱惑如何大,一旦确定意见以后就不能改了

大佬们默默点头,表示同意。

游戏规则

勤政继续道,游戏规则比较简单,主要两个阶段,

  1. 给自己拉票阶段,这一阶段的目的是争夺“发言权”,只有多数人同意听你“发言”,才能进入下一阶段;
  2. 确认阶段:大多数人听你发言以后,告诉他们具体的行动是啥,即确定去户外CS或者吃小龙虾。

博文:小意思,开始吧!

爱东:没问题,听明白了!

第一次游戏

在勤政的组织下,大佬们开始第一次游戏。

拉票阶段

精明的博文暗地里想,程序员都需要防秃生发,何不每人给他们来一瓶黑吕洗发水,让他们乖乖听我“发言”!于是抢占先机说道:听我的建议,我给你们每人一瓶黑吕洗发水,解决秃发烦恼!

game1_phase1_req

松阳和郭哥听了很高兴,免费拿新的洗发水,为什么不呢,况且之前也没答应过别人,于是爽快地答应了博文。

game1_phase1_ack

博文心里暗自高兴,没想到这么快就收买了松阳和郭哥,连我自己(我当然不会背叛自己啦),已经超过半数的人听我“发言”了,这时候可以进入第二阶段了!

确认阶段

博文见状,立马对松阳和郭哥说:按照之前的约定,我给你们每人一瓶黑吕,我们一起去户外CS吧!松阳和郭哥听了都表示同意,并在行程表上写下:得一瓶黑吕洗发水,去户外CS

game1_phase2

博文看到松阳和郭哥记录了行程表,高兴地对全组宣布:已经有超过半数的人确认去户外CS,按照游戏约定,咱们就定户外CS了!

Drawing

爱东:我还没参与呢,游戏就结束了!不公平,要求重新玩一次!

勤政:好好好,刚才算试玩,下一次一局定胜负!

第二次游戏

经历第一次游戏,双方心理都有了准备,意味着久经沙场的老铁们要使出浑身解数决胜负了!

博文拉票阶段

经过第一次试玩,博文心里早有了计划——抢占先机!于是,使出老套路:每人一瓶黑吕洗发水,争夺发言权。

game2_phase1_round1_req

松阳和郭哥依旧陶醉于“免费的午餐”,欣然同意了博文的要求。

game2_phase1_round1_ack

博文心里暗喜:情况和第一次游戏几乎一样,只要我抓紧时间进入确认阶段并取得松阳和郭哥的确认,那么便一锤定音了!

Drawing

爱东这时候来了个回马枪,打得博文措手不及!

爱东拉票阶段

吸取了第一次游戏的经验教训,爱东自然不肯放弃机会,在博文进入确认阶段之前,提高了“待遇”,试图笼络人心:向每人提供两瓶黑吕洗发水

game2_phase1_round2_req

之前宏达并没有上博文的车,原来这小子是在等更多的洗发水呢!宏达毫不犹豫地接受了爱东的邀请!

郭哥本来已经答应博文了,可是见到爱东提供了双倍的福利,情不自禁地调头上了爱东的车

game2_phase1_round2_ack

博文二次拉票阶段

博文竟然被郭哥拒绝了,感到不可思议,暗暗发誓一定要争取回来,否则CS计划无法实施!于是,在爱东还没有进入确认阶段前,对郭哥抛出了三瓶黑吕洗发水的“橄榄枝”!

game2_phase1_round3

为了公平对待,同时也避免别人被爱东“拐走”,博文把每个人的待遇都提高到了三瓶。

松阳听了当然很高兴,之前给一瓶就欣然接受了,给三瓶当然更好啦!

郭哥这时候犹豫了,心里暗想:当墙头草不好吧,不过谁给的多我就听谁的,才不管呢!于是礼貌地拒绝了爱东,果断对博文投怀送抱!

game2_phase1_round3_ack

博文确认阶段

聪明的博文看到拉拢回了郭哥的心,马不停蹄地进入确认阶段,他心里明白:只有进入确认阶段,才能把去户外CS这件事情确定下来。于是对松阳和郭哥说:按照约定,我给你们每人三瓶黑吕洗发水,我们去户外CS吧!

game2_phase2_round3

郭哥想:会不会有人给我四瓶黑吕洗发水把我拉拢过去,我要不要再等等呢?一旦接受了博文的确认,那么即便别人给我更多的洗发水,我也没法接受了。算了算了,先接受吧,谁知道未来会发生什么事呢!于是,郭哥同意了博文的确认请求,并在行程表上记录下:给三瓶黑吕洗发水,去户外CS。松阳也答应了博文并记录了一样的行程。

博文看到松阳和郭哥的行程表上已经更新了最新的记录,脸上露出了得意的表情,超过半数的人去户外CS,心里暗喜,他已经赢了第二局游戏。

爱东确认阶段

爱东此时还不知道博文已经向他们抛出了三瓶黑吕的橄榄枝,且已经确认完了。于是不慌不忙地对郭哥和宏达说:按照约定,我给你们每人两瓶黑吕洗发水,我们去吃小龙虾吧!

宏达:之前已经说好了,我没有改变主意,听你的。于是在行程表上写下:爱东给我两瓶黑吕洗发水,跟他去吃饭。

郭哥:爱东啊,不好意思!本来之前已经答应听你的,但由于博文给了我更丰厚的“福利”,我已经答应他去户外CS了,下次再和你去吃小龙虾吧!

game2_phase2_round2

只有宏达一人同意了爱东的确认,郭哥拒绝了,没有超过半数,表示爱东确认失败了。

爱东二次拉票阶段

尽管大家去户外CS玩的都很开心,但爱东对吃小龙虾念念不忘,为了尽快达成心愿,爱东豁出去了。之前从郭哥的口中了解到,博文已经把对他们的“福利”提高到了三瓶黑吕洗发水,爱东自然不能落后,并且还要提高“待遇”才能收服他们的心,于是给每人发四瓶黑吕洗发水

game2_phase1_round4

郭哥和宏达在沾沾自喜:竟然主动提高“福利”,受宠若惊啊。此时郭哥也跟爱东如实交代:我目前收到的最大“诱惑”是四瓶瓶黑吕洗发水,曾经在别人给我三瓶黑吕洗发水的时候,我同意一起去户外CS。宏达自然不用说了,“老相好了”,跟爱东吐露心声:目前收到的最大“诱惑”是四瓶黑吕洗发水,曾经在别人给我两瓶黑吕洗发水的时候,我同意一起去吃小龙虾。说到这里,郭哥和宏达早已跟爱东一起畅想吃小龙虾的快感。。

game2_phase1_round4_ack

爱东二次确认阶段

尽管有了郭哥和宏达的支持,但爱东意识到必须尽快确认行程,否则不知道又被哪个土豪把他们抢走了。于是爽快地发起二次确认:按照约定,我给你们每人四瓶黑吕洗发水,跟我去吃小龙虾吧!郭哥和宏达抑制不住内心的激动,欣然接受了邀请,并在行程表上更新:爱东答应给四瓶黑吕洗发水,一起去吃小龙虾。

game2_phase2_round4_ack

对郭哥和宏达的确认无误后,爱东自然也就放松起来。多数人达成了统一的意见,这下每种口味的小龙虾都可以尝一遍了。

Paxos简介

这个游戏的名字叫Paxos。

Paxos算法是莱斯利·兰伯特(英语:Leslie Lamport,LaTeX中的“La”)于1990年提出的一种基于消息传递且具有高度容错特性的一致性算法^1

分布式系统中的节点通信存在两种模型:共享内存(Shared memory)和消息传递(Messages passing)。基于消息传递通信模型的分布式系统,不可避免的会发生以下错误:进程可能会慢、被杀死或者重启,消息可能会延迟、丢失、重复,在基础 Paxos 场景中,先不考虑可能出现消息篡改即拜占庭错误的情况。Paxos 算法解决的问题是在一个可能发生上述异常的分布式系统中如何就某个值达成一致,保证不论发生以上任何异常,都不会破坏决议的一致性。

Paxos有几个重要的概念需要说明:

  • Proposer: 提议者,即写入数据的发起者,是发起Paxos算法的进程,Paxos角色之一。
  • Acceptor: 接受者,拥有接受/不接受提议的投票权,作用是存储节点,接受、处理和存储消息,Paxos角色之一。
  • Learner: 最终决策学习者,没有投票权,当接受者达成多数派意见后,学习Acceptor的意见,Paxos角色之一。(通常情况下,Proposer同时担任Learner一职)
  • Round(rnd): Proposer向Acceptor拉票和确认的一轮过程,分为两个阶段:拉票阶段(phase-1)和确认阶段(phase-2)。
  • Acceptor收到的最大rnd(last_rnd): Acceptor记住这个值来识别哪个Proposer可以写,Proposer发起写请求时,只接受和这个rnd相等的Proposer的请求。
  • Value(v):Acceptor接受的值,即要写入的数据。
  • Value Round Number(vrnd):Acceptor接受Value时候的rnd。

Paxos执行条件与约束

经典的Paxos算法是不考虑数据丢失以及消息被串改这两种情况的,即拜占庭将军问题^3

Paxos算法的执行具有一些约束条件,具体如下^4

  1. 一个Acceptor必须接受第一次接收到的value;
  2. 一旦一个value被确认,那么之后确认的提案必须具有该value
  3. 一旦一个value被确认,那么之后任何Acceptor再次接受提案必须具有该value
  4. 一旦一个value被确认,那么以后任何Proposer提出的提案必须具有该value。
  5. 如果一个编号为n的提案具有值value,那么存在一个多数派,要么他们中所有人都没有接受编号小于n的任何提案,要么他们已经接受的所有编号小于n的提案中编号最大的那个提案具有该value。

Paxos算法执行流程

Paxos算法主要分为三个阶段,但主要由前两个阶段来确认并通过一个提议:

  1. 第一阶段:Prepare阶段。Proposer生成一个提案n,向Acceptors广播Prepare(n)请求,Acceptors针对收到的Prepare(n)请求进行Promise承诺,此处并非所有的Acceptor都会回复。
  2. 第二阶段:Accept阶段。Proposer收到多数Acceptors承诺的Promise后,向Acceptors发出Propose请求,Acceptors针对收到的Propose请求进行Accept处理。
  3. 第三阶段:Learn阶段。Proposer在收到多数Acceptors的Accept之后,标志着本次Accept成功,决议形成,将形成的决议发送给所有Learners。

算法流程图可以用下图表示(图片引用自网络

paxos_procedure

游戏剧情回顾

让我们来看看,Paxos协议在游戏中是如何体现的。

游戏中的角色

游戏中的角色对应的Paxos协议中的什么概念呢?

  • Proposer:博文、爱东,他俩分别提出了去CS和去吃小龙虾的提议,即发起Paxos的进程
  • Acceptor:宏达、松阳、郭哥,他们对博文和爱东提出的提议进行投票,跟随并记录别人的意见。
  • Round(rnd):游戏轮数,1轮包含两个阶段:选举(phase-1)和确认(phase-2)。在游戏中用N瓶黑吕来记录轮次,在Paxos中是一个普通的数字n,单调递增,后写胜出,全局唯一
  • Last Round(last_rnd):Acceptor看到的最大rnd,如博文和爱东在拉票抢郭哥的过程中,郭哥看到的最大黑吕数是3
  • Value(v):写入的值,在游戏中是去CS或者吃饭
  • Value Round Number(vrnd):Acceptor接受CS或者吃饭的提议时对应的N瓶黑吕

第一次游戏

郭哥、松阳和宏达之前都没有接受过任何的提议,所以行程表上还是空空如也。下面将第一次游戏分为4个回合。

Proposer广播Prepare(1)

exp_game1_phase1_req

第一个回合,博文向松阳、郭哥和宏达提出每人给一瓶黑吕的提议(rnd=1黑吕),即Proposer向所有的Acceptors广播Prepare(1)

Acceptor回应Prepare(1)

exp_game1_phase1_ack

第二个回合,松阳和郭哥收到博文的请求后,由于他们之前没有接受过任何的提议,所以在回应博文时告诉他,现在能接受的提议是1黑吕(last_rnd=1黑吕),行程表上没有任何内容(v=随意,vrnd=0黑吕)。而一旦松阳和郭哥回应了博文并同意他的提议,那么任何小于或等于一瓶黑吕的提议他们便不再接受(此时last_rnd=1黑吕,只接受诱惑力更大的提议)^5

Proposer广播Accept(1, CS)

exp_game1_phase2_req

第三个回合,博文看到松阳和郭哥能够接受过提议时只需要1瓶黑吕,和自己的提议一致(rnd==last_rnd),于是博文给每人带了1瓶黑吕,并告诉他们提议就是去CS。在Paxos中,即广播Accept(rnd=1黑吕, v=CS)给所有的Acceptors

Acceptor回应Accept(1, CS)

exp_game1_phase2_ack

第四个回合,郭哥和松阳收到了博文的1瓶黑吕,由于目前没有其他人给他们更多的黑吕,所以他们愉快地接受了请求,并在行程表上记录当收到1瓶黑吕(vrnd=1黑吕)时,接受去CS(v=CS),随后分别将这条消息通知博文。博文收到郭哥和松阳的回应以后,这时候可以确定是去CS了(v=CS)

第二次游戏

第二次游戏情况比第一次复杂,下面来一一分析。

拉票阶段

exp_game2_phase1

第一个回合,博文向松阳、郭哥和宏达提出每人给一瓶黑吕的提议(rnd=1黑吕),即Proposer向所有的Acceptors广播Prepare(1)

第二个回合,松阳和郭哥收到博文的请求后,由于他们之前没有接受过任何的提议,所以在回应博文时告诉他,现在能接受的提议是1黑吕(last_rnd=1黑吕),行程表上没有任何内容(v=随意,vrnd=0黑吕)。而一旦松阳和郭哥回应了博文并同意他的提议,那么任何小于或等于一瓶黑吕的提议他们便不再接受(此时last_rnd=1黑吕,只接受诱惑力更大的提议)。

第三个回合,在博文向每个人发起确认前,爱东抢先向松阳、郭哥和宏达提出每人给两瓶黑吕的提议,即Proposer向所有的Acceptors广播Prepare(2)

第四个回合,郭哥收到爱东的请求,发现自己之前接受的最大提议是1瓶黑吕(last_rnd=1黑吕),且还没有在行程表上记录任何值(v=随意),而当前的提议是2黑吕(rnd=2黑吕),比之前的多,因此他接受了爱东的提议(last_rnd=2黑吕),并回应爱东行程表上的内容(v=随意,vrnd=0黑吕);而宏达之前没有接受过任何的提议,所以在回应爱东时告诉他,现在能接受的提议是2黑吕(last_rnd=2黑吕),行程表上没有任何内容(v=随意,vrnd=0黑吕)。

第五个回合,在爱东向每个人发起确认前,博文抢先向松阳、郭哥和宏达提出每人给三瓶黑吕的提议,即Proposer向所有的Acceptors广播Prepare(3)

第六个回合,松阳收到博文的请求,发现自己之前接受的最大提议是1瓶黑吕(last_rnd=1黑吕),且还没有在行程表上记录任何值(v=随意),而当前的提议是3黑吕(rnd=3黑吕),比之前的多(rnd>last_rnd),因此他接受了博文的提议(last_rnd=3黑吕),并回应博文行程表上的内容(v=随意,vrnd=0黑吕);郭哥收到爱东的请求,发现自己之前接受的最大提议是2瓶黑吕(last_rnd=2黑吕),且还没有在行程表上记录任何值(v=随意),而当前的提议是3黑吕(rnd=3黑吕),比之前的多,因此他接受了博文的提议(last_rnd=3黑吕),并回应博文行程表上的内容(v=随意,vrnd=0黑吕)

确认阶段

博文收到松阳和郭哥的回应以后,发现可以进入确认阶段了。

exp_game2_phase2

第一个回合,博文抢先爱东向所有人发起确认,博文向松阳、郭哥和宏达提出每人给三瓶黑吕,去CS的提议,即Proposer向所有的Acceptors广播Accept(rnd=3黑吕,v=CS)

第二个回合,松阳和郭哥收到博文的请求(rnd=3黑吕,v=CS),与自己能够接受的最大提议进行对比,发现满足要求(n>=last_rnd),于是在自己的行程表上写下接受3瓶黑吕(vrnd=3黑吕),去CS(v=CS),并把这个结果回应给博文,博文收到请求以后,博文去CS的计划就被确定下来了,他将这个计划发送给所有的Learners,这时候博文发起的Paxos进程就执行完了

第三个回合,爱东向每个人发起确认,提出每人给两瓶黑吕,去吃小龙虾的提议,即Proposer向所有的Acceptors广播Accept(rnd=2黑吕,v=小龙虾)

第四个回合,郭哥之前已经确认给3瓶黑吕去CS(vrnd=3黑吕,v=CS)了,接受的最大提议是3黑吕(last_rnd=3黑吕),因此不会再同意爱东的提议了,并将他能够接受的最大提议(last_rnd=3黑吕),以及之前接受过的提议(vrnd=3黑吕,v=CS)告诉爱东。而宏达收到爱东的请求,发现和自己接受的最大黑吕数一致,因此同意了爱东的请求,并在行程表上写下收到2瓶黑吕(vrnd=2黑吕)时,去吃小龙虾(v=小龙虾)

爱东收到了郭哥的拒绝,宏达的同意,而松阳可能联系不上没有回应,没有超过半数的人同意去吃小龙虾的提议,因此这轮游戏以失败告终,此时爱东仍然遵循游戏规则,在郭哥和宏达的回应中找到最大的提议值(last_rnd=3),遵循他的意见去CS(v=CS)

二次拉票和确认

爱东经历了之前的失败,为了尽快达成去吃小龙虾的提议,于是将“待遇”提高到了4瓶黑吕(rnd=4黑吕)。

exp_game3_phase1&2

第一个回合,爱东向松阳、郭哥和宏达提出每人给四瓶黑吕的提议(rnd=4黑吕),即Proposer向所有的Acceptors广播Prepare(4)

第二个回合,郭哥收到爱东的请求后,发现自己之前接受的最大提议是四瓶黑吕(last_rnd=3黑吕),行程表上有记录(vrnd=3黑吕,v=CS),而当前的提议是四瓶黑吕(rnd=4黑吕),比之前的多,因此他接受了爱东的提议(last_rnd=4黑吕),并回应爱东行程表上的内容。宏达收到爱东的请求,发现自己之前接受的最大提议是两瓶黑吕(last_rnd=2黑吕),行程表上有记录(vrnd=2黑吕,v=小龙虾),而当前的提议是四瓶黑吕(rnd=4黑吕),比之前的多,因此他接受了爱东的提议(last_rnd=4黑吕),并回应爱东行程表上的内容(vrnd=2黑吕,v=小龙虾)

第三个回合,爱东向每个人发起确认,提出每人给四瓶黑吕,去吃小龙虾的提议,即Proposer向所有的Acceptors广播Accept(rnd=4黑吕,v=小龙虾)

第四个回合,郭哥和宏达收到了爱东的4瓶黑吕,由于目前没有其他人给他们更多的黑吕,所以他们愉快地接受了请求,并在行程表上记录当收到4瓶黑吕(vrnd=4黑吕)时,接受去吃小龙虾(v=小龙虾),随后分别将这条消息通知爱东。爱东收到郭哥和宏达的回应以后,这时候可以确定是去吃小龙虾了(v=小龙虾)

Reference

  1. https://zh.wikipedia.org/wiki/Paxos%E7%AE%97%E6%B3%95
  2. https://zh.wikipedia.org/wiki/Quorum_(%E5%88%86%E5%B8%83%E5%BC%8F%E7%B3%BB%E7%BB%9F)
  3. https://zh.wikipedia.org/wiki/%E6%8B%9C%E5%8D%A0%E5%BA%AD%E5%B0%86%E5%86%9B%E9%97%AE%E9%A2%98
  4. https://www.jianshu.com/p/5e9aeb46540f
  5. https://zhuanlan.zhihu.com/p/31780743

全文完。