mysql gr_fast paxos_paxos视频

1982年，Leslie Lamport与另两人共同发表论文描述了一种计算机容错理论。为了形象的表达其中的问题，Lamport设想出了一种场景：拜占庭帝国有许多支军队，军队的将军们必须制订一个统一的行动计划——进攻或者撤退。将军们在地理上是分隔开来的，只能靠通讯员进行通讯。并且将军中存在叛徒。叛徒可以任意篡改消息，欺骗某些将军进攻或撤退。

这就是著名的“拜占廷将军问题”。理论研究显示，在一个3N+1的系统中，只有叛徒数目小于等于N的情况下，才有可能设计出一种协议，使得不管叛徒怎样作梗也能达成一致。

大多数系统在同一局域网中，消息被篡改的情况很罕见；因硬件和网络造成的消息不完整，只需简单的校验，丢弃不完整的消息即可。因此可以假设不存在拜占庭问题，也即假设所有消息都是完整的，没有被篡改的。在这种情况下需要什么样的算法保证一致性呢？

Leslie Lamport在1990年提出了理论上的解决方案，并给出了严格的数学证明。fast paxos介于阐述“拜占廷将军问题”时这种类比方式的成功，Lamport同样用心良苦地设想出了一种场景来描述这种算法面对的问题和解决的过程：

在古希腊有一个Paxos小岛，岛上以议会的形式通过法令。议会中的议员通过信使传递消息，议员和信使都是的，随时可能离开议会厅，并且信使可能重复投递消息，也可能一去不复返。议会协议要保证在这种情况下法令仍然能够正确的产生，并且不会出现冲突。

这也是Paxos算法名称的由来。于是有了《The Part-Time Parliament》这篇论文。但是论文中压根没有说Paxos小岛是虚构出来的，而是煞有介事的说是考古工作者发现了Paxos议会事务的手稿，从这些手稿猜测Paxos人议会的做法。从问题的提出到算法的推演论证，通篇贯穿了对Paxos议会历史的描述。

Paxos算法用来解决通信不可靠的分布式系统中的一致性问题。通信不可靠包括：消息会延迟、重复投递甚至丢失，但是消息不会被篡改（没有拜占庭问题）。

在《The Part-Time Parliament》中议会协议以一个基本的Synod协议为基础。Synod协议描述了在早期的宗教会议中，多个牧师在随机缺席的情况下如何通过一项法令，并能保证一致性：每个牧师用结实耐用的律簿和擦不掉的墨水来记录法令，他们会把一些重要的表决信息记在律簿的背面。律簿上的法令条目永远不会改变，但是律簿背面的备注可能会被划掉。fast paxos每个牧师p必须且只需在他的律簿后面记录如下信息：

lastTried[p]：由p试图发起的最后一个表决的编号，如果没有发起过则记录-∞

prevVote[p]：由p投票的所有表决中，编号最大的表决对应的p的投票，如果没有投过票则记录-∞

nextBal[p]：由p发出的所有LastVote(b,v)消息中，表决编号b的最大值。

基本协议的完整过程为：

(1) 牧师p选择一个比lastTried[p]大的表决编号b，设置lastTried[p]为b，然后发送NextBallot(b)消息给某些牧师。

(2) 在从p收到一个b大于nextBal[q]的NextBallot(b)消息后，牧师q将nextBal[q]设置为b，然后发送一个LastVote(b,v)消息给p，其中v等于prevVote[q]。（b<= nextBal[q]的NextBallot(b)消息将被忽略）

(3) 在从某个多数集合Q中的每个成员都收到一个LastVote(b,v)消息后，牧师p发起一个编号为b，法定人数集为Q，法令为d的新表决，其中d的选择遵守B3条件。然后他发送一个BeginBallot(b,d)消息给Q中的每一个牧师

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-29394-1.html