paxos算法

‘壹’ 号称史上最晦涩的算法paxos，如何变得平易近人

分布式一致性算法（Consensus Algorithm）是一个分布式计算领域的基础性问题，其最基本的功能是为了在多个进程之间对某个（某些）值达成一致（强一致）；进而解决分布式系统的可用性问题（高可用）。Paxos是最重要的分布式一致性算法，很多人都把它作为“分布式一致性协议”的代名词（Mike Burrows, inventor of the Chubby service at Google, says that“there is only one consensus protocol, and that’s Paxos”）。
关于Paxos的历史和原理，已经有很多经典的论文可以参考，也有厂内外的文章有详细的描述，本文就不再重复了。感兴趣的同学可以阅读下这些论文[1,2,3,4]。

‘贰’ 如何浅显易懂地解说 Paxos 的算法

Paxos算法解决的问题是在一个可能发生消息可能会延迟、丢失、重复的分布式系统中如何就某个值达成一致，保证不论发生以上任何异常，都不会破坏决议的一致性。

一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。

一个通用的一致性算法可以应用在许多场景中，是分布式计算中的重要问题。 节点通信存在两种模型：共享内存和消息传递。Paxos算法就是一种基于消息传递模型的一致性算法。

分析Paxos算法的目的

Paxos算法的目的是为了解决分布式环境下一致性的问题。多个节点并发操纵数据，如何保证在读写过程中数据的一致性，并且解决方案要能适应分布式环境下的不可靠性（系统如何就一个值达到统一）。

Paxos算法中，可分为4种角色：

• Proposer：提议发起者，处理客户端请求，将客户端的请求发送到集群中，以便决定这个值是否可以被批准。

• Acceptor：提议批准者，负责处理接收到的提议，他们的回复就是一次投票。会存储一些状态来决定是否接收一个值。

• Client：产生议题者，Proposer就像Client的使者，由Proposer使者拿着Client的议题去向Acceptor提议，让Acceptor来决策。

• Learner：最终决策学习者，最终学习的目标是Acceptor们最终接受了什么议题？

Paxos算法的原理

例如：公司商定年会举办的地点，每个人都可以提出建议。在现实环境中我们可以在一个会议室共同讨论或在微信群中讨论（基于内存共享方式）；但在基于消息传递的分布式环境中每个人只能通过手机短信与其它人通过。如何在这种会延迟、丢失的环境中确定一个年会举办地点。

Paxos算法是这样解决这个问题：

每个人都可以提出建议、同意建议、接受建议

少数服从多数。只要建议被多数人同意即可确定该建议。

于是确定以下讨论方式：

• 只有被提出来的建议才能被大家同意。

• 最终只能确定一个建议。

• 如果某个人认为大家同意了某 个建议，那么这个建议必须真的是被大家同意的。

Paxos算法图解



在实现环境中会通过一次提议，选择一个Leader。后续所有的提议都只能由Leader提出。

原来paxos算法里的角色都是这样的不靠谱，不过没关系，结果靠谱就可以了。该算法就是为了追求结果的一致性。

原文链接：什么是Paxos算法？Paxos算法是区块链核心算法之一

‘叁’ 如何浅显易懂地解说 Paxos 的算法

Paxos真的并不是很容易理解，而且最初版本的Paxos也不能实现，相对而言一些变种算法更加容易理解，而且在工程实现上也比较简单。

其实看论文确实是最有效的，但却不是最高效的。理解运作过程也好，推导过程也好，大家的回答都是为了帮助大家更高效的掌握这门算法。大家的回答已经很好， 我这里作为补充，也是算另一个角度，帮助大家去理解paxos的数学推导过程，写了这么一篇文章：Paxos理论介绍(1): 朴素Paxos算法理论推导与证明 - 分布式一致性与高可用实践 - 知乎专栏。希望能帮到大家。

‘肆’ chubby的设计目标是什么4 paxos算法在chubby起什么作用

