Chubby: How to Design a Distributed Locking Service?

簡介#

Chubby 是 Google 內部的分散式鎖服務（Distributed Lock Service），同時也可以儲存小型檔案。其內部實作為一個鍵值儲存（Key/Value Store），並在每個儲存的物件上提供鎖定機制。Chubby 被廣泛應用於 Google 內部的各種系統中，為 GFS 和 BigTable 等系統提供儲存與協調服務。Apache ZooKeeper 是 Chubby 的開源替代方案。

總結來說，Chubby 是一個集中式服務，提供開發者友善的介面（取得/釋放鎖定、建立/讀取/刪除小型檔案）。應用程式只需加入少量程式碼，無需大幅修改應用邏輯即可整合 Chubby。

設計目標#

設計一個高可用（Highly Available）且強一致性（Strongly Consistent）的服務，能夠儲存小型物件並在這些物件上提供鎖定機制。

使用案例#

Chubby 最初是為了提供可靠的鎖定服務而開發的。隨著時間推移，它衍生出了一些有趣的用途。以下是 Chubby 在實務中的主要使用案例：

領導者選舉（Leader/Master Election）#

任何鎖定服務都可以被視為一種共識服務（Consensus Service），因為它將達成共識的問題轉化為分配鎖定。基本上，一組分散式應用程式競爭取得鎖定，最先取得鎖定的就獲得資源。同樣地，一個應用程式可以運行多個副本（Replica），並希望從中選出一個作為領導者。Chubby 可用於在一組副本中進行領導者選舉，例如 GFS 和 BigTable 的領導者/主節點。

命名服務（Naming Service，類似 DNS）#

由於 DNS 基於時間的快取特性，很難快速更新 DNS，這意味著在最新的 DNS 對應生效之前通常會有延遲。因此，Chubby 在 Google 內部已取代 DNS，成為發現伺服器的主要方式。

儲存小型物件（Storage）#

Chubby 提供類似 Unix 的介面，可靠地儲存不常更新的小型檔案（補充 GFS 所提供的服務）。應用程式可以將這些檔案用於 DNS、設定檔等用途。GFS 和 BigTable 將其中繼資料（Metadata）儲存在 Chubby 中。部分服務使用 Chubby 儲存存取控制清單（ACL）檔案。

分散式鎖定機制（Distributed Locking Mechanism）#

Chubby 提供開發者友善的介面，用於粗粒度（Coarse-grained）的分散式鎖定（相對於細粒度鎖定），以同步分散式環境中的活動。應用程式只需加入少量程式碼，Chubby 服務就會處理所有鎖定管理，讓開發者可以專注於應用程式的業務邏輯。換言之，Chubby 為分散式環境提供了類似信號量（Semaphore）和互斥鎖（Mutex）的機制。

不適合使用 Chubby 的場景#

由於其設計選擇和預期用途，以下情況不應使用 Chubby：

需要大量儲存（Bulk Storage）
資料更新頻率高
鎖定頻繁取得/釋放
用途更接近發佈/訂閱（Publish/Subscribe）模型

背景#

Chubby 並非一項研究成果，也不宣稱引入任何新演算法。相反地，Chubby 描述的是 Google 內部的特定設計與實作，目的是為客戶端提供同步活動並就環境基本資訊達成共識的方式。

Chubby 與 Paxos#

Paxos 在 Chubby 內部扮演著重要角色。熟悉分散式運算（Distributed Computing）的讀者知道，讓分散式系統中的所有節點就某件事達成共識（例如在對等節點中選舉主節點），本質上就是一種分散式共識問題（Distributed Consensus Problem）。使用非同步通訊（Asynchronous Communication）的分散式共識已由 Paxos 協定解決，而 Chubby 底層正是使用 Paxos 來管理系統在任何時間點的狀態。

高層架構#

常見術語#

在深入 Chubby 的架構之前，先了解一些常見術語。

Chubby Cell#

Chubby Cell 基本上指的是一個 Chubby 叢集（Cluster）。大多數 Chubby Cell 限制在單一資料中心或機房內，但也可能存在副本相隔數千公里的 Chubby Cell。一個 Chubby Cell 有兩個主要元件：伺服器（Server）和客戶端（Client），透過遠端程序呼叫（RPC）進行通訊。

Chubby 伺服器#

一個 Chubby Cell 由一小組伺服器（通常 5 個）組成，稱為副本（Replica）
使用 Paxos，其中一個伺服器被選為主節點（Master），處理所有客戶端請求。若主節點故障，另一個副本會成為新的主節點
每個副本維護一個小型資料庫來儲存檔案/目錄/鎖定
主節點直接寫入自己的本地資料庫，並非同步地同步到所有副本。這確保了資料可靠性，即使主節點故障，客戶端也能獲得順暢的體驗
為了容錯（Fault Tolerance），Chubby 副本被放置在不同的機架（Rack）上

Chubby 客戶端程式庫#

客戶端應用程式使用 Chubby 程式庫（Library），透過 RPC 與 Chubby Cell 中的副本通訊。

Chubby API#

