深度探秘

一個查詢背後的三件大事

你打字之前，Google 早就忙了好幾週

當你搜尋 distributed systems book，0.2 秒內就拿到結果。但這背後其實有三個獨立的工作，而且大部分在你打字之前就完成了：

• 爬取 (Crawling)：派出一隻叫 Googlebot 的軟體機器人，沿著網頁上的超連結一頁一頁讀過去。讀到一頁就把上面的連結收集起來，再排程去爬那些連結——這種一路往下挖的方式叫做 deep searching（深度搜尋），幾乎能觸及全網。
• 索引 (Indexing)：光是把網頁抓回來還不夠。索引會建立一份 inverted index（倒排索引），把『一個字 → 它在哪些文件的哪些位置出現』整理成一張可快速查詢的表。
• 排名 (Ranking)：找得到還不夠，要先給你最重要的。PageRank 演算法負責決定哪一頁該排在前面。

重點：找一個關鍵字其實不難，難的是在數十億頁中，又快又準地挑出最該給你看的那幾頁。

flowchart TD
  A[Googlebot 爬取網頁] --> B[建立倒排索引]
  B --> C[PageRank 排名]
  C --> D[回傳排序後的結果清單]

生活妙喻

倒排索引就像一本書最後面的索引頁

想像一本超級厚的書

一本書最後面通常有「索引」：你想找『遞迴』，翻到索引就看到「遞迴 …… 頁 88、142、201」。你不必從第一頁翻到最後一頁。倒排索引就是這個概念，但規模是整個網際網路。

那 PageRank 像什麼？ 像學術論文的「被引用次數」。一篇論文被很多人引用，代表它重要。一個網頁被很多頁連結，也代表它重要——而且連結來源本身越重要，這個連結就越有份量。來自 bbc.co.uk 的連結，比來自某個人個人首頁的連結更有說服力。

所以 Google 不是問『這頁有沒有這些字』，而是問『這頁有這些字，而且全網有多看重它？』

實用超能力

從數十億頁縮到幾頁的真實過程

跟著 distributed systems book 走一遍

1. 拆字查索引：分別查 distributed、systems、book 三個字，各自得到一大堆出現它們的頁面。
2. 取交集：找出同時包含三個字的頁面，例如 amazon.com、www.cdk5.net。光這步就能把候選從數十億頁砍到大概幾萬頁。
3. 排名：對這幾萬頁算重要性——
   • 被很多『重要網站』連結的頁面（如 amazon 的書頁）往上排；
   • 三個字靠得很近的頁面往上排（代表真的在講這個主題）；
   • 字出現在頁面開頭或用大寫/大字體的頁面往上排。
4. 回傳：最重要的排最上面，於是你第一眼就看到最相關的結果。

Caffeine 與 Percolator：早期爬取是『每幾週批次跑一次』，但突發新聞、股價需要更即時。2010 年 Google 用 Caffeine 改成持續性的增量更新，底層靠 Percolator 對大型資料集做增量更新，讓搜尋結果更新鮮。

深度探秘

撐起 Google 的四根柱子

設計之前，先搞懂『要解什麼問題』

所有後面的技術選擇，都是為了滿足這四個需求。先記住它們，後面每個服務都會回頭呼應：

• 可擴展性 (Scalability)：Google 是所謂的 ULS（Ultra-Large Scale，超大規模） 系統。它把擴展拆成三個維度：
  1. 更多資料（網路一直變大、圖書館數位化）；
  2. 更多查詢（用的人越來越多，到 2010 年底每月超過 880 億次查詢）；
  3. 更好結果（搜尋品質是用戶會不會繼續用的關鍵）。
• 可靠性 (Reliability)：要 24/7 不中斷。Google Apps 對付費客戶提供 99.9% 的服務水準協議 (SLA)。
• 效能 (Performance)：目標是 0.2 秒回傳搜尋結果。效能是端到端 (end-to-end) 的，網路、儲存、運算要一起到位。
• 開放性 (Openness)：基礎設施要可擴充，方便不斷長出新的 Web 應用。

flowchart TD
  S[可擴展性] --> A[更多資料]
  S --> B[更多查詢]
  S --> C[更好結果]

生活妙喻

經營一家永不打烊的超大連鎖餐廳

把 Google 想成一家全球連鎖餐廳

一個重要洞見：可靠性必須在『設備經常會壞』的前提下達成。Google 用便宜 PC，每天約有 20 台因軟體問題要重開機。它不是去買貴一點、更不容易壞的設備，而是設計成『壞了也沒關係，系統自己撐住』。

與其追求『永不故障的零件』，不如打造『會故障也不怕的系統』。

實用超能力

用『信封背面的計算』感受規模

為什麼非得用分散式不可？

