iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 19
0

Chubby

架構

下圖是一個Chubby的架構

  • 分成ClientChubby Cells
  • 五個replica servers組成一個高可用的Chubby Cells提供Lock Service給Client用。
  • Client透過chubby library和Chubby Service利用RPC

除了使用Chubby的為分散式系統以外,Chubby本身也是分散式系統,且為了提供上面的Client一致性的服務,Chubby Cell裡面的replica servers本身就必須是一致性的。

Chubby 內部的一致性

為了讓Chubby高可用,且支撐上千個Google內部的分散式服務,因此Chubby本身的設計也是分散式系統,理所當然就會需要共識演算法來達成一致性,且因為設計了Watch機制與事件通知機制,Chubby內部的replica servers必須是Strong Consistency。

雖然論文並沒有明說Chubby是採用哪種共識演算法,但是既然Mike Burrows本人對Paxos非常情有獨鍾,很大機率就是使用他們自己實現的Paxos且是Multi-Paxos,我們這邊做個簡介,比較與之前介紹的Paxos有什麼不同。

因此Chubby內部的一致性如下:

  1. 內部的5個replica servers先經過共識演算法選出一個Master (Leader)
  2. 與Paxos有多個Proposers不同
    • 這個Master只會有一個且有lease時間。也就是在此lease時間內都會只有這個Master來提出Proposer,來更新其他replica servers的訊息。
    • 就不需像原本的Paxos一樣多個Proposers每次都要兩階段提交(Prepare->Commit)過程,甚至必須競爭Proposer Number。
    • 這個Master可以不斷的向所有的replica servers commmit更新的資料。
  3. Client的讀寫都是經過Master,讀直接從Master讀,寫入必須等待Master利用Paxos共識演算法同步replica server才返回寫成功。
  4. Master失效的話,replica servers可以重新做Leader Election。

Paxos如果發生Partition,比方說3:2,因為2個replica servers不過半數。所以如果client對那2個servers發出請求,會顯示不可用,Availability被交換掉。只有那3個servers還可以運作Paxos協定所以可以使用。

Lock 的實作 與 File System

File, Directory 為 Node

我們先看Chubby的Interface,了解Client如何使用這個Lock Service,再來看他怎麼實作Lock。

  1. Node: Chubby的底層實際上是一個分散式文件系統(Distributed File System),提供一個類似UNIX的文件系統,因此包含了Files和Directory來存儲Data。而不管是File還是Directory都統稱為 Node,名字在系統唯一。

  2. /ls/foo/wombat/pouch:

    • ls: lock service
    • foo: Chubby cell
      (5個servers組成一個Cell提供Chubby服務,Google內部有好幾個Chubby Cell)
    • /wombat/pouch: Directory 和 File Name
  3. Ephemeral Node: 該Node的生命週期等於Client的連接時間,Client離線或是一個Node沒有被任意Client打開,此Node會被刪除,可以用來判斷Client是否仍然活著。另有Permanent Node

  4. Handle: Clients Open/Create Node,會得到類似UNIX的File Discriptor的Handle以訪問該Node,包含:

    • check digits: 避免Client偽造或是猜到Handle
    • sequence number: Chubby Master可以用此seq來判斷這個Handle是之前的Master產生的還是自己。

Node

Node除了本質上是一個File或是Directory

Node含有以下資訊:

  • Client儲存的Data
  • access control lists (ACL): 更改ACL共3種,創建實際成自parent node,可以覆蓋。
  • Instance number: 比之前創建的同名Node還大。
  • Content generation number: 每當Data被更新就增加,用來判斷資料是否被更新。
  • Lock generation Number: 當此Node被一個Client從Free到Held就增加,視為鎖號。
  • ACL generation number: 當ACL被更新就增加。
  • 64-bit file-content checksum: 比對文件內容

Node 為 Lock 的實作方法 & Sequencer

