一、分布式鎖服務

今天，要接觸有些難理解的知識點了，這也許就是涉及到當時趙致琢老師強調的在中國沒人能有資格講和講得清的一塊—分布式算法。說實話，這塊看了兩遍了，到現在還不敢說自己人懂了一半啊·！

Chubby

?Google設計的提供粗粒度鎖服務(???)的一個文件系統，它基于松耦合分布式系統，解決了分布的一致性問題

——一種建議性的鎖(相信看過《UNIX環境下高級編程》的人對建議性的鎖這個名詞不會陌生)，而不是一種強制性的鎖：具有更大的靈活性

?GFS使用Chubby選取一個GFS主服務器

?Bigtable使用Chubby指定一個主服務器并發現、控制與其相關的子表服務器

?Chubby還可以作為一個穩定的存儲系統存儲包括元數據在內的小數據

?Google內部還使用Chubby進行名字服務（Name Server）

想像一下，要在大規模集群的條件下，保證所有指令和數據的一致性（即：在初始狀態相同情況下，要求各結點接收到同樣相同指令，且最終狀態一致）會遇到什么樣的困難？——這也許正是分布式算法要發揮作用的境地，很多時候設計的算法根本不可能會是十全十美。Chubby中即要用到Paxos算法

1、Paxos算法

試想想：該方案存在什么缺陷？？？？

試圖由以下三點來保證數據的一致性:

（1）決議只有被proposers提出后才能批準

（2）每次只批準一個決議

（3）只有決議確定被批準后learners才能獲取這個決議

系統的約束條件：

p1:每個acceptor只接受它得到的第一個決議

p1表明每個可以接收到多個決議，為區分，對每個決議進行編號，后得到的決議編號要大于先到的編號；p1不是很完備!!(??一個問題可能是：對于每個結點，其收到的所謂第一個編號是否都是一樣？？)

P2：一旦某個決議通過，之后通過的決議必須和該決議保持一致

P1+P2——>P2a:一旦某個決議V得到通過，之后任何acceptor再批準的決議必須是V

P2a和P1是有矛盾的!(我的理解是：有可能這個V不是某個結點收到的第一個決議)

P2a——》P2b:一旦某個決議V得到通過，之后任何proposer再提出的決議必須是V

P1和P2b保證條件（2），彼此之間不存在矛盾。但是P2b很難通過一種技術手段來實現它，因此提出了一個蘊涵P2b的約束P2c?

P2b——》P2c:如果一個編號為n的提案具有值v，那么存在一個“多數派”，要么它們中沒有誰批準過編號小于n的任何提案，要么它們進行的最近一次批準具有值v

決議通過的兩個階段：

準備階段：proposers選擇一個提案并將它的編號設為n，然后將它發送給acceptors中的一個“多數派”。Acceptors收到后，如果提案的編號大于它已經回復的所有消息，則acceptors將自己上次的批準回復給proposers，并不再批準小于n的提案 （那么，可以問問：如果小于它已經回復的所有消息呢？這個思考之后，對算法的流程就有個印象——但似乎這樣一想，這中間的延遲倒很是個問題，看來，這個算法還是未弄懂！！）

批準階段：當proposers接收到acceptors 中的這個“多數派”的回復后，就向回復請求的acceptors發送accept請求，在符合acceptors一方的約束條件下，acceptors收到accept請求后即批準這個請求?

解決一致性問題算法：為了減少決議發布過程中的消息量，acceptors將這個通過的決議發送給learners的一個子集，然后由這個子集中的learners去通知所有其他的learners；

特殊情況：如果兩個proposer在這種情況下都轉而提出一個編號更大的提案，那么就可能陷入活鎖。此時需要選舉出一個president，僅允許 president提出提案

2、Chubby的系統設計

Chubby中還添加了一些新的功能特性；這種設計主要是考慮到以下幾個問題:

1、開發者初期很少考慮系統的一致性，但隨著開發進行，問題會變得越來越嚴重。單獨的鎖服務可以保證原有系統架構不會發生改變，而使用函數庫很可能需要對系統架構做出大幅度的改動

2、系統中很多事件發生是需要告知其他用戶和服務器，使用一個基于文件系統的鎖服務可以將這些變動寫入文件中。有需要的用戶和服務器直接訪問這些文件即可，避免因大量系統組件之間事件通信帶來系統性能下降

