行程韌性靠複製，複製就離不開可靠多播（reliable multicasting）——保證訊息送達行程群組的所有成員。不幸的是，可靠多播出乎意料地棘手。本節依序討論基本方案、擴展性問題，以及在行程可能失效時的原子多播與虛擬同步。

基本可靠多播方案#

多數傳輸層只提供可靠的點對點通道，很少提供對一群行程的可靠通訊。最陽春的做法是讓每對行程之間各建一條點對點連線——浪費頻寬，但行程數不多時，這是簡單而常見的解。

要走得更遠，得先精確定義「可靠多播」。直覺上是「送給群組的訊息應送達每個成員」，但通訊進行中若有行程加入群組呢？它該收到這則訊息嗎？傳送中的行程當機了又怎麼算？因此要區分兩種情境：

• 行程可能故障：多播可靠意指保證所有無故障成員收到訊息。難處在於遞送訊息前，還得先對「群組長什麼樣子」達成共識，外加各種順序約束——這是後面原子多播的主題。
• 假設行程都正常：若進一步假設行程不失效、通訊期間也無人進出群組，可靠多播就單純是「每則訊息送達每個現任成員」。最簡單的情況下甚至不要求各成員以相同順序收到訊息。

後者這種較弱的可靠多播相對容易實作（同樣以接收者數量有限為前提）。假設底層只有不可靠多播——訊息可能中途遺失，只送達部分接收者。一個簡單的解法：

• 傳送者為每則多播訊息配上序號，並將訊息存在本地的歷史緩衝區（history buffer）；假設訊息依發送順序被接收，接收者便能輕易發現自己漏了哪一則。
• 傳送者已知所有接收者，把訊息留在緩衝區直到每個接收者都回了確認（ACK）。
• 接收者發現漏訊息時，可回**否定確認（negative acknowledgment, NACK）**要求重傳；或者由傳送者在時限內沒收齊確認時自動重傳。

設計上還有取捨空間：確認可以搭其他訊息的便車（piggyback）以減少回傳訊息量；重傳可以用點對點送給提出要求的行程，也可以再多播給全體。

可靠多播的擴展性#

上述方案撐不起大量接收者：N 個接收者就意味著傳送者要準備接收至少 N 個確認。接收者一多，傳送者會被回饋訊息淹沒，稱為回饋爆炸（feedback implosion）；何況接收者還可能散布在廣域網路上。

第一個改良是只回 NACK、不回 ACK：接收者只在漏訊息時回報。一般而言擴展性較佳，但無法硬性保證回饋爆炸不會發生；而且理論上傳送者必須永遠留著訊息——它永遠無法確知訊息已送達所有人，得隨時準備重傳舊訊息。實務上會在一段時間後把訊息移出緩衝區以免溢位，代價是屆時的重傳要求可能無法滿足。

非階層式回饋控制#

減少回傳給傳送者的回饋訊息數，是擴展性的關鍵。**回饋抑制（feedback suppression）**是廣受採用的模型，也是 SRM（Scalable Reliable Multicasting）協定的基礎：

• 接收者從不確認成功遞送，只回報漏失（如何偵測漏失交給應用層）。
• 接收者發現漏了訊息 m 時，把回饋多播給整個群組，而不是單獨告訴傳送者。
• 若假設重傳一律多播給全體，那麼只要一個重傳要求送達傳送者 S 就夠了。因此漏失 m 的接收者 R 會把回饋延遲一段隨機時間再送；若期間先收到別人對 m 的重傳要求，R 就抑制自己的回饋。理想情況下只有一則回饋抵達 S，S 隨後重傳 m。

回饋抑制的擴展性尚可，已用在共享白板等多個協作型網際網路應用。但它也帶來新問題：

• 要確保「只有一則重傳要求回到傳送者」，各接收者的回饋排程得相當精準，否則許多接收者仍會同時回報。在散布於廣域網路的行程群中把計時器調準，並不容易。
• 多播回饋會打擾已成功收到訊息的行程——它們被迫接收和處理對自己毫無用處的訊息。一種解法是讓漏失 m 的接收者加入一個專屬 m 的多播群組，但這要求群組管理極有效率，在廣域系統很難做到；較好的做法是讓常漏同一批訊息的接收者結盟，共用回饋與重傳通道。

