深度探秘

什麼是「複製」，為什麼分散式系統離不開它

複製是什麼

複製（replication） 就是「在多台電腦上維護同一份資料的多個副本」。聽起來很單純，但它幾乎撐起了整個現代分散式系統。你每天用的瀏覽器快取、web proxy、DNS 名稱服務，其實都是某種複製。

複製的動機有三個，彼此不完全相同，常被搞混：

關鍵差別：高可用的資料不一定是正確的資料。它可能過期、或在網路分割兩側被改成互相衝突。容錯則更嚴格——它保證在一定數量與類型的故障下，行為永遠嚴格正確。

為什麼複製不可變資料很便宜，可變資料很貴

• 複製**不可變（immutable）**資料幾乎沒成本：反正不會改，多放幾份只會更快。
• 複製會變動的資料（像網頁內容）就要付出代價：得設計協定確保客戶端拿到夠新的資料。所以複製作為效能手段是有極限的。

生活妙喻

連鎖便利商店

把複製想成「連鎖便利商店」

想像一個品牌在城市各處開了很多家分店，每家都賣一樣的東西。

• 效能：你不用大老遠跑到總店，就近的分店就能買到——這就是「把資料放在離使用者近的地方降低延遲」。
• 高可用：某家分店今天裝修沒開？沒關係，你走去下一家還是買得到。一台 server 壞了，客戶端就去找另一台。
• 容錯：但「買得到」不等於「買到對的東西」。如果某家分店的標價牌還沒更新（過期資料），你可能用舊價結帳。要保證每家分店資訊都嚴格正確，需要額外、更費工的協調。

這正是 availability vs. correctness 的差別：分店全開（高可用）很容易，但要每家標價都同步到分秒不差（容錯／一致），就得付出代價。

火車上斷網的使用者把行事曆複製到筆電，就像「把分店的庫存抄一份帶在身上」——能離線工作，但回到公司可能發現別人也訂走了同一個時段。

實用超能力

用機率公式估算可用性

算一算：多放幾台能多可用？

假設每台 server 獨立地以機率 $p$ 故障或不可達。那麼 $n$ 台 server 上某物件的可用性是：

$$\text{availability} = 1 - p^{n}$$

意思是：只有「全部 $n$ 台都掛掉」物件才不可用，而那件事的機率是 $p^n$。

舉例：若單台故障機率 $p = 0.05$（5%），放兩台（$n=2$）：

$$1 - 0.05^{2} = 1 - 0.0025 = 0.9975 = 99.75%$$

只要再多一台，可用性就明顯逼近 100%。

注意快取和伺服器複製的差別

快取（cache）不一定整份完整保存物件——你可能快取了檔案 A 卻沒快取檔案 B。所以快取不一定提升「應用層級」的可用性。整份複製到 server 才真正撐起可用性。

別忘了網路分割與斷線

除了 server 故障，網路分割（partition） 與斷線運作也是可用性的大敵，尤其行動裝置使用者常常不小心斷線。要在斷線時還能工作，就得能容忍過期資料並在重連後解決衝突。

深度探秘

三個角色：client、front end、replica manager

複製管理的通用模型

要管理複製資料，書中給了一個與具體系統無關的通用架構，由三種角色組成：

• client（客戶端）：發出操作請求，例如讀取或更新一個邏輯物件（如行事曆、銀行帳戶）。
• front end（前端）：客戶端的請求先經過它。它負責用訊息和一個或多個 replica manager 溝通，讓客戶端不必自己處理「有好幾份副本」這件事。
• replica manager（副本管理員，RM）：實際存放副本、直接對副本執行操作的元件。在 client-server 環境裡，一個 RM 就是一台 server。

flowchart LR
  C[客戶端] --> FE[front end]
  FE -->|請求與回覆| RM1[replica manager]
  FE --> RM2[replica manager]
  FE --> RM3[replica manager]

front end 是讓複製透明的關鍵。客戶端只看到「一個邏輯物件」，回傳「一組值」，不知道背後其實有好幾份實體副本在協同運作。

兩個重要假設

• 可恢復地套用操作：RM 套用操作要能在中途失敗時不留下不一致結果。
• state machine（狀態機）：有時要求每個 RM 是狀態機——原子地套用操作，且最終狀態完全由「初始狀態 + 操作序列」決定，不受時鐘或感測器等非決定性因素影響。這也意味著 server 可能不能多執行緒。

生活妙喻

點餐櫃台與後場廚房

把架構想成「速食店點餐」

• 你（client） 走到櫃台說「我要一份套餐」。
• 櫃台店員（front end） 接下你的單。你不需要知道後場有幾位廚師、誰負責炸薯條、誰煎肉排。櫃台幫你把單分派出去、收集結果，最後遞給你一份完整的餐。
• 後場廚師們（replica managers） 各自實際做菜。

你只看到「一份套餐」（一個邏輯物件），不會看到背後三位廚師其實各做了一份。這就是複製透明性。

五個階段就像一張單的旅程

1. Request：櫃台把單交給後場（給一位、或同時廣播給全部廚師）。
2. Coordination：廚師們先喬好——這單要不要做、誰先做、順序怎麼排。
3. Execution：廚師動手做（有時是「暫時做」，之後可撤回）。
4. Agreement：大家對「最後要出哪份」達成共識（交易系統裡可能集體決定 commit 或 abort）。
5. Response：把成品遞回櫃台，櫃台給你。

不同系統會調整這幾個階段的順序與內容。例如支援離線的系統會「儘早回應」你，而容錯系統會「等到確定正確才回應」。

實用超能力

看懂五階段與三種排序

一次請求的五個階段

flowchart TD
  A[Request 前端發出請求] --> B[Coordination 副本管理員協調順序]
  B --> C[Execution 執行可能是暫時的]
  C --> D[Agreement 對效果達成共識]
  D --> E[Response 回覆前端再給客戶端]