Chubby 匯出一個類似 POSIX 但更簡化的檔案系統介面。它由檔案和目錄組成嚴格的樹狀結構，名稱元件以斜線分隔。

檔案格式：/ls/chubby_cell/directory_name/.../file_name

其中 /ls 指的是鎖定服務（Lock Service），表示這是 Chubby 系統的一部分；chubby_cell 是特定 Chubby 系統實例的名稱（Chubby 使用「cell」一詞來表示系統的一個實例）。後面跟著一系列目錄名稱，最終以 file_name 結尾。

特殊名稱 /ls/local 會被解析為相對於呼叫端應用程式最近的 Cell。

Chubby 最初被設計為鎖定服務，因此其中的每個實體都是一個鎖定。但後來，其建立者意識到將少量資料與每個實體關聯是有用的。因此，Chubby 中的每個實體都可以用於鎖定或儲存少量資料，或兩者兼具，也就是帶有鎖定的小型檔案儲存。

Chubby API 可分為以下幾組：

一般操作（General）#

Open() - 開啟指定的檔案或目錄並回傳一個控制代碼（Handle）
Close() - 關閉一個開啟的控制代碼
Poison() - 允許客戶端取消其他執行緒發出的所有 Chubby 呼叫，而不需擔心釋放正在被存取的記憶體
Delete() - 刪除檔案或目錄

檔案操作（File）#

GetContentsAndStat() - 以原子方式（Atomically）回傳整個檔案內容和相關的中繼資料。這種讀取整個檔案的方式是為了阻止建立大型檔案，因為這不是 Chubby 的預期用途
GetStat() - 僅回傳中繼資料
ReadDir() - 回傳目錄的內容，即所有子項目的名稱和中繼資料
SetContents() - 以原子方式寫入整個檔案內容
SetACL() - 寫入新的存取控制清單資訊

鎖定操作（Locking）#

Acquire() - 取得檔案的鎖定
TryAcquire() - 嘗試取得檔案的鎖定；是 Acquire 的非阻塞變體
Release() - 釋放鎖定

序列器操作（Sequencer）#

GetSequencer() - 取得鎖定的序列器（Sequencer）。序列器是鎖定的字串表示
SetSequencer() - 將序列器與控制代碼關聯
CheckSequencer() - 檢查序列器是否有效

Chubby 不支援追加（Append）、搜尋（Seek）、在目錄之間移動檔案，或建立符號連結（Symbolic Link）及硬連結（Hard Link）等操作。檔案只能被完整讀取或完整寫入/覆寫。這使得 Chubby 只適合儲存非常小的檔案。

設計考量#

在進一步探討 Chubby 的細節和運作之前，了解某些設計決策背後的邏輯是很重要的。這些經驗可以應用於類似性質的其他問題。

為什麼 Chubby 要建構為服務？#

首先了解為什麼要建構一個服務，而不是只提供 Paxos 分散式共識的客戶端程式庫。鎖定服務相比客戶端程式庫有一些明顯的優勢：

開發更容易：有時候高可用性在開發早期並未被規劃。系統從低負載的原型開始，失去可用性保證。隨著服務成熟並獲得更多客戶端，可用性變得重要；此時才會在設計中加入複製和主節點選舉。雖然可以使用提供分散式共識的程式庫來實現，但鎖定伺服器使得維護現有的程式結構和通訊模式更加容易。例如，選舉領導者只需添加幾行程式碼，這比讓現有伺服器參與共識協定要容易得多，特別是在過渡期間必須保持相容性的情況下
鎖定介面對開發者友善：程式設計師通常熟悉鎖定。在分散式系統中直接使用鎖定服務，比在本地管理 Paxos 協定狀態要容易得多，例如 Acquire()、TryAcquire()、Release()
提供法定人數與副本管理：分散式共識演算法需要法定人數（Quorum）來做出決定，因此使用多個副本以實現高可用性。可以將鎖定服務視為一種通用選舉機制，允許客戶端應用程式在其自身成員不足多數時仍能正確做出決定。若沒有服務的支持，每個應用程式都需要擁有並管理自己的伺服器法定人數
廣播功能：客戶端和複製服務的副本可能希望知道服務的主節點何時更換；這需要事件通知機制。如果系統中有一個中央服務，這種機制就很容易建構

為什麼使用粗粒度鎖定？#

Chubby 鎖定的使用預期不是細粒度的（即只持有很短時間，如幾秒或更少）。例如，選舉領導者並不是頻繁發生的事件。以下是 Chubby 決定只支持粗粒度鎖定的主要原因：

鎖定伺服器負載較低：粗粒度鎖定對伺服器施加的負載遠低於細粒度鎖定，因為鎖定取得頻率遠低於客戶端的交易頻率
能承受伺服器故障：由於粗粒度鎖定很少被取得，鎖定伺服器的暫時不可用不會顯著延遲客戶端。使用細粒度鎖定時，即使鎖定伺服器的短暫不可用也會導致許多客戶端停滯
需要的鎖定伺服器更少：粗粒度鎖定允許較少數量的鎖定伺服器以相對較低的可用性充分服務許多客戶端

為什麼使用建議性鎖定（Advisory Lock）？#