Jeff Dean 在演講裡做過一個經典的『back of the envelope（信封背面）』估算：

• 假設全網約 200 億頁，每頁 20 KB，總量約 400 TB。
• 一台電腦若以 30 MB/s 讀取，要爬完這些資料得花超過 4 個月。
• 但 1000 台機器並行，只要不到 3 小時。

這就是為什麼爬取、索引、排名、搜尋全部都得是高度分散式的解法——單機根本不可能在合理時間內完成。

真實世界的提醒：2009 年 9 月 1 日 Gmail 曾中斷 100 分鐘，原因是例行維護期間伺服器過載引發連鎖反應。即使設計再好，可靠性仍是持續的挑戰。

搜尋的一個小秘密：搜尋的失敗其實『天生容易遮蔽』——因為使用者根本無從得知是不是所有相關結果都回傳了。這讓搜尋在可靠性上比金融交易這類應用稍微寬鬆一點。

深度探秘

為什麼選一堆便宜 PC，而不是一台超級電腦？

核心哲學：買『每塊錢的效能』

Google 的實體基礎設施有一個很反直覺的決定：用大量的 commodity PC（一般市售規格的便宜電腦），而不是少數昂貴的高階伺服器。每台大約 1,000 美元，配備約 2 TB 硬碟、16 GB DRAM，跑精簡版的 Linux。

採購邏輯是 best performance per dollar（每塊錢的最佳效能），而不是絕對效能。

為什麼這樣划算？ 看故障數據就懂了：

• 軟體故障最常見：每天約 20 台因軟體問題要重開機（而且重開是純手動的！）。
• 硬體故障只有軟體的約 1/10：每年約 2–3% 的 PC 因硬體壞掉，其中 95% 是硬碟或 DRAM 出問題。

既然絕大多數故障來自軟體，花大錢買更可靠的硬體並不值得——這就反過來證明了選便宜 PC 是對的。

生活妙喻

螞蟻雄兵 vs 一頭大象

一頭大象，還是一群螞蟻？

你要搬一座山的資料。你可以雇『一頭超強大象』（昂貴的超級電腦），也可以派『一百萬隻螞蟻』（便宜 PC 大軍）。

• 大象很貴，而且牠一倒下，整個工作就停了。
• 螞蟻便宜又好補充，死掉幾隻完全不影響整群繼續搬。

Google 選了螞蟻雄兵。為了管理這群螞蟻，牠們被組織成清楚的層次：

flowchart TD
  PC[便宜 PC] --> Rack[機架 40 到 80 台 PC]
  Rack --> Cluster[叢集 30 個以上機架]
  Cluster --> DC[資料中心 散布全球]

為了容錯，每個機架接到兩個高頻寬交換器，每個交換器又有冗餘的對外連線。

實用超能力

算一算 Google 到底能存多少

用乘法感受『天文數字』

讓我們順著層次算下去（這正是『信封背面估算』的精神）：

• 1 台 PC ≈ 2 TB
• 1 個機架（80 台）≈ $80 \times 2 = 160$ TB
• 1 個叢集（30 機架）≈ $30 \times 160 = 4800$ TB ≈ 4.8 PB
• 假設約 200 個叢集 ≈ $200 \times 4.8 = 960$ PB ≈ 接近 1 EB（exabyte，$10^{18}$ bytes）

而這還被認為是保守估計。

這給我們什麼超能力？

1. 容錯的本錢：因為機器多、又有層次化的冗餘（雙交換器、複製服務），少數機器掛掉時，系統可以把工作轉移走，使用者完全無感。
2. 管理的單位：以叢集為單位來決定『某個服務放在哪、要複製幾份』，讓大規模管理變得有章法。
3. 就近部署：資料中心散布全球，讓服務更靠近使用者，降低延遲。

深度探秘

上中下三層，中間那層最關鍵

Google 系統的三明治結構

Google 的整體系統架構可以看成三層：

flowchart TD
  A[Google 應用與服務 搜尋 Gmail 地圖] --> B[Google 基礎設施 中介軟體 middleware]
  B --> C[Google 平台 便宜 PC 機架 叢集]

• 最上層：大家熟悉的應用與服務（搜尋、Gmail、Docs、Maps…）。
• 最下層：上一節講的實體平台（便宜 PC、機架、叢集）。
• 中間層（最關鍵）：共用的分散式基礎設施（中介軟體 middleware），提供搜尋與雲端共用的通訊、儲存、運算服務。

這個中間層封裝了處理可擴展性、可靠性、效能的關鍵策略。它的價值在於：

1. 重用：新應用不必重造輪子，直接用底層服務就能快速 bootstrap。
2. 一致性：強制大家用共同的策略與設計原則，讓越長越大的程式碼庫仍保持整體連貫。