其实就是简单的 replica
冗余存在的目的就是为了防止挂掉
任何形式的挂掉都要防止
基本的原理异常的简单
如下：
每一个replica HDFS ，HBse 这些都有各自的replica
每一个replica都会企图在 zookeeper 的某一个目录节点获取一个锁
拿到锁的就是master ， 比如说replica（1）拿到了锁，但是需要定期的和zookeeper 交流感情，
要么就是zookeeper periodical 的ping一下，看看那个replica（1）还活着没有，要么就是replica（1）主动去报道，告诉master “ 呵呵我还活着” 这个叫 master session
其他没拿到锁的 replica (2.3.4.5.6.)就告诉 zookeeper 说：“你要是觉得那个replica（1）挂了你告诉我一声 啊！
注意： 是觉得哦！ 这里分两种可能
1） replica（1）挂了
2） network partition 把replica（1） 从网络中物理的隔开了。
这个时候其他的replica（2.3.4.5.6.) 就会再去争抢那个 master了.

这就是冗余机制 其实 hdfs的冗余机制没啥特别的 ， 主要是 作为BigTable的开源实现，NONsql数据库的特性比较重要吧

而且zookeeper 本身 作为 Google Chubby 的开源实现 ，也是通过实现 PAXOS 算法来保持 自身的 Consensus 的 只不过它是建立在 TCP 协议基础上的， 所以zookeeper吧Chubby的算法改进了一下换了个名字叫 ..total order broadcast protocol 略无耻.

所谓特点的话： 其实就是在有这个zookeeper （Chubby） 以前 Google 使用另外一种算法来保证核心锁机制的 Consensus的 .. 只是那个有很多问提， 需要有人值守 这个就是我上面为什么提到挂掉的那两种可能的原因

基本上就是这样了 。。。
你要是想学的话 Google scholar + Hadoop in action 用起来 五六个月就能有所小成了

‘伍’ paxos算法在chubby起什么作用

其实就是简单的 replica ... 冗余存在的目的就是为了防止挂掉 任何形式的挂掉都要防止 基本的原理异常的简单 如下： 每一个replica ... HDFS ，HBse 这些都有各自的replica 每一个replica都会企图在 zookeeper 的某一个目录节点获取一个锁

‘陆’ raft算法与paxos算法相比有什么优势，使用场景有什么差异

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
算法中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法，包含了一些随机输入。

‘柒’ Paxos 算法的几种算法

