Paxos 简易推导

paxos

声明:

  1. 本文思路完成模仿 朱一聪 老师的的 如何浅显易懂地解说 Paxos 而得,版权属于 朱一聪 老师 。只是为了自己理解更加透彻,又重新推导了一下而已。文章发出已经获得 朱一聪 老师的同意。
  2. 本文最后结论完全引用 Paxos Made Simple 中文翻译版
  3. 学习 paxos 请优先选择 Paxos Made SimplePaxos lecture,不要选择本文。本文仅能起到引导思路的作用
  4. 文章肯定有不严谨,推导不严谨的地方,欢迎讨论。

背景:

在一个高可用分布式存储系统中,如果只使用一台机器,只要这台机器故障,系统就会崩溃。所以肯定需要多台机器,但是由于网络延迟,机器崩溃等原因,多台机器对于数据很难达成共识(Consensus not Consistency)。而 paxos 协议就是用来使各个机器达成共识的协议。

如何理解共识(Consensus):

共识就是在一个或多个进程提议了一个值应当是什么后,使系统中所有进程对这个值达成一致意见。但是必须明确:在一个完全异步且可能出现任何故障的系统中,不存在一个算法可以确保达到共识(FLP Impossibility)。

前提:

需要保证安全性:

  1. 只有被提出的提案才能被选定
  2. 只能有一个值被选定
  3. 如果某个进程认为某个提案被选定了,那么这个提案必须是真的被选定的那个

可能出现的场景

  1. 进程之间的通信可能出现故障
  2. 每个进程都可能提出不同的值
  3. 每个进程也可能随时崩溃
  4. 进程之间传输的数据不会篡改

达成共识的条件

N 个进程中大多数(超过一半)进程都选定了同一个值

推导流程

假设存在三个进程 p1 p2 p3,共同决定 v 的值

1.1 每个进程只接受收到的第一个提案

场景 1.1.1

p1 proposal:v = a
p2 proposal: v = b
p3 proposal: 无

假设是 p1 的 proposal 优先到达 p3,p2 的 proposal 在到达 p3 时会被拒绝,系统就 v = a 达成了共识,反之如果 p2 的 proposal 优先到达,系统会就 v = b 达成共识。

场景 1.1.2

p1 proposal:v = a
p2 proposal: v = b
p3 proposal: v = c

这样每个机器只能接受自己机器上的 proposal,对于 v 的值就永远不能达成共识了。

结论 1.1:
  1. 进程必须能够多次改写 v 的值,否则可能永远达不成共识
  2. 进程必须接受第一个 proposal,否则可能永远达不成共识(系统只有一个提案时)

1.2 每个进程只接受 proposal_id 大的提案

根据 1.1 的结论,进程必须接受第一个 proposal, 所以需要一种拒绝策略或者修正后到达的 proposal 的 value 我们需要额外的信息作为依据来完成。

  1. 我们得到哪些信息呢?
    提出 proposal 进程的标识 process_id,当前进行到轮次 round_number(每个进程自增)
  2. 这些信息有什么用?
    这两个信息加在一起标识唯一的 proposal
    暂定 proposal_id = round_number + process_id
  3. 如何更新 proposal_id?
    每个 process 的 proposal_id = max(proposal_id, a_proposal_id)
场景 1.2.1

假设 p1_proposal_id > p2_proposal_id
p1 proposal:v = a
p2 proposal: v = b
p3 proposal: 无

如果 p1 proposal 先到达 p3 ,p2 后到达,会形成
p1 proposal:v = a
p2 proposal: v = a
p3 proposal: v = a
系统就 v = a 达成共识。

场景 1.2.2

如果 p2 proposal 先到达 p3 , p1 后到达,p3 会先接受 p2 proposal,形成
p1 proposal:v = a
p2 proposal: v = b
p3 proposal: v = b
系统就 v = b 达成共识,因为 p1 proposal 也已经发出,接着又会形成
p1 proposal:v = a
p2 proposal: v = a
p3 proposal: v = a
系统又就 v = a 达成了共识。
在这个策略中,有两个值先后达成共识,不满足安全性。

结论 1.2:

按照现有 1.2 策略存在proposal id 小 proposal 先到达,系统多次就不同的值达成共识的问题。从如下几个角度思考解决此问题

  1. p3 可以拒绝 p2 proposal(p2 proposal 先到达 p3,p2_proposal_id < p1_proposal_id )
  2. 限制 p1 提出的 proposal

1.3 p3 可以拒绝 p2 proposal 角度

  1. 发送带有 proposal_id PreProposal,
  2. 接收到 PreProposal 的进程,根据 proposal_id = max(proposal_id, accept_proposal_id) 进行更新
  3. 进程发送 proposal
  4. 每个进程只接受 proposal_id 大的 proposal

假设 p1_proposal_id > p2_proposal_id
p1 proposal:v = a
p2 proposal: v = b
p3 proposal: 无

