Paxos算法分析

发表于
字数统计 3.4k 字 | 阅读时长 12 分钟

追本溯源

Lamport在1990年提出了一个理论上的一致性解决方案，同时给出了严谨的数学证明。为描述 Paxos 算法，Lamport 虚拟了一个叫做 Paxos 的希腊小岛：岛上采用议会的形式来通过法令，议会中的议员通过信使进行消息的传递，而议员和信使都是兼职的，他们随时有可能离开议会厅，并且信使可能会重复的传递消息，也可能一去不复返，此处假设没有拜占庭将军问题（消息不会被篡改）。这样的环境下，通过议会协议仍然能保证有法令会被通过，并被所有议员所接受。

Paxos是什么

Paxos算法是一种基于消息传递且具有高度容错特性的一致性算法，Google的粗粒度锁服务Chubby的设计开发者Burrows曾经说过：“所有一致性协议本质上要么是Paxos要么是其变体”，在过去十年里，Paxos基本成为了分布式领域内一致性协议的代名词。Paxos的提出者Lamport也因其对分布式系统的杰出理论贡献获得了2013年图灵奖

Paxos解决什么

在常见的分布式系统中，总会发生诸如机器宕机或网络异常等情况，Paxos算法需要解决的问题就是如何在分布式环境中，快速且正确地在集群内部对某个数据的值达成一致，并且保证不论发生以上任何异常，都不会破坏整个系统的一致性

相关概念

角色

  • 提议者(proposer): 进行提议的角色，Proposer 可以有多个，Proposer 提出议案（value）。所谓 value，可以是任何操作，比如“设置某个变量的值为value”。不同的 Proposer 可以提出不同的 value，例如某个Proposer 提议“将变量 X 设置为 1”，另一个 Proposer 提议“将变量 X 设置为 2”，但对同一轮 Paxos过程，最多只有一个 value 被批准

  • 批准者(acceptor): 通过提议的角色，Acceptor 有 N 个，Proposer 提出的 value 必须获得超过半数(N/2+1)的 Acceptor批准后才能通过。Acceptor 之间完全对等独立。

注意：也就是说集群中7个最多挂掉3个，8个最多挂掉3个，确保存活数量大于挂掉的数量

  • 学习者(learner): 感知(learn)被选定的提议，上面提到只要超过半数accpetor通过即可获得通过，那么learner角色就会感知到被通过的提议

在具体的实现中，一个进程可能同时充当多种角色。比如一个进程可能既是Proposer又是Acceptor又是Learner

提案

最终要达成一致的value就在提案里（pid，value），Proposer可以提出（propose）提案；Acceptor可以接受（accept）提案；如果某个提案被选定（chosen），那么该提案里的value就被选定了

选定提案

在何种情况下不同的进程认为提案被选中了？

  • Proposer：只要Proposer发的提案被Acceptor接受，Proposer就认为该提案里的value被选定了
  • Acceptor：只要Acceptor接受了某个提案，Acceptor就认为该提案里的value被选定了
  • Learner：Acceptor告诉Learner哪个value被选定，Learner就认为那个value被选定

推导过程

这个一致性需要满足三个要求：

  • v达成一致时的值是由某个进程提出的。这是为了防止像这样的作弊方式：无论如何，最终都令每个进程的v为同一个预先设置好的值，例如都令v=2，那么这样的一致也太容易了，也没有任何实际意义。
  • 【重点】一旦v就某个值达成了一致，那么v不能对另一个值再次达成一致。这个要求称为安全性。
  • 一致总是能够达成，即v总会被决定为某个值。这是因为不想无休止的等待，这个要求也称为活性。

Paxos要求满足的前置假设只有一个：消息内容不会被篡改

进程必须能够多次改写v的值（在还没达成一致性时）。同时我们也要意识到：当进程收到第一个消息时，进程是没有任何理由拒绝这个消息的请求的

如果一个提案被大多数进程所接受，那么称提案被通过，此时显然v被决定为提案中的值。进程P记录的接受的提案ID记做a_proposal_id

核心原理