生活妙喻

共用基礎設施像城市的水電網路

為什麼開新店不用自己挖水井？

想像你要在一座城市裡開咖啡店。你不必自己挖水井、自己發電、自己鋪路——城市早就提供了水、電、道路這些共用基礎設施。你只要接上去就能營業。

Google 的中間層就是這座城市的水電網路：

• 想做新應用（開新店）？直接接上 GFS（儲存）、Bigtable（資料庫）、MapReduce（運算）就好。
• 大家都接同一套水電，整座城市（程式碼庫）才不會亂成一團。

而這座城市的『市政原則』有三條，貫穿整個 Google：

實用超能力

簡單原則怎麼落實到日常設計

把『簡單』變成可操作的習慣

『簡單』聽起來很抽象，但 Google 把它落實成具體做法：

• API 設計：Bloch 指出 API 應該『盡可能小，但不能更小』。少一個多餘的方法，未來就少一個維護與相容包袱。
• 效能估算：Jeff Dean 強調工程師要能心算基本操作的成本——存取記憶體、讀硬碟、發一個網路封包、鎖/解鎖一個 mutex 各要多久。有了這些數字，就能做『信封背面』的設計評估，提早發現瓶頸。
• 測試文化：口號是『if it ain't broke, you are not trying hard enough（沒測壞，就是你還不夠拚）』。配合大量 logging（日誌）與 tracing（追蹤），故障一發生就能快速定位根因。

這給你的超能力：當你看到後面 GFS、Chubby、Bigtable 的設計時，會發現它們反覆選擇『簡單但夠用』而非『功能齊全但複雜』——例如 Bigtable 不支援完整關聯式運算、Chubby 只做整檔讀寫。這不是偷懶，而是刻意的設計紀律。

深度探秘

讓不同機器講同一種『打包語言』

問題：機器之間怎麼傳遞結構化資料？

當一台機器要把『一本書的資料』傳給另一台，它得先把記憶體裡的物件攤平成一串位元組（這叫 serialization 序列化），對方再還原。XML 也能做，但它太『萬用』導致又肥又慢。

Google 因此打造了 protocol buffers：一種語言中立、平台中立的序列化格式，號稱比 XML 小 3–10 倍、快 10–100 倍。

你先用一個簡單語言寫 .proto 檔描述訊息格式：

message Book {
  required string title = 1;
  repeated string author = 2;
  enum Status { IN_PRESS = 0; PUBLISHED = 1; OUT_OF_PRINT = 2; }
  message BookStats {
    required int32 sales = 1;
    optional int32 citations = 2;
    optional Status bookstatus = 3 [default = PUBLISHED];
  }
  optional BookStats statistics = 3;
  repeated string keyword = 4;
}

每個欄位有名字、型別、唯一編號（=1、=2…，這個編號是二進位編碼裡的 tag）。欄位標籤有三種：

• required：一定要有；
• optional：可有可無；
• repeated：可出現 0 到多次（像動態陣列）。

接著用 protoc 工具編譯 .proto，自動產生程式碼（如 getTitle()、setTitle()、hasTitle()、clearTitle()），讓你方便地存取訊息。

生活妙喻

宅配紙箱 vs 印滿說明的禮盒

寄包裹要用哪種箱子？

你要寄一份禮物。有兩種包裝：

• XML：像一個印滿說明文字的精美禮盒，盒子上寫著『這是一個盒子，裡面第一格放卡片，第二格放…』。自我描述、誰拿到都看得懂（互通性好），但盒子本身又大又重。
• Protocol buffers：像一個樸素的宅配紙箱，箱子上只有編號標籤（=1、=2）。收件人手上有同一份『編號對照表』(.proto)，所以一看編號就知道內容。又小又快，但前提是雙方都得有對照表。

書中提醒：拿 protobuf 跟 XML 比其實不太公平——Google 是相對封閉的系統，不需要 XML 那種跨開放系統的互通性與自我描述能力，所以可以選又小又快的方案。

實用超能力

用 protobuf 撐起一進一出的 RPC

從『描述資料』到『遠端呼叫』

protocol buffers 最常見的用途是定義 RPC（遠端程序呼叫）。只要多寫一段語法：

service SearchService {
  rpc Search (RequestType) returns (ResponseType);
}

protoc 會產生一個抽象介面與一個 stub（樁），讓你能型別安全地呼叫遠端服務。

兩個關鍵設計決策（都呼應簡單原則）：

1. 一進一出：每個遠端操作只能吃一個參數、回傳一個結果（兩者都是 protobuf 訊息）。這跟一般 RPC/RMI 可以有任意多參數很不一樣。
   • 為什麼？ 為了可演進性。把複雜度推到『資料』裡，介面本身保持穩定不易變——這跟 REST 哲學（少量操作、聚焦於操作資源）相呼應。
