Computer Systems

這學期我修了影響我很深的三堂課，

operating systems

distributed computing systems

interconnection networks

每一門課中 都接觸到了大量相關領域的論文

在系統這個領域

Trade off 和 performance 一直是主要的課題

或者說 how to utilize the resources.

網路與系統 探討的是工程問題

也就是沒有最佳解或是唯一答案

會隨著參數或是硬體設備更新

有所突破

同樣的設計執行不同的程序也會有不同的表現

這些沒有標準答案又開放的學科

一開始學習會很挫折

通常研究一個問題時

切入一個點時需要做很多假設

先想好想要改進的點

然後試想可能可以改進的情況

同時間還要注意更動是否符合原本的設想

否則可能會在解決問題的同時製造出另外一個問題

目前我掌握這方面還是有限

只能從案例中學習

但是在分析一個系統時

已經能夠用比較全面的角度去切入

以及考慮不同情況

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