深度探秘

當一筆交易橫跨多台伺服器

從單一伺服器到分散式

在前一章，我們討論的交易只存取單一伺服器上的物件。但真實世界裡，一筆交易常常需要碰好幾台不同電腦上的資料。

分散式交易 (distributed transaction)：存取由多台伺服器管理之物件的交易（不論它是平面或巢狀結構）。

原子性帶來的挑戰

交易最重要的性質之一是原子性 (atomicity)：一筆交易裡的所有動作，要嘛全部生效，要嘛全部不生效，不能只做一半。

當交易只在一台伺服器上時，這台伺服器自己說了算。但分散式交易牽涉多台伺服器，原子性就要求：

• 要嘛所有涉及的伺服器都 **commit（提交）**這筆交易；
• 要嘛所有伺服器都 **abort（中止）**這筆交易。

不能 X 伺服器提交、Y 伺服器卻中止，否則資料就不一致了。

誰來統一指揮？

為了達成「同進退」，其中一台伺服器會擔任協調者 (coordinator) 的角色，負責確保所有伺服器得到相同的結果。協調者怎麼做到，取決於選用的協定——最常用的就是後面會談的兩階段提交協定 (two-phase commit protocol)。

生活妙喻

三個人合送一份大禮

合送禮物的約定

想像你和兩位朋友要合送一份生日大禮：你出蛋糕、朋友 A 出花束、朋友 B 出禮物卡。你們有個約定：

要嘛三樣都到位、一起送出；要嘛大家都不送，各自把錢拿回來。

絕不能變成只有蛋糕送出去、花和卡片卻沒買——那壽星只收到一塊孤零零的蛋糕，場面很尷尬。

對應關係

只要有一個人臨時說「我準備不了」，整個合送計畫就取消、大家退錢——這正是分散式交易「全有或全無」的精神。

實用超能力

跨行轉帳背後的祕密

一個經典場景：跨行轉帳

你在手機上按下「從 A 帳戶轉 4 元到 C 帳戶」。但 A 在 BranchX 銀行、C 在 BranchZ 銀行——這就是一筆分散式交易！

背後發生的事：

1. 扣款：BranchX 從 A 扣 4 元（a.withdraw(4)）。
2. 入帳：BranchZ 給 C 加 4 元（c.deposit(4)）。

如果扣款成功、入帳卻失敗（例如 BranchZ 當機），原子性就會讓整筆交易中止：A 的錢退回去，就像什麼都沒發生。

程式碼長相

T = openTransaction
  a.withdraw(4);   // 在 BranchX
  c.deposit(4);    // 在 BranchZ
closeTransaction

從程式設計師的角度看，這幾行就像在「同一筆交易」裡，但底層其實有多台伺服器在偷偷協調。正是這個機制，讓你不用擔心錢「轉到一半不見」。

深度探秘

兩種組織分散式交易的方式

平面交易 (flat transaction)

在平面交易中，客戶端依序對好幾台伺服器發出請求。

• 它會完成一個請求後才進行下一個，所以是循序 (sequentially) 存取各伺服器的物件。
• 當伺服器使用鎖定時，一筆平面交易在同一時間只能等待一個物件。

例如交易 T 依序對伺服器 X、Y、Z 上的物件操作。

巢狀交易 (nested transaction)

在巢狀交易中，最上層的交易可以開啟子交易 (subtransaction)，每個子交易又能再開更深一層的子交易，深度不限。

關鍵特性：

同一層的子交易可以「並行 (concurrently)」執行；若它們在不同伺服器上，甚至能真正「平行 (in parallel)」跑。

結構示意

flowchart TD
  T[頂層交易 T] --> T1[子交易 T1 在 X]
  T --> T2[子交易 T2 在 Y]
  T1 --> T11[子交易 T11 在 M]
  T1 --> T12[子交易 T12 在 N]
  T2 --> T21[子交易 T21 在 N]
  T2 --> T22[子交易 T22 在 P]

T1 與 T2 並行，底下四個子交易也並行。

生活妙喻

一個人跑腿 vs 一群人分頭辦事

辦一場活動的兩種辦法

假設你要辦一場聚會，需要：訂蛋糕、買飲料、租場地、印邀請卡。

平面交易 = 一個人跑腿：你自己一站一站去，訂完蛋糕才去買飲料、買完才去租場地……一次只能站在一個櫃台前排隊等。事情會完成，但很花時間。

巢狀交易 = 分頭辦事：你當總指揮（頂層交易），派出兩位組長（T1、T2），每位組長底下又各帶兩位小幫手（T11、T12、T21、T22）。大家同時分頭去不同店家辦事，效率大增。

對應關係

巢狀的好處就是：能同時做的事就同時做，整體更快完成。

實用超能力

用巢狀結構加速雙重轉帳

場景：一次做兩筆轉帳

客戶端想做兩件事：

1. 從 A 轉 10 元到 C
2. 從 B 轉 20 元到 D

其中 A 在伺服器 X、B 在 Y、C 與 D 在 Z。這總共需要四個動作：兩次 withdraw、兩次 deposit。

為什麼用巢狀更快？

如果用平面結構，四個動作得一個接一個做完。

如果用巢狀結構，把它拆成四個子交易：

T = openTransaction
  openSubTransaction; a.withdraw(10);   // 子交易 1
  openSubTransaction; b.withdraw(20);   // 子交易 2
  openSubTransaction; c.deposit(10);    // 子交易 3
  openSubTransaction; d.deposit(20);    // 子交易 4
closeTransaction

這四個請求可以平行執行（因為它們碰的是不同伺服器上的物件），整體效能就比循序版本好得多。

小提醒

巢狀結構還有一個重要特性：每個子交易在父交易之後開始、在父交易之前結束——就像小幫手要在組長收工前先回報。

深度探秘

誰指揮、誰配合

交易如何開始

客戶端透過向任一伺服器的協調者送出 openTransaction 請求來啟動交易。被聯絡到的協調者執行 openTransaction，並回傳一個交易識別碼 (TID, transaction identifier) 給客戶端。

分散式系統中的 TID 必須全域唯一。簡單做法是讓 TID 包含兩部分：建立它的伺服器識別碼（例如 IP 位址）＋該伺服器內的唯一編號。

協調者 vs 參與者

• 協調者 (coordinator)：開啟交易的那台伺服器就成為這筆分散式交易的協調者，最後負責提交或中止整筆交易。
• 參與者 (participant)：每台管理「被交易存取之物件」的伺服器都是參與者，負責追蹤該伺服器上涉及交易的可回復物件，並配合協調者執行提交協定。