• Request：front end 可只送給一個 RM（再由它轉給其他人），或直接群播給全部 RM。
• Coordination：RM 之間協調，決定是否套用此請求，以及它相對於其他請求的順序。
• Execution：執行，可能是暫時性的（之後能 undo）。
• Agreement：對「要 commit 的效果」達成共識。
• Response：一個或多個 RM 回覆 front end，front end 可能挑第一個到達的（重可用），或挑多數派的（容忍 Byzantine 失效）。

三種排序，多數應用只要 FIFO

大多數應用只需要 FIFO；因果與全序的需求會在被動／主動複製中討論。

深度探秘

動態群組、群組檢視與被懷疑的成員

為什麼複製需要「動態群組」

複製時，replica manager 會加入（有人複製一份行事曆到自己筆電）與離開（某 RM 當機）。前幾章假設群組成員是靜態的，但複製需要動態成員管理（group membership management）。

一個完整的群組成員服務會維護 群組檢視（group view）：當前群組成員的清單，依加入順序排列，每次有人加入或被排除就產生一個新檢視。

「被懷疑」也會被踢出

關鍵觀念：成員服務可能因為某 process 被**懷疑（Suspected）**而把它排除，即使它根本沒當機——它可能只是因為通訊故障變得不可達，本身還在正常運作。

• 一旦被排除，就不再有訊息送達它。
• 在 closed group 裡，它若重新連上，送出的訊息也不會被遞送，它得用新身分重新加入。

設計難題：除了把失效偵測器做得儘量準確，更要確保系統即使誤判某 process也不會行為錯誤。

primary-partition vs. partitionable

網路分割會把群組切成多個子群。成員服務分兩派：

• primary-partition：最多只讓一個子群（多數派）存活，其餘被告知暫停。適合資料重要、不一致代價高的場合。
• partitionable：允許多個子群各自繼續運作（例如視訊會議分組討論），分割修復後再合併。

生活妙喻

群組視訊通話的成員名單

把群組檢視想成「視訊會議的參與者名單」

你開過線上會議吧？畫面側邊有一份「目前在線」的名單：

• 有人加入、有人離開，名單就更新成新版本——這就是一個新的 group view。
• 重點是：每個人看到的「名單更新順序」要一致，不然會很混亂。

「被懷疑」就像網路卡頓被踢出

有時某位同事其實人還在、麥克風也開著，但他網路卡住、訊號傳不出來。系統判定他「失聯」就把他從名單移除——即使他本人沒離開。等他網路恢復，他得重新加入會議（等於用新身分回來），而不是無縫接回。

這正是「被懷疑（Suspected）」：不可達不代表當機，但成員服務有權先把他排除。

兩種分割策略

• primary-partition：會議分裂成兩半時，只讓人數多的那半繼續，另一半被請出去。適合「決議很重要、不能各開各的」的場合。
• partitionable：允許兩半各自繼續討論，之後再把結論合併。適合「分組腦力激盪」這種可容忍各做各的場合。

實用超能力

檢視同步通訊：在系統上畫一條線

檢視遞送的基本要求

每個成員會收到一連串檢視 $v_0(g), v_1(g), v_2(g), \dots$。基本要求：

• Order（順序）：若 p 先遞送 v 再遞送 v'，則沒有其他 process 會在遞送 v 之前先遞送 v'——各 process 看到的檢視變化順序一致。
• Integrity（完整性）：若 p 遞送了某檢視，則 p 自己在那個檢視裡。
• Non-triviality（非平凡）：若兩個 process 能無限期互通，最終應被視為同群成員；分割若持續，檢視最終應反映分割。

檢視同步群組通訊

view-synchronous group communication 在上述之上，額外保證「檢視通知」與「群播訊息」的遞送順序一致。它把可靠群播延伸到「群組檢視會變動」的情況：

• Agreement：正確 process 遞送相同的檢視序列，且在任一檢視內遞送相同的訊息集合。
• Integrity：訊息只遞送一次，且送訊者在遞送該訊息的檢視內。
• Validity：正確 process 一定能遞送自己送出的訊息；若某 process q 沒收到，系統會在該檢視之後立刻遞送一個排除 q 的新檢視。

flowchart TD
  M[p 送出訊息 m] --> Q{m 有沒有先到達其他人}
  Q -->|沒到任何人| A[q 與 r 只遞送新檢視 不含 m 允許]
  Q -->|至少到一人| B[q 與 r 先遞送 m 再遞送新檢視 允許]
  Q -->|先檢視後 m| C[不允許 等於收到已判失敗者的訊息]

直覺：遞送新檢視就像在系統上畫一條線，每個被遞送的訊息都一致地落在線的某一側。這讓程式設計師能靠本地觀察推斷其他人的狀態，也能拿來做 state transfer（把現有成員的工作狀態交給新加入者）。

深度探秘

看似合理卻會出錯的天真複製

什麼叫「正確」的複製服務

直覺上，一個基於複製的服務若要算正確，要滿足兩件事：

1. 即使有故障仍持續回應；
2. 客戶端分不出它拿到的服務和「單一正確 RM」提供的有何不同。

聽起來簡單，但若不小心，多個 RM 就會出現單一 server 永遠不會發生的怪異行為。

一個會出錯的銀行例子

兩台 RM 在電腦 A 和 B 各存帳戶 x 和 y 的副本，初始皆為 $0。RM 之間在背景互相傳播更新（回應客戶端之後才傳）。

• Client 1 在本地 B 把 x 設為 $1，接著想把 y 設為 $2，卻發現 B 掛了，於是改在 A 設 y = $2。
• Client 2 在本地 A 讀取：先讀到 y = $2，再讀 x = $0（因為 x 從 B 的更新還沒傳到 A，B 已掛）。

sequenceDiagram
  participant C1 as Client 1
  participant B
  participant A
  participant C2 as Client 2
  C1->>B: setBalance x 1
  Note over B: B 當機，更新沒傳到 A
  C1->>A: setBalance y 2
  C2->>A: getBalance y 得到 2
  C2->>A: getBalance x 得到 0

這違反常識：既然 Client 2 讀到 y = $2（y 是在 x 之後更新的），它就應該讀到 x = $1。單一 server 絕不會出現這種矛盾。第一步是先弄清楚「什麼才算複製系統的正確行為」。

