Chubby

Caching

首先Chubby應用在Google內部，必須支撐上千個Client，每一個Client都是另外一個分散式系統與服務。因此Chubby必須有很好的效能，另外應用也是一個讀多於寫的情境。

如同在設計時採用Coarse-grained lock，降低Client對Chubby的頻繁溝通，以增加Chubby效能。

Cache 讀寫設計

Chubby希望以犧牲寫入的效能增加讀取的效能。
因此Chubby的Caching機制為Consistent Cachinig，減少Client直接對Chubby的讀請求，並且讀取一定是最新的資料且一定正確，否則返回錯誤(Strong Consistency)。

• Client端的Cache可以儲存Node Data、Metadata、Handle與Lock...等
• Chubby Master維護一個list來記錄目前有caching的client與caching內容
• Chubby Master收到寫入請求時，為了保證Client的Consistent Caching
  • 寫入為blocking call
  • 通知相關的Client invalid自己的cache
  • 等待Client完成後
  • Master收到所有的Client確認訊息或是Lease過期才執行寫入請求
• 可以看到這就是所謂的「犧牲寫入效能，增加讀取的一致性，減少對Chubby的直接讀取」

什麼是Lease (租期)

Cache lease設計

除了上面寫入時，必須invalid自己的cache外，還引入了lease設計，什麼意思呢？

也就是說Cache是有有效期限的，當Cache過期後，Cache會自動失效，以避免Client失效沒辦法回覆Master。

我們綜合上面兩點來看昨天的Lock應用還記得

1. process p 向 Chubby Acquire() 一個Lock
2. key-value store q利用Lock的sequencer來驗證可以執行p的請求

今天我們將Cache與租期的使用加進去

• 透過Cache的機制，q不用每次都拿Sequencer去Chubby驗證

• 當p release lock後表示有更新，q會收到來自Chubby的invalidate cache訊息
• q如果運作正常可以回覆Chubby，Chubby就會 Release() Lock

• 而lease的用意就是在如果q失效沒有回覆或是訊息丟失，Chubby會等待lease過期，這段期間不允許有人在對這個Node Acquire() Lock

以上就是Cache讀寫機制，與Cache Lease機制，是一個很好的設計參考！

Notification

Client可以向Chubby訂閱事件
每當有事件發生，Chubby會透過Client內部的Chubby Library來通知Client。
事件包含以下:

• Node(File, Directory) Data被更新
• 屬於這個client的node，其child node的新增刪除與修改
• Chubby Cell選出新的Master (才知道找誰發送請求)
• Client取得的Handle被invalidated
• Lock acquired / released

Client與Chubby Cell互動

Session - Cell-Client relationship

Client跟Chubby連線期間
Chubby藉由Session來管理這個Client，Session也會有租約(lease)期限

而Client從Chubby這邊取得的

• Locks
• Cache
• Handles

皆跟Session有同樣的有效期限

KeepAlive

那Client與Chubby怎麼通訊呢？
就是透過KeepAlive RPC call，一個類似handshaking的方法來維護自己的Session。

• Master 會收到來自Client送來的KeepAlive message
• KeepAlive RPC call會被Master block住，直到以下兩種狀況
  1. 直到Session lease要到期了，返回並通知Client要到期了
  2. 當Master要invalidate Client的Cache時，通知Client要清除Cache了。

我們來分析一下這個KeepAlive blocking call的好處

Chubby 對 Client

• 正常情況下，Client發起KeepAlive在Chubby那邊建立Session，Chubby會Block此KeepAlive直到租約到期
  • 對於每個Client的連線皆有一個blocking call在Chubby，便於管理每一個Client。
  • 如果Client要繼續保持連線，就在上一個KeepAlive被返回後，在發送一個新的
  • 如果Client沒有發送新的KeepAlive，則租約到期，Chubby可以invalidate相關的Lock、Handles與Cache
  • 如果Cache要更新，也可以透過返回KeepAlive夾帶訊息通知Client，Client也可以藉著建立一個新的KeepAlive傳送清除Cache完成的訊息給Master

Client 對 Chubby - Jeopardy