要再強化 SRM 的擴展性，可讓接收者協助局部復原（local recovery）：已成功收到 m 的接收者收到重傳要求時，可以不等要求傳回原始傳送者，直接自己多播 m。

階層式回饋控制#

回饋抑制本質上是非階層式解法；要支撐非常大的接收群，得走階層式：

• 假設只有一個傳送者。接收者被劃分成多個子群組，子群組再組織成一棵樹，含傳送者的子群組為根。子群組內部可用任何適合小群組的可靠多播方案。
• 每個子群組指派一位本地協調者（local coordinator），負責處理子群組內接收者的重傳要求，並擁有自己的歷史緩衝區。
• 協調者自己漏了訊息 m 時，向父子群組的協調者要求重傳。在基於確認的方案中，協調者收到訊息後向父節點送 ACK；當它收齊子群組所有成員以及所有子節點對 m 的確認，就能把 m 移出緩衝區。

主要難題是建樹，而且往往得動態建。一種思路是利用底層網路的多播樹（若有的話），把網路層的每個多播路由器強化成本地協調者——但實務上要這樣改造現有網路並不容易，這也是應用層多播（application-level multicasting）方案得以流行的原因之一。

結論：要建構能擴展到「大量接收者散布於廣域網路」的可靠多播方案是困難的問題，不存在單一最佳解，每種解法都引入新問題。

原子多播#

回到行程可能失效的情境。分散式系統常需要的保證是：訊息要嘛送達所有行程、要嘛一個都不送，而且通常還要求所有訊息以相同順序送達所有行程——這就是原子多播（atomic multicast）問題。

虛擬同步#

行程可能失效時的可靠多播，可以用行程群組與群組成員資格變更來精確定義。沿用先前的模型：分散式系統有一個通訊層，訊息在其中**接收（receive）後先在本地緩衝，直到可以遞送（deliver）**給邏輯上位於更高層的應用。

• 一則多播訊息 m 唯一對應一份「應遞送對象」清單，即群組視圖（group view）——傳送者多播 m 當下所看到的群組成員集合。關鍵是清單上每個行程都持有相同的視圖：大家都同意 m 應遞送給彼此、且不遞送給其他行程。
• 假設 m 在視圖 G 下多播，同時另一個行程加入或離開群組。這個變更會以一則**視圖變更（view change）**訊息 vc 多播給 G 中所有行程。此時 m 與 vc 同時在途，必須保證：m 要嘛在每個行程收到 vc 之前遞送給 G 的所有行程，要嘛完全不遞送。這與第六章的全序多播有幾分相似。
• 「完全不遞送」唯一被允許的情況：m 的傳送者在多播途中當機。此時要嘛 G 的所有成員都收不到，等同於傳送者在送出 m 之前就當了。

具備這種性質的可靠多播稱為虛擬同步（virtually synchronous）（Birman 與 Joseph）。例如四個行程 P1–P4：P1 加入群組後，眾人多播了一些訊息；接著 P3 當機，但當機前它已把某則訊息送達 P2 與 P4，卻沒送到 P1。虛擬同步保證這則訊息完全不被遞送——效果上等於 P3 當機前從未送出它。P3 被移出群組後，其餘成員繼續通訊；P3 復原後可以重新加入，但狀態得先更新到最新。

虛擬同步的精髓：所有多播都發生在視圖變更之間。視圖變更如同一道屏障，任何多播都不能跨越——所有在途多播都會在視圖變更生效前完成。這與前一章分散式資料儲存中同步變數的用法相似。

訊息順序#

虛擬同步讓開發者把多播想成發生在「以成員資格變更為界的紀元」之中，但尚未談到多播之間的順序。一般區分四種：