生活妙喻

兩本還沒同步的記帳本

把兩台 RM 想成「兩本記帳本」

你和室友各拿一本記帳本記錄共同花費，講好「先各自記，晚點再對帳同步」。

• 你在你的本子記下「買菜 $1」，正想再記「水電 $2」時，發現你的本子被借走了（B 當機），於是你改在室友的本子記「水電 $2」。
• 室友後來只看自己的本子：看到「水電 $2」卻沒看到「買菜 $1」（那筆還困在你被借走的本子裡）。

結果室友的帳對不起來：明明水電是在買菜之後記的，怎麼會有水電卻沒買菜？

如果只有一本共用帳本，這種矛盾根本不會發生。問題就出在「兩本還沒同步」加上「中途一本不見了」。

兩個一般性需求

• 複製透明性：使用者不該需要知道有好幾本帳。
• 一致性（consistency）：操作打在這群副本上，結果要符合物件的正確性規格。連線中的不同客戶端用不同副本時，通常不能拿到互相矛盾的結果。

實用超能力

辨認違反正確性的執行

怎麼判斷一個執行是否「合理」

核心檢驗：能不能找到一種把所有客戶端操作交錯起來的順序，使得結果符合「單一正確副本」的規格？

在銀行例子中，找不到任何交錯能同時滿足合理的帳戶規格——因為若 y 的更新被觀察到，而 y 是在 x 之後更新的，那麼 x 的更新也應該被觀察到。這個執行因此是不正確的。

正確性關心三件事

• 資料新鮮度（freshness）：客戶端拿到的資料夠不夠新。
• 操作效果：客戶端的操作對資料造成的效果是否符合規格。
• 有時還關心及時性（timeliness）：如空中交通管制，需要在很短時間內拿到正確資料。

一致性的強度可以調

一致性的需求強弱因應用而異：

• 離線運作時，資料可以暫時不一致（行事曆例子）。
• 但連線中的多個客戶端用不同副本時，通常不能得到違反應用正確性的矛盾結果。

下一節會把「正確」精確化成兩個著名標準：linearizability 與 sequential consistency。

深度探秘

兩種正確性標準的精確定義

用「虛擬交錯」定義正確性

設客戶端 $i$ 在某次執行的讀寫操作序列為 $o_{i0}, o_{i1}, o_{i2}, \dots$。單一 server 會把這些操作序列化成一條交錯序列。我們用一個虛擬交錯（不一定真的發生在哪台 RM 上）來定義正確性。

Linearizability（線性化）

一個複製服務是 linearizable，若存在一種把所有客戶端操作交錯的順序，同時滿足：

1. 交錯序列符合單一正確副本的規格；
2. 交錯中的操作順序，與操作實際發生的真實時間一致。

這是最嚴格的標準：它捕捉「客戶端應拿到最新資訊」的直覺。

Sequential consistency（循序一致）

較弱的標準。保留第 1 條，但把第 2 條改成：

2'. 交錯中的操作順序，與**每個客戶端各自的程式順序（program order）**一致。

關鍵差別：循序一致不涉及真實時間，也不要求任何全域總順序，只要不違反每個客戶端自己的先後順序、且結果符合規格即可。

兩者的關係

• 每個 linearizable 服務必然也是 sequentially consistent（真實時間順序本就反映了各客戶端程式順序）。
• 反之不成立：可以循序一致卻不線性化。
• 注意：linearizability 只管「個別操作」的交錯，不是交易性的；沒有並行控制時仍可能破壞應用層的一致性。

生活妙喻

洗牌：保留每疊原順序

把循序一致想成「洗牌」

想像每個客戶端各有一疊撲克牌，牌的順序就是它的程式順序。

• 循序一致就像把好幾疊牌**洗（shuffle）**在一起：可以任意交錯，唯一規則是每一疊內部的原始順序不能被打亂，而且每張牌翻開時結果要對得上規格。
• 至於兩疊之間誰先誰後？洗牌時完全自由——這就是「不涉及真實時間」。

線性化多了一條「時間軸」規則

線性化比洗牌更嚴格：除了保留每疊內部順序，還要求最後的牌序符合真實世界發生的時間先後。

打個比方：兩個人分別在 10:00 和 10:01 出牌，線性化要求結果裡 10:00 那張一定排在 10:01 那張前面；而循序一致不管時間，只要各自那疊的內部順序沒亂就行。

所以線性化是「洗牌 + 尊重真實時鐘」，循序一致只是「洗牌 + 尊重各疊順序」。難怪每個線性化都是循序一致，反過來卻不一定。

實用超能力

為什麼真實時間那條規則難實作

一個循序一致但不線性化的例子

flowchart TD
  A[Client1 在 B 設 x 為 1] --> B[更新尚未傳到 A]
  B --> C[Client2 在 A 讀 x 得到 0]
  C --> D[真實時間上設定早於讀取 但讀到舊值]
  D --> E[違反線性化的真實時間規則]
  E --> F[卻能排出符合循序一致的交錯]

即使 A、B 都沒當機，只要 Client 1 在 B 對 x 的更新還沒傳到 A，Client 2 在 A 讀 x 就會讀到舊值 0。

• 真實時間規則被違反：設定 x 確實早於讀取 x，卻讀到舊值。所以不線性化。
• 但能排出一種交錯：把讀取排在設定之前，且不違反任一客戶端的程式順序——所以仍循序一致。

為什麼真實時間那條規則「理想但難做」

• 線性化的真實時間要求很理想，因為它保證客戶端拿到最新資訊。
• 但它要求把各台機器的時鐘同步到足夠精確，現實中往往做不到。
• 因此循序一致成為實務上常用的較弱替代——它捕捉「處理順序」的要求，卻不訴諸真實時間。

記憶口訣：要最新、要對齊真實時鐘 → 線性化（貴）；只要各自順序說得通 → 循序一致（實際）。

深度探秘

一個主、多個備援的容錯模型

被動複製的結構

