胖胖鎖服務 - chikaku

繼續翻譯論文，Chubby 是 Google 內部很多分佈式系統依賴的重要組件之一，這裡看原文

設計#

理由#

首先比較了 client Paxos library 和 centralized lock service 兩種方式的差異。

client Paxos library 不依賴其他服務，而且可以提供標準的編程框架，但是在開發早期原型階段不會充分考慮高可用性，且不適用於一致性協議。使用鎖可以更方便的維護現有的程序結構和通信模式，不需要維護一定數量的 client 來保證達成共識，減少了實現可靠客戶端系統所需的伺服器數量。基於這些原因，作者選擇了鎖服務，並允許存儲小文件以實現選舉主節點和廣告傳播等功能。此外，作者還介紹了一些預期使用和環境方面的決策，包括支持大量客戶端觀察文件、事件通知機制、文件緩存和安全機制等。

系統結構#

Chubby 主要包含兩個通過 RPC 通信的組件: server 以及客戶端鏈接庫。客戶端和服務端之間的所有 RPC 通信都是通過客戶端庫來協調。

一個 Chubby cell 是由多個 (一般是五個) server (副本) 組成的集合，這些副本被放置在不同的位置 (如不同的機架) 以降低相關故障的可能性。副本使用分佈式共識算法進行選舉 master 必須獲得大多數副本的投票和一段時間 (master 租約) 內不會選舉另外一個 master 的承諾。只要主節點繼續贏得副本的大多數選票，租約會周期性的進行續期。

每個副本維護了一個簡單數據庫的拷貝，但是只有 master 能夠對數據庫進行讀寫操作，其他副本通過共識協議從 master 拷貝更新。客戶端通過向 DNS 中列出的副本發送 master location 請求來找到 master 非 master 節點收到請求後會返回 master 的標識。一旦客戶端定位到 master 之後所有的請求都會向其發送，直到節點停止響應，或者其標識自己不再是 master。

寫請求會通過共識協議廣播到所有副本，只有請求到達 call 中的大多數副本才能被確認。讀請求由 master 節點獨自處理，在 master 租約未過期期間這樣是安全的，因為同時不可能有其他 master 存在。

如果一個 master 失效，其他副本會在他們的 master 租約過期時執行選擇協議，一般幾秒鐘以後新的 master 就會選舉出來。

如果一個副本失效，並且在幾個小時內沒有恢復，有一個簡單的替換系統會在空閒池中選一個新的機器來啟動 lock server 進程並且更新 DNS 表中對應副本的 IP 當前的 master 節點會周期性的輪詢 DNS 並且最終能夠發現這個變更，然後會在數據庫中更新 cell 成員列表，這個列表會通過普通的複製協議在所有成員間保持一致。同時新的副本會通過文件伺服器中的備份和其他活躍副本中的更新獲取最近的數據庫拷貝。一旦新副本處理了一個當前 master 等待提交的請求，就可以在新的 master 選舉中進行投票。

文件、目錄和句柄#

Chubby 提供了一個類似於文件系統的接口，但是比 UNIX 接口更簡單，整個系統由斜杠分割的名字組成一棵樹的結構，比如 /ls/foo/wombat/pouch 其中 /ls 是所有名字的公共前綴，表示 lock service 第二部分 foo 是 Chubby cell 的名字，通過 DNS 查詢解析成一個或多個 Chubby servers 一個特殊的 cell 名稱 local 表示客戶端應該使用本地的 cell 通常這個 cell 是跟客戶端在同一建築內的。剩下的部分 /wombat/pouch 是客戶端自行定義的。

使用這種類似於文件系統的結構，無需實現基礎的瀏覽和命名空間操作工具，並且減少了教育用戶的成本。

Chubby 和傳統的 UNIX 文件系統設計不同以便於分發。為了允許不同目錄的文件 (不同的 cell) 服務於不同的 master Chubby 不支持將文件從一個目錄移動到另一個目錄的操作，也不維護目錄的修改時間，並且避免路徑依賴權限 (即每個文件的權限由文件自身控制，與其所在的目錄無關)

為了簡化文件元數據緩存，系統並不顯示最後訪問時間。命名空間僅包含文件和目錄，統稱為節點。每個節點在其 cell 中僅有一個名字，也不適用符號鏈接或者硬鏈接。

節點可以是永久的或者是臨時的，所有節點都可以顯式的刪除，臨時節點會在沒有客戶端將其打開 (或目錄為空) 時刪除，臨時節點可以用作臨時文件，用於向其他節點表明表明一個客戶端是活躍的。

所有節點都可以用作讀 / 寫諮詢鎖。每個節點有各種元數據，包括三個 ACLs (access control lists) 名稱用於：讀取控制，寫入控制，更改節點 ACL 名稱。

