STEP 1

深度探秘

當兩個人同時改同一個數字

問題的根源：交錯執行

伺服器通常用多執行緒 (threads) 來同時服務很多客戶端，這對效能很好——但也埋下危機。如果兩個客戶端同時對同一個帳戶呼叫 deposit（存款），而這個方法沒有被妥善保護，兩個執行緒的動作就可能任意交錯 (interleaved)。

想想看 deposit 內部其實是三步：

1. 讀出目前餘額
2. 把餘額加上存款金額
3. 寫回新餘額

如果兩個執行緒都先做了第 1 步（都讀到舊餘額 $100），再各自加錢寫回，後寫的那個會蓋掉前一個的結果。明明存了兩次，餘額卻只增加一次。

原子操作 (atomic operation)

不會被其他執行緒的並行操作干擾的操作，稱為原子操作。

在 Java 裡，可以把方法標記成 synchronized：一個執行緒進入某物件的 synchronized 方法時，這個物件就被「鎖住」，其他執行緒想呼叫它的 synchronized 方法就得等待，直到鎖被釋放。這樣就強迫執行緒一個一個來，物件的內部變數就不會被改亂。

flowchart TD
  A[執行緒一 呼叫 deposit] --> B[取得物件鎖]
  B --> C[讀餘額 加錢 寫回]
  C --> D[釋放鎖]
  E[執行緒二 呼叫 deposit] --> F[想取得鎖 但被佔用]
  F --> G[等待]
  D --> G
  G --> H[取得鎖 接著做]

STEP 2

生活妙喻

共用一本記帳本

一本只有一支筆的記帳本

想像辦公室有一本共用的零用金記帳本，但只有一支筆。

• 沒有規矩時：小明和小華同時想記帳。兩人都先看到本子上寫「餘額 100」，小明心算「加 50 變 150」，小華心算「加 30 變 130」。可是他們各寫各的，最後本子上只剩其中一個數字——另一筆完全消失了。這就是遺失更新的雛形。

• 有規矩時：規定「拿到筆的人才能寫，寫完才把筆交出去」。小明拿筆時，小華只能在旁邊等；小明寫完「150」放下筆，小華才拿筆，看到的是最新的 150，再加成 180。兩筆都算進去了。

那支筆就是 synchronized 帶來的鎖；「拿到筆才能寫」就是原子操作。

還需要互相溝通：wait 與 notify

有時光是排隊還不夠。例如一個共享佇列，客戶端 A 想拿出第一個東西，但佇列是空的——它不該被告知「等等再試」（這樣它得一直來問，很沒效率又不公平），而是應該掛起來等，直到客戶端 B 放了東西進來再叫醒它。

這就像點餐：客人點了一道還沒備料的菜，店家不是叫客人「等下再來點一次」，而是讓客人坐著等，料一到就出菜。Java 的 wait（我先睡，把筆讓出去）和 notify（我放東西進來了，叫醒等的人）就是做這件事。

STEP 3

實用超能力

設計一個不會出錯的共享物件

動手設計：可安全並行的 Account

當你在寫一個會被多個客戶端同時呼叫的伺服器物件時，記住這個原則：

任何會讀寫「可變動的實例變數」的方法，都應該設成原子操作。

以銀行帳戶為例：

public class AccountImpl implements Account {
  private int balance = 0;

  // 加上 synchronized，確保一次只有一個執行緒能改 balance
  public synchronized void deposit(int amount) {
    balance = balance + amount;
  }

  public synchronized void withdraw(int amount) {
    balance = balance - amount;
  }

  public synchronized int getBalance() {
    return balance;
  }
}

用 wait/notify 做一個阻塞佇列

當「消費者要等生產者」時：

public synchronized Object first() {
  while (isEmpty()) {
    wait();          // 佇列空就放掉鎖、掛起自己
  }
  return removeFirst();
}

public synchronized void append(Object o) {
  addLast(o);
  notify();          // 放了東西，叫醒等待者
}

注意兩個重點：

• wait 與 notify 必須在 synchronized 方法裡用。
• 用 while 而不是 if 檢查條件——因為被叫醒後，條件可能又被別人改掉了，得再確認一次。

這套機制就是後面章節「鎖」的基礎：當客戶端搶不到鎖時，就讓它 wait，等別人釋放鎖時再 notify 叫醒它。

STEP 1

深度探秘

把一串操作綁成一個不可分割的步驟

什麼是交易 (transaction)

光是把單一方法原子化還不夠。客戶端常常需要做一連串操作，並且希望這一整串：

1. 不被其他客戶端的並行操作干擾。
2. 要嘛全部成功，要嘛在當機時完全沒有效果。

這種「一連串操作被當成一個不可分割單位」的東西，就是交易。

經典例子是轉帳：從 A 轉 100 元到 B，其實是 a.withdraw(100) 加上 b.deposit(100) 兩步。如果只做了扣款卻沒入帳（中間當機），錢就憑空消失了。交易保證這兩步「全有或全無」。

原子性的兩個面向

交易作用在可復原物件 (recoverable objects) 上，並保證原子性，這包含：

• 全有或全無 (all or nothing)：成功就全部生效，失敗或中止就完全沒效果。它又分成：
  • 失敗原子性 (failure atomicity)：就算伺服器當機，效果仍是原子的。
  • 持久性 (durability)：成功後所有效果都存進永久儲存，行程當掉也還在。
• 隔離性 (isolation)：每筆交易不受其他交易干擾，中間的暫態不會被別人看到。

flowchart TD
  A[交易開始] --> B[執行一連串操作]
  B --> C{順利完成?}
  C -->|是| D[commit 全部效果生效並存入永久儲存]
  C -->|否| E[abort 所有效果完全消除]

STEP 2

生活妙喻

ATM 轉帳與婚禮誓詞

轉帳像「兩人同時點頭」的承諾

想像你在 ATM 把 100 元從活存轉到定存。系統得先從活存扣 100、再往定存加 100。如果機器在扣完款的瞬間斷電——你絕對不希望錢就這樣蒸發。

交易的保證就像婚禮誓詞：「我願意」必須兩個人都說了才算數，只有一方說了不算結婚。交易也是——所有步驟都成功才 commit（正式生效），否則 abort（當作什麼都沒發生）。

ACID：四個字記住交易的承諾

字母	性質	白話解釋
A	Atomicity 原子性	全有或全無，不會做一半
C	Consistency 一致性	從一個正確狀態變到另一個正確狀態
I	Isolation 隔離性	別人看不到你做到一半的暫態
D	Durability 持久性	成功後就算當機也救得回來