在 passive（primary-backup） 模型裡，任何時刻只有：

• 一個 primary（主） replica manager；
• 一個或多個 backup（備援／slave） replica manager。

純粹形式下，front end 只跟 primary 溝通。primary 執行操作，再把更新後的狀態送給 backups。primary 一旦失效，就由某個 backup 升格成新的 primary。

一次請求的事件序列

1. Request：front end 把帶有唯一識別碼的請求送給 primary。
2. Coordination：primary 依收到順序原子地處理；先檢查識別碼，若已執行過就直接重送回應。
3. Execution：primary 執行請求並儲存回應。
4. Agreement：若是更新，primary 把「更新後狀態 + 回應 + 識別碼」送給所有 backup，backup 回傳確認。
5. Response：primary 回覆 front end，再交回客戶端。

flowchart TD
  FE[front end] -->|請求| P[primary RM]
  P -->|更新狀態| B1[backup RM]
  P -->|更新狀態| B2[backup RM]
  B1 -->|確認| P
  B2 -->|確認| P
  P -->|回應| FE

因為 primary 把所有操作排序，這個系統在 primary 正確時實作了 linearizability。

生活妙喻

主廚與見習廚師

把 primary-backup 想成「主廚帶見習生」

餐廳後場有一位主廚（primary） 和幾位見習廚師（backup）：

• 所有訂單都先交給主廚。主廚決定怎麼做、按什麼順序做——他一個人說了算，所以出菜順序絕不會亂（這就是 linearizability 的來源）。
• 主廚做完後，不是叫見習生重做一遍，而是直接告訴他們「最後成品長這樣」，讓他們照抄記下來（傳的是更新後的狀態，不是操作本身）。
• 主廚突然請假（當機）？見習生裡選一位升格當主廚，從中斷處接手。

為什麼「傳狀態」很聰明

因為傳的是結果狀態而非「操作的規格」，所以即使主廚的行為是非決定性的（例如多執行緒），見習生也只是忠實記下主廚決定的狀態，不會各自算出不同結果。

這是被動複製相對主動複製的一個優點：primary 可以非決定性運作，backup 只負責「照抄狀態」。

實用超能力

靠檢視同步通訊安全接手

primary 失效時，怎麼保證接手正確？

要維持 linearizability，接手必須滿足兩件事：

1. primary 被唯一一個 backup 取代（不能兩個 backup 同時自認是新 primary）；
2. 存活的 RM 對「接手時哪些操作已執行」達成一致。

解法：把 primary 與 backups 組成一個群組，primary 用檢視同步群組通訊送更新。如此：

• primary 當機後，通訊系統最終遞送一個排除舊 primary 的新檢視；存活 backup 可用該檢視挑出唯一新 primary（例如選檢視中第一個成員），並向名稱服務註冊。
• 由檢視同步的順序性 + 已存識別碼，新 primary 與存活 backup 一致同意每個更新到底處理了沒有。

重送請求也安全

沒收到回應的 front end 會把請求重送給新 primary。新 primary 不必知道舊 primary 當機在哪個階段——它直接從階段 2 開始，靠檢視同步保證大家都處理過同一組訊息，無需再諮詢 backup。

成本與取捨

實例：Harp 檔案系統、Sun NIS（用較弱保證）。

深度探秘

所有副本平等、各自獨立執行

主動複製的結構

在 active replication 模型裡，所有 replica manager 都是平等的 state machine，組成一個群組。沒有 primary。

• front end 把請求**群播（multicast）**給整個群組；
• 每個 RM 獨立但完全相同地處理請求並回覆；
• 任何一個 RM 當機都不影響服務效能，因為其他 RM 照常回應。

一次請求的事件序列

1. Request：front end 附上唯一識別碼，用全序、可靠群播送給群組。它最多只會 crash 失效，且在收到回應前不發下一個請求。
2. Coordination：群組通訊系統以相同的（全序）順序把請求遞送給每個正確 RM。
3. Execution：每個 RM 執行請求。因為是 state machine 且順序相同，所有正確 RM 處理結果完全一致。
4. Agreement：不需要額外的共識階段——群播的遞送語意已保證一致。
5. Response：每個 RM 回覆 front end，front end 依失效假設決定收集幾個回應。

flowchart TD
  FE[front end] -->|全序可靠群播| RM1[RM state machine]
  FE -->|全序可靠群播| RM2[RM state machine]
  FE -->|全序可靠群播| RM3[RM state machine]
  RM1 -->|回應| FE
  RM2 -->|回應| FE
  RM3 -->|回應| FE

因為大家以相同順序處理相同請求，最終狀態都相同。

生活妙喻

全班同學抄同一份板書

把主動複製想成「全班抄同一份板書」

老師（front end）在黑板上依固定順序寫下每一道題目，全班同學（每個 RM）各自抄、各自算：

• 因為大家拿到的題目順序完全相同，而且每個人都用相同的算法（state machine），所以全班算出的答案必然一致。
• 某個同學打瞌睡缺了一題（當機）？沒關係，老師收作業時看其他同學的就好，課堂照常進行——這就是「任何 RM 當機都不影響服務」。

為什麼「順序」這麼關鍵

如果老師對不同同學報出不同順序的題目，大家的中間狀態就會分岔，答案就對不上了。所以必須是全序群播：每個正確同學都以同一順序收到同一批題目。

抓出說謊的同學

如果有同學故意亂寫答案（Byzantine），老師可以比對多份作業：只要正確的人夠多，多數一致的答案就能蓋過搗蛋的。這是主動複製能容忍 Byzantine 失效的關鍵——front end 收集並比對回應。

實用超能力

一致性層級與 Byzantine 容錯

達成的是 sequential consistency，不是 linearizability

• 所有正確 RM 處理相同請求集合（可靠群播）且相同順序（全序），加上是 state machine，故狀態一致。
• 每個 front end 的請求以 FIFO 處理（它等回應才發下一個），等同程式順序 → sequential consistency。
• 但不達成 linearizability：RM 處理的全序不必然等於客戶端發請求的真實時間順序。
  • Schneider 提出在同步系統用近似同步時鐘＋物理時間戳排序，可逼近但不保證線性化。