2. 與 RPC 協定無關 (protocol-agnostic)：stub 只假設存在 RpcChannel 與 RpcController 兩個抽象介面。你想用 HTTP、TCP 或第三方 RPC 實作都行，自己提供實作即可。

flowchart TD
  A[.proto 檔 定義 service 與 message] --> B[protoc 編譯]
  B --> C[產生 stub 與抽象介面]
  C --> D[呼叫端透過 stub 發出 RPC]
  D --> E[底層可換成 HTTP 或 TCP]

深度探秘

當 RPC 不夠用的時候

一對多的即時廣播，RPC 撐不住

protocol buffers 的 RPC 很適合『一對一、請求-回應』。但有些場景完全不適合 RPC，例如 Google 廣告系統：

• 廣告伺服器遍布全球，任何一台都得在幾分之一秒內知道某則廣告現在能不能投放。
• 如果用 RPC：發送端得知道所有廣告伺服器的身分、對每一台發 RPC、佔用大量連線與緩衝區、還要耗掉廣域網路頻寬。根本不可行。

所以 Google 另外提供一個 publish-subscribe（發布訂閱） 系統來補強（不是取代）protobuf。它的關鍵特性是時間與空間解耦 (time and space uncoupling)：

• 空間解耦：發送者不需知道接收者是誰、在哪。
• 時間解耦：發送與接收不必同時在線。

這也天然支援訂閱者的故障與復原。順帶一提，這個發布訂閱系統底層仍然用 protobuf 來通訊。

flowchart TD
  P[發布者 publisher 根節點] --> B1[broker]
  P --> B2[broker]
  B1 --> S1[訂閱者]
  B1 --> S2[訂閱者]
  B2 --> S3[訂閱者]

生活妙喻

廣播電台 vs 一通通打電話

你會打電話通知每個聽眾嗎？

假設你要通知全國上百萬人『颱風來了』：

• RPC 方式：你拿著電話簿，一個一個打電話。你得知道每個人的號碼、一通通打、佔線又耗時。一百萬人？打到天荒地老。
• 發布訂閱方式：你只要在廣播電台講一次。誰想聽就訂閱那個頻道。你不必知道聽眾是誰、有幾個、在哪裡——這就是空間解耦。聽眾晚一點打開收音機也能收到重播——這就是時間解耦。

Google 採用 topic-based（主題式） 發布訂閱：每個頻道 (channel) 對應一個主題 (topic)。

為了補救表達力的不足，Google 允許加強版訂閱：每個事件含 header、一組 keywords 和一個不透明的 payload；訂閱時除了選頻道，還能用 filter（依關鍵字過濾） 挑出頻道內的子集。

實用超能力

用 broker 樹做到又可靠又即時

一棵棵『主題樹』如何運作

Google 的發布訂閱系統實作成一個 broker overlay（中介者疊加網路），長得像一組樹：

• 每棵樹代表一個主題。
• 樹的根 (root) 是發布者，葉節點 (leaf) 是訂閱者。
• filter 會被盡量往樹的後方（靠近根）推，這樣不必要的流量就能及早被擋掉，省頻寬。

和第 6 章一般的發布訂閱不同，Google 特別強調『可靠』又『即時』：

1. 可靠 (reliability)：每個邏輯頻道維護兩棵獨立的樹（冗餘樹）。一棵出問題，另一棵頂上。
2. 即時 (timely delivery)：用 QoS（服務品質）管理 控制訊息流量——採用簡單的速率限制 (rate control)，以『每使用者／每主題』為基礎，管理記憶體、CPU 與訊息/位元組速率的預期用量。

樹一開始用最短路徑演算法建構，並持續重新評估調整。

重點：頻道適合『相對靜態、粗粒度、高吞吐』的資料流（至少 1 Mbps）。若某主題流量不到這個量，會被併進別的主題，但仍可用關鍵字辨識出來。

深度探秘

不是萬用檔案系統，而是『為 Google 量身訂做』

GFS 的需求與一般檔案系統不一樣

Google File System (GFS) 也是分散式檔案系統，但它和 NFS、AFS 那種『萬用』檔案系統的目標完全不同。Google 觀察自己的使用模式後，提出三個特別的需求：

1. 要能在會壞的便宜硬體上可靠運行：設計一開始就假設『元件（含軟硬體）必然會壞』。
2. 檔案少但超大、存取以順序為主：約一百萬個檔案、平均 100 MB，有些到 GB 級。存取以大檔案的順序讀與附加寫 (append) 為主，小型隨機讀寫很少。高度並行的 append 特別常見。
3. 要滿足整體需求：可擴展、可靠、高效能、開放。效能上優化高且持續的讀取吞吐量，優先於延遲。

