- 浏览: 723758 次
- 性别:
- 来自: 北京
最新评论
-
wxweven:
Surmounting 写道既然 Java 的跳表那么少,我决 ...
SkipList 跳表 -
暮雪云然:
写的不错,很透彻
Java静态内部类 -
bzhao:
好,赞扬!
Linux信号详解 -
jacktao219:
赞一个~! ,现在正在看redis 所以接触到跳表
SkipList 跳表 -
is_leon:
vote--后还要判断是否为0吧,如果为0则废掉重新置位can ...
现在有一个整数数组,已知一个数出现的次数超过了一半,请用O(n)的复杂度的算法找出这个数
分布式系统的核心问题是数据一致性,解决一致性有很多算法,而 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 3326题目 给定两个字符串 s ... -
SkipList 跳表
2011-10-09 01:08 39760为什么选择跳表 目前经常使用的平衡数据结构有:B树,红黑树, ... -
(转)一致性哈希算法及其在分布式系统中的应用
2011-09-29 19:02 2316原文地址: http://www.cnb ... -
算法导论习题 5.1 -2
2011-09-29 09:23 2001描述random(a, b)过程的一种实现,它只调用rando ... -
现在有一个整数数组,已知一个数出现的次数超过了一半,请用O(n)的复杂度的算法找出这个数
2011-05-05 19:43 6234现在有一个整数数组,已知一个数出现的次数超过了一半,请用O(n ... -
从海量数据中找中位数(c语言实现)
2011-05-05 12:49 5039题目:5亿个int,从中找出第k大的数 算法:之后补上 ... -
寻找最大的K个数 (C语言实现)
2011-05-04 16:31 5342题目:100亿个整数,求最大的1万个数,并说出算法的时间复杂度 ... -
kmp算法的理解与实现
2011-04-30 21:29 25494KMP算法曾被我戏称为看毛片算法,当时笑喷...... ... -
败者树 多路平衡归并外部排序
2011-04-25 21:52 10676一 外部排序的基本思路 ... -
实现两个整数的除法,不能用除号和乘号
2011-04-22 15:17 3635对于两个整数a和b, 求a/b,可以从1开始枚举结果resul ... -
最大公共子字符串(Longest Common Substring)
2011-04-22 13:33 3400Longest Common Substring和Longes ... -
poj 1458 最长公共子串(Longest Common Subsequence)
2011-04-22 10:45 2566LCS问题: 给定序列 X = <x1,x2,... ... -
归并排序
2011-04-21 21:51 1170#include <stdio.h> #i ... -
快速排序 顺序统计量 数组分割
2011-04-21 19:28 1362#include <stdio.h> #in ... -
位运算集锦
2011-04-21 17:15 2106文中2'k代表2的k次方 1 除以2的k次幂可以用位运 ... -
最长递增子序列
2011-04-21 14:45 1183设L = <a1,a2,...an>是n个不同的实 ... -
poj 2774 后缀数组
2011-03-21 17:28 1783#include <stdio.h> # ... -
poj 2823 线段树
2011-03-17 18:49 1617赤裸裸的线段树,数据量很大,加了IO优化函数。 #in ... -
poj 3368 RMQ 线段树 离散化
2011-03-17 17:00 2731一 题意:给定递增序列 ...
相关推荐
**云计算中的Paxos算法** Paxos算法是一种在分布式系统中解决一致性问题的经典协议,由Leslie Lamport提出。它的主要目标是在存在网络延迟、消息丢失或重复、节点故障等不可靠因素的情况下,确保一组分布式节点能够...
Paxos算法是一种在异步分布式系统中实现共识(Consensus)的算法,由Leslie Lamport提出。它能够确保系统中的多个节点即使在某些节点出现故障时,也能就某个值(例如一个操作请求)达成一致意见。Paxos算法的核心...
### Paxos算法详解与Zookeeper应用 #### 一、Paxos算法概述 Paxos算法是一种用于解决分布式系统中一致性问题的经典算法。该算法由Leslie Lamport于1990年提出,并逐渐成为分布式一致性算法领域的核心理论之一。在...
**Paxos算法详解** Paxos算法是Leslie Lamport提出的一种分布式一致性协议,它在分布式系统中解决了一个核心问题:如何在一个网络环境中保证多个节点间的数据一致性,即使在网络存在延迟、消息丢失或重复、节点故障...
通过详细阐述Paxos算法的工作原理,并设计具体的教学案例,该教学方案在实际教学实践中获得了良好的教学效果,加深了学生对Paxos算法工作原理的理解。 Paxos算法是由莱斯利·兰伯特(Leslie Lamport)提出的一种...
为了深入理解基于Paxos算法的ATS数据分布式存储模型,我们首先需要探讨相关的概念和技术背景。 Paxos算法是一种解决分布式系统中一致性问题的算法,由莱斯利·兰伯特(Leslie Lamport)提出。在分布式系统中,多个...
**Paxos算法详解** Paxos算法是分布式系统中的一种一致性协议,由Leslie Lamport提出,旨在解决在存在网络延迟、消息丢失或重复、节点故障等不确定因素的环境中,如何让分布式系统的多个节点就某个值达成一致。...
这篇名为"cheap-paxos.pdf"的论文深入探讨了Paxos算法的一个变种——廉价Paxos(Cheap Paxos),它在保持Paxos算法基本性质的同时,优化了性能,降低了复杂性,尤其适用于大规模分布式系统。 Paxos算法最初由Leslie...
很不错的paxos算法分析文档,值得一看,虽不能深入研究,但是可以初步了解!
**Paxos算法详解** Paxos算法,以其创始人Leslie Lamport的灵感来源——希腊小岛Paxos命名,是一种解决分布式系统中一致性问题的关键算法。在Paxos算法中,Lamport构建了一个虚拟的希腊城邦,通过模拟岛上的议会...
### 深入理解Paxos算法 #### 引言 在分布式系统领域,一致性算法是确保多个节点间数据同步的基础。其中,Paxos算法因其简洁性和有效性而备受推崇,成为了众多分布式系统设计的核心。本文旨在深入探讨Paxos算法的...
### Paxos算法详解 #### 一、Paxos算法概览与背景 Paxos算法是一种用于解决分布式系统中一致性问题的重要算法,由莱斯利·兰伯特(Leslie Lamport)在1990年提出。该算法旨在解决在分布式系统中,即使面对节点故障...
Paxos算法是莱斯利·兰伯特(Leslie Lamport,就是 LaTeX 中的"La",此人在微软研究院)1990年提出的一种基于消息传递的一致性算法。[1] 这个算法被认为是类似算法中最有效的。 背景介绍编辑 播报 Paxos 算法解决的...
根据给定文件的内容,本知识点将专注于分布式系统中的Paxos算法,高可用性、一致性问题以及分布式锁服务系统的设计与实现。 1. 分布式系统与Paxos算法:分布式系统由多个分布在网络中的节点组成,它们通过通信和...
Paxos算法是一种解决分布式系统中一致性问题的算法,它的主要目标是在网络通信不可靠的情况下,确保集群中的节点能就某个提案达成一致。在Zookeeper中,Paxos算法被用来选举 Leader 和维护集群的状态一致性。Paxos...
基于消息传递的Paxos算法是一种用于解决分布式系统中一致性问题的共识算法。Paxos算法由Leslie Lamport提出,旨在在分布式系统中达成一致意见,即便是在有节点失效的情况下。它被广泛应用在分布式计算系统中,以保证...
【微信PaxosStore:深入浅出Paxos算法协议】 Paxos算法是由Leslie Lamport提出的分布式一致性协议,其目标是确保在一个可能存在网络延迟、消息丢失或重复、节点故障的分布式系统中,所有节点能够就某个值达成一致。...
Paxos 算法是一种经典的分布式一致性...Paxos算法虽然复杂,但它是解决分布式一致性问题的基础,对后来的Raft、ZAB等一致性算法产生了深远影响。理解并应用Paxos算法,对于构建大规模、高可用的分布式系统至关重要。
Paxos算法是一种分布式一致性算法,由Leslie Lamport提出,主要用于解决分布式系统中节点间的一致性问题,确保即使在存在网络延迟、故障或消息丢失的情况下,也能达成一致的决策。它在Google的Chubby、MegaStore、...