有趣的是，書中說 C（一致性）通常是程式設計師的責任——例如若有個欄位記錄「所有帳戶餘額總和」，那麼每次 deposit、withdraw 都要記得同步更新它，這樣用 branchTotal 和逐一加總才會得到相同結果。系統本身主要負責 A、I、D。

STEP 3

實用超能力

什麼時候你會需要交易

辨認「需要交易」的情境

只要你的操作符合以下任一特徵，就該考慮包成交易：

• 跨多筆資料的相依更新：轉帳、訂票（扣庫存 + 建訂單 + 收款）、下單（建單 + 扣點數 + 發通知）。
• 不能被別人看到半成品：報表查詢時，不該看到轉帳只做了扣款那一半。
• 失敗要能完整回復：流程中斷時要能乾淨地復原，而不是留下髒資料。

交易長什麼樣

從客戶端角度，一筆交易就是一段「開始—操作—結束」：

Transaction T:
  a.withdraw(100);   // 從 A 扣 100
  b.deposit(100);    // 存進 B
  c.withdraw(200);   // 從 C 扣 200
  b.deposit(200);    // 存進 B

從客戶端看，這整段是單一步驟，把伺服器資料從一個一致狀態轉換到另一個一致狀態。

為什麼不直接「一筆一筆排隊做」就好？

最簡單的隔離方式是讓所有交易完全序列執行（一次一筆）。但這對多人共用的伺服器太慢了——銀行不可能規定全分行只能有一個行員同時作業。所以目標是最大化並行：只要並行的效果跟某種序列執行相同（也就是後面要學的「序列等價」），就允許它們同時跑。

STEP 1

深度探秘

協調者與三個關鍵動作

協調者 (coordinator)

每一筆交易都由一個協調者建立與管理。協調者提供三個操作給客戶端：

• openTransaction()：開始一筆新交易，回傳一個唯一的交易識別碼 (TID)。
• closeTransaction(trans)：表示交易結束，回傳結果是 commit（已提交）或 abort（已中止）。
• abortTransaction(trans)：客戶端主動中止交易，所有效果都要被移除。

客戶端拿到 TID 後，會把它附在交易內的每一個操作上，讓伺服器知道這些操作屬於同一筆交易。當交易作為中介軟體（如 CORBA Object Transaction Service）提供時，TID 可以隱式地自動帶上，不必手動傳。

三種結局

flowchart TD
  A[openTransaction] --> B[一連串 operation]
  B --> C{結局}
  C -->|順利| D[closeTransaction 回傳 commit]
  C -->|客戶端主動| E[abortTransaction 客戶端中止]
  C -->|伺服器決定| F[server aborts 回報錯誤給客戶端]

• 成功：客戶端 closeTransaction，得到 commit，承諾所有變更已永久記錄。
• 客戶端中止：客戶端呼叫 abortTransaction。
• 伺服器中止：因衝突或當機等原因，伺服器自己中止它。

後兩種都稱為交易失敗 (failing)。

STEP 2

生活妙喻

餐廳訂位與點餐單號

一張帶號碼的點餐單

把協調者想成餐廳的點餐系統：

• 你入座開始點餐 → openTransaction，系統給你一個桌號／單號 (TID)。
• 接下來你點的每一道菜，都會寫上這個單號（操作帶 TID），廚房才知道哪些菜是同一桌的。
• 你說「就這些，結帳」→ closeTransaction，廚房確認全部備齊、出餐、收款（commit）。
• 你中途說「不點了，全部取消」→ abortTransaction（客戶端中止）。
• 廚房發現某材料用完、無法上整桌的菜 → 由餐廳這邊取消（伺服器中止）。

當機怎麼辦：回到最後一次「結清」的狀態

如果廚房（伺服器）突然停電重開機，它會：

• 把所有還沒結清（未 commit）的單子作廢。
• 用紀錄把帳目還原到最近一次成功結清的狀態。

至於客戶端中途落跑（client 當掉），伺服器會給每筆交易一個到期時間 (expiry time)，超時還沒結束就自動中止——就像佔著桌位太久沒點餐會被請離。

STEP 3

實用超能力

客戶端如何面對交易失敗

客戶端要會處理「交易不見了」

在真實系統中，交易並不保證一定成功，客戶端必須準備好應對：

1. 伺服器中途當機：客戶端會在某個操作逾時後收到例外 (exception)。如果伺服器當機後被新行程取代，原本的交易就不再有效，客戶端必須在下一個操作收到例外時知道這件事。

2. 收到例外後要有計畫：客戶端（必要時和真人使用者商量）要決定是重做整筆交易，還是放棄這項任務。

一個健壯的客戶端骨架

int attempts = 0;
while (attempts < MAX_RETRY) {
  trans = openTransaction();
  try {
    a.withdraw(trans, 100);
    b.deposit(trans, 100);
    result = closeTransaction(trans);  // 回傳 commit 或 abort
    if (result == COMMIT) break;       // 成功，結束
  } catch (Exception e) {
    // 伺服器當機或交易失效：記錄、稍後重試
  }
  attempts++;
}

設計重點

• 不要假設交易一定成功：每個 close 都要檢查回傳的是 commit 還是 abort。
• 逾時與重試要有上限：避免無限重試。
• 伺服器端也要保護自己：用到期時間中止那些「客戶端掛了、一直不結束」的交易，避免它們長期佔住資源。

STEP 1

深度探秘

兩個並行交易交錯時的災難

遺失更新問題 (lost update)

設帳戶 A=100、B=200、C=300。交易 T 把 B 加 10%（從 A 轉），交易 U 也把 B 加 10%（從 C 轉）。正確答案應該是 B 被加兩次 10%，最後 $242。

但若兩交易交錯成這樣：

步驟	T	U	B 的值
1	balance = b.getBalance()		讀到 200
2		balance = b.getBalance()	也讀到 200
3	b.setBalance(220)		220
4		b.setBalance(220)	220

結果 B 只變成 220（加了 20），不是 242（加了 42）。U 的更新被 T 蓋掉而消失——因為兩者都在對方寫入前讀到了舊值。這就是遺失更新。

不一致擷取問題 (inconsistent retrievals)

A、B 都初始 $200。交易 V 從 A 轉 100 到 B；交易 W 用 branchTotal 加總所有帳戶。若交錯成：

flowchart TD
  A[V 執行 a.withdraw 100  A 變成 100] --> B[W 開始加總 讀 A 得到 100]
  B --> C[W 讀 B 得到 200 此時還沒入帳]
  C --> D[W 算出 A 加 B 等於 300 錯誤]
  D --> E[V 才執行 b.deposit 100  B 變成 300]

W 算出的總和把 A+B 當成 300（正確應是 400），因為它在 V「只轉了一半」（扣了款還沒入帳）時就去加總。這就是不一致擷取。

