注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

网易杭研后台技术中心的博客

 
 
 
 
 

日志

 
 

Basic Paxos  

来自hzzhouxinran   2013-06-18 21:04:09|  分类: 默认分类 |举报 |字号 订阅

  下载LOFTER 我的照片书  |
断断续续看了一段时间的 Paxos 算法, 总结一下, 这次先写一下 Basic Paxos, 主要基于论文 <Paxos made simple>.

一, Paxos 算法是用来解决什么问题的?

先看一个场景: 一个日志收集系统, 需要从多个不同的机器上收集日志.

最简单的实现方式是, 找一台中心服务器, 所有的日志生产机器作为客户端, 不断的把日志发送到中心服务器, 中心服务器存放所有收集到的日志.

但这种实现方式有一个问题, 中心服务器是一个单点, 一旦中心服务器发生故障, 整个系统不可用.

改进方案: 找多个服务器来收集日志, 例如 2 个. 当每台日志生产机器需要提交日志时, 每条日志都同时被提交到两台收集日志的服务器上面. 这样, 同时有多个日志收集服务器在工作, 解决了单点问题.

但这种多收集服务器的实现方式有另外一个问题, 两台收集日志服务器上收集到的日志可能会不一致. 例如, 假设有两台日志生产机器 P1, P2; 同时有两台日志收集机器: Q1, Q2. 考虑下面这种情况:

  1. P1 发送一条日志信息 M1 分别到 Q1, Q2
  2. P2 发送一条日志信息 M2 分别到 Q1, Q2

但由于实际网络的状况, 日志被收集到的顺序在 Q1, Q2 可能会不一致, 例如:

  • Q1 收集到的日志的顺序是 M1, M2
  • 而 Q2 收集到的日志的顺序是 M2, M1

上面的请求只是一种不一致的情况, 现实环境中, 情况更加复杂, 可能会遇到更多的问题 (例如, 由于网络不稳定, P1 发出的消息 M1 到达了 Q1, 但 M1 没有到达 Q2, 丢失了)

上面这种情况是一个典型的分布式系统的一致性 (consensus) 问题:

  • 在一个分布式系统中, 有一些 processes, 每个 process 都可以提出一个 value.
  • consensus 算法就是用来从这些 values 里选定一个最终 value.
  • 如果没有 value 被提出来, 那么就没有 value 被选中
  • 如果某个 value 被选中, 那么所有的 processes 都应该被学习到

有很多分布式一致性算法来解决这种问题.

而 Paxos 算法就是一种分布式一致性算法, 同时 Paxos 还具有容错性, 能在各种错误环境中, 保证一致性

二, Paxos 算法的系统模型

算法设定了三种角色:

  • 提议者 (proposers): 提议者提出提案
  • 决策者 (acceptors): 决策者负责批准提案
  • 学习者 (learners): 一旦某个提案被多数派决策者批准, 那么就形成了一个决议. 当决议形成以后, 学习者负责学习决议 (我的理解是学习者感知到这个决议已经形成了, 并以某种形式把决议持久化)

在具体实现中, 某个 process 可以扮演多个角色.

这里还有一个 多数派 的概念: acceptors 数量为 n,超过 (n+1)/2 的 acceptors 的集合就是一个多数派.

节点之间通过发送消息进行通信, 通信方式采用异步, 非拜占庭模型, 该模型中:

  • process 以任意的速度进行操作, 可能因为故障而停止, 也可以重新启动. 并且processes选举出来的决议的值不会因为重启等故障而丢失
  • 消息可以延迟发送, 多次发送或丢失, 但不会被篡改 (即不存在拜占庭问题)

一般来说, 分布式算法都需要满足 Safety 和 Liveness:

  • Safety: 一般指一致性, 正确性
  • Liveness: 一般指不会死锁, 活锁

Paxos 算法的系统模型中,

Safety:

  • 最后形成的决议必须是之前被提议者提出的提案
  • 算法的每次执行, 最后只能形成一个决议 (这个最重要, 如果不满足这个, 那么会形成多个决议, 就出现不一致了)
  • 只有形成决议以后才能被学习者学习 (在形成决议之前, 提案是不能被学习的)

Liveness:

  • 只要有提案被提出, 保证最终有一个提案会被选出来做为决议
  • 决议形成以后, 学习者最后能学习到决议

三, Paxos 算法解决问题的思路

基于前面描述的系统模型, 最简单的解决办法就是只设置一个 acceptor, 而这个 acceptor 只批准它接收到的第一个提案. 但这种实现中的 acceptor 是一个单点, 不能处理各种故障.


改进方式, 利用多个 acceptors + 多数派:

  • 设置多个 acceptors
  • 每个 acceptors 最多只能批准一个提案 (如果每个 acceptor 能批准多个提案, 就乱了, 不能形成多数派)
  • 对于某个提案, 只要 acceptors 中有一个多数派批准, 就形成决议