flowchart TD
  C[GFS client] -->|問 metadata| M[GFS master 單一]
  M -->|回傳 chunk 位置| C
  C -->|直接讀寫資料| CS1[chunkserver 複本1]
  C --> CS2[chunkserver 複本2]
  C --> CS3[chunkserver 複本3]

生活妙喻

圖書館的大書庫與一位總館長

把 GFS 想成一座巨型書庫

• 大 chunk（64 MB）：GFS 把檔案切成固定 64 MB 的大區塊，比一般檔案系統大得多。就像書庫用大箱子收書，而不是一本一本散放。
  • 好處：適合大檔案、順序讀寫超有效率、需要的『目錄資訊 (metadata)』也少很多（若用 64 KB 的小區塊，metadata 會暴增 1000 倍）。
  • 代價：對『只想讀小檔案一小段』的隨機存取非常沒效率。
• 單一 master（總館長）：每個 GFS 叢集只有一位 master，負責管理 metadata（命名空間、存取控制、檔案→chunk 的對應、複本位置）。
  • 好處：館長有全域視野，能做最佳的放置決策；實作也簡單，開發快。
  • 代價：單點故障。怎麼補救？ 把 master 的操作日誌 (operation log) 複製到多台機器，掛了能迅速重建。
• chunkserver（書架管理員）+ 三份複本：每個 chunk 預設複製到三台獨立的 chunkserver，這樣壞一台也不怕（NFS/AFS 並不做這種更新複製）。

最妙的設計：控制流與資料流分離。 client 先問 master『這段資料在哪個 chunk、哪些複本上？』(控制流)，拿到後把 master 晾在一邊，直接找 chunkserver 讀大量資料（資料流）。一次問完，之後 64 MB 想讀多快就讀多快。

實用超能力

放寬的一致性：write 與 record append 的差別

不追求完美一致，而是『夠用就好』

因為 chunk 有複本，更新時就得維持一致。GFS 用一種放寬的一致性 (relaxed consistency)：當有 mutation（write/append/delete）時，master 把 chunk lease（租約） 給其中一個複本當 primary（主），由它決定並行更新的順序，再讓 secondary（從）依同樣順序套用。

這其實是被動複製 (passive replication) 的變形：一般被動複製中，資料和控制都走 primary；GFS 則讓 client 把資料直接送給所有複本，但控制請求才送 primary，由 primary 排序。這讓大量資料傳輸能獨立於控制流去優化。

write 與 record append 的關鍵差別：

這是領域特定的取捨：GFS 明知道放寬一致性會讓資料可能重複，但因為 Google 的應用能容忍這種語意，就換取了更高的效能。

其他務實設計：GFS 幾乎不做快取（順序串流讀，快取幫助不大，還能省去 cache 一致性協定的麻煩）；伺服器端則靠 Linux 的 buffer cache。所有 GFS 伺服器都維護大量診斷日誌，持續監控、出事時用來找根因。

深度探秘

一個服務，四種面貌

Chubby：把『鎖』和『檔案』合而為一

Chubby 是 Google 基礎設施的核心協調服務，被 GFS、Bigtable 等服務倚賴。它身兼四種能力：

1. 粗粒度分散式鎖 (coarse-grained distributed locks)：在大規模非同步環境中同步各方活動。
2. 小檔案儲存：可靠地存放少量資料（補足 GFS 不擅長的小檔案）。
3. 協助選主 (primary election)。
4. 命名服務 (name service)。

一個服務做四件事，看似違反『簡單原則』？其實它的核心只有一個：解決分散式共識 (distributed consensus)，其餘三種面貌都從這個核心衍生而來。

介面像檔案系統（採 Plan 9『一切皆檔案』的觀點）：路徑形如 /ls/chubby_cell/directory_name/.../file_name。實體（entity）同時具備鎖與檔案的功能——可純粹拿來鎖、可存小資料、也可把小資料（當 metadata）和鎖綁在一起。

操作刻意精簡：Open/Close/Delete、整檔讀寫的 GetContentsAndStat/SetContents（整檔讀寫且原子，刻意不鼓勵存大檔），以及鎖操作 Acquire/TryAcquire/Release。

生活妙喻

公司公佈欄上的『會議室預約單』

用一張預約單，順便公告誰是負責人

想像公司公佈欄上有一張會議室預約單。它同時做了兩件事：

• 鎖：誰先簽上去，誰就鎖定這間會議室（拿到鎖）。
• 檔案：簽名旁邊還能寫一行字（存小資料）。

這正是 Chubby 選主 (primary election) 的做法：

