# Paxos Made Live - An Engineering Perspective

## Abstract

* 說明 google 在實作 Paxos 時所遇到的挑戰。

## Background

* 介紹chubby:
* Chubby 是一個分散式的 lock service 且可以用來儲存一些小的文件。
* 一般而言 Chubby 會維護五個 replica。
* 詳細可以參考 [Chubby](https://ithelp.ithome.com.tw/articles/10224321)。

## Architecture outline

* 單個 Chubby replica 的架構
* API 的流程:
* 如果 API 被trigger，Chubby 會利用 Paxos 讓各個 replica 紀錄的 log 達成一致，同時可以有很多個 Paxos 同時進行。

## On Paxos

* 回顧 Paxos 原理，可以參考 [Paxos](https://ithelp.ithome.com.tw/articles/10220123)。

## Algorithmic challenges

### disk corruption:
* 硬碟錯誤會造成 Paxos 協議出現問題，可能違背它先前對其它副本所做的承諾(我猜測是acceptor ack 的部分)。
* 硬碟錯誤可能有兩種形式，文件內容被改變與無法存取。
* 文件內容被改變可以依靠維護文件的 checksum 解決。
* 無法存取則是在底層的檔案系統(GFS)針對該文件打上標記解決。

### master lease:
* 為了在實務上解決 Paxos 演算法可能需要過長時間才能解決共識的問題。
* 讓一個 master 持續足夠久的時間，而不是每發生一次短時間的 network partition 就重選一次 master。

### epoch numbers

### Group membership

### Snapshots
* 為了解決當 log 過長時，每次同步需要花費大量時間的問題。
* 當 log 累積到一定程度後，清除掉先前部分的 log，將其製成 snapshot，並利用 Paxos 將 snapshot 同步到其他的 replica。

### Database transactions
* 為了實現資料庫中 atomic 的 cas(compare and swap) 操作，google開發出了一種更general的架構叫 MultiOp 來解決這個問題。
* MultiOp 由三個部分組成，guard、t_op、f_op，我自己認為可以將其理解成廣義的三元運算子，也就是 $$ \text{condition ? true_operation : false_operation} $$。
* guard就是資料庫中的condition，可以用來檢查資料庫中的值是否符合某些條件。
* t_op就是如果guard成功執行，就執行t_op所包含的操作，f_op則是相反。

## Software Engineering

### Expressing the algorithm effectively

* 問題: 無法很輕易的去表達這種容錯演算法
* 解決方式: 將演算法使用狀態機表示

### Runtime consistency checking

* 問題: 很難在系統執行期發現錯誤
* 解決方式: 在程式碼中使用很多assert與在資料庫中建立各種驗證機制(例如: 使用checksum驗證資料庫中的資料與log是否衝突)。

### Testing

* 問題: 很難測試這個系統是否正確
* 解決方式: 針對系統進行一連串的隨機故障，並測試其行為是否符合預期。

### Concurrency

* 問題: 使用 concurrency 導致測試難以重現
* 解決方式: 沒解決，但提出如果測試要有可重現性，那就必須約束 concurrency 的使用。

## Unexpected failures

## Measurements


## Summary and open problems

* > 現實系統的需求的與Paxos演算法的描述之間有很大的隔閡。為了建構現實的系統，專家需要使用分散在各種文獻中的許多思想，並做出一些較小的協議擴展。這些不斷累積的擴展會非常多，最後系統會基於一個未被證明的協定。

* > 容錯計算社群還沒有開發能使實現它們的演算法變得簡單的工具。

* > 容錯運算社群對測試沒有給予足夠的關注，這是建立容錯系統中關鍵的部分。

## Reference

<https://blog.mrcroxx.com/posts/paper-reading/paxos-made-live/>