把資料送給多個接收者——即多播通訊（multicast communication）——是分散式系統通訊的重要主題。多年來這個題目屬於網路協定的領域：大量網路層與傳輸層的方案被實作與評估過，但共同的難題是建立資訊散播的通訊路徑——實務上牽涉龐大的管理工作，往往還需要人工介入；再加上各方案遲遲沒有收斂，ISP 一直不太願意支援多播。

隨著點對點（peer-to-peer）技術、特別是結構化覆蓋網路管理的出現，建立通訊路徑變得容易許多。由於點對點方案通常部署在應用層，各種**應用層多播（application-level multicasting）**技術應運而生。多播也不一定要靠明確建立通訊路徑：以八卦為基礎（gossip-based）的資訊散播提供了簡單（但通常較不高效）的多播方式。

應用層多播#

基本想法：節點組織成一個覆蓋網路（overlay network），再用它把資訊散播給成員。關鍵觀察是網路路由器不參與群組成員管理——因此覆蓋網路中節點間的連線可能橫跨多條實體鏈路，在覆蓋層內繞送訊息的效率，可能不如網路層繞送所能達到的最佳結果。

覆蓋網路的建構是核心設計議題，基本上有兩種做法：

• 樹（tree）：節點直接組織成樹，任兩節點間有唯一的（覆蓋層）路徑。
• 網格（mesh）：每個節點有多個鄰居，任兩節點間一般存在多條路徑。主要優勢是強健性較高：某條連線中斷（例如節點故障）時，仍有機會繼續散播資訊，不必立刻重組整個覆蓋網路。

具體來看一個在 Chord 上建構多播樹的相對簡單方案（此方案最初為 Scribe 提出；Scribe 是建立在 Pastry——同為 DHT 式點對點系統——之上的應用層多播方案）：

• 想發起多播會期的節點產生一個多播識別碼 mid（隨機選的 160 位元鍵值），查出負責該鍵值的節點 succ(mid)，把它推舉為多播樹的樹根。
• 節點 P 要加入樹，就執行 LOOKUP(mid)：一個帶著「請求加入多播群組 mid」的查詢訊息從 P 被繞送到 succ(mid)。
• 加入請求在通往樹根的路上會經過若干節點。假設先到節點 Q：若 Q 沒見過 mid 的加入請求，它就成為該群組的轉送者（forwarder），P 成為 Q 的子節點，Q 繼續把加入請求往樹根轉送；下一個節點 R 若也還不是轉送者，同樣照辦並記 Q 為子節點。
• 若 Q（或 R）已經是 mid 的轉送者，它記下前一個發送者為子節點即可，不必再往樹根送加入請求——它已在樹中。
• 像 P 這樣明確要求加入的節點，依定義也是轉送者。結果是一棵橫跨覆蓋網路的多播樹，節點有兩類：純幫忙的轉送者，以及明確加入的轉送者。多播本身很簡單：節點執行 LOOKUP(mid) 把多播訊息送往樹根，訊息再沿樹散播。

覆蓋網路的建構#

在覆蓋網路上建樹本身不難，難的是建出有效率的樹。上述方案選擇參與樹的節點時完全不考慮任何效能指標，純粹依覆蓋層的（邏輯）繞送而定。

延伸案例：覆蓋層連線與實體鏈路的落差

考慮四個節點組成的簡單覆蓋網路，節點 A 是多播樹的樹根，每條實體鏈路各有跨越成本。當 A 對其他節點多播訊息時，可以觀察到訊息會把某幾條實體鏈路各走兩次——因為覆蓋層的兩條邏輯連線，實際上部分重疊在同一條實體鏈路上。若當初不建 B 到 D 的覆蓋連線、改建 A 到 C，就能省掉那些重複的跨越。這正是「邏輯拓撲對實體網路視而不見」的代價。

應用層多播樹的品質一般以三個指標衡量：

• 鏈路壓力（link stress）：按鏈路定義，計算同一封包跨越同一條鏈路的次數。壓力大於 1 的原因是：封包在邏輯層雖沿兩條不同連線轉送，這些連線的一部分可能對應到同一條實體鏈路。
• 延展（stretch）或相對延遲懲罰（Relative Delay Penalty, RDP）：兩節點在覆蓋層中的延遲，與它們在底層網路中會經歷的延遲之比。例如覆蓋網路中 B 到 C 的訊息走 B→Rb→Ra→Rc→C，總成本 59 單位；底層網路本可走 B→Rb→Rd→Rc→C，總成本 47 單位——延展即 1.255。建構覆蓋網路的目標是讓總延展（或所有節點對的平均 RDP）最小化。
• 樹成本（tree cost）：全域指標，通常關乎最小化鏈路成本總和。例如以兩端節點間的延遲作為鏈路成本，最佳化樹成本就等於找一棵最小生成樹（minimal spanning tree），使資訊散播到所有節點的總時間最小。