1. 所有候選者都去搶同一個鎖；
2. 只有一個會成功——它就是 primary，其餘變 secondary；
3. 勝出者把自己的身分寫進那個檔案，其他人讀檔案就知道誰是主。

這完美示範了『鎖＋檔案合一』的妙用，也說明選主可以建在共識服務之上，作為環狀演算法或 bully 演算法的替代方案。

Chubby 的鎖是 advisory（建議性）的：系統不強制擋住沒拿鎖的人，大家得自律地走『先拿鎖再存取』的流程。為什麼不用更強硬的 mandatory（強制性）鎖？因為 advisory 鎖更有彈性、更有韌性。

快取一致性：Chubby 的小檔案常被重複讀，所以 client 快取很有效（和 GFS 相反）。它用一個簡單的協定：要 mutation 時，先等所有相關快取失效才放行（失效通知搭便車附在 KeepAlive 回覆上），快取資料從不直接更新。結果是確定性 (deterministic) 的語意——這也是為什麼 Google 拿 Chubby 當命名服務（比 DNS 那種會不一致的更可靠）。

實用超能力

Paxos：在混亂中達成共識的三步驟

Chubby 的心臟：Paxos 共識演算法

一個 Chubby cell（實例） 通常有五個複本，其中一個是 master。複本資料庫的一致性靠 Paxos 共識演算法維持。Paxos 是為非同步系統設計的共識協定，假設：複本可任意速度運作也可能失敗復原、有持久儲存、訊息可能遺失/重排/重複但不會損毀。

關鍵特性：Paxos 保證正確性 (safety) 但不保證終止 (liveness)。也就是說它不會給出錯誤答案，但在純非同步下不保證一定談成（這與 Fischer 等人的不可能性結果一致）。只要多數複本穩定運作夠久，最終就能達成共識。

三步驟（用 Google 的術語）：

sequenceDiagram
  participant C as 協調者 coordinator
  participant R as 複本們 replicas
  C->>R: 步驟1 Propose 帶序號
  R-->>C: Promise 承諾不理更舊的協調者
  C->>R: 步驟2 Accept 帶選定的值
  R-->>C: Acknowledgement
  C->>R: 步驟3 Commit 通知達成共識

• 步驟 1（選協調者）：想當協調者的複本挑一個更高的唯一序號廣播 Propose。序號唯一性靠：每個複本有唯一 id $i_r$（$0$ 到 $n-1$），挑最小的、比看過的都大、且 $s \bmod n = i_r$ 的序號（例如 5 個複本、id=3、最後看到 20，就挑 23）。收到多數 Promise 就當選，這群多數叫 quorum（法定人數）。
• 步驟 2（求共識）：協調者選一個值送 Accept。若有 Promise 帶回舊的值，就必須沿用其中一個；否則可自選。等多數 Acknowledge。
• 步驟 3（達成共識）：多數確認後即達成，廣播 Commit。

為什麼安全？ 靠 quorum：任兩個多數至少有一個共同複本，且網路分裂時最多只有一個分區能湊出多數。實務上 Chubby 要對『一連串的值』達成共識（log 的每一格），稱為 Multi-Paxos，可長期固定一個協調者以省掉重複的步驟 1。

深度探秘

不是關聯式資料庫，而是超大表格

為什麼不直接用關聯式資料庫？

GFS 很會存『大平檔』，但很多 Google 應用（搜尋、Maps、Analytics、個人化搜尋）需要結構化、可依內容索引的資料。Google Analytics 例如把原始點擊存一張表（約 200 TB），分析後摘要存另一張（約 20 TB）。

大可用關聯式資料庫（支援 union、selection、join 等完整運算）。但在分散式環境要做到好效能與可擴展性非常難，而且 Google 的應用根本不需要這麼完整的功能。於是 Google 打造了 Bigtable：保留『表格』模型，但介面簡單得多，專為高效存取超大結構化資料集設計。

Bigtable 是一個三維表格，每個 cell 由三個鍵索引：

• Row（列）：row key 是任意字串（最多 64 KB）。表格依 row key 字典序排序。
• Column（欄）：欄被組織成 column family（欄族），用 family:qualifier 命名。通常欄族少、但每個欄族內的欄（qualifier）可以很多。
• Timestamp（時間戳）：同一個 cell 可有多個版本，依時間戳索引，反向排序（最新的先出）。可設定自動垃圾回收舊版本。

生活妙喻

一本可以查歷史版本的超級電話簿

三維表格像什麼？

想像一本超級電話簿：

• 列 (row)＝每一個人（用 row key 找）；
• 欄族:欄 (family:qualifier)＝資訊分類，例如『聯絡方式:手機』『聯絡方式:市話』『地址:住家』；
• 時間戳 (timestamp)＝這筆資料的歷史版本，最新的擺最前面。

