# Week 04 - The Paxos Consensus (共識) Algorithm
###### tags: `WS2020-IN2259-DS`

## Consensus problems
* 在一或更多 node **proposed a value** 後，希望**所有 nodes** **認同 (agree on)** 一個值。
* 這也稱作 **problems of agreement**。
* 挑戰
* 在 **node failures** 與 **unreliable networking** 的情況下，達成共識 (reach consensus)。
* 一或更多 node 會 proposed value：
**How do we get a collection of nodes to agree on exactly one of the proposed values?**
* Examples
* 兩軍同意進攻或撤退。
* **Mutual exclusion**：Processes 同意誰進入 CS
* **Leader election**：Processes 同意誰是 leader。
* ...
* **Requirements for consensus**
* Agreement：所有的 correct node (not failing) 必須 agree on 一樣的 value。
* Validity：只有 proposed values 可以被決定。
* 如果一 node 決定了某個 value，那這必須是被某個 node proposed 的 value。
* Integrity：各個 node 最多只能決定 value 一次。
* Termination：所有 correct nodes 最終決定 (decide on) 一個 value。
## Replication

## Coordination services (Paxos inside)
* 也稱作 distributed lock service
* Highly-available and persistent
* Use in Bigtable/HBase
* 在任何時間可保證最多僅有一個 active 的 Bigtable master。
* 儲存**資料的 bootstrap 位置**(也就是 **root tablet**)。
* **Discover** tablet servers (管理它們的生命週期)。
* 儲存 **configuration information**。

## Brief history of Paxos
* 解決 **asynchronous systems** 中的 **consensus** 問題，而且允許 **node failure** 與 **network omission failure**！
* 比前面介紹過的所有演算法都好！
* 但是這世界上有「**FLP 不可能原理**」(後面介紹)。
* Original paper：“The Part-Time Parliament,” by Lamport (submitted in 1990, published in 1998?!)
* Lamport 虛擬了一個叫做 Paxos 的希臘城邦來描述 legislative **consensus system**。
* Rewritten into “plain English” as “Paxos Made Simple”
* Paxos family：有很多基於 Paxos 演算法的變化版本。

## Paxos in light of **FLP** result
* 在 **asynchronous systems** 中，就算只有 **one node crashing**，沒有演算法可以保證達到共識 (consensus)。
* 因此 Paxos 只能妥協，保證 **safety** 但 **not liveness**。
* “Conditions that could prevent progress are difficult to provoke.”
* Paxos 在一些限制數量以內 (bounded number of) 的 nodes 沒有回應的情況下，**attempts to make progress**！

## Assumptions for Basic Paxos
* Nodes
* Asynchronous model：操作的速度是不固定的 (**arbitrary speed**)。
* Fail-stop faults：可能會有 **failures**。
* **Crash-recovery failure model**：nodes **可能**會在失敗後重新加入 protocol 中 (會記得先前的狀態)。
* **No Byzantine (拜占庭) failures**：do not collude (串通), lie (說謊), or otherwise attempt to subvert (顛覆) the protocol
* Network
* Nodes 間使用 unicast 傳送訊息。
* Messages 的傳送是 **asynchronous** (may take arbitrarily long)。
* Messages 可能會 **lost**、**reordered** 或 **duplicated**。
* Network 可能會 partition 脫離。
* Messages 的傳送不會被「汙染」(**no Byzantine failures**，cf. Byzantine Paxos)。
* Number of nodes
* 一般而言， Paxos 功能上具有 2f+1 個 nodes (也稱作 majority)。
* 可允許任意 f 個 nodes 同時故障 (simultaneous failure)。
* 如：5 個 nodes，可以抵禦 (resilient against) 2 個 failing。
* 5 replicas in Chubby

## Roles in Paxos
像是 client 與 server 間的腳色關係
* Client 觸發 (triggers) protocol。
* Roles
* **P**roposer
* **A**cceptor
* **L**earner
* Leader (one of P)
* **Single process** 可能會同時扮演好幾個腳色，這不會影響 protocol correctness。
* 整合 (coalesce) 腳色是很常見 (common) 的事，可以改善 latency、number of messages exchanged 等等。

## Paxos informal, high-level overview
* 一個 **proposer** 會透過傳送 proposal message 給 **acceptors** 來啟動一個新的 ++proposal++。
* 如果 **acceptors** 接受這個 proposal，將會回傳 promise，
* 如果 **proposer** 收集到 a majority of promises， 這個 **proposer** 將會為這個 proposal 指定一個 ++value++，然後再傳送給 **acceptors**。
* 如果 **acceptors** 接受這個 value，那麼將傳送這個 ++decided value++ 給所有 **learners**。
* 當 **learners** 從 **acceptors** 收到帶有 ++decided value++ 的 majority of messages 後，學習此 ++decided value++。

