Skip to main content
  1. Posts/

Raft 作者出的 Paxos 的试题

·2287 字·5 分钟
计算机科学 分布式
Table of Contents

试题 #

1. #

(4 分)下面的每张图都显示了一种 Multi-Paxos 服务器上可能的日志(每个条目中的数字代表 acceptedProposal 值)。考虑每份日志都是独立的,下列日志是否可能发生在正确实现的 Multi-Paxos 中?

a.

paxosLoga

b.

paxosLogb

c.

paxosLogc

d.

paxosLogd

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 被关闭,因为它们不属于新配置。描述下这可能在系统中引起的问题。


答案 #

1. #

a. 是。

b. 是。

c. 是。

d. 是。

2. #

是。如果 S1,S2 和 S3 接受了提案 <5.1, X>,其它服务器仍然可能接受更早的提案编号的提案值 Y。

例如,S4 先发送 Prepare(3.4) 发现并没有已接受的提案值,接着 S1 发送 Prepare(5.1)到 S1,S2,S3,然后 S1,S2,S3 接受了<5.1, X>,此时 S4 仍然可能在 S4,S5 完成提案 <3.4, Y>

3. #

a. 最少只发送 1 轮 Prepare RPC,如果多数派 Prepare 都立即返回了具有 noMoreAccepted=true 的响应。

b. 最多是: Leader 节点上每有一个未 chosen 但是 Acceptor 已经接受的日志记录,就会有一轮 Prepare RPC。这发生在如果每次 Leader 为其没有 chosen 的日志发送 Prepare 请求,都发现有一个 Acceptor 已经接受了该提案值,那它就会在该条目位置采用这个提案值,然后继续尝试下一个日志条目。这样就会发生最多的轮次。

4. #

可能出现的异常行为是:服务器会标记两个不同的 chosen 值。用 2 个竞争的提案,3 节点集群和 2 个日志来举例:

  • S1 完成一轮 Prepare 发送提案编号 n=1.1, index=1 给 S1,S2
  • S1 只完成 S1(它自己)的 Accept 提案 n=1.1, value = X, index = 1
  • S2 完成一轮 Prepare 发送提案编号 n=2.2, index=1 给 S2,S3,收到二者包含 noMoreAccepted=true 的响应
  • S2 完成一轮 Accept,S2、S3 收到 n=2.2, value=Y, index=1
  • S2 标记 index 1 的日志为 chosen
  • S2 完成一轮 Accept,S1, S2, 和 S3 收到 n=2.2, value=Z, index=2, firstUnchosenIndex=2,此时,S1 将会发生异常:将 n=1.1, value=X 的日志设为 chosen,然后将 X 应用到状态机。这是不正确的,因为实际上是 Y 被 chosen。

5. #

a. 不会。因为安全性只需要提案编号唯一,每台服务器的 server_id 是唯一的,并且有自增 id,所以唯一性得到保证。

b. 会。例如,server_id 最大的服务器向集群中每一台服务器发出的 Prepare RPC 将会永远失败。然后,其它 Proposer 无法继续运行,因为其它服务器的 minProposal 对于 Proposer 来说太大了。

6. #

不安全。不同的提案必须具有不同的提案编号。下面是一个 3 节点集群的例子:

  • S1 发送 Prepare(n=1.1) 至 S1,S2
  • S1 发送 Accept(n=1.1, v=v1) 至 S1
  • S1 重启
  • S1 发送 Prepare(n=1.1) 至 S2,S3(并且发现还没有被接受的提案)
  • S1 发送 Accept(n=1.1, v=v2) 与 S2,S3
  • S1 将 v2 被 chosen 返回给客户端
  • S2 发送 Prepare(n=2.2) 至 S1,S2 并收到响应:
    • 来自 S1: acceptedProposal=1.1, acceptedValue=v1
    • 来自 S2: acceptedProposal=1.1, acceptedValue=v2
  • S2 直接选择了 v1 作为提案值
  • S2 发送 Accept(n=2.2, v=v1)至S1,S2,S3
  • S2 将 v1 被 chosen 返回给客户端

可能出现的另一个问题是,崩溃前的请求在崩溃之后才被送到:

  • S1 发送 Prepare(n=1.1) 至 S1,S2
  • S1 发送 Accept(n=1.1, v=v1) 至 S1
  • S1 发送 Accept(n=1.1) 至 S2 和 S3,但是它们并没有收到
  • S1 重启
  • S1 发送 Prepare(n=1.1) 至 S2,S3(并且发现还没有被接受的提案)
  • S1 发送 Accept(n=1.1, v=v2) 至 S2 和 S3
  • S1 将 v2 被 chosen 返回给客户端
  • 现在,S2 和 S3 收到了(之前的) Accept(n=1.1, v=v1) 请求,并且覆盖了 acceptedValue 设为 v1。现在集群的状态是 v1 被 chosen,但是客户端收到 v2 被 chosen。

7. #

用 5 个节点的 Basic Paxos 举例:

  • S1 发送 Prepare(n=1.1) 至 S1, S2, S3(并且发现没有接受的提案)
  • S5 发送 Prepare(n=2.5) 至 S3, S4, S5(并且发现没有接受的提案)
  • S5 发送 Accept(n=2.5, v=X) 至 S2, S3, S5,这时 S2 的 minProposal 应该是 2.5
  • S5 返回 X 被 chosen 给客户端
  • S1 发送 Accept(n=1.1, v=Y) 至 S2,这通常会被拒绝,但是如果 Accept 阶段未更新 S2 的 minProposal,这会被接受
  • S3 发送 Prepare(n=3.3) 至 S1, S2, S4(并且发现 n=1.1, v=Y)
  • S3 发送 Accept(n=3.3, v=Y)至 S1, S2, S3, S4, S5
  • S3 返回 Y 被 chosen 给客户端

8. #

这将导致新集群的活性(liveness)问题,因为新集群服务器上的 firstUnchosenIndex 可能小于 N+α。

例如,在最坏情况下,S3 可能永久故障了,而 S1 和 S2 则可能没有尝试将任何值同步到 S4 和 S5(仅使用本讲义中介绍的算法)。然后,S4 和 S5 将永远无法学习到日志记录第 1 到 N+α-1 所 chosen 的值,因为它们无法和 S1、S2 或 S3 进行通信。S4 和 S5 的状态机将永远无法超越其初始状态。