## 3-2 Paxos Made Live - An Engineering Perspective

### Introduction
:::danger
將Paxos共識演算法從理論轉到實際應用的挑戰
:::
* 從理論到實踐挑戰
* 雖然Paxos可以用僅一頁的pseudo code來表示，但實際C++實現包含數千行code，也涉及很多優化
* 難以傳統證明正確性的方式來證明，要用不同方法來增強系統對實際系統"正確性"的信心
* 容錯演算法傳統只處理有限的錯誤類型，而實際軟件錯誤會更多樣化
* 實際系統規格的很少被精確的指定，反而可能實現過程中會有各種變化
### Background
:::danger
Google Chubby介紹
:::
* Chubby功能和用途
* 分散式的lock
* 儲存小文件
* 每個資料中心都有一個Chubby實例或是"cell"
* 被多個Google系統，如GFS和Bigtable，用分散式協調和儲存少量元數據
* 容錯機制
* Chubby透過複製達到容錯
* Chubby細胞由五個副本組成，每個副本運行相同的code
* 每個Chubby對象(lock，文件)都存在數據庫中的一個條目
* 主副本和client的交互：
* 副本中會有一個主副本
* Chubby client會聯繫Chubby cell以獲取服務，進而聯繫主副本
* 若主副本失敗，會自動選一個新的主副本，該主副本會繼續基於本地的複製數據庫的內容來服務，從而確保主副本故障轉移期間的Chubby狀態的連續性
### Architecture outline
:::danger
Chubby副本的架構
:::
* 單個Chubby副本架構：
* 容錯複製log位於協議的stack的最底層
* 每個副本都維護一個本地的log副本
* 為保證所有副本的本地log一致，需要重複運行Paxos演算法
* 副本之間透過專門的Paxos協議進行通信
* 容錯複製數據庫：
* 下一層是每個副本本地拷貝的容錯複製數據庫
* 數據庫包含本地的snapshot和數據庫操作的重播log
* 新的數據庫操作將提交至複製log
* 數據庫的操作會應用於該副本的本地數據庫的拷貝
* Chubby用容錯數據庫來存其狀態
* 致力將設計一個乾淨的接口來分Paxos framework, database和Chubby
* 能使開發更清晰
* 為了重複使用其他應用程式中的複製log層
* 因預期Google未來系統會透過複製來尋求容錯能力
* API
* 提交值進入容錯log後，系統會在每個副本上調用callback function來傳遞該值
* 支援多線程，不同線程可以同時提交多個值
### On Paxos
:::danger
解釋Paxos的演算法和Paxos的multiple execution
:::
#### Paxos Basics
* Paxos共識達成過程
* 是一種共識演算法，由一組副本的程序執行，目的是在副本崩潰時也要達成一個值的共識。
* 副本可以在訪問崩潰後依然存在的存儲
* 一些副本可能會提交值已達共識，若大多副本能夠長時間不崩潰，所有運行中的副本保證會對提交其中一個值達成一致性
* 演算法分三階段
:::info
* 選舉一個副本做為協調者
* 協調者選擇一個值以消息來廣播給所有副本。其他副本要確認/拒絕該消息
* 一旦大多數副本確認了協調者發來的訊息，則達成共識，協調者會廣播一個提交的消息來通知副本
:::

* 協調者
* 由於協調者可能會fail，故可以多個副本都當協調者來執行演算法
* 賦予連續的協調者一個遞增的序號來排序協調者
* 當一個副本想成為協調者，他生成一個唯一的序號碼，廣播一個提案訊息給其他所有的副本
* 若多數回覆指出他們沒有看到更高的序列號，則該副本則作為協調者
* 共識達成
* 一旦某值達成共識，Paxos要迫使未來的協調選擇相同的值以確保達繼續保持協議
* 來自副本的承諾訊息包括他們聽到的最新值以及協調者的序號
* 新協調者從最近的協調者中選擇值
* 如果沒有一個promise訊息包括一個值，協調者則自由選擇提交的值
#### Multi-Paxos
* 一般實踐方式
* 通過重複執行Paxos演算法來實現一系列值上的共識
* 每次執行都被稱為一個Paxos實例
* Multi-Paxos方式
* 落後的副本可能沒有參與最近的Paxos的實例，需要一個追趕機制來讓落後的副本趕上領先的副本
* 每個副本維護一個本地持久log來記錄所有Poxas操作
* 當副本崩潰並恢復後，會重播崩潰前的狀態
* log也用來幫助落後的副本追趕
* 該演算法在其關鍵路徑上要執行五次寫入操作(提議、承諾、接受、確認、提交)，並將所有寫入立即刷新到新的磁盤
* 這刷新磁盤時間可能會產生延遲，故優化延遲的方法:
* 串聯Paxos來演少涉及的消息數量，若協調者身分不便則可以省略提議消息
* 這算法可能被設計成一個長時間選擇一個協調者，盡量使協調者不要更改
* 這種優化會使每次只要單次寫入磁盤

