mysileng

http://blog.csdn.net/historyasamirror/article/details/3870168

Google利器之Chubby 

寫完了Google Cluster，該輪到Chubby了。

參考文獻：
[1] The Chubby lock service for loosely-coupled distributed systems 
[2] Paxos Made Simple

聲明

文中大部分的觀點來自于文獻[1]中的描述，但也夾雜了部分本人自己的理解，所以不能保證本文的正確性。真想深入了解Chubby還是好好讀原版論文吧：)

前言

MapReduce很多人已經知道了，但關于Chubyy似乎熟悉它的就非常有限，這倒是不奇怪，因為MapReduce是一個針對開發人員的ProgrammingModel，自然會有很多人去學習它，而Chubby更多的是一種為了實現MapReduce或者Bigtable而構建的內部的 工具，對于開發人員來說基本上是透明的。文獻[1]我反復讀了至少有兩三天，但感覺也只是一個囫圇吞棗的結果，里面有很多工程實現上的細節，如果不是自己 親自去設計或者實現，很難體會到其中的道理和奧妙。但是，對于這樣一個分布式service的研究，還是讓我對一個分布式系統的結構和設計思想有了更加直 觀的感覺。

從distributed consensus problem說起

distributed consensus problem(分布的一致性問題)是分布式算法中的一個經典問題。它的問題描述大概是這樣的：在一個分布式系統中，有一組的Process，它們需要確 定一個Value。于是每個Process都提出了一個Value，consensus就是指只有其中的一個Value能夠被選中作為最后確定的值，并且 當這個值被選出來以后，所有的Process都需要被通知到。
表面上看，這個問題很容易解決。比如設置一個server，所有的process都 向這個server提交一個Value，這個server可以通過一個簡單的規則來挑選出一個Value（例如最先到達的Value被選中），然后由這個server通知所有的Process。但是在分布式系統中，就會有各種的問題發生，例如，這個server崩潰了怎么辦，所以我們可能需要有幾臺server共同決定。還有，Process提交Value的時間都不一樣，網絡傳輸過程中由于延遲這些Value到達server的順序也都沒有保證。
為 了解決這個問題，有很多人提出了各種各樣的Protocol，這些Protocol可以看做是一組需要遵循的規則，按照這些規則，這些Process就能 夠選舉出一個唯一的Value。其中，最有名的一個Protocol就是Paxos算法。（八卦一下，Paxos的提出者叫做Lamport，有很多分布 式的算法都是他提出的，他還是Latex的作者，大牛啊...）。想更加了解Paxos算法可以參考文獻[2]，很漂亮的一篇文章。

那么 這些和Chubby有什么關系呢？其實Chubby就是為了這個問題而構建出來的。只是它并不是一個Protocol或者是一個算法，而是google精 心設計的一個service。這個service不僅能夠解決一致性問題，還有其它的一些很實用的好處，會在下文慢慢介紹。

一個實例

在Google File System(GFS)中，有很多的server，這些server需要選舉其中的一臺作為master server。這其實是一個很典型的consensus問題，Value就是master server的地址。GFS就是用Chubby來解決的這個問題，所有的server通過Chubby提供的通信協議到Chubby server上創建同一個文件，當然，最終只有一個server能夠獲準創建這個文件，這個server就成為了master，它會在這個文件中寫入自己 的地址，這樣其它的server通過讀取這個文件就能知道被選出的master的地址。

Chubby是什么

從 上面的這個實例可以看出，Chubby首先是一個分布式的文件系統。Chubby能夠提供機制使得client可以在Chubby service上創建文件和執行一些文件的基本操作。說它是分布式的文件系統，是因為一個Chubby cell是一個分布式的系統，一般包含了5臺機器，整個文件系統是部署在這5臺機器上的。
但是，從更高一點的語義層面上，Chubby是一個lock service，一個針對松耦合的分布式系統的lock service。所謂lock service，就是這個service能夠提供開發人員經常用的“鎖”，“解鎖”功能。通過Chubby，一個分布式系統中的上千個client都能夠 對于某項資源進行“加鎖”，“解鎖”。
那么，Chubby是怎樣實現這樣的“鎖”功能的？就是通過文件。Chubby中的“鎖”就是文件，在上例 中，創建文件其實就是進行“加鎖”操作，創建文件成功的那個server其實就是搶占到了“鎖”。用戶通過打開、關閉和讀取文件，獲取共享鎖或者獨占鎖； 并且通過通信機制，向用戶發送更新信息。