3、基于鎖的開發接口容易被開發者接受。雖然在分布式系統中鎖的使用會有很大的不同，但是和一致性算法相比，鎖顯然被更多的開發者所熟知

Paxos算法實現過程中需要一個“多數派”就某個值達成一致，本質上就是分布式系統中常見的quorum機制；為保證系統高可用性，需要若干臺機器，但使用單獨鎖服務的話一臺機器也能保證這種高可用性

Chubby設計過程中一些細節問題值得關注：

在Chubby系統中采用了建議性的鎖而沒有采用強制性的鎖。兩者的根本區別在于用戶訪問某個被鎖定的文件時，建議性的鎖不會阻止訪問，而強制性的鎖則會阻止訪問，實際上這是為了方便系統組件之間的信息交互

另外，Chubby還采用了粗粒度（Coarse-Grained）鎖服務而沒有采用細粒度（Fine-Grained）鎖服務，兩者的差異在于持有鎖的時間，細粒度的鎖持有時間很短

3、Chubby中的Paxos算法

(個人疑問：從上面來看，似乎上面給我們的啟發是——我們無需在整個系統的每個環節保持數據和指令的一致性，只需其操作日志是一致，那么說明其操作一致？？)

?Chubby設計者借鑒了Paxos的兩種解決機制：給協調者指派序號或限制協調者可以選擇的值

?? F指派序號的方法

????? –（1）在一個有n個副本系統中，為每個副本分配一個id ，其中? 0≤ir≤n-1。則副本的序號，其中k的初始值為0 ("則副本的序號，其中k的初始值為0?"這句話可能寫得有點問題，這里沒看懂)

????? –（2）某個副本想成為協調者之后，它就根據規則生成一個比它以前的序號更大的序號（實際上就是提高k的值），并將這個序號通過propose消息廣播給其他所有的副本

????? –（3）如果接受到廣播的副本發現該序號比它以前見過的序號都大，則向發出廣播的副本返回一個promise消息，并且承諾不再接受舊的協調者發送的消息。如果大多數副本都返回了promise消息，則新的協調者就產生了

??? F限制協調者可以選擇的值

????? –Paxos強制新的協調者必須選擇和前任相同的值

?Chubby做了一個重要優化來提高系統效率—在選擇某一個副本作為協調者之后就長期不變，此時協調者就被稱為主服務器（Master）

? F客戶端的數據請求由主服務器完成，Chubby保證在一定時間內有且僅有一個主服務器，這個時間就稱為主服務器租約期（Master Lease）

? F客戶端需要確定主服務器的位置，可向DNS發送一個主服務器定位請求，非主服務器的副本將對該請求做出回應

? Chubby對于Paxos論文中未提及的一些技術細節進行了補充，所以Chubby的實現是基于Paxos，但其技術手段更加的豐富，更具有實踐性

4、Chubby文件系統

Chubby系統本質上就是一個分布式的、存儲大量小文件的文件系統，它所有的操作都是在文件的基礎上完成

?Chubby最常用的鎖服務中，每一個文件就代表一個鎖，用戶通過打開、關閉和讀取文件，獲取共享（Shared）鎖或獨占（Exclusive）鎖

?選舉主服務器過程中，符合條件的服務器都同時申請打開某個文件并請求鎖住該文件

?成功獲得鎖的服務器自動成為主服務器并將其地址寫入這個文件夾，以便其他服務器和用戶可以獲知主服務器的地址信息

?Chubby的文件系統和UNIX類似

?? ?F例如在文件名“/ls/foo/wombat/pouch”中，ls代表lock service，這是所有Chubby文件系統的共有前綴；foo是某個單元的名稱；/wombat/pouch則是foo這個單元上的文件目錄或者文件名

?? Google對Chubby做了一些與UNIX不同的改變

???? F例如Chubby不支持內部文件的移動；不記錄文件的最后訪問時間；另外在Chubby中并沒有符號連接（Symbolic Link，又叫軟連接，類似于Windows系統中的快捷方式）和硬連接（HardLink，類似于別名）的概念

?在具體實現時，文件系統由許多節點組成，分為永久型和臨時型，每個節點就是一個文件或目錄。節點中保存著包括ACL（Access Control List，訪問控制列表）在內的多種系統元數據 o

5、通信協議

故障處理 客戶端租約過期