join：參與者報到

當某物件第一次被交易碰到，它所在的伺服器若還沒通知協調者，就會用 join 操作向協調者報到：

join(Trans, 指向參與者的參考)

flowchart TD
  C[客戶端] -->|openTransaction| Coord[協調者 在 BranchX]
  Coord -->|記錄參與者清單| P1[參與者 BranchY]
  Coord --> P2[參與者 BranchZ]
  P1 -->|join| Coord
  P2 -->|join| Coord

到客戶端呼叫 closeTransaction 時，協調者已握有所有參與者的參考。

生活妙喻

婚禮總召與各廠商

一場婚禮的籌備

把分散式交易想成籌備婚禮：

• 新人聯絡了婚禮總召（協調者）。總召給這場婚禮一個唯一的案件編號（TID），方便日後溝通。
• 隨著籌備進行，花店、餐廳、攝影師陸續被找來幫忙——他們就是參與者。
• 每個廠商接到工作時，會主動向總召報到：「我是這場婚禮 No.123 的花店，把我列進名單」——這就是 join。

為什麼要互相認識？

總召手上有完整的廠商名單，每個廠商也知道總召是誰。等到婚禮當天要「確認一切就緒」時，總召才能逐一問每個廠商：「你那邊 OK 嗎？」這正是後面兩階段提交的基礎。

實用超能力

追蹤一筆銀行交易的角色分工

場景：跨三家分行的轉帳

客戶端的交易 T 牽涉帳戶 A、B、C、D，分別在 BranchX、BranchY、BranchZ。T 要從 A 轉 4 元到 C、從 B 轉 3 元到 D。

運作步驟：

1. openTransaction 與 closeTransaction 都送到協調者（位於其中一台伺服器，例如 BranchX）。
2. 當客戶端呼叫 b.withdraw(T, 3)，接收呼叫的物件 B（在 BranchY）通知它的參與者：「這個物件屬於交易 T」。
3. 若 BranchY 還沒通知協調者，參與者就用 join 報到。
4. TID 會被當作額外引數傳遞，讓接收方能轉交給協調者。

一個重要的逃生門

參與者若因某種原因無法繼續交易，它可以呼叫協調者的 abortTransaction 來中止整筆交易。

這個設計很關鍵：它讓任何一個「做不下去」的參與者都能踩煞車，而不是被迫硬撐——這也是後面兩階段提交要保障的能力。

深度探秘

最直覺的做法為何有漏洞

最簡單的想法：一階段提交

交易結束時，最直覺的做法是：協調者把「提交」或「中止」的請求傳給所有參與者，並不斷重試直到每個參與者都確認執行完畢。這就是一階段原子提交協定 (one-phase atomic commit protocol)。

致命缺陷

這個簡單做法不夠用，因為它不允許伺服器在客戶端要求提交時，單方面決定中止。

但伺服器確實可能「想提交卻提交不了」，原因多半和並行控制有關：

• 鎖定：為了解開死結，某筆交易可能被中止——而客戶端在再次請求前根本不知情。
• 樂觀並行控制：某伺服器的驗證失敗，就會決定中止交易。
• 當機被替換：協調者可能不知道某伺服器在交易進行中當機又被換掉——這台新伺服器必須中止交易。

結論

既然任何一個參與者都可能「做不到」，協定就必須給它一個說 No 的機會——這正是兩階段提交要解決的。

flowchart TD
  A[客戶端要求提交] --> B[一階段: 協調者直接命令全部提交]
  B --> C{某參與者其實提交不了}
  C -->|沒有說 No 的機會| D[原子性被破壞]

生活妙喻

老師直接宣布出遊 vs 先問大家

班級出遊的兩種決策

一階段（直接宣布）：班長直接在群組宣布「明天大家一起去郊遊！」並不斷催大家確認。問題是——有人其實家裡有事去不了，可是班長從沒問過他願不願意，只是一味要他「確認收到」。結果到了現場才發現少人，計畫被打亂。

兩階段（先徵詢）：聰明的班長會先問一輪：「明天郊遊，能去的回我一聲。」等大家都回覆「可以」之後，才正式宣布「那就明天見！」。只要有一個人說「我去不了」，計畫就調整或取消。

對應關係

關鍵差別：有沒有給每個人「說不行」的機會。

實用超能力

辨認哪些情況會讓伺服器想中止

為什麼伺服器會「想提交卻不行」？

理解這些情境，你就能看懂為何非得有兩階段提交不可：

1. 死結解除：使用鎖定時，系統偵測到死結，挑一筆交易中止來解套。被中止的交易，其參與者顯然無法提交。
2. 樂觀驗證失敗：使用樂觀並行控制時，伺服器在驗證階段發現與其他交易衝突，只好中止。
3. 伺服器當機被替換：交易進行到一半，某台伺服器當機，換上的新伺服器沒有舊狀態，只能中止這筆交易。

設計啟示

兩階段提交協定就是為了讓任何參與者都能中止它那部分的交易而設計的。

由於原子性的要求：只要一部分被中止，整筆交易就必須中止。所以協定要先收集所有人的「意願」，再做出一致的決定。

下次你看到「prepare / commit」這種兩步驟設計，就知道它背後的動機：先確認大家都做得到，再一起動手。

深度探秘

投票階段與完成階段

兩個階段

兩階段提交協定 (two-phase commit protocol, 2PC) 分成投票階段與完成階段。

Phase 1（投票階段）

1. 協調者對每個參與者送出 canCommit? 請求。
2. 參與者收到後回覆它的票（Yes 或 No）。投 Yes 前，它會先把改動的物件存進永久儲存以準備提交；若投 No，它立即中止。

Phase 2（依投票結果完成） 3. 協調者收集所有票（含自己的）：

• (a) 若無故障且全是 Yes → 決定提交，對每個參與者送 doCommit。
• (b) 否則 → 決定中止，對投 Yes 的參與者送 doAbort。

4. 投 Yes 的參與者等待 doCommit 或 doAbort；收到後照做，若是提交則回傳 haveCommitted 確認。

關鍵規則

一旦參與者投了 Yes，就不能反悔去中止。所以投 Yes 前必須確保自己未來一定能完成提交（即使中途當機被替換）。能保證做到的狀態稱為 prepared（已準備）——它把所有改動的物件與「prepared」狀態都存進永久儲存。

生活妙喻

婚禮當天的兩輪確認