STEP 2

生活妙喻

共筆文件與盤點到一半

遺失更新：兩人同時編輯同一行

想像你和同事都打開同一份「未即時同步」的文件，各自看到「庫存：100」。你改成 150 存檔，同事也改成 130 存檔。誰後存，誰的版本就贏，另一個人的修改就這樣不見了。明明兩個人都做了修改，卻只有一筆生效——這就是遺失更新。

不一致擷取：搬東西搬到一半時去盤點

想像倉庫正在把 100 箱貨從 A 區搬到 B 區。搬運工已經從 A 區搬走了（A 區少了 100），但還在路上、還沒放進 B 區。

這時候老闆突然要盤點總庫存：他數 A 區（已少 100）、再數 B 區（還沒多 100），加起來發現少了 100 箱！其實貨根本沒少，只是正卡在「搬運途中」這個中間狀態。

老闆讀到的是一個不該被外人看到的暫態。這正是隔離性要防止的事——別讓人在轉帳做一半時去看總額。

STEP 3

實用超能力

辨認並避開這兩種陷阱

如何辨認你正面臨哪種問題

問題	涉及的操作	症狀
遺失更新	兩個交易都「讀後寫」同一物件	有人的更新憑空消失
不一致擷取	一個查詢交易撞上一個更新交易	查詢讀到改到一半的暫態

共通點：都是因為缺乏並行控制，讓交易看到了彼此的中間狀態。

解法的方向

這兩個問題都能用一個原則治本：讓並行的執行效果，等同於某種「一筆接一筆」的序列執行（也就是下一節的序列等價）。

• 若遺失更新中 T 完全做完 B 的操作 U 才開始，U 就會讀到 T 寫的新值，不會覆蓋掉。
• 若不一致擷取中 W 在 V 完成「之前」或「之後」才加總，就不會看到半成品。

寫程式時的具體警訊

當你看到這種「先讀出來、算一算、再寫回去」的模式（read-modify-write）被多個並行者執行時，就要警覺遺失更新。例如：

balance = account.getBalance();   // 讀
balance = balance * 1.1;          // 算
account.setBalance(balance);      // 寫回

這段若沒有交易與並行控制保護，兩個人同時跑就會丟更新。下一節會看到「序列等價」如何當作正確性的判準來根治它。

STEP 1

深度探秘

什麼樣的交錯算「正確」

序列等價 (serial equivalence)

如果每筆交易單獨執行時都是正確的，那麼把它們一筆接一筆（某種順序）執行，合起來的效果也會正確。

一種交易操作的交錯，若其合併效果與「把這些交易一筆接一筆依某順序執行」相同，就稱為序列等價的交錯 (serially equivalent interleaving)。

以序列等價當作「並行執行正確」的判準，就能同時避免遺失更新與不一致擷取——因為序列執行裡，後者一定讀到前者寫好的值，查詢也不會撞上半成品。

操作衝突 (operation conflicts)

要判斷一個交錯是否序列等價，得先看哪些操作會衝突。把操作簡化成 read 與 write：

操作 A	操作 B	衝突？	原因
read	read	否	兩個讀的效果與順序無關
read	write	是	讀和寫的效果取決於誰先
write	write	是	兩個寫的效果取決於誰先

兩操作衝突，意思是它們的合併效果取決於執行順序。

序列等價的精確條件

兩筆交易要序列等價，充分必要條件是：它們在所有共同存取的物件上，所有成對的衝突操作都以相同的順序執行。

flowchart TD
  A[找出兩交易共同存取的物件] --> B[列出所有成對的衝突操作]
  B --> C{每對衝突在各物件上順序一致?}
  C -->|是| D[序列等價 正確]
  C -->|否| E[非序列等價 可能出錯]

STEP 2

生活妙喻

兩個廚師、兩個鍋子

read-read 不衝突：兩人同時看食譜

兩個廚師同時「讀」同一張食譜，誰先看誰後看都沒差，食譜不會因此改變——這就是 read-read 不衝突。

而只要其中一人要在食譜上「改」字（write），順序就重要了：你是看了原版才改，還是看了改過的版本，結果完全不同。這就是 read-write 與 write-write 會衝突。

序列等價：兩個鍋子要「一致地讓位」

假設廚師 T 和 U 都要用 B 鍋和某個別的鍋。序列等價要求：

如果在 B 鍋上是「T 先用、U 後用」，那麼在所有兩人共用的鍋子上，都必須是「T 先、U 後」。

不能在 B 鍋讓 T 先，卻在另一個鍋讓 U 先——那樣順序自相矛盾，等於沒有一個一致的「誰先誰後」，就不是序列等價。

書中的反例：T 對物件 i 全部先做、U 對物件 j 全部先做。雖然各自看起來有序，但「i 上 T 先、j 上 U 先」順序相反，所以不是序列等價。正確的序列等價要嘛「兩個物件都 T 先」，要嘛「兩個物件都 U 先」。

STEP 3

實用超能力

用衝突規則檢查一個交錯

實戰：判斷一個交錯是否序列等價

看這兩筆交易（i、j 是兩個物件）：

T: x = read(i); write(i,10); write(j,20);
U: y = read(j); write(j,30); z = read(i);

某個交錯實際執行順序為：

x = read(i)      (T)
write(i,10)      (T)
y = read(j)      (U)
write(j,30)      (U)
write(j,20)      (T)
z = read(i)      (U)

檢查步驟：

1. 在物件 i 上：T 的 read(i)、write(i,10) 都在 U 的 read(i) 之前 → 在 i 上是「T 先於 U」。
2. 在物件 j 上：U 的 read(j)、write(j,30) 都在 T 的 write(j,20) 之前 → 在 j 上是「U 先於 T」。
3. 兩個物件上的順序相反！所以這個交錯不是序列等價。

帶走的判定流程

序列等價的兩個合法可能：(1) 兩物件上都 T 先於 U；或 (2) 兩物件上都 U 先於 T。只要出現「一個物件 T 先、另一個 U 先」就破功。

這正是後面三大並行控制協定的共同目標——它們都在想辦法把交易對物件的存取序列化，讓所有衝突操作順序一致：鎖用「到達順序」、時戳用「開始時間」、樂觀法用「提交前驗證」。

STEP 1

深度探秘

中止帶來的三個新麻煩

為什麼序列等價還不夠

上一章保證了交易「序列等價」就不會遺失更新或不一致擷取。但別忘了交易可能中止 (abort)——這又帶來新問題。即使在序列等價的執行下，這些問題仍會發生。

髒讀 (dirty read)