• Client也會有一個Local Lease Timeout，跟Master那邊的Session差不多一樣的時間長
• 但是因為我們知道分散式系統的時間不可靠，因此Local跟Master那邊的時長不一定一樣
• 因為KeepAlive在租約到期後正常情況下，會由Master返回。如果是Client這邊的Local Lease Timeout比Master先到期，Client會進入一個叫做Jeopardy的狀態。
  • Jeopardy: Client認為Master要返回KeepAlive訊息了。所以如果Master沒有返回KeepAlive，表示Chubby出狀況，可能Master死掉了，此時Client會進入Jeopardy，並等待大約45秒的寬限期。
    • 此時Client可以主動清除自己的Cache
    • 並等待Chubby返回KeepAlive。
    • 如果Chubby在寬限期內回覆KeepAlive，則Client正常繼續維護Cache
    • 如果仍然沒有返回，Client主動視為Session失效，會再重新發送KeepAlive嘗試建立Session。
• 因為有Session的機制，因此Client透過取得的Handle對Node做操作時，如果有一個操作因為Session結束而失敗，可以保證後面的所有操作也會因為Session結束而失敗，Client可以清楚知道某個時刻之前的操作是成功的，該時刻之後的操作是失敗的，而不會混亂。

故障恢復

當Chubby的Master失效後，其餘的replica servers會透過共識演算法選出新的Master。

1. Chubby 進入新的任期 epoch (term)
2. 利用備份且存在Disk中的replica data恢復Session、Lock等與Client有關的訊息。
3. Client延續上面的Jeopardy嘗試再次發送KeepAlive
4. 此時Client的KeepAlive會帶著比較舊的epoch，因此被拒絕，但是也會知道新的Master epoch。
5. 第二個KeepAlive建立新的Session，新的Master直接返回KeepAlive讓Client也可以設定新的Local Lease Timeout
6. 第二個KeepAlive回復原本被Master block住的運作模式。

如下圖圖解:

一些啟示

Chubby在Google內部支撐了上千個分散式服務，橫跨好幾個地區，因此如何有效的增加效能與分散責任是我們可以從Chubby學到的。

Scaling

而我們一路看下來可以發現Chubby最大的努力在於減少Client與Chubby Master的通訊次數，而非提高Chubby Master處理請求的效能！

1. 利用 "ls/chubbycell/parentnode/childnode"，來讓不同的Chubby Cell支援Google內部不同地區的分散式服務的使用

2. Consistenct Caching，Client可以放心讀取Cache。而不是採用資料不一定一致的Caching機制。

3. 更新資料不是Master主動更新所有Cache，而是直接讓Client的Cache失效，之後Client重新Cache新的資料

4. 如果目前負載很重，可以調整session、lease時間長，減少Client與Master通訊次數

5. 可以使用Proxies處理Client的KeepAlive和Read請求 (Write還是要交給Chubby Cell處理)

使用

1. Google File System: 使用Chubby選出GFS Master
2. Google BigTable:
   • 選Master
   • 發現與紀錄tablet servers (類似服務發現)
   • 讓Client利用Chubby找到資料所在之tablet servers (服務發現後引導Client連線)

3. 當作小型File system，可以用來存大型分散式系統會用到的 metadata，作為root

4. 作為Lock來sequentialize一系列平行操作

5. 選Leader的具體方法我們留待之後Zookeeper來說，利用Zookeeper的API，當然也可以去看Chubby原論文看他怎麼用Chubby的API來操作，方法是一樣的。

總結

Chubby花了三天的篇幅來做介紹是因為他真的有很多的細節...

也許第一次看非常難懂，因為平常也不太會用到這種分散式的Lock Service，
甚至可能平常就很少在Multithreading用Lock解Race Condition，因為有些語言像是NodeJS作為single threading model幾乎不用面對這個問題。

但是Chubby仍然非常重要，
因為它讓我們了解分散式系統裡面的Lock應用情境，
與他自身提供了Lock、File、Event-Watch等綜合性服務的設計考量，
甚至是他作為分散式系統本質上關於Fail Over、Scaling、Caching、Clinet連線等設計都非常有參考價值。

值得大家借鑒。

Ref:

• 原文 https://storage.googleapis.com/pub-tools-public-publication-data/pdf/c64be13661eaea41dcc4fdd569be4858963b0bd3.pdf
• 我覺得寫得很好的介紹 https://catkang.github.io/2017/09/29/chubby.html