婚禮總召的兩輪呼叫

回到婚禮的比喻。當天總召（協調者）要確認一切就緒：

第一輪（投票）：總召打電話問每個廠商：「你準備好了嗎？」（canCommit?）

• 花店把花都備齊、車也叫好，回答「好了！」（Yes）。為了保證真的能交付，它甚至先把花裝上車——這就是 prepared，東西已就位，跑不掉。
• 若某廠商說「我交不出來」（No），總召就知道要取消。

第二輪（執行）：

• 如果所有廠商都說好了，總召下令「開始！」（doCommit），大家把東西送到現場。
• 只要有人說不行，總召就通知大家「取消」（doAbort）。

為什麼說好了就不能反悔？

廠商一旦把花裝上車、回報「我準備好了」，就等於承諾一定交得出來，即使老闆臨時生病（伺服器當機），換個人來也能照著清單把花送出去。這就是 prepared 的精神：承諾前先確保自己跑不掉。

實用超能力

讀懂 2PC 的訊息流

五個關鍵操作

完整訊息流

sequenceDiagram
  participant C as 協調者
  participant P as 參與者
  C->>P: canCommit?
  Note over P: 存物件到永久儲存, 進入 prepared
  P->>C: Yes
  Note over C: 收齊所有 Yes, 決定提交
  C->>P: doCommit
  Note over P: 提交
  P->>C: haveCommitted

haveCommitted 的真正角色

第 4 步的 haveCommitted 不是協定正確性的必要部分——少了它協定仍能正確運作。它的用途是讓協調者知道「資訊不再需要了」，可以清掉這筆交易的舊資料。下次你看到這類「確認收到」訊息，記得它常是為了清理而非決策。

深度探秘

uncertain 狀態與逾時動作

最棘手的處境：uncertain（不確定）

當一個參與者已投 Yes，正等待協調者告知結果（commit 或 abort），它就處於 **uncertain（不確定）**狀態。此時它：

• 不知道最終結果，不能自行決定下一步；
• 它的物件仍被鎖住，無法釋放給其他交易使用。

它能做的是向協調者發 getDecision 詢問結果。但若協調者也當機了，它就得苦等到協調者被替換——這會造成嚴重延遲。

各步驟的逾時動作

協定在每個可能卡住的步驟都設計了逾時動作（因為非同步系統中，逾時不一定代表對方真的故障）：

• 參與者已做完工作、但還沒收到 canCommit?：因為還沒做任何決定，它可以單方面中止。
• 協調者在等投票：等太久可以決定中止，並對已投票者送 doAbort。
• 參與者投 Yes 後在等結果（uncertain）：只能 getDecision，無法單方面決定。

flowchart TD
  A[參與者投 Yes] --> B[進入 uncertain 等待結果]
  B --> C{協調者有回覆嗎}
  C -->|有| D[依指示 commit 或 abort]
  C -->|協調者當機| E[卡住, 物件無法釋放, 苦等替換]

三階段提交協定 (three-phase commit) 就是為了緩解這種延遲而設計，但代價是正常情況需要更多訊息與回合。

生活妙喻

簽了賣身契卻等不到老闆回覆

進退兩難的廠商

想像花店已經回報「我準備好了！」（投 Yes），把花裝上車，現在就等總召一聲令下：到底是送過去、還是取消？

這時花店陷入 uncertain：

• 它不能自作主張把花送出去（萬一其他廠商出包、婚禮取消怎麼辦）。
• 它也不能擅自把花拿去賣別人（這些花已經被這場婚禮鎖定了）。
• 它只能一直打電話問總召：「到底要不要送？」（getDecision）

最慘的情況：總召手機沒電（協調者當機）。花店只能抱著一車花乾等，直到總召換了新手機、找回名單為止。這段期間花就這樣被卡住，誰也用不了。

對比：還沒裝車的廠商

如果某廠商根本還沒接到「準備好了嗎」的詢問（還沒收到 canCommit?），它倒可以爽快地自己取消——反正還沒做任何承諾。

實用超能力

估算 2PC 的成本

正常情況的訊息成本

假設一切順利（協調者、參與者、通訊都不故障），有 $N$ 個參與者時：

• canCommit? 訊息與回覆：各 $N$ 個
• doCommit 訊息：$N$ 個

所以訊息成本與 $3N$ 成正比，時間成本是三回合訊息：

$$\text{訊息數} \approx 3N, \quad \text{時間} = 3 \text{ 回合}$$

注意：haveCommitted 訊息不計入成本估算，因為協定沒有它也能正確運作。

最壞情況與保證

最壞情況下可能有任意多次伺服器與通訊故障。但 2PC 被設計成能容忍一連串的故障，並保證最終一定會完成——只是無法保證在特定時間內完成。

實務取捨

所以選擇協定時要權衡：你比較在意正常情況的效率，還是故障時的延遲？這就是工程上的經典取捨。

深度探秘

暫定提交與孤兒子交易

暫定提交 (provisional commit)

當一個子交易完成時，它會獨立決定是暫定提交還是中止。

暫定提交 ≠ prepared！ 暫定提交不寫永久儲存——它只代表「我順利做完了，之後被問到時大概會同意提交」。若伺服器隨後當機，替換上來的程序無法提交它。

相對地，prepared 是保證一定能提交。

子交易的命運綁在祖先身上

• 子交易的 TID 是父交易 TID 的延伸，從中可推算出父／頂層交易的 TID。
• 若父交易中止，子交易被迫中止。
• 父交易（含頂層）可以提交，即使它的某個子交易已中止——程式會依子交易成功與否採取不同動作。

孤兒 (orphan)

當某子交易的祖先中止（明確中止或協調者當機），它就成為孤兒。例如 T2 中止時只向父交易報告 abort，卻沒傳遞底下 T21、T22 的資訊，於是 T21、T22 成了孤兒。孤兒可用 getStatus 詢問父交易狀態；已暫定提交但祖先已中止的子交易，應該中止。

flowchart TD
  T[頂層交易 T 決定提交] --> T1[T1 提交]
  T --> T2[T2 中止]
  T1 --> T11[T11 中止]
  T1 --> T12[T12 暫定提交 將參與]
  T2 --> T21[T21 暫定提交 但成孤兒]
  T2 --> T22[T22 暫定提交 但成孤兒]

生活妙喻

公司專案的層層回報

一個大專案的回報鏈

把巢狀交易想成公司的大專案：總經理（頂層交易 T）底下有兩位經理（T1、T2），每位經理底下又各有兩位組員。

