971
[讀書筆記] The Part-Time Parliament
在剛接觸到一致性算法的時候就知道了Paxos，同時也發現看到的所有文章提到Paxos的時候都說難於理解。於是我決定，咱就要看Paxos是怎麼個難法，萬一我一遍就看明白了，是不是證明我的智商高啊，So --- LESLIE LAMPORT大爺，我來了。
不過這篇The Part-Time Parliament我一打開就開始懵比。這個名字就不像IT論文啊，“臨時議會”什麼意思？ 開頭這麼一段：
Early in this millennium, the Aegean island of Paxos was a thriving mercantile center.1 Wealth led to political sophistication, and the Paxons replaced their ancient theocracy with a parliamentary form of government. But trade came before civic duty, and no one in Paxos was willing to devote his life to Parliament. The Paxon Parliament had to function even though legislators continually wandered in and out of the parliamentary Chamber.
The problem of governing with a part-time parliament bears a remarkable correspondence to the problem faced by today’s fault-tolerant distributed systems, where legislators correspond to processes, and leaving the Chamber corresponds to failing. The Paxons’ solution may therefore be of some interest to computer scientists. I present here a short history of the Paxos Parliament’s protocol, followed by an even shorter discussion of its relevance for distributed systems.
翻譯過來是：
希臘島嶼Paxon 上的執法者在議會大廳中表決通過法律，並通過服務員傳遞紙條的方式交流信息，每個執法者會將通過的法律記錄在自己的賬目上。問題在於執法者和服務員都不可靠，他們隨時會因為各種事情離開議會大廳，並隨時可能有新的執法者進入議會大廳進行法律表決，使用何種方式能夠使得這個表決過程正常進行，且通過的法律不發生矛盾。
不難看出故事中的議會大廳就是我們的分布式係統，牧師對應節點或進程，服務員傳遞紙條的過程就是消息傳遞的過程，法律即是我們需要保證一致性的值（value）。牧師和服務員的進出對應著節點/網絡的失效和加入，牧師的賬目對應節點中的持久化存儲設備。上麵表決過程的正常進行可以表述為進展需求（progress requirements）：當大部分牧師在議會大廳呆了足夠長時間，且期間沒有牧師進入或者退出，那麼提出的法案應該被通過並被記錄在每個牧師的賬目上。
這篇文章從頭到位的文風都是這個樣子，講一講故事，然後再講一講算法，可能LESLIE LAMPORT 大爺想借此讓大家更容易理解他的理論，可是說實話這讓我更加的懵比，沒看多久就敗下陣來。後來看了一些中文翻譯及解釋才算明白了部分內容吧。很讚同Raft那篇“In Search of an Understandable Consensus Algorithm”論文裏對它的描述：“不幸的是，Paxos 有兩個明顯的缺點。第一個缺點是 Paxos 算法特別的難以理解。完整的解釋是出了名的不透明；通過極大的努力之後，也隻有少數人成功理解了這個算法。因此，有了幾次用更簡單的術語來解釋 Paxos 的嚐試。盡管這些解釋都隻關注了單決策的子集問題，但依然很具有挑戰性。在 2012 年 NSDI 的會議中的一次調查顯示，很少有人對 Paxos 算法感到滿意，甚至在經驗老道的研究者中也是如此。我們自己也嚐試去理解 Paxos；我們一直沒能理解 Paxos 直到我們讀了很多對 Paxos 的簡化解釋並且設計了我們自己的算法之後，這一過程花了近一年時間。”
看到Diego Ongaro和John Ousterhout那麼NB的人，也不能一次看懂，讓我感覺好受了不少。不過我還是建議大家沒事看看這篇論文，萬一一次就看明白了，那多NB啊，而且Paxos畢竟是個精巧，又強大的協議，現實中很多一致性係統也是基於它（變體）做得。
對於Paxos的一些詳細解釋大家可以看看知乎上麵的帖子：
https://www.zhihu.com/question/19787937
最上麵的幾個回複已經說的很不錯了。
最後更新：2017-08-21 16:02:34