上面通过证明如果一个协议满足B1-B3 约束条件，那么就可以保证一致性。直接从这些约束得到preliminary protocol ，basic protocol 是preliminary protocol 的限制版，保证了一致性。complete Synod protocol 进一步限制了basic protocol ，满足一致性和过程需求（progress requirements）。下面将这三个算法的具体过程。 满足B1，牧师发起选举的编号必须满足偏序关系，有一个方法是每个发起牧师使用递增的数值作为选举编号，但这样牧师无法立即知道他们选的数值有没有被其他牧师选作选举编号已经被使用。还有一个方法是使用数字+牧师姓名作为选举编号，这样就避免了自己的选举编号被其他牧师使用。
满足B2，每次选举的法定人数必须是一个大部分集合（majority set）Q，这样任意两个选举都会有一个共同的牧师。这里大部分集合是一个灵活的选择，在原文中Lamport 使用体重打比方，体重的人更有可能呆在议会大厅，这样就可以使用体重超过一半的牧师集合作为大部分集合。至于实际情况中的大部分集合是什么要看具体情况了。
满足B3，要求每个牧师p 每次在发起选举前必须找到B_qrm 中每个牧师q 的MaxVote(b,q,B)。
根据以上要求，可以得到初始协议：
1. 牧师p 选择一个选举编号b ，并发送NextBallot(b)送给其他牧师
2. 其他牧师q 在收到NextBallot(b) 后，返回LastVote(b,v) 给牧师p，v=MaxVote(b,q,B)$是小于b 编号的q 投的最大的赞成票。为了保证B3，q 不能在b 和b_bal 之间的选举投赞成票。（如果q 在发送了LastVote(b,v)又对新的选举投票了那么v 也就不是q 投的最大赞成票）
3. 牧师p 从一个大部分集合Q 中每个牧师q 中都收到LastVote(b,v) 后，发起一个新的选举，编号为b，法定人数为Q，法律d满足B3。然后牧师p 将这个法律写在自己账目的背面，发送BeginBallot(b,d)给Q 中每个牧师。
4. 牧师q 收到BeginBallot(b,d) 后决定是否为这次选举投赞成票，如果赞同，则他将发送Vote(b,q) 给牧师p。
5. 如果牧师p 收到Q 中每个牧师q 发来的赞成票Vote(b,q)，则将法律d 写入他的账目中，并向所有q发送Success(d) 消息。
6. 收到Success(d) 消息后，牧师q 将法律d 写入到自己的账目中。
说明：第一步表示发起法律的牧师p 希望下一个选举的编号是b 。牧师q 用LastVote(b,v) 回应了牧师p 的请求，也就是向牧师p 通过法律时保证了v=MaxVote(b,q,B) 的被改变，具体来说就是不在b 和b_bal 之间的选举投赞成票。
第三步要求法律d 需要满足B3，这里我开始有点迷糊，实际系统中的值是客户端决定的，而不应该是B3 决定的。这里我们还是用上面的key-value 数据库的例子来理清下思路：当某个节点/牧师第一次发起更新前相当于B为空集，发起更新/选举的操作不断进行，直至所有法定人数（quorum）都对法律投了赞成票（即majority set 的节点都更新了该key-value 的值则认为更新成功），B3对应的就是之前的更新没有成功，那么新的选举值需要保持的情况。第四步允许牧师可以不发送Vote(b,q) 或者发送几次，对应的是发送的信息可能因为通信而失败而未发送或者被多次发送。一旦牧师投了赞成票则确认可以修改该值。
考虑到最后第六步法律d 才被牧师q 写入到账目，有可能出现的情况就是在第五步的时候牧师p 将法律写入到了自己账目中，接着发送Success(d) 给其他牧师，其中因为通信或者牧师离开议会大厅而没有被写入到自己的账目中，导致不一致。所以真正写入到账目时机应该是在第四步牧师q 在发送给牧师p 赞成票的同时就法律写入到了各自账目中。而不用考虑如何保证牧师q 第四步写入的法律会导致不一致，因为法律如果没有通过则还有更多的选举来保证一致性。后面也谈到了当法律第一次别写入到账目中算通过法律。 初始协议（Preliminary Protocol）要求每个牧师都保存 (i) 他发起的每个选举； (ii) 他投的每个赞成票； (iii) 他发送的每个$LastVote$。为了简化牧师需要保存的数据，我们对上面的协议做一个限制，得到基础（Basic Protocol）协议。首先介绍三个新的参数：
lastTried[p] 牧师p 发起的最后一个选举
prevVote[p] 牧师p 最近一次的投票
nextBal[p] 收到的选举编号的b 的最大值，即牧师p参加的最大选举编号
在初始协议中，每个牧师可以同时发起任意个选举，在基础协议中要求每个牧师只能发起一个选举lastTried[p]，一旦发起一个选举，那么之前发起选举的信息就都不重要了。在初始协议中要求每个牧师不能在b_bal 和b 之间投赞成票，在基础协议中则更严格地要求不能给小于b 的选举投赞成票。那么基础协议可以概述为下面几步：
1. 牧师p 选择一个大于lastTried[p] 的选举编号b ，发送NextBallot(b)给其他牧师
2. 牧师q 收到NextBallot(b) 且b>nextBal[q]后设置nextBal[q]=b ，接着发送LastVote(b,v) 给牧师p，其中v==prevBa[q] 。（如果b 小于或等于nextBal[q]，则不回复）
3. 从满足某个大部分集合Q 中每个牧师收到了LastVote(b,v) 信息，牧师p 发起一个编号为b ，法定人数为Q ，法律为d（满足B3 ）的选举，并将BeginBallot(b,d) 发送给Q 中每个牧师。（如果没有满足任意大部分集合Q 的牧师返回，则返回第一步）
4. 牧师q 收到BeginBallot(b,d) ，决定投赞成票，设置prevVote[p] 为这次投票，并发送Vote(b,q) 给牧师p。（如果在收到BeginBallot(b,d) 后发现b 不等于nextBal[q] 则忽略这条信息，说明这期间牧师q 还收到了其他的编号更大的选举）
5. 牧师p 从大部分集合Q 中每个牧师q 收到了Voted(b,d) ，且b==lastTried[p] ，则认为这次选举成功，将法律d 记录在账目中，并向Q 中每个牧师q 发功成功消息Success(d) 。
6. 每个牧师q 收到Success(d) 消息后将法律写入账目。
基础协议是初始协议的限制版，因为两者都对牧师没有行为要求，所以也不保证过程（QS）。下面介绍一个保证过程的协议— 完整议会协议（complete Synode protocol）。 基础协议保证了一致性却没有保证任何过程，因为它只阐述了牧师可能做什么，没有要求牧师应该做什么。为了达到之前谈到的过程需求（Qrogress Requirements），我们需要添加一些额外的要求使得牧师们尽快执行完2-6 步。
考虑一种情况如果牧师q 第二步收到的选举编号b 都比之前收到的要大，那么他就要放弃之前收到的所有选举。可是在选举编号为b 的选举在未确认前，可能又会收到更大编号的选举b’ ，这样就无法通过任何法律，过程也不能保证。所以为了达到过程需求则需要一个选举成功后再发起另一个选举。而首先应该知道服务员传递消息和牧师处理消息的时间，在网络中常常通过设置timeout 来实现，同样的如果超过了一定时间牧师没有收到服务员的回复，则认为该服务员或者对应的牧师离开了议会大厅。
假设牧师执行一个动作在7 分钟以内，服务员传递一个消息在4 分钟以内，那么一个牧师p 发送消息给牧师q ，希望其回复的时间应该是在22 分钟内（7+4+7+4 分钟）。
有了上面时间的假设，再考虑上面讨论过的情况，如果发起选举的牧师p 会在第二步和第四步期望22 分钟内收到其他牧师的回复，如果没有则可能是一些牧师或者服务员离开了议会大厅，或者还有一些牧师发起了编号更大的选举。遇到这两种情况都牧师p 应该终止本次选举，而重新开始发起一个新的选举，为了不至于新发起的选举编号还是太小而仍不能执行，需要从其他牧师哪里获取最新的选举编号，从而选取一个更大的编号发起选举。
进而假设牧师p 是唯一能够发起选举的牧师且议会大厅内有大部分集合的牧师，那么可以保证在99分钟内通过一条法律：22 分钟内发现了有更大编号的法律，22 分钟内获取最大编号并选择个更大的编号，55 分钟内完成1-6 步完成一次成功的选举（疑问：既然只有牧师p 能够发起选举，那么编号都是由其控制的，前两步发现并选择更大的编号似乎就没有必要了。答：并不是所有的选举都是president发起的，其他牧师发起选举，president向其他希望发起选举的牧师配发选举编号）。从上面的过程我们发现完整议会协议需要一个选举president的过程，president的选举算法不是文章重点，所以文章中仅用T 分钟代替了选举president的时间，这样T+99 分钟内可以通过一部法律。
文中选择president的方法是谁的姓在字母表中最后，并将自己的姓发送给议会大厅内所有牧师，如果在T-11 分钟内某个牧师没有收到比自己姓在字母表中更靠后的姓，则认为自己是president（我觉得广播体重也应该不错，不是说体重更重的呆在议会大厅会更久么？^_^）。还有一个细节：在选举president的时候每个牧师p 需要将自己的lastTried[p] 发送给其他牧师，以使得president能够在第一次选举时选择一个足够大的编号。
至此，通过选举president和设置超时，完整议会协议就可以保证过程了。
多法律国会协议
上节的议会协议（complete Synod protocol）中，president被选举出来后，每个希望发起选举的牧师通知他，president给牧师配发选举编号，每次仅通过一部法律。多法律国会协议（The Multi-Decree Parliment）选择一个president通过一系列法律，且只需要执行前两步一次即可。
具体方法是president第一步发送NextBallot(b,n) 代替NextBallot(b) ，表示希望通过n-b 之间的所有的法律，在president 的账目上，编号n 之前的法律都是连续记录了的，b>n 。其他牧师q 收到消息后将每部已经出现在其账目中编号大于$n$的法律都返回给president，不在账目上的返回正常的LastVote 信息。
下面谈到多法律国会协议有关性质，首先是法律的顺序，不同法律编号的选举同时进行，发起选举的每个牧师都认为自己是president（不知道president 是怎么选举出来的，也不知道法律通过的顺序）。在完整议会协议第三步中法律被提议，第一次写入到账目上时称法律被通过。当一个president需要提出新的法案时，他必须从大部分集合牧师中学习到那么法律他们都投了赞成票，每部法律都被大部分集合牧师中至少一个牧师投了票，所以president发起新的选举前总能学到所有之前通过了的法律。president不会在空缺的法律编号内填补重要的法律。，也不会乱序提议法律，所以协议满足“法律有序性”：如果法律A 和法律B 都是重要的法律，法律A 在法律B 提议之前通过，那么法律A 有比法律B 更低的法律编号。第二点属性是president在选举出后且没有人再进出议会大厅，法律是按照下面步骤不断通过的（对应完整议会协议的3-5步）：
3. president 向一个法定人数牧师中每个牧师发送BeginBallot ；
4.每个牧师向president 发送Voted 信息。
5.president向每个牧师发送Success 消息。这样通过每部法律只需要三次消息传递，通过合并BeginBallot 和Success 命令可以进一步减少消息传递。