在非覆蓋情況下，一個節點在創建時會繼承其父目錄的 ACL 名稱 ACL 本身也是在 ACL 目錄下的文件，屬於 cell 本地命名空間的一部分。這些 ACL 文件包含一個簡單的負責人名字的列表。因此如果一個文件 F 的寫入 ACL 名字是 foo 並且 ACL 目錄包含一個名為 foo 的文件，此文件中包含條目 bar 則用戶 bar 被允許寫入 foo 文件，用戶通過 RPC 系統內置的機制進行驗證。

由於 Chubby 的 ACLs 是簡單的文件，對於其他想要使用類似權限控制機制的服務來說是自動可用的。

每個節點的元數據包含四個單調遞增的 64 位數字允許客戶端簡單的檢查變更:

實例編號：大於具有相同名稱的示例編號 (刪除，創建相同節點)
內容生成編號 (僅文件): 在寫入文件內容時遞增
鎖產生編號：當節點鎖從空閒轉換到被持有時遞增
ACL 生成編號：當節點的 ACL 名稱被寫入時遞增

Chubby 也提供了 64 位的文件內容校驗和客戶端就可以知道文件是否有變更。客戶端打開文件獲取 handle 類似於 UNIX 的文件描述符 handle 包含:

校驗位，預防客戶端創建或者猜測 handle 因此只需要在 handle 創建時執行完整的訪問控制檢查。（類似於 UNIX 只在打開文件時檢查權限位）
一個序列號，允許 master 判斷這個 handle 是自己還是之前的 master 節點生成的
在打開文件時提供的模式信息，允許在出現舊的 handle 時新啟動的 master 也能夠重建其狀態

鎖和序列器#

每個 Chubby 的文件和目錄都表現得像是一個讀寫鎖：一個客戶端 handle 以互斥模式持有鎖，或者多個客戶端 handle 以共享模式持有鎖。

這裡的鎖是一種諮詢鎖：只會跟其他試圖獲取相同鎖的操作產生衝突，持有鎖 F 並不是訪問文件 F 所必須的，也不會阻塞其他客戶端訪問此文件。相對而言，強制性所鎖住對象後會導致沒有持有這個鎖的其他所有客戶端無法訪問：

Chubby 鎖保護的資源是其他服務實現的，而不僅僅是鎖相關的文件，如果需要強制實施強制鎖需要對這些服務進行修改
我們不希望當用戶出於 debug 或者管理的目的需要訪問被鎖住的文件時，強制他們關閉應用 (為了移除鎖)
執行錯誤檢查更簡單，進行類似 lock X is held 的斷言即可
bug 或者惡意操作有很多機會在沒有持有鎖時損壞數據，所以我們發現強制鎖提供的額外保證並沒有太大的價值

在 Chubby 中無論獲取什麼類型的鎖都需要寫的權限，這樣沒有權限的 reader 就不能阻止 writer 的操作。

分佈式系統中的鎖是很複雜的，因為通信一般是不確定的，且進程可能會獨立失敗。因此一個持有鎖 L 的進程可能會發出 R 請求然後自己失效了，同時另外一個進程可能會獲取到鎖 L 然後在 R 請求沒有到達目的地之前執行一些操作，如果 R 稍後到達，可能會在沒有鎖 L 的保護下，使用不一致的數據執行操作。接收消息順序混亂的問題已經有很多研究了，解決方案包括 virtual time, virtual synchrony 通過確保消息以所有參與者觀察到的一致的順序處理，來避免這個問題。

在現有複雜系統中給所有交互引入序列號成本很高，而 Chubby 提供了一種方法，只在使用鎖的交互中引入序列號。在任何時間，一個鎖的持有者請求 sequencer (序列控制器) 產生一個非透明字節字符串來描述鎖在獲取後的即時狀態：包含鎖的名字，鎖模式 (互斥或共享)，鎖生成編號。

如果客戶端想要在 server 上執行一些需要受到保護的操作會將 sequencer 傳遞到 server 接收到的 server 會檢查 sequencer 是否依然有效且處於合適的模式，否則會拒絕請求。一個 sequencer 可以通過伺服器的 Chubby 緩存進行有效性驗證，如果伺服器不想維持一個與 Chubby 的會話，也可以使用伺服器最後觀察到的 sequencer 進行驗證 sequencer 機制僅需要在消息上附加一個字符串，這也很容易跟開發者解釋。

儘管 sequencers 用起來很簡單，但是對於一些比較重要的協議進展很慢。因此 Chubby 還給不支持 sequencers 的服務提供了一種不完美但是更簡單的機制來降低延遲或者亂序請求的風險。

如果一個客戶端正常釋放了一個鎖，其他客戶端立即可以獲得這個鎖。然後如果一個鎖因為持有者崩潰或者無法訪問而釋放，則 lock server 會阻止其他客戶端在一段時間內獲得這個鎖稱為 lock-delay 客戶端可以指定延遲時間，但上限是一分鐘，這個上限是為了避免崩潰的客戶端導致鎖 (及其關聯的資源) 在任意長的時間不可用。雖然不完美，但是 lock-delay 保護了未經修改的伺服器和客戶端免受消息延遲和重啟導致的日常問題。