我们称超过半数的进程组成的集合为法定集合，两个法定集合必然存在非空交集，即至少有一个公共进程，称为法定集合性质。 例如A,B,C,D,F进程组成的全集，法定集合Q1包括进程A,B,C，Q2包括进程B,C,D，那么Q1和Q2的交集必然不在空，C就是Q1，Q2的公共进程

推导过程

1、三个进程的场景P1,P2,P3（n个进程的场景类似），P1尝试令v的值被决定为a,P2尝试令v被决定为b

为了满足安全性，需要拒绝策略：根据提案ID的大小来作为拒绝或接受的依据

假设P1的id大于P2的id

1.1、P3先收到P1的消息，通过拒绝策略，可以达到目的

1.2、P3先收到P2的消息，无法拒绝，会接受两次，无法满足安全性，因此从三个角度考虑

1.2.1、P3能够拒绝掉P2的提案：在接收到P2前，先收到P1的预提案，需要引入预提案,进程P在发送提案前，先广播一轮消息，消息附带着接下来要发送的提案的proposal_id，接收者收到后，根据a_proposal_id = max(proposal_id,a_proposal_id)保留较大的提案，但仍然依赖与预提案的接收顺序，因此问题仍然存在

1.2.2、P3能够拒绝掉P1的提案：不符合我们的拒绝策略

1.2.3、限制P1提出的提案中的值，如果P1的提案中的值与P2的提案一致，那么接受P1也不会破坏一致性：意味着P1在正式提出提案前，需要有途径能获悉P2的提案的值

目前的流程

  • 阶段一 提议者Proposer：向接受者Acceptor广播预提案，附带接下来提案Proposal的proposal_id 接受者Acceptor：收到预提案后更新a_proposal_id = max(proposal_id,a_proposal_id)

  • 阶段二 提议者Proposer：向接受者Acceptor广播提案，和之前的预提案共享同一个proposal_id 接受者Acceptor：如果收到的提案的proposal_id>= a.proposal_id，那么接受这个提案，更新a_proposal_id = max(proposal_id,a_proposal_id)

2、N个进程的场景，存在两个进程Pi,Pj，Pi尝试另v被决定为a,Pj尝试另v被决定为b，Pi提出的预提案记作PreProposal-i，提案记作Proposal-i；Pj的预提案PreProsal-j，提案Proposal-j

Pi的提案被通过代表了存在一个法定集合Q-i，Q-i中的进程都接受了Proposal-i，Pj同理，存在一个Q-j，Q-j中的进程都接受了Proposal-j。由于法定集合的性质，两个多数集Q-i和Q-j中必然存在一个公共进程Pk。Pk即相当于场景1中的P3，只要Pk能够拒绝Proposal-i和Proposal-j中的一个，协议依旧是安全的

2.2.3、由于拒绝策略失效，所以只能令Proposal-i.v = Proposal-j.v=b，首先需要主动询问进程集合，假设回复的是法定集合Q-i，同理法定集合Q-j收到了Proposal-j.v=b，因此存在一个Pk即接收到了Pj提案，也收到了Pi的预提案，而该场景的前提下，Pk是先收到Pj提案，因此记录了Proposal-j.v = b

假设存在CL策略，使得Pi轮训访问回复的集合K-i中选定的 Proposal-m.v = Proposal-j.v=b

假设其中有一个提案是Proposal-f.v != Proposal-j.v=b，则存在法定集合Q-f和法定集合Q-j的公共节点P-s，Ps即接受了PreProposal-f又接受了Proposal-j

假设 PreProposal-f.proposal_id > Proposal-j.proposal_id

2.2.3.1、Ps先收到PreProposal-f，因为拒绝策略，则会拒绝Proposal-j，与假设矛盾

2.2.3.2、Ps先收到Proposal-j，则PreProposal-f来了之后会把Proposal-j.v=b回复给Proposal-f，由于CL策略则Proposal-f.v = Proposal-j.v=b，与假设矛盾

推论

当 Proposal-f.v != Proposal-j.v=b，那么 PreProposal-f.proposal_id < Proposal-j.proposal_id（最初两个提案也不相等）
即是，当 Proposal-f.v = Proposal-j.v=b，那么 PreProposal-f.proposal_id > Proposal-j.proposal_id（这就是CL策略）

