zookeeper-3.5--1.summary-paxos

====以下部分内容转自paxos算法,并在其中以不同颜色加以评论====

算法的内容[编辑]

要满足 P2c 的约束，proposer 提出一个提案前，首先要和足以形成多数派的 acceptors 进行通信，获得他们进行的最近一次接受(accept)的提案（prepare 过程），之后根据回收的信息决定这次提案的 value，形成提案开始投票。当获得多数 acceptors 接受(accept)后，提案获得批准(chosen)，由 proposer 将这个消息告知 learner。这个简略的过程经过进一步细化后就形成了 Paxos 算法。

在一个paxos实例中，每个提案需要有不同的编号，且编号间要存在全序关系。可以用多种方法实现这一点，例如将序数和 proposer 的名字拼接起来。如何做到这一点不在 Paxos 算法讨论的范围之内。

如果一个没有 chosen 过任何proposer提案的acceptor 在 prepare 过程中回答了一个 proposer 针对提案 n 的问题，但是在开始对 n 进行投票前，又接受(accept)了编号小于 n 的另一个提案（例如 n-1），如果 n-1 和 n 具有不同的 value，这个投票就会违背 P2c。因此在 prepare 过程中，acceptor 进行的回答同时也应包含承诺：不会再接受(accept)编号小于 n 的提案。这是对 P1 的加强：

P1a：当且仅当 acceptor 没有回应过编号大于 n 的 prepare 请求时，acceptor 接受(accept)编号为 n 的提案。

现在已经可以提出完整的算法了。

决议的提出与批准[编辑]

通过一个决议分为两个阶段：

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

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

实例[编辑]

用实际的例子来更清晰地描述上述过程:

有 A1, A2, A3, A4, A5 5位议员, 就税率问题进行决议. 议员 A1 决定将税率定为 10%, 因此它向所有人发出一个草案. 这个草案的内容是:

现有的税率是什么? 如果没有决定, 则建议将其定为 10%. 时间: 本届议会第3年3月15日; 提案者: A1

在最简单的情况下, 没有人与其竞争; 信息能及时顺利地传达到其它议员处.

于是, A2-A5 回应:

我已收到你的提案, 等待最终批准

而 A1 在收到2份回复后就发布最终决议:

税率已定为 10%, 新的提案不得再讨论本问题.

这实际上退化为二段提交协议.

现在我们假设在 A1 提出提案的同时, A5 决定将税率定为 20%:

现有的税率是什么? 如果没有决定, 则建议将其定为 20%. 时间: 本届议会第3年3月15日; 提案者: A5

草案要通过侍从送到其它议员的案头. A1 的草案将由4位侍从送到 A2-A5 那里. 现在, 负责 A2 和 A3 的侍从将草案顺利送达, 负责 A4 和 A5 的侍从则不上班. A5 的草案则顺利的送至 A3 和 A4 手中.

现在, A1, A2, A3 收到了 A1 的提案; A3, A4, A5 收到了 A5 的提案. 按照协议, A1, A2, A4, A5 将接受他们收到的提案, 侍从将拿着

我已收到你的提案, 等待最终批准

的回复回到提案者那里.

而 A3 的行为将决定批准哪一个.

情况一[编辑]

假设 A1 的提案先送到 A3 处, 而 A5 的侍从决定放假一段时间. 于是 A3 接受并派出了侍从. A1 等到了两位侍从, 加上它自己已经构成一个多数派, 于是税率 10% 将成为决议. A1 派出侍从将决议送到所有议员处:

税率已定为 10%, 新的提案不得再讨论本问题.

A3 在很久以后收到了来自 A5 的提案. 由于税率问题已经讨论完毕, 他决定不再理会. 但是他要抱怨一句:

税率已在之前的投票中定为 10%, 你不要再来烦我!

这个回复对 A5 可能有帮助, 因为 A5 可能因为某种原因很久无法与与外界联系了. 当然更可能对 A5 没有任何作用, 因为 A5 可能已经从 A1 处获得了刚才的决议.

情况二[编辑]

依然假设 A1 的提案先送到 A3 处, 但是这次 A5 的侍从不是放假了, 只是中途耽搁了一会. 这次, A3 依然会将"接受"回复给 A1. 但是在决议成型之前它又收到了 A5 的提案. 这时协议有两种处理方式:

1. 如果 A5 的提案更早, 按照传统应该由较早的提案者主持投票. 现在看来两份提案的时间一样(本届议会第3年3月15日). 但是 A5 是个惹不起的大人物. 于是 A3 回复:

我已收到您的提案, 等待最终批准, 但是您之前有人提出将税率定为 10%, 请明察.

于是, A1 和 A5 都收到了足够的回复. 这时关于税率问题就有两个提案在同时进行. 但是 A5 知道之前有人提出税率为 10%. 于是 A1 和 A5 都会向全体议员广播:

 税率已定为 10%, 新的提案不得再讨论本问题.

一致性得到了保证.

2. A5 是个无足轻重的小人物. 这时 A3 不再理会他, A1 不久后就会广播税率定为 10%.

情况三[编辑]

在这个情况中, 我们将看见, 根据提案的时间及提案者的权势决定是否应答是有意义的. 在这里, 时间和提案者的权势就构成了给提案编号的依据. 这样的编号符合"任何两个提案之间构成偏序"的要求.

A1 和 A5 同样提出上述提案, 这时 A1 可以正常联系 A2 和 A3; A5 也可以正常联系这两个人. 这次 A2 先收到 A1 的提案; A3 则先收到 A5 的提案. A5 更有权势.

在这种情况下, 已经回答 A1 的 A2 发现有比 A1 更有权势的 A5 提出了税率 20% 的新提案, 于是回复 A5 说:

我已收到您的提案, 等待最终批准.

而回复了 A5 的 A3 发现新的提案者A1是个小人物, 不予理会.

A1没有达到多数，A5达到了，于是 A5 将主持投票, 决议的内容是 A5 提出的税率 20%.

如果 A3 决定平等地对待每一位议员, 对 A1 做出"你之前有人提出将税率定为 20%" 的回复, 则将造成混乱. 这种情况下 A1 和 A5 都将试图主持投票, 但是这次两份提案的内容不同.

这种情况下, A3 若对 A1 进行回复, 只能说:

有更大的人物关注此事, 请等待他做出决定.

另外, 在这种情况下, A4 与外界失去了联系. 等到他恢复联系, 并需要得知税率情况时, 他(在最简单的协议中)将提出一个提案:

现有的税率是什么? 如果没有决定, 则建议将其定为 15%. 时间: 本届议会第3年4月1日; 提案者: A4

这时, (在最简单的协议中)其他议员将会回复:

税率已在之前的投票中定为 20%, 你不要再来烦我!

ps:这个觉得是有异议的,因为现在已经是这样了:

responser-->	A1	A2	A3	A5
获取投票数v
A1	1	1[先来先主持]	0
A5		1[A5的权重大]	1	1

所以最终A1得2票;A5得3票.

而作者说如果A3平等对待每一个proposer,那么由于先来先主持的原则,即使回复A1"你之前有人提出将税率定为 20%"也不应该出现混乱.除非我理解 错了吧;)

而此时如果权重是一样,那么将出现A1得2,A5得2,即出现"do nothing"局面.但无碍大局.

 

决议的发布[编辑]

一个显而易见的方法是当 acceptors 批准一个 value 时，将这个消息发送给所有 learner。但是这个方法会导致消息量过大。

由于假设没有 Byzantine failures，learners 可以通过别的 learners 获取已经通过的决议。因此 acceptors 只需将批准的消息发送给指定的某一个 learner，其他 learners 向它询问已经通过的决议。这个方法降低了消息量，但是指定 learner 失效将引起系统失效。

因此 acceptors 需要将 accept 消息发送给 learners 的一个子集，然后由这些 learners 去通知所有 learners。

但是由于消息传递的不确定性，可能会没有任何 learner 获得了决议批准的消息。当 learners 需要了解决议通过情况时，可以让一个 proposer 重新进行一次提案。注意一个 learner 可能兼任 proposer。

Progress 的保证[编辑]

[[1]根据上述过程当一个 proposer 发现存在编号更大的提案时将终止提案。这意味着提出一个编号更大的提案会终止之前的提案过程。如果两个 proposer 在这种情况下都转而提出一个编号更大的提案，就可能陷入活锁，违背了 Progress 的要求]。[[2]这种情况下的解决方案是选举出一个 leader，仅允许 leader 提出提案。但是由于消息传递的不确定性，可能有多个 proposer 自认为自己已经成为 leader。Lamport 在The Part-Time Parliament一文中描述并解决了这个问题。]

 ps:其中[1]不是很清楚为什么说会终止smaller 编号提案,这样不是与作者的'先来先主持'观点矛盾了?而且确实会出现 不断被打断的局面.