Chubby 的鎖定是建議性（Advisory）的，這意味著是否遵守鎖定取決於應用程式。Chubby 不會讓未持有鎖定的客戶端無法存取被鎖定的物件。這更像是記錄保存，允許鎖定請求者發現鎖定已被持有。持有特定鎖定既不是存取檔案的必要條件，也不會阻止其他人存取。

另一種鎖定類型是強制性鎖定（Mandatory Lock），使未持有鎖定的客戶端無法存取物件。Chubby 不使用強制性鎖定的原因如下：

對其他服務實作的資源強制執行強制性鎖定，需要對這些服務進行更大幅度的修改
強制性鎖定會阻止使用者為了除錯或管理目的存取被鎖定的檔案。如果必須存取某個檔案，就需要關閉或重新啟動整個應用程式以打破強制性鎖定
通常，良好的開發實務是撰寫斷言（如 assert("Lock X is held")），因此強制性鎖定帶來的好處很有限

為什麼 Chubby 需要儲存功能？#

Chubby 的儲存功能很重要，因為客戶端應用程式可能需要與他人分享 Chubby 的結果。例如，應用程式需要儲存資訊以：

宣傳其選出的主節點（領導者選舉使用案例）
將別名解析為絕對位址（命名服務使用案例）
在資料重新分區後公告架構

不需要單獨的服務來分享結果，減少了客戶端所依賴的伺服器數量。Chubby 的儲存需求非常簡單，即儲存少量資料（KB 等級）並支援有限的操作（建立/刪除）。

為什麼 Chubby 匯出類似 Unix 的檔案系統介面？#

Chubby 匯出一個類似 Unix 但更簡化的檔案系統介面，由檔案和目錄組成嚴格的樹狀結構，名稱元件以斜線分隔。

檔案格式：/ls/cell/remainder-path

Chubby 的命名結構之所以類似檔案系統，主要原因是讓它既可以透過自身的專用 API 供應用程式使用，也可以透過其他檔案系統（如 Google File System）使用的介面來存取。這大幅減少了撰寫基本瀏覽和命名空間操作工具所需的工作量，也減少了教育一般 Chubby 使用者的需求。然而，這些檔案只能執行非常有限的操作，例如建立（Create）、刪除（Delete）等。

高可用性與可靠性#

正如 CAP 定理所證明的，沒有應用程式可以同時具備高可用性、強一致性和高效能。由於 Chubby 預期使用案例的特性，Chubby 在效能方面做出妥協，以換取可用性和一致性。

運作方式#

服務初始化#

Chubby 在初始化時執行以下步驟：

使用 Paxos 從 Chubby 副本中選出一個主節點
當前主節點資訊被持久化到儲存中，所有副本都知道主節點是誰

客戶端初始化#

Chubby 客戶端在初始化時執行以下步驟：

客戶端聯繫 DNS 以獲取已列出的 Chubby 副本清單
客戶端透過遠端程序呼叫（RPC）直接呼叫任一 Chubby 伺服器。如果該副本不是主節點，它會回傳當前主節點的位址
一旦找到主節點，客戶端就與它維持一個會話（Session），並將所有請求發送給它，直到主節點表示自己不再是主節點或停止回應

使用 Chubby 進行領導者選舉的範例#

以下是一個應用程式使用 Chubby 從多個實例中選出單一主節點的範例：

選舉開始後，所有候選人嘗試取得與選舉相關的 Chubby 檔案上的鎖定
最先取得鎖定的成為主節點
主節點將其身份寫入檔案，以便其他程序知道當前的主節點是誰

flowchart TD
    Start["所有候選人(Candidates)同時啟動"]
    S1["1. 所有候選人嘗試取得<br/>同一個 Chubby 鎖定檔案(Lock File)"]
    Race{"競爭鎖定<br/>(Lock Contention)"}
    Winner["2. 最先取得鎖定者<br/>成為主節點(Leader)"]
    Loser["其他候選人<br/>取得鎖定失敗"]
    S3["3. 主節點將身份(Identity)<br/>寫入鎖定檔案"]
    Discover["其他程序讀取檔案<br/>發現當前主節點"]

    Start --> S1 --> Race
    Race -->|取得鎖定| Winner
    Race -->|未取得鎖定| Loser
    Winner --> S3 --> Discover
    Loser --> Discover

領導者選舉的虛擬碼#

以下虛擬碼展示了如何只需添加幾行程式碼，就能輕鬆地將領導者選舉邏輯加入現有應用程式：

/* 在 Chubby 中手動建立這些檔案一次。
   通常至少需要 3-5 個以滿足最低法定人數要求。 */
lock_file_paths = {
  "ls/cell1/foo",
  "ls/cell2/foo",
  "ls/cell3/foo",
}

Main() {
  // 初始化 Chubby 客戶端程式庫。
  chubbyLeader = newChubbyLeader(lock_file_paths)

  // 建立客戶端與 Chubby 服務的連線。
  chubbyLeader.Start()

  // 等待成為領導者。
  chubbyLeader.Wait()

  // 成為領導者
  Log("Is Leader: " + chubbyLeader.isLeader())

  While(chubbyLeader.renewLeader()) {
    // 執行工作
  }
  // 不再是領導者。
}