容忍 Byzantine 失效

解決全序可靠群播等價於解決 consensus。若有能容忍 Byzantine 的共識解，主動複製可遮蔽最多 $f$ 個 Byzantine 失效，只要至少有 $2f+1$ 個 RM：

• 每個 front end 等到收集 $f+1$ 個相同回應才回給客戶端；
• 為確認回應對應正確請求，要求 RM 對回應數位簽章。

可放寬的地方

被動 vs. 主動 對照

深度探秘

用閒聊傳播更新換取高可用

gossip 架構在做什麼

前面的容錯系統用急切（eager）方式傳播更新——所有 RM 儘快收到並達成共識才回應客戶端。這對高可用很不利。

gossip 架構反其道而行：把資料複製到靠近各群客戶端的地方，RM 之間定期交換「gossip（閒聊）」訊息來傳遞各自收到的更新。名字就來自這種「八卦傳話」的味道。

gossip 服務有兩種操作（比前面的定義更窄）：

• query：唯讀；
• update：只修改、不讀取狀態。

front end 可把 query 與 update 送給任何一個可用、回應快的 RM。系統提供兩個保證：

1. 每個客戶端隨時間得到一致的服務：RM 回答 query 時，至少反映該客戶端目前為止觀察過的所有更新（即使換了 RM）。
2. 副本間的鬆弛一致：所有 RM 最終都會收到所有更新，但兩個客戶端可能看到不同副本，也可能讀到過期資料。

flowchart LR
  FE1[front end] -->|query 或 update| RM1[RM]
  FE2[front end] -->|query 或 update| RM2[RM]
  RM1 -.gossip.-> RM2
  RM2 -.gossip.-> RM3[RM]
  RM3 -.gossip.-> RM1

生活妙喻

辦公室口耳相傳的消息

把 gossip 想成「辦公室八卦」

公司沒有強制的公告系統，消息靠同事口耳相傳：

• 你聽到一則消息，就在茶水間遇到同事時順口提一下；過幾天，整個辦公室遲早都知道（最終所有 RM 都收到所有更新）。
• 但在某個瞬間，A 同事可能已經知道、B 同事還沒——所以兩個人「掌握的版本」可能不同（鬆弛一致、可能讀到過期資料）。
• 不過有個底線：你自己問同一件事，得到的版本只會越來越新、不會倒退（每客戶端隨時間一致），即使你問的是不同同事。

三種傳話的「規矩」

因果順序最便宜，能用就用；強制與立即較貴。query 永遠以因果順序執行。

實用超能力

向量時間戳與 RM 的狀態元件

向量時間戳怎麼追蹤更新

RM 編號為 0, 1, 2, …。向量時間戳的第 $i$ 個元素＝該 RM 從 front end 收到的更新數；第 $j$ 個（$j \neq i$）＝經由 gossip 從 $j$ 傳來、$i$ 已收到的更新數。

例如三 RM 系統中，manager 0 的 value timestamp 為 $(2, 4, 5)$ 表示：它的值已反映 manager 0 的前 2 個、manager 1 的前 4 個、manager 2 的前 5 個更新。

• front end 維護 prev 時間戳，記錄它（與客戶端）觀察過的最新版本，隨每個請求送出；RM 回傳 query 結果時附上 new，update 則回傳唯一的 Update ID，front end 把它們合併進 prev。
• 客戶端之間直接通訊時，也透過 front end 夾帶（piggyback）向量時間戳，以正確推斷因果關係。

RM 的主要狀態元件

flowchart TD
  V[Value 應用狀態] --- VT[Value timestamp 已反映的更新]
  L[Update log 所有收到的更新] --- RT[Replica timestamp 已接受進 log 的更新]
  E[Executed operation table 防重複套用] --- T[Timestamp table 各 RM 的時間戳]

一個更新只有在stable（可符合其順序保證地套用）時才會被執行；否則先壓在 log 裡。

深度探秘

讓大家先改再喬，靠領域知識解衝突

Bayou 的核心想法

Bayou 和 gossip 一樣提供高可用、弱於循序一致的複製，RM 也成對交換更新（稱為 anti-entropy 反熵協定）。但 Bayou 的突破在於：它做領域特定的衝突偵測與解決（domain-specific conflict detection and resolution）。

回想行事曆例子：在 gossip 中若要嚴格一致，更新得用 forced（全序）操作，於是只有多數派分割能更新——即使你只是想填一個不衝突的空檔，也被當成可能重複預訂的人一樣對待。

Bayou 不一樣：火車上和辦公室的使用者想改就改，更新都被先套用記錄在抵達的那個 RM 上。等兩個 RM 在 anti-entropy 交換中合併更新時，才偵測並解決衝突。

例如主管在外地和秘書在公司各自在同一時段加了約會，Bayou 在主管重連後偵測到衝突，並依領域特定政策解決（例如確認主管的約會、移除秘書的預訂）。這種「撤銷或修改部分衝突操作以解決衝突」的效果，稱為 operational transformation（操作轉換）。

Bayou 複製的狀態存成資料庫，一個 Bayou 更新是帶有 ACID 保證的特殊交易。

生活妙喻

共用 Google 行事曆的自動協調

把 Bayou 想成「聰明的共用行事曆」

你和同事共用一份行事曆，各自在沒網路時都可以先填上約會：

• 回到有網路時，系統把大家的修改合併。
• 如果發現你和同事都訂了週三 14:00（衝突），它不會傻傻地兩個都留或都拒，而是依事先講好的規則自動處理——例如「主管優先」，就保留主管的、把同事的挪走或取消。
• 你原本訂的時段可能「跳」到附近的空檔——這就是操作轉換：你的操作被改成「達成類似目的但避開衝突」。

tentative（暫定）vs. committed（確定）

• 新填的約會一開始是暫定（tentative），畫面上可能標成灰色或「待確認」。
• 系統最終會把暫定更新排進一個標準順序並標記為確定（committed），之後不再變動。
• 在暫定期間，系統可能反覆撤銷再重做這些更新以產生一致狀態。

