Raft 作者出的 Paxos 试题，看看你能得多少分？

感谢 Diego 和 John 允许翻译。

作为一个“小镇做题家”，我坚定不移地认为做题能帮助理解知识。

1. (4 分）下面的每张图都显示了一台 Multi-Paxos 服务器上可能存储的日志（每个条目中的数字代表 acceptedProposal 值）。考虑每份日志都是独立的，下列日志是否可能发生在正确实现的 Multi-Paxos 中？

2. (6 分) 对于 Basic Paxos，假设一个集群有 5 台服务器，其中 3 台接受了(accepted)提案编号 5.1 和对应的提案值 X，在这种情况下，集群中的任意服务器是否有可能接受不同的值 Y ？解释你的答案。

3. (10 分) 假设 Multi-Paxos 集群选出了一个节点作为 Leader，而且没有其它 Leader。此外，假设该节点继续担任一段时间的 Leader，为日志 chosen 了很多命令，并且在这期间依然没有其它节点试图担任 Leader。

a. 在此期间，该节点最少要发送多少轮 Prepare RPC？给出解释，且尽可能精确。

b. 在此期间，该节点最多要发送多少次 Prepare RPC？给出解释，且尽可能精确。

4. (5 分) 当一个 Acceptor 使用 Proposer 提供的 firstUnchosenIndex 来标记被 chosen 的日志记录时，它必须先检查日志记录中的提案编号（acceptedProposal[i] == request.proposal）。假设它跳过了这一检查：请描述一个系统异常的情况。

5. (5 分) 假设提案编号的两个部分（自增 id 和唯一 server_id）进行了互换，即 server_id 位于高位。

a. 这会影响 Paxos 的安全性（Safety）吗？请简单解释你的答案。

b. 这会影响 Paxos 的活性（Liveness）吗？请简单解释你的答案。

6. (10 分) 假设一个 Proposer 以初始值 v1 运行 Basic Paxos，但是它在协议执行过程中或执行后的某个（未知）时间点宕机了。假设该 Proposer 重新启动并从头开始运行协议，使用之前使用的相同的提案编号，但初始值为 v2，这样安全吗？请解释你的答案。

7. (10 分) 在一个成功的 Accept RPC 中，Acceptor 将其 minProposal 设为 n（Accept RPC 中的提案编号）。描述一个这样做实际上改变了 minProposal 值的场景（即 minProposal 还没有等于 n）。描述如果没有这段代码，系统将出现异常行为的场景。

8. (10 分) 考虑 Multi-Paxos 的配置变更，旧配置由服务器 1、2 和 3 组成，新配置由服务器 3、4 和 5 组成。假设新配置在日志中第 N 条被 chosen，同时日志记录 N 到 N+α (含)也都被 chosen。假设此时旧服务器 1 和 2 被关闭，因为它们不属于新配置。描述下这可能在系统中引起的问题。

欢迎关注我的公众号，查看答案。

"Paxos/Raft user study" by Diego Ongaro and John Ousterhout is licensed under CC BY 4.0