Paxos算法分析

标签: 分布式系统 | 发表时间:2011-10-26 18:01 | 作者:wli chuang
出处:http://www.schooner-ht.com

Paxos 算法要解决的问题是在一个分布式系统中如何就某个值(提案)达成一致。是一个非常基础而且经典的算法,也是目前最有效的一个算法。【来自Schooner中国团队,转载请申明】

算法理论描述:

提案的提出与通过

通过一个提案分为两个阶段:

  1. prepare 阶段:
    1. proposer 选择一个提案编号 n 并将 prepare 请求发送给 acceptors 中的一个多数派;
    2. acceptor 收到 prepare 消息后,如果提案的编号大于它已经回复的所有 prepare 消息,则 acceptor 将自己上次的批准回复给 proposer,并承诺不再批准小于 n 的提案;
  2. 批准阶段:
    1. 当一个 proposor 收到了多数 acceptors 对 prepare 的回复后,就进入批准阶段。它要向回复 prepare 请求的 acceptors 发送 accept 请求,包括编号 n 和根据 P2c 决定的 value(如果根据 P2c 没有决定 value,那么它可以自由决定 value)。
    2. 在不违背自己向其他 proposer 的承诺的前提下,acceptor 收到 accept 请求后即批准这个请求。

这个过程在任何时候中断都可以保证正确性。例如如果一个 proposer 发现已经有其他 proposers 提出了编号更高的提案,则有必要中断这个过程。因此为了优化,在上述 prepare 过程中,如果一个 acceptor 发现存在一个更高编号的”草案”,则需要通知 proposer,提醒其中断这次提案。

详细的解释,见http://zh.wikipedia.org/wiki/Paxos%E7%AE%97%E6%B3%95,已经说的很清楚了,不过理论性比较强,这里,就我个人的理解,做一个比较通俗的分析,希望可以帮助大家理解

假设条件:

  1. 不存在拜占庭失效,即所有的消息可以丢失,可以乱序,但是不可能出现错误。
  2. 所有的提案之间都存在偏序关系,这里我们可以简单的假设,所有的提案编号都是唯一且单调递增的。

核心概念:

  1. 提案只有在提出之后才能批准
  2. 批准分为两个阶段,批准提案和批准该提案的值
  3. 值的形成不是简单的由提案提出,需要由批准提案的返回值决定
  4. 每次算法执行过程中,只能批准一个值
  5. 每次批准需要大于半数的人同意

算法描述:

我们通过一个分布式的Key-Value store系统来描述这个算法。假设系统中有5个节点(A,B,C,D,E),共同维护一个分布式的Key-Value store。那么我们可以通过工程实际对应上述抽象概念,每一个写请求对应一个提案(Paxos针对的应该是对于同一个值的写请求,即我们常说的写冲突),每一个写请求都应该是一个事务,所以应该有一个trx-id, 对应我们的提案编号。我们通过一个写冲突来描述算法过程。

  1. A节点接受一个写请求(set abc=0,trx-id=0),同时D节点接受一个写请求(set abc=1, trx-id=1)
  2. A的写请求提交多数派,A,B,C审议,D的写请求提交多数派C,D,E审议
  3. A,B同意A,D,E同意D,关键点在C
  4. 如果C先收到A的请求,那么C先同意A,不回复任何值,但记下A的值(set abc=0), 之后C收到D的请求,发现D的trx-id大于A的,那么C回复同意D,但是同时回复值需要是0(因为C已经记下A的值为0)
    1. A收到回复,发现没有任何值,于是设其写请求的值是0提出值批准请求给A,B,C。D收到回复,发现值是0,设其写请求的值是0提出值批准请求给C,D,E
    2. A,B批准A的值批准请求,D,E批准D的值批准请求,C由于已经批准了trx-id=1的请求,所以驳回了A trx-id=0的值批准请求,  之后C批准D的值批准请求
    3. 最终D的提案获得通过,但是值是0
    4. 将通过的提案广播出去,所有节点set abc=0
  5. 如果C先收到D的请求,那么C先同意D,不回复任何值,但记下D的值(set abc=1), 之后C收到A的请求,发现A的trx-id小于D的,那么不回复A,
    1. A只收到A,B的回复,提案失败,D收到C,D,E的回复,提案成功
    2. D收到回复,发现没有任何值,设其写请求的值是1提出值批准请求给C,D,E.
    3. C,D,E批准D的值批准请求
    4. 最终D的提案获得通过,其值是1.
    5. 将通过的提案广播出去,所有节点set abc=1

那么通过上述的描述,我们就可以看到,一个写冲突就可以解决了,无论最终结果是值为1还是值为0,系统不会出现数据不一致问题,即Paxos算法可以很严格的保证数据的一致性。但是,具体算法的时间复杂度还是比较高的,在工程实践中,需要考虑采用其变种,降低一部分的一致性要求或降低系统的并发度,来提高该算法的实用性,将在后续文章中讨论。

相关 [paxos 算法分析] 推荐:

Paxos算法分析