事件#

Chubby 客戶端在創建 handle 時可以訂閱一系列的事件，這些事件會通過 Chubby 庫的上層調用異步的派發給客戶端。事件包括：

文件內容修改：經常用於監控通過文件廣播的 service location (服務發現)
子節點新增，移除或修改：用於實現 mirroring
Chubby master 故障轉移：警告客戶端其他事件可能會丟失，所以需要重新掃描數據
一個 handle 及其關聯的鎖失效：一般表明通信存在問題
鎖獲取：用於確定是否已經選舉出了一個 primary
其他客戶端的衝突鎖請求：允許鎖緩存

事件是在對應的行為發生後派發的，因此如果一個客戶端被告知文件內容變更，能夠保證之後讀取的數據都是新的。上述的後兩個事件很少使用，回過頭來看可以被省略。比如選舉後客戶端通常需要和新的 primary 進行通信，而不僅僅是只知道有一個 primary 存在，因此他們等待一個表明新的 primary 將其地址寫入到了文件的修改事件。

衝突鎖事件理論上允許客戶端緩存被其他 server 持有的數據，使用 Chubby 鎖維護緩存一致性。一個鎖衝突請求通知向客戶端表明應該完成未處理的操作 flush 修改，丟棄緩存數據然後釋放鎖 (鎖衝突意味著有另外一個客戶端要修改數據)。但是到目前位置還沒有任何人採用這種方式。

API#

客戶端將 Chubby handle 視作一個支持各種操作的非透明指針 handle 只能通過 Open 創建，通過 Close 銷毀。

Open 打開一個指定名稱的文件或目錄產生一個 handle 類似於 UNIX 的文件描述符，也只有 Open 使用名字，所有其他的操作都基於 handle 這裡使用的名字是相對於一個已經存在的目錄 handle (相對路徑) 然後庫中提供了一個永遠有效的 handle / 即根目錄，目錄 handle 避免了在多層抽象的多線程程序內全局使用 current directory 會產生的問題。

客戶端提供了多種選項:

將會如何使用 handle (讀 / 寫 / 鎖 / 修改 ACL) client 擁有合適的權限 handle 才能創建成功
應該派發的事件
是否應該 (必須) 立即創建一個文件或目錄，如果創建了文件，調用者可以提供初始內容和初始 ACL 名稱，返回值會表明是否創建了文件

Close () 關閉一個打開的 handle 此後 handle 不允許被使用，這個調用永遠都不会失败。一个相关的调用 Poison () 会导致 handle 在不需要 close handle 的情况下，使得所有未完成的和后续的操作都失败。这种方式允许一个客户端可以取消其他线程执行的 Chubby 调用而无需担心释放这些调用访问的内存。

在一個 handle 上主要執行的調用是:

GetContentsAndStat () 返回文件的內容和元數據，文件內容被原子性的完整讀取。我們避免部分讀取和寫入，來阻止使用大文件。有一個相關的調用 GetStat () 僅僅返回文件的元數據而 ReadDir () 返回目錄下子節點的名字和元數據
SetContents () 向文件中寫入內容，客戶端可以提供一個文件生成編號來模擬文件的 compare-and-swap 只有生成編號和當前一致才會修改內容。寫入操作也是具有原子性的整體寫入。類似還有一個 SetACL () 調用在節點關聯的 ACL 名稱上執行類似的操作
Delete () 調用在節點沒有子節點時將其刪除
Acquire (), TryAcquire (), Release () 申請和釋放鎖
GetSequencer () 返回一個描述當前 handle 持有的所有鎖的 sequencer
SetSequencer () 將 handle 和一個 sequencer 關聯在一起，如果 sequencer 已經失效則相關所有的 sequencer 操作都會失敗
CheckSequencer () 檢查 sequencer 是否有效

如果 handle 創建之後節點被刪除則調用會失敗，即使後續文件被重新創建。因為 handle 總是和一個文件實例相關聯而不是一個名字 Chubby 雖然可以對所有調用執行訪問控制檢查，但是實際上只會檢查 Open 調用。

以上所有調用除了本身所使用的參數以外，都会附带一个操作参数保存可能与任何调用相关的数据和控制信息，具体来说通过操作参数，客户端可以：

提供一个回调函数来使调用异步
等待一个调用结束
获取扩展错误和诊断信息

客戶端可以使用這些 API 執行 primary 選舉：所有潛在的 primary 打開鎖文件然後嘗試獲取鎖，其中一個成功且成為 primary 其他則成為副本。然後 primary 使用 SetContents () 調用將自己的標識寫入鎖文件，這樣就可以被其他客戶端和副本通過 GetContentsAndStat () 讀取文件發現 (可能是作為文件修改事件的響應)。理想情況下 primary 通過 GetSequencer () 獲取一個 sequencer 在後續通信時傳遞到 server 上，他們會執行 CheckSequencer () 確認其依然是 primary 對於無法檢查 sequencer 的服務，可以使用之前提到過的延遲鎖