场景 1.3.1
  1. p1_PreProposal 携带 p1_proposal_id 到达 p3
  2. P3 更新 p3_proposal_id 为 p1_proposal_id, P2 更新 p2_proposal_id 为 p1_proposal_id
  3. p2_PreProposal 携带 p2_proposal_id 到达,p2_proposal_id < p1_proposal_id,被拒绝。
  4. p1_proposal (v = a)到达 p2, p3
  5. 此时系统就 v = a 达成共识
    • p1: v = a
    • p2: v = a
    • p3: v = a
场景 1.3.2
  1. p2_PreProposal 携带 p2_proposal_id 进行广播,到达 p3
  2. P3 更新 p3_proposal_id 为 p2_proposal_id
  3. p2_proposal (v = b)到达 p3,系统此时会就 v = b 达成共识
    • p1: v = a
    • p2: v = b
    • p3: v = b
  4. p1_PreProposal 携带 p1_proposal_id 进行广播,到达 p2, p3, p2_proposal_id < p1_proposal_id,p2 p3 更新 proposal_id 为 p1_proposal_id
  5. p1_proposal (v = a)到达 p2, p3
  6. 此时系统就 v = a 达成共识
    • p1: v = a
    • p2: v = a
    • p3: v = a
结论 1.3:

1.3 策略解决了一部分问题,但是还是依赖消息到达的先后顺序。在某些条件下还是不能保证安全性。

1.4 限制 p1 提出的 proposal

现在已知 process_id round_number,还能得到哪些信息?
按照 1.3 的策略,我们只是更新了接受 pre_proposal 的 accept_process 的 proposal_id 为较大的 proposal_id,并没有回复给发送 pre_propoal 的 send_process 任何消息。是不是可以把 accept_process 已经获得的提案的 proposal_id 和 proposal 这样是不是限制 send_process 接下来发送的 proposal ?现在模拟一下流程,看看能否解决 1.3 中存在的问题。

  1. 发送带有 proposal_id 的 PreProposal
  2. 接收到 PreProposal 的进程,根据 proposal_id = max(proposal_id, accept_proposal_id) 进行更新,并回复当前进程已经接收到的 proposal_id
  3. 进程发送 proposal
  4. 每个进程只接受 proposal_id 大的 proposal
    假设 p1_proposal_id > p2_proposal_id
    p1 proposal:v = a
    p2 proposal: v = b
    p3 proposal: 无
场景 1.4.1
  1. p2_PreProposal 携带 p2_proposal_id 进行广播,到达 p3
  2. P3 更新 p3_proposal_id 为 p2_proposal_id
  3. P3 给 P2回复 (p2_proposal_id, v=NULL)
  4. p2_proposal (v = b)到达 p3,系统此时会就 v = b 达成共识
    • p1: v = a
    • p2: v = b
    • p3: v = b
  5. p1_PreProposal 携带 p1_proposal_id 进行广播,到达 p2, p3, p2_proposal_id < p1_proposal_id,p2 p3 更新 proposal_id 为 p1_proposal_id
  6. P3 回复 P1 (p2_proposal_id, v=b)
  7. P1 发现 P3 已经接受了 v = b,把自己的提案 v = a 修改成 v = b
  8. p1_proposal (v = b)到达 p2, p3
  9. 此时系统还是就 v = b 达成共识
    • p1: v = b
    • p2: v = b
    • p3: v = b
      问题得到了解决。
      上文所有的推导,全部来源于三个进程,看似问题已经解决。但是这个流程能否一般化,应用于 N 个进程呢?提案数从 2 到 N 呢?

泛化推导,

场景 1.5 进程数从 3 到 N

Pi 进程集合:提出 PreProposal-i,Proposal-i(v = a)
Qi 进程集合:接受了 Proposal-i 的超半数进程
Pj 进程集合:提出 PreProposal-j,Proposal-j(v = b)
Qj 进程集合:接受了 Proposal-j 的超半数进程
Pk 进程集合:Qi 和 Qj 的进程集合交集
只要 Pk 能够拒绝 Proposal-i 和 Proposal-j 的一个就是安全的

每个 Proposal-j-id < Proposal-i-id

  1. Proposal-j 到达部分进程,此时系统未达成共识
  2. PreProposal-i 到达部分进程,此时系统未达成共识
  3. 所有接收到 PreProposal-i 的进程回复(Proposal-j-id, v = b)或者 (NULL, NULL) 给 Pi
  4. Pi 接受到(Proposal-j-id,v = b),将 Proposal-i 原先的 v = a 修改成 v = b,然后进行广播。
  5. 系统就 v = b 达成共识。
场景 1.6 不同的 proposal 由 2 到 N

