- 浏览: 716800 次
- 性别:
- 来自: 北京
最新评论
-
wxweven:
Surmounting 写道既然 Java 的跳表那么少,我决 ...
SkipList 跳表 -
暮雪云然:
写的不错,很透彻
Java静态内部类 -
bzhao:
好,赞扬!
Linux信号详解 -
jacktao219:
赞一个~! ,现在正在看redis 所以接触到跳表
SkipList 跳表 -
is_leon:
vote--后还要判断是否为0吧,如果为0则废掉重新置位can ...
现在有一个整数数组,已知一个数出现的次数超过了一半,请用O(n)的复杂度的算法找出这个数
Paxos算法
- 博客分类:
- algorithms
分布式系统的核心问题是数据一致性,解决一致性有很多算法,而 Paxos 算法
无疑是最著名的,Google 工程师曾说,所有一致性算法都可以归结为 Paxos 算法
的一个特列。可见,很有必要学习 Paxos 算法。
Paxos 算法是由 Lamport 提出来的,他得论文 Paxos made simple 是最好的
学习资料。我在阅读的过程中遇到很多困难,文中的一些逻辑推论隐藏得比较深,
需要反复研读,这里对算法的描述就不写了,只是记录一些个人的理解。
论文首先指出一致性最核心的要求是,Only a single value is chosen,就是说,
协商的结果,最终只能确定一个值,不能选多个值。后面的一些条例都是为了满足
这个要求。
我们规定,每个 acceptor 最多只能 accept 一个 value,如果存在一个 acceptor
的多数派,其中每个 acceptor 都 accept 了同一个 value 时,该 value就能被 chosen ,
这里多数派,我的理解是超过一半的 acceptor。所以说,一个 value 要想被 chosen,必须有超过一半
的 acceptor 支持(accept)它。由于每个 acceptor 最多只能投一票,因此不可能存在两个 value
它们的支持率均超过 50%,最终只能有一个 value 获胜。这就保证了 Only a single value is chosen.
一致性问题产生的原因是多个 proposer 可能提出各种不同的 value,导致系统不知道选择哪个 value,
有一个特例,如果只有一个 proposer 提出 value,显然就不存在一致性问题,这个时候,必须选择这个
唯一的 value。考虑只有一个 proposer 提出 value的情况,该 proposer 向所有 acceptor 发出 proposal,
由于没有其他的 proposal,所以每个 acceptor 会而且只会收到唯一的 proposal,如前所说,这个 proposal
理应被 chosen,但是要想它被chosen,就要求多数派的 acceptor 都支持(accept)此 proposal。于是有了准则 P1:
P1. An acceptor must accept the first proposal that it receives.
说的是,对于第一个 receive 到的 proposal, acceptor 必须无条件 accept。
有了这个准则,就可以保证形成一个多数派的 acceptor 来支持这个唯一的 proposal。于是在只有一个
proposer 提出 value 时,该 value 必将被 chosen。
准则 P1 只是为了满足上面提到的特列,即只有一个 proposer 的时候,而如果有多个 proposer,准则 P1 就
不一定能保证一致性了。考虑两个 proposer 分别提出 value1 和 value2,如果 value1 和 value2 各得到
一半的 acceptor 支持,这样两者都不能形成一个多数派,就无法确定获胜者了。
为了形成多数派,解决的办法是允许 acceptor 投多张票,即让 acceptor 可以同时支持多个 proposal。
但这样又会产生一个问题,可能两个proposal 都形成了多数派,比如 proposal1 获得超过一半的 acceptor 支
持,proposal2也获得了超过一半的 acceptor 支持,那到底选哪个 proposal 呢,其实我们的要求是确定一个
value 出来,只要 proposal1 和proposal2都具有相同的 value,就能保证 only a single value is chosen。
所以我们允许多个 proposal 被 chosen,即多个 proposal 同时获得超过一半 acceptor 的支持,但是要求
这些 proposal 都具有相同的 value。 如何保证这点呢,看准则 P2
P2. If a proposal with value v is chosen, then every higher-numbered proposal that is chosen
has value v
为了区分 proposal,我们给每个 proposal 一个唯一的编号,这样 proposal 由编号和 value 组成,可简单表示
为 <n, value>,其中 n 就是编号。
准则 P2 说的是,如果 <n, v> 被 chosen,则要求其他被 chosen 的,而且编号比 n 大的 proposal 的 value
也是 v。比如这几个proposal <n, v>, <n1, v1>, <n2, v2>, <n3, v3> 都被 chosen,而且有 n < n1 < n2 < n3。
根据准则P2, <n, v> 被 chosen,要求 v1 == v, v2 == v, v3 == v。 于是保证了所有被 chosen 的 proposal
的 value 都是 v。
准则 P2 是对 chosen 的结果做要求,为了得到这样的结果,我们需要在算法运行过程中对 acceptor 做要求。
于是有了准则 P2a,P2a 蕴含着 P2
P2a. If a proposal with value v is chosen, then every higher-numbered proposal accepted
by any acceptor has value v.
说的是,如果 <n, v> 被 chosen,则要求任何被 acceptor 支持(accept)的,而且编号比 n 大的 proposal
的 value 也是 v。 这一条准则保证了所有 acceptor 支持的 proposal 都具有相同的 value。进而所有被 chosen
的 proposal 具有相同的 value,所以说,P2a 蕴含 P2。
准则 P2a 有一个漏洞,假设 <n, v> 被 chosen,说明 <n, v> 得到了大多数 acceptor 的支持,但由于网络原因,
可能某个 acceptor a,没有收到任何 proposal,网络恢复的时候,恰好 a 收到一个编号更高的 proposal <m, v1>,
其中 m > n, v1 与 v 不相同,根据准则 P1, a 必须支持 <m, v1>,而 <m, v1> 与 <n, v> 的 value 是不相同的,
这就违反了 P2a。所以 P1 和 P2a 不能很好的配合,我们需要寻找一个更合适的准则来与 P1 配合,共同保证一致性。
于是出现准则 P2b。
P2b. If a proposal with value v is chosen, then every higher-numbered proposal issued by
any proposer has value v.
说的是,如果 <n, v> 被 chosen, 则要求任何 proposer 提出的,编号比 n 大的 proposal 的 value 也是 v。
这一条准则要求所有 proposer 提出的 proposal 都具有相同的 value。
准则 P2b 非常严格,因为它从源头上要求各个 proposal 具有相同的 value。但是做到这点不容易,必须对
proposer 做严格要求,绝不允许proposer 随意提出 proposal, proposer 提出一个 proposal前,得先看看该
proposal 是否满足条件,如果不满足,则不允许 proposer 提出 proposal。于是出现了准则 P2c:
P2c. For any v and n, if a proposal with value v and number n is issued, then there is a
set S consisting of a majority of acceptors such that either (a) no acceptor in S has
accepted any proposal numbered less than n, or (b) v is the value of the highest-numbered
proposal among all proposals numbered less than n accepted by acceptors in S.
P2c 说明了在何种条件下,proposer 才能提出 proposal <n, v>。只要满足两个条件中的任意一个,就可以提出
proposal。
条件1说的是, 如果大多数 acceptor 都没有 accept 过任何 proposal,根据 P1, 也可以理解为
大多数 acceptor 都没有 receive 到任何 proposal,就允许该 proposal 提出,而且 proposal 的值
可以是任意的。比如一个多数派 acceptor,其中每个 acceptor 都没有 receive 到 proposal,这个时候
proposer 把 <n, v> 发送给多数派 acceptor,根据 P1,多数派中每个 acceptor 都无条件 accept 此 proposal。
然后 <n, v> 被 chosen,满足一致性的要求:Only a single value is chosen。
条件2说的是,先取得大多数 acceptor accept过的,编号最大的 proposal 的 value,记为 v1,
如果 v 和 v1 相同,就允许该 proposal 提出。
P2C 可以保证一致性,可以用递推证明,P2C 的两个条件恰好对应证明过程的初始状态和递推状态:
最开始,所有 acceptor 都没有 accept 过任何 proposal,根据 P2C的条件1,proposer 可以
提出任何 proposal <n, v>, 而且都会被 chosen。然后另一个 proposer 也想提出 proposal <n1, v1>,
由于这个时候不满足条件1,我们看能否满足条件2,先取得大多数 acceptor accept 过的,编号最大的
proposal,即为 <n, v>,然后看 v1 和 v 是否相等,如果相等,就可以提出 <n1, v1>。当 <n1, v1> 被
chosen 后,Since v1 is equal to v, The chosen value is still v. 同理后续提出的 proposal 的 value
都是 v,最后算法完成,The chosen value is v, 保证了 Only a single value is chosen。
发表评论
-
编程之美3.3 计算字符串的相似度
2012-03-13 23:26 33问题描述 定义一套操作方法, 把两个不相同的字符串变得相同, ... -
编程之美3.1 字符串移位包含的问题
2012-03-12 23:26 3258题目 给定两个字符串 s ... -
SkipList 跳表
2011-10-09 01:08 39242为什么选择跳表 目前经常使用的平衡数据结构有:B树,红黑树, ... -
(转)一致性哈希算法及其在分布式系统中的应用
2011-09-29 19:02 2269原文地址: http://www.cnb ... -
算法导论习题 5.1 -2
2011-09-29 09:23 1957描述random(a, b)过程的一种实现,它只调用rando ... -
现在有一个整数数组,已知一个数出现的次数超过了一半,请用O(n)的复杂度的算法找出这个数
2011-05-05 19:43 6162现在有一个整数数组,已知一个数出现的次数超过了一半,请用O(n ... -
从海量数据中找中位数(c语言实现)
2011-05-05 12:49 4984题目:5亿个int,从中找出第k大的数 算法:之后补上 ... -
寻找最大的K个数 (C语言实现)
2011-05-04 16:31 5287题目:100亿个整数,求最大的1万个数,并说出算法的时间复杂度 ... -
kmp算法的理解与实现
2011-04-30 21:29 25411KMP算法曾被我戏称为看毛片算法,当时笑喷...... ... -
败者树 多路平衡归并外部排序
2011-04-25 21:52 10504一 外部排序的基本思路 ... -
实现两个整数的除法,不能用除号和乘号
2011-04-22 15:17 3591对于两个整数a和b, 求a/b,可以从1开始枚举结果resul ... -
最大公共子字符串(Longest Common Substring)
2011-04-22 13:33 3338Longest Common Substring和Longes ... -
poj 1458 最长公共子串(Longest Common Subsequence)
2011-04-22 10:45 2516LCS问题: 给定序列 X = <x1,x2,... ... -
归并排序
2011-04-21 21:51 1134#include <stdio.h> #i ... -
快速排序 顺序统计量 数组分割
2011-04-21 19:28 1327#include <stdio.h> #in ... -
位运算集锦
2011-04-21 17:15 2041文中2'k代表2的k次方 1 除以2的k次幂可以用位运 ... -
最长递增子序列
2011-04-21 14:45 1153设L = <a1,a2,...an>是n个不同的实 ... -
poj 2774 后缀数组
2011-03-21 17:28 1740#include <stdio.h> # ... -
poj 2823 线段树
2011-03-17 18:49 1568赤裸裸的线段树,数据量很大,加了IO优化函数。 #in ... -
poj 3368 RMQ 线段树 离散化
2011-03-17 17:00 2686一 题意:给定递增序列 ...
相关推荐
在github上找到的paxos算法实现,具体是运行和实现方法可以看README文件,注意acceptor、proposer、以及learner的数量根据打开进程的数量变化,不是局限于.c文件的数量。
Paxos算法是莱斯利·兰伯特(Leslie Lamport,就是 LaTeX 中的"La",此人在微软研究院)1990年提出的一种基于消息传递的一致性算法。[1] 这个算法被认为是类似算法中最有效的。 背景介绍编辑 播报 Paxos 算法解决的...
Paxos算法的中文翻译,值得参考,讲述了paxos协议的原理
Paxos算法.pdf
很不错的paxos算法分析文档,值得一看,虽不能深入研究,但是可以初步了解!
面向云计算基础课程的Paxos算法教学设计研究.pdf
Paxos算法是莱斯利·兰伯特(Leslie Lamport,就是 LaTeX 中的"La",此人在微软研究院)1990年提出的一种基于消息传递的一致性算法。[1] 这个算法被认为是类似算法中最有效的。 背景介绍编辑 播报 Paxos 算法解决的...
Paxos算法虽然可以容忍已经申请到访问权的“提案委员”故障,可以容忍少数派“审批委员”故障;但在出现竞争的情况下,其收敛速度很慢,甚至可能出现活锁的情况,例如当有等于或多于审批委员会数量的“提案委员”在同时...
Paxos算法详解.ppt
Paxos算法是分布式技术大师Lamport提出的,主要目的是通过这个算法,让参与分布式处理的每个参与者逐步达成一致意见。用好理解的方式来说,就是在一个选举过程中,让不同的选民最终做出一致的决定。 Lamport为了...
paxos算法学习.docx
paxos 算法推导中文版。清晰描述paxos的前世今生。
Paxos算法介绍,paxos个角色的职责和可能的实现分析,离我们把paxos算法变为一个可执行程序的目标又进了一步,使我们对paxos的实现方式大致心里有底,但还有诸多的问题需要进一步讨论,比如错误处理。虽然文中也提到...
#资源达人分享计划#
Paxos算法深入分析.doc
人工智能-项目实践-多线程-Paxos算法的多线程实现 Paxos算法的多线程实现 采用java多线程方式,实现分布式一致性算法Paxos
融入了作者自己对于paxos 算法的理解 lamport 经典之作 Google chubby 服务核心, 云计算 研究必读
Paxos算法(参考).doc
zookeeper是一款高性能的分布式协调服务,其基于paxos算法来做集群,并产生出Leader和Follower。这两个都是英文的,有兴趣的童鞋可以看下。