分布式理论(三)—— Multi Paxos算法
Basic Paxos 算法通过两轮的 Prepare/Accept 过程来确定一个值，我们称这个过程为一个 Paxos 实例 Instance。Multi Paxos 是通过 Paxos 算法来确定很多个值，并保证这些值的顺序在各个 Acceptor 节点完全一致，概括来讲就是确定一个全局顺序日志。
为了达到这个目的，Multi Paxos 需要从多个方面对 Paxos 算法进行增强。
增加日志索引
在 Multi Paxos 中，每一条日志都是 Basic Paxos 中的一个实例，在每个 Prepare 和 Accept 请求中都增加一个日志索引 index 参数，用来指定对应的日志记录，即 Prepare(n, index), Accept(n, index, value)， 每个实例按日志索引分别进行提案表决。所有的服务器日志里的每一条日志都相互独立。
Multi Paxos 允许多个 Proposer 并行提交，而每个 Proposer 有自己的日志，因此发起提交前先得协商确定全局唯一且可用的日志索引，如下图。
图中 S3 始终故障超时，S1 收到客户端请求并发起提案：
Proposer 接受到请求后，找到自己日志中第一个没有被 Chosen 成为决议的日志记录 firstUnchosenIndex，用该日志索引发送 Prepare(n, index) 请求。
如果 Acceptor 返回了某个提案，说明该条日志已被占用但还没成为决议，Proposer 继续用返回的提案完成决议选定，并设置 acceptedProposal = ∞ 无穷大，保证决议不会再被覆盖，同时更新自己的 firstUnchosenIndex，再回到第1步重新选择可用的日志索引。
如果 Prepare 请求成功，说明当前日志可用，Proposer 使用当前的请求完成提案，并返回结果给客户端。
在这种方式下，单个 Proposer 可以同时处理多个客户端请求，也就是说前一个客户端请求会找到记录3，下一个客户端请求就会找到记录4，只要我们为不同的请求使用不同的记录，它们都能以并行的方式独立运行。注意多 Proposer 并行情况下，日志可能会乱序，即时序上后发的请求最终记录在了日志靠前的位置。不过，当进入到状态机后，就必须以一定的顺序来执行命令，命令必须与它们在日志内的顺序一致，也就是说只有当记录3、4、5都完成执行后，才能执行记录6。
提升执行效率
直接通过多次执行 Basic Paxos 实例，来实现一系列值的共识，会存在以下问题：
多个 Proposer 同时提交提案，可能在准备阶段出现竞争冲突导致重试甚至活锁
每个实例都执行 2 轮 RPC 通讯（准备阶段和接受阶段）往返消息多、耗性能、延迟大
Multi Paxos 提到了一种解决竞争冲突的方式，由 Leader 作为唯一提议者，这样就不存在多个提议者同时提交提案的情况，也就不存在提案冲突的情况了。但是在 Multi Paxos 中，Leader 并不是必须的，Lamport 也没有对如何选举领导者做出约定，需要在实现的时候单独考虑，比如修改 Basic Paxos 算法进行一段时间的拒绝提交，或者直接使用 Basic Paxos 进行投票选举，或者采用基于租约的方式，当然也可以使用其他方式比如随机启动时间来解决竞争冲突问题。
Basic Paxos 中准备阶段的作用是通过提案编号 n 预占 Instance，阻止来自其他 Proposer 的旧提案。Multi Paxos 把提案编号 n 的预占作用范围扩展到了整个日志，一次 Prepare 请求就可以预占整个日志。另外 Acceptor 在返回 Prepare(n, index) 请求时，除了返回当前日志索引下已接受的提案，还会检查 n 以后的日志索引是否被占用，如果之后的日志都没有任何提案，说明之后的日志都是空的，即可用的，Acceptor 就会在回复 Prepare(n, index) 时携带一个 noMoreAccepted 标志。如果最终 Proposer 收到了超过半数的 noMoreAccepted 回复，说明在整个系统中大部分的 Acceptor 在 n 号日志之后的内容都是空的，Proposer 可以对这些节点直接发送 Accept 请求，直到被拒绝，再重新进行 Prepare。
分发完整日志
Basic Paxos 算法只保证了多数 Acceptor 节点的取值一致，并且最终决议只有 Proposer 才知道。要想保证所有节点的状态一致，就必须做到全部节点都能完整接受到日志的最新内容，并且每个节点都知道哪些日志记录已经形成了决议，可以交给状态机处理。
Multi Paxos 在分发完整日志时必须考虑各节点日志可能存在的空洞和不一致情况，前面介绍 Proposer 在发起提交前协商可用的日志索引时，已经补齐了自己的日志，将当前系统可以确定的提案都形成了决议记录在本机日志，后续通过以下步骤来将本机日志分发到所有节点：
Proposer 给全部节点发送 Accept 请求，请求中带上自己第一个没有成为决议的日志索引 firstUnchosenIndex，在达成多数派决议，同时设置 acceptedProposal = ∞ ，更新 firstUnchosenIndex，并返回客户端后，在后台仍继续重试接收剩余的回复，直到所有的 Acceptor 都回应，确保本次请求日志发送到所有节点。
Acceptor 接收到 Accept 请求后，如果发现自己维护的 firstUnchosenIndex 小于 Proposer 发送的索引值，表示 Acceptor 日志落后于 Proposer，Acceptor 就把自己日志中小于 Proposer 发送的索引且来自于该 Proposer 的提案都标记为决议，并设置 acceptedProposal = ∞ 无穷大，保证决议不再被覆盖，同时更新自己的 firstUnchosenIndex。要注意的是，只能标记来自于当前 Proposer 的提案，由于不同 Proposer 拥有的信息不同且可以同步提交，不区分 Proposer 直接标记的话会导致冲突，也就是说 Proposer 只能批准由自己发起的提案。
但是 Acceptor 没有成为决议的日志里可能有日志空洞，或来自故障 Proposer 的提案，这些都需要更新，所以 Acceptor 返回接受请求时会带上自己最新的 firstUnchosenIndex，尝试从当前 Proposer 上获取已经形成决议的日志更新。
Proposer 收到 Acceptor 返回的日志索引后，发现比自己的 firstUnchosenIndex 小，说明 Acceptor 上的该日志需要更新，就在后台发送一个 Success(n, index, value) 请求，将自己该位置的决议同步给 Acceptor，Acceptor 更新日志记录后再次返回最新的 firstUnchosenIndex，直到和 Proposer 的值相等。
最终所有服务器里的日志都完整一致，每个节点都知道所有已选定的日志记录，保证了系统内状态的完整统一。
留个思考题：上图中最后的 firstUnchosenIndex 是几？
客户端交互
客户端第一个请求可以发送给任意节点，该节点负责将请求重定向给 Leader。Leader 直到日志记录被 chosen 成为决议，并且被 Leader 的状态机执行后才返回响应给客户端。
客户端会一直和 Leader 交互，直到无法再联系上它（例如请求超时）。在这种情况下，客户端会联系其它任意节点，当集群出现新的 Leader 后，请求将再次被重定向到实际的 Leader。
但这存在一个问题，如果旧 Leader 已经成功执行了命令，但在回复客户端之前宕机了。客户端会认为请求失败，并在新 Leader 下重试请求。这样就可能会导致相同的命令被执行两次，这是不允许发生的，我们需要保证的是每个命令都仅执行一次。
为此客户端要为每个请求增加一个唯一 id，服务器将该 id 与命令一起保存到日志记录中。状态机在执行命令之前，会根据 id 检查该命令是否被执行过。
集群配置变更
分布式集群不可避免会有规模变化或节点变动，这些变更会影响 Paxos 的仲裁过程，导致最终结果出现混乱。
为了保证在任何时候都不会出现两种重叠的集群配置，Multi Paxos 用日志来管理集群配置变更，每一次的配置结果作为日志的一条记录存储，并与其他的日志记录一同被复制同步。 同时，Multi Paxos 增加了一个系统参数 α，来决定日志中记录的集群配置，从它本身的索引后多少个记录才开始生效。
如上图中C0、C1、C2 表示不同的集群配置， α=3，那么日志1记录的配置 C1 直到第4条日志表决过程中才会生效，C2 从第6条日志开始生效，而 C1、C2 本身的表决过程用的则是更早的配置 C0。
α 同时也限定了整个系统的并发数量，因为在索引 i 到 i+α-1 中间可能会有新的配置变更，导致处于 i+α 及以后的日志使用的集群配置是不确定的，不能被提前使用，所以系统最大的并发数只能是 α。当 α 为 1 时，系统就变成了序列化的了；但是 α 太大了，例如 1000，那么新的配置会过很久才能生效，所以 α 值需要根据实际情况设置。
为了让配置变更能尽快生效，可以在配置变更日志选定后，Proposer 主动发送 noop 空日志将配置变更后的 α 个日志记录都填满，从而快速达到新配置生效条件。
最后总结一下 Multi Paxos 的核心思想：
Multi Paxos 不是一个严格的算法，而是一种思想，可以有多种实现方案
给出了分布式日志状态机的核心理论，就分布式系统内一系列值达成共识
允许多节点并行提交请求
可以容忍半数以下的 Acceptor 出现故障
可以保证每个节点的数据一致
支持集群本身的在线配置变更