假设 j - i = N,b - a = N
Pi Pi+1 ... Pi+N-1 Pj 每个进程组都会提出 Proposal(v = a, a+1, .. a+N-1, b) Proposal_id 大小顺序相反
Qi -> Qj 与 Pi 相对
Pk 是收到了很多不同提案的进程的集合,但是一直没有达成共识。

  1. Proposal-i+1 Proposal-i+2 到达 Pk,系统并没有达成共识。
  2. PreProposal-j 发出到达部分进程
  3. 接收到 PreProposal-j 的进程选择 [(Proposal-i+1-id, v = a + 1), (Proposal-i+2-id, v = a + 2)] 其中的一个或者两个一起回复给 Pj
  4. Pj 应该选择哪个 v 值修改自己的 proposal 呢
    • 回顾前边的逻辑,每个进程会拒绝 Proposal-id 较小的提案,Proposal-i+1-id > Proposal-i+2-id
    • Proposal-i+1-id 相比 Proposal-i+2-id 的提案肯定先到 Pk 的,系统还有一部分进程没有接收到 (Proposal-i+1-id, v = a + 1),没有就 (Proposal-i+1-id, v = a + 1) 形成共识
    • 假设 Pj 选择 proposal_id 较小的 proposal ,那么会选择 (Proposal-i+2-id, v = a + 2) ,在 Pj 发出 (Proposal-j, v = a + 2) 之前,没有收到 (Proposal-i+1-id, v = a + 1) 的进程可能恰好收到了,系统就 v = a + 1 达成了共识。此后(Proposal-j, v = a + 2) 达到了, 系统又 v = a + 2 达成的共识。系统两次达成共识,存在问题。
    • 假设 Pj 选择 proposal_id 较大的 proposal,那么会选择 (Proposal-i+1-id, v = a + 1) ,在 Pj 发出 (Proposal-j, v = a + 1) 之前,没有收到 (Proposal-i+1-id, v = a + 1) 的进程可能恰好收到了,系统就 v = a + 1 达成了共识。此后(Proposal-j, v = a + 2) 达到了,还是 v = a + 1。不存在问题。
    • 系统选择 proposal_id 较大的修改依据
  5. Pj 选择 proposal_id 较大的 proposal,修改 v = a + 1,并发出 (Proposal-j, v = a + 2)
  6. 系统就 v = a + 2 达成共识

不能覆盖的场景

如果每次 proposal 被接受之前,先接受了携带较大 proposal-id 的 PreProposal,这样每次都会拒绝即将成功的达成共识的 proposal 系统每次都不会达成共识。这个场景可以通过不断重试解决。

paxos

Proposer: 发起提案的进程
Acceptor: 接受题提案的进程
一个进程可能充当多个角色

Phase 1:
  1. Proposer 选择一个提案编号 n,然后向 Acceptors 的某个 majority 集合的成员发送编号为 n 的prepare请求。
  2. 如果一个Acceptor收到一个编号为 n 的prepare请求,且 n 大于它已经响应的所有prepare请求的编号,那么它就会保证不会再通过(accept)任何编号小于 n 的提案,同时将它已经通过的最大编号的提案(如果存在的话)作为响应。
Phase 2
  1. 如果 Proposer 收到来自半数以上的 Acceptor 对于它的 prepare 请求(编号为 n)的响应,那么它就会发送一个针对编号为 n ,value 值为 v 的提案的 accept 请求给 Acceptors,在这里 v 是收到的响应中编号最大的提案的值,如果响应中不包含提案,那么它就是任意值。
  2. 如果 Acceptor 收到一个针对编号 n 的提案的accept请求,只要它还未对编号大于 n 的 prepare 请求作出响应,它就可以通过这个提案。

推荐阅读更多精彩内容

  • paxos通俗说就是 发起提案之前首先判断当前是否是最新的 如果不是 则把最新的值赋值 如果是则不用赋值即 ...
    时待吾阅读 700评论 0 0
  • 原文:Paxos Made Simple作者:Leslie Lamport时间:01 Nov 2001 1 Int...
    随安居士阅读 1,332评论 1 2
  • 问题: 基于消息传递通信模型的分布式系统,不可避免的会发生以下错误:进程可能会慢、被杀死或者重启,消息可能会延迟、...
    LaxChan阅读 1,780评论 6 1
  • Paxos是什么 Paxos算法是基于消息传递且具有高度容错特性的一致性算法,是目前公认的解决分布式一致性问题最有...
    jiangmo阅读 1,236评论 0 6
  • 这世界有多美好 用手电筒映照星空 宇宙传来呼叫 说我发出讯号 让我寻找 找寻宇宙的赤道
    鳳回阅读 128评论 0 1
  • 你猜。 理由一:避世不闭市 小隐隐于野,大隐隐于市。真正的隐士不是属于陶渊明、王维这些躲进山中一隅的人,而是那些和...
    WiFi密码是多少阅读 1,484评论 2 4
  • 爱情,是一个美好而又令人渴望的词语,每个人都需要爱情,然而我不知道是不是每个人都会和我一样,在爱情中失去自我。 有...
    自己努力阅读 123评论 0 0