字典序排序帶來的超能力：locality（區域性）。 Bigtable 依 row key 字典序排，連續的列會落在同一個 tablet（小表） 上。所以 row key 怎麼取很關鍵：

把網域反轉當 row key，相關資料就會聚在一起——這個小技巧大幅提升資料區域性。注意：取 key 完全由程式設計師負責，要懂這個排序特性才能用得好。

所有對單一列的存取都是原子的（呼應 GFS、Chubby 的設計）。但 Bigtable 不支援跨列的全域交易——又一次『簡單但夠用』的取捨。

實用超能力

站在 GFS 與 Chubby 的肩膀上

Bigtable 的架構：和 GFS 像得驚人

Bigtable 把表格切成 tablet（約 100–200 MB）。一個 Bigtable 實例叫 cluster，架構有三部分：client 端 library、單一 master server、大量 tablet server。

它借用了 GFS 的兩個關鍵決策：

1. 單一 master（全域視野、好實作）；
2. 控制與資料流分離（master 只做控制：監控 tablet server、分派 tablet、負載平衡、垃圾回收；資料存取完全走 tablet server）。

Bigtable 甚至比 GFS 更進一步：master 不參與『tablet → 實際資料』的對應，所以 client 完全不必跟 master 通訊，大幅減輕 master 負擔。

資料怎麼存？ 用 SSTable（有序、不可變的 key→value 對應檔，存在 GFS）。寫入先進持久 log（也在 GFS），再寫到記憶體裡的 memtable；讀取則合併 SSTable 與 memtable 的視圖。tablet 的定位用一個受 B+-tree 啟發的三層階層索引：

flowchart TD
  A[Chubby 檔案 指向根] --> B[Root tablet]
  B --> C[其他 metadata tablets]
  C --> D[使用者資料 tablets]

最妙的：用 Chubby 監控 tablet server。 每台 tablet server 上線時在 Chubby 目錄建一個檔並取得獨佔鎖。鎖在＝健在。

• server 端：發現鎖丟失就停止服務；檔案還在就試著重拿鎖，檔案消失就自我了斷。
• master 端：定期查鎖狀態；若鎖丟失或 server 沒回應，master 嘗試搶鎖，搶到代表 Chubby 活著、問題在 server，於是刪掉該檔（逼 server 自盡）並把它的 tablet 重新分派。

這是重用一個可靠服務（Chubby）來達成監控，而不是另造一個監控服務——再次呼應簡單原則。

深度探秘

把『平行運算』濃縮成兩個函式

一個驚人的觀察

有了海量資料後，怎麼算？Google 觀察到許多平行運算其實長得一樣：

1. 把輸入資料切成小塊；
2. 對每塊做初步處理，產生中間結果；
3. 把中間結果合併成最終輸出。

既然模式相同，那就把『會變的部分』抽成兩個函式，其餘『不會變的部分』（平行化、排程、容錯、負載平衡…）由框架統一處理。這就是 MapReduce：

• map：吃一組 key-value 對，吐出一組中間 key-value 對。
• （中間步驟）：框架把中間結果依 key 排序、分組。
• reduce：吃同一個 key 的那組值，產生最終結果（可能是一個值或一串值）。

flowchart TD
  A[輸入資料] --> B[切成多塊]
  B --> C[多個 map 產生中間 key-value]
  C --> D[依 key 排序分組]
  D --> E[多個 reduce 彙整]
  E --> F[輸出結果]

威力有多大？ 2003 年 Google 用 MapReduce 重寫主要索引系統，C++ 行數從 3,800 降到 700。而且改善底層 MapReduce，所有應用立刻受惠。

生活妙喻

全班一起數一大箱選票

怎麼又快又準地數完一大箱選票？

一箱幾百萬張選票，一個人數要數到天荒地老。聰明的做法：

1. 分堆 (map)：把選票分給很多同學，每人拿一疊。每位同學翻看自己那疊，每看到一張票就喊出『候選人 A，+1』『候選人 B，+1』——這就是 map 吐出 <候選人, 1> 的中間結果。
2. 歸類 (中間步驟)：把所有『候選人 A』的紙條收到一起、『候選人 B』的收到一起——這就是依 key 排序分組。
3. 加總 (reduce)：每個候選人指派一個同學，把屬於他的那堆 1 全部加起來——這就是 reduce。

這正是經典的 word count（字數統計） 範例：map 對每個出現的字 emit <word, 1>，reduce 把同一個字的所有 1 加總。

你只要負責『怎麼分堆、怎麼加總』，至於『派給誰、誰偷懶、誰中途離場』全由 MapReduce 框架搞定。

實用超能力

框架如何容錯、又如何對付『拖油瓶』

執行細節與容錯的真功夫