每一個Node都可以被拿來作為 advisory reader/writer lock 使用。

  1. 先說Advisory與Mandatory Lock差別

    • Mandatory Lock: 當一個資源或是文件被Lock住後,其他的Client皆無法在讀取查看該文件,返回錯誤。
    • Advisory Lock: 反之,即使該資源或是文件被Lock住,Client仍然可以讀取查看該資源,因此只有當其他Client也想要取得Lock時,會出現錯誤。

    原因:

    • Chubby的Lock可能被用在其他服務的資源上,如果是Mandatory Lock,但是該服務其實允許資源被鎖住仍可讀取,則不滿足該服務的使用情境,還必須做改寫。
    • 當一個資源目前被Chubby鎖住,結果為了debug方便,使用者必須暫停Chubby服務來解鎖,才能查看資源文件狀態。
    • bug的發生,跟這個鎖允不允許使用者讀取critical section的資源不怎麼有關,因此Mandatory Lock效益不大,可以鎖就好。
  2. 使用
    (1). 每一個Node都是Lock,有兩種模式 (都是Advisory Lock)

    • exclusive (writer) mode: 只限一個Client使用
    • shared (reader) mode: 多個Clients使用

    回過頭來利用Multithreading的經驗想一下什麼時候會用Lock,就是有好幾個processes都會操作共用資源時嘛。
    除了這些是平行發生的,在網路的世界中,還有訊息延遲或是亂序的情況發生。
    所以其實前面介紹ACID、DB的Transacrion、共識演算法,其實有一部份在講的是 sequentialized
    而Chubby Lock Service最主要就是解決了這個問題,他使得使用同一個Lock的請求被 sequentialized
    我們來看看怎麼用。

    (2). Sequencer
    舉一個簡單的例子,如果一個Key-Value Store是需要被Lock住的共享資源,我希望對這個儲存服務的操作被 sequentialized,要求對Key-Value Store的更新都必須拿到Chubby Locks才能做事。

    1. 當一個Client acquire a given lock (of a node),他會取的該Lock(Node)的Sequencer,這個東西包含。
      • Lock的名稱(Node)
      • 是哪一種Mode(read, write)
      • Lock generation Number(Node的Metadata),每次取得與釋放會增加,故唯一可判斷此Lock新舊。
    2. 這個client可以將此Sequencer遞給另外一個Service,表示自己拿到Lock,有這個權限。
    3. 此服務拿Sequencer再去跟Chubby比對,確認是最新合法的Lock允許了Client的操作請求。

搭配NodeAcquire Lock得到的Sequencer我們就可以實現與Multithreading一樣的Lock概念。

圖解

範例一

  1. q 為Key-Value儲存服務,p為一個process。p 先向Chubby acquire 一個 Lock。

  2. p要更新儲存的資料時,將取得Sequencer傳給 q,q去向Chubby驗整正確性與是否最新,同意請求。

  3. 每次操作都先拿取Lock

以上就是很基本Chubby Lock Service使用。

範例二 - Leader Election

  1. Leader Election
    如果你只是像Kafka或是Hadoop這種要選Leader,不是需要一致性資料的儲存服務,那選Leader就不用像Raft還要比較log新舊或是一對term限制。
    直接搭配Chubby就非常簡單,
    這就是一個搭配File System加上Lock Service應用的情境。

    1. 每一個Process都去Chubby搶著acquire "myservice/primary" Node的Lock。
    2. 誰先創建誰就可以把自己的ip寫進去,他就是Leader

    其他人只要去Watch的 "myservice/primary" Node 就可以知道現在Leader是否還活著,因為如果Leader斷線Chubby Node也會有反應跟事件通知。

夠簡單吧!

  1. New/Old Leader
    那如果Old Leader失效重啟他以為自己還是Leader,仍然要求別的replica server運作呢?搭配剛剛學到的Sequencer我們就可以運作起來如下。
    Leader取得Lock也會拿到Sequencer

    • 每一次通知replica servers去做事都必須把自身的Sequencer給他

    • replica servers拿著Sequencer去Chubby驗證,就知道這個Leader是新的還是舊的了

也很簡單吧!

小結

Chubby 其實是一個蠻強大且方便的系統,在分散式的環境中提供了很多功能,包含File System、Event-Watch、Lock Service等。

但是就像Borg或是很多Google的論文一樣,非常工程經驗導向,
有很多的名詞與定意與設計,卻又同時不開源,導致入門門檻很高。
論文有時看起來似懂非懂,希望上面的解釋搭配兩個小例子可以讓大家有點具體的印象。

如果還是不太能理解,沒關係我們之後拿Zookeeper來當例子,或是你本身有在用Zookeeper那一定非常有感,因為使用上是差不多的。

明天將要針對上面例子提到的問題,怎麼解決效能問題來介紹。

Chubby整理成筆記好難 =_=


上一篇
Day 18 - Google Distributed Lock Service - Chubby(上)
下一篇
Day 20 - Google Distributed Lock Service - Chubby(下)
系列文
分散式系統 - 在分散的世界中保持一致30

尚未有邦友留言

立即登入留言