• 組員做完工作後跟經理說「我這部分弄好了，初步沒問題」——這是暫定提交。注意，他只是口頭回報，還沒把成果正式存檔備份（沒寫永久儲存）。
• 經理 T2 整個專案被砍掉（中止），那麼 T2 底下兩位組員的成果再好也作廢——子交易隨祖先中止。
• 但總經理可以決定：即使 T2 那條線砍了，T1 這條線還是照常推進——父交易可在某子交易中止下仍提交。

孤兒組員

T2 被砍時，只跟總經理說「我這條線取消」，沒提底下兩位組員。這兩位組員就成了孤兒——他們還傻傻地以為自己的成果有效。他們得主動打聽（getStatus）：「我主管的專案還在嗎？」一問才發現上面早砍了，只好認命作廢。

實用超能力

階層式 vs 平面式兩階段提交

頂層交易扮演協調者

頂層交易完成時，扮演 2PC 的協調者，參與者名單是所有「已暫定提交且沒有中止祖先」的子交易協調者。第二階段與非巢狀情況相同。執行方式有兩種：

階層式 (hierarchic)

canCommit? 訊息沿樹一層層往下傳：T 傳給 T1，T1 再傳給它的子交易……每個參與者收齊後代的回覆才回報給父交易。

• canCommit?(trans, subTrans)：第一引數是頂層 TID，第二引數是發話者的 TID。
• 優點：每一層只需查看自己直屬子交易。

平面式 (flat)

頂層協調者直接對所有暫定提交清單上的子交易協調者發 canCommit?。

• canCommit?(trans, abortList)：第二引數帶一份中止清單。
• 為何需要中止清單？因為同一伺服器可能同時跑著「該提交」和「該中止」的子交易（例如伺服器 N 上的 T12 該提交、T21 卻因父交易 T2 中止而該中止）。參與者得靠中止清單剔除有中止祖先的子交易。

比較

Moss 偏好平面式，因為協調者能直接和所有參與者溝通，省去沿樹來回傳訊。

深度探秘

本地鎖與全域序列化

各管各的鎖

在分散式交易中，物件的鎖由所在伺服器在本地持有。本地的鎖管理員 (lock manager) 自行決定要授予鎖、還是讓請求的交易等待。

但有個關鍵限制：

本地鎖管理員不能釋放任何鎖，直到它知道這筆交易在所有涉及的伺服器上都已提交或中止。

所以在原子提交協定進行期間，物件仍被鎖住、無法給其他交易用（不過被中止的交易會在協定第一階段後就釋放鎖）。

隱藏的危機：不同伺服器的順序衝突

各伺服器的鎖管理員獨立設定鎖，因此不同伺服器可能對交易強加不同的順序。看這個交錯：

結果：在伺服器 X 是 T 先於 U，在伺服器 Y 卻是 U 先於 T。這種互相矛盾的順序會造成循環相依，進而演變成分散式死結 (distributed deadlock)。

生活妙喻

兩條走廊上的禮讓僵局

狹窄走廊的對峙

想像兩條狹窄走廊（伺服器 X 和 Y），各只能容一人通過。

• 小明（交易 T）先站上走廊 X，等著要進走廊 Y。
• 小華（交易 U）先站上走廊 Y，等著要進走廊 X。

現在：

• 在走廊 X，是小明先佔（T 先於 U）；
• 在走廊 Y，是小華先佔（U 先於 T）。

兩人都堵在原地等對方先讓——誰也不肯放手，誰也走不了。這就是分散式死結。

為什麼鎖不能早早放掉？

你可能會想：那小明先退一步不就好了？問題是，在交易裡，鎖必須撐到整筆交易在所有伺服器都塵埃落定才能放——因為提早放手可能破壞一致性。這份「堅持」雖然保證了正確性，卻也埋下了死結的種子。

實用超能力

看懂鎖定如何引發死結

全域序列化的責任

每台伺服器負責讓存取自己物件的交易在本地序列化；而一群伺服器共同負責讓分散式交易全域序列化。原則是：

若在某伺服器上 T 在 U 之前（衝突存取），那麼在所有它們衝突存取的伺服器上，都必須是 T 在 U 之前。

死結被偵測後怎麼辦

flowchart TD
  A[偵測到分散式死結] --> B[挑一筆交易中止來解套]
  B --> C[協調者被告知]
  C --> D[協調者在各參與者中止該交易]
  D --> E[該交易的鎖被釋放, 其他人得以前進]

當死結被偵測到，系統會中止其中一筆交易來打破僵局。協調者會被告知，並在所有相關參與者上中止這筆交易，連帶釋放它的鎖。

給你的啟示

用鎖定做並行控制時，死結是無法完全避免的副作用。所以系統不是『杜絕死結』，而是『偵測並解除死結』——這正是下一章邊追蹤演算法要登場的原因。

深度探秘

全域唯一時間戳記

從單機到分散式

在單一伺服器交易中，協調者在交易啟動時發給它一個唯一時間戳記 (timestamp)，並依時間戳記順序提交物件版本來達成序列等價。

在分散式交易中，要求每個協調者發出全域唯一的時間戳記：

交易第一次接觸到的協調者，發給客戶端一個全域唯一的交易時間戳記；這個時間戳記會被傳遞給後續每個執行該交易操作的伺服器協調者。

如此一來，所有伺服器都用同一個時間戳記來排序這筆交易。

時間戳記的結構

為了讓所有協調者對時間戳記順序有一致看法，時間戳記是一個配對：

$$\langle \text{本地時間戳記}, \ \text{伺服器識別碼} \rangle$$

比較時，先比本地時間戳記，伺服器識別碼較不重要（用來打破平手）。這樣即使各伺服器本地時鐘沒有同步，也能對交易達成相同的排序。

為何仍希望時鐘大致同步？

為了效率，希望各協調者發出的時間戳記大致同步。如此一來，交易的排序通常會對應它們在真實時間中啟動的順序——可用第 14 章的同步實體時鐘來達成。

生活妙喻

全國連鎖店的統一取號機

統一發號碼牌

想像一家全國連鎖餐廳，每家分店都會服務同一群常客。為了讓所有分店對「誰先誰後」有一致看法，總部規定：

• 顧客第一次進任何一家分店時，就拿到一張全國唯一的號碼牌（全域唯一時間戳記）。
• 之後不管他去哪家分店，都亮同一張號碼牌——所有分店都依這張牌的號碼決定服務順序。

