论文阅读笔记 - Paxos made simple
作者：刘旭晖 Raymond 转载请注明出处
Email：colorant at 163.com
BLOG：http://blog.csdn.net/colorant/
更多论文阅读笔记 http://blog.csdn.net/colorant/article/details/8256145
关键字
Paxos，一致性
==目标问题 ==
基本的问题就是一组进程在一个不可靠的通信环境下如何对一件事情达成一致并获知结果。常见的具体应用，比如一组节点如何决定并获知谁是主节点。
这里不可靠的环境，指的是
- 进程本身可能崩溃重启
- 进程间通过发送消息传递信息，消息可能丢失，可能失败，重发，可能延迟，但是不会是错误的
==核心思想 ==
为了方便描述和分析这个问题，做了如下定义
- 值（Valule）：要解决的问题，这里定义为选择一个值（Valule）
- 议案（Proposal）任何进程对这个值的一个提议，我们叫做一个议案
- 三种角色：提议者Proposer（提出一个议案），批准者Acceptor（同意这个议案），观察者Learner（获知结果）。一个进程可以同时兼任这几个角色。
对结果也做了一定的要求限制：
- 只有被提出过的值可以被选择
- 只有一个值可以被选择
- 一个进程不会知道一个值被选择了，除非这个值真的被选择了（也就是没有错误信息）
总体而言，问题的目标是保证，如果有一些值被提议了，那最终会有一个值会被选择通过，如果一个值被选择通过了，任一进程最终都会得知这个结果。值得注意的是，在这里，最终哪个值被选择了不重要（显然如果每个进程都坚持自己的议案，那永远不能达成一致），重要的是有一个值最终被选择了。
方案推理过程
最简单的思考是，只有一个批准者，所以提议者都把议案发给这个批准者，批准者会选择并通过他收到的第一个议案，显然，当这个批准者失效的时候，这个系统就不工作了。
那么换一种方式，有多个批准者，提议者把议案分发给他们，批准者可以接受或否决这个议案，当过半的批准者接受这个议案的时候，就认为这个议案被通过了。
我们的最终目标是希望假设即使只有一个值被一个提议者提出，最终这个值也将被选择通过。这也就要求：
- P1：批准者应该批准它收到的第一个议案（显然，如果不能保证这一点，前面的假设就可能不成立)
再来看如果有多个议案被同时提出，按照P1的要求，他们可能被不同的批准者接受，这样假设有一个批准者失效了，也可能导致任何一个议案都没有达到过半接受的条件。要能继续下去，就要求批准者应该可以批准多个议案。为了便于识别议案，我们进一步定义议案包含一个议案号码（这个号码必须是唯一的自然数）和一个值（可以相同）
这样一个值被选择通过，可以定义为一个包含这个值的议案被过半批准者接受了。我们要求只能有一个值被选择通过，但是这并不阻止我们可以允许多个议案被通过，前提是只要我们保证这些议案包含的值是一样的。这可以由以下条件保证：
- P2：如果一个包含值V的议案被通过，那么任何被通过的比这个议案号码高的议案都包含值V
由于议案要被通过，前提是至少被一个提议者接受，那么：
- P2A：如果一个包含值V的议案被通过，那么任何被接受的比这个议案号码高的议案都包含值V
我们可以通过满足P2A来满足P2。但是P1我们也是要满足的，由于消息的不可靠性，如果一个之前没有收到过任何议案的批准者收到了一个更高号码的议案包含了一个不同于V的值，按照P1他必须接受，这就违反了P2A。为了防止这种情况出现，我们要求：
- P2B：如果一个包含值V的议案被通过，那么任何被提出的比这个议案号码高的议案都包含值V
P2B显然涵盖了P2A，同时也和P1不冲突。但是如和保证P2B呢？可以通过以下条件来满足：
- P2C：对于任意一个提案号码n和值v，如果一个提案T(n)=v被提出，那么必须有一个过半的批准者集合满足，要么，他们没有接受过任何小于n的提案，要么v是他们接受过的比n小的提案中号码最大的提案的值。
简单的证明P2C包含P2B：如果一个v被通过，则任意一个过半批准者集合，至少有一个接受过v，那么只要满足P2C，递归一下，也就要求每个更高号码的议案都包含v
实现逻辑
在实际实现中，P2是不可控的，P2A不完备，P2B不具可操作性，你不可能在提出议案时预知一个议案是否被通过。而P2C则是可以实现的，只要我们要求提议者在发出提案之前得知过半批准者所接受的议案中比n小的最大号码的议案的值什么。由于消息的不确定性，我们可以知道批准者当前接受的议案的情况，但是不可能预知将来批准者所接受的议案，要保证我们得到的信息是准确的，我们不是去预测将来，而是可以要求批准者不再接受比号码n小的议案，这样提议者的运作策略可以是这样的：
提议者选择一个议案号码n，将这个议案号码分发给批准者，并要求他们回复：
- 承诺不再接受比号码n小的议案
- 他们接受过的比n小的议案中最大号码议案的值v
我们称这个过程为发出一个“准备请求”
当提议者收到过半批准者的回复后，他就可以发出正式的议案n了，议案的值是回复中最大号码的议案的值v，如果回复中没有任何议案被接受过，那么可以任意选一个值作为议案的值。我们称这个过程为发出一个“接受请求”
对于批准者，我们要求:
P1A：如果一个批准者没有回复过一个比号码n大的议案的准备请求，那么它可以接受号码n的议案的接受请求。
崩溃重启等容错：
为了满足P2C，批准者即使崩溃重启过后，也要记得他的做过的回复，所以批准者需要记录它接受过的最大号码的议案，和他回复过的最大号码的准备请求。对于提议者，它可以任意放弃它之前发送的准备请求，只要它不重复发送同样号码的议案就没有问题。
观察者：
批准者每接受一个提案后，就发送消息给每个观察者，或者，发送给一些特定观察者，再由这些观察者发送给其它观察者，以减少通讯量。观察者也可以主动询问批准者。从观察者的角度，应该只需要记录与被接受的最高号码的议案的值相同的其它议案的信息就可以了，因为按照P2A的要求可以得知被接受的号码低的议案，如果值不相同的话，是不会被通过的。
其它
个人理解，Paxos本身是一个保证议案的一致性的方案，避免单点失败的问题。但是为了高效性，一个Paxos的过程，通常还是希望保证只有一个提议者提议案，所以基本可以认为平时还是有主节点的，如果主节点失败或者别的节点认为自己是主节点时，由Paxos过程保证决策的顺利进行。
实现上的问题
这里的实现逻辑提供了一个解决冲突的方案，但是实现中，如何具体的操作这些步骤，大概会有各种各样的细节问题，尤其是要考虑到效率，稳定性，可用性等等，比如
- 如何生成唯一的议案号，如何保证各个议案号的有序性，即如何比较他们的大小？
- 每个提议者有一个分组的有序号码（比如分配一个N*i+x？N总共有几个提议者，X这个提议者第几次议案，i这个提议者的序号），每次他们都使用自己比上一个号码更大的号码
- 如何保证议案被提出，即如何驱动这一过程能进行下去？如果之前的议案被放弃，大家都在等？有什么策略保证新的议案被提出？如何驱动结果向一个议案被过半接受收敛，不会反复纠缠？
- 要有Leader提议者，由Leader提议者发起议案，但是选择Leader提议者又是一个问题，实践中，随机和timeout机制是可行的方案(原文描述，可以想象，但是不完全理解），再有如何通知大家leader是谁等，需要找个具体实现看一看。
- 效率问题，一个paxos过程最少需要两轮通讯，在很多跨区域的分布式系统中，Latency的问题就很突出，针对各种应用场合有各种的特定优化
- 各种实际系统失效问题：paxos过程中有一些假设，比如批准者要记住它作过的承诺，理论上这是靠将相关信息记录在磁盘上来实现，实际系统中，如果磁盘文件崩溃了，Paxos过程的这一假设就不成立了，需要检测和处理这种情况。
==相关研究，项目等 ==
paxos made live :基于Paxos的系统的实现，有很多工程实际问题，这篇Paper阐述了这些问题以及解决方案
Chubby :基于Paxos算法构建的一个分布式锁服务
Megastore：使用Paxos进行跨数据中心副本同步，支持多点发起更新操作
- 要有Leader提议者，由Leader提议者发起议案，但是选择Leader提议者又是一个问题，实践中，随机和timeout机制是可行的方案(原文描述，可以想象，但是不完全理解），再有如何通知大家leader是谁等，需要找个具体实现看一看。
- 如何保证议案被提出，即如何驱动这一过程能进行下去？如果之前的议案被放弃，大家都在等？有什么策略保证新的议案被提出？如何驱动结果向一个议案被过半接受收敛，不会反复纠缠？
- 每个提议者有一个分组的有序号码（比如分配一个N*i+x？N总共有几个提议者，X这个提议者第几次议案，i这个提议者的序号），每次他们都使用自己比上一个号码更大的号码
- 如何生成唯一的议案号，如何保证各个议案号的有序性，即如何比较他们的大小？
- P2C：对于任意一个提案号码n和值v，如果一个提案T(n)=v被提出，那么必须有一个过半的批准者集合满足，要么，他们没有接受过任何小于n的提案，要么v是他们接受过的比n小的提案中号码最大的提案的值。
- P2B：如果一个包含值V的议案被通过，那么任何被提出的比这个议案号码高的议案都包含值V
- P2A：如果一个包含值V的议案被通过，那么任何被接受的比这个议案号码高的议案都包含值V
- P2：如果一个包含值V的议案被通过，那么任何被通过的比这个议案号码高的议案都包含值V
- P1：批准者应该批准它收到的第一个议案（显然，如果不能保证这一点，前面的假设就可能不成立)