## Paxos in context: Roles, proposals, value

## Corner cases (極端案例) addressed by Paxos
* 多個 proposers 同時發出 proposals。
* ==proposer 發出一個不同於 already decided value 的 value。(這怎樣才會發生？)==
* 如果發生 network partition？
* proposer 在徵求 (soliciting) promises 的途中 crash 了。
* proposer 在獲得 a majority of promises 後 crash，尚未為它的 proposal 設定 value。

## Lessons learned from Strawmen (稻草人) 1-4 號
1. 需要 multiple acceptors (tolerate faults)。
2. 需要 acceptors 多數決 (votes on a value) 來打破僵局 (break ties)。
3. 必須允許 acceptors 改變心意 (change their mind)，如此才能製造出多數決。
4. 需要兩階段的 protocol 來檢查先前的決定 (prior decisions)。
5. 愈要排序 proposals 的方法，以確保單一結果 (single value results)。

## The Paxos way - Preview

### Client
* **不參與 Paxos protocol**。
* 傳送 **requests 至 proposer**，然後**等待 learner 回傳 response**。
* Basic Paxos 會決定接受哪個 request。
* Request 的性質取決於使用哪種 Paxos。

### Proposal number & agreed value
* Proposal number：**`P#`**
* 必須是獨一無二的 (uniqued)。
* 任兩個 proposers 不可能擁有相同的 Proposal number。
* 理想上 (desirable)，新的 proposal number 必須大於前一個。
* 如果 proposal number 相撞，那 proposer 會將自己的提議拒絕掉，然後進行 re-try。
* 構成：**`incrementing counter`** + **`globally unique node/process identifier`**
* `(logical clock, unique node/process identifier)`
* `(2345 1921681215555)`

* Value **`V`**：代表需要被同意的訊息，如：input from the client、client request。

### Proposers
* 使 acceptor 同意於一 client requests。
* Paxos 將 **client requests** 簡單地稱作 **values**。
* 多個 Proposers 可能會同時 propose 不同的 proposals。
* Proposers 必須先檢查是否有 acceptors 同意於其他的 value。
* Proposer 傳送的 messages：
* 第一階段：**`prepare (P#(N))`**
* 第二階段：**`acceptReq (P#(N), Value(V))`**
* Proposal 的目標是定義共同同意的 value **`V`**。
* Proposal 有可能會被 acceptors 拒絕。

### Acceptor
* Acceptors 決定要接受哪個 proposal 並且記憶其 value。
* Proposal 必須送給法定數量 (**quorum**) 的 acceptors。
* 如：5 個 acceptors，**quorum** 即為 3。
* 通常都是全送。
* 以 ordering 的方式，acceptor 可接收多個 proposals。
* 如果 acceptor 已經 promised **`P#n`**，那它只能接受**新的** proposal **`P#m`** 且 **`m > n`**。
* 如果 acceptor 接受新的 proposal **`P#m`**，那它會拿**舊** (**`P#n`**) 的 **value** 要求 proposer 設定成 **`P#m`** 的 value。
* Acceptor 傳送的 messages：
* 第一階段：**`promise (P#, old P#(N’), old Value(V’))`**
* 第二階段：**`accepted (P#, V)`**
* Proposal 必須超過 quorum 才能通過。
* 雖然 Paxos 提供「consensus」，但內在實作上只需要多數決。
* Tolerates failures：比起 strict unanimity (一致意見) ，更加 fault-tolerant。

### Quorum (法定人數團)
* 定義：quorum 為 acceptors 的子集合，因此兩個 quorum 至少分享一個成員。
* 保證 safty：至少有一台 acceptor 決策兩個以上的 proposals。
* 範例：
* acceptors {A,B,C,D}
* Majority quorum： {A,B,C}, {A,C,D}, {A,B,D}, {B,C,D}, {A,B,C,D}
* Weighted quorum (此處 A 的權重為 2)：{A,B}, {A,C}, {A,D}, {B,C,D}, {A,B,C,D}

### Learner
* Learner 傳送的 messages：
* `clientRes (Value (V))`
* 最終決策的儲存點。
* Learner 轉換「多數決」成為「共識」。

### Safety and liveness properties
* **Non-triviality (不平凡)**：只有 propose 的 value 可以被學習。
* **Safety**：最多學習一個 value (兩個 Learner 不能學習不同的值)。
* **Liveness**：如果 value `V` 已經 propose 出去了，learner `L` 一定會學習到某個值 (**some value**)。
* 除非 2f+1 nodes 陣亡，不然 Paxos 保證 Safety。
* liveness 不備保證，可能會有 livelock。

### Summary of Paxos roles (流程圖)