重點：一定要讓使用者清楚分辨「哪些是暫定、哪些已確定」，否則約會突然『跳格』會讓人很困惑。

實用超能力

dependency check 與 merge procedure

每個更新自帶兩樣法寶

除了操作本身（型別與參數），每個 Bayou 更新還包含兩個領域特定元件：

flowchart TD
  U[一個 Bayou 更新] --> D[dependency check 依賴檢查]
  D -->|無衝突| AP[直接套用操作]
  D -->|有衝突| M[merge procedure 合併程序]
  M -->|找到替代| AP2[套用調整後的操作]
  M -->|找不到| ERR[回報錯誤]

• dependency check（依賴檢查）：套用操作前先呼叫，檢查若套用會不會衝突，可檢查資料庫任何部分。
  • 最簡單：測 write-write 衝突（別人是否已填該時段）。
  • 也能測 read-write 衝突（例如該時段空著且當天約會少於六個）。
• merge procedure（合併程序）：若依賴檢查發現衝突就呼叫，把操作改成「達成類似目的但避開衝突」（例如改訂鄰近時段，或用優先權決定誰留）。找不到合適調整就回報錯誤。

合併程序的效果是決定性的——Bayou RM 是 state machine，這樣每個 RM 才會解出相同結果。

最終一致與缺點

• Bayou 保證：最終每個 RM 收到相同更新集合，並套用成完全相同的資料庫（若更新停止）。這叫最終循序一致（eventually sequentially consistent）。
• 它讓複製非透明——應用必須提供依賴檢查與合併程序。
• 缺點：(1) 程式設計師負擔大（要寫這兩個程序）；(2) 使用者負擔大（要面對暫定資料與『被改掉』的操作）。適用於衝突少、語意簡單、使用者能接受暫定資訊的場合（如 CSCW）。

深度探秘

為斷線而生的高可用檔案系統

Coda 想解決什麼

Coda 是 AFS 的後裔，要補足 AFS 不足的三件事：

1. AFS 的複製僅限唯讀 volume，規模一大就成瓶頸；
2. server 與網路故障常造成可用性問題；
3. AFS 不支援行動／可攜電腦的離線使用。

Coda 把這些歸納為「constant data availability（持續資料可用性）」：讓使用者在共享檔案庫部分或完全不可達時，仍能完全依賴本地資源工作。它和 Bayou 一樣採**樂觀（optimistic）**策略——允許分割或離線時更新，賭衝突很少且事後可修。

架構：Venus 與 Vice

• Vice：跑在檔案 server 上，就是我們說的 replica manager。
• Venus：跑在客戶端電腦，是 front end 與 replica manager 的混合體——它對本地行程隱藏服務細節（front end 角色），又管理本地檔案快取（replica manager 角色）。

VSG 與 AVSG

• VSG（volume storage group）：持有某 volume 副本的全部 server 集合。
• AVSG（available VSG）：客戶端當下能存取的 VSG 子集，會隨 server 可達性變動。

正常運作時，Coda 像 AFS：從 AVSG 任一 server 取得快取副本，用 callback promise 通知變更。檔案 close 時，修改過的副本會平行廣播給 AVSG 的所有 server。斷線運作則定義為 AVSG 為空時。

生活妙喻

出差前先把檔案載到筆電

把 Coda 想成「出差前的離線準備」

你要出差到收訊很差的地方，出發前先把工作會用到的檔案載到筆電快取：

• VSG 就像公司機房裡所有存了這份檔案的伺服器；
• AVSG 是你「現在連得上」的那幾台。出差路上可能一台都連不上（AVSG 為空）——這就是斷線運作。
• 因為連不上 server，你只能靠筆電快取工作。所以出發前要把需要的檔案都載好，否則出差途中需要一個沒快取的檔案就卡住了（cache miss 會讓計算暫停）。

Coda 讓你把重要檔案標成 sticky（黏住），保證一直留在快取裡；還提供工具記錄你的檔案使用習慣，預測離線時會用到什麼。

回來之後要「對帳」

出差回來、重新連上網路，就進入重整（reintegration）：把你離線期間改過的檔案同步回 server。若期間別人也改了同一檔案，就可能偵測到衝突。

Coda 的設計哲學：server 上的副本比客戶端快取更可靠。所以衝突時優先採信 server，你的快取版本被暫存到一個叫 covolume 的地方等你處理。

實用超能力

用 CVV 偵測衝突

Coda version vector（CVV）

Coda 的樂觀複製靠每份檔案附帶一個 CVV——一個向量時間戳，VSG 裡每個 server 一格，每格估計該 server 上這版檔案被修改的次數。

判斷規則（$v_1, v_2$ 為兩個 CVV）：

• 若某站的 CVV $\geq$ 其他所有站的對應 CVV（即 $v_1 \geq v_2$），則無衝突：較舊的副本可自動更新到新版。
• 若既非 $v_1 \geq v_2$ 也非 $v_2 \geq v_1$，則有衝突：兩邊各有對方沒有的更新。Coda 一般不自動解決，把檔案標為 inoperable 並通知擁有者手動處理。

flowchart TD
  A[比較兩份 CVV] --> B{一方是否大於等於另一方}
  B -->|是| C[無衝突 舊副本自動更新成新版]
  B -->|否 兩者互不包含| D[有衝突 標為 inoperable 通知擁有者手動解決]

例子（VSG = S1, S2, S3）

初始三站都是 $[1,1,1]$。網路故障下：

• C1 只能存取 S1、S2，更新後 S1、S2 變 $[2,2,1]$，S3 不變。
• C2 只能存取 S3，更新兩次後 S3 變 $[1,1,3]$。
• 修復後比較：$[2,2,1]$ 與 $[1,1,3]$ 互不包含 → 衝突，需手動處理。

若 C2 沒改 F（S3 仍 $[1,1,1]$），則 $[2,2,1] \geq [1,1,1]$ → 無衝突，S3 自動更新。