?客戶端向主服務器發出一個KeepAlive請求（上圖1）

?如果有需要通知的事件時則主服務器會立刻做出回應，否則等到客戶端的租約期C1快結束的時候才做出回應（圖2），并更新主服務器租約期為M2

?客戶端接到回應后認為該主服務器仍處于活躍狀態，于是將租約期更新為C2并立刻發出新的KeepAlive請求（圖3）

?寬限期內，客戶端不會立刻斷開其與服務器端的聯系，而是不斷地做探詢，當它接到客戶端的第一個KeepAlive請求（圖4）時會拒絕（圖5）

?客戶端在主服務器拒絕后使用新紀元號來發送KeepAlive請求（圖6）

?新的主服務器接受這個請求并立刻做出回應（圖7）

如果客戶端接收到這個回應的時間仍處于寬限期內，系統會恢復到安全狀態，租約期更新為C3。如果在寬限期未接到主服務器的相關回應，客戶端終止當前的會話 主服務器出錯

正常情況下舊的主服務器出現故障后系統會很快地選舉出新的主服務器，新選舉需要經歷以下九個步驟：

（1）產生一個新的紀元號以便今后客戶端通信時使用，這能保證當前的主服務器不必處理針對舊的主服務器的請求

（2）只處理主服務器位置相關的信息，不處理會話相關的信息

（3）構建處理會話和鎖所需的內部數據結構

（4）允許客戶端發送KeepAlive請求，不處理其他會話相關的信息

（5）向每個會話發送一個故障事件，促使所有的客戶端清空緩存

（6）等待直到所有的會話都收到故障事件或會話終止

（7）開始允許執行所有的操作

（8）如果客戶端使用了舊的句柄則需要為其重新構建新的句柄

（9）一定時間段后（1分鐘），刪除沒有被打開過的臨時文件夾 ——如果這一過程在寬限期內順利完成，則用戶不會感覺到任何故障的發生，也就是說新舊主服務器的替換對于用戶來說是透明的，用戶感覺到的僅僅是一個延遲?

?系統實現時，Chubby還使用了一致性客戶端緩存（Consistent Client-Side Caching）技術，這樣做的目的是減少通信壓力，降低通信頻率

?? ?F在客戶端保存一個和單元上數據一致的本地緩存，需要時客戶可以直接從緩存中取出數據而不用再和主服務器通信

???? F當某個文件數據或者元數據需要修改時，主服務器首先將這個修改阻塞；然后通過查詢主服務器自身維護的一個緩存表，向對修改的數據進行了緩存的所有客戶端發送一個無效標志（Invalidation）

??? F客戶端收到這個無效標志后會返回一個確認（Acknowledge），主服務器在收到所有的確認后才解除阻塞并完成這次修改
——這個過程的執行效率非常高，僅僅需要發送一次無效標志即可，因為對于沒有返回確認的節點，主服務器直接認為其是未緩存

6、正確性與性能

一致性

?每個Chubby單元是由五個副本組成的，這五個副本中需要選舉產生一個主服務器，這種選舉本質上就是一個一致性問題。實際執行過程中，Chubby使用Paxos算法來解決

?? ?

?主服務器產生后客戶端的所有讀寫操作都是由主服務器來完成的

?a讀操作很簡單，客戶直接從主服務器上讀取所需數據即可

?a寫操作就會涉及數據一致性的問題；為了保證客戶的寫操作能夠同步到所有的服務器上，系統再次利用了Paxos算法
性能優化

?為滿足系統高可擴展性，Chubby目前已經采取了一些措施：比如提高主服務器默認的租約期、使用協議轉換服務將Chubby協議轉換成較簡單的協議、客戶端一致性緩存等；除此之外，Google的工程師們還考慮使用代理（Proxy）和分區（Partition）技術

?? ?

? a代理可以減少主服務器處理KeepAlive以及讀請求帶來的服務器負載，但是它并不能減少寫操作帶來的通信量

?a使用分區技術的話可以將一個單元的命名空間（NameSpace）劃分成N份。除了少量的跨分區通信外，大部分的分區都可以獨自地處理服務請求。通過分區可以減少各個分區上的讀寫通信量，但不能減少KeepAlive請求的通信量

總結

以上是生活随笔為你收集整理的《云计算》学习笔记3——Google的云计算原理与应用(分布式锁服务——Chubby)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。