檔案、目錄與控制代碼#

Chubby 檔案系統介面基本上是一個檔案和目錄的樹狀結構，每個目錄包含一個子檔案和子目錄的清單。每個檔案或目錄稱為一個節點（Node）。

節點（Node）#

任何節點都可以作為建議性讀取器/寫入器鎖定（Advisory Reader/Writer Lock）
節點可以是暫時性（Ephemeral）或永久性（Permanent）的
暫時性檔案用作臨時檔案，並作為向他人表示客戶端存活的指標
暫時性檔案在沒有客戶端開啟它們時也會被刪除
暫時性目錄在為空時也會被刪除
任何節點都可以被明確刪除

中繼資料（Metadata）#

每個節點的中繼資料包括存取控制清單（ACL）、四個單調遞增的 64 位元數字，以及一個校驗和（Checksum）。

**存取控制清單（ACL）**用於控制節點的讀取、寫入和 ACL 名稱修改：

節點在建立時繼承其父目錄的 ACL 名稱
ACL 本身是位於 ACL 目錄中的檔案，該目錄是 Cell 本地命名空間的已知部分
使用者透過 RPC 系統內建的機制進行身份驗證

單調遞增的 64 位元數字允許客戶端輕鬆偵測變更：

實例號碼（Instance Number）：大於任何先前同名節點的實例號碼
內容世代號碼（Content Generation Number，僅限檔案）：每次檔案內容被寫入時遞增
鎖定世代號碼（Lock Generation Number）：當節點的鎖定從空閒轉為持有時遞增
ACL 世代號碼（ACL Generation Number）：當節點的 ACL 名稱被寫入時遞增

校驗和（Checksum）：Chubby 公開一個 64 位元的檔案內容校驗和，讓客戶端可以判斷檔案是否不同。

控制代碼（Handle）#

客戶端開啟節點以取得控制代碼（類似於 Unix 檔案描述符）。控制代碼包括：

檢查碼（Check Digits）：防止客戶端建立或猜測控制代碼，因此完整的存取控制檢查僅在建立控制代碼時執行
序列號碼（Sequence Number）：讓主節點能夠判斷控制代碼是由自己還是由先前的主節點產生的
模式資訊（Mode Information，在開啟時提供）：讓主節點能夠在舊的控制代碼被呈現給新重啟的領導者時重建其狀態

鎖定、序列器與鎖定延遲#

鎖定（Lock）#

每個 Chubby 節點都可以作為讀取器-寫入器鎖定，以下列兩種方式之一運作：

獨佔模式（Exclusive）：一個客戶端可以以獨佔（寫入）模式持有鎖定
共享模式（Shared）：任意數量的客戶端可以以共享（讀取）模式持有鎖定

序列器（Sequencer）#

在分散式系統中，訊息亂序接收是一個問題；Chubby 使用序列號碼來解決這個問題。在取得檔案的鎖定後，客戶端可以立即請求一個「序列器」（Sequencer），這是一個描述鎖定狀態的不透明位元組字串：

序列器 = 鎖定名稱 + 鎖定模式（獨佔或共享）+ 鎖定世代號碼

應用程式的主伺服器可以產生序列器，並將其與任何內部指令一起發送到其他伺服器。接收來自主節點指令的應用程式伺服器可以向 Chubby 檢查序列器是否仍然有效，以及它是否不屬於過時的主節點（以處理「腦裂」（Split Brain）場景）。

鎖定延遲（Lock-delay）#

對於不支援序列器的檔案伺服器，Chubby 提供鎖定延遲期間（Lock-delay Period）來防範訊息延遲和伺服器重啟。

如果客戶端以正常方式釋放鎖定，它會立即可供其他客戶端取得
然而，如果鎖定因為持有者故障或無法存取而變為空閒，鎖定伺服器會在一段稱為鎖定延遲的期間內阻止其他客戶端取得鎖定
客戶端可以指定任何鎖定延遲，最多到某個上限，預設為一分鐘。此限制可防止故障客戶端使鎖定（及相關資源）在任意長的時間內不可用
雖然不完美，鎖定延遲可以保護未修改的伺服器和客戶端免受訊息延遲和重啟所造成的日常問題

會話與事件#

什麼是 Chubby 會話（Session）？#

Chubby 會話是 Chubby Cell 與 Chubby 客戶端之間的關係：

它存在於某個時間區間內，透過稱為 KeepAlive 的定期握手來維持
客戶端的控制代碼、鎖定和快取資料僅在其會話有效時保持有效

會話協定#

客戶端在首次聯繫 Chubby Cell 的主節點時請求新的會話
如果客戶端明確結束會話或會話已閒置，會話就會終止。如果一分鐘內沒有開啟的控制代碼和呼叫，會話被視為閒置
每個會話都有一個關聯的租約（Lease），這是一個時間區間，在此期間主節點保證不會單方面終止會話。此區間的結束稱為「會話租約逾時」（Session Lease Timeout）
主節點在以下三種情況下延長「會話租約逾時」：
- 在會話建立時
- 當主節點故障轉移（Failover）發生時
- 當主節點回應客戶端的 KeepAlive RPC 時