‘捌’ 共识算法ByzantinePaxos（2010）是谁发明的

原始Paxos的BFT版本，在相同网络假设下存在1/3拜占庭故障节点时是安全的。这是由LeslieLamport发明的，是他最初的Paxos论文的延伸。

‘玖’ 分布式存储中，怎样使用paxos算法保证数据的一致性

在分布式系统中，我们经常遇到多数据副本保持一致的问题，在我们所能找到的资料中该问题讲的很笼统，模模糊糊的，把多个问题或分类糅合在一起，难以理解。在思考和翻阅资料后，通俗地把一致性的问题可分解为2个问题：
1、任何一次修改保证数据一致性。
2、多次数据修改的一致性。
在弱一致性的算法，不要求每次修改的内容在修改后多副本的内容是一致的，对问题1的解决比较宽松，更多解决问题2，该类算法追求每次修改的高度并发性，减少多副本之间修改的关联性，以获得更好的并发性能。例如最终一致性，无所谓每次用户修改后的多副本的一致性及格过，只要求在单调的时间方向上，数据最终保持一致，如此获得了修改极大的并发性能。
在强一致性的算法中，强调单次修改后结果的一致，需要保证了对问题1和问题2要求的实现，牺牲了并发性能。本文是讨论对解决问题1实现算法，这些算法往往在强一致性要求的应用中使用。
解决问题1的方法，通常有两阶段提交算法、采用分布式锁服务和采用乐观锁原理实现的同步方式,下面分别介绍这几种算法的实现原理。