緩存#

為了減少讀流量 Chubby 客戶端在內存中緩存文件數據和節點的元數據。緩存由一個租約機制維護，通過 master 發送的失效請求保持一致，這個協議保證客戶端要麼看到一個一致的 Chubby 狀態，要麼發生錯誤。

當文件數據或元數據改變時，修改操作會阻塞到 master 給所有可能緩存數據的客戶端發送失效請求，這個機制位於 KeepAlive RPCs 之上。當接收到失效請求後，客戶端清除無效狀態，並且在下一次 KeepAlive 調用中進行確認。修改流程會持續到 server 知道每個客戶端都將其緩存失效：要麼是因為客戶端確認了失效消息，要麼是客戶端允許其緩存的租約過期。

只需要一輪無效化是因為，當緩存無效化一直無法確認時 master 會將節點認為是不可緩存的。這種方式允許讀請求不會被延遲處理，在讀操作遠超過寫操作的情況下這樣很有用。一種替代方案是在無效化期間阻塞所有訪問對應節點調用，這將會減少一些熱點客戶端在無效化期間對 master 進行的轟炸式的非緩存訪問，代價是偶爾的延遲。如果這是一個問題，可以想像採用混合方案，一旦檢測到超載就切換策略。

緩存協議很簡單，在有變更時直接將其失效，從不更新緩存。更新可能比無效化更簡單，但是僅更新的協議可能會非常低效，客戶端訪問一個文件時可能會收到無限多的更新，導致無限多的非必要的更新 (失效後直接獲取最新的就可以了)。

儘管提供嚴格一致性的開銷很高，我們也拒接使用弱一致性的模型因為這種對程序員來說很難用。類似的，比如虛擬同步機制，在一個預先存在多樣化通信協議的環境中，需要客戶端在所有消息中交換序列號是不合適的。

除了緩存數據和元數據 Chubby 客戶端還緩存打開的 handle 因此如果一個客戶端打開之前已經已經打開過的文件，只有第一個 Open 請求需要發送到 master 這種緩存受到一些小的限制，以確保不會對客戶端觀察到的語義產生影響：臨時文件上的 handle 在應用將其關閉以後不能保持打開狀態，允許加鎖的 handle 可以被重用但是不能同時被多個 handle 使用。後一條限制存在是因為客戶端可能會使用 Close () 或者 Poison () 取消向 master 未完成的 Acquire () 調用並產生副作用。

Chubby 協議允許客戶端緩存鎖，即超出所需的時間更長的持有鎖，可以在同一個客戶端上重用。當其他客戶端請求鎖衝突時會通知鎖的持有者一個事件，允許持有者在其他地方需要鎖時釋放。

會話和 KeepAlives#

Chubby 會話指的是一個 Chubby cell 和一個客戶端的關係，其存在一段事件，通過稱為 KeepAlives 的周期性握手來維護。除非客戶端主動通知 master 否則客戶端的 handle 鎖和緩存數據在會話保持有效期間都是保持有效的 (會話維護消息可能會需要客戶端確認緩存無效化來保證會話有效)

客戶端在第一次和 Chubby cell 聯繫時會請求一個新的會話，而會話結束是隱式的，可能是客戶端自己終止或者會話被閒置 (掛起)(在一分鐘內沒有打開 handle 和任何調用)。

每個會話有一個關聯的租約 (一個續期的間隔時間)，保證未來的一段時間內 master 不會單方面的終止會話，這個時間間隔的結束稱為會話租約超時 master 可以自由的將超時時間進一步推遲到未來，但是不能移到過去。

master 會在以下三種情形下推遲租約超時的時間：會話創建時，master 發生故障轉移時，響應客戶端 KeepAlive RPC 時。收到 KeepAlive 請求時 master 一般會將 RPC 阻塞到客戶端的前一個租約間隔快過期，然後才允許 RPC 返回給客戶端並且告知客戶端新的租約超時的時間 master 可能會將超時的時間延長任意時長，默認的延長時間是 12s 但是負載高的 master 可能會使用更長的時間以減少需要處理的 KeepAlive 的調用的數量。客戶端收到前一個響應後會立即發起一個新的 KeepAlive 因此客戶端可以保證幾乎總是有一個 KeepAlive 阻塞在 master 上。

除了延長租約 KeepAlive 的響應還可以用來傳輸事件和失效緩存 master 允許在派發事件或者無效化時提早返回 KeepAlive 在響應中搭載事件確保客戶端在確認緩存失效前無法維持會話，並且使得所有的 Chubby RPCs 從客戶端流向 master 這簡化了客戶端並且允許協議在只允許單向連接初始化的防火牆上運行。

客戶端在本地維護一個相對於 master 較為保守的租約超時時間，因為客戶端需要考慮到響應消息在返回過程中花費的時間和 master 上時鐘超前的可能性，為了保持一致，我們需要保證 server 的時鐘不能比客戶端的時鐘超過一個已知的常數因子。