隔離性要求交易不該看到別人未提交的狀態。考慮：T 把 A 餘額加 10，U 接著讀到這個新值、再加 20 並提交。然後 T 中止了——A 被還原成原值。但 U 已經根據一個「從未真正存在的值」提交了，且無法回頭。我們說 U 做了髒讀。

連鎖中止 (cascading aborts)

為了可復原，U 應該延遲提交，直到它觀察過的交易（T）都提交為止；若 T 中止，U 也得中止。但若還有其他交易讀過 U 寫的值，它們也得跟著中止……一路連鎖下去，這叫連鎖中止。

避免連鎖中止的辦法：交易只能讀已提交交易寫的值。

過早寫入 (premature writes)

這牽涉兩個交易對同物件的 write。許多系統用「前像 (before image)」來實作中止（中止時還原成寫之前的值）。但若 T、U 接連寫同一物件，前像就可能對應錯，導致中止後得到錯誤的值。

flowchart TD
  A[T 寫 A 但尚未提交] --> B[U 讀或寫 A]
  B --> C{T 之後中止?}
  C -->|是| D[U 基於不存在的值 出錯]
  C -->|否| E[沒事]

STEP 2

生活妙喻

鉛筆草稿與骨牌

髒讀：照抄別人還沒確定的草稿

同事在白板上用鉛筆寫了「預算 = 110」（還沒確定），你看到後就拿去做了你的報表並交了出去。結果同事說「啊那只是草稿」把它擦掉改回 100。你的報表已經送出去、收不回了——你引用了一個從未正式存在的數字。這就是髒讀。

連鎖中止：推倒的骨牌

如果你的報表又被別人引用、那個人的東西又被下一個人引用……一旦最初的草稿被擦掉，所有引用過它的人都得作廢重做。一張牌倒下，整排骨牌跟著倒——這就是連鎖中止。

防骨牌的規矩：只准引用「已經正式拍板（提交）」的數字，不准抄草稿。這樣最初那張牌就算倒了，也沒人靠在它身上。

嚴格執行：等對方拍板再動

要同時防髒讀和過早寫入，最乾脆的規矩是：

對某物件的讀或寫，都延遲到所有先前寫過它的交易都已提交或中止為止。

這就像「你想用這份文件？等正在改它的人按下『完成』或『取消』，你再動」。這種執行方式叫嚴格執行 (strict execution)，它確保了隔離性。

STEP 3

實用超能力

嚴格執行與暫存版本

兩個讓中止安全的關鍵機制

1. 嚴格執行 (strict execution)

規則：讀和寫都延遲，直到所有先前寫過同物件的交易都已 commit 或 abort。

• 防髒讀：你不會讀到還沒提交的值（要嘛已提交、要嘛已撤銷）。
• 防過早寫入：你不會覆蓋一個還沒定案、之後可能被還原的值。

這正是後面「嚴格兩階段鎖」的理論基礎——把鎖一直握到交易結束。

2. 暫存版本 (tentative versions)

要讓中止能乾淨地撤銷，所有更新都先做在暫存版本上（放在揮發性記憶體中，每筆交易有自己私有的一份）：

• 交易的所有寫入都存到自己的私有暫存版本。
• 讀取優先從自己的暫存版本取，沒有才去讀真正物件。
• 提交時：才把暫存版本一次套用到真正物件（並寫入永久儲存），這一步要排除其他交易存取。
• 中止時：直接丟掉暫存版本，真正物件毫髮無傷。

// 概念示意
交易 T 的私有暫存區: { A: 110 }   // 還沒套用
真正物件:            { A: 100 }   // 維持原值
// 若 T commit → 真正物件變 110
// 若 T abort  → 丟掉暫存區，真正物件仍是 100

帶走的設計準則

想讓「可以反悔」的交易不傷到別人：先寫在暫存版本（反悔零成本），並用嚴格執行讓大家都等先前的寫者定案後才動。

STEP 1

深度探秘

交易裡再開交易

什麼是巢狀交易 (nested transaction)

巢狀交易擴充了原本的交易模型，允許一筆交易由其他交易組成。這樣交易就像可以組裝的模組。

• 最外層的交易叫頂層交易 (top-level transaction)。
• 其他都叫子交易 (subtransaction)。

例如 T 開出子交易 T1、T2；T1 又開出 T11、T12；T2 開出 T21，T21 再開 T211，形成一棵樹。

子交易對它的父交易而言是原子的（就失敗與並行存取而言）。同層的子交易（如 T1、T2）可並行執行，但對共同物件的存取會被序列化。

為什麼要巢狀（相對於「平坦交易 flat transaction」）

平坦交易所有工作都在同一層，無法只提交或中止其中一部分。巢狀交易有兩大優點：

1. 更多並行：同層子交易可並行，跑在不同伺服器上時甚至能平行運算。例如 branchTotal 對每個帳戶呼叫 getBalance，每個都當作子交易就能並行（彼此不衝突）。
2. 可獨立提交或中止：更健壯。例如「寄信給一串收件人」可拆成多個子交易，某些失敗時父交易仍可記錄並提交成功的那些，之後再重試失敗的。

flowchart TD
  T[T 頂層交易] --> T1[T1 子交易]
  T --> T2[T2 子交易]
  T1 --> T11[T11]
  T1 --> T12[T12]
  T2 --> T21[T21]
  T21 --> T211[T211]

STEP 2

生活妙喻

公司專案的層層分工

一個大專案，分包給好幾個小組

把頂層交易想成一個大專案，子交易是分派出去的子任務：

• 大專案（頂層 T）拆成「設計」「開發」兩個子任務（T1、T2）。
• 「開發」又拆成「前端」「後端」（T21、T211）。
• 不同子任務可以同時進行（同層並行）；如果在不同部門做，等於平行作業。

「暫時拍板」與「最終定案」

關鍵規則是子交易的提交只是暫時提交 (provisional commit)：

• 子任務做完，自己決定「暫時拍板」或「放棄」——但放棄是最終的，拍板只是暫時的。
• 子任務的成果在整個大專案（頂層）正式拍板前都不算數。
• 父任務取消，底下所有子任務（即使已暫時拍板）也一律作廢。
• 某子任務放棄時，父任務可以自己決定要不要跟著取消——例如寄信例子裡，少數收件人失敗，父交易仍可選擇提交成功的部分。

就像專案經理說：「就算前端組做完了，要等我（整個專案）簽字，你們的成果才正式生效；萬一整個專案喊停，已經做的也都不算。」

STEP 3

實用超能力

巢狀交易的提交規則

提交規則（有點微妙，但很關鍵）

