Google利器之Chubby.doc

/historyasamirror/article/details/3870168Google利器之Chubby 分類： 分布式系統(tǒng)（Distributed System）2009-02-09 11:3712914人閱讀評論(15)收藏舉報(bào)寫完了Google Cluster，該輪到Chubby了。參考文獻(xiàn)：1 The Chubby lock service for loosely-coupled distributed systems 2 Paxos Made Simple聲明文中大部分的觀點(diǎn)來自于文獻(xiàn)1中的描述，但也夾雜了部分本人自己的理解，所以不能保證本文的正確性。真想深入了解Chubby還是好好讀原版論文吧：)前言MapReduce很多人已經(jīng)知道了，但關(guān)于Chubyy似乎熟悉它的就非常有限，這倒是不奇怪，因?yàn)镸apReduce是一個(gè)針對開發(fā)人員的ProgrammingModel，自然會(huì)有很多人去學(xué)習(xí)它，而Chubby更多的是一種為了實(shí)現(xiàn)MapReduce或者Bigtable而構(gòu)建的內(nèi)部的 工具，對于開發(fā)人員來說基本上是透明的。文獻(xiàn)1我反復(fù)讀了至少有兩三天，但感覺也只是一個(gè)囫圇吞棗的結(jié)果，里面有很多工程實(shí)現(xiàn)上的細(xì)節(jié)，如果不是自己 親自去設(shè)計(jì)或者實(shí)現(xiàn)，很難體會(huì)到其中的道理和奧妙。但是，對于這樣一個(gè)分布式service的研究，還是讓我對一個(gè)分布式系統(tǒng)的結(jié)構(gòu)和設(shè)計(jì)思想有了更加直 觀的感覺。從distributed consensus problem說起distributed consensus problem(分布的一致性問題)是分布式算法中的一個(gè)經(jīng)典問題。它的問題描述大概是這樣的：在一個(gè)分布式系統(tǒng)中，有一組的Process，它們需要確 定一個(gè)Value。于是每個(gè)Process都提出了一個(gè)Value，consensus就是指只有其中的一個(gè)Value能夠被選中作為最后確定的值，并且 當(dāng)這個(gè)值被選出來以后，所有的Process都需要被通知到。表面上看，這個(gè)問題很容易解決。比如設(shè)置一個(gè)server，所有的process都 向這個(gè)server提交一個(gè)Value，這個(gè)server可以通過一個(gè)簡單的規(guī)則來挑選出一個(gè)Value（例如最先到達(dá)的Value被選中），然后由這個(gè)server通知所有的Process。但是在分布式系統(tǒng)中，就會(huì)有各種的問題發(fā)生，例如，這個(gè)server崩潰了怎么辦，所以我們可能需要有幾臺(tái)server共同決定。還有，Process提交Value的時(shí)間都不一樣，網(wǎng)絡(luò)傳輸過程中由于延遲這些Value到達(dá)server的順序也都沒有保證。為 了解決這個(gè)問題，有很多人提出了各種各樣的Protocol，這些Protocol可以看做是一組需要遵循的規(guī)則，按照這些規(guī)則，這些Process就能 夠選舉出一個(gè)唯一的Value。其中，最有名的一個(gè)Protocol就是Paxos算法。（八卦一下，Paxos的提出者叫做Lamport，有很多分布 式的算法都是他提出的，他還是Latex的作者，大牛啊.）。想更加了解Paxos算法可以參考文獻(xiàn)2，很漂亮的一篇文章。那么 這些和Chubby有什么關(guān)系呢？其實(shí)Chubby就是為了這個(gè)問題而構(gòu)建出來的。只是它并不是一個(gè)Protocol或者是一個(gè)算法，而是google精 心設(shè)計(jì)的一個(gè)service。這個(gè)service不僅能夠解決一致性問題，還有其它的一些很實(shí)用的好處，會(huì)在下文慢慢介紹。一個(gè)實(shí)例在Google File System(GFS)中，有很多的server，這些server需要選舉其中的一臺(tái)作為master server。這其實(shí)是一個(gè)很典型的consensus問題，Value就是master server的地址。GFS就是用Chubby來解決的這個(gè)問題，所有的server通過Chubby提供的通信協(xié)議到Chubby server上創(chuàng)建同一個(gè)文件，當(dāng)然，最終只有一個(gè)server能夠獲準(zhǔn)創(chuàng)建這個(gè)文件，這個(gè)server就成為了master，它會(huì)在這個(gè)文件中寫入自己 的地址，這樣其它的server通過讀取這個(gè)文件就能知道被選出的master的地址。Chubby是什么從 上面的這個(gè)實(shí)例可以看出，Chubby首先是一個(gè)分布式的文件系統(tǒng)。Chubby能夠提供機(jī)制使得client可以在Chubby service上創(chuàng)建文件和執(zhí)行一些文件的基本操作。說它是分布式的文件系統(tǒng)，是因?yàn)橐粋€(gè)Chubby cell是一個(gè)分布式的系統(tǒng)，一般包含了5臺(tái)機(jī)器，整個(gè)文件系統(tǒng)是部署在這5臺(tái)機(jī)器上的。但是，從更高一點(diǎn)的語義層面上，Chubby是一個(gè)lock service，一個(gè)針對松耦合的分布式系統(tǒng)的lock service。所謂lock service，就是這個(gè)service能夠提供開發(fā)人員經(jīng)常用的“鎖”，“解鎖”功能。通過Chubby，一個(gè)分布式系統(tǒng)中的上千個(gè)client都能夠 對于某項(xiàng)資源進(jìn)行“加鎖”，“解鎖”。那么，Chubby是怎樣實(shí)現(xiàn)這樣的“鎖”功能的？就是通過文件。Chubby中的“鎖”就是文件，在上例 中，創(chuàng)建文件其實(shí)就是進(jìn)行“加鎖”操作，創(chuàng)建文件成功的那個(gè)server其實(shí)就是搶占到了“鎖”。用戶通過打開、關(guān)閉和讀取文件，獲取共享鎖或者獨(dú)占鎖； 并且通過通信機(jī)制，向用戶發(fā)送更新信息。綜上所述，Chubby是一個(gè)lock service，通過這個(gè)lock service可以解決分布式中的一致性問題，而這個(gè)lock service的實(shí)現(xiàn)是一個(gè)分布式的文件系統(tǒng)?？赡軙?huì)有人問，為什么不是直接實(shí)現(xiàn)一個(gè)類似于Paxos算法這樣的Protocol來解決一致性問題，而是要通過一個(gè)lock service來解決？文獻(xiàn)1中提到，用lock service這種方式有幾個(gè)好處：1.大部分開發(fā)人員在開始開發(fā)service的時(shí)候都不會(huì)考慮到這種一致性的問題，所以一開始都不會(huì)使用consensus protocol。只有當(dāng)service慢慢成熟以后，才開始認(rèn)真對待這個(gè)問題。采用lock service可以使得在保持原有的程序架構(gòu)和通信機(jī)制的情況下，通過添加簡單的語句就可以解決一致性問題；2.正如上文實(shí)例中所展現(xiàn)，很多時(shí)候并不僅僅是選舉出一個(gè)master，還需要將這個(gè)master的地址告訴其它人或者保存某個(gè)信息，這種時(shí)候，使用Chubby中的文件，不僅僅是提供鎖功能，還能在文件中記錄下有用的信息（比如master的地址）。所以，很多的開發(fā)人員通過使用Chubby來保存metadata和configuration。3. 一個(gè)基于鎖的開發(fā)接口更容易被開發(fā)人員所熟悉。并不是所有的開發(fā)人員都了解consensus protocol的，但大部分人應(yīng)該都用過鎖。4. 一個(gè)consensus protocol一般來說需要使用到好幾臺(tái)副本來保證HA（詳見Paxos算法），而使用Chubby，就算只有一個(gè)client也能用?？梢钥闯?，之所以用lock service這樣的形式，是因?yàn)镃hubby不僅僅想解決一致性問題，還可以提供更多更有用的功能。事實(shí)上，Google有很多開發(fā)人員將Chubby當(dāng)做name service使用，效果非常好。關(guān)于lock service，還有兩個(gè)名詞需要提及。一 個(gè)是advisory lock。Chubby中的lock都是advisory lock。所謂的advisory lock，舉個(gè)例子，就是說當(dāng)有人將某個(gè)文件鎖住以后，如果有其他的人想不解鎖而直接訪問這個(gè)文件，這種行為是不會(huì)被阻止的。和advisory lock對應(yīng)的是mandatory lock，即如果某個(gè)文件被鎖住以后，如果有其他的人直接訪問它，那么這種行為是會(huì)產(chǎn)生exception的。另 一個(gè)是coarse-grained（粗顆粒度的）。Chubby的lock service是coarse-grained，就是說Chubby中的lock一般鎖住的時(shí)間都比較長，可能是幾小時(shí)或者幾天。與之對應(yīng)的是fined-grained，這種lock一般只維持幾秒或者更少。這兩種鎖在實(shí)現(xiàn)的時(shí)候是會(huì)有很多不同的考慮的，比如coarse-grained的lock service的負(fù)載要小很多，因?yàn)榧渔i解鎖并不會(huì)太頻繁。其它的差別詳見文獻(xiàn)1。Chubby的架構(gòu)上圖就是Chubby的系統(tǒng)架構(gòu)。 基本上分為了兩部分：服務(wù)器一端，稱為Chubby cell；client一端，每個(gè)Chubby的client都有一個(gè)Chubby library。這兩部分通過RPC進(jìn)行通信。client端通過Chubby library的接口調(diào)用，在Chubby cell上創(chuàng)建文件來獲得相應(yīng)的鎖的功能。由于整個(gè)Chubby系統(tǒng)比較復(fù)雜，且細(xì)節(jié)很多，我個(gè)人又將整個(gè)系統(tǒng)分為了三個(gè)部分：Chubby cell的一致性部分分布式文件系統(tǒng)部分client與Chubby cell的通信和連接部分先從Chubby cell的一致性部分說起。一般來說，一個(gè)Chubby cell由五臺(tái)server組成，可以支持一整個(gè)數(shù)據(jù)中心的上萬臺(tái)機(jī)器的lock service。cell中的每臺(tái)server我們稱之為replicas（副本）。當(dāng)Chubby工作的時(shí)候，首先它需要從這些replicas中選舉出一個(gè)master。注意，這其實(shí)也是一個(gè)distributed consensus problem，也就是說Chubby也存在著分布式的一致性問題。Chubby是通過采用consensus protocol（很可能就是Paxos算法）來解決這個(gè)問題的。所以，Chubby的client用Chubby提供的lock service來解決一致性問題，而Chubby系統(tǒng)內(nèi)部的一致性問題則是用consensus protocol解決的。每個(gè)master都具有一定的期限，成為master lease。在這個(gè)期限中，副本們不會(huì)再選舉一個(gè)其它的master。為 了安全性和容錯(cuò)的考慮，所有的replicas（包括master）都維護(hù)的同一個(gè)DB的拷貝。但是，只有master能夠接受client提交的操作對DB進(jìn)行讀和寫，而其它的replicas只是和master進(jìn)行通信來update它們各自的DB。所以，一旦一個(gè)master被選舉出來后，所有的client端都之和master進(jìn)行通信（如圖所示），如果是讀操作，那么master一臺(tái)機(jī)器就搞定了，如果是寫操作，master會(huì)通知其它的replicas進(jìn)行update。這樣的話，一旦master意外停機(jī)，那么其它的replicas也能夠很快的選舉出另外一個(gè)master。再說說Chubby的文件系統(tǒng)前 文說過，Chubby的底層實(shí)現(xiàn)其實(shí)就是一個(gè)分布式的文件系統(tǒng)。這個(gè)文件系統(tǒng)的接口是類似于Unix系統(tǒng)的。例如，對于文件名“/ls/foo /wombat/pouch”，ls表示的是“l(fā)ock service”，foo表示的是某個(gè)Chubby cell的名字，wombat/pouch則是這個(gè)cell上的某個(gè)文件目錄或者文件名。如果一個(gè)client端使用Chubby library來創(chuàng)建這樣一個(gè)文件名，那么這樣一個(gè)文件就會(huì)在Chubby cell上被創(chuàng)建。Chubby的文件系統(tǒng)由于它的特殊用途做了很多 的簡化。例如它不支持文件的轉(zhuǎn)移，不記錄文件最后訪問時(shí)間等等。整個(gè)文件系統(tǒng)只包含有文件和目錄，統(tǒng)一稱為“Node”。文件系統(tǒng)采用Berkeley DB來保存Node的信息，主要是一種map的關(guān)系。Key就是Node的名字，Value就是Node的內(nèi)容。還有一點(diǎn)需要提及的 是，Chubby cell和client之間用了event形式的通知機(jī)制。client在創(chuàng)建了文件之后會(huì)得到一個(gè)handle，并且還可以訂閱一系列的event，例 如文件內(nèi)容修改的event。這樣的話，一旦client相關(guān)的文件內(nèi)容被修改了，那么cell會(huì)通過機(jī)制發(fā)送一個(gè)event來告訴client該文件被 修改了。最后談?wù)刢lient與cell的交互部分這里大致包含兩部分的內(nèi)容：cache的同步機(jī)制和KeepAlive握手協(xié)議。為 了降低client和cell之間通信的壓力和頻率，client在本地會(huì)保存一個(gè)和自己相關(guān)的Chubby文件的cache。例如如果client通過Chubby library在cell上創(chuàng)建了一個(gè)文件，那么在client本地，也會(huì)有一個(gè)相同的文件在cache中創(chuàng)建，這個(gè)cache中的文件的內(nèi)容和cell上文件的內(nèi)容是一樣的。這樣的話，client如果想訪問這個(gè)文件，就可以直接訪問本地的cache而不通過網(wǎng)絡(luò)去訪問cell。cache有兩個(gè)狀態(tài)，有效和無效。當(dāng) 有一個(gè)client要改變某個(gè)File的時(shí)候，整個(gè)修改會(huì)被master block，然后master會(huì)發(fā)送無效標(biāo)志給所有cache了這個(gè)數(shù)據(jù)的client（它維護(hù)了這么一個(gè)表），當(dāng)其它c(diǎn)lient端收到這個(gè)無效標(biāo)志 后，就會(huì)將cache中的狀態(tài)置為無效，然后返回一個(gè)acknowledge；當(dāng)master確定收到了所有的acknowledge之后，才完成整個(gè)modification。需要注意的是，master并不是發(fā)送update給client而是發(fā)送無效標(biāo)志給client。這是因?yàn)槿绻l(fā)送update給client，那么每 一次數(shù)據(jù)的修改都需要發(fā)送一大堆的update，而發(fā)送無效標(biāo)示的話，對一個(gè)數(shù)據(jù)的很多次修改只需要發(fā)送一個(gè)無效標(biāo)示，這樣大大降低了通信量。至于KeepAlive協(xié)議，則是為了保證client和master隨時(shí)都保持著聯(lián)系。client和master每隔一段時(shí)間就會(huì)KeepAlive一次，這樣的話，如果master意外停機(jī)，client可以很快的知道這個(gè)消息，然后迅速的轉(zhuǎn)移到新的master上。并且，這種轉(zhuǎn)移