執行流程：輸入切成 M 塊（每塊 16–64 MB，不大於一個 GFS chunk），中間結果的鍵空間用 partition function 切成 R 塊（預設 hash(key) mod R）。框架啟動一批 worker，其中一個當 master，其餘做 map 或 reduce。典型規模：M=200,000、R=5,000、2,000 台 worker。

資料區域性 (locality)：輸入存在 GFS 且複製三份，master 盡量把 map worker 安排在存有該資料的機器上，避免耗網路頻寬——把運算搬到資料旁邊。

容錯：master 定期 ping 每個 worker，沒回應就當它掛了：

• 若是 map 任務：不管做完沒，都標記為 idle 重排（因為結果存在本機磁碟，機器掛了就拿不到）。
• 若是 reduce 任務：只有還在進行中才重排（已完成的結果寫到全域複製的檔案系統，仍可取得）。

只要 map/reduce 對輸入是確定性 (deterministic) 的，即使有故障，MapReduce 也保證產出和循序執行相同的結果（關鍵在於輸出是原子寫入的）。

對付 straggler（落後者/拖油瓶）：有些 worker 因硬碟出毛病等原因跑很慢。當程式接近完成時，master 會為剩下的進行中任務啟動備援 worker，誰先完成就算誰的。這對縮短完成時間影響顯著。

MapReduce 常與 Bigtable 搭配：從 Bigtable 讀入、輸出又寫回 Bigtable（如 Google Analytics、Google Maps 的圖磚生成）。

深度探秘

比 MapReduce 更高一層的語言

Sawzall：讓平行分析更好寫

MapReduce 已經很強，但寫起來仍有些繁瑣。Sawzall 是一個直譯式程式語言，目標是進一步簡化在超大資料集上的平行分析。實際成效驚人：Sawzall 程式常比等效的 MapReduce 程式小 10 到 20 倍。

Sawzall 不是另起爐灶，而是站在現有基礎設施上：用 MapReduce 來建立與管理底層平行執行、用 GFS 存資料、用 protocol buffers 當共同的紀錄格式。

它假設平行運算遵循一個模式：輸入是一堆記錄 (records)，由 filter（過濾器） 平行處理每一筆並 emit 結果，再由 aggregator（彙整器） 把 emit 的資料彙整成最終結果。

對應到 MapReduce：filter 跑在 map 階段，aggregator 對應 reduce 階段。

flowchart TD
  A[原始資料 records] --> F1[filter]
  A --> F2[filter]
  A --> F3[filter]
  F1 --> AG[aggregator 彙整]
  F2 --> AG
  F3 --> AG
  AG --> R[結果]

生活妙喻

工廠的『分檢員』與『統計員』

Sawzall 像一條自動化產線

想像一條輸送帶送來大量產品（records）：

• filter（分檢員）：站在輸送帶旁，各自獨立檢查每一件產品，把符合條件的資料挑出來丟到籃子裡（emit）。很多分檢員可以同時、任意順序工作。
• aggregator（統計員）：把籃子裡的資料彙整出總結，例如加總（sum）、收集全部（collection）、算累積機率分布（quantile）、估最常見的值（top）。

Sawzall 對這兩種角色有兩個關鍵假設：

1. filter 必須可交換 (commutative)：分檢員的工作順序不影響結果（誰先檢查都一樣）。
2. aggregator 必須可結合 (associative)：彙整時的括號分組不影響結果（先合誰、後合誰都行）。

為什麼這兩個假設這麼重要？因為唯有可交換、可結合，才能放心地平行化——可以任意拆分、任意順序、任意分組去執行，最後結果都一樣。這就是平行運算能成立的數學前提。

一個迷你 Sawzall 範例（計數＋加總一串浮點數）：

count: table sum of int;
total: table sum of float;
x: float = input;
emit count <- 1;
emit total <- x;

table sum of ... 宣告了兩個『加總型』aggregator，emit 把值送進去——程式短得不可思議。

實用超能力

回顧整章：真正的設計功力在哪

把整章的智慧串起來

這一整章其實在傳一個核心訊息：好的分散式系統設計，不在於用了多炫的技術，而在於『理解領域、提煉核心原則、然後一致地套用』。

反覆出現的設計模式（你應該已經很熟了）：

MapReduce/Sawzall 的共同哲學：先鼓勵一種特定的運算風格，再提供共用基礎設施讓這種風格能高效實作。代價是框架較具規範性，未必適合所有問題領域——這也引發了資料管理社群關於『這類抽象是否足夠通用』的有趣辯論。

整本書的收尾啟示：Google 的成功，源自把『simplicity、every millisecond counts、嚴格測試與 logging/tracing』這套原則從上到下、始終如一地貫徹。技術會變，但這套設計紀律才是真正可帶走的功夫。