什麼是 KeepAlive？#

KeepAlive 基本上是客戶端與 Chubby Cell 維持持續會話的方式。以下是回應 KeepAlive 的基本步驟：

收到 KeepAlive 後，主節點通常會阻塞 RPC（不允許其返回），直到客戶端的先前租約區間接近到期
主節點稍後允許 RPC 返回給客戶端，從而通知客戶端新的租約逾時
主節點可以將逾時延長任意時間。預設延長為 12 秒，但過載的主節點可能使用更高的值以減少它必須處理的 KeepAlive 呼叫數量
客戶端在收到先前的回覆後立即發起新的 KeepAlive。因此，客戶端確保幾乎總是有一個 KeepAlive 呼叫在主節點上被阻塞

sequenceDiagram
    participant C as 客戶端(Client)
    participant M as 主節點(Master)

    C->>M: 1. 發送 KeepAlive 請求
    Note over M: 2. 阻塞 RPC<br/>等待先前租約接近到期

    M->>C: 3. 回覆 KeepAlive<br/>通知新的租約逾時<br/>（預設延長 12 秒）
    Note over C: 4. 更新本地租約

    C->>M: 4. 立即發送新的 KeepAlive
    Note over M: 阻塞 RPC，等待租約接近到期

    M->>C: 回覆 KeepAlive，再次延長租約
    Note over C: 更新本地租約

    C->>M: 立即發送新的 KeepAlive
    Note over C,M: 持續循環...<br/>確保幾乎總有一個 KeepAlive 在主節點上被阻塞

會話優化#

事件附載（Piggybacking Events）：KeepAlive 回覆用於將事件和快取失效通知傳輸回客戶端
本地租約（Local Lease）：客戶端維護一個本地租約逾時，這是主節點租約逾時的保守近似值
危險狀態（Jeopardy）：如果客戶端的本地租約逾時到期，它就不確定主節點是否已終止其會話。客戶端會清空並停用其快取，此時我們說其會話處於「危險狀態」
寬限期（Grace Period）：當會話處於危險狀態時，客戶端會等待一段額外的時間，稱為寬限期（預設 45 秒）。如果客戶端和主節點能在客戶端寬限期結束之前成功交換 KeepAlive，客戶端就會重新啟用其快取。否則，客戶端會假設會話已過期

故障轉移（Failover）#

故障轉移場景發生在主節點故障或失去成員資格時。以下是主節點故障轉移時發生的事情摘要：

故障的主節點丟棄其記憶體中關於會話、控制代碼和鎖定的狀態
會話租約計時器停止。這意味著在主節點故障轉移期間不會有租約過期，等同於租約延長
如果主節點選舉很快發生，客戶端會在本地租約過期之前聯繫並繼續使用新的主節點
如果選舉延遲，客戶端會清空快取（進入危險狀態），並在嘗試尋找新主節點的同時等待「寬限期」（45 秒）

故障轉移詳細流程#

客戶端與主節點有租約 M1（及本地租約 C1），並有待處理的 KeepAlive 請求
主節點開始租約 M2 並回覆 KeepAlive 請求
客戶端將本地租約延長到 C2 並發出新的 KeepAlive 呼叫。主節點在回覆下一個 KeepAlive 之前故障。因此無法分配新租約。客戶端的 C2 租約過期，客戶端程式庫清空其快取並通知應用程式已進入危險狀態。寬限期在客戶端開始
最終，新的主節點被選出，並最初使用保守的近似值 M3 作為其前任可能為客戶端分配的會話租約。客戶端向新主節點發送 KeepAlive
客戶端對新主節點的第一個 KeepAlive 請求被拒絕，因為它的主節點紀元號碼（Epoch Number）不正確
客戶端使用另一個 KeepAlive 請求重試
重試的 KeepAlive 成功。客戶端將其租約延長到 C3，並可選擇通知應用程式其會話不再處於危險狀態（會話現在處於安全模式）
客戶端發出新的 KeepAlive 呼叫，從此正常協定開始運作
因為寬限期足夠長以涵蓋租約 C2 結束到租約 C3 開始之間的區間，客戶端只會感受到延遲。如果寬限期比該區間短，客戶端就會放棄會話並向應用程式回報故障

sequenceDiagram
    participant C as 客戶端(Client)
    participant M1 as 舊主節點(Old Master)
    participant M2 as 新主節點(New Master)

    Note over C,M1: 階段一：正常運作
    C->>M1: 1. 持有租約 M1，發送 KeepAlive
    M1->>C: 2. 開始租約 M2，回覆 KeepAlive

    Note over C,M1: 階段二：主節點故障
    C->>M1: 3. 延長本地租約至 C2，發送新 KeepAlive
    destroy M1
    Note over M1: 主節點故障！<br/>無法回覆 KeepAlive

    Note over C: C2 租約過期<br/>清空快取，進入危險狀態(Jeopardy)<br/>開始寬限期(Grace Period)

    Note over M2: 4. 副本選出新主節點<br/>使用保守租約 M3

    C->>M2: 5. 向新主節點發送 KeepAlive
    M2-->>C: 拒絕：紀元號碼(Epoch)不正確

    C->>M2: 6. 使用正確紀元號碼重試 KeepAlive
    M2->>C: 7. 回覆成功，延長租約至 C3

    Note over C: 離開危險狀態，會話恢復安全

    C->>M2: 8. 發送新 KeepAlive，恢復正常協定
    Note over C: 9. 若寬限期涵蓋 C2→C3 區間<br/>客戶端僅感受到延遲