两阶段提交算法

在两阶段提交协议中，系统一般包含两类机器（或节点）：一类为协调者（coordinator），通常一个系统中只有一个；另一类为事务参与者（participants，cohorts或workers），一般包含多个，在数据存储系统中可以理解为数据副本的个数。两阶段提交协议由两个阶段组成，在正常的执行下，这两个阶段的执行过程如下所述：
阶段1：请求阶段（commit-request phase，或称表决阶段，voting phase）。
在请求阶段，协调者将通知事务参与者准备提交或取消事务，然后进入表决过程。在表决过程中，参与者将告知协调者自己的决策：同意（事务参与者本地作业执行成功）或取消（本地作业执行故障）。
阶段2：提交阶段（commit phase）。
在该阶段，协调者将基于第一个阶段的投票结果进行决策：提交或取消。当且仅当所有的参与者同意提交事务协调者才通知所有的参与者提交事务，否则协调者将通知所有的参与者取消事务。参与者在接收到协调者发来的消息后将执行响应的操作。
举个例子：A组织B、C和D三个人去爬长城：如果所有人都同意去爬长城，那么活动将举行；如果有一人不同意去爬长城，那么活动将取消。用2PC算法解决该问题的过程如下：
首先A将成为该活动的协调者，B、C和D将成为该活动的参与者。
阶段1：A发邮件给B、C和D，提出下周三去爬山，问是否同意。那么此时A需要等待B、C和D的邮件。B、C和D分别查看自己的日程安排表。B、C发现自己在当日没有活动安排，则发邮件告诉A它们同意下周三去爬长城。由于某种原因，D白天没有查看邮件。那么此时A、B和C均需要等待。到晚上的时候，D发现了A的邮件，然后查看日程安排，发现周三当天已经有别的安排，那么D回复A说活动取消吧。
阶段2：此时A收到了所有活动参与者的邮件，并且A发现D下周三不能去爬山。那么A将发邮件通知B、C和D，下周三爬长城活动取消。此时B、C回复A“太可惜了”，D回复A“不好意思”。至此该事务终止。
两阶段提交算法在分布式系统结合，可实现单用户对文件（对象）多个副本的修改，多副本数据的同步。其结合的原理如下：
1、客户端（协调者）向所有的数据副本的存储主机（参与者）发送：修改具体的文件名、偏移量、数据和长度信息，请求修改数据，该消息是1阶段的请求消息。
2、存储主机接收到请求后，备份修改前的数据以备回滚，修改文件数据后，向客户端回应修改成功的消息。 如果存储主机由于某些原因（磁盘损坏、空间不足等）不能修改数据，回应修改失败的消息。
3、客户端接收发送出去的每一个消息回应，如果存储主机全部回应都修改成功，向每存储主机发送确认修改的提交消息；如果存在存储主机回应修改失败，或者超时未回应，客户端向所有存储主机发送取消修改的提交消息。该消息是2阶段的提交消息。
4、存储主机接收到客户端的提交消息，如果是确认修改，则直接回应该提交OK消息；如果是取消修改，则将修改数据还原为修改前，然后回应取消修改OK的消息。
5、 客户端接收全部存储主机的回应，整个操作成功。
在该过程中可能存在通信失败，例如网络中断、主机宕机等诸多的原因，对于未在算法中定义的其它异常，都认为是提交失败，都需要回滚，这是该算法基于确定的通信回复实现的，在参与者的确定回复（无论是回复失败还是回复成功）之上执行逻辑处理，符合确定性的条件当然能够获得确定性的结果哲学原理。