與 Bayou 的差別

• Coda 偵測衝突不看資料語意（只比 CVV），能抓write-write 衝突但抓不到 read-write 衝突；
• 它對解衝突只提供有限的系統支援，多半交給人工處理（目錄是特例，可自動合併）。

深度探秘

從單一操作升級到交易序列

從「單一操作」到「交易」

前面討論的都是客戶端一次只請求單一操作。但交易是一連串操作，要滿足 ACID。複製交易系統一樣可以用複製來提升可用性與效能。

正確性目標：one-copy serializability

從客戶端角度，複製物件上的交易應該和非複製版本看起來一樣。非複製系統靠**序列等價（serially equivalent）**的交錯，讓交易彷彿一次一個地執行。

複製版本要達到的目標：客戶端在複製物件上的交易效果，要等同於它們一次一個地作用在單一物件集合上。這個性質叫 one-copy serializability（單副本序列化）。

注意區分：one-copy serializability 把客戶端操作聚合成交易來看；sequential consistency 則不把操作聚合成交易。兩者相似但不同。

每個 RM 自己做並行控制與恢復

• 每個 RM 對自己的物件做並行控制與恢復；本節假設用兩階段鎖定（two-phase locking）。
• 恢復較複雜：當一個失效的 RM 復原時，它要用其他 RM 的資訊把物件還原成當前值，把不可用期間發生的所有變更補上。

生活妙喻

多本帳本要像一本在記帳

把 one-copy serializability 想成「多本帳本假裝是一本」

一家公司在多個分點各放一本帳本（複製），但對客戶承諾：帳目效果要像只有一本總帳、交易一筆一筆依序記。

• 即使實際上有好幾本帳本同時在記，最後算出來的結果不能和「單一總帳依序記帳」有任何差異。
• 這就是 one-copy serializability：多份副本，但對外表現得像一份、且交易序列化。

read-one/write-all：最簡單的記帳規矩

為了達成這個承諾，最簡單的規矩是：

• 讀帳：問任何一本帳本就好（read-one）。
• 記帳（寫）：必須在每一本帳本都記上（write-all）。

這樣一來：

• 兩筆寫操作會在所有帳本上要求互相衝突的鎖（誰先記誰後記就排好了）；
• 一讀一寫會在某一本帳本上要求衝突的鎖。

只要在每本帳本上用兩階段鎖定，這些鎖的衝突就能保證交易序列化——也就是 one-copy serializability。

實用超能力

架構選擇與兩階段提交的巢狀化

架構上的幾個選擇

• 誰收請求：front end 可群播給整組 RM，或送給單一 RM（本節假設送給單一 RM）。
  • primary copy：所有 front end 都跟一個 primary RM 溝通，由它更新 backup。
  • 或允許跟任一 RM 溝通，但 RM 之間協調更複雜。
• 幾個 RM 才算完成：read-one/write-all 中讀只要一個、寫要全部；quorum 方案則減少寫的數量但增加讀的數量。
• 何時轉發更新：lazy（懶散）——交易 commit 後才轉發；eager（急切）——交易 commit 前就轉發給所有必要 RM。
  • lazy 常用於 primary copy（由單一 primary 序列化）；但若不同交易可能在不同 RM 存取同物件，為正確序列化就只能用 eager。

flowchart TD
  C[協調者 coordinator] -->|canCommit| W1[worker 兼 RM]
  W1 -->|轉發 canCommit| RG1[同組其他 RM]
  C -->|canCommit| W2[worker 兼 RM]
  W2 -->|轉發 canCommit| RG2[同組其他 RM]

兩階段提交變成「兩層巢狀」

當 coordinator 或 worker 本身是 RM 時，它得再跟「交易期間它轉發過請求的其他 RM」協調。於是 2PC 變成兩層巢狀的 2PC：

• 第一階段：coordinator 送 canCommit? 給 workers，workers 再轉發給其他 RM、收齊回覆才回 coordinator。
• 第二階段：coordinator 送 doCommit／doAbort，同樣往下傳到各組 RM。

read-one/write-all 達成 one-copy serializability

• 每個 write 在所有 RM 設寫鎖；每個 read 在單一 RM 設讀鎖。
• 任兩個 write 在所有 RM 要衝突鎖；一讀一寫在單一 RM 要衝突鎖 → 達成 one-copy serializability。

深度探秘

讓部分 RM 可以暫時缺席

read-one/write-all 不夠實際

簡單的 read-one/write-all 有個致命缺點：write 要寫所有 RM，但只要有一個 RM 當機或通訊失敗，寫操作就做不下去了。現實中 RM 暫時不可用很常見。

available copies：寫「可用的」就好

available copies（可用副本） 方案放寬規則：

• read：客戶端的讀請求可由任一可用 RM 執行；
• write：客戶端的更新請求必須由所有當下可用且持有副本的 RM 執行（不是全部，是可用的全部）。

「可用的 RM 成員」概念，就類似 Coda 的 AVSG（available volume storage group）。正常情況下，請求由運作中的 RM 接收處理。

這樣即使少數 RM 缺席，服務照樣能進行。但這也帶來新的正確性挑戰：當 RM 當機或復原穿插在交易之間時，可能讓不同交易看到不一致的 RM 集合。

生活妙喻

分店輪流休息的連鎖店

把 available copies 想成「分店會輪休的連鎖店」

回到連鎖帳本的比喻，但這次承認分店有時會臨時關門：

• 查帳（read）：找任何一家有開的分店問就好。
• 記帳（write）：在所有目前有開的分店都記上（關門的那家先跳過，等它開門再補）。

這比「必須每家都記」實際多了——一家裝修就停業未免太脆弱。

但「誰有開」會變，要小心對帳

問題來了：分店開開關關的時機，可能讓兩筆交易各自以為「某家有開、某家沒開」，結果記出對不起來的帳。

例如：交易 T 在 X 分店讀了 A、又在 M、P 寫了 B 然後提交，期間 X 才關門；同時交易 U 在 N 讀了 B、在 Y 寫了 A 提交，期間 N 才關門。若兩者都成立，帳就矛盾了。

