zookeeper(二)-Paxos算法

分布式系統中的節點通信存在兩種模型：共享記憶體（Shared memory）和消息傳遞（Messages passing）。基于消息傳遞通信模型的分布式系統，不可避免的會發生以下錯誤：程序可能會慢、被殺死或者重新開機，消息可能會延遲、丢失、重複，在基礎 Paxos 場景中，先不考慮可能出現消息篡改即拜占庭錯誤的情況。Paxos 算法解決的問題是在一個可能發生上述異常的分布式系統中如何就某個值達成一緻，保證不論發生以上任何異常，都不會破壞決議的一緻性。一個典型的場景是，在一個分布式資料庫系統中，如果各節點的初始狀态一緻，每個節點都執行相同的操作序列，那麼他們最後能得到一個一緻的狀态。為保證每個節點執行相同的指令序列，需要在每一條指令上執行一個“一緻性算法”以保證每個節點看到的指令一緻。一個通用的一緻性算法可以應用在許多場景中，是分布式計算中的重要問題。是以從20世紀80年代起對于一緻性算法的研究就沒有停止過。

為描述 Paxos 算法，Lamport 虛拟了一個叫做 Paxos 的希臘城邦，這個島按照議會民主制的政治模式制訂法律，但是沒有人願意将自己的全部時間和精力放在這種事情上。是以無論是議員，議長或者傳遞紙條的服務員都不能承諾别人需要時一定會出現，也無法承諾準許決議或者傳遞消息的時間。但是這裡假設沒有拜占庭将軍問題（Byzantine failure，即雖然有可能一個消息被傳遞了兩次，但是絕對不會出現錯誤的消息）；隻要等待足夠的時間，消息就會被傳到。另外，Paxos 島上的議員是不會反對其他議員提出的決議的。

Paxos描述了這樣一個場景，有一個叫做Paxos的小島(Island)上面住了一批居民，島上面所有的事情由一些特殊的人決定，他們叫做議員(Senator)。議員的總數(Senator Count)是确定的，不能更改。島上每次環境事務的變更都需要通過一個提議(Proposal)，每個提議都有一個編号(PID)，這個編号是一直增長的，不能倒退。每個提議都需要超過半數((Senator Count)/2 +1)的議員同意才能生效。每個議員隻會同意大于目前編号的提議，包括已生效的和未生效的。如果議員收到小于等于目前編号的提議，他會拒絕，并告知對方：你的提議已經有人提過了。這裡的目前編号是每個議員在自己記事本上面記錄的編号，他不斷更新這個編号。整個議會不能保證所有議員記事本上的編号總是相同的。現在議會有一個目标：保證所有的議員對于提議都能達成一緻的看法。

好，現在議會開始運作，所有議員一開始記事本上面記錄的編号都是0。有一個議員發了一個提議：将電費設定為1元/度。他首先看了一下記事本，嗯，目前提議編号是0，那麼我的這個提議的編号就是1，于是他給所有議員發消息：1号提議，設定電費1元/度。其他議員收到消息以後查了一下記事本，哦，目前提議編号是0，這個提議可接受，于是他記錄下這個提議并回複：我接受你的1号提議，同時他在記事本上記錄：目前提議編号為1。發起提議的議員收到了超過半數的回複，立即給所有人發通知：1号提議生效！收到的議員會修改他的記事本，将1好提議由記錄改成正式的法令，當有人問他電費為多少時，他會檢視法令并告訴對方：1元/度。

現在看沖突的解決：假設總共有三個議員S1-S3，S1和S2同時發起了一個提議:1号提議，設定電費。S1想設為1元/度, S2想設為2元/度。結果S3先收到了S1的提議，于是他做了和前面同樣的操作。緊接着他又收到了S2的提議，結果他一查記事本，咦，這個提議的編号小于等于我的目前編号1，于是他拒絕了這個提議：對不起，這個提議先前提過了。于是S2的提議被拒絕，S1正式釋出了提議: 1号提議生效。S2向S1或者S3打聽并更新了1号法令的内容，然後他可以選擇繼續發起2号提議。

好，我覺得Paxos的精華就這麼多内容。現在讓我們來對号入座，看看在ZK Server裡面Paxos是如何得以貫徹實施的。

小島(Island)——ZK Server Cluster

議員(Senator)——ZK Server

提議(Proposal)——ZNode Change(Create/Delete/SetData…)

提議編号(PID)——Zxid(ZooKeeper Transaction Id)

正式法令——所有ZNode及其資料

貌似關鍵的概念都能一一對應上，但是等一下，Paxos島上的議員應該是人人平等的吧，而ZK Server好像有一個Leader的概念。沒錯，其實Leader的概念也應該屬于Paxos範疇的。如果議員人人平等，在某種情況下會由于提議的沖突而産生一個“活鎖”（所謂活鎖我的了解是大家都沒有死，都在動，但是一直解決不了沖突問題）。Paxos的作者Lamport在他的文章”The Part-Time Parliament“中闡述了這個問題并給出了解決方案——在所有議員中設立一個總統，隻有總統有權發出提議，如果議員有自己的提議，必須發給總統并由總統來提出。好，我們又多了一個角色：總統。

總統——ZK Server Leader

又一個問題産生了，總統怎麼選出來的？oh, my god! It’s a long story. 這次先不涉及。

現在我們假設總統已經選好了，下面看看ZK Server是怎麼實施的。

情況一：

屁民甲(Client)到某個議員(ZK Server)那裡詢問(Get)某條法令的情況(ZNode的資料)，議員毫不猶豫的拿出他的記事本(local storage)，查閱法令并告訴他結果，同時聲明：我的資料不一定是最新的。你想要最新的資料？沒問題，等着，等我找總統Sync一下再告訴你。

情況二：

屁民乙(Client)到某個議員(ZK Server)那裡要求政府歸還欠他的一萬元錢，議員讓他在辦公室等着，自己将問題反映給了總統，總統詢問所有議員的意見，多數議員表示欠屁民的錢一定要還，于是總統發表聲明，從國庫中拿出一萬元還債，國庫總資産由100萬變成99萬。屁民乙拿到錢回去了(Client函數傳回)。

情況三：

總統突然挂了，議員接二連三的發現聯系不上總統，于是各自發表聲明，推選新的總統，總統大選期間政府停業，拒絕屁民的請求。

呵呵，到此為止吧，當然還有很多其他的情況，但這些情況總是能在Paxos的算法中找到原型并加以解決。這也正是我們認為Paxos是Zookeeper的靈魂的原因。當然ZK Server還有很多屬于自己特性的東西：Session, Watcher，Version等等等等，需要我們花更多的時間去研究和學習。