paxos协议

前边微服务框架选择中,反复看到一致性的协议,这一阶段就来对这些一些进行研究,包括:Paxos协议、Raft协议、Gossip协议,本文是这一系列第一篇:Paxos协议

概述

网上关于Paxos协议的介绍有很多,概览一番之后,觉得参差不齐、深浅不一,有些还相互矛盾,不看原论文估计是不行了,本文是Lamport2001年的Paxos Made Simple论文的摘要以及一点思考。

关于作者

本节是写raft时发现把作者的图片贴出来,一来表示尊敬,二来也挺有趣的.
Leslie_Lamport

问题

一致性要求

  • 一个值只有被提出来之后才可能被选中
  • 只有一个值被选中
  • 只有当一个值被选中后,process才能learn它

  • Only a value that has been proposed may be chosen

  • Only a single value is chosen, and
  • A process never learns that a value has been chosen unless it actually has been.

3种agent

  • proposers
  • acceptors
  • learners

一个进程可以扮演多个agent,agent与进程之间的映射关系,这里并不关注。

通信模型

使用异步、非拜占庭模型:

  • Agents 以随意的速度运行,它可能宕机、重启。由于在一个值被选中后,任意一个agents都可能宕机、重启,一个solution只有在某些信息被agent记住才可能有效
  • 消息传输可能不稳定、重复、丢失,但不会冲突

选择一个值

推导过程

  • P1: acceptor必须接收它收到的第一份议案
    => 当多个proposer同时提出自己的提案时,各acceptor各自接收自己value,而达不到多数胜出
    => 为了区分这些同时提出的议案,自然就需要对它们进行编号,这样一个议案就包括2个属性:编号number与值value
    => 当有多数acceptor接收一个议案时,这个议案才能被选中

  • P2: 如果值为v的议案被选中,那么所有被选中的更高编号的议案值都是v
    允许多个议案被选中,但必须保证所有被选中的议案有相同的number。

  • P2a: 如果值为v的议案被选中,那么所有被acceptor接收的更高编号的议案值都是v

  • P2b: 如果值为v的议案被选中,那么所有被proposer提出的更高编号的议案值都是v

  • P2c: 对于任意 v与n,如果一个值为v、编号为n的议案被提出,那么有一个由多数acceptors组成的集合S,使得(a)没有接收过编号小于n的议案,或者(b)v是被acceptors接收的编号小于n的议案中最高编号的议案对应的值

    => 为了维持P2c 不变,如果proposer想提出编号为n的议案,必须学习过上一个被大多数acceptor接收的议案。

    可以这样来思考,如果在值为v被选中,而这个v提出时议案的编号为m,在这个m后,proposer又提出了几个议案,一致到编号n(n>m),那么propser在[m+1, n]这几个议案的值都需要是v。proposer在提出这几个议案的时候,只需要参考上一个议案(如在提m+1时,参考m议案)的值即可。那这样会不会有问题?当然有,上一个议案如果发生变化怎么办?为了防止这种可能,就需要accptor做出承诺,上一个议案保证不变。怎么能保证不变呢?保证上次议案与本次议案之间不会再有新的插队议案就可以。

    这样一直在说的都是都是在m已经达成一致的情况,如何让在编号为m上达成一致?自然就需要进行一次投票,决定出m与v。

  • P1a 如果acceptor在prepare阶段没有响应过大于n的议案,那么它能够接收编号为n的议案。

PS:
=> 对于learner来说,目的是最后的value一致
=> 既然为了区分不同的议案,给它们做了编号,那么 1. 只要编号一致,就能保证value一致; 2. 如果编号不一致,那么只要保证不同编号的值是一致的
=> paxos本着少数服从多数的原则
=> 编号n的单调递增性对一致性的价值是什么?
在现实中,通过一起开会的方式(同步)对某个议案进行表决,最终少数服从多数得出一致性
但计算机没有同步的条件,只能通过异步的方式,单调递增是给异步定了一个方向。像极了时间的概念。