為簡化問題，假設每個多播群組有一個關聯且眾所周知的會合節點（rendezvous node），記錄已加入樹的節點。新節點發出加入請求時，先向會合節點取得（可能不完整的）成員清單，目標是從中挑出最適合當自己父節點的成員。該挑誰？提案眾多、做法各異。以單一來源的多播群組為例：最佳選擇顯然是來源本身（延展保證等於 1），但這會形成以來源為中心的星狀拓撲，來源很容易過載——因此節點的選擇一般會加上限制：只能挑鄰居數不超過 k 的節點（k 為設計參數）。這個限制大幅提高建樹演算法的難度，因為好的解可能需要重組既有的樹的一部分。

一個具體的解法家族是切換樹（switch-trees），基本想法很簡單。假設已有一棵以單一來源為根的多播樹，樹中節點 P 可以換父節點：放棄與現任父節點的連線，改連到另一個節點。唯二的限制是：

• 新父節點不可以是以 P 為根的子樹的成員（否則會把樹切開並形成迴圈）；
• 新父節點的直接子節點不能太多（限制單一節點的轉送負擔）。

換父節點的準則有多種：

• 最佳化通往來源的路徑：每個節點定期收到其他節點的資訊，評估換成某節點當父親是否能縮短到來源的延遲，是則發起切換——等於最小化多播訊息的延遲。
• 看往候選父節點的延遲是否低於往現任父節點：若每個節點都以此為準，理想上整棵樹的總延遲會最小——這就是前述最佳化樹成本的例子。建出這種樹本需更多資訊，但事實證明這個簡單方案是不錯的啟發式，能得到接近最小生成樹的結果。

例如節點 P 收到父節點的鄰居的資訊（即 P 的祖父，加上父親的其他兄弟姊妹），P 評估到這些節點各自的延遲，挑延遲最低者（設為 Q）當新父親，向 Q 送出切換請求。為防止並發切換請求形成迴圈，有未完成切換請求的節點會直接拒絕處理任何進來的請求——實際效果是同一時間只有完全獨立的切換能並行。P 也會提供 Q 足夠的資訊，讓 Q 能判斷兩者同父、或 Q 是祖父。

節點故障呢？切換樹採用簡單的解法：節點發現父親故障時，直接把自己接到樹根，之後最佳化協定照常運作，終會把該節點放回樹中合適的位置。實驗顯示所得的樹確實接近最小生成樹。

以八卦為基礎的資料散播#

一項日益重要的散播技術是仰賴流行病行為（epidemic behavior）。研究者長期觀察疾病在人群中的傳播，探討能否用簡單技術在超大規模分散式系統中散播資訊。**流行病協定（epidemic protocols）**的主要目標：只用本地資訊，在大量節點間快速散播資訊——沒有任何協調散播的中央元件。

以下假設某一資料項的所有更新都由單一節點發起（藉此排除寫寫衝突），論述基礎是 Demers 等人（1987）的經典論文。

資訊散播模型#

流行病演算法源自研究傳染病傳播的流行病學理論，只是把散播的對象從疾病換成資訊——而且目標完全相反：衛生組織想盡辦法阻止傳染，分散式系統的設計者卻要盡快「感染」所有節點。借用流行病學術語：

• 已感染（infected）：持有資料且願意散播給其他節點的節點。
• 易感染（susceptible）：尚未見過該資料的節點。
• 已移除（removed）：已更新但不願或不能散播資料的節點。

（這裡假設能分辨資料新舊，例如靠時間戳記或版本；因此也說節點在散播更新。）

流行的傳播模型是反熵（anti-entropy）：節點 P 隨機挑另一個節點 Q，然後與 Q 交換更新。交換方式有三種：

1. P 只把自己的更新**推（push）**給 Q；
2. P 只從 Q **拉（pull）**新更新；
3. P 與 Q 互送更新（推拉並用，push-pull）。

就快速散播更新而言，只用推是糟糕的選擇。直覺理由：純推式做法中，更新只能由已感染節點傳播；當多數節點已感染，每個已感染節點挑中易感染節點的機率很小，某些節點可能長期沒被挑中而一直維持易感染。反之，拉式在多數節點已感染時表現好得多：散播由易感染節點主動觸發，它很有機會接觸到已感染節點並把更新拉回來。可以證明：只要有一個節點已感染，任一形式的反熵最終都會把更新快速散播到所有節點，但推拉並用仍是最佳策略。

定義一個回合（round）為「每個節點都至少發起過一次與隨機挑選節點交換更新」的期間，那麼把單一更新傳播到所有節點需要 O(log N) 個回合（N 為系統節點數）——散播不只快，更重要的是可擴展。

這種做法的一個特定變體稱為謠言散播（rumor spreading），或簡稱八卦（gossiping）：節點 P 剛收到資料項 x 的更新時，找任意節點 Q 嘗試把更新推給它；若 Q 早已被別的節點更新過，P 可能（以機率 1/k）對繼續散播失去興趣，也就是變成已移除。

八卦是快速散播消息的絕佳方式，但無法保證所有節點都會被更新。可以證明，當參與的節點數很大時，最終仍對更新一無所知（維持易感染）的節點比例 s 滿足：

s = e^(-(k+1)(1-s))

例如 k = 4 時 ln(s) = −4.97，s 小於 0.007——不到 0.7% 的節點漏接。但要保證這些節點也被更新，仍需特別措施：把反熵與八卦結合即可。

流行病演算法的主要優點之一是可擴展性：行程間的同步次數比其他傳播方法少得多。對廣域系統，Lin 與 Marzullo（1999）指出把實際網路拓撲納入考量效果更好：他們的做法以較高機率去接觸連線數少的節點——假設這類節點是通往網路其他偏遠部分的橋梁，應盡早接觸。這稱為方向性八卦（directional gossiping），有多種變體。

多數流行病方案假設節點能隨機挑選任何其他節點交換，這隱含每個成員原則上都得知道完整的節點集合——大型系統中不可能成立。所幸不需要完整清單：如第 2 章所述，維護一個持續更新的部分檢視（partial view），就能把節點集合組織成隨機圖，隨機挑選便不再是問題。

刪除資料#

流行病演算法極擅長散播更新，卻有個奇怪的副作用：散播「刪除」很困難。問題的本質在於刪除會摧毀該資料項的所有資訊——若只是把資料項從節點移除，該節點終究會收到這個資料項的舊副本，並把它當成沒見過的新資料。

訣竅是把刪除記錄成另一種更新並保留紀錄：這樣舊副本不會被當成新資料，只會被視為已被刪除操作更新過的版本。刪除的紀錄靠散播**死亡證明（death certificates）**達成。

死亡證明的問題是它們終究得清理，否則每個節點會逐漸累積一個巨大且無用的歷史刪除資料庫。Demers 等人提出休眠死亡證明（dormant death certificates）：每張死亡證明建立時打上時間戳記；若可假設更新會在已知的有限時間內傳播到所有節點，死亡證明就能在該最大傳播時間過後移除。不過，為了對「刪除確實傳到所有節點」提供硬保證，仍有極少數節點維護永不丟棄的休眠死亡證明：假設節點 P 持有資料項 x 的證明，一旦 x 的過時更新碰巧到達 P，P 就重新散播 x 的死亡證明。

應用#

流行病協定的有趣應用，除了最廣泛部署的散播更新、以及協助發現有少數對外廣域連線的節點以套用方向性八卦之外，還有聚合（aggregating）資訊：

• 計算平均值：每個節點 i 先選一個任意數 x_i。節點 i 與節點 j 交換時，雙方都把值更新為兩人的平均——交換後兩者的值相同。不難看出最終所有節點都會收斂到同一個值：所有初始值的平均，且傳播速度同樣是指數級。
• 估計系統規模：讓所有節點把 x_i 設為 0，只有 x_1 設為 1。若有 N 個節點，最終每個節點都會算出平均值 1/N，於是每個節點 i 都能以 1/x_i 估計系統大小。這個資訊可用來動態調整各種系統參數——例如部分檢視的大小（每個節點追蹤的鄰居數）應取決於參與節點總數；知道總數就能動態調整，可視為一種**自我管理（self-management）**的性質。
• 節點頻繁進出時：計算平均會變得困難。一個實用解法是引入世代（epoch）：假設節點 1 是穩定的，由它不時開啟新世代；節點 i 第一次看到新世代時，把自己的 x_i 歸零、重新開始計算平均。
• 隨機推選發起者：不必固定由 x_1 開始，可以這樣隨機挑節點——每個節點 i 從同一區間（如 [0, 1]）取隨機數作為 x_i，並永久另存為 m_i；節點 i 與 j 交換時，雙方都把值改為兩者的最大值。凡 m_i < x_i 的節點就輸掉「發起計算平均」的競賽，最後只剩單一贏家。判斷自己輸了很容易，判斷自己贏了卻難得多——無法確定所有結果都已到齊。解法是樂觀主義：節點一律先假設自己是贏家，直到被證明不是——屆時把用來計算平均的變數歸零即可。注意此時可能有多個不同的計算（本例中求最大值與求平均）同時並行。