號碼牌怎麼編？

號碼牌寫成 〈時間, 分店代號〉。先比時間，萬一兩人時間一模一樣，就用分店代號分高下（打破平手）。這樣即使各分店的時鐘沒對得很準，大家還是能對先後順序達成一致。

為何時鐘最好還是對一下？

如果各分店時鐘大致同步，號碼順序就會貼近顧客真正光臨的先後，服務體驗更自然——這就是為何實務上仍希望時鐘大致同步。

實用超能力

時間戳記排序下的提交特性

衝突在操作當下就解決

使用時間戳記排序時，衝突是在每個操作執行的當下就用規則解決的（依第 16 章的規則）。如果某次衝突的解決需要中止某交易，協調者會被告知，並在所有參與者上中止它。

一個很棒的結果

因此，任何走到客戶端要求提交這一步的交易，通常一定能提交；兩階段提交的參與者正常都會同意提交。

唯一不會同意提交的情況是：參與者在交易進行中當機了。

flowchart TD
  A[操作執行時即時檢查衝突] --> B{衝突需中止}
  B -->|是| C[協調者通知各參與者中止]
  B -->|否| D[交易順利推進到提交]
  D --> E[2PC 參與者通常都同意提交]

對你的意義

這代表在時間戳記排序下，「中止」大多發生在交易過程中、而非提交時刻。提交階段相對單純——衝突早就在過程中被擋掉了。這也是不同並行控制策略在分散式環境下的有趣對比：鎖定容易在提交前才爆出死結，時間戳記排序則傾向把問題提早解決。

深度探秘

分散式驗證的兩個難題

先回顧樂觀並行控制

樂觀並行控制 (optimistic concurrency control) 讓交易先盡情執行，到提交前才驗證 (validate)。交易編號在驗證開始時指派，並依編號順序序列化。分散式交易由一群獨立伺服器各自驗證它存取的物件，驗證發生在兩階段提交的第一階段。

難題一：提交死結 (commitment deadlock)

第 16 章為了簡化，規定一次只有一筆交易能做驗證與更新。考慮以下交錯：T 與 U 在 X 是 T 先於 U、在 Y 是 U 先於 T。若 T、U 約同時開始驗證，X 先驗 T、Y 先驗 U——

兩台伺服器都得等對方先驗完那筆才能驗自己的，於是互相卡死——這就是提交死結。

難題二：順序不一致

分散式交易的兩階段提交可能耗時較久，期間其他交易都進不了驗證。為此，每台伺服器採用平行驗證 (parallel validation)，允許多筆交易同時處於驗證階段（後向驗證須額外檢查規則 3：被驗交易的寫集合要和較早重疊交易的寫集合比對）。

但若各伺服器只做獨立驗證，可能把同一組交易排成不同順序（X 是 T 先 U、Y 是 U 先 T）——必須防止這種情況。

生活妙喻

兩家審核處互等對方蓋章

互卡的審核流程

想像辦一件事需要兩個審核處（伺服器 X、Y）都蓋章，而每個審核處規定「一次只能審一份案子」。

• 審核處 X 手上先排了你的案子（T），但要審完才肯處理隔壁的案子（U）。
• 審核處 Y 剛好相反，先排了 U，要審完才肯處理 T。

結果 X 在等 Y 先審完 U、Y 在等 X 先審完 T——兩邊互等，誰也動不了。這就是提交死結。

解法的直覺

平行驗證就像審核處改成「可以同時審多份案子」，不再一次一份，自然就不會互卡。

但即使能同時審，還有個問題：兩家審核處可能對「誰的案子排前面」各有各的認定（X 覺得你先、Y 覺得隔壁先）。如果不協調，最後蓋章順序就會打架——這就需要額外的全域協調來確保大家排同一個順序。

實用超能力

兩種確保全域一致順序的方法

怎麼防止各伺服器排出矛盾順序？

伺服器們必須阻止「X 是 T 先 U、Y 是 U 先 T」這種情況。書中介紹兩種途徑：

方法一：全域驗證 (global validation)

每台伺服器先做完本地驗證後，再做一次全域驗證，檢查各伺服器排序的組合是否可序列化——也就是確認被驗交易沒有捲入循環。

方法二：共用全域交易編號

讓某交易的所有伺服器在驗證一開始就用同一個全域唯一的交易編號。兩階段提交的協調者負責產生這個編號，並透過 canCommit? 訊息傳給參與者。由於不同伺服器可能協調不同交易，這些伺服器（如同分散式時間戳記排序）必須對它們產生的編號有一致的順序。

flowchart TD
  A[本地驗證各自完成] --> B{如何確保全域一致順序}
  B -->|方法一| C[全域驗證: 檢查組合無循環]
  B -->|方法二| D[共用全域交易編號: 協調者產生並下發]

進階一瞥

Agrawal 等人提出偏好唯讀交易的變形，以及 MVGV（多版本廣義驗證）演算法——它是一種平行驗證，確保交易編號反映序列順序，必要時甚至允許更改交易編號以救回原本會驗證失敗的交易。重點觀念是：分散式樂觀控制的核心挑戰，就是讓所有伺服器對交易順序達成共識。

深度探秘

死結就是等待圖中的環

等待圖 (wait-for graph)

大多數死結偵測都靠在等待圖中找環。等待圖是一個有向圖：

• 節點代表交易（與物件）；
• 邊代表「物件被某交易持有」或「某交易在等待某物件」。

有死結，若且唯若等待圖中存在一個環 (cycle)。

由於一筆交易同時只能等一個物件，常把物件省略，直接畫「交易等交易」的簡化圖。

全域等待圖 (global wait-for graph)

在多伺服器系統中，全域等待圖理論上可由各本地等待圖組合而成。關鍵是：

全域等待圖裡可能有一個環，是任何單一本地圖裡都看不到的——這正是分散式死結。

例如：

flowchart LR
  U -->|在 Y 等| V
  V -->|在 Z 等| W
  W -->|在 X 等| U

每台伺服器只看到一條邊（Y 看到 U→V、Z 看到 V→W、X 看到 W→U），單獨看都沒有環，但合起來就是一個完整的環！因此偵測分散式死結需要伺服器之間通訊來拼湊。

生活妙喻

三人傳球的隱形循環

各自只看到一段的循環

想像三個人 U、V、W 圍成一圈，每人手上拿著一顆別人想要的球：

• U 在等 V 手上的球（這件事只有裁判 Y 看到）
• V 在等 W 手上的球（只有裁判 Z 看到）
• W 在等 U 手上的球（只有裁判 X 看到）