主節點選舉與 Chubby 事件#

新選出的主節點初始化#

新選出的主節點按以下步驟進行：

選擇紀元號碼（Epoch Number）：首先選擇一個新的客戶端紀元號碼，以區分自己與先前的主節點。客戶端在每次呼叫時都需要提供紀元號碼。主節點會拒絕使用較舊紀元號碼的客戶端呼叫。這確保新的主節點不會回應發送給先前主節點的舊請求
回應主節點位置請求，但尚不回應與會話相關的操作
建構記憶體資料結構：建構資料庫中記錄的會話和鎖定的記憶體資料結構。會話租約被延長到先前主節點可能使用的最大值
允許客戶端執行 KeepAlive，但此時不允許其他與會話相關的操作
向每個會話發出故障轉移事件：這會導致客戶端清空快取（因為它們可能錯過了失效通知），並警告應用程式其他事件可能已丟失
等待：主節點等待每個會話確認故障轉移事件或讓其會話過期
允許所有操作繼續進行
接受客戶端的舊控制代碼：如果客戶端使用在故障轉移之前建立的控制代碼，主節點會重建控制代碼的記憶體表示並處理該呼叫
刪除暫時性檔案：在一段時間（一分鐘）之後，主節點會刪除沒有開啟檔案控制代碼的暫時性檔案。客戶端應在故障轉移後的這段時間內重新整理暫時性檔案的控制代碼

flowchart TD
    S1["1. 選擇新的紀元號碼(Epoch Number)<br/>區分新舊主節點"]
    S2["2. 回應主節點位置請求<br/>尚不處理會話操作"]
    S3["3. 從資料庫建構記憶體資料結構<br/>延長會話租約至最大值"]
    S4["4. 允許客戶端執行 KeepAlive<br/>其他會話操作仍不允許"]
    S5["5. 向每個會話發出故障轉移事件(Failover Event)<br/>客戶端清空快取"]
    S6["6. 等待所有會話確認故障轉移事件<br/>或讓過期會話終止"]
    S7["7. 允許所有操作繼續進行"]
    S8["8. 接受並重建客戶端的舊控制代碼(Handle)"]
    S9["9. 刪除無開啟控制代碼的暫時性檔案(Ephemeral Files)<br/>（等待一分鐘後）"]

    S1 --> S2 --> S3 --> S4 --> S5 --> S6 --> S7 --> S8 --> S9

Chubby 事件#

Chubby 支援簡單的事件機制，讓客戶端可以訂閱各種事件。事件透過 Chubby 程式庫的回呼（Callback）非同步地傳遞給客戶端。客戶端在建立控制代碼時訂閱一系列事件。以下是這些事件的範例：

檔案內容被修改
子節點被新增、移除或修改
Chubby 主節點發生故障轉移
控制代碼（及其鎖定）已變為無效
鎖定被取得
來自其他客戶端的衝突鎖定請求

此外，客戶端會向應用程式發送以下會話事件：

危險（Jeopardy）：當會話租約逾時且寬限期開始時
安全（Safe）：當會話已知在通訊問題中存活下來時
過期（Expired）：如果會話逾時

快取#

Chubby 快取#

在 Chubby 中，快取扮演著重要角色，因為讀取請求的數量遠超寫入請求。為了減少讀取流量，Chubby 客戶端在客戶端記憶體中以一致的、寫入穿透（Write-through）快取方式快取檔案內容、節點中繼資料和開啟控制代碼的資訊。由於這種快取機制，Chubby 必須維護檔案與快取之間，以及檔案不同副本之間的一致性。Chubby 客戶端透過租約機制維護其快取，並在租約過期時清空快取。

快取失效（Cache Invalidation）#

以下是當檔案資料或中繼資料被更改時，快取失效的協定：

主節點收到更改檔案內容或節點中繼資料的請求
主節點阻塞修改操作，並向所有快取了該資料的客戶端發送快取失效通知。為此，主節點必須維護每個客戶端快取內容的清單
為了效率，失效請求被附載在主節點的 KeepAlive 回覆中
客戶端收到失效信號後，清空快取，並在下一次 KeepAlive 呼叫中向主節點發送確認
收到所有活躍客戶端的確認後，主節點繼續執行修改操作。主節點更新其本地資料庫，並向副本發送更新請求
收到 Cell 中多數副本的確認後，主節點向發起寫入的客戶端發送確認