解法是提交前先做「本地驗證（local validation）」，確認自己看到的開關門狀態在提交時仍然成立，否則不准提交。

實用超能力

本地驗證與網路分割的應對

本地驗證（local validation）

交易提交前，先檢查它存取過的物件之 RM 有沒有發生失效或復原。

• 以上面例子，T 提交前要確認 N 仍不可用、且 X、M、P 仍可用。若成立，T 才能提交。
• 這隱含「X 在 T 驗證後、U 驗證前才失效」，於是 U 的驗證在 T 之後，而 U 會因為 N 已失效而驗證失敗。
• 驗證時若觀察到某 RM 失效，會嘗試聯絡它確認它還沒復原；「RM 自存取後未失效」這部分則可併入兩階段提交。

重要前提：available copies 演算法不能用在「運作中的 RM 彼此無法通訊」的環境——也就是它本身不處理網路分割。

網路分割帶來的根本挑戰

網路分割把一組 RM 切成多個子群，子群之間無法通訊（如圖：收到 deposit 的 RM 無法把它傳給收到 withdraw 的 RM）。

flowchart TD
  subgraph 分割左側
    A[RM 收到 deposit]
  end
  subgraph 分割右側
    B[RM 收到 withdraw]
  end
  A -. 無法通訊 .- B

設計假設分割終將修復，所以分割期間執行的請求不能在修復後造成不一致。Davidson 等人把方法分兩類：

available copies with validation（樂觀）

每個分割內各自跑 available copies；分割修復後，對可能衝突的交易做驗證，若違反 one-copy serializability 就**中止（abort）其中一個——有時還要在現實世界做補償（如處理透支帳戶）。可用 version vector（如 Coda 的 CVV）驗證 write-write 衝突，或用先行圖（precedence graph）**找循環來偵測不一致。

深度探秘

用投票規則保證只有一邊能動

quorum consensus 的核心想法

要防止不同分割的交易產生不一致，一個辦法是規定：操作只能在其中一個分割內進行。但分割間無法通訊，每個子群得自己判斷是否有權執行操作。

quorum（法定人數） 就是一個「大到有權執行操作」的 RM 子群。例如以「多數」為準，擁有多數成員的子群就構成 quorum——因為不可能有兩個子群都是多數。

Gifford 的加權投票方案

Gifford 給每個實體副本分配若干票（votes）。每個操作要先湊到足夠的票：

• 讀操作要先取得 read quorum $R$ 票；
• 寫操作要先取得 write quorum $W$ 票。

$R$ 和 $W$ 的設定須滿足兩條規則：

$$W > \frac{\text{總票數}}{2}$$

$$R + W > \text{總票數}$$

這兩條保證：任何「讀 quorum 與寫 quorum」或「兩個寫 quorum」必定有共同副本（重疊）。因此分割時不可能在不同分割對同一副本做衝突操作。

生活妙喻

董事會表決需要的票數

把 quorum 想成「董事會表決」

公司董事會有好幾位董事，每人手上票數不同（加權投票）。要通過決議需要湊到一定票數：

• 寫（改公司章程） 是大事，必須拿到過半票數（$W >$ 總票數一半）——這保證不可能有兩派同時各自過半通過互相矛盾的章程。
• 讀（查章程） 也要湊到 $R$ 票，且規定 $R + W >$ 總票數——這保證你查到的人裡，至少有一位參與過最新那次修章（讀寫必定重疊），所以你不會查到舊版本。

重疊就是關鍵

為什麼一定要重疊？想像兩個分割（公司開會分成兩個會議室）：

• 若兩個寫 quorum 不重疊，兩邊可能各自通過矛盾的修章 → 災難。
• 規則保證任兩個寫 quorum必有共同成員，那位成員不可能同時參加兩邊矛盾的決議，於是分割時最多只有一邊能寫。

讀也一樣：每個讀 quorum 一定和每個寫 quorum 重疊，所以讀 quorum 裡至少含一份最新副本，讀操作就套用到那份最新的。

實用超能力

版本號、可設定性與虛擬分割

用版本號找最新副本

quorum 方案中，更新可能只在子群完成，其他成員會持有過期副本。用**版本號（version number）**分辨：

• 讀：湊到 $R$ 票的副本集合（不必都最新），因為與每個寫 quorum 重疊，必含至少一份最新副本，讀就套用到那份。
• 寫：湊到 $W$ 票的最新副本；若最新副本不夠，先把過期副本換成最新，再套用更新、遞增版本號。其餘可用 RM 則在背景更新。
• 用兩階段讀寫鎖定做並行控制，read quorum 設讀鎖、write quorum 設寫鎖，靠重疊保證 one-copy serializability。

可設定性：調 R 與 W 換效能／可靠度

例如高讀寫比的系統目錄，可給遠端 RM 配票讓讀很容易（如 $R=1$），寫則需更多票（如 $W=3$）。

Dynamo 的 quorum

Dynamo 用類似 quorum：$R + W > N$（$N$ 為副本節點數），常見配置 $[N,R,W]=[3,2,2]$。但分割時 Gifford 只能在多數派運作，Dynamo 用 sloppy quorum——把副本暫存到替代節點，待原節點恢復再轉交。

虛擬分割（virtual partition）

結合 quorum consensus 與 available copies：

flowchart TD
  VP[虛擬分割 含一組 RM] --> Q{是否同時擁有 read quorum 與 write quorum}
  Q -->|是| AC[在此虛擬分割內使用 available copies 讀只需一份副本]
  Q -->|否| NEW[嘗試建立新的虛擬分割以取得 quorum]

• 若虛擬分割同時有讀、寫 quorum，就在其內用 available copies（讀只需單一副本，可選最近的，效能好）。
• 交易進行中若 RM 失效、虛擬分割改變，則中止交易，確保所有存活交易以相同順序看到失效與復原，達成 one-copy serializability。
• 成員偵測到無法聯絡其他成員時，會嘗試建立新的虛擬分割以重新取得讀寫 quorum。