1. 交易必須在它的子交易都完成後才能提交或中止。
2. 子交易完成時，獨立決定暫時提交或中止；中止的決定是最終的。
3. 父交易中止時，它所有子交易都中止——即使那些子交易已暫時提交。例如 T2 中止，T21、T211 也得中止。
4. 子交易中止時，父交易可自行決定要不要中止。例如 T 仍選擇提交，即使 T2 已中止。
5. 頂層交易提交時，所有暫時提交且祖先都沒中止的子交易才能真正提交。例如 T 提交讓 T1、T11、T12 提交，但 T21、T211 不行（因為父 T2 中止了）。

重點：子交易的效果在頂層交易提交前都不是永久的。

實例：轉帳拆成子交易

Transfer 從 B 轉 100 到 A:
  subtx1: a.deposit(100)
  subtx2: b.withdraw(100)   // 若 B 透支則中止

• 若 withdraw 子交易因透支而中止，但 deposit 已暫時提交——
• 頂層 Transfer 多半會決定中止：父交易一中止，deposit 子交易也被撤銷，所有效果歸零。

為什麼在分散式系統特別有用

子交易可在不同伺服器並行執行——這是巢狀交易在分散式環境的最大價值（第 17 章會深入）。當一筆任務天然能拆成「對不同資源、彼此獨立」的子工作時，巢狀結構讓你又快又健壯。

STEP 1

深度探秘

用鎖把存取序列化

鎖如何達成序列等價

最簡單的序列化機制是互斥鎖 (exclusive lock)：伺服器在某物件即將被交易使用前鎖住它；若該物件已被別的交易鎖住，後來者就等待直到解鎖。鎖把對該物件的存取序列化了。

兩階段鎖 (two-phase locking)

要保證序列等價，所有衝突操作必須以相同順序執行。為此規定：

交易一旦釋放任何一個鎖，就不能再取得新鎖。

於是每筆交易分成：

• 成長期 (growing phase)：只取得新鎖。
• 收縮期 (shrinking phase)：只釋放鎖。

嚴格兩階段鎖 (strict two-phase locking)

因為交易可能中止（會有髒讀、過早寫入），需要嚴格執行。做法是：所有鎖都握到交易提交或中止為止。提交時為了可復原，鎖還要握到所有更新都寫入永久儲存。

讀寫鎖：多讀單寫

單一互斥鎖太嚴——read-read 其實不衝突。所以改用兩種鎖（多讀單寫 many readers/single writer）：

已設的鎖	請求 read	請求 write
無	OK	OK
read（共享）	OK	wait
write	wait	wait

讀鎖可被多個交易共享（又稱共享鎖），寫鎖則互斥。

flowchart TD
  A[交易要存取物件] --> B{物件已被鎖?}
  B -->|沒鎖| C[上鎖 操作進行]
  B -->|有衝突鎖| D[等待 直到解鎖]
  B -->|有非衝突的讀鎖| E[共享該鎖 操作進行]
  C --> F[交易結束 commit或abort 才解鎖]
  E --> F

STEP 2

生活妙喻

會議室與圖書館借書

互斥鎖：一次一組人的會議室

互斥鎖像會議室——一組人進去就反鎖，其他人只能在門外等到他們出來。這保證裡面的討論不被打斷（存取序列化）。

兩階段鎖：先借齊、再一起還

「成長期只借、收縮期只還，且一旦開始還就不能再借」這條規矩，可以想成：

你出門辦事，該借的工具一開始全借齊；一旦開始歸還任何一樣，就代表你進入收尾，不准再回頭借新東西。

為什麼？如果你還了 A 工具、別人拿走改了它，你又回頭借 B——你看到的世界就可能前後不一致，破壞序列等價。

讀寫鎖：圖書館的閱覽 vs 修訂

讀寫鎖像圖書館的一本書：

• 很多人可以同時『閱讀』（共享讀鎖）——大家看的是同一份內容，不衝突。
• 但要『修訂』這本書時必須獨佔（寫鎖）——修訂期間別人不能讀也不能改，否則會讀到改到一半的內容。

所以是「多讀單寫」：讀的人可以一起來，寫的人必須一個人關起門來改。

STEP 3

實用超能力

鎖升級、粒度與實作

鎖升級 (lock promotion)

防遺失更新的技巧：交易讀物件時先設讀鎖，要寫同物件時再升級成寫鎖。

鎖只能升級（變更獨佔）不能降級（變更寬鬆）。降級會讓別人在交易還沒結束時插入不符序列等價的操作。

注意：若讀鎖正被多個交易共享，持有者無法直接升級成寫鎖（會跟別人的讀鎖衝突），只能請求寫鎖並等其他讀鎖釋放。

粒度 (granularity) 很重要

鎖的粒度該盡量小——只鎖每個操作真正用到的部分。

反例：若銀行把鎖加在「整個分行的所有帳戶」上，那同一時間只有一個行員能作業，完全不可接受。

所以 deposit/withdraw 只鎖一個帳戶餘額，branchTotal 才需要鎖全部。

鎖的實作骨架

鎖由 LockManager 管理（用雜湊表存所有 Lock）。每個 Lock 記錄：被鎖物件、目前持有者的 TID（共享鎖可多個）、鎖的型別。

acquire(trans, lockType):
  while (另一交易以衝突模式持有此鎖) wait();
  if (沒人持有) 加入持有者, 設型別
  else if (別人持有且可共享) 把自己加入持有者
  else if (自己已持有但需更獨佔) promote() 升級

release(trans):
  從持有者移除 trans
  設型別為 none
  notifyAll()   // 叫醒所有等待者，因共享讀鎖可能多人能繼續

用 while 包 wait、釋放時 notifyAll：因為被叫醒的人不一定都能繼續，得各自再檢查條件。

STEP 1

深度探秘

鎖帶來的副作用

死結 (deadlock) 是什麼

用鎖可能造成死結。經典場景：

• 交易 T 先鎖住 A，再想鎖 B。
• 交易 U 先鎖住 B，再想鎖 A。
• 結果：T 等 U 放 B，U 等 T 放 A——兩者互相等待，誰都動不了。

死結是一群交易中，每個成員都在等另一個成員釋放鎖的狀態。

等待圖 (wait-for graph)

用一張圖來表示等待關係：節點是交易，邊代表「等待」——從 T 到 U 的邊表示「T 在等 U 釋放鎖」。

上面的例子裡，T→U 且 U→T，形成一個循環 (cycle)。

等待圖中有循環，就代表死結。

flowchart LR
  T[交易 T] -->|等待| U[交易 U]
  U -->|等待| T

更複雜時（如 T 等 U 與 V、V 等 W、W 等 T 等等），一個交易可能同時牽涉在多個循環裡。要打破死結，只要中止循環中的一個交易、釋放它的鎖，循環就斷了。