分布式锁服务

分布式锁是对数据被外界修改持保守态度，在整个数据处理过程中将数据处于锁定状态，在用户修改数据的同时，其它用户不允许修改。
采用分布式锁服务实现数据一致性，是在操作目标之前先获取操作许可，然后再执行操作，如果其他用户同时尝试操作该目标将被阻止，直到前一个用户释放许可后，其他用户才能够操作目标。分析这个过程，如果只有一个用户操作目标，没有多个用户并发冲突，也申请了操作许可，造成了由于申请操作许可所带来的资源使用消耗，浪费网络通信和增加了延时。
采用分布式锁实现多副本内容修改的一致性问题， 选择控制内容颗粒度实现申请锁服务。例如我们要保证一个文件的多个副本修改一致， 可以对整个文件修改设置一把锁，修改时申请锁，修改这个文件的多个副本，确保多个副本修改的一致，修改完成后释放锁；也可以对文件分段，或者是文件中的单个字节设置锁， 实现更细颗粒度的锁操作，减少冲突。
常用的锁实现算法有Lamport bakery algorithm （俗称面包店算法）， 还有Paxos算法。下面对其原理做简单概述。

Lamport面包店算法

是解决多个线程并发访问一个共享的单用户资源的互斥问题的算法。 由Leslie Lamport（英语：Leslie Lamport）发明。
Lamport把这个并发控制算法可以非常直观地类比为顾客去面包店采购。面包店只能接待一位顾客的采购。已知有n位顾客要进入面包店采购，安排他们按照次序在前台登记一个签到号码。该签到号码逐次加1。根据签到号码的由小到大的顺序依次入店购货。完成购买的顾客在前台把其签到号码归0. 如果完成购买的顾客要再次进店购买，就必须重新排队。
这个类比中的顾客就相当于线程，而入店购货就是进入临界区独占访问该共享资源。由于计算机实现的特点，存在两个线程获得相同的签到号码的情况，这是因为两个线程几乎同时申请排队的签到号码，读取已经发出去的签到号码情况，这两个线程读到的数据是完全一样的，然后各自在读到的数据上找到最大值，再加1作为自己的排队签到号码。为此，该算法规定如果两个线程的排队签到号码相等，则线程id号较小的具有优先权。
把该算法原理与分布式系统相结合，即可实现分步锁。

Paxos算法

该算法比较热门，参见WIKI，http://zh.wikipedia.org/wiki/Paxos%E7%AE%97%E6%B3%95
Paxos算法解决的问题是一个分布式系统如何就某个值(决议)达成一致。一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。一个通用的一致性算法可以应用在许多场景中，是分布式计算中的重要问题。节点通信存在两种模型：共享内存(Shared memory)和消息传递(Messages passing)。Paxos算法就是一种基于消息传递模型的一致性算法。BigTable使用一个分布式数据锁服务Chubby，而Chubby使用Paxos算法来保证备份的一致性。