- chuang - Schooner中国技术团队
Paxos 算法要解决的问题是在一个分布式系统中如何就某个值(提案)达成一致. 是一个非常基础而且经典的算法,也是目前最有效的一个算法. 【来自Schooner中国团队,转载请申明】. prepare 阶段: proposer 选择一个提案编号 n 并将 prepare 请求发送给 acceptors 中的一个多数派;.

Paxos与zookeeper

- - 互联网 - ITeye博客
1,什么是Paxos算法. Paxos算法是分布式计算领域中一个非常重要的算法,主要解决分布式系统如何就某个值(决议)达成一致的问题. 一个典型的场景是分布式数据库的一致问题:如果分布式数据库的各个节点初始状态一致,又能执行相同的操作序列,那么最后能达到一个一致的状态. 但是如何保证在每个节点上执行相同的命令序列呢.

短文: Block Chain 与 Paxos

- comain - fcicq's blog-beta
作为 P2P 系统, Bitcoin 的一致性实现方法是值得专门写出来的.. 下面一一列举 Paxos 的专有名词, 并指出 Bitcoin 中的对应方法/实现.. –最长链中所有的 Block 均为决议. (但链末尾并不稳定, 所以最近 120 个 Block 里产生的钱不能花.. 经历 120 block 之后, block 是彻底不可逆转的, 严格意义上最近 120 block 不能算通过的决议).

分布式选举算法Paxos

- - 互联网 - ITeye博客
Paxos算法是分布式计算领域中一个非常重要的算法,主要解决分布式系统如何就某个值(决议)达成一致的问题. 一个典型的场景是分布式数据库的一致问题:如果分布式数据库的各个节点初始状态一致,又能执行相同的操作序列,那么最后能达到一个一致的状态. 但是如何保证在每个节点上执行相同的命令序列呢. 这就需要在每条指令上执行一个“一致性算法”以保证每个节点看到的指令一致.

分布式架构之 Paxos 协议

- - IT瘾-dev
这周一下了个决定"裸辞",逼自己一把. 当你在一个复杂的环境下,对所负责的项目失去激情时、不开心时你会选择怎样. 已经进入到分布式架构系列的尾声了,倒数第三篇文章. Paxos、Raft、以及变种/类似的协议都是用于在分布式里面解决选举的问题. 2pc、3pc、Waro是保证数据的强一致性,它们之间的强一致性在层次上是不同的概念、解决的问题不同,需要注意区分.

分布式系统基石:Paxos

- - DockOne.io
这个世界上只有一种一致性算法,那就是Paxos,其它的算法都是残次品. ——Mike Burrows(Google Chubby 的作者). Paxos是学习分布式系统无法绕开的一环,从理论上看Paxos是非常优雅的,但是实现起来就没有那么简单了. 《 The Part-Time Parliament》又看不懂,只能看《 Paxos Made Simple》和 视频教程这种东西才能维持的了生活这样子.

【首发原创】Mansory 算法分析

- - HTML5研究小组
相信大家对 mansory排版算法印象十分深刻,它能够十分有效的实现页面紧凑排版,节省空间,并且还显得十分美观. 在很多网站,包括鼎鼎有名的 pinterest都使用了这个算法来实现排版. 这个过程有点象瓦匠在码砖头,所以我会有时候称这些div为brick(砖头),容器为墙面!. 有一个现象不知道大家注意否,这个排版的方法对于输入是很敏感的.

raft算法与paxos算法相比有什么优势,使用场景有什么差异? - 知乎

- -
Raft协议比paxos的优点是 容易理解,容易实现. 它强化了leader的地位,把整个协议可以清楚的分割成两个部分,并利用日志的连续性做了一些简化: (1)Leader在时. 由Leader向Follower同步日志 (2)Leader挂掉了,选一个新Leader,Leader选举算法. 但是本质上来说,它容易的地方在于流程清晰,描述更清晰,关键之处都给出了伪代码级别的描述,可以直接用于实现,而paxos最初的描述是针对非常理论的一致性问题,真正能应用于工程实现的mulit-paxos,Lamport老爷爷就提了个大概,之后也有人尝试对multi-paxos做出更为完整详细的描述,但是每个人描述的都不大一样.

云存储中的HTTP鉴权算法分析

- - 忘我的追寻
基于Base64编码的 HTTP Basic Authentication由于安全问题,已经不再广泛使用了. 在云存储中,数据的安全性一直被广泛关注. 亚马逊的AWS S3和Openstack Swift分别采取了不同的算法来对每一个HTTP请求进行鉴权. 这里想对二者的鉴权过程作简单分析和总结.

[转]排名算法(二)--淘宝搜索排序算法分析

- - 工作笔记
原文:https://blog.csdn.net/u011966339/article/details/78052569 . 淘宝搜索排序的目的是帮助用户快速的找到需要的商品. 从技术上来说,就是在用户输入关键词匹配到的商品中,把最符合用户需求的商品排到第一位,其它的依次排在后续相应的位置. 为了更好的实现这个目标,算法排序系统基本按三个方面来推进:.