?
目錄
前言
定義 slowdown
為什么現(xiàn)有的共識(shí)協(xié)議無(wú)法容忍 slowdown
Copilot 如何處理 slowdown
設(shè)計(jì)
模型?
排序
Client 同時(shí)發(fā)送指令至 pilot 與 copilot
Pilot 提議指令與其初始依賴(lài)
節(jié)點(diǎn)回復(fù) FastAccept
Pilot 嘗試通過(guò) fast path 來(lái) commit 該指令
Pilot 在 Accept 階段最終確定依賴(lài)?
執(zhí)行
Copilot 最終合并后的指令順序?
依序執(zhí)行?
去重執(zhí)行并回復(fù)?
Fast Takeover
entry 內(nèi)容的恢復(fù)過(guò)程
觸發(fā) Fast Takeover
額外設(shè)計(jì)?
Copilot 能達(dá)到 1-slowdown-tolerant 的原因
優(yōu)化
Ping-Pong Batching
Null Dependency Elimination
總結(jié)
論文原文：Tolerating Slowdowns in Replicated State Machines using Copilots
以下內(nèi)容是對(duì)這篇論文的閱讀總結(jié)，以及部分重要章節(jié)（§3 Design、§5 Optimizations）的翻譯。
前言
現(xiàn)有的分布式狀態(tài)機(jī)共識(shí)協(xié)議，不論其是何種流派，何種實(shí)現(xiàn)，都在模型中將節(jié)點(diǎn)狀態(tài)抽象為僅有“在線(xiàn)”與“下線(xiàn)”兩種情況。然而在實(shí)踐上，節(jié)點(diǎn)狀態(tài)并非只有這兩種互斥的狀態(tài)——節(jié)點(diǎn)可能因配置錯(cuò)誤，節(jié)點(diǎn)側(cè)網(wǎng)絡(luò)問(wèn)題，部分硬件出現(xiàn)問(wèn)題，垃圾回收事件，以及其它很多原因而導(dǎo)致響應(yīng)速度變慢（slowdown）。由于現(xiàn)有的共識(shí)算法沒(méi)有很好地處理這一狀態(tài)，系統(tǒng)內(nèi)一個(gè)節(jié)點(diǎn) slowdown 可能導(dǎo)致整個(gè)系統(tǒng)的響應(yīng)速度變慢。Copilot 協(xié)議旨在解決這一問(wèn)題：它可以在任何情況下可以容忍系統(tǒng)中 1 個(gè)節(jié)點(diǎn)發(fā)生 slowdown（1-slowdown-tolerant）。
定義 slowdown
要想解決這一問(wèn)題，首先要對(duì) slowdown 進(jìn)行明確的定義。
首先要定義一個(gè)節(jié)點(diǎn)的處理速度。一個(gè)節(jié)點(diǎn)從收到一條消息開(kāi)始，到其處理這條消息完畢，將回復(fù)送出為止，這段時(shí)間的長(zhǎng)短就是一個(gè)節(jié)點(diǎn)的處理速度。這段時(shí)間不包含消息在網(wǎng)絡(luò)鏈路上的傳輸時(shí)間，僅包含消息在節(jié)點(diǎn)本機(jī)處理所需的時(shí)間。假設(shè)一個(gè)節(jié)點(diǎn)處理一條消息的典型時(shí)間為 1ms，而設(shè)置超時(shí)閾值 t = 10ms，那么如果該節(jié)點(diǎn)處理一條消息花費(fèi)了大于 10ms，就說(shuō)明該節(jié)點(diǎn)出現(xiàn)了 slowdown。出錯(cuò)（failed）的節(jié)點(diǎn)一定是 slowdown 的，但 slowdown 的節(jié)點(diǎn)不一定 failed——它只是響應(yīng)速度變慢，而不是停止響應(yīng)。
下面定義?s-slowdown-tolerance。當(dāng)一個(gè)系統(tǒng)中有 s 個(gè)節(jié)點(diǎn)發(fā)生 slowdown 時(shí)，系統(tǒng)仍能正常地提供服務(wù)，那么這個(gè)系統(tǒng)就是 s-slowdown-tolerance。假設(shè)一個(gè)分布式狀態(tài)機(jī)系統(tǒng)有節(jié)點(diǎn)集 {r1, ..., rs, ..., rn}，且根據(jù)目前的 “slowdown” 定義排序，其中 {r1, ..., rs} 是最慢的節(jié)點(diǎn)。定義當(dāng)前整個(gè)系統(tǒng)的處理速度為 T，并定義 T' 為將系統(tǒng)中節(jié)點(diǎn) {r1, ..., rs} 全部替換為 rs + 1 時(shí)整個(gè)系統(tǒng)的處理速度。如果 T 與 T' 的差值接近 0，那么該系統(tǒng)就是 s-slowdown-tolerance。換句話(huà)講，就是系統(tǒng)中出現(xiàn) s 個(gè)節(jié)點(diǎn) slowdown 不會(huì)影響整個(gè)系統(tǒng)的處理速度。
為什么現(xiàn)有的共識(shí)協(xié)議無(wú)法容忍 slowdown
一個(gè)分布式狀態(tài)機(jī)系統(tǒng)在處理一條客戶(hù)端指令時(shí)，如果在處理過(guò)程中的任意時(shí)間點(diǎn)，只有一條路徑可走，那么該系統(tǒng)就存在“單點(diǎn)故障”的可能性——在這點(diǎn)處負(fù)責(zé)處理的節(jié)點(diǎn)發(fā)生 slowdown 會(huì)影響整個(gè)節(jié)點(diǎn)的處理速度。
Multi-Paxos
在 Multi-Paxos 系統(tǒng)中，所有客戶(hù)端指令會(huì)通過(guò) leader 處理，而 leader 可能會(huì) slowdown 甚至 failed，此時(shí)系統(tǒng)的整體處理速度就會(huì)降低。
EPaxos
在 EPaxos 系統(tǒng)中，客戶(hù)端指令會(huì)通過(guò)與之通信的節(jié)點(diǎn)處理，如果此節(jié)點(diǎn) slowdown，系統(tǒng)的整體處理速度就會(huì)降低。
Copilot 如何處理 slowdown
根據(jù)上一節(jié)，只要保證 在處理一條客戶(hù)端指令過(guò)程中的任意時(shí)間點(diǎn)，都有大于等于 s + 1 條路徑處理該條客戶(hù)端指令，那么該系統(tǒng)就是 s-slowdown-tolerant。
Copilot 容忍一個(gè)節(jié)點(diǎn) slowdown，因此需要在處理客戶(hù)端指令時(shí)有兩條路徑。
?
設(shè)計(jì)
本節(jié)內(nèi)容是對(duì)論文 §3 Design 的翻譯。
Copilot 的設(shè)計(jì)核心是同時(shí)使用兩個(gè) leader 互為冗余地處理每一條 client 指令。兩個(gè) leader 為 pilot (P) 與 copilot (P')。
模型?
- crash failure model - 出錯(cuò)的節(jié)點(diǎn)會(huì)停止發(fā)送與相應(yīng)信息，無(wú)拜占庭錯(cuò)誤
- 異步 - 執(zhí)行指令與傳遞消息所需的時(shí)間沒(méi)有限制，消息可能會(huì)延遲、亂序甚至丟失?
- 容忍 2f + 1 個(gè)節(jié)點(diǎn)中出現(xiàn) f 個(gè)錯(cuò)誤并保證指令執(zhí)行的線(xiàn)性順序?
- 可容忍 1 個(gè)節(jié)點(diǎn)發(fā)生 slowdown
排序
?
?
在 Copilot 排序中，pilot 與 copilot 都會(huì)收到 client 的指令并各自放入其 log 記錄中，兩者協(xié)調(diào)后得到最終順序。pilot log 與 copilot log 通過(guò) 依賴(lài) 進(jìn)行排序。依賴(lài)是指：應(yīng)在執(zhí)行某條指令前完成執(zhí)行的指令。在提議階段，pilot 與 copilot 會(huì)提出被排序指令的初始依賴(lài)。節(jié)點(diǎn)要么同意收到提議中的依賴(lài)順序，要么回復(fù)其認(rèn)為正確的依賴(lài)順序。最終，每一條指令都會(huì)有其最終的依賴(lài)，以用于被執(zhí)行。最終依賴(lài)可能會(huì)成環(huán)，這將在被執(zhí)行時(shí)處理。執(zhí)行時(shí)，pilot 與 copilot 的 log 記錄通過(guò)上述排序過(guò)程被整合，在成環(huán)的依賴(lài)中 pilot 的指令會(huì)被優(yōu)先執(zhí)行以打破環(huán)。Copilot 排序會(huì)將指令與最終依賴(lài)持久化至其它節(jié)點(diǎn)以用于錯(cuò)誤恢復(fù)。與 EPaxos 類(lèi)似，每次排序操作都會(huì)經(jīng)過(guò) FastAccept 階段，又是會(huì)經(jīng)過(guò) Accept 階段。以下是排序的具體過(guò)程（暫時(shí)省略 fast takeover 與 view-change）。
Client 同時(shí)發(fā)送指令至 pilot 與 copilot
每個(gè) client 都擁有 ID：cliid。client 會(huì)為每一個(gè)指令分配一個(gè)遞增且不重復(fù)的 ID：cid。發(fā)送指令時(shí)，client 也會(huì)附加 cliid 與 cid 以標(biāo)識(shí)指令，以便在執(zhí)行階段去重。
Pilot 提議指令與其初始依賴(lài)
當(dāng)一 pilot 收到 client 發(fā)來(lái)的一條指令時(shí)會(huì)將其追加至自身 log 記錄中，同時(shí)將最后收到的來(lái)自另一 pilot 的指令作為該指令的初始依賴(lài)。該 pilot 向其它節(jié)點(diǎn)（包括自己與另一 pilot）發(fā)送 FastAccept 消息提議這條指令與其初始依賴(lài)。
節(jié)點(diǎn)回復(fù) FastAccept
當(dāng)一節(jié)點(diǎn)收到 FastAccept 消息時(shí)，它會(huì)檢查收到的指令初始依賴(lài)是否與其之前已 Accept 的其它 entry 沖突。若不沖突，節(jié)點(diǎn)會(huì)回復(fù)此 FastAcceptOk。若沖突，節(jié)點(diǎn)會(huì)回復(fù)其認(rèn)為正確的依賴(lài)順序。
compability check：
對(duì)于兩個(gè)依賴(lài)，如果其中至少有一個(gè)的 entry 位于另一個(gè)的 entry 之后，則兩依賴(lài)不沖突。在上圖 a 中表示了沖突與未沖突的依賴(lài)：依賴(lài)于 P.1 的 P'.1 與依賴(lài)于 P'.1 的 P.2 沒(méi)有沖突，因?yàn)?P.2 位于 P'.1 之后. 依賴(lài)于 P.2 的 P'.3 與依賴(lài)于 P'.2 的 P.3 沖突，因?yàn)樗鼈兌疾晃挥趯?duì)方 entry 之后。由于沖突的依賴(lài)可能導(dǎo)致指令執(zhí)行順序不一致，所以必須避免，如有節(jié)點(diǎn)會(huì)先執(zhí)行 P.3 再執(zhí)行 P'.3，有節(jié)點(diǎn)會(huì)反之。
節(jié)點(diǎn)會(huì)使用 compatibility check 檢查 pilot 提供的初始依賴(lài)是否沖突。依賴(lài)于 P'.j 的 entry P.i 與 P.i 與 P'.j 之前 accept 的 entry 不沖突，所以 compatibility check 只需要檢查該依賴(lài)是否與另一 pilot 之后的 log 是否沖突。若節(jié)點(diǎn)已 accept 另一 pilot 的 entry P'.k (k > j)，且 P'.k 依賴(lài)位于 P.i 之前的 entry，則依賴(lài)沖突。
如果節(jié)點(diǎn)：
- 還未收到之后的關(guān)于之后 entry 的依賴(lài)?
- 已收到之后的 entry P'.k，但其依賴(lài)為 P.i 或在其后，如 P'.j, P.i, ... , P'.k
它會(huì)認(rèn)為依賴(lài)不沖突，以 FastAcceptOk 回復(fù)，而相同的規(guī)則會(huì)阻止另一 pilot 之后的依賴(lài)沖突。否則節(jié)點(diǎn)會(huì)回復(fù) FastAcceptReply 并附加其收到的最后一條來(lái)自另一 pilot 的 entry。
Pilot 嘗試通過(guò) fast path 來(lái) commit 該指令
與 EPaxos 類(lèi)似，若 pilot 收到至少 f + (f + 1) / 2 （fast quorum，包括該 pilot 本身）個(gè)節(jié)點(diǎn)的 FastAcceptOk 回復(fù)，就足以從之后可能發(fā)生的節(jié)點(diǎn)錯(cuò)誤中恢復(fù)。此時(shí) pilot 會(huì)通過(guò) fast path 直接 commit 該指令與其依賴(lài)，向其它節(jié)點(diǎn)發(fā)送 commit 消息（無(wú)需等待回復(fù)）。
可能有兩種原因?qū)е?pilot 無(wú)法收到 fast quorum 的 FastAcceptOk 回復(fù)：
- 有其它節(jié)點(diǎn)出錯(cuò)，導(dǎo)致剩余節(jié)點(diǎn)不足 fast quorum
- 有其它節(jié)點(diǎn)檢測(cè)到依賴(lài)沖突，回復(fù) FastAcceptReply 與其認(rèn)為正確的依賴(lài)順序?
不論哪種原因，pilot 都需要等待有至少 f + 1 個(gè)節(jié)點(diǎn)回復(fù)，才能進(jìn)入下一步。
Pilot 在 Accept 階段最終確定依賴(lài)?
pilot 將上一步中收到的推薦依賴(lài)（包括自身，且 FastAcceptOk 即初始依賴(lài)）以升序排序，并選擇第 f + 1 個(gè)推薦依賴(lài)作為最終依賴(lài)。選擇第 f + 1 個(gè)是為了保證該依賴(lài)與任何已經(jīng) commit 的命令有交集以確保線(xiàn)性，不選擇第 f + 1 個(gè)之后的依賴(lài)是為了防止之后的依賴(lài)與該依賴(lài)有依賴(lài)關(guān)系。
之后 pilot 使用 Accept 消息發(fā)送最終依賴(lài)到其它節(jié)點(diǎn)。最終依賴(lài)可能會(huì)導(dǎo)致成環(huán)，但這可以接受，因?yàn)閳?zhí)行時(shí)所有節(jié)點(diǎn)都會(huì)按照相同的方法打破環(huán)。其它節(jié)點(diǎn)收到該最終依賴(lài)后回復(fù) AcceptOk。當(dāng) pilot 收到 f + 1 個(gè) AcceptOk 回復(fù)后（包括其本身），即可 commit 該命令與最終依賴(lài)。
執(zhí)行
節(jié)點(diǎn)使用兩 pilot 的 log 合并后的順序執(zhí)行。合并后的 log 中，每個(gè) client 指令都會(huì)出現(xiàn)兩次。節(jié)點(diǎn)會(huì)在發(fā)現(xiàn)已執(zhí)行過(guò)的指令時(shí)跳過(guò)該指令。執(zhí)行指令后，pilot 與 copilot 都會(huì)將結(jié)果返回給 client。
Copilot 最終合并后的指令順序?
最終合并后的指令順序由以下因素決定：
- 各 pilot 內(nèi)各自的 log 順序?
- 兩 pilot 指令間的依賴(lài)關(guān)系?
- pilot 優(yōu)先級(jí)，用于處理成環(huán)依賴(lài)
- 最終順序包含各 pilot 內(nèi)各自的 log 順序。上圖，P.0 < P.1 < P.2。該順序可能成環(huán)?
- 當(dāng)依賴(lài)不成環(huán)時(shí)，依賴(lài)順序即為最終順序。上圖，P.1 < P'.0 < P'.1 < P.2
- 當(dāng)依賴(lài)成環(huán)時(shí)，最終順序由 pilot 優(yōu)先級(jí)決定，pilot 的指令會(huì)在 copilot 的指令前執(zhí)行。上圖，P.4 < P.5 < P'.5
依序執(zhí)行?
各節(jié)點(diǎn)在得到每條指令的最終依賴(lài)后就會(huì)按照相同的順序執(zhí)行。當(dāng)一條指令 commit，且對(duì)應(yīng) entry 前的所有指令已都被執(zhí)行后，節(jié)點(diǎn)會(huì)執(zhí)行這條指令。
以下規(guī)則決定何時(shí)可以執(zhí)行一條 entry 為 P.i、依賴(lài)為 P'.j 的指令：
- P.i 已 commit
- P.(i - 1) 已被執(zhí)行?
- P'.j 已被執(zhí)行，或 P.i 與 P'.j 成環(huán)且 P 為 pilot 指令
節(jié)點(diǎn)可以亂序接受指令的 commit 消息，如節(jié)點(diǎn)可能先得知一指令 commit，之后再得知該指令的依賴(lài) commit。為了達(dá)到所有指令的執(zhí)行順序一致，節(jié)點(diǎn)必須在執(zhí)行一條指令前執(zhí)行過(guò)該指令的依賴(lài)以及該指令 entry 前的所有指令。例如在執(zhí)行一條 entry 為 P.i、依賴(lài)為 P'.j 的指令時(shí)，需要：
- P.i 之前 entry 的所有指令都已被執(zhí)行?
- P'.j 已被執(zhí)行
- P'.j 之前 entry 的所有指令都已被執(zhí)行
才能執(zhí)行 P.i。Copilot 的 Fast Takeover 機(jī)制可以防止正常運(yùn)行的 pilot 等待 slowdown 的 pilot。
去重執(zhí)行并回復(fù)?
若排序過(guò)程按正常情況執(zhí)行，每一條指令在 log 合并后都會(huì)出現(xiàn)兩次。節(jié)點(diǎn)只會(huì)在一條命令出現(xiàn)第一次時(shí)執(zhí)行該命令。cliid 與 cid 組成的元組在這里可以用來(lái)標(biāo)識(shí)指令。若該節(jié)點(diǎn)是 pilot 或 copilot，執(zhí)行完成一條命令后會(huì)將結(jié)果返回給客戶(hù)端?？蛻?hù)端收到一個(gè)返回的結(jié)果后，會(huì)忽略之后由另一 pilot 返回的結(jié)果。
Fast Takeover
為了達(dá)到執(zhí)行順序一致，有時(shí)一 pilot 需要等待另一 pilot 的 commit 消息。正常工作的 pilot 等待另一 slowdown 的 pilot 會(huì)消耗大量時(shí)間，因此需要 Fast Takeover 機(jī)制。
每個(gè)節(jié)點(diǎn) log 中的每一個(gè) entry 都會(huì)附有一 ballot number。與 Paxos 的 proposal number 類(lèi)似，Copilot 協(xié)議過(guò)程中的每條消息都會(huì)帶有 ballot number。通過(guò)這些序列號(hào)可以讓 pilot 安全地進(jìn)行與 Paxos 類(lèi)似的所有權(quán)競(jìng)爭(zhēng)的 Fast Takeover。
當(dāng)一個(gè)節(jié)點(diǎn)被選舉為 pilot 或 copilot，所有節(jié)點(diǎn)中該 pilot log 的 entry ballot number 都會(huì)被設(shè)置為 b。節(jié)點(diǎn)只會(huì)接受附加 ballot number 大于等于對(duì)應(yīng) entry 的 ballot number 的消息。在 pilot 正常工作時(shí)，其發(fā)出的所有消息的 ballot number 值都為 b。
當(dāng)一 pilot 發(fā)現(xiàn)另一 pilot slowdown ，希望代替其完成某 entry 的 commit 時(shí)，正常工作的 pilot 會(huì)向所有其它節(jié)點(diǎn)發(fā)送關(guān)于該 entry 的 Prepare 消息并附加大于 b 的 ballot number 值 b'。如果其它節(jié)點(diǎn)確認(rèn) b'大于該 entry 原本的 ballot number 值 b 時(shí)會(huì)回復(fù) PrepareOk 消息，并將該 entry 的 ballot number 值設(shè)置為 b'。PrepareOk 消息中會(huì)包含該 entry 目前的狀態(tài)（not-accepted、fast-accepted、accepted 或 committed），同時(shí)包含該 entry 之前最大的 ballot number、指令與依賴(lài)。
在正常 pilot 發(fā)送 Prepare 消息后，它需要等待接收到至少 f + 1（包含它本身）個(gè) PrepareOk 消息。如果通過(guò)某 PrepareOk 消息得知該指令已被 commit，該 pilot 會(huì)立即停止等待并 commit 該指令與其依賴(lài)，結(jié)束 Fast Takeover 過(guò)程。否則，該 pilot 會(huì)通過(guò)如下過(guò)程選擇該指令與其依賴(lài)，并通過(guò) Accept 消息發(fā)送，等待 f + 1 個(gè) AcceptOk 回復(fù)，然后繼續(xù)執(zhí)行。
entry 內(nèi)容的恢復(fù)過(guò)程
Fast Takeover 與 view-change 都使用了本過(guò)程，以正確恢復(fù)任意可被 commit 并執(zhí)行的 entry。本過(guò)程十分復(fù)雜，細(xì)節(jié)可參閱 Technical Report TR-004-20。
在附加正確 ballot number 的 PrepareOk 回復(fù)集合中：
- 若有至少一個(gè)回復(fù) entry 狀態(tài)為 accepted，則采用該回復(fù)的指令與依賴(lài)?
- 當(dāng)有小于 (f + 1) / 2 個(gè)回復(fù)狀態(tài)為 fast-accepted 時(shí)，設(shè)置該 entry 為 no-op 且依賴(lài)為空?
- 當(dāng)有大于等于 f 個(gè)回復(fù)狀態(tài)為 fast-accepted 時(shí)，采用該回復(fù)的指令與依賴(lài)?
在第一種情況中，該 entry 可能已經(jīng)被 commit 并附加了更小的 ballot number，所以必須采用原值與依賴(lài)。在第二種情況中，該 entry 不可能已被 commit，所以采用 no-op 是安全的。在第三種情況下，該 entry 可能已經(jīng)被 commit 并附加了更小的 ballot number，所以可以采用原值與依賴(lài)，因?yàn)?f 個(gè) fast-accepted 回復(fù)與該 pilot 本身已構(gòu)成了一個(gè) majority quorum。
除上述情況外，還有一種可能，有大于等于 (f + 1) / 2 且小于 f 個(gè)回復(fù)狀態(tài)為 fast-accepted。這種情況下，該 entry 可能已被 commit，也可能有另一 pilot 已提案另一與之沖突的指令，且有其它節(jié)點(diǎn)已收到了該 fast-accept。為了確定情況，發(fā)起這次恢復(fù)過(guò)程的節(jié)點(diǎn)需要檢查另一 pilot log 中是否存在沖突的 entry。若發(fā)現(xiàn)沖突的 entry 但還未 commit，則對(duì)此 entry 重復(fù)整個(gè)上述過(guò)程，最終安全地完成恢復(fù)。
觸發(fā) Fast Takeover
當(dāng) pilot 得知一條 entry 為 P.i、依賴(lài)為 P'.j 的指令被 commit 時(shí)，如果：
- P.i 之前 entry 有指令未被 commit
- P'.j 未被 commit
- P'.j 之前 entry 有指令未被 commit
pilot 就會(huì)啟動(dòng)一個(gè) timer。若 timer 達(dá)到了 takeover-timeout 且仍有執(zhí)行 P.i 所需的指令沒(méi)有被 commit，該 pilot 就會(huì)停止等待，主動(dòng)接過(guò) commit 所需指令與排序的任務(wù)，fast takeover 另一 pilot log 中所有可能為該指令執(zhí)行前置條件的 entry。在該 Copilot 實(shí)現(xiàn)中，所有 entry 的 fast takeover 過(guò)程是被批量合并且是并行的。
如果 takeover-timeout 設(shè)置的時(shí)間太短，就會(huì)產(chǎn)生沒(méi)有必要的錯(cuò)誤 fast takeover，從而導(dǎo)致 proposal 競(jìng)爭(zhēng)。proposal 競(jìng)爭(zhēng)問(wèn)題可以使用指數(shù)退避隨機(jī)化 timeout 來(lái)避免。為了避免必要的錯(cuò)誤 fast takeover，可以將 takeover-timeout 設(shè)置為一個(gè)中等大小的值（如 10ms）。中等大小的 takeover-timeout 可能導(dǎo)致處理速度變慢，但是使用 Null Dependency Elimination 可以避免這個(gè)問(wèn)題。
Fast takeover 與 leader 選舉看起來(lái)十分類(lèi)似，它們都是通過(guò)等待某節(jié)點(diǎn)相應(yīng)時(shí)超時(shí)觸發(fā)的。Leader 選舉是由于某節(jié)點(diǎn)無(wú)法在設(shè)定 timeout 內(nèi)收到另一節(jié)點(diǎn)的某種消息（如心跳或新指令提議）觸發(fā)的。但是有時(shí)雖然 leader 仍可正常發(fā)送心跳，但其實(shí)際處理指令的速度會(huì)因?yàn)橐恍┮蛩囟兟?。Fast takeover 是由指令處理路徑上某點(diǎn)的 slowdown 觸發(fā)的，配合指令同時(shí)有兩條互不依賴(lài)的處理路徑，可以在發(fā)生 slowdown 時(shí)總會(huì)由較快的 pilot 處理完成指令。當(dāng)一個(gè) pilot slowdown 時(shí)，另一個(gè) pilot 會(huì)通過(guò) fast overtake 處理所有指令，無(wú)需等待較慢的 pilot。
額外設(shè)計(jì)?
本節(jié)未提到的 Copilot 設(shè)計(jì)都與其它分布式狀態(tài)機(jī)的設(shè)計(jì)一致。
保證指令僅被執(zhí)行一次是通過(guò)檢查 cliid 與 cid 實(shí)現(xiàn)的。記錄一條指令已被執(zhí)行一次的 cliid 與 cid 容器會(huì)在第二次遇到相同指令時(shí)清空。
對(duì)于結(jié)果非確定的指令（如涉及隨機(jī)數(shù)生成，每次執(zhí)行結(jié)果都不同），可以由兩 pilot 完成非確定部分（隨機(jī)數(shù)生成），此時(shí)該指令的執(zhí)行結(jié)果變?yōu)榭纱_定的值，再進(jìn)行排序與執(zhí)行等操作。兩 pilot 在完成非確定部分時(shí)可能不同，所以最終的指令可能的執(zhí)行結(jié)果會(huì)有兩個(gè)版本，但執(zhí)行的去重機(jī)制可以保證只有一個(gè)結(jié)果有效。
與 Multi-Paxos 的 leader 選舉類(lèi)似，pilot 與 copilot 選舉使用 view-change。view-change 選舉得到的新的 pilot 與 copilot 使用之前提到的 entry 對(duì)應(yīng)內(nèi)容的恢復(fù)過(guò)程。由于兩 pilot 有各自獨(dú)立的 log，在重新選舉一個(gè) leader 時(shí)另一 pilot 可以不間斷地為 client 提供服務(wù)。在這個(gè)過(guò)程中，正常的 pilot 不會(huì)將另一 pilot 的 entry 作為依賴(lài)，所以可以一直在 fast path 上 commit，直到另一 pilot 選舉完畢。
Copilot 能達(dá)到 1-slowdown-tolerant 的原因
Copilot 通過(guò)保證任何客戶(hù)端指令在任意時(shí)間節(jié)點(diǎn)都在兩條不同的處理路徑上。兩條路徑的處理速度不同，處理速度快的路徑得到的結(jié)果必定先返回客戶(hù)端。
當(dāng)兩 pilot 都為正常狀態(tài)時(shí)，就算有最多 f 個(gè)其它節(jié)點(diǎn) slowdown 時(shí)，1-slowdown-tolerant 仍成立，因?yàn)樵?regular path 上 commit 只需要 f + 1 個(gè)節(jié)點(diǎn)回復(fù)。
當(dāng)一 pilot 發(fā)生 slowdown 或出錯(cuò)時(shí)，另一個(gè)正常的 pilot 仍可以正常 commit 其 entry，如果有對(duì) slowdown pilot 指令的依賴(lài)，正常 pilot 會(huì)執(zhí)行 fast takeover 解決這個(gè)問(wèn)題。在 slowdown 發(fā)生后，正常 pilot 會(huì)通過(guò) fast takeover 迅速的解決對(duì) slowdown pilot 指令的依賴(lài)，之后即可按正常流程繼續(xù)處理。此時(shí)該分布式狀態(tài)機(jī)的總體執(zhí)行速度取決于此正常的 pilot，所以 1-slowdown-tolerant 成立。
優(yōu)化
本節(jié)內(nèi)容是對(duì)論文 §5 Optimizations 的翻譯。
Ping-Pong Batching
當(dāng)兩個(gè) pilot 都在正常運(yùn)行時(shí)，如果幾條指令同時(shí)以亂序到達(dá)兩個(gè) pilot，就可能因順序不一致導(dǎo)致無(wú)法通過(guò) compability check。Ping-Pong Batching 通過(guò)協(xié)調(diào)兩 pilot 的提案順序從而避免上述情況，使提案總會(huì)通過(guò) fast path 完成。
在 Ping-Pong Batching 過(guò)程中，各 pilot 會(huì)打包（batching）在一定時(shí)間段內(nèi)到達(dá)的指令。在此期間該 pilot 每收到一條指令都會(huì)將其放入自己的下一個(gè) entry 中，因此打包后的指令會(huì)是一組連續(xù)的 entry。當(dāng)該 pilot 收到另一 pilot 的 FastAccept 消息，或到達(dá)設(shè)定的打包最長(zhǎng)時(shí)間段（ping-pong-wait timeout），就會(huì)結(jié)束當(dāng)前的打包操作。
當(dāng)兩 pilot 都未出現(xiàn) slowdown 的正常情況下，打包操作會(huì)因收到另一 pilot 的 FastAccept 消息結(jié)束。如此，兩 pilot 的 FastAccept 會(huì)如 ping-pong 一般進(jìn)行。Pilot 結(jié)束其對(duì)第一批指令的打包并發(fā)送 FastAccept 消息，copilot 收到該消息后也會(huì)結(jié)束打包并發(fā)送這批指令的 FastAccept 消息，pilot 收到該消息后又會(huì)結(jié)束其對(duì)第二批指令的打包并發(fā)送 FastAccept 消息，如此往復(fù)。
上述流程可以保證每個(gè) pilot 會(huì)在發(fā)出 FastAccept 前都會(huì)收到另一 pilot 的 entry 順序，因此可以避免發(fā)出有依賴(lài)沖突的消息，因此其它節(jié)點(diǎn)在收到 FastAccept 消息后進(jìn)行的 compability check 都會(huì)成功，使得每一次提案都可以在 fast path 上完成。
當(dāng)有一 pilot 出現(xiàn) slowdown 時(shí)，另一 pilot 會(huì)在達(dá)到 ping-pong-wait timeout 后結(jié)束打包操作。這避免了因一個(gè) pilot 出現(xiàn) slowdown 導(dǎo)致整個(gè)系統(tǒng) slowdown。
Null Dependency Elimination
當(dāng)一 pilot 發(fā)現(xiàn)自己將要執(zhí)行的指令有依賴(lài)位于另一 pilot log 中，且還未 commit，這時(shí)它會(huì)檢查自身是否已執(zhí)行過(guò)該依賴(lài)所對(duì)應(yīng)的指令，若發(fā)現(xiàn)已執(zhí)行過(guò)，則無(wú)需等待另一 pilot 的 commit 消息，可直接跳過(guò)。滿(mǎn)足以上條件的依賴(lài)稱(chēng)為 null dependency，該機(jī)制名為 Null Dependency Elimination。在 null dependency 出現(xiàn)時(shí)，pilot 無(wú)需等待該未 commit 的依賴(lài)，因?yàn)樵撘蕾?lài)不會(huì)對(duì)最終的執(zhí)行結(jié)果產(chǎn)生影響，pilot 只需將該依賴(lài)標(biāo)記為已執(zhí)行然后繼續(xù)。
當(dāng)有一 pilot 出現(xiàn)持續(xù)的 slowdown 時(shí)，Null Dependency Elimination 可以讓正常的 pilot 省去 fast takeover 的步驟。因?yàn)?slowdown 的 pilot 的提案比正常的 pilot 慢，所以其 entry 都是 null dependency，正常 pilot 可以直接跳過(guò)等待。若一 pilot 在提案后才發(fā)生 slowdown，fast takeover 仍是必要的。在正常 pilot fast takeover 過(guò) slowdown pilot 的提案后，就可以通過(guò) Null Dependency Elimination 跳過(guò)等待發(fā)生 slowdown 的 pilot 了。因此 1-slowdown-tolerant 仍是成立的。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-491310.html
總結(jié)
Copilot 協(xié)議借鑒了之前各協(xié)議的優(yōu)點(diǎn)，其排序部分與 EPaxos 類(lèi)似，fast takeover 過(guò)程與 Paxos 類(lèi)似，pilot 選舉與 Multi-Paxos 一致。同時(shí)，Copilot 排序不依賴(lài)客戶(hù)端指令本身是否 interfere，而將指令到達(dá)時(shí)間作為排序的唯一依據(jù)，這也減小協(xié)議的實(shí)現(xiàn)難度。通過(guò)文中提到的優(yōu)化，Copilot 在無(wú)節(jié)點(diǎn) slowdown 時(shí)雖然無(wú)法達(dá)到 Multi-Paxos 或 EPaxos 性能水平，但仍有一定競(jìng)爭(zhēng)力。在有節(jié)點(diǎn) slowdown 時(shí)，Copilot 是唯一能避免整個(gè)系統(tǒng)速度收到影響的協(xié)議。綜上，在選擇分布式狀態(tài)機(jī)系統(tǒng)的共識(shí)協(xié)議時(shí)，Copilot 協(xié)議不失為一個(gè)好的選擇。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-491310.html
到了這里，關(guān)于分布式狀態(tài)機(jī)共識(shí)協(xié)議 Copilot的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