sequenceDiagram
    participant W as 客戶端(Writer)
    participant M as 主節點(Master)
    participant C1 as 客戶端A(Cached)
    participant C2 as 客戶端B(Cached)
    participant R as 副本(Replicas)

    W->>M: 1. 發送寫入請求(Write Request)
    M->>C1: 2. 發送快取失效通知(Invalidation)
    M->>C2: 2. 發送快取失效通知(Invalidation)
    Note over M: 阻塞寫入操作，等待確認

    C1->>C1: 3. 清除本地快取
    C1->>M: 3. 回傳確認(ACK)
    C2->>C2: 3. 清除本地快取
    C2->>M: 3. 回傳確認(ACK)

    Note over M: 4. 收到所有確認後執行寫入
    M->>M: 更新本地資料庫
    M->>R: 發送更新請求至副本
    R->>M: 多數副本確認

    M->>W: 5-6. 回傳寫入確認與新資料
    Note over C1,C2: 後續讀取將取得新版本

在主節點等待確認期間，其他客戶端是否可以讀取檔案？ 在主節點等待客戶端確認期間，檔案被視為「不可快取」（Uncachable）。這意味著客戶端仍然可以讀取檔案，但不會快取它。這種方式確保讀取操作始終不會有延遲，這很有用，因為讀取的數量遠超寫入。

客戶端是否可以快取鎖定？ Chubby 允許客戶端快取鎖定，這意味著客戶端可以持有鎖定比必要的時間更長，期望相同的客戶端可以再次使用。

客戶端是否可以快取開啟的控制代碼？ Chubby 允許客戶端快取開啟的控制代碼。這樣，如果客戶端嘗試開啟先前已開啟的檔案，只有第一次 open() 呼叫會到達主節點。

資料庫#

最初，Chubby 使用 Berkeley DB 的複製版本來儲存資料。後來，Chubby 團隊認為使用 Berkeley DB 使 Chubby 面臨更多風險，因此他們決定撰寫一個簡化的自訂資料庫，具有以下特點：

使用預寫日誌（Write-ahead Logging）和快照（Snapshotting）的簡單鍵值資料庫
僅支援原子操作（Atomic Operations），不支援通用交易（Transaction）
資料庫日誌使用 Paxos 在副本之間分發

備份（Backup）#

為了在故障時恢復，所有資料庫交易都儲存在交易日誌（預寫日誌）中。由於交易日誌可能隨時間變得非常大，每隔幾小時，每個 Chubby Cell 的主節點會將其資料庫的快照寫入不同建築物中的 GFS 伺服器。使用不同的建築物確保備份在建築物損壞時仍能存活，並且備份不會在系統中引入循環依賴（同一建築物中的 GFS Cell 可能依賴 Chubby Cell 來選舉其主節點）。

一旦取得快照，先前的交易日誌就會被刪除
因此，在任何時候，系統的完整狀態由最後一個快照加上交易日誌中的交易集合決定
備份資料庫用於災難恢復，以及初始化新替換副本的資料庫，而不會對其他副本產生負載

鏡像（Mirroring）#

鏡像是一種允許系統自動維護多個副本的技術：

Chubby 允許一組檔案從一個 Cell 鏡像到另一個 Cell
鏡像最常用於將設定檔複製到分佈在世界各地的各個運算叢集
由於檔案很小，鏡像速度很快
事件機制會在檔案被新增、刪除或修改時立即通知
通常，變更會在一秒之內反映在全球數十個鏡像中
無法存取的鏡像在連線恢復之前保持不變；然後透過比較校驗和來識別更新的檔案

Chubby 有一個特殊的「全域」Cell 子樹 /ls/global/master，它被鏡像到每個其他 Chubby Cell 的子樹 /ls/cell/replica。全域 Cell 是特殊的，因為其副本位於世界上相距甚遠的地方。全域 Cell 用於：

Chubby 自身的存取控制清單（ACL）
各種檔案，Chubby Cell 和其他系統在其中向監控服務宣傳其存在
指標，允許客戶端定位大型資料集（如 BigTable Cell），以及其他系統的許多設定檔

擴展 Chubby#

Chubby 的客戶端是個別的程序，因此 Chubby 處理的客戶端數量比預期更多。在 Google，超過 90,000 個客戶端與單一 Chubby 伺服器通訊就是一個例子。以下技術已被用於減少與主節點的通訊：

最小化請求頻率：建立更多 Chubby Cell，讓客戶端幾乎總是使用附近的 Cell（透過 DNS 找到），避免依賴遠端機器
最小化 KeepAlive 負載：KeepAlive 是目前最主要的請求類型；增加客戶端租約時間（從 12 秒到 60 秒）可以減少 KeepAlive 的負載
快取：Chubby 客戶端快取檔案資料、中繼資料、控制代碼以及檔案不存在的資訊
簡化協定轉換：新增可將 Chubby 協定轉換為較不複雜協定的伺服器。代理（Proxy）和分區（Partitioning）是兩個幫助 Chubby 進一步擴展的範例

代理（Proxy）#