### Algorithmic challenges
:::danger
說明實現這演算法的難處
:::
#### Handling dick corruption

* 兩種故障表現:
    * 文件可能被修改
    * 文件無法訪問
* 為了檢測文件是否被修改，會儲存每個文件的checksum
* 但後者可能很難從新的副本和空磁盤中做區分，故新副本在啟用後會在GFS留下一個標記，來檢測新副本或是無法訪問的文件，區分空磁碟的新副本
* 磁盤損壞的副本通過作為非投票成員參與Paxos並使用追趕機制來重建狀態
#### Master leases
``一般Paxos演算法要實現複製數據結構時，讀操作需要實行Paxos實例``
* 但因為讀操作佔據所有操作的大部分，導致讀操作的成本很高
* 為了解決這問題，則透過master lease，含意是只要master擁有租約，其他副本則不能像Paxos提交值，從而允master本地的服務讀操作
* master通過定期提交"heartbeat"值給Paxos來刷新期租約
#### Epoch numbers
``為了確保請求master副本的一致性和穩定性，引入了epoch number``
* 這機制核心是透過這編號在master副本變更時準確監測識別並適當反映，確保一致性和可靠性，在必要時中止操作
#### Group membership
``實際系統要能處理一個set的副本的變更``
* 這超出本文章範圍，不解釋
#### Snapshots
``不斷成長的log和維護數據一致性是兩個挑戰，採snapshot來允許某個時間點的數據狀態進行儲存，避免對空間的無限增長需求，以及耗時的恢復``
* 過程
    * 用程式負責產生快照，並通知Paxos框架snapshot已完成。
    * snapshot產生後，Paxos框架會截斷舊的log記錄，保留快照點之後的記錄。
* 用於系統恢復
    * 落後的副本可以透過採用新的snapshot和重放其之後的log來同步當前狀態，減少恢復時間，不用trace所有的log
#### Database transactions
* 透過log的結構設計，數據庫狀態的snapshot及操作log，處理一致性問題
* 引入epoch number判斷操作是否失敗，更進一步確保一致性
### Software Engineering
:::danger
用軟工方式來開發維護故障容錯系統
:::
#### Expressing the algorithm effectively
* 用狀態機來規範語言，並把規範轉為C++
#### Runtime consistency checking
* 使用各種自檢機制，如廣泛使用assert和明確的檢驗代碼來測試數據結構一致性
* 如通過週期性提交數據庫log的校驗和請求，並計算checksum來檢查數據庫一致性
#### Testing
* 難證明實際系統的正確性，故通過測試系統極為最佳解決方案
* 提出兩套測試方法，都可用兩種模式之一運行:
    * Safety mode: 無論是否一致都需要任何進展，如操作為難完成也是可以接受的
    * Liveness mode: 會進行一些進展，所有操作都需完成且要求一致性
#### Concurrency
* 原先測試是可重複的，但隨著項目演進，一些子系統比預期想像需要更多的併發性，犧牲了可重複性
### Unecpected failures
:::danger
運行超過100 machine year，遇到的一些意外故障情況
:::
    * 性能與資源競爭
    * 回滾機制的問題
    * 升級腳本失敗
    * 數據庫語意不匹配
    * 數據庫一致性問題
    * 升級腳本多次失敗
    * 操作系統漏洞
對於當前Chubby而言當前故障率還是認為過高，其中有些意外為操作員錯誤有關，故Google充分寫測試腳本以及自動化部署來最小化操作員介入
### Measurements
:::danger
與現有的系統比較
:::
![image](https://hackmd.io/_uploads/S1_uTxHeA.png)
* 系統最初目的是要取代3DB，故與3DB進行性能比較
* 測試內容: 
    * 測試包括Chubby client，網路，Chubby server以及故障容錯數據庫在內的整個系統throughput
    * 主要測試為模擬密集型操作，因為讀的請求通常在擁有租約的master上處理，不會觸發到Paxos演算法
    * 用大content測試延遲，小content來測試throughput
    
儘管性能上超過了3DB，作者仍認為系統還有很大的優化空間
### Summary and open problems
:::danger
仍因複雜系統故實際建構還是很困難
:::
* 儘管Paxos有15年歷史，但因為複雜系統，實際建構還是比預期中困難，以下為幾個因素:
    * 理想與實踐的巨大差異
    * 缺乏易用的工具
    * 測試不足
* 作者認為應該集中精力解決這些短版