Paxos协议(Paxos Protocol)

即使无法解决分布式系统异步通信中的共识问题,放弃Termination属性后我们仍可以找到实用的解决方案(Practical Solution),Paxos就是其中之一。

系统模型

  • 进程间通过消息通信
  • 消息是异步的:不限制传输延迟,但是在正确的进程间消息最终总能送达
  • 进程可以重启并恢复状态(restart and remember)


角色

Paxos协议中进程有三种基本的角色:

  1. Proposers 提议者
    提出一个想要达成共识的数值
  2. Acceptors 接收者
    选择达成共识的数值
  3. Learners 学习者
    学习Proposers与Acceptors已达成共识的数值

一个进程可以承担多个角色。


原理

Proposer试图获得大多数Acceptor的接受(acceptance by the majority of acceptors)。

大多数指一半以上,假如存在N个节点,则大多数为至少N/2+1个节点。这种方法最多可以忍受(N-1)/2个节点发生错误。

只有一个值可以被大多数节点接受,因此保证了Agreement性质。

只允许输入数据被提议,因此保证了Validity。

当提议多于两个时或进程崩溃时,无法保证Termination。
但是Paxos通过以下方式来减少Non-Termination情况的发生:

  • Proposer可以重新提议(by restart the protocol)
  • Acceptors可以从之前的接受结果中被释放(can be released from old acceptance)
  • 使用唯一的提议编号和Primary Proposer

提议编号:
每个提议都带有一个唯一的提议编号,且该编号是递增的。(distinct & increasing)
例如可以通过时间戳或者轮询。


算法

Paxos的算法分为两个阶段。

Phase 1: Preparation

Prepare

Proposer向所有或大多数节点发送prepare(n)消息。其中n是提议编号,注意该过程中没有发送提议值。

Promise

随后每个收到prepare(n)消息的Acceptor将新的提议编号n与其已经应答过的旧提议号N作比较。
当新的提议编号更大时,用ack(n, (nx, vx))响应新提议的Proposer,并把N改为n。

ack(新Proposer Number,(旧Proposer Number,已经Accept的值))

根据Acceptor之前是否接受过某些提议值可以将ack分为以下两种情况:

未接受过value:ack(n, -)
接受过:ack(n, (nx, vx))

也即,当节点接受过其他提议时,响应新提议的prepare请求时需要带上之前的提议编号和提议值。

若新的提议编号小于旧的,则Acceptor忽略或给出拒绝响应。

Phase 2: Accept

Propose

Proposer等待来自大多数Acceptor的ack消息:

  • 若ack消息包含值:
    • 若仅有一个ack(n, (nx, vx))包含值,其他为ack(n, -),则选择该vx值作为自己propose的数值,向Acceptor发送accpet(n, vx)
    • 若有多个ack(n, (nx, vx))包含了多个值,则从这些值中选择最大提议编号nx所对应的值vx作为propose的数值,发送accept(n, vx)
  • 若ack消息不包含值:则将自己的数值放入accept中,发送accept(n, own-value)

注意:Paxos中,如果一个值已经被选择了,则后续的提议只能提出这个值。
Once a value has been chosen, future proposals must propose the same value.

Accept

Acceptor收到accept请求,若此前没有带有更大提议编号的prepareaccpet消息到达,则Acceptor接受提议,更新提议编号和提议值。

An Acceptor accepts an accept message with proposal numbered n:
if and only if it

  • has not responded to a prepare massage with a number n’>n and
  • has not accepted an accept meessage with a number n’>n

否则不响应或给出拒绝响应。

Learning a chosen value

Learner需要找出被大多数Acceptor所接受的提议。

实现方法:

  • 每个Acceptor在接受一个提议之后都会给每个Learner发送消息
  • 当一个Learner从大多数Acceptor那里接收到了相同的消息时,它就知道哪个值应该被选择
  • 可以设计一类独特的Learner用于通知其他Learner选择哪个值


分布式系统的一致性属性(Consistency Properties)

目前还没有系统地学过分布式系统的课程,所以借用了Shrik3在博客上写的FCDS课程笔记。