代理是一個可以代表實際伺服器行動的額外伺服器。Chubby 代理可以處理 KeepAlive 和讀取請求。如果一個代理處理 N 個客戶端，KeepAlive 流量就會減少 N 倍。所有寫入和首次讀取會通過快取到達主節點。這意味著代理會為寫入和首次讀取增加一個額外的 RPC。這是可以接受的，因為 Chubby 是一個讀取密集（Read-heavy）的服務。

分區（Partitioning）#

Chubby 的介面（檔案和目錄）被設計為命名空間可以在需要時輕鬆地在多個 Chubby Cell 之間分區。這將減少任何分區的讀/寫流量，例如：

ls/cell/foo 及其所有內容可以由一個 Chubby Cell 服務
ls/cell/bar 及其所有內容可以由另一個 Chubby Cell 服務

有些場景中分區不會帶來改善：

刪除目錄時，可能需要跨分區呼叫
分區不一定能減少 KeepAlive 流量
由於 ACL 可能只儲存在一個分區中，檢查 ACL 時可能需要跨分區呼叫

經驗教訓#

缺乏積極快取：最初，客戶端沒有快取檔案不存在或開啟檔案控制代碼的資訊。濫用的客戶端可能寫出無限重試的迴圈（當檔案不存在時）或透過反覆開啟和關閉檔案來輪詢。Chubby 教育了使用者在這類場景中使用積極快取
缺乏配額：Chubby 從未打算用作大量資料的儲存系統，因此沒有儲存配額。事後看來，這是天真的想法。為了處理這個問題，Chubby 後來引入了 256KB 的檔案大小限制
發佈/訂閱：曾有多次嘗試將 Chubby 的事件機制用作發佈/訂閱系統。Chubby 是一個強一致性系統，其維護一致快取的方式使其成為發佈/訂閱的緩慢且低效的選擇。Chubby 開發者在早期就發現並阻止了這類使用
開發者很少考慮可用性：開發者通常沒有思考故障機率，錯誤地假設 Chubby 總是可用的。Chubby 教育了客戶端為短暫的 Chubby 中斷做好規劃，使其對應用程式幾乎沒有影響

總結#

Chubby 是 Google 系統內部使用的分散式鎖定服務
它提供粗粒度鎖定（持續數小時或數天），不建議用於細粒度鎖定（持續數秒）的場景。由於此特性，它更適合高讀取和稀少寫入的場景
Chubby 的主要使用案例包括：命名服務、領導者選舉、小型檔案儲存和分散式鎖定
一個 Chubby Cell 基本上指的是一個 Chubby 叢集。一個 Chubby Cell 有多個伺服器（通常至少 5 個），稱為副本
使用 Paxos，在任何時間點一個伺服器被選為主節點並處理所有請求。如果主節點故障，另一個副本成為主節點
每個副本維護一個小型資料庫來儲存檔案/目錄/鎖定。主節點直接寫入自己的本地資料庫，並非同步地同步到所有副本以實現容錯
客戶端應用程式使用 Chubby 程式庫透過 RPC 與 Chubby Cell 中的副本通訊
類似 Unix，Chubby 檔案系統介面基本上是一個檔案和目錄的樹狀結構（統稱為節點），每個目錄包含子檔案和目錄的清單
鎖定：每個節點都可以作為建議性讀取器/寫入器鎖定，以獨佔模式或共享模式運作
暫時性節點用作臨時檔案，並作為客戶端存活的指標。無客戶端開啟時或目錄為空時會被刪除
中繼資料：每個節點的中繼資料包括存取控制清單（ACL）、單調遞增的 64 位元數字和校驗和
事件：Chubby 支援簡單的事件機制，讓客戶端可以訂閱各種事件，如鎖定被取得或檔案被編輯
快取：為了減少讀取流量，Chubby 客戶端在客戶端記憶體中以一致的、寫入穿透快取方式快取檔案內容、節點中繼資料和開啟控制代碼的資訊
會話：客戶端透過向 Chubby 發送 KeepAlive RPC 來維持會話。這約佔 Chubby 叢集請求的 93%
備份：每隔幾小時，每個 Chubby Cell 的主節點將資料庫快照寫入不同建築物中的 GFS 伺服器
鏡像：Chubby 允許一組檔案從一個 Cell 鏡像到另一個 Cell。鏡像最常用於將設定檔複製到分佈在世界各地的各個運算叢集

系統設計模式#

以下是 Chubby 中使用的系統設計模式總結：

預寫日誌（Write-Ahead Log）：為了容錯和處理主節點崩潰，所有資料庫交易都儲存在交易日誌中
法定人數（Quorum）：為了確保強一致性，Chubby 主節點將所有寫入請求發送到副本。在收到 Cell 中多數副本的確認後，主節點向發起寫入的客戶端發送確認
世代時鐘（Generation Clock）：為了忽略來自先前主節點的請求，Chubby 中每個新選出的主節點使用「紀元號碼」（Epoch Number），這是一個簡單的單調遞增數字，用於指示伺服器的世代。這意味著如果舊主節點的紀元號碼為「1」，新的就會是「2」。這確保新主節點不會回應發送給先前主節點的任何舊請求
租約（Lease）：Chubby 客戶端與主節點維持有時間限制的會話租約。在此時間區間內，主節點保證不會單方面終止會話

簡介#