如果客戶端本地租約超時，它沒辦法確定是否 master 已經終止了此會話，客戶端會禁用和清空緩存，並處於一個不確定的狀態。客戶端等待一個寬限期的間隔時間 (默認 45s) 如果在此間隔結束之前成功交換了 KeepAlive 則客戶端再一次啟用緩存，否則客戶端假設會話已經過期。這樣做的為了當 Chubby cell 無法訪問時 Chubby API 調用不會無限期的阻塞，在寬限期結束之前如果通信沒有重新建立，調用會返回一個錯誤。

當寬限期開始時 Chubby 庫可以通知應用一個危險事件，當會話通信問題恢復後會發送一個安全事件，反之如果會話超時則發送一個超時事件。這些信息能夠使應用在不確定自己會話的狀態時保持安靜，當遇到暫時性問題時也無需重啟即可恢復。對一些啟動開銷很大的服務來說防止中斷很重要。

如果一個客戶端持有一個節點的 handle H 並且由於關聯的會話過期所有在 H 上的操作都失敗了，後續的所有請求 (除了 Close) 都會以相同的方式失敗。客戶端可以以此來保證，網絡和服務中斷只會導致操作序列的某個後綴部分丟失，而非任意的子序列，因此可以使用最終的寫入來將複雜的變更標記為已經提交 (只要最終寫入的是成功，前面的所有操作一定是成功的)

故障轉移#

當 master 產生故障或失去主控權，會丟棄掉所有的內存狀態包括：會話 handle 和鎖。會話租約的權威定時器運行在 master 上，所在在新的 master 被選舉出來之前租約定時器是停止的，這樣等效於延長了客戶端的租約。如果 master 選舉很快，客戶端可以在本地 (寬鬆) 租約定時器過期之前，連接到新的 master 而如果租約花費了較長的事件，客戶端會清除本地的緩存並在寬限期內等待新的 master 因此寬限期允許在超過正常租約超時的故障轉移過程中維持會話。

故障轉移

上圖顯示了在漫長的 master 故障轉移事件過程中的一系列事件，客戶端必須使用其寬限期保護其會話。初始 master 有一個客戶端租約 M1 然後客戶端有一個相對保守估計的 C1 接著 master 提交了 M2 租約，客戶端延續租約到 C2 然後在響應下一條 KeepAlive 之前 master 宕機，在一個 master 選舉出來之前過去了一些時間，最終客戶端租約 C2 到期，然後客戶端清除緩存並開啟了一個新的寬限期定時器。

在這個時期內，客戶端無法確認是否其租約在 master 上過期，客戶端不會立即銷毀會話，但是會阻塞所有應用層的 API 調用避免應用層觀察到不一致的數據。在寬限期的開始 Chubby library 發送一個危險事件到應用層讓其監聽發送請求，直到能夠確認會話狀態。

最終一個新的 master 被選舉出來 master 給之前可能持有的租約初始化一個保守估計的租約 M3 從客戶端發送到新的 master 的第一個 KeepAlive 請求會被拒絕因為包含錯誤的 master 週期編號，重試請求 (6) 能夠成功但是一般不會延長 master 租約因為 M3 本身就是保守估計的 (延長了) 然而響應 (7) 允許客戶端再次延續其本身的租約到 C3 並且可以通知應用層會話不再處於危險中。由於寬限期足夠長覆蓋了 C2 的結束到 C3 的開始的間隔，客戶端只能感知到一段延遲，而如果寬限期比這個間隔小，客戶端會放會話然後向應用層報告錯誤。

一旦客戶端連接到新的 master 客戶端 library 和 master 協作給應用層提供一個錯覺好像從來沒有發生過故障，為了達到這個目標新的 master 必須重新構造一個相對於之前的 master 保守估計的內存狀態，部分通過讀取穩定存儲在磁碟上的數據 (通過普通的數據庫複製協議備份)，部分通過獲取從客戶端獲取到的狀態，部分通過保守的估計。數據庫記錄每個會話，持有鎖和臨時文件。

被選舉出的新的 master 執行以下步驟：

master 選取一個新的 epoch number 客戶端需要在每個調用中傳入 master 會拒絕低於此 epoch number 的請求並且提供當前最新的編號，確保新的 master 不會響應發給之前的 master 的數據包，即使是運行在相同的機器上。
master 可能會響應 master-location 請求，但是一開始不會處理傳入的與會話相關的請求。
master 在內存中重建記錄在數據庫中的會話和鎖的數據結構，會話租約會被延期到上個 master 可能會使用的最大時長
master 開始讓客戶端執行 KeepAlives 但不執行其他會話相關的操作。
master 向所有的會話發送一條 fail-over 事件，這會使客戶端清除他們的緩存 (因為他們可能會錯過一些緩存無效化的通知) 並且警告應用層一些事件可能已經丟失了。
master 等待所有會話確認 fail-over 事件或者使其過期。
master 允許處理所有操作
如果一個客戶端使用一個在故障轉移之前創建的 handle (通過 handle 中的 sequence number 確定) master 會重新創建這個 handle 在內存中的表示然後響應調用。如果這個新創建的 handle 被關閉 master 會在內存中記錄，這樣在當前的 epoch 內就不會被重新創建，這樣能夠保證一個延遲或者重複的網絡包不會意外的重新創建一個已經關閉的 handle 故障的客戶端可以在以後的 opoch 中重新創建一個已經關閉的 handle 由於客戶端已經故障，這樣是無害的。
在一段時間後 master 刪除已經沒有被打開的 handle 的臨時文件，客戶端也應該在故障轉移一段時間以後刷新臨時文件上的 handle 這種機制的不幸效果是，如果最後一個使用該文件的客戶端在故障轉移期間丟失了會話，臨時文件可能無法及時消失。

