# The Chubby lock service for loosely-coupled distributed systems

## Intro
這篇論文主要是在描述一個Google研發的Distributed Lock Service 稱之為 ***Chubby***

> Chubby provides coarse-grained locking as well as reliable storage for a loosely-coupled distributed system.

跟其他很多分散式系統論文相同，不外乎想解決兩個大問題

1. 選出Leader
2. 解決資料一致性的問題

這部份可以利用 **Paxos** 共識演算法搭配 **Raft** 來達成，但開發過程想拿來使用卻很麻煩，在後面的段落會解釋為何 **Chubby** 更易於使用。

Chubby最主要的目標為

可靠性(reliability)、可用性(availability)、易於理解(easy-to-understand)

次要目標為

吞吐量(throughput),儲存量大小(storage capcity)

## Design
### 基本理念
作者在這段解釋了為什麼他們設計了這個service

1. 一般的系統開發初期，系統還很小不需要太在意效能，不用考慮consensus的問題，隨著系統越來越成熟，服務越來越多，我們需要replica servers並加入Leader的設計，我們可以用提供 distributed consensus的Library達成，但是要加入原先的架構相對困難，如使用一個提供Lock的service只要一個RPC參數，並加上兩條if判斷式，就能在不大量更動架構下達到一致性。
2. 在系統選出Leader或進行data partition後，我們需要讓processes和client知道這些資訊 e.g. Leader的位址（ip)。然而，這個聽起來像是**Name Service**的工作，最大的Name Service即為DNS，與其分拆成另一個service，不如利用Chubby為file system的特性，將Chubby當成name server用，讓client和processes去讀由Chubby維護的文件，得到Leader的資訊和Data的metadata，再搭配後面會介紹的client cache，以減少client所依賴的server，避免維護DNS time-to-live的成本及loading
3. 設計Chubby的人認為，Lock是大部分開發者都熟悉的東西，畢竟在寫Multithreading/Multiprocessing時，都曾用過Lock來管理Race Condition。諷刺的是，其實很多開發者以為自己會用Lock，但是其實非常容易犯錯，尤其沒有考慮到在分散式系統Asynchronous環境下process失效或是網路延遲對Lock的影響，因此他們設計了一個適用於分散式系統的Lock service，由於大多數的開發者對Lock更熟悉，更容易說服開發者在開發中使用Lock。
4. replica servers若要高可用性，就需要共識演算法，要滿足Quorum的要求，一般來說，Chubby cell有5個replicas，必須要三個relica活著系統才能運作，但如果用Lock service的話，只要一個relica能拿著Lock，系統還是能保持一致性，因此lock service能減少系統progress所需的最低servers數量。

### 設計方向
Chubby除了上述兩個功能還針對一些使用情境設計了一些功能。
:::info

1. 選擇實作一個Lock Service而非一個Consensus Protocal Library
2.為了Leader Election和資訊紀錄機制，提供文件儲存
3. 這個資訊需要被上千個clients得知，因此要建立client觀看這個檔案的機制。
4. 搭配事件通知機制，而不用讓client一直polling資訊
5. 但是還是會有人不斷polling，所以提供caching機制給有權限能觀看的clients
6. 因為有些開發者對cache consistency不熟，所以一律提供Consistent Caching，不懂機制沒關係，只要讀就好，因為保證資料正確性
7. 可能因為這個服務導致財物損失與官司，所以我們提供安全機制與存取控制
:::
### Coarse-Grained(粗粒度) Lock
這邊講一下Chubby提供的Coarse-Grained Lock，簡單說就是這個Lock的租期比較長，因為使用情境大部分都不需要頻繁地取得/釋放Lock，比方說Leader Election在Leader存活期間可以一直拿著Lock不用釋放又取得，作者提到如果Lock掉了要重新得到的恢復成本非常大、也就是時間會非常久。

好處有兩個

1.對Chubby的負擔較小效能較高，可以服務更多Client。
2.如果Chubby短暫失效，Client不需要重新索求Lock，運作不太會被延遲。
e.g. Coarse-Grained的設計可以在Chubby短暫失效又恢復後很大機率還在同一個Lock週期(幾天、幾週)，如果是Fine-Grained Lock則Chubby失效後，可能Lock也剛好到期，Client要重新拿Lock時就要等Chubby恢復。
如果是Fine-Grained Lock，Client(分散式系統)要頻繁的重新拿取Lock，作者建議如果想要應用程式想要使用fine-grained，最好是使用coarse-grained的lock service再分成group的方式達成fine-grained。