## Basic Paxos
* 一個 instance 產出 一個 value。
* 可能會執行好幾個 rounds。
* 一個成功的 round 有兩個階段：
* first phase：prepare (P) and promise (A)
* second phase：acceptRequest (P) and accepted (A)
* 當 learner 得到多數同意的 Value：
* third phase：clientResponse (L)
* Proposer 必須跟至少一個 quorum 溝通。

### Phase 1a: Prepare (@ Proposers)
* 首先 proposers 建立 `P#N`。
* N 是遞增的，因此 `P#N` 肯定比以前的 `P#N'` 大。
* 傳送 **prepare message**：`prepare(N)` 給 **quorum of acceptors**。
* Proposer 決定 quorum 的成員有誰。

### Phase 1b: Promise (@ Acceptors)
* 如果收到的 `N` 比 以前收到的 `N'` 大，那麼把以前的 `N'` drop 掉，回傳 `promise(N, -, -)`
* 如果已經獲得 Value `V'`，那就回傳 `promise(N, N’, V’)`。
* 其他情況，回傳 negative reply (NACK)。

// N larger than any P# previously received 
// N > max_PN 
IF N ≤max_PN  
    //!(N > max_PN)  
    do not reply (or reply with a NACK) 
ELSE  
    //(N > max_PN), was proposal accepted before?    
    IF (proposal_accepted == true)   
        reply: promise(N, N’, V’) 
    ELSE      
        reply: promise(N,  -,  -)

### Phase 2a: Accept Request (@Proposer)
* 當 proposer 收到足夠的 promises，便可以為 proposal 設定 value。
* 如果 acceptors 回傳的 promises 包含 value `V'` (這種 `promise(N, N’, V’)`)，那 proceser 必須設定最大的 `N` 與 `V'`。
* 如果沒有 acceptors 回傳其他 value，那 proposer 會自己設定 value (從 client 那邊得到的 `V`)。
* Processor 傳送 accept request message 給 quorum of acceptors：`acceptReq(N, V)`
* Proposer 此時選擇的 quorum 可能與 promised back 的不一樣。

Were promises from a majority of acceptors received? 
IF yes    
    Did any reply contain accepted values (from other proposals)?  
    IF yes        
        //Take value from promise with highest PN        
        V = accepted_VALUE
    ELSE        
        // Use own value (client's input)        
        V = OUR_VALUE   
    reply acceptReq(N, V) to majority of acceptors (or more)

### Phase 2b: Accepted (@Acceptor)
* 當 acceptor 收到 acceptReq message (P#N)，如果還沒 promise 任何 `n' > n` 的 proposal (更新的)，就會接受這個 acceptReq message (P#N)。
* 傳送 accepted message 給 proposer 與 every learner：`accepted(N, V)`
* 否則，Drop acceptReq (可選：傳送 NACK 給 proposer)。

// Is P# N the largest seen so far?
IF (N >= max_PN)
    // note that we accepted a proposal
    proposal_accepted = true
    // save the accepted proposal number
    accepted_ID = N
    // save the accepted proposal value
    accepted_VALUE = V
    reply: accepted(N, V) to proposer & learners
ELSE
    do not respond (or respond with a NACK)

### Phase 3: Decided (@Learner)
* **learner** 從 **quorum** of acceptors 學習 **decided value**。
* quorum 是必須的，用以避免 concurrent proposals 造成的衝突。
* 只要 learner 學習到 **decided value**，便可以執行 associate command 與/或 client 溝通。

### Basic Paxos protocol timeline

## FAILURE HANDLING IN PAXOS

### Failure of acceptor

### Failure of redundant learner

### Failure of proposer

### Failure in Phase

### Dueling proposers

### Communication failures

## spectrum of trade-offs (權衡範圍)
* Number of processes
* Number of message delays before learning the agreed value
* Activity level of individual participants
* Number of messages sent
* Types of failures tolerated

## Discussion
* ==Configuration management not addressed by Basic Paxos (nassumed fix in protocol instance)==
* 腳色有可能重疊。
* 如果一個 client request 沒有得到共識，那需要 client 自己再重新發起 (retry)。

## Summary
* 在 **asynchronous environment** with **failures** and **unreliable network** 的情況下，假設有 2f+1 nodes。
* 比之前教過的 coordination 演算法好。
* 保安全 (safety)，但不保進度 (progress)。
* 核心機制：**ordering** using proposal numbers、**quorum accepts** without rollback (如新的 proposals 使用舊的 accepted values)。
* Paxos 是當今 Internet-scale systems 中的核心 (如 Chubby)。
* Paxos 有很多 family：
* **Basic Paxos**：decides only on one value
* **Multi**-Paxos
* **Cheap** Paxos
* **Fast** Paxos
* **Byzantine** Paxos