每個裁判只看到自己場上的那一段：Y 只知道「U 等 V」，X 只知道「W 等 U」……沒有任何一個裁判看得出這是個死循環。

拼圖才看得見全貌

只有當三個裁判把各自看到的片段湊在一起，才會發現：U→V→W→U 繞了一整圈，大家都在等別人、誰也拿不到球——死結！

這就是分散式死結的精髓：沒有人掌握全貌，必須靠溝通把碎片拼起來。

實用超能力

集中式偵測為何不理想

集中式死結偵測 (centralized deadlock detection)

一個直覺解法：派一台伺服器當全域死結偵測器。各伺服器不時把最新的本地等待圖送給它，由它合併成全域等待圖並檢查有沒有環。找到環就決定中止哪筆交易、通知相關伺服器。

flowchart TD
  X[伺服器 X 本地圖] --> D[全域死結偵測器]
  Y[伺服器 Y 本地圖] --> D
  Z[伺服器 Z 本地圖] --> D
  D --> E[合併成全域圖, 找環]
  E --> F[決定中止哪筆交易並通知]

為什麼不理想？

集中式方案有典型的單點問題：

而且還有取捨：若為省成本而較少收集全域圖，死結就要更久才被發現。

啟示

這解釋了為什麼後面要介紹分散式的偵測法（邊追蹤）——把「找環」這件事分散出去，避免單點瓶頸。下次設計系統，看到「派一台中央伺服器統管」時，記得想想可用性、容錯與擴展性的代價。

深度探秘

被誤判的死結

什麼是幻影死結 (phantom deadlock)

幻影死結：一個「被偵測到」、但其實根本不存在的死結。

在分散式死結偵測中，交易間的等待關係要從一台伺服器傳到另一台才能拼出全域圖。這個過程需要時間，於是有機會發生：在拼圖的途中，某筆持有鎖的交易其實已經釋放了鎖，死結早就不存在了——但偵測器手上的舊資訊仍顯示有環。

一個經典情境

全域偵測器分別收到伺服器 X、Y 的本地圖。假設交易 U 接著釋放了 X 上的物件、轉而請求 V 在 Y 持有的物件；又假設偵測器先收到 Y 的圖、後收到 X 的圖。

結果它會偵測到一個環 $T \rightarrow U \rightarrow V \rightarrow T$，儘管 $T \rightarrow U$ 這條邊早就不存在了。這就是幻影死結——因為各片段是在不同時間點拍下的快照，拼起來才產生了假象。

flowchart LR
  T -->|這條邊其實已消失| U
  U --> V
  V --> T

生活妙喻

用過期照片拼出的假八卦

拼錯時間線的誤會

想像三位朋友各自在不同時間拍了照片，然後湊在一起腦補劇情：

• 早上 9 點的照片：小美在等小華還她的書。
• 但其實10 點時小華就把書還了，這段『等待』早就結束。
• 偵探卻把 9 點的舊照片，和別人 11 點拍的新照片拼在一起，硬是推理出「大家都在互等、僵住了」的死結結論。

問題出在哪？這些照片不是同一時刻拍的。用過期的快照拼湊現況，自然會拼出根本不存在的僵局——這就是幻影死結。

關鍵教訓

在分散式系統裡，沒有統一的「現在」。當你把不同時間、不同地點收集到的狀態硬湊成「全域現況」，就可能得到一個從未真正同時成立的畫面。

實用超能力

兩階段鎖如何排除某些幻影

一個重要的觀察

如果交易使用兩階段鎖 (two-phase locks)，它們不能先釋放物件再取得更多物件（成長期只拿、收縮期只放，不能交錯）。在這個前提下，前述「U 先放掉 X 的鎖、再去要 Y 的鎖」的幻影死結情境根本不會發生。

進一步推論：若偵測到 $T \rightarrow U \rightarrow V \rightarrow T$ 這個環，那麼要嘛這是真死結，要嘛 T、U、V 終究都會提交。但在這個環裡，沒有任何一個能提交（各自都在等一個永遠不會被釋放的物件）——所以它一定是真死結。

那什麼時候還會出現幻影？

若死結環中某個等待中的交易，在偵測過程中中止了，環就已經被打破，於是不再是死結。例如環 $T \rightarrow U \rightarrow V \rightarrow T$ 中，收集到 U 的資訊後 U 才中止，那麼這個被偵測出的環就是幻影。

對你的意義

flowchart TD
  A[偵測到一個環] --> B{有用兩階段鎖嗎}
  B -->|有| C[排除 先放後拿 造成的幻影]
  C --> D{偵測中有交易中止嗎}
  D -->|沒有| E[這是真死結]
  D -->|有| F[可能是幻影, 環已被打破]

設計死結偵測時，要意識到：幻影死結會讓你白白中止無辜的交易。理解它何時可能、何時不可能發生，才能避免過度反應。

深度探秘

邊追蹤的三個步驟

邊追蹤 (edge chasing)

這是一種分散式的死結偵測法，又稱 path pushing。它不建構完整的全域等待圖，而是讓每台伺服器只掌握自己的部分邊，再透過稱為探測 (probe) 的訊息沿著等待圖的邊在系統中傳遞、嘗試找環。探測訊息內含一段「交易等待關係」的路徑。

三個步驟

1. 發起 (Initiation)：當伺服器發現交易 T 開始等待交易 U，而 U 又在另一台伺服器等待物件，它就送出含 $\langle T \rightarrow U \rangle$ 的探測到 U 受阻的物件所在伺服器。
2. 偵測 (Detection)：收到探測 $\langle T \rightarrow U \rangle$ 的伺服器，檢查 U 是否也在等待。若是，把 U 等待的交易（如 V）加進探測成 $\langle T \rightarrow U \rightarrow V \rangle$；若 V 又在別處等待，就轉發探測。在轉發前，伺服器會檢查剛加入的交易是否使探測形成環（如 $\langle T \rightarrow U \rightarrow V \rightarrow T \rangle$），若是就偵測到死結。
3. 解除 (Resolution)：偵測到環時，中止環中一筆交易來打破死結。

flowchart LR
  X[伺服器 X 發起 W→U] --> Y[伺服器 Y 加 V 成 W→U→V]
  Y --> Z[伺服器 Z 加 W 成 W→U→V→W 偵測到環]

訊息成本