數據庫實現#

第一版的 Chubby 使用帶複製版本的 Berkeley DB 的作為其數據庫 Berkeley DB 提供了 B-trees 將 bytestring key 映射到任意 bytestring value 我們使用了一個 key 比較函數：首先比較路徑中層級的數目，將所有節點按照路徑名劃分成 key 還能保證兄弟節點在在排序中相鄰。由於 Chubby 不使用基於路徑的權限，每次文件訪問只需要在數據庫中查找一次就夠了。

Berkeley DB 使用一個分佈式共識協議在多個 server 之間複製數據庫日誌，一旦添加了 master 租約，這就和 Chubby 的設計相匹配，使得實現變得簡單直接。

Berkeley DB 的 B-tree 代碼已經被廣泛使用且非常成熟，但是複製的代碼是最近新加的並且用戶很少。軟件維護者必須優先考慮維護和改進他們最流程的產品功能 Berkeley DB 的維護者解決了我們的問題，我們覺得使用複製代碼會使我們面臨比我們願意承擔更多的風險。最終我們使用 WAL 和快照技術寫了一個簡單的數據庫。和之前一樣，數據庫日誌通過一個分佈式共識協議在所有副本間分發 Chubby 使用了 Berkeley DB 很少一部分的特性，因此這次重寫允許我們極大簡化了整個系統，比如當我們需要原子操作，不需要事務。

備份#

每幾個小時每個 Chubby cell 的 master 將其數據庫快照寫入到不同建築的 GFS server 上。使用分開的建築確保建築物損壞時備份能夠存活，且副本不會在系統內引入循環依賴，因為同一建築內的 GFS cell 可能會依賴其選舉出來的 Chubby cell

備份提供了災難恢復，和一種不會給正在運行中的服務增加負載的初始化新的替代副本的數據庫的方法。

鏡像#

Chubby 允許將一組文件從一個 cell 鏡像到另一個 cell 鏡像操作很快，因為文件很小，而且事件機制可以在添加 / 刪除 / 修改文件時立即通知鏡像代碼。假設沒有網絡問題，變更會在不到一秒內反映到事件範圍內的數十個鏡像中。如果一個鏡像不可到達，其會保持不變直到連接恢復，文件更新通過比較他們的校驗和來標識。

鏡像最經常用於拷貝配置文件到分佈在世界各地的不同的計算集群上。一個名為 global 的特殊 cell 包含一個子樹 /ls/global/master 被鏡像到所有其他 cell 上的子樹 /ls/cell/slave global cell 是特殊的，因為其五個副本分佈在世界各地相距較遠的地方，所以它基本上在大多數地方能被訪問到。

在 global cell 鏡像文件中包含 Chubby 自身的權限控制列表，以及 Chubby cell 和其他服務向監控服務告知其存在的文件，允許客戶端定位類似 Bigtable cells 的大數據集的指針，和許多其他系統的配置文件。

擴展的機制#

Chubby 的客戶端是獨立的進程，因此 Chubby 必須處理比預期更多的客戶端，我們已經見過超過 90000 個客戶端直接和一個 Chubby master 直接相連，涉及到比這個數量更多的機器。由於每個 cell 中僅有一個 master 並且其機器和客戶端是相同的，客戶端數據遠超其處理能力。因此最有效的擴容技術通過顯著減少與 master 的通信來實現，假設 master 沒有嚴重的性能 bug 在 master 對請求處理上的微小改進對其影響很小，我們使用了幾種方法：

我們可以創建任意數量的 Chubby cell 但客戶端幾乎總是使用一個最近的 cell 來避免依賴遠程機器，我們典型的部署方式是在一個數千台機器的數據中心中使用一個 Chubby cell
master 可以在處於高負載時，將其租約時間從 12s 提高到最多 60s 這樣可以處理更少的 KeepAlive RPCs (KeepAlive 是主要的請求類型，無法及時處理請求是負載過重伺服器的典型故障模式，客戶端對其他調用的延遲變化很不敏感)
Chubby 客戶端緩存文件數據，元數據，缺失文件和打開的 handle 來減少向伺服器發起的調用
使用協議轉換伺服器將 Chubby 協議轉換成更簡單的協議比如 DNS 等。