### System Structure
 圖為一個chubby cell和client的架構


- 分成Client與Chubby Cells
- 五個replica servers組成一個高可用性的Chubby Cells提供Lock Service給Client用。
- Client透過chubby library利用RPC和Chubby Cell溝通

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

### Chubby 內部的一致性

Chubby本身的設計也是分散式系統，就需要共識演算法來達成一致性，且因為設計了client觀看機制與事件通知機制，Chubby內部的replica servers必須是 ==**Strong Consistency**==。

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

- 內部的5個replica servers先經過共識演算法選出一個Master (Leader)
- 與Paxos有多個Proposers不同
- 這個 ==**Master**只會有一個且有lease（租約）時間。== 也就是在此lease時間內都會只有這個Master來提出所有Proposal，來更新其他replica servers的訊息。
- Client的讀寫都是經過Master，讀直接從Master讀，寫入必須等待Master利用Paxos共識演算法同步replica server才返回寫成功，後面會更詳細的解釋這個機制。
- Master失效的話，replica servers需要重新做Leader Election。
> Paxos如果發生Partition，比方說3:2，因為2個replica servers不過半數。所以如果client對那2個servers發出請求，會顯示不可用，只有那3個servers還可以運作Paxos協定所以可以使用。

### Files, directories, and handles

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

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

在Chubby內的路徑會長的類似這個樣子
**/ls/foo/wombat/pouch**:

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

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

- check digits: 檢查Client是否偽造或是猜到Handle的值
- sequence number: Master可以用此來判斷這個Handle是前任Master產生的還是自己產生的。

### Locks and sequencers

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

1. Advisory與Mandatory Lock的差別

- **Mandatory Lock**: 當一個文件被Lock住後，其他的Client皆無法在讀該文件，返回錯誤。
- **Advisory Lock**: 該文件被Lock住時，Client仍然可以讀該文件，因此只有當其他Client也想要取得Lock時，才會返回錯誤。
- 原因:

- Chubby的Lock可能被用在其他服務的資源上，如果是**Mandatory Lock**，但是該服務其實允許資源被鎖住仍可讀取，不滿足該服務的使用情境，必須做改寫。
- 當一個文件目前被Chubby鎖住，為了debug方便，使用者必須暫停Chubby服務來解鎖，才有辦法得知文件狀態，來進行debug。
- bug的發生情景，跟這個鎖允不允許使用者讀取critical section的資源無關，因此**Mandatory Lock**效益不大，可以鎖住即可。

2. 使用
1. 每一個Node都是Lock，有兩種模式 (都是Advisory Lock)

- exclusive (writer) mode: 只限一個Client同時使用
- shared (reader) mode: 可多個Clients同時使用

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的操作請求。搭配Node與Acquire 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
- Leader Election
如果要選Leader，而不是一致性資料的儲存服務，那選Leader就不用像Raft還要比較log新舊。
直接搭配Chubby就非常簡單，
這是一個搭配File System加上Lock Service應用的情境。

- 每個Process都到Chubby爭奪acquire "myservice/primary" Node的Lock。
- 誰先完成就可以把自己的ip寫進去，就成為了Leader。

其他人只要去查看 "myservice/primary" Node 就能得知現在Leader是否還存活，如果Leader斷線，Chubby Node也會有反應跟事件通知。

- 新舊 Leader

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


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

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

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

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

### Cache 讀寫設計

Chubby希望以犧牲write的效能增加read的效能。
因此Chubby的Caching機制為**Consistent Cachinig**，減少Client直接對Chubby的read request，並且讀取一定是最新的資料且一定正確，否則返回錯誤 **(Strong Consistency)**。
- Client端的Cache可以儲存Node Data、Metadata、Handle與Lock...等
- Chubby Master維護一個list來記錄目前有caching的client與caching內容
- Chubby Master收到寫入請求時，為了保證Client的Consistent Caching
- 寫入為blocking call
- 通知相關的Client invalidate自己的cache
- 等待Client完成後
- Master收到所有的Client invalidate完成訊息或是Lease過期才執行寫入請求
- 可以看到這就是所謂的「犧牲寫入效能，增加讀取的一致性，減少對Chubby的直接讀取」

那什麼是Lease (租期)？

### Cache lease設計
除了上面寫入時，必須invalidate自己的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驗證，在Local端就可以驗證了

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

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

### 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可以清楚知道某個時刻之前的操作是成功的，該時刻之後的操作是失敗的，而不會混亂。

### Fail-over(故障恢復)
當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住的運作模式。

如下圖圖解:

### 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處理)