另外, 为了满足 Liveness, 还需要规定:

P1: 一个 acceptor 必须批准它收到的第一个提案

这样就保证了即使只有一个提案被提出, 也必然能形成决议.

但这种解决方案存在问题:

  • 某个 acceptor 发生故障, 就可能不会出现多数派, 不能得到决议; 这时, 就可能需要进行多次提交提案, 进行多次批准.
  • 而允许多次提交, 多次批准, 就可能违背 Safety 中的第二条. 可能形成多个不同内容的决议.

为了解决 "允许多次提交, 多次批准" 可能造成的形成多个不同内容的决议的问题, Paxos 在前面的实现方案的基础上, 又加入了一系列的限制条件 (P2, P2a, P2b, P2c):

  • P2 -> P2a -> P2b -> P2c
  • 只要满足 P2 就能满足 Safety 的第二条, 但是 P2 比较难实现
  • 然后又想出来 P2a, 只要满足 P2a, P2 也就满足了; 但是发现 P2a 存在问题, 需要修订 (P1 和 P2a 有冲突, 如果要满足 P1, 有的情况下, 就做不到 P2a)
  • 然后又想出来 P2b, P2b 和 P1 不冲突, 只要 P1 和 P2b 同时满足就可以解决问题; 但 P2b 比较难实现
  • 然后又想出来 P2c, 只要满足 P2c, P2b 也就满足了; Paxos 算法就是基于 P2c 实现的

下面一节详细介绍这些限制条件.

四, P2 -> P2a -> P2b -> P2c

Paxos 算法中, 给每个提案引入了 版本号 的概念. 每个提案由两部分组成:

  • 提案内容: v
  • 提案版本号: n

这样每个提案就是一个二元组: {v, n}

同时, Paxos 规定, 在全局范围内 (所有的 processes 提出的提案), 每个提案有唯一的版本号, 这样所有的版本号就形成了一个全序关系.

而且, 既然所有提案的版本号是全局范围内的全序关系, 也就给所有的提案进行逻辑时间上的排序提供了可能:

例如, 两个提案: V{v, n}, W{w, m}, 如果 n > m, 可以认为提案 V 比 提案 W 后提出

后面具体介绍算法时也会提到, 怎么利用版本号来规定提案的时间顺序.

1. P2

P2: 假设一个提案 {v, n} 已经被选为决议,对于选出来的其他所有决议 {w, m}, 如果 m > n, 那么内容 w 必须和内容 v 相同

说明:

前面已经说过, 利用版本号可以在逻辑上对全局时间排序, m > n, 代表, {w, m} 是在 {v, n} 之后的提案 (但怎么利用版本号来排序这里没有说, 后面才会讲, 现在姑且这样认为).

P2 其实就是说 (参考前面 Safety 的第二条), 一旦已经形成了一个决议, 那么之后如果又发生了多次提交, 多次批准, 而形成了新的决议, 那么形成的新的决议必须和之前形成的决议的内容相同.

2. P2a

因为 P2 限制很难实现, 就想出了 P2a.

P2a: 假设一个提案 {v, n} 已经被选为决议, 其他所有被 acceptors 批准的提案 {w, m}, 如果 m >n, 那么内容 w 必须和内容 v 相同

显而易见, P2a 被满足了的话, P2 也就满足了.

但 P2a 存在一个问题: P2a 和 P1 有些时候会冲突 (P1 是 Liveness 的限制), 也就是说, 满足了 P1 的话, 有的时候, 做不到满足 P2a:

  • 提案 V{v, n} 已经被选为决议
  • 但在这次选举过程中, 某个 acceptor 没有批准过任何提案 (也就是说, 这个 acceptor 还可能批准更高版本号的提案, 例如: W{w, m}, m > n)
  • 之后, 有一个 proposer 提交了一个提案 W{w, m} 给上面这个 acceptor, 而根据 P1, 这个 acceptor 会批准这个提案, 且这个提案的 m > n, w 和 v 不相同
  • 这就和 P2a 矛盾了: 在 V{v, n} 已经被选为决议的情况下, 任何 acceptor 批准的更高版本 (> n) 的提案的内容必须和 v 相同

说明: 在有一个决议已经形成的情况下, 是有可能发生某个 proposer 提出新的不同内容的提案的可能的.

3. P2b

为了解决 P2a 和 P1 的冲突, 想出了 P2b:

P2b: 假设一个提案 {v, n} 已经被选为决议, 所有被 proposer 提出的提案 {w, m}, 如果 m >n, 那么内容 w 必须和内容 v 相同