為什麼互動式程式特別容易死結

互動程式裡的交易可能持續很久（使用者慢慢操作），導致很多物件被鎖住又遲遲不放，更容易卡住其他客戶端。

STEP 2

生活妙喻

兩台車的窄巷對峙

窄巷裡頭對頭的兩台車

想像一條只能單向通過的窄巷，兩台車從兩端開進來，在中間頭對頭卡住：

• A 車要往前，得等 B 車先退。
• B 車要往前，也得等 A 車先退。
• 兩個都不退，永遠卡在那裡。

這就是死結。等待圖就是把「A 等 B、B 等 A」畫成一個圈。要解決，只能請其中一台車倒退離開（中止一個交易）——這樣另一台就能通過了。

為什麼會形成圈

死結的本質是「環狀的相互依賴」：每個人手上握著別人想要的東西，又在等別人手上的東西。只要這個「想要」的箭頭連成一圈，就解不開。

久候不一定是死結

注意：等很久 ≠ 一定死結。也許對方只是還在忙、待會就會放手。真正的死結是「形成了封閉的循環，誰都不可能先放」。這個區別很重要——後面會看到用「逾時」來猜死結時，常會誤殺其實沒死結、只是慢的交易。

STEP 3

實用超能力

預防、偵測、逾時三種解法

化解死結的三條路

1. 預防 (prevention)——治本但代價高

• 一開始就鎖住所有要用的物件（單一原子步驟）：不會死結，但嚴重限制並行，且常無法預知會用到哪些物件（互動式瀏覽根本說不準）。
• 依固定順序請求鎖：可避免循環，但會造成過早上鎖、降低並行。
• 升級鎖 (upgrade lock)：CORBA 引入的第三種鎖，持有者可讀該資料，但與其他交易的升級鎖衝突，避免「兩個交易都先拿讀鎖再搶著升寫鎖」造成的死結。

2. 偵測 (detection)——找循環再中止

鎖管理員維護等待圖，setLock 時加邊、unLock 時刪邊，定期（或每次加邊時）檢查是否有循環。發現死結就選一個交易中止打破循環。選誰中止不簡單，可參考交易的年紀和它牽涉幾個循環。

3. 逾時 (timeout)——常用但有缺點

每個鎖有一段「不可侵犯期」，過後變成脆弱 (vulnerable)。若此時有別的交易在等這個物件，鎖就被打破、等待者繼續，被打破鎖的交易通常被中止。

flowchart TD
  A[偵測到死結] --> B[在循環中選一個交易]
  B --> C[中止它 釋放其鎖]
  C --> D[移除對應節點與邊 循環被打破]

逾時法的痛點

• 最糟的是：交易其實沒有死結，只是鎖剛好變脆弱又有人在等，就被冤枉中止。
• 系統過載時逾時暴增，長交易容易被懲罰。
• 逾時長度也很難拿捏。相較之下，偵測法是「真的有死結才中止，且能挑選犧牲者」。

STEP 1

深度探秘

讓鎖更聰明，擠出更多並行

即使粒度已最小，仍有空間

就算讀寫鎖、粒度也夠細了，還是有提升並行的餘地。書中介紹兩種進階策略：雙版本鎖（延後設互斥鎖到提交）與階層鎖（混合粒度）。

雙版本鎖 (two-version locking)

這是一種樂觀色彩的方案：允許一個交易寫入暫存版本，同時其他交易仍從已提交版本讀取。讀取只在「另一交易正在提交同一物件」時才需要等。

它用三種鎖——讀鎖、寫鎖、提交鎖 (commit lock)：

已設的鎖	設 read	設 write	設 commit
無	OK	OK	OK
read	OK	OK	wait
write	OK	wait	–
commit	wait	wait	–

• 讀鎖：除非物件有 commit 鎖，否則都能設。
• 寫鎖：除非物件有 write 或 commit 鎖，否則都能設。
• 交易要提交時，協調者把它的所有寫鎖轉成 commit 鎖；若物件還有別人的讀鎖，得等那些讀交易完成。

取捨：讀操作只在「提交期間」被擋（而非整個交易期間），通常很短；但讀操作反而可能拖延別人的提交。等待提交時還可能死結，故有時需中止。

STEP 2

生活妙喻

草稿與正本、行事曆的週與時段

雙版本鎖：改稿時別人還能看正本

想像一份公告：撰稿人正在改草稿版，但其他人此刻仍可閱讀牆上那份已定案的正本，完全不受影響。只有在撰稿人要把草稿「正式貼上牆取代正本」（提交）的那短短一刻，閱讀者才需要稍等一下。

相比傳統寫鎖「我一開始改你就不能看」，雙版本鎖把「不能看」的時間壓縮到只剩提交那一瞬間，所以讀取被擋得更少。

階層鎖：行事曆的「週／日／時段」

想像一本行事曆，結構是：週 → 每天一頁 → 每天再切成時段。

• 想「看整週」→ 在最頂層（週）設讀鎖，自動防止任何人改底下的時段。
• 想「填一個時段的約會」→ 只在那個時段設寫鎖。

這樣大範圍操作鎖一個大節點就好（省下大量小鎖），小範圍操作鎖細節點以保並行。同理，銀行的 branchTotal 在「分行」設讀鎖即隱含鎖住所有帳戶，而 deposit 只鎖一個帳戶餘額。

flowchart TD
  W[週] --> M[週一]
  W --> T[週二]
  M --> S1[時段 9到10]
  M --> S2[時段 10到11]

STEP 3

實用超能力

階層鎖與意圖鎖怎麼運作

階層鎖 (hierarchic locks)

Gray 提出：用一個有不同粒度的鎖階層，設一個父鎖等同於設了所有對應的子鎖，省下大量鎖。在銀行例子裡，分行是父、帳戶是子。

每個節點都可被鎖，鎖一個節點＝對它顯式存取、對其子節點隱式存取。

意圖鎖 (intention lock)

關鍵巧思：在對子節點上讀寫鎖前，要先在父節點及其祖先設一個「意圖讀／意圖寫」鎖，宣告「我等下要動底下某個子節點」。

• 意圖鎖彼此相容（大家都只是宣告意圖，互不干擾）。
• 但意圖鎖與真正的讀／寫鎖依常規衝突。

已設	read	write	I-read	I-write
無	OK	OK	OK	OK
read	OK	wait	OK	wait
write	wait	wait	wait	wait
I-read	OK	wait	OK	OK
I-write	wait	wait	OK	OK

實戰：銀行如何避免衝突

• branchTotal：在分行請求讀鎖 → 隱含對所有帳戶設讀鎖。
• deposit：要對某帳戶餘額設寫鎖，但先在分行設『意圖寫』鎖。