采用乐观锁原理实现的同步

我们举个例子说明该算法的实现原理。如一个金融系统，当某个操作员读取用户的数据，并在读出的用户数据的基础上进行修改时（如更改用户帐户余额），如果采用前面的分布式锁服务机制，也就意味着整个操作过程中（从操作员读出数据、开始修改直至提交修改结果的全过程，甚至还包括操作员中途去煮咖啡的时间），数据库记录始终处于加锁状态，可以想见，如果面对几百上千个并发，这样的情况将导致怎样的后果。
乐观锁机制在一定程度上解决了这个问题。乐观锁，大多是基于数据版本（ Version）记录机制实现。何谓数据版本？即为数据增加一个版本标识，在基于数据库表的版本解决方案中，一般是通过为数据库表增加一个 “version” 字段来实现。读取出数据时，将此版本号一同读出，之后更新时，对此版本号加一。此时，将提交数据的版本数据与数据库表对应记录的当前版本信息进行比对，如果提交的数据版本号大于数据库表当前版本号，则予以更新，否则认为是过期数据。
对于上面修改用户帐户信息的例子而言，假设数据库中帐户信息表中有一个 version 字段，当前值为 1 ；而当前帐户余额字段（ balance ）为 $100 。
操作员 A 此时将其读出（version=1 ），并从其帐户余额中扣除 $50（$100-$50 ）。
在操作员 A 操作的过程中，操作员B也读入此用户信息（ version=1 ），并从其帐户余额中扣除 $20 （ $100-$20 ）。
操作员 A 完成了修改工作，将数据版本号加一（ version=2 ），连同帐户扣除后余额（ balance=$50 ），提交至数据库更新，此时由于提交数据版本大于数据库记录当前版本，数据被更新，数据库记录 version 更新为 2 。
操作员 B 完成了操作，也将版本号加一（ version=2 ）试图向数据库提交数据（ balance=$80 ），但此时比对数据库记录版本时发现，操作员 B 提交的数据版本号为 2 ，数据库记录当前版本也为 2 ，不满足 “ 提交版本必须大于记录当前版本才能执行更新 “ 的乐观锁策略，因此，操作员 B 的提交被驳回。这样，就避免了操作员 B 用基于 version=1 的旧数据修改的结果覆盖操作员A 的操作结果的可能。
乐观锁机制与分布式系统相结合上， 我整理了伪代码如下：
obj 操作的目标
vlaue 修改的值
atom_update_ver 每个目标上的版本，每次修改该值递增
set( obj, value)
{
//从每个节点上取出修改前的对象版本
get original_ver = obj.atom_update_ver from each node;
//将值赋到每个节点的obj目标
set obj = value from each node;
//条件修改每个节点的obj版本，目标版本加一
//比较和修改操作是原子操作
result = (set obj.atom_update_ver = original_ver + 1
where original_ver + 1 > obj.atom_update_ver
for each node);
if(result == ok)
return set_ok;
else
return set(obj, value);//不成功递归修改

该算法未考虑节点下线、失效等问题，在后续我将分析采用乐观锁原理实现一致性算法，解决问题2、节点失效、通信失败等问题。

‘拾’ Paxos怎么读，麻烦给出英文音标

Paxos读作[ˈpæksoʊs]。

Paxos

发音：[ˈpæksoʊs]

含义：Paxos（帕克索斯）算法

用法：在句子中充当主语或宾语。

例句：

The High Replication Datastore increases the number of data centers that maintain replicas of your data by using the Paxos algorithm to synchronize that data across datacenters in real time.

High Replication Datastore使用Paxos算法来实时同步跨越多个数据中心的数据，进而增加了用于维护数据复制的数据中心数量。

(10)paxos算法扩展阅读：

Paxos 算法的背景：

Paxos 算法解决的问题是一个分布式系统如何就某个值（决议）达成一致。一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点执行相同的操作序列，那么他们最后能得到一个一致的状态。

为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。一个通用的一致性算法可以应用在许多场景中，是分布式计算中的重要问题。因此从20世纪80年代起对于一致性算法的研究就没有停止过。

节点通信存在两种模型：共享内存（Shared memory）和消息传递（Messages passing）。Paxos 算法就是一种基于消息传递模型的一致性算法。