总结

  • Phase 1: Prepare
    (a)proposer选择一个编号n,然后发送prepare请求给大多数的acceptor,这个请求中只携带编号n(这时候没有value)
    (b) 当acceptor接收到prepare请求后,如果它没有响应过编号大于n的议案,那么它就回复给proposer一个承诺,表示不再接收编号小于n的议案,以及它接收过的上一个议案,(如果有的话),包括编号n与值v

  • Phase 2: Accept
    (a) 如果proposer接收到大多数acceptors的回复,那么它就给每一个acceptors发送一个accept请求,包括编号n与值v,v是所有回复中最高编号议案对应的值(如果有的话),或者是proposer选择的任意值(如果没有回复的话)。
    (b) acceptor如果没有响应过比n更高的议案,它就接收这个编号为n的议案

学习被选中的值

为了学习被选中的值,learner需要找到被选中的议案,最简单的方式是,每个acceptor选则一个议案后,都想每一个learner汇报自己的选择,但这样就会有 Number(learners) * Number(acceptors) 次通信。

由于假设了非拜占庭的模式,learner可以从另外一个learner中获取答案。这样只要找到一个杰出的learner,所有的acceptors都向它汇报自己的选择,然后这个杰出的learner再通知其他learner,这样通信的次数就减少到Number(learners) + Number(acceptors)。

也可以有多个杰出的learner,这样以更高一点的通信复杂度换取更高一点的可靠性。

由于信息丢失,以及acceptor宕机,可能让learner不知道议案是否被大多数acceptors选中,这样只有等到一个新的议案被选中时才能知道,当然learner也可以发起一个询问议案。

演变

想象一个有2个proposer交互持续提出议案的情景,proposer p以编号n1结束phase 1,另一个proposer q以编号n2(n2> n1)完成phase 1,这时候当p以n1提出phase 2时,它的议案就被忽略。然后p接着以n3(n3>n2)完成phase 1,而q以n2提出phase 2时,也遇到p相同的情况…,依次循环,这样就永远不会有值被选中。

这样就需要一个杰出的proposer,只有它可以提出议案,它可以与大多数acceptors通信,就可以保证提出更高编号的议案。

实现

假设有多个进程组成一个网络,每个进程扮演proposer,acceptor,learner的角色,算法选择出一个leader,扮演杰出的proposer与杰出的learner的角色。每个acceptor都应该有持久化存储,在发送响应前先存储一下。

剩下的就是如果保证两个议案不会有相同的编号,不同的proposer从独立的空间中选择编号,这样就可以保证。 每个proposer都记住自己提出的最高编号的议案,在开始新议案时,采用比它更大的编号。

状态机

实现分布式系统的一种简单方式是一组clients向中心server提交指令。当sever以一定的顺序执行指令时,它的状态就是确定的。这个状态机有一个当前的状态,执行每一个指令都会产生一个新的状态。比如银行系统的出纳是分布式系统的client,状态机包括所有账户的盈余。对于一个取钱指令,当账户余额大于取钱数的时,就会执行减少账户余额操作从而产生新的状态。
如果只用单一的中心server,当它宕机时,操作就会失败。所以引入多台sever,每个server都是一个状态机。因为它们状态是确定的,当执行相同的指令序列后,它们最后的结果是一致的。
为了保证所有机器执行相同序列的指令,我们实现一系列单独实例的Paxos一致算法,第i个实例选择的值就是指令序列中第i个指令。在所有的实例中,每一个server扮演所有的角色(proposer、acceptor、learner)。假定server的集合是固定的,那么在一致性算法的所有实例,使用的都是相同的agents。
通常,一个server被选成为leader,在所有一致性算法的实例中扮演杰出的proposer的角色。client向leader发送指令,leader决定每个指令的次序。如果leader决定某一个指令是第135号,它尝试使这个指令成为第135号一致性算法的实例。一般都会成功,也会由于错误或者另外一个觉得是leader的server提出一个不同的第135号指令而失败。但一致性算法保证了至多只有一个指令是第135号指令。