看表：分行已有 read 鎖時，I-write 請求要 wait。於是 branchTotal（分行讀鎖）和 deposit（分行意圖寫）不能同時跑，正確地序列化了——而不必對每個帳戶逐一上鎖比對。

階層鎖的好處：混合粒度時大幅減少鎖數量；代價是相容表與升級規則變複雜。長交易可鎖整批，短交易鎖細粒度，各取所需。

STEP 1

深度探秘

假設衝突很少，先衝再說

為什麼要樂觀

Kung 與 Robinson 指出鎖的幾個缺點：

• 維護鎖的開銷：連唯讀查詢都得上鎖，但其實大多時候沒人來搶。例如兩個程式各自更新 n 個物件，平均只有 1/n 的機會撞同一個——鎖往往只在最壞情況才需要。
• 可能死結：預防死結會嚴重降低並行，偵測與逾時都不完美。
• 為避免連鎖中止，鎖要握到交易結束，大幅降低並行。

樂觀法基於觀察：多數應用裡兩交易撞同物件的機率很低。於是讓交易盡情進行，假裝沒有衝突，等到要提交時才檢查。

三個階段

flowchart TD
  A[工作階段 用暫存版本自由讀寫 記錄讀集合與寫集合] --> B[驗證階段 收到closeTransaction時檢查是否與他人衝突]
  B --> C{驗證通過?}
  C -->|是| D[更新階段 把暫存版本變永久]
  C -->|否| E[衝突解決 中止某交易並重啟]

• 工作階段 (working phase)：每交易有自己的暫存版本，讀取讀已提交值或自己的暫存值，寫入只進自己的暫存值（別人看不到）。同時記錄讀集合 (read set) 與寫集合 (write set)。因為讀的都是已提交值，不會髒讀。
• 驗證階段 (validation phase)：提交時檢查與其他交易是否衝突；不通過就要中止某方。
• 更新階段 (update phase)：通過後把暫存版本永久化。唯讀交易通過驗證即可立刻提交。

STEP 2

生活妙喻

維基百科編輯與道歉比許可容易

像維基百科那樣「先編輯、送出時才看有沒有撞」

鎖是「事前許可」：動手前先搶到鎖，沒搶到就乾等。樂觀法是「事後驗證」：你儘管編輯（在自己的草稿上），按下送出時系統才檢查「這段期間有沒有別人也改了同一處」。

• 沒撞（大多數情況）→ 順利送出，超有效率。
• 撞了 → 顯示「編輯衝突」，請你重來。

背後的哲學是工程界名言：「請求原諒比請求許可容易」——既然衝突很少，何必每次都先去拿許可（上鎖）？先做，真出事再處理。

讀集合與寫集合：記下你「看過誰、改過誰」

驗證時要判斷會不會撞，靠的是每筆交易隨手記下的兩本帳：

• 讀集合：我這趟讀過哪些物件。
• 寫集合：我這趟改過哪些物件。

就像你編輯時記下「我參考了 A、B 段，動手改了 C 段」。送出時系統拿你的清單跟別人的清單比對，看有沒有重疊到會出事的地方。

STEP 3

實用超能力

前向驗證 vs 後向驗證，與飢餓

驗證的兩種方向

交易進入驗證階段時拿到一個遞增的交易編號（像每完成一筆就跳一格的偽時鐘）。驗證就是檢查 Tv 與重疊交易 Ti 的衝突。

後向驗證 (backward validation)

拿正在驗證的交易的讀集合，去比對較早、已提交的重疊交易的寫集合。若重疊→驗證失敗。

valid = true;
for (Ti = startTn+1; Ti <= finishTn; Ti++)
  if (Tv 的讀集合 與 Ti 的寫集合 有交集) valid = false;

• 唯一的解決方式：中止正在驗證的這筆（別人已提交無法動）。
• 只有寫、沒有讀的交易不必檢查。
• 需保留舊的寫集合，長交易時是負擔。

前向驗證 (forward validation)

拿正在驗證的交易的寫集合，去比對還在進行中（活躍）交易的讀集合。

• 較有彈性：可中止驗證中的這筆，或中止那些衝突的活躍交易，或延後驗證。
• 唯讀交易因為沒有寫集合，永遠通過前向驗證。

比較與飢餓

面向	後向驗證	前向驗證
比對對象	大的讀集合 vs 舊寫集合	小的寫集合 vs 活躍讀集合
衝突解決	只能中止自己	多種選擇
成本	要保留舊寫集合	要應付驗證中又有新交易開始

飢餓 (starvation)：靠中止重啟的方案無法保證某交易終究能通過——它可能每次重啟又撞上別人。Kung 與 Robinson 建議：若伺服器偵測到某交易被中止多次，就給它獨佔存取（用 semaphore 保護的臨界區）讓它做完。

STEP 1

深度探秘

一開始就決定誰先誰後

核心想法

時戳排序中，每筆交易一開始就拿到一個唯一的時戳 (timestamp)，定義它在時間序列中的位置。所有請求都可依時戳全序排列。每個操作執行時就立即驗證——不行就立刻中止並可重啟。

基本規則非常簡單：

交易要寫某物件，只有當該物件最後是被更早的交易讀和寫時才有效。交易要讀某物件，只有當該物件最後是被更早的交易寫時才有效。

物件帶著哪些時戳

每個物件有：一個寫時戳 (write timestamp)、一組暫存版本（各帶自己的寫時戳）、一組讀時戳 (read timestamp)（可用最大值代表）。

• 接受寫操作 → 建一個新暫存版本，寫時戳設為交易時戳。
• 讀操作 → 導向「寫時戳小於交易時戳中最大的」那個版本。
• 接受讀操作 → 把交易時戳加入該物件的讀時戳集合。
• 提交時 → 暫存版本的值與時戳變成物件的正式值與時戳。

衝突規則（Tc 是當前交易，Ti 是別的交易）

規則	Tc 操作	Ti 操作	條件
1	write	read	Tc 不可寫已被更晚 Ti 讀過的物件（Tc ≥ 最大讀時戳）
2	write	write	Tc 不可寫已被更晚 Ti 寫過的物件（Tc > 已提交版本寫時戳）
3	read	write	Tc 不可讀已被更晚 Ti 寫過的物件（Tc > 已提交版本寫時戳）

重點：時戳排序的序列順序是靜態決定（交易開始時就定了），這跟鎖的動態順序（看存取先後）不同。

STEP 2

生活妙喻

領號碼牌的銀行櫃台

進門就領號碼牌

時戳就像你一進銀行就抽的號碼牌——號碼小的「資歷較深」，理應先被服務。整間銀行的服務順序在大家抽號的那一刻就靜態決定了。