一个提案被 acceptor 批准之前肯定要由某个 proposer 提出, 因此 P2b 就隐含了 P2a, 进而隐含了 P2.

4. P2c

怎么做到 P2b 呢? 又想出了 P2c.

P2c: 如果某个 proposer 要提出一个提案 {v, n},那么必须满足下面两个条件中的一个:

  1. 存在一个 acceptors 的多数派 S, 其中的任何一个 acceptor 都没有批准过比 n 小的提案
  2. 存在一个 acceptors 的多数派 S, 集合中的某些 acceptor 曾经批准过小于 n 的提案, 而所有的这些版本号小于 n 的提案中, 拥有最大的版本号那个提案的内容与 v 相同

也就是说, 如果每个 proposer 都按 P2c 为约束来提出一个提案, 那么就可以满足 P2b, 即:

  • 要么还没有形成决议, 可以任选提案的内容;
  • 要么提出的版本号更高的提案的内容和已经形成的决议的内容相同.

对 P2c 的理解如下:

证明1: 假设现在 n=4 的 proposal 已经被选举出来了, 那么我们要证明在满足上面两个条件的前提下提出一个n=5的提案, 那么这个n=5的提案的内容肯定和n=4的提案的内容一致

  • 第一个条件: 能找到一个多数派集合, 其中所有的人都没有批准过比 5 小的提案 (这种情况是不可能发生的, 因为n=4的提案已经被通过了)
  • 第二个条件: 能找到一个多数派集合, 首先来看, 如果其中某人批准过 n=4 的提案, 只要这个n=4的提案的内容和n=5的提案的内容相等的话 (4是比5小的数中最大的一个), 那么如果n=5的提案被选举出来, 就是ok的 (不会破坏上一次选举 n=4 的结果); 其次, 会不会其中没有人批准过n=4, 只发现有人批准过n<=3的提案? 不可能, 因为n=4的提案已经被多数派批准选举出来了

证明2: 假设现在 n=4 的 proposal 已经被选举出来了, 那么我们要证明在满足上面两个条件的前提下提出一个n=6的提案, 那么这个n=6的提案的内容肯定和n=4的提案的内容一致

  • 第一个条件: 能找到一个多数派集合, 其中所有的人都没有批准过比 6 小的提案 (这种情况是不可能发生的, 因为n=4的提案已经被通过了)
  • 第二个条件: 能找到一个多数派集合, 首先来看, 如果其中某人批准过 n=5 的提案, 而这个n=5的提案的内容肯定和n=4的提案的内容相同 (证明1证明). 所以只要这个n=5的提案的内容和n=6的提案的内容相等的话, n=6的提案的内容也就和n=4的提案的内容相同.

总之, 只要 proposer 提交提案时遵守 P2c, 一旦某个版本号的决议形成, 之后形成的更高版本的决议的内容也和最早形成的决议的内容相同.

这里可能有人会提出疑问, 前面说了这么多, 都说的是, 决议从小到大形成的情况, 会不会有先形成大版本号的决议, 再形成小版本号的决议的情况? 比如下面这种场景:

  1. 先形成了 4 号决议
  2. 接下来, 有一个 proposer 企图提出版本号为 3 的提案. 此时这个 proposer 是否能够找到一个多数派, 其中所有的人都没有批准过比 3 小的提案? (多数派里面的所有成员都批准了 4 号提案)

答案是考虑 P2 系列的约束时, 不用考虑版本号会降低的情况, 因为下面一个小节引入的 P1a. 一旦 4 号决议形成, n < 4 的提案就不可能被提出.

也就是说, 多个决议形成, 只能是从小的版本号升到大的版本号.

5. 提案生成算法

保证 P2c, 也就是要保证 proposer 在提出一个提案时, 必须满足 P2c. 所以 proposer 想要提交提案时需要 2 个步骤:

  1. 先探查一下是否能找到 P2c 中描述的多数派
  2. 如果找到了多数派, 就可以提交提案了 (根据找到的多数派的不同类型, 或者提出任意内容的提案, 或者提出和之前形成的低版本的决议内容一致的提案)

这里有个问题要特别注意一下:

因为这两个步骤之间有时间间隔, 可能在第一步找到了一个多数派, 但到了第二步要提交提案的时候, 第一步找到的那个多数派中的某个 acceptor 的状态已经变化了.

此时如果再提交提案, 那个多数派可能已经不满足 P2c 了.

所以, 在第一步探查多数派的同时, 也要锁死被探查的 acceptor 的状态.

具体怎么做, 看下面的提案生成算法的描述:

proposer 选择一个版本号 n, 然后向一个 acceptors 的集合发送请求, 要求 acceptor 做出以下动作:

  1. 承诺不再批准任何小于 n 的提案 (锁定 acceptor 的状态不破坏 P2c)
  2. 返回这个 acceptor 到目前为止已经批准过的, 且小于 n 的最大版本号的提案. 返回消息为: 内容+版本号 (如果没有批准过任何版本号小于 n 提案, 返回一个空值)

如果 proposer 收到了一个多数派的返回响应, 那么这个 proposer 可以提出版本号为 n 的提案, 其对应的内容为:

  1. 如果返回的所有响应都是一个空值 (也就是说, 存在一个多数派没有批准过小于 n 的提案), 提出的提案的内容可以任选
  2. 找出所有响应中最大版本号的内容, 作为要提交的提案的内容

总之, proposer 生成提案需要两个步骤, 发送两种请求:

  1. prepare 请求: 询问状态; 希望 acceptor 端做出承诺, 并返回响应
  2. accept 请求: 提交提案; 希望 acceptor 端批准提案

前面说的是 proposer 端的算法. 接下来说一下 acceptor 端的算法.

  • acceptor 收到 proposer 的两种请求都可以不做任何回答 (因为不回答不会破坏算法的安全性)
  • 如果要对 prepare 请求做出响应, 只要做出承诺, 并根据其当前的状态返回响应就行了 (找出目前为止已经批准过的, 且版本号小于 n 的最大版本号的提案, 作为响应返回)
  • 而对于 accept 请求, 必须查看是否之前已经做过承诺, 只有在不违反承诺的情况下才能返回响应

这就是 P1a: 一个 acceptor 只有在没有响应过任何版本号大于 n 的 prepare 请求时, 才会批准一个编号为 n 的提案

换句话说, acceptor 如果承诺过不会批准任何小于 n 的提案, 那么它会拒绝之后收到的任何小于 n 的 accept 请求.

而 P1a 和 P1 不矛盾. 所以只要同时满足 P1a 和 P2c 就可以达到 Safety.

五, Paxos 算法

上一节已经说过了, 同时满足 P1a 和 P2c 就可以达到 Safety 满足一致性. 不过在这个基础上还可以做一个优化:

  • 如果某个 acceptor 先对版本号为 5 的 prepare 请求返回过承诺, 那么当它之后收到一个版本号为 4 的 prepare 请求时, 这个 acceptor 可以忽略这个版本号为 4 的 prepare 请求
  • 因为, 就算对 4号 prepare 请求返回响应, 之后也不会批准 4号提案的 accept 请求

acceptor 需要持久化两种信息:

  • 它已经批准过的最大版本号的提案
  • 它已经承诺过的 prepare 请求中的最大版本号的请求的版本号

这里要特别解释一下为什么只需要保存 "已经批准过的最大版本号的提案" 就行了?

前面说了, acceptor 收到一个版本号为 n 的 prepare 请求时, 必须找出目前为止已经批准过的, 且版本号小于 n 的最大版本号的提案, 作为响应返回

又由于上面的这个优化, 当收到一个版本号为 n 的 prepare 请求时:

  • 如果发现目前已经批准过的所有提案的最高版本号为 m, 且 m > n, 那么可以不响应这个 prepare 请求 (因为采用前面的优化, 一旦做过版本号为 m 的承诺, 就可以不给所有小于 m 的 prepare 请求返回响应)
  • 如果发现目前已经批准过的所有提案的最高版本号为 m, 且 m < n, 那么就返回这个版本号为 m 的提案就行了

总之, 当 acceptor 重启恢复以后, 只要能重新拿到这两个信息, 就可以恢复到正常工作状态. 同时, proposer 不需要持久化任何信息, 可以随意重启 (只需要每次提交提案时, 都用一个全局唯一的版本号就行了)

完整的算法如下:

Phase 1:

  • proposer 选择一个提案版本号为 n, 然后向 acceptor 的某个多数派集合的成员发送版本号为 n 的 prepare 请求
  • 如果一个 acceptor 收到一个版本号为 n 的 prepare 请求, 且 n 大于它已经承诺过的所有 prepare 请求的版本号, 那么它就会承诺不会再批准任何版本号小于 n 的提案, 同时将它已经批准过的最大编号的提案 (如果存在的话) 作为响应返回

Phase 2:

  • 如果 proposer 收到来自半数以上的 acceptor 对于它的 prepare 请求 (版本号为 n) 的响应, 那么它就会发送一个针对版本号为 n, value 值为 v 的提案的 accept 请求给 acceptor, 在这里, v 是收到的响应中版本号最大的提案的值, 如果所有响应中都不包含提案, 那么它就是任意值。
  • 如果 acceptor 收到一个针对版本号 n 的提案的 accept 请求, 只要它还未对版本号大于 n 的 prepare 请求作出承诺, 它就可以批准这个提案

参考文档


  评论这张
 
阅读(1100)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017