這裡，我們描述兩種熟悉的機制：代理和分區，我們期望這些能夠使 Chubby 進一步擴展。我們還沒有在生產環境中使用，但是已經被設計好，可能很快就用上。我們目前無需考慮超過五倍的擴展：首先，我們放在一個數據中心上的機器或者依賴於單個服務的實例都有數量限制；其次，由於我們在 Chubby 客戶端和伺服器上使用相似的機器，硬件優化在每台機器上增加客戶端的數量，也會增加每個 server 的容量。

代理#

Chubby 的協議可以被信任的進程代理，代理可以通過處理 KeepAlive 和讀取請求來降低伺服器的負載，但是不能通過代理緩存減少寫流量，不過即使使用了積極的客戶端緩存策略，寫入流程也只占 Chubby 正常工作負載的不到百分之一。所以使用代理可以極大增加客戶端的數量。

如果一個代理處理 N 個客戶端 KeepAlive 流量就減少了 N 可能是 10k 或更多，代理緩存最多可以減少的讀取流量大約是讀共享的平均值，大約是 10 倍的因素。但是由於讀取只占 Chubby 負載的不到 10% 節省 KeepAlive 流量的效果更重要。另外代理添加了寫入和首次讀取的額外 RPC 調用。人們可能會期望代理使得 cell 臨時不可用性相比之前增加了一倍，因為每個代理客戶端依賴兩台可能會故障的機器：代理伺服器和 Chubby master 伺服器。敏銳的讀者可能會注意到之前描述的故障轉移策略對於代理伺服器並不理想。

分區#

Chubby 的接口被設計成一個 cell 的命名空間可以被分區到不同的 server 上，儘管我們現在還不需要，代碼可以通過目錄將命名空間分區。如果開啟，一個 Chubby cell 可以由 N 個分區組成，每個分區都有一個副本集合和一個 master 每個目錄 D 中的節點 D/C 會被存儲在分區 P(D/C) = hash(D) mod N 上，注意 D 的元數據可能會存儲子啊不同的分區上 P(D) = hash(D0) mod N 這裡 D0 是 D 的父目錄。

分區旨在實現區分之間只有少量通信的大型 Chubby cell 儘管 Chubby 缺少硬鏈接，目錄修改時間，和跨目錄的重命名操作，少部分操作仍然需要跨分區的通信：

ACLs 本身就是文件，因此一個分區可能會使用其他分區進行權限檢查，然而 ACL 文件很容易緩存，只有 Open () 和 Delete () 調用需要 ACL 檢查，並且大多數客戶端讀取的是公開可訪問的文件，不需要 ACL
當一個目錄被刪除，跨分區調用可能需要確認這個目錄是空的

由於每個每個分區處理的調用大部分不依賴其他分區，我們預期分區間通信對性能和可用性的影響有限。儘管分區的數量 N 很大，可以預期每個客戶端都會聯系大多數的分區，因此分區能夠將給分區上的讀寫流量減少 N 倍但是並不一定會 KeepAlive 流量。

如果有必要讓 Chubby 處理更多的客戶端，我們的策略包括使用代理和分區的組合。

使用、驚喜和設計錯誤#

... 省略相關數據和使用情況

作為名稱服務的使用#

儘管 Chubby 被設計成一個鎖服務，我們發現它最常見的用途是作為一個 name server 常見的互聯網 name system 使用基於時間的緩存 DNS 條目有一個存活時間 TTL 如果在這個時期內沒有刷新則 DNS 數據會被丟棄。通常如果選擇一個合適的 TTL 值是很直觀的，但是如果希望快速替換失敗的服務 TTL 可能會足夠小以至於拖垮 DNS 伺服器。

例如，對我們的開發者來說，運行一個涉及到上千個進程的作業是很普遍的，每個進程都要和其他進程通信，導致平方級別的 DNS 查詢。我們可能希望使用 60s 的 TTL 這會使得行為不當的客戶端可以在沒有過多延遲的情況下被替換，而且在我們的環境中不被認為是一個過於短暫的替換時間。

在這種情況下，為了維護一個將近 3000 個客戶端的作業，每秒需要 150k 次查詢 DNS 緩存，更大型的作業會帶來更嚴重的問題，而且許多作業可能會同時進行。在引入 Chubby 之前我們的 DNS 負載的變化一直是 Google 的一個嚴重問題。

作為對比 Chubby 的緩存使用顯示的無效化，因此在沒有變化的情況下，以一個恆定的速率請求會話 KeepAlive 可以在客戶端上無限期的維護任意數量的緩存條目。一個 2 核 2.6GHz 的 Chubby master 可以處理與其直連的 90k 個客戶端，其中包括上面提到過的大型作業的客戶端。不需要逐個輪詢每個名稱，就能夠提供快速名稱更新的能力是非常吸引人的，以至於現在 Chubby 為公司的許多系統提供 name service