1. 無序多播（unordered multicast）：對不同行程遞送訊息的順序不做任何保證。P1 多播 m1、m2 給群組，P2 可能依 m1、m2 的順序遞送，P3 卻可能先收到 m2 而依 m2、m1 遞送。
2. FIFO 順序多播（FIFO-ordered multicast）：通訊層必須依同一傳送者的發送順序遞送其訊息。若 P1 送出 m1、m2，P2 送出 m3、m4，則所有行程都必須 m1 先於 m2、m3 先於 m4；但不同傳送者的訊息之間無約束——P2 可以 m1 先於 m3，P3 同時可以 m3 先於 m1。
3. 因果順序多播（causally-ordered multicast）：保留訊息間的潛在因果關係——若 m1 因果先於 m2（無論是否同一傳送者所發），每個接收者的通訊層都必須先遞送 m1 再遞送 m2。可用第六章的向量時戳實作。
4. 全序遞送（totally-ordered delivery）：這是可疊加的額外約束——無論底下採無序、FIFO 或因果順序，都再要求訊息以相同順序遞送給所有成員。例如 FIFO 加全序時，P2 與 P3 可以都先遞送 m3 再 m1；但若 P2 先 m1 後 m3、P3 卻先 m3 後 m1，就違反全序（同時 FIFO 仍須遵守：m2 在 m1 之後、m4 在 m3 之後）。

實作虛擬同步#

以 Isis 為例——一套已在業界實用多年的容錯分散式系統（實作議題見 Birman 等人的描述）：

• Isis 利用底層網路可靠的點對點通訊（實務上是 TCP）：多播 m 給群組，就是把 m 可靠地送給每個成員。每次傳輸保證成功，但不保證所有成員都收到 m——傳送者可能在送完之前就失效。Isis 另假設同一來源的訊息會依發送順序被通訊層收到（由 TCP 連線解決）。
• 核心問題：保證送往視圖 G 的所有訊息，在下一次成員資格變更前遞送給 G 中所有無故障行程。由於 m 的傳送者可能沒送完就當了，G 中可能有行程永遠收不到 m，得從別處拿。
• 解法：讓 G 中每個行程保留 m，直到確知 G 的所有成員都已收到。被所有成員收到的訊息稱為穩定（stable）訊息，只有穩定訊息才允許遞送。要讓訊息穩定，選 G 中任一個運作中的行程，請它把 m 補送給其他所有行程即可。

視圖變更的流程（設當前視圖 Gi，要安裝下一個視圖 Gi+1，不失一般性假設兩者至多差一個行程）：

• 行程 P 收到 Gi+1 的視圖變更訊息（可能來自要加入／離開的行程，或偵測到 Gi 中某行程失效的行程）。
• P 先把自己手上 Gi 的每則不穩定訊息轉送一份給 Gi+1 的所有行程，然後將其標記為穩定。因為點對點通訊可靠，轉送不會丟——這保證 Gi 中凡被至少一個行程收到的訊息，所有無故障行程都會收到。（其實選一個協調者統一轉送不穩定訊息也就夠了。）
• 接著 P 多播一則 flush 訊息，表示自己已無不穩定訊息、準備好安裝 Gi+1。當 P 收到其他每個行程的 flush 訊息後，就能安全地安裝新視圖。
• 行程 Q 收到在 Gi 中發送的訊息 m 且它仍認為當前視圖是 Gi 時，就遞送 m（並考慮額外的順序約束）；若已收過，視為重複而丟棄。Q 終究會收到 Gi+1 的視圖變更訊息，同樣先轉送不穩定訊息、再送 flush 收尾。由於底層通訊保序，一個行程的 flush 訊息必然在其不穩定訊息之後才被收到。

上述協定有個重大缺陷：無法處理「視圖變更宣告期間又有行程失效」——它假設在 Gi+1 被所有成員安裝完成之前，Gi+1 中不會再有行程失效（否則就得產生下一個視圖 Gi+2）。解法是允許在前一批變更尚未被所有行程安裝完成時，就宣告任何視圖 Gi+k 的變更；細節原書留作習題。