CS 425 期中視覺讀本：把分散式系統動起來

分散式系統的難點，常常藏在兩個步驟之間：訊息送出後，對方真的收到了嗎？收到之後，可以直接交給應用程式嗎？一個節點說寫好了，其他副本也知道嗎？

這篇把期中複習裡的九個主題做成可逐步操作的圖。我對照了 Cloud Computing Concepts, Part 1 的投影片與逐字稿，但使用較小的例子重新呈現。圖是教學模型，不是效能量測，也不是任何產品完整的實作。

建議先猜下一步，再按按鈕。每張圖下方會說明「這次改變了什麼、為什麼能改」。窄螢幕可以左右捲動圖；Logical time 保留完整線條，只逐一揭露數字。

1. 通訊：沒有回覆，不代表什麼都沒發生

Client 送出 request，等到 timeout，卻沒有收到 response。這個觀察可能對應三種現實：server 還在處理、操作做完但回覆遺失，或 server 已停止。

同步 system model 假設處理與傳輸時間有已知上界；非同步模型不提供這個保證。這不是「同步 API 會不會卡住 thread」的意思。有時間上界，也仍要搭配通道與失效假設，才能判斷逾時代表什麼。

比較「回覆遺失」與「Server 失效」：client 看到的結果一樣，server 端發生的事卻可能不同。 所以 timeout 代表「目前不知道結果」，不是「確定沒有執行」。

實務延伸：有副作用的重試，需要 idempotency key、可查詢的操作狀態或對帳機制。這不是把 timeout 調長就能解決。

2. P2P：找位置，和把內容下載完，是不同問題

三種機制不全在解同一件事：

• Gnutella flooding： 不知道檔案在哪，就請鄰居繼續問。TTL 每跳消耗，Query ID 避免重複轉送；QueryHit 沿查詢的反向路徑回來。
• Chord lookup： 把節點與 key 放到 identifier ring。每個 finger 是 successor(n + 2^i)，用長距離跳轉加速找路，最後到 key 的 successor。
• BitTorrent rarest-first： 已找到可交換檔案的 peer，接著決定先下載哪個缺少的 piece。數的是目前鄰居有幾份，不是全網有幾份。

Flooding 的初始 TTL 固定為 3，「下一步」代表多走一跳，不是增加 TTL。圖只標亮首次探索的路徑，沒有把所有重複查詢與回覆都畫出來。

Chord 查找 key 143：19 → 96 → 120 → 151。143 是 key 的位置，不是節點；真正負責的是順時針第一個節點 151。這裡假設 finger table 正確且節點未失效，維護與失效處理是另一筆成本。

3. Gossip：傳播快，不代表每一輪都有保證

Push 是「我知道新消息，告訴你」；pull 是「你有我不知道的消息嗎？」；push-pull 在查詢時帶上自己的更新，回覆也能帶回對方的更新。

Push-pull 不需要中央控制器判斷是否已經過半。 節點通常也不知道全體有多少人收到了。

同時看覆蓋率和封包數。Pull 的查詢與回覆是兩個封包；對方沒有新資料，是成功但沒收穫的查詢，不是 packet loss。

模擬器固定亂數種子，重設後可以重播。每個參與的節點一輪選兩個對象，允許重複選中；新收到更新的節點從下一輪開始傳播。分輪是為了方便觀察，真實協定不需要全體同步。

全部收到後仍可按下一輪，看重複傳輸的成本。實作還要決定保留多久、何時停止傳播，本圖不模擬這些策略；gossip 也無法跨過永久的網路分割。

4. SWIM：間接探測與反駁懷疑，要分開看

Probe 負責蒐集證據，dissemination 負責散播 membership 判斷；兩者可以共用 ping／ACK，把更新夾帶在訊息裡。

三條路徑各走一次：

1. 間接探測成功： P0 收不到 P3 的直接回覆，請 P1、P2 協助。P3 回 ACK 給 P1，P1 再轉給 P0。這能繞過部分路徑問題，不必提高 incarnation。
2. 反駁懷疑： 直接與間接探測都逾時，P0 先記錄 suspect(P3,4)。P3 收到懷疑後，自己提高 incarnation，送出 alive(P3,5)；P0 在懷疑期限內收到，才恢復 alive。
3. 持續無回應： 懷疑期限到期，P0 將 P3 標為 failed，再把判斷傳出去。

圖上是 P0 的 membership view，不是上帝視角的真相。若 P3 其實只被隔離，也可能遭到誤判。依課程狀態機，被誤移除的程序需要重新加入，不是提高 incarnation 就無條件復活。

5. Logical time：每個數字都只用當下知道的資訊

沿同一張圖分別計算 Lamport 與 vector clock。所有 process 從 0 開始；實心圓是內部事件，訊息箭頭的起點與終點本身也是事件。

Lamport 的規則很短：

• 內部事件、送出訊息：自己的數字加一。
• 收到訊息：max(本機時間, 訊息時間) + 1。

例如 P1 第一次收到 P2 的訊息前，本機是 3，訊息帶來 7，所以結果是 8，不是 4。

Vector 接收時先逐格取最大值，再把自己的那格加一。圖下方會顯示實際合併的向量；e1 表示只增加 P1 那格，其他 process 同理。

有因果關係，Lamport 數值一定往前；但數值較大，不能反向證明因果。Vector 則逐格比較：全部不大於、且至少一格較小，才是向量先後；若兩邊各有較大的格子，事件就是 concurrent。

播放次序只是方便算答案的一種合法次序，不代表 concurrent event 具有共同的實體時鐘。

6. Multicast ordering：收到，不代表現在就能交付

Receiver 可以先收到資料，放進 hold-back queue，等條件滿足才交給應用程式。

注意下方的抵達順序、等待訊息、已交付訊息。

FIFO 只管同一 sender。B 先收到 A 的序號 2，不能跳過序號 1。等 1 交付後，再釋放 2；另一個 sender 有獨立的計數。

Causal 還要檢查前置訊息。B 看過 A 的 m1 才送 m2，C 就不能先交付 m2。向量 (1,1,0) 表示 C 必須已看過 A 的第一則 multicast。這裡數的是 multicast，不是上一節每個 local／send／receive event 都增加的 clock。

Total 讓所有接收者採用同一順序。圖使用課程的 sequencer：獨立發出的 x、y 被編成 y:1、x:2，receiver 即使先收到 x:2，也要等 1。這不代表 y 造成 x；單獨的 total order 也不自動保證 FIFO 或 causal order。

排序不等於可靠傳送。缺少的訊息永遠不來，等待就不會自行結束；補傳、成員變更與 sequencer 復原需要其他機制。

7. MapReduce：資料往哪裡走，決定失效要重算什麼

輸入是 red blue 和 blue blue。兩個 mapper 各自產生 (word,1)；shuffle 把相同 key 送到同一個 reducer；reduce 才加總。

正常結果是 red=1, blue=3。Blue 的三個 1 來自兩個 mapper，不是一個 mapper 只配一個 reducer。

切到「Map 輸出遺失」：HDFS input 還有副本，但 worker 本機的 output 不在了。若 reducer 還沒抓到那份 partition，就得重跑 map。輸入與最終結果持久化，中間結果可以重算。

再看 straggler：同一 reduce task 啟動第二份 attempt，採用先完成的成功結果，不是把兩次結果相加。若慢是熱門 key 資料太多，換機器重算仍然很多；推測執行不是資料偏斜的解法。

圖省略 YARN 的資源配置往返。安全重跑也假設計算具合適的可重現性；任意外部副作用不會自動得到 exactly-once 保證。

8. Quorum：交集是起點，不是完整的正確性證明

N=5 份副本，write 等 W 份確認，read 等 R 份回覆。假設一次寫入已完成、沒有同時寫入與失效，把 W 份 v1 更新為 v2。

圖刻意把 read set 排到最不重疊的位置：

最少重疊數 = max(0, R + W − N)

先試 R=2, W=2：read 可以完全錯過新值。改成 R=3, W=3：不管怎麼選，至少讀到一份確認過該次寫入的副本，之後還要正確比較版本。

2W > N 只表示兩次成功寫入的確認集合相交，不等於共享節點自動幫你鎖住或排序所有寫入。Concurrent writes、未完成的 writes、版本規則、副本集合變動，都需要額外推理。

R、W 越大，等待的人越多，也越容易因部分副本不可達而湊不齊回覆。它不是無代價的「強一致性開關」。

9. Cassandra：Flush、compaction、repair 不是同一件事

• Flush： 把記憶體的 memtable 寫成 SSTable。
• Compaction： 在同一 replica 內合併 SSTable、整理版本。
• Repair： 處理不同 replica 之間的不一致。

讀取範例有三種 SSTable。A 的 Bloom filter 說「一定沒有」，可以跳過；B 說「可能有」，查 index 才知道是 false positive；C 才真正找到資料。Bloom filter 不會提供 value，「可能有」也不是存在的證明。

Repair 只查 R1、R2。把 R2 修成 v3，不代表沒被查詢的 R3 也變成 v3。「收到的最新版本」和「全系統最新版本」仍是兩回事。

版本補充：圖以 blocking read repair 示意，先修補再回覆。Cassandra 4.0 起提供資料表層級的 BLOCKING／NONE 選項，不能概括成「read repair 一定在背景非同步執行」；它也不能取代其他 repair 作業。Apache Cassandra 官方說明

複習時，把問題縮成這四句

1. 這個 process 現在知道什麼？哪些只是猜測？
2. 這一步在等誰、等什麼條件？
3. 哪份狀態真的改了？別的副本也改了嗎？
4. 這時失效，是靠重送、重算，還是持久化資料恢復？

能沿著圖回答這四題，比只背演算法名稱更接近理解。

來源與示意範圍

主要依據 Indranil Gupta 的 Cloud Computing Concepts, Part 1 投影片與逐字稿。以下講次方便回到課程複習；圖與小型例子是重新繪製，不是官方互動教材。

假設與省略範圍已寫在各節。課程概念模型與產品現行版本應分開理解。