綜上所述，Chubby是一個lock service，通過這個lock service可以解決分布式中的一致性問題，而這個lock service的實現是一個分布式的文件系統。

可能會有人問，為什么不是直接實現一個類似于Paxos算法這樣的Protocol來解決一致性問題，而是要通過一個lock service來解決？文獻[1]中提到，用lock service這種方式有幾個好處：
1.大部分開發人員在開始開發service的時候都不會考慮到這種一致性的問題，所以一開始都不會使用consensus protocol。只有當service慢慢成熟以后，才開始認真對待這個問題。采用lock service可以使得在保持原有的程序架構和通信機制的情況下，通過添加簡單的語句就可以解決一致性問題；
2.正如上文實例中所展現，很多時候并不僅僅是選舉出一個master，還需要將這個master的地址告訴其它人或者保存某個信息，這種時候，使用Chubby中的文件，不僅僅是提供鎖功能，還能在文件中記錄下有用的信息（比如master的地址）。所以，很多的開發人員通過使用Chubby來保存metadata和configuration。
3. 一個基于鎖的開發接口更容易被開發人員所熟悉。并不是所有的開發人員都了解consensus protocol的，但大部分人應該都用過鎖。
4. 一個consensus protocol一般來說需要使用到好幾臺副本來保證HA（詳見Paxos算法），而使用Chubby，就算只有一個client也能用。
可以看出，之所以用lock service這樣的形式，是因為Chubby不僅僅想解決一致性問題，還可以提供更多更有用的功能。事實上，Google有很多開發人員將Chubby當做name service使用，效果非常好。

關于lock service，還有兩個名詞需要提及。
一 個是advisory lock。Chubby中的lock都是advisory lock。所謂的advisory lock，舉個例子，就是說當有人將某個文件鎖住以后，如果有其他的人想不解鎖而直接訪問這個文件，這種行為是不會被阻止的。和advisory lock對應的是mandatory lock，即如果某個文件被鎖住以后，如果有其他的人直接訪問它，那么這種行為是會產生exception的。
另 一個是coarse-grained（粗顆粒度的）。Chubby的lock service是coarse-grained，就是說Chubby中的lock一般鎖住的時間都比較長，可能是幾小時或者幾天。與之對應的是fined-grained，這種lock一般只維持幾秒或者更少。這兩種鎖在實現的時候是會有很多不同的考慮的，比如coarse-grained的lock service的負載要小很多，因為加鎖解鎖并不會太頻繁。其它的差別詳見文獻[1]。


Chubby的架構

上圖就是Chubby的系統架構。 

基本上分為了兩部分：服務器一端，稱為Chubby cell；client一端，每個Chubby的client都有一個Chubby library。這兩部分通過RPC進行通信。
client端通過Chubby library的接口調用，在Chubby cell上創建文件來獲得相應的鎖的功能。
由于整個Chubby系統比較復雜，且細節很多，我個人又將整個系統分為了三個部分：
Chubby cell的一致性部分
分布式文件系統部分
client與Chubby cell的通信和連接部分