儘管 Chubby 的緩存允許一個 cell 支撐大量的客戶端，但是負載峰值仍然是一個問題。當我們首次部署基於 Chubby 的 name service 開了 3k 個進程 (產生了 9m 的請求) 就可以把 master 打跪。為了解決這個問題，我們選擇將一組名稱查詢組成批處理，這樣單個查詢就可以返回和緩存大量 (一般是 100 個) 作業中相關進程的名稱映射。

Chubby 提供的緩存語義比 name service 更精確，名稱解析只需要及時通知而非完全一致性。通過引入一個專門用於名稱查詢的簡單的協議轉換伺服器，有機會減輕對 Chubby 的負載。如果我們預見到 Chubby 作為 name service 的使用，我們可能會更早的實現完全代理，以避免對這個簡單的需求的需要。

還存在一個進一步的協議轉換伺服器：Chubby DNS server 存儲在 Chubby 上的名稱數據對 DNS 客戶端可用。這個服務對簡化從 DNS 名稱到 Chubby 名稱的過渡和適應無法輕鬆轉化的現有應用 (如瀏覽器) 都很重要。

教訓#

開發者很少考慮可用性，我們發現我們的開發者很少考慮故障的可能性，並且傾向於將 Chubby 這樣的服務視為始終可用。比如，我們的開發者曾構建過一個系統，使用了數百台機器，當 Chubby 選舉出一個 master 後，這個程序會啟動恢復程序，需要幾十分鐘的時間。這不僅將單個故障在時間上放大了一百倍，而且影響了數百台機器。我们更希望开发者对 Chubby 的短暂中断做好计划，这样这种事件对他们的应用程序几乎没有任何影响。

開發者們也沒能理解 service 啟動和 service 對他們的應用可用的區別，比如 global cell 基本上總是在運行，因為很少見到地理上相距較遠的兩個或以上數據中心同時宕機。然而對於客戶端所觀察到的可用性總是低於客戶端本地的 local cell 首先客戶端與 local cell 分開的概率較低，並且儘管 local cell 可能會經常因為維護宕機，同樣的維護也會直接影響到客戶端，所以 Chubby 的不可用性不會被客戶端觀察到。

我們的 API 選擇也會影響到開發者處理 Chubby 中斷的方式，比如 Chubby 提供了事件允許客戶端發現 master 故障轉移，原本的目的是讓客戶端檢查可能的變更，因為其他事件可能丟失了。不幸的是，許多開發者在收到這個事件時會直接崩潰他們的應用，由此顯著的降低了他們系統的可用性。我們可能更好還是發送冗餘的文件變更事件，或者確保在故障轉移期間沒有事件丟失。

當前我們使用了三種機制避免開發者對於 Chubby 的可用性過於樂觀，特別是 global cell 首先，像之前提到過的，我們檢查工程團隊如何計劃使用 Chubby 並且建議他們不要使用那些將他們系統的可用性與 Chubby 緊密聯系在一起的技術。其次，我們現在提供 libraries 執行一些高層次的任務將開發者和 Chubby 的中斷自動隔離開來。第三，我們對每次 Chubby 中斷進行事後分析，不僅用於消除 Chubby 和我們操作程序中的 bug 還減少了應用對於 Chubby 可用性的敏感性，這兩者都可以提高整個系統的可用性。

細粒度的鎖可以被忽略，前面章節描述過一個可以使客戶端使用細粒度鎖的服務的設計。令人驚訝的是，目前為止我們不需要實現這樣一個服務。我們的開發者發現，為了優化應用程序，他們必須移除不必要的通信，而這通常意味著找到了一个使用粗粒度鎖的方式。

糟糕的 API 選擇會產生意想不到的影響，總體而言我們的 API 發展良好，但是出現了一個突出的錯誤。我們意圖取消長時間運行調用的 API 是 Close () 和 Poison () RPCs 這也會丟棄 handle 在伺服器上的狀態。這避免了 handle 這會阻止可以獲取鎖的 handle 被共享，例如被多個線程共享。我們可以添加一個 Cancel () RPC 允許打開的 handle 被共享。

RPC 的使用會影響傳輸協議 KeepAlives 同時用於刷新客戶端的會話，傳遞事件和 master 下發的緩存無效化。這種設計使得客戶端無法確認緩存無效化時無法刷新其會話，這看起來是很理想的，但是會使我們在設計協議時小心謹慎 TCP 的退避策略不關心上層的超時比如 Chubby 的租約，因此基於 TCP 的 KeepAlives 在網絡擁堵時產生了非常多的會話丟失。我們被迫使用 UDP 而非 TCP 發送 KeepAlive RPCs UDP 沒有擁塞避免機制，所以當上層時間限制需要考慮時我們更傾向於使用 UDP。

在正常情況下，我們可以通過一個額外的基於基於 TCP 的 GetEvent () RPC 擴充協議，用於傳遞事件和無效化，用法和 KeepAlive 相同 KeepAlive 響應依然包含一個未確認事件的列表，這樣可以確保事件最終得到確認。