偵測到含 $N$ 筆交易的環，會經 $N-1$ 個協調者與 $N-1$ 個物件伺服器轉發，需要 $2(N-1)$ 個訊息。所幸多數死結只涉及兩筆交易，訊息量不必過度擔心。

生活妙喻

接力傳紙條找出欠錢循環

一張愈寫愈長的紙條

想像一群朋友互相欠人情，但沒人知道是否形成了循環。於是發明了傳紙條遊戲：

• 小張發現自己在等小李還人情，就寫張紙條「張→李」，傳給小李那邊（發起）。
• 收到紙條的人檢查：李是不是也在等別人？是的話就把那個人加到紙條尾巴，變成「張→李→王」，再傳下去（偵測與轉發）。
• 某一刻，紙條變成「張→李→王→張」——欸，繞回小張自己了！這就抓到了一個欠人情的死循環（偵測到死結）。

重點直覺

• 沒有人需要掌握全貌，紙條一站一站接力就能把環拼出來。
• 只有正在等待的人才會把紙條往下傳；如果某人此刻沒在等任何人，紙條就停在他那（沒必要送探測）。

這正是邊追蹤的精神：讓資訊沿著等待關係自己走，走回原點就證明有環。

實用超能力

用優先權避免重複中止

問題：同一個環被中止了好幾次

邊追蹤中，環裡每一筆交易都可能各自發起偵測。結果同一個環可能在多個伺服器被偵測到，導致環中不只一筆交易被中止——這是浪費。

解法：交易優先權 (transaction priorities)

給每筆交易一個全序的優先權（例如用時間戳記）。規則：

偵測到環時，中止優先權最低的那筆交易。

這樣即使多個伺服器都偵測到同一個環，它們會一致地選出同一筆來中止。例如假設 $T > U > V > W$（T 優先權最高），則無論偵測到 $\langle T \rightarrow U \rightarrow W \rightarrow V \rightarrow T \rangle$ 還是 $\langle W \rightarrow V \rightarrow T \rightarrow U \rightarrow W \rangle$，被中止的都是 W。

進階：用優先權減少探測，但小心陷阱

優先權還能用來減少探測數：規定只在「高優先權交易開始等低優先權交易」時才發起探測（探測『往下坡』走，從高到低）。這約可減少一半探測訊息。

陷阱：探測能否偵測到死結，可能取決於交易開始等待的順序。若一律用『往下坡』規則，某些情況下該發的探測沒發出，死結就漏掉了。解法是讓協調者把收到的探測存進探測佇列 (probe queue)，當交易開始等待時把佇列中的探測一併往下游轉發，補上漏掉的路徑。

flowchart TD
  A[偵測到環] --> B[比較環中各交易優先權]
  B --> C[中止優先權最低者]
  C --> D[各伺服器一致選出同一筆, 只中止一個]

深度探秘

耐久性與故障原子性

原子性的兩個面向

交易的原子性要求：已提交交易的所有效果都要反映在物件上，而未完成或已中止交易的效果一概不留。這可拆成兩個面向：

• 耐久性 (durability)：物件要存進永久儲存，此後永遠可取得。因此一旦回應客戶端「已提交」，就代表效果已寫入永久儲存。
• 故障原子性 (failure atomicity)：即使伺服器當機，交易的效果仍然是原子的。

回復 (recovery) 就是確保伺服器物件的耐久性與服務的故障原子性。

回復管理員 (recovery manager)

本章假設伺服器執行時把物件放在揮發性記憶體，並把已提交物件記錄到回復檔 (recovery file)。回復管理員的任務是：

• 為已提交交易把物件存進回復檔（永久儲存）；
• 當機後還原伺服器物件；
• 重整回復檔以加速回復；
• 回收回復檔的儲存空間。

有時還要能抵抗媒體故障——此時需要另一份回復檔副本，可用穩定儲存 (stable storage)（鏡像磁碟或異地副本）來達成。

生活妙喻

餐廳的點餐白板與正式帳本

白板 vs 帳本

想像一家餐廳：

• 點餐白板（揮發性記憶體）：服務生忙的時候在白板上塗塗改改，速度快、但一停電就全沒了。
• 正式帳本（回復檔／永久儲存）：每當一桌客人結帳完成，就把這筆正式抄進帳本——這本帳本鎖在保險箱裡，就算停電也還在。

對應關係

耐久性就是「結了帳的一定記在帳本上」；故障原子性就是「即使突然停電，帳目也不會只記一半」。而那位專門負責抄帳、停電後重建營業狀態的店員，就是回復管理員。

實用超能力

意圖清單怎麼用

意圖清單 (intentions list)

交易進行時，更新操作是套用在物件的暫定版本 (tentative version) 上（私有的）。每台伺服器為每筆活躍交易記錄一份意圖清單：

意圖清單包含這筆交易所改動的所有物件的參考與值。

它就像一張「我打算改這些東西」的清單。

提交與中止時的用法

flowchart TD
  A[交易進行中, 改動寫到暫定版本] --> B{交易結束}
  B -->|提交| C[用意圖清單找出受影響物件]
  C --> D[把暫定版本變成正式版本, 寫入回復檔]
  B -->|中止| E[用意圖清單刪掉所有暫定版本]

• 提交時：用意圖清單找出受影響的物件，把每個物件的已提交版本換成該交易做的暫定版本，並把新值寫入回復檔。
• 中止時：用意圖清單刪除該交易做的所有暫定版本。

與兩階段提交的關係

當參與者說它準備好提交 (prepared) 時，它的回復管理員必須已經把該交易的意圖清單與清單中的物件都存進回復檔——這樣即使隨後當機，也能照著清單完成提交。

這就是為什麼 prepared 是個「鄭重承諾」：白紙黑字的意圖清單已經備份好，跑不掉了。

深度探秘

日誌法 (logging)

日誌法

在日誌法 (logging) 中，回復檔是一份日誌 (log)，記錄伺服器執行過的所有交易歷史：物件的值、交易狀態項、交易意圖清單。日誌中項目的順序，反映交易在該伺服器準備、提交、中止的先後。實務上日誌開頭是一份近期快照，後面接著快照之後的交易歷史。

正常運作時

回復管理員在交易準備、提交或中止時被呼叫：

• 準備提交：把意圖清單中的物件附加到日誌，接著寫入該交易的 prepared 狀態與意圖清單。
• 提交或中止：把對應的狀態附加到日誌。

append 操作是原子的（一次寫一或多個完整項目），若伺服器當機只有最後一次寫入可能不完整。

還原與當機後的處理