先從Chubby cell的一致性部分說起。
一般來說，一個Chubby cell由五臺server組成，可以支持一整個數據中心的上萬臺機器的lock service。
cell中的每臺server我們稱之為replicas（副本）。
當Chubby工作的時候，首先它需要從這些replicas中選舉出一個master。注意，這其實也是一個distributed consensus problem，也就是說Chubby也存在著分布式的一致性問題。Chubby是通過采用consensus protocol（很可能就是Paxos算法）來解決這個問題的。所以，Chubby的client用Chubby提供的lock service來解決一致性問題，而Chubby系統內部的一致性問題則是用consensus protocol解決的。
每個master都具有一定的期限，成為master lease。在這個期限中，副本們不會再選舉一個其它的master。
為 了安全性和容錯的考慮，所有的replicas（包括master）都維護的同一個DB的拷貝。但是，只有master能夠接受client提交的操作對DB進行讀和寫，而其它的replicas只是和master進行通信來update它們各自的DB。所以，一旦一個master被選舉出來后，所有的client端都之和master進行通信（如圖所示），如果是讀操作，那么master一臺機器就搞定了，如果是寫操作，master會通知其它的replicas進行update。這樣的話，一旦master意外停機，那么其它的replicas也能夠很快的選舉出另外一個master。

再說說Chubby的文件系統
前 文說過，Chubby的底層實現其實就是一個分布式的文件系統。這個文件系統的接口是類似于Unix系統的。例如，對于文件名“/ls/foo /wombat/pouch”，ls表示的是“lock service”，foo表示的是某個Chubby cell的名字，wombat/pouch則是這個cell上的某個文件目錄或者文件名。如果一個client端使用Chubby library來創建這樣一個文件名，那么這樣一個文件就會在Chubby cell上被創建。
Chubby的文件系統由于它的特殊用途做了很多 的簡化。例如它不支持文件的轉移，不記錄文件最后訪問時間等等。整個文件系統只包含有文件和目錄，統一稱為“Node”。文件系統采用Berkeley DB來保存Node的信息，主要是一種map的關系。Key就是Node的名字，Value就是Node的內容。
還有一點需要提及的 是，Chubby cell和client之間用了event形式的通知機制。client在創建了文件之后會得到一個handle，并且還可以訂閱一系列的event，例 如文件內容修改的event。這樣的話，一旦client相關的文件內容被修改了，那么cell會通過機制發送一個event來告訴client該文件被 修改了。

最后談談client與cell的交互部分
這里大致包含兩部分的內容：cache的同步機制和KeepAlive握手協議。
為 了降低client和cell之間通信的壓力和頻率，client在本地會保存一個和自己相關的Chubby文件的cache。例如如果client通過Chubby library在cell上創建了一個文件，那么在client本地，也會有一個相同的文件在cache中創建，這個cache中的文件的內容和cell上文件的內容是一樣的。這樣的話，client如果想訪問這個文件，就可以直接訪問本地的cache而不通過網絡去訪問cell。
cache有兩個狀態，有效和無效。當 有一個client要改變某個File的時候，整個修改會被master block，然后master會發送無效標志給所有cache了這個數據的client（它維護了這么一個表），當其它client端收到這個無效標志 后，就會將cache中的狀態置為無效，然后返回一個acknowledge；當master確定收到了所有的acknowledge之后，才完成整個modification。
需要注意的是，master并不是發送update給client而是發送無效標志給client。這是因為如果發送update給client，那么每 一次數據的修改都需要發送一大堆的update，而發送無效標示的話，對一個數據的很多次修改只需要發送一個無效標示，這樣大大降低了通信量。

至于KeepAlive協議，則是為了保證client和master隨時都保持著聯系。client和master每隔一段時間就會KeepAlive一次，這樣的話，如果master意外停機，client可以很快的知道這個消息，然后迅速的轉移到新的master上。并且，這種轉移對于client端的application是透明的，也就是說application并不會知道master發生了錯誤。關于cache和KeepAlive還有很多的 細節，想了解的讀文獻[1]吧。

總結

其實在我的這篇文章中，還有一個很大的主題沒有提及，那就是Chubby的容錯機制。基本上，容錯這個思想貫穿了文獻[1]的始終，也正是因此，我很難將 它單獨提取出來解釋，因為它散落在了Chubby系統設計的所有角落。我個人感覺，容錯是一個分布式系統設計的核心思想，在設計的時候要求考慮到所有可能 會發生的錯誤，不僅僅包括了硬件的錯誤，網絡的故障，還包括了開發人員可能出現的錯誤。我想，這是我讀這篇文章[1]最大的收獲。


/Files/mysileng/Paxos算法深入分析.doc