Thursday, February 22, 2018

Paxos Algorithm

最近上 operating systems, distributed systems 的課看了一些論文,

發現網路上中文資料相對英文還是少了一點,

所以想嘗試以初學者的角度解釋一些概念。


Paxos Algorithm 通常用在容錯分布式系統 (fault-tolerant distributed systems) 用來實現 Consensus Algorithm.

先來討論一下為什麼需要分布式系統。

假設你是一家銀行,擁有帳戶和餘額。

a. 今天我去領錢,機器當機了

1. 如果只有一個主機存資料,
-> 所有帳戶餘額會不正確

2. 如果有多個主機
-> 根據沒有當機的主機,recovery


b. 但是如果有多個主機,

餘額減少的那個主機,

如何更新餘額給其他主機知道就是 Paxos algo 討論的問題


核心概念:

每個process(node) 有 proposer, acceptor, learner.

proposer 送request 給其他 acceptors. (acceptors 有可能會收到多個)
prepare_request(n)

acceptors 會選收到最高的 n 的傳回去proposer
response_to_prepare_request(Proposal[m, w]/None)

proposer 根據 response 選出 MAJORITY 之後傳給其他 acceptor
accept_request(proposal[n,v])

acceptor 傳給其他 learner
decision(proposal[n,v])

learner 把收到的value寫到系統裡。

最終全部的process 都會有更新過的value.


這些步驟裡面有寫可以簡化,因此 paxos 還有其他的變種算法。


references:

https://www.youtube.com/watch?v=UUQ8xYWR4do
http://lamport.azurewebsites.net/pubs/paxos-simple.pdf

No comments:

Post a Comment

Computer Systems

這學期我修了影響我很深的三堂課, operating systems distributed computing systems interconnection networks 每一門課中 都接觸到了大量相關領域的論文 在系統這個領...