Paxos Made Simple 读后感
近来在Cousera上学习 Cloud Computing Concept Part 1，其中涉及到了对Paxos算法的介绍。Paxos算法固然是比较难懂的，但是幸好有简化版论文 Paxos Made Simple，相对好理解很多，分享一下自己的理解。
Paxos算法的问题背景
分布式系统进程模型：多个分布式进程节点，彼此只能通过网络消息通信；整个系统是异步的，时钟可能不同步，时间流速也可能不同，消息可能丢失，乱序到达，也可能无限延迟，任一进程可能失败退出（但是至少超过半数节点存活并可以互相通信）。
分布式一致性问题：分布式系统中每个进程都有一个变量y，最初处于为未初始化状态，一旦变量y的值被确定，就不允许被修改；经过有限步骤，使得所有活着的进程都确定同一个y值，这就是一致性问题
简单说明
- Paxos 算法可以简单分为两个阶段，Prepare和Accept, 分别用于收集选票和提案
- 有两种进程角色（Proposer和Acceptor，简称P和A），P在收集到足够多选票的情况下发起提案，A则负责投票和接受提案
Prepare阶段
P选定一个全新的序号n，发起一个Prepare请求；A收到Prepare请求，如果请求中的序号n大于过去收到的n，那么A需要记录最新n值，返回Promise信息，并附带最近一次Accept阶段接收的序号和值（如果没有则不需要）；P需要等待A返回的Promise信息，如果超过半数则进入下一阶段，否则可以尝试发起新一轮Paxos。
Accept阶段
P从上一阶段Promise信息中找出序号最大的Accept值，并用它发起Accept请求，如果所有Promise都不包含Accept值，那么P可以自行选择一个值；A收到Accept请求，如果请求中的序号等于当前序号n则写入日志并返回OK；如果P收到超过半数OK，说明超过半数都接受了结果，否则可以尝试发起新一轮Paxos。
容错分析
正常情况下：Prepare阶段全票通过，Accept阶段全部OK，这是最理想的情况，无须多言；Paxos 算法在复杂的分布式环境下依然有很好的容错性，这是我们需要学习的地方。
要做容错分析，我们先整理一下分布式系统中可能遇到的错误：
- 消息延迟：消息经过一段时间的延迟以后才送达
- 消息重传：为了避免消息丢失而再次传递相同消息
- 消息乱序：历史消息乱序到达，某种意义上是由于延迟/重传造成的
- 消息丢失：由于网络分区，消息无法送达
- 进程退出：由于某些外部因素，进程崩溃退出
- 消息错误，存储错误或算法之外的步骤等：这类拜占庭问题不在我们的考虑范畴
整体而言，错误可以分为两类：
- 网络分区（丢失）：消息丢失属于网络分区的范畴，进程退出的直接结果就是消息丢失，因此也可以归于网络分区问题，如果网络延迟比较大的情况消息延迟就等同于丢失了，即使后续收到了也和消息重传等效，因此消息延迟也属于网络分区
- 消息重传（重复）：消息延迟，消息乱序和消息重传也可以看作是等效的，都可以通过超时重传机制达成同样的效果
因此，Paxos算法的容错性其实就是对消息丢失与重复的容错
消息丢失
Paxos可以在网络分区的前提下仍然达成共识（至少有半数以上节点存活且属于同一分区），并且共识一旦达成就不再改变，非常安全，非常适合做事务性协议基础。简单而言，Paxos在任何阶段如果超过半数消息丢失，都是直接发起新一轮Paxos。接下来，详细列出不同阶段对消息丢失的处理原因。
| 阶段 | 消息丢失场景 | 处理方式 |
|---|---|---|
| Prepare请求 | P当前所处分区可能是少数派，没有足够多A可以接收到该请求，见图(a) | P无法得到足够多的选票，随机等待一段时间，开始下一轮Paxos即可。如果P一直处于少数派，那么它将永远无法获得足够多的选票，永远停留在这个Prepare阶段 |
| Promise接收 | Prepare请求被大多数节点都收到了，但是只收到了少数Promise消息，这个情况意味着网络分区发生了变化，P从多数派分区变成少数派分区，见图(b) | P无法得到足够多的选票，需要开启下一轮Paxos |
| Accept请求 | P所在分区属于少数派，没有足够的A可以收到Accept请求，与图(a)类似，就不再单独出图 | P无法得到足够多的OK响应，那么P需要重新发起新一轮Paxos |
| OK响应 | 已经有超过半数的节点接受了Accept请求，但是P所在分区变成了少数派，OK响应丢失，见图(c) | 在Paxos的设计中，只要超过半数的节点接受了Accept请求，那么事实上就已经达成了实质性的共识。Paxos不需要仰赖OK消息的稳定性，即使这些OK响应都丢失了，即使P没有收到OK响应，也没有关系，它仍然可以确保未来每一轮Paxos都会使用这个实质性共识里的值。 |
那么更具体而言，如果所有OK响应丢失了，Paxos是如何确保共识的值不会再被新的值覆盖呢？它的安全性如何得到保障？请注意，Promise响应除了有选票的作用外，还附带了最近一次Accept的值的信息。因此，即使OK响应丢失了，下一轮Paxos发起的时候，P仍然可以通过Promise消息得到上一轮被Accept的值，P会继续使用这个值发起Accept请求，而不是其他值。因此，通过重试和Promise机制，解决了消息丢失导致的共识覆盖问题。
消息重复
对于重复或者迟到的消息，也会对一致性共识造成一定干扰，Paxos对此也有防御措施：Paxos中的进程都会记录一个n值，代表了当前Paxos的轮次序号。如果消息中的n值小于进程里的n值，这个消息会被认为是重复/延迟/乱序到达的消息，因此会被忽略。接下来，具体列出不同阶段对消息重复的处理
| 阶段 | 消息重复场景 | 处理方式 |
|---|---|---|
| Prepare请求 | Prepare消息的重传/延迟/乱序，或者另一个P正好也使用这个序号n,见图(d) | 如果A接收到的Prepare消息里的n值小于等于A存储的n值，那么A会忽略或拒绝它。在P看来这种处理方式就是发生了网络分区，但是不影响A的处理方式 |
| Promise接收 | 响应内容的重复可以忽略 | |
| Accept请求 | Accept消息的重传/延迟/乱序，或者另一个P发起了更高序号的Prepare请求,见图(e) | 如果Accept请求里的n值小于A存储的n值，那么A会拒绝这个请求。对于第二种情况，两个P分别处于Prepare/Accept阶段轮转，他们会互相干扰，导致Acceptor在不断更新n值，不断拒绝Accept请求，导致无法达成最终的共识，这也是所谓的活锁问题。活锁问题可以用选主加随机的方式解决 |
| OK响应 | 响应内容的重复可以忽略 |