分布式系统的一致性主要考虑两个方面:

  1. Safety (Correctness)
    安全性:系统能否给出想要的结果
  2. Liveness (Progress)
    活性:系统能否持续运行

课堂上Fetzer教授讲解了Safety,Liveness的问题在练习中由Fernandez讲解。所以下面根据这两方面来说明Paxos是如何实现一致性的。


Paxos协议的安全性(Why does it work?)

Validity

由于accept的消息包含的值总是来自Proposer自身或是Acceptor通过ack消息返回的,而ack返回的值也曾经来自一个accept消息,因此,被选择的值一定是被Proposer提出过的。

Agreement

假如Learner L1和L2分别学习了值v1和v2,则大多数节点接受了消息accept(n1, v1)和accpet(n2, v2)。

因此一定有Proposer P1和P2分别发送了这两个accept消息。

如果n1==n2,那么大多数Acceptor一定通过ack消息响应了P1和P2,这也就意味着P1=P2,因为每个提议号只能被ack一次且大多数是相互重叠的(majorities overlap)。

大多数相互重叠的意思是:一个固定的Acceptor集合只能存在一个Majority,因此只存在一个被大多数Acceptor响应的提议号。

所以我们可以假设n1<n2,那么P1从大多数Acceptor那里收到了ack(n1, v1′),P2从大多数那里收到了ack(n2, v2′);且P1至少成功向一个Acceptor A1发送了accept消息,才使得P2从A1那里获得了ack(n2, (nx, v1))且nx是ack消息中最大的提议号。
因为P1的accept(n1, v1)消息被大多数接受,这意味着之前没有其他带有更大提议号的Proposer得到过ack消息。所以下一个得到大多数Acceptor应答的Proposer Px将得到Acceptor返回的带有(n1, v1)的ack消息,而且会因此发送带有v1的accept消息,且从这时起以后所有的accept消息都带有v1。

这一部分是直接对教授所给的课件进行翻译得到的,个人感觉重点在最后一段:一方面,如果一个值被大多数Acceptor接受,说明他们之前没有收到过带有值的accept消息,且之前没有更大的提议号出现过(否则这个accept消息也不会被接受)。另一方面,在大多数Acceptor接受了一个值v1后,对其他更大提议号的Proposer应答时ack消息带有v1,则根据Phase 2中Accept消息发送给阶段的规则,这些Proposer只能发送accept(ny, v1),因此保证了大多数Acceptor都选择了同一个值。


竞争(Liveness)


当P1和P2两个Proposer依次增加提议编号n1和n2,但在accept消息到达前Acceptor就收到了另一方新的带有更大提议编号的prepare消息,此时会产生竞争(Race)情况,两个Proposer都无法正常地发送accept消息。

这样的情况威胁了系统的Liveness性质。

解决方法:

  • 分配优先级
    选择Primary Proposer
  • 选举
    当Primary Proposer缓慢/崩溃时,选举新的
  • bully id
  • 指数退避(exponential backoff)
    等待一个指数增加的随机时间后重发消息


一些问题

Q:Learner怎样知道哪个值被选择?如果从Acceptor获取数据丢失怎么处理(例如因为数据丢失导致选择两个数值的Acceptor数量一样)?
A:只有Proposer知道某个提案的值是否被选择,因为他们通过ack消息获得大多数Acceptor返回的值,并用这个值来更新自己的提议值。Learner可以向Proposer提议某个值,通过一轮Paxos来验证该值是否被选择。

Q:多个值的问题?
A:Multi-Paxos:把日志中的条目划分为多个基本Paxos问题,通过index参数来选择条目。教授没有提到Multi-Paxos问题,所以还没有深入学习,以后有机会可以补上。

参考内容

TUD Systems Engineering 1 – Consensus and Paxos
理解 Paxos(含伪代码)
Paxos lecture (Raft user study) by Diego Ongaro
Implementing Replicated Logs with Paxos (Slide)
[FCDS] correctness conditions of concurrent programs, 3 types of consistency

发表评论

您的电子邮箱地址不会被公开。