即如果一个提案Proposal-j最终会被通过，那么对于任意的一个提案Proposal-i,如果Proposal-i.proposal_id > Proposal-j.proposal_id，那么Proposal-i.v = Proposal-j.v

Paxos协议流程

根据上述推导过程，总结了Paxos的协议内容

阶段一 预提案阶段：

  • 提议者Proposer：向接受者Acceptor广播预提案，附带接下来提案Proposal的proposal_id

  • 接受者Acceptor：收到预提案后更新a_proposal_id = max(proposal_id,a_proposal_id)，如果预提案的proposal_id>a_proposal_id，Acceptor回复记录的接受过的proposal_id最大的提案（包含value），否则拒接提案不予理会

阶段二 提案阶段：

  • 提议者Proposer：整个协议最为关键的点：Proposer得到了Acceptor响应

    1、如果未超过半数accpetor响应，直接转为提议失败；

    2、如果超过多数Acceptor的承诺，又分为不同情况：

    1、如果所有Acceptor都未接收过值（都为null），那么向所有的Acceptor发起自己的值和提议编号n，记住，一定是所有Acceptor都没接受过值；
2、如果有部分Acceptor接收过值，那么从所有接受过的值中选择对应的提议编号最大的作为提议的值，提议编号仍然为n。但此时Proposer就不能提议自己的值，只能信任Acceptor通过的值，维护一但获得确定性取值就不能更改原则

  • 接受者Acceptor：如果收到的提案的proposal_id>= a.proposal_id，那么接受这个提案，更新a_proposal_id = max(proposal_id,a_proposal_id)，更新记录的提案，否则拒绝提案不予理会

一句话总结

如果在集群中一个题案A（pid，value）会被通过，让集群中超过半数的人达成一致，那么小于该题案编号的题案会被拒绝，大于该题案编号的题案的值为该题案的值

关于脑裂

什么是脑裂

脑裂(split-brain)就是“大脑分裂”，也就是本来一个“大脑”被拆分了两个或多个“大脑”，我们都知道，如果一个人有多个大脑，并且相互独立的话，那么会导致人体“手舞足蹈”，“不听使唤

脑裂通常会出现在集群环境中，比如ElasticSearch、Zookeeper集群，而这些集群环境有一个统一的特点，就是它们有一个大脑，比如ElasticSearch集群中有Master节点，Zookeeper集群中有Leader节点

如何避免脑裂

在集群中，通常需要选举出一个leader，选举需要采用过半机制，集群中如果有奇数个，例如7个，最多可以挂掉3个。集群中如果有偶数个，例如8个，最多可以挂掉3个，存活数量5个>8/2，才可以选举成功

1
2
集群的容灾数量 = 集群总节点数/2-1（偶数）
集群的容灾数量 =（集群总节点数-1）/2（奇数）

如果是可以挂掉4个，则可能会产生脑裂（两个leader）

image

7个最多挂3个，8个也是最多挂3个

由此可以看出，奇数个节点的集群可以满足相同容灾数量，用更少的节点，所以通常集群的节点数都为奇数

由此可得构建一个集群至少需要3个节点

思考与总结

如何理解一致性

集群中所有存活的节点对某个值达成一致（v=a），而不能出现某个节点认为v=b，

为什么需要预提案

一致性需要满足安全性（一旦v就某个值达成了一致，那么v不能对另一个值再次达成一致），如果只有提案阶段，由于先后问题，P1先令P3的v=a，P2再令P3的v=b，这个过程出现两次一致的情况（认为超过半数对某个值达成一致），视为不安全。如果这里用了拒绝策略（根据提案id大小来拒绝），那么集群中存在P1的v=a，P2的v=b，视为不安全。

拒接策略为什么不能是先来后到

如果使用先来后到的拒接策略的话，那么在集群中如果P1、P2、P3都尝试修改v的值，会导致永远不会出现两个进程的v值相等的情况

流程示例

集群中有三个节点，P1（Proposer、Acceptor、Learner），P2（Proposer、Acceptor、Learner）,P3（Acceptor、Learner），这里分析一下P3如何处理P1和P2的提案的

P3先收到P1的预提案

image

image

image

image

image

流程示例：P3先收到P2的预提案

image

image

image

image

结论

集群中对某个值达成一致，与P3先接收到谁的预提案有关

参考文献