相較之下，鎖比較像「沒有號碼牌，誰先擠到櫃台誰先辦」——順序是動態地看誰先到。

「來晚了」就被請回

時戳排序的規矩很硬：

• 如果一個**號碼較大（較晚）的人已經先動過某筆資料，那麼一個號碼較小（較早）**的人現在才來想寫它——太遲了！按理它該排在前面卻姍姍來遲，於是它被中止、請它重新抽號（重啟）。

這就是「寫得太晚就中止」：因為一個時戳更晚的交易已經讀或寫過該物件了，這個遲到的早號交易若硬寫進去，會破壞「按號碼順序」的世界。

讀要等前面的人辦完

讀操作若指向一個還是暫存（未提交）的版本，就得等做出那版本的交易提交或中止——像你要參考前一位客戶剛辦的業務，得等他正式辦妥。這種等待不會死結，因為大家只會等號碼更小（更早）的人，箭頭永遠朝同一方向，不會繞成圈。

STEP 3

實用超能力

寫規則、讀規則與多版本改良

時戳排序寫規則

對交易 Tc 寫物件 D：

if (Tc >= D 的最大讀時戳 && Tc > D 已提交版本的寫時戳)
    在 D 的暫存版本上執行寫 寫時戳設為 Tc
else
    中止交易 Tc   // 寫得太晚

「太晚」意思是已有時戳更晚的交易讀或寫過該物件。

時戳排序讀規則

對交易 Tc 讀物件 D：

if (Tc > D 已提交版本的寫時戳) {
    選出寫時戳 <= Tc 中最大的版本 Dselected
    if (Dselected 已提交) 讀它
    else 等待做出 Dselected 的交易提交或中止 然後重新套用讀規則
} else
    中止交易 Tc   // 讀得太晚

• 讀到「太早」（指向未提交版本）→ 等先前交易完成（防髒讀）。
• 讀到「太晚」→ 中止。

重要性質與改良

• 這個演算法是嚴格的：讀寫都延遲到先前寫者提交或中止，達成嚴格執行。
• 它不會死結（只等更早者），但容易造成重啟。
• 忽略過時寫規則 (ignore obsolete write)：若一個寫太晚但沒人讀過該物件，可直接忽略而不中止整筆交易（反正它的效果本來也會被蓋掉）。
• 多版本時戳排序 (multiversion timestamp ordering)：為每個物件保留一串舊的已提交版本。好處是讀永遠不必因為來晚而被拒——晚到的讀可以去讀一個舊的已提交版本。代價是儲存空間，但並行度高、無死結、讀操作總被允許。

STEP 1

深度探秘

三種武器的取捨

三種方法回顧

我們學了三種控制並行存取的方法：嚴格兩階段鎖、樂觀法、時戳排序。三者都有時間與空間開銷，也都會在某種程度上限制並行。

悲觀 vs 樂觀

• 悲觀法 (pessimistic)：鎖與時戳排序——存取每個物件時就當場偵測衝突。
• 樂觀法 (optimistic)：讓所有交易先進行，提交時才檢查（前向驗證可更早中止）。衝突少時很有效率，但中止時得重做大量工作。

鎖 vs 時戳排序（都是悲觀法）

面向	時戳排序	兩階段鎖
序列順序何時定	靜態（交易開始）	動態（依存取順序）
衝突時的反應	立刻中止交易	讓交易等待（之後可能為解死結而中止）
擅長	讀多的交易（尤其多版本）	寫多的交易

flowchart TD
  A[偵測到衝突存取] --> B{用哪種方法}
  B -->|時戳排序| C[立刻中止]
  B -->|鎖| D[等待 必要時為解死結才中止]
  B -->|樂觀法| E[先放行 提交時才驗證再決定中止]

因此有人提出混合方案：讀多的交易用時戳排序、寫多的用鎖。歷史上分散式系統最主流的還是鎖（如 CORBA 並行控制服務完全基於鎖，並提供階層鎖）。

STEP 2

生活妙喻

三種餐廳帶位策略

用三種餐廳帶位法理解三種並行控制

• 鎖＝先到先佔桌，後到的乾等：你坐下就佔住桌子（上鎖），別人想用就得在旁邊等你離開。兩桌互佔對方想要的位子時，會卡死（死結）。適合「大家都要動很多桌」（寫多）的場合。

• 時戳排序＝進門領號碼牌，順序當場定：號碼決定一切。若你號碼小卻晚到、別人號碼大卻先動了，你就被請回重新領號（中止重啟）。對「只是來看看菜單」（讀多）的客人特別友善，尤其有多份菜單副本（多版本）時。

• 樂觀法＝先入座點餐，結帳時才查有沒有重複下單：大家先自由點，結帳時系統才檢查有沒有撞單。沒撞（多數情況）超順暢；撞了就請其中一桌重點（中止重做）。

為什麼鎖最常見

就像多數餐廳還是用最直覺的「先到先坐」——鎖在資料庫界用了數十年、最被理解、工具最成熟，所以分散式系統歷史上以鎖為主流。

STEP 3

實用超能力

雲端協作怎麼處理並行

三種排程選擇

排程一個操作時，永遠只有三種選擇：(1) 立刻執行、(2) 延遲、(3) 中止。三大方法只是用不同策略在這三者間取捨。

真實世界：雲端協作多用樂觀法 + 衝突解決

二十一世紀的網路協作應用，常用樂觀並行控制搭配衝突解決（而不是直接中止某一方）：

服務	並行控制方式	粒度
Dropbox	樂觀法；兩人同改同檔，第一個寫入被接受、第二個被拒；提供版本歷史供手動合併	整個檔案
Google Docs	樂觀法；多人同編可即時看到彼此的游標與輸入，因持續感知而少衝突	文字逐字元、試算表逐儲存格（同格則最後寫入者贏）
Wikipedia	樂觀法；第一個寫入被接受，後者看到「編輯衝突」畫面請其解決	頁面
Dynamo（Amazon）	樂觀法加衝突解決；用 get/put 而非交易，不提供 ACID 的隔離保證	鍵值

共同點：既然衝突少，就先讓大家做，真撞上了再讓人合併或重做，而不是事先用鎖把大家擋住。這跟前面學的樂觀法精神一脈相承。

帶走的判斷力

下次設計系統時可以這樣想：

• 寫密集、衝突多 → 偏向鎖。
• 讀密集、衝突少 → 偏向時戳排序／多版本或樂觀法。
• 使用者能彼此感知、可接受事後合併（協作編輯）→ 樂觀法 + 衝突解決。

沒有萬靈丹，重點是看你的讀寫比例與衝突機率選對工具。