Raft 作者出的 Paxos 的試題，看看你能得多少分？
(4 分）下面的每張圖都顯示了一種 Multi-Paxos 服務(wù)器上可能的日志（每個(gè)條目中的數(shù)字代表?acceptedProposal?值）?？紤]每份日志都是獨(dú)立的，下列日志是否可能發(fā)生在正確實(shí)現(xiàn)的 Multi-Paxos 中？
a.?
b.?
c.?
d.?
答案：
a. 是。
b. 是。
c. 是。
d. 是。
(6 分) 對(duì)于 Basic Paxos，假設(shè)一個(gè)集群有 5 臺(tái)服務(wù)器，其中 3 臺(tái)接受了(accepted)提案編號(hào) 5.1 和對(duì)應(yīng)的提案值 X，在這種情況下，集群中的任意服務(wù)器是否有可能接受不同的值 Y ？解釋你的答案。
答案：
是。如果 S1，S2 和 S3 接受了提案 <5.1, X>，其它服務(wù)器仍然可能接受更早的提案編號(hào)的提案值 Y。
例如，S4 先發(fā)送 Prepare(3.4) 發(fā)現(xiàn)并沒(méi)有已接受的提案值，接著 S1 發(fā)送 Prepare（5.1）到 S1，S2，S3，然后 S1，S2，S3 接受了<5.1, X>，此時(shí) S4 仍然可能在 S4，S5 完成提案 <3.4, Y>
(10 分) 假設(shè) Multi-Paxos 集群選出了一個(gè)節(jié)點(diǎn)作為 Leader，而且沒(méi)有其它 Leader。此外，假設(shè)該節(jié)點(diǎn)繼續(xù)擔(dān)任一段時(shí)間的 Leader，為日志 chosen 了很多命令，并且在這期間依然沒(méi)有其它節(jié)點(diǎn)試圖擔(dān)任 Leader。a. 在此期間，該節(jié)點(diǎn)最少要發(fā)送多少輪?Prepare RPC？給出解釋?zhuān)冶M可能精確。? ? ?b. 在此期間，該節(jié)點(diǎn)最多要發(fā)送多少次?Prepare RPC？給出解釋?zhuān)冶M可能精確。
答案：
a. 最少只發(fā)送 1 輪?Prepare RPC，如果多數(shù)派 Prepare 都立即返回了具有?noMoreAccepted=true?的響應(yīng)。
b. 最多是：Leader 節(jié)點(diǎn)上每有一個(gè)未 chosen 但是 Acceptor 已經(jīng)接受的日志記錄，就會(huì)有一輪?Prepare RPC。這發(fā)生在如果每次 Leader 為其沒(méi)有 chosen 的日志發(fā)送?Prepare?請(qǐng)求，都發(fā)現(xiàn)有一個(gè) Acceptor 已經(jīng)接受了該提案值，那它就會(huì)在該條目位置采用這個(gè)提案值，然后繼續(xù)嘗試下一個(gè)日志條目。這樣就會(huì)發(fā)生最多的輪次。
(5 分) 當(dāng)一個(gè) Acceptor 使用 Proposer 提供的?firstUnchosenIndex?來(lái)標(biāo)記被 chosen 的日志記錄時(shí)，它必須先檢查日志記錄中的提案編號(hào)（acceptedProposal[i] == request.proposal）。假設(shè)它跳過(guò)了這一檢查：請(qǐng)描述一個(gè)系統(tǒng)異常的情況。
答案：
可能出現(xiàn)的異常行為是：服務(wù)器會(huì)標(biāo)記兩個(gè)不同的 chosen 值。用 2 個(gè)競(jìng)爭(zhēng)的提案，3 節(jié)點(diǎn)集群和 2 個(gè)日志來(lái)舉例：
?S1 完成一輪 Prepare 發(fā)送提案編號(hào) n=1.1, index=1 給 S1，S2?S1 只完成 S1（它自己）的 Accept 提案 n=1.1, value = X, index = 1?S2 完成一輪 Prepare 發(fā)送提案編號(hào) n=2.2, index=1 給 S2，S3，收到二者包含?noMoreAccepted=true?的響應(yīng)?S2 完成一輪 Accept，S2、S3 收到 n=2.2, value=Y, index=1?S2 標(biāo)記 index 1 的日志為 chosen?S2 完成一輪 Accept，S1, S2, 和 S3 收到 n=2.2, value=Z, index=2, firstUnchosenIndex=2，此時(shí)，S1 將會(huì)發(fā)生異常：將 n=1.1, value=X 的日志設(shè)為 chosen，然后將 X 應(yīng)用到狀態(tài)機(jī)。這是不正確的，因?yàn)閷?shí)際上是 Y 被 chosen。
(5 分) 假設(shè)提案編號(hào)的兩個(gè)部分（自增 id 和唯一 server_id）進(jìn)行了互換，即?server_id?位于高位。a. 這會(huì)影響 Paxos 的安全性（Safety）嗎？請(qǐng)簡(jiǎn)單解釋你的答案。b. 這會(huì)影響 Paxos 的活性（Liveness）嗎？請(qǐng)簡(jiǎn)單解釋你的答案。
答案：
a. 不會(huì)。因?yàn)榘踩灾恍枰岚妇幪?hào)唯一，每臺(tái)服務(wù)器的 server_id 是唯一的，并且有自增 id，所以唯一性得到保證。
b. 會(huì)。例如，server_id 最大的服務(wù)器向集群中每一臺(tái)服務(wù)器發(fā)出的?Prepare RPC?將會(huì)永遠(yuǎn)失敗。然后，其它 Proposer 無(wú)法繼續(xù)運(yùn)行，因?yàn)槠渌?wù)器的?minProposal?對(duì)于 Proposer 來(lái)說(shuō)太大了。
(10 分) 假設(shè)一個(gè) Proposer 以初始值 v1 運(yùn)行 Basic Paxos，但是它在協(xié)議執(zhí)行過(guò)程中或執(zhí)行后的某個(gè)（未知）時(shí)間點(diǎn)宕機(jī)了。假設(shè)該 Proposer 重新啟動(dòng)并從頭開(kāi)始運(yùn)行協(xié)議，使用之前使用的相同的提案編號(hào)，但初始值為 v2，這樣安全嗎？請(qǐng)解釋你的答案。
答案：
不安全。不同的提案必須具有不同的提案編號(hào)。下面是一個(gè) 3 節(jié)點(diǎn)集群的例子：
?S1 發(fā)送?Prepare(n=1.1)?至 S1，S2?S1 發(fā)送?Accept(n=1.1, v=v1)?至 S1?S1 重啟?S1 發(fā)送?Prepare(n=1.1)?至 S2，S3（并且發(fā)現(xiàn)還沒(méi)有被接受的提案）?S1 發(fā)送?Accept(n=1.1, v=v2)?與 S2，S3?S1 將 v2 被 chosen 返回給客戶(hù)端?S2 發(fā)送?Prepare(n=2.2)?至 S1，S2 并收到響應(yīng)：
?來(lái)自 S1: acceptedProposal=1.1, acceptedValue=v1?來(lái)自 S2: acceptedProposal=1.1, acceptedValue=v2
?S2 直接選擇了 v1 作為提案值?S2 發(fā)送?Accept(n=2.2, v=v1)至S1，S2，S3?S2 將 v1 被 chosen 返回給客戶(hù)端
可能出現(xiàn)的另一個(gè)問(wèn)題是，崩潰前的請(qǐng)求在崩潰之后才被送到：
?S1 發(fā)送?Prepare(n=1.1)?至 S1，S2?S1 發(fā)送?Accept(n=1.1, v=v1)?至 S1?S1 發(fā)送?Accept(n=1.1)?至 S2 和 S3，但是它們并沒(méi)有收到?S1 重啟?S1 發(fā)送?Prepare(n=1.1)?至 S2，S3（并且發(fā)現(xiàn)還沒(méi)有被接受的提案）?S1 發(fā)送?Accept(n=1.1, v=v2)?至 S2 和 S3?S1 將 v2 被 chosen 返回給客戶(hù)端?現(xiàn)在，S2 和 S3 收到了（之前的）?Accept(n=1.1, v=v1)?請(qǐng)求，并且覆蓋了 acceptedValue 設(shè)為 v1。現(xiàn)在集群的狀態(tài)是 v1 被 chosen，但是客戶(hù)端收到 v2 被 chosen。
(10 分) 在一個(gè)成功的?Accept RPC?中，Acceptor 將其?minProposal?設(shè)為 n（Accept RPC?中的提案編號(hào)）。描述一個(gè)這樣做實(shí)際上改變了?minProposal?值的場(chǎng)景（即?minProposal?還沒(méi)有等于 n）。描述如果沒(méi)有這段代碼，系統(tǒng)將出現(xiàn)異常行為的場(chǎng)景。
答案：
用 5 個(gè)節(jié)點(diǎn)的 Basic Paxos 舉例：
?S1 發(fā)送?Prepare(n=1.1)?至 S1, S2, S3（并且發(fā)現(xiàn)沒(méi)有接受的提案）?S5 發(fā)送?Prepare(n=2.5)?至 S3, S4, S5（并且發(fā)現(xiàn)沒(méi)有接受的提案）?S5 發(fā)送?Accept(n=2.5, v=X)?至 S2, S3, S5，這時(shí) S2 的?minProposal?應(yīng)該是 2.5?S5 返回 X 被 chosen 給客戶(hù)端?S1 發(fā)送?Accept(n=1.1, v=Y)?至 S2，這通常會(huì)被拒絕，但是如果 Accept 階段未更新 S2 的?minProposal，這會(huì)被接受?S3 發(fā)送?Prepare(n=3.3)?至 S1, S2, S4（并且發(fā)現(xiàn) n=1.1, v=Y）?S3 發(fā)送?Accept(n=3.3, v=Y)至 S1, S2, S3, S4, S5?S3 返回 Y 被 chosen 給客戶(hù)端
(10 分) 考慮 Multi-Paxos 的配置變更，舊配置由服務(wù)器 1、2 和 3 組成，新配置由服務(wù)器 3、4 和 5 組成。假設(shè)新配置在日志中第 N 條被 chosen，同時(shí)日志記錄 N 到 N+α (含)也都被 chosen。假設(shè)此時(shí)舊服務(wù)器 1 和 2 被關(guān)閉，因?yàn)樗鼈儾粚儆谛屡渲谩Ｃ枋鱿逻@可能在系統(tǒng)中引起的問(wèn)題。
答案：
這將導(dǎo)致新集群的活性(liveness)問(wèn)題，因?yàn)樾录悍?wù)器上的?firstUnchosenIndex?可能小于 N+α。
例如，在最壞情況下，S3 可能永久故障了，而 S1 和 S2 則可能沒(méi)有嘗試將任何值同步到 S4 和 S5（僅使用本講義中介紹的算法）。然后，S4 和 S5 將永遠(yuǎn)無(wú)法學(xué)習(xí)到日志記錄第 1 到 N+α-1 所 chosen 的值，因?yàn)樗鼈儫o(wú)法和 S1、S2 或 S3 進(jìn)行通信。S4 和 S5 的狀態(tài)機(jī)將永遠(yuǎn)無(wú)法超越其初始狀態(tài)。
"Paxos/Raft user study" by Diego Ongaro and John Ousterhout is licensed under?CC BY 4.0
推薦閱讀