當機後，任何在日誌中沒有 committed 狀態的交易都會被中止。因此交易提交時，它的 committed 狀態項必須強制寫入 (forced) 日誌。

還原可以「反向讀取日誌」：每個交易狀態項都有指標指向前一個狀態項，回復管理員據此往回走，用 committed 狀態的交易還原尚未還原的物件，直到所有物件都還原。這樣每個物件只還原一次。

還原必須冪等 (idempotent)：做幾次結果都一樣，因為伺服器在還原途中可能再次當機。

flowchart TD
  A[從日誌尾端開始] --> B{此交易 committed 嗎}
  B -->|否| C[忽略其效果]
  B -->|是| D[用意圖清單還原尚未還原的物件]
  D --> E[沿指標往前一個狀態項]
  E --> B

生活妙喻

流水帳日記 vs 一目了然的目錄

兩種記帳風格

日誌法 = 流水帳日記：你每天把發生的事一條一條往後寫，從不塗改舊頁。要查某樣東西的最新狀態，得從最後一頁往前翻，翻到第一次提到它為止。寫的時候超快（只管往後加），但查的時候要翻。

陰影版本 = 一份隨時更新的目錄：你另外維護一張目錄表，寫著「A 的最新版在第幾頁、B 的最新版在第幾頁」。要查最新狀態，看目錄一眼就知道去哪頁拿，超快；但每次更新都得多花工夫去改目錄。

對應關係

這正是兩種技術的取捨：日誌法寫得快、陰影版本還原得快。

實用超能力

陰影版本與檢查點

陰影版本 (shadow versions)

陰影版本用一張地圖 (map) 把物件識別碼對應到它在版本庫 (version store) 中目前版本的位置。

• 交易準備提交時，被改動的物件附加到版本庫，原本的已提交版本保持不變——這些暫定的新版本就是陰影版本 (shadow versions)。
• 交易提交時，複製舊地圖、填入陰影版本的位置成為新地圖，再用單一原子步驟讓新地圖取代舊地圖。
• 地圖必須寫在眾所周知的位置（如版本庫開頭或獨立檔案），且要用穩定儲存，確保即使寫入失敗也有一份有效地圖。

為何陰影版本不夠用於分散式交易？

光靠陰影版本不足以支援分散式交易：交易狀態項與意圖清單要另存在一個交易狀態檔 (transaction status file)（可組織成日誌）。

風險：伺服器可能在「committed 狀態已寫入狀態檔」與「地圖已更新」之間當機。回復管理員必須檢查地圖是否含最後一筆已提交交易的效果；若沒有，就把該交易標記為 aborted。

檢查點 (checkpoint)

檢查點是把伺服器物件的目前已提交值寫到新回復檔的程序（連同尚未完全解決的交易狀態與意圖清單）。目的是減少回復時要處理的交易數並回收空間。回復時若遇到檢查點，就能立刻從中還原所有未決物件。

flowchart LR
  M[地圖] --> V1[版本庫: A 的位置]
  M --> V2[版本庫: B 的位置]
  T[交易提交] --> NM[複製並更新地圖, 原子替換]

深度探秘

done 與 uncertain 兩種新狀態

為兩階段提交新增的狀態

分散式交易中每台伺服器都有自己的回復檔。為了處理「當機時正在跑兩階段提交」的交易，回復管理員多用兩個狀態值：

• done：協調者用來表示整個兩階段提交協定已完成（committed 則表示投票結果是 Yes）。
• uncertain：參與者用來表示它已投 Yes、但還不知道結果。

還新增兩種項目：協調者項 (Coordinator) 記錄參與者清單；參與者項 (Participant) 記錄它的協調者。

各階段寫了什麼

Phase 1：

• 協調者準備提交（已加 prepared 狀態）後，回復管理員加一個協調者項。
• 參與者投 Yes 前必先 prepared；投 Yes 時記錄參與者項並把 uncertain 狀態以強制寫入加進回復檔。投 No 則加 abort 狀態。

Phase 2：

• 協調者依決定強制寫入 committed 或 aborted 狀態。
• 參與者依協調者訊息加 commit 或 abort 狀態。
• 協調者收到所有參與者確認後，加 done 狀態（不需強制寫入）。done 不屬於協定本身，是供回復檔重整時使用。

flowchart TD
  A[協調者: prepared] --> B[協調者項 參與者清單]
  B --> C[committed 強制寫入]
  C --> D[done 供重整用]
  E[參與者: prepared] --> F[參與者項 + uncertain 強制寫入]
  F --> G[committed 或 aborted]

生活妙喻

婚禮總召與廠商的記事本

各自的記事本

回到婚禮比喻，當天總召（協調者）和每個廠商（參與者）都各自帶著一本防火記事本（回復檔），把關鍵進度記下來，萬一臨時換人（當機被替換）也能接手。

• 廠商把花裝上車、回報「我準備好了」後，會在記事本寫下「我已答應、但還沒收到開不開動的命令」——這就是 uncertain。萬一這時換了個新員工來，他翻記事本就知道：得趕快問總召「到底要不要送？」
• 總召收齊所有廠商的確認、整場都收尾後，會在記事本蓋一個「全部搞定」的章——這就是 done。這個章不是給當天用的，而是事後整理檔案時，知道哪些紀錄可以丟掉。

為什麼 uncertain 要『強制寫入』？

因為這是最關鍵、最危險的時刻：廠商已經承諾卻不知結果。這條紀錄必須立刻、確實寫進防火記事本，不能只是先記在便條紙上——萬一這瞬間出事，接手的人才不會搞錯狀態。

實用超能力

當機後依角色與狀態採取行動

回復動作取決於「角色 × 當機時狀態」

當機後，回復管理員看最靠近日誌尾端的交易狀態項判斷當機時的狀態，再依角色行動：

重整回復檔的注意事項

• 沒有 done 狀態的協調者項不可移除——要保留到所有參與者都確認完成。
• done 狀態的項目可以丟棄。
• uncertain 狀態的參與者項也必須保留。

flowchart TD
  A[當機後看日誌尾端狀態] --> B{我是協調者還是參與者}
  B -->|協調者 committed| C[對參與者 doCommit]
  B -->|參與者 uncertain| D[getDecision 問協調者]
  B -->|協調者 done| E[無需動作]

對你的意義

這張表就是分散式交易『災後重建手冊』。理解它你會發現：uncertain 的參與者最被動（只能問協調者），而 done 最輕鬆（什麼都不用做）——因為一切早已塵埃落定。