好難找到原文是誰(shuí)寫的，滿網(wǎng)都是轉(zhuǎn)載的冕茅，我看到的原文地址：http://blog.sina.com.cn/s/blog_5d97745a0101ey63.html
那么ZK Server最基礎(chǔ)的東西是什么呢蛹找？應(yīng)該是Paxos了。
所以本文會(huì)介紹Paxos以及它在ZKServer中對(duì)應(yīng)的實(shí)現(xiàn)乍楚。先說(shuō)
Paxos届慈，它是一個(gè)基于消息傳遞的一致性算法忿偷，Leslie
Lamport在1990年提出臊泌，近幾年被廣泛應(yīng)用于分布式計(jì)算中
Google的Chubby，
Apache的Zookeeper都是基于它的理論來(lái)實(shí)現(xiàn)的缺虐，
Paxos還被認(rèn)為是到目前為止唯一的分布式一致性算法高氮，其它的算法都是Paxos的改進(jìn)或簡(jiǎn)化。
有個(gè)問(wèn)題要提一下剪芍，Paxos有一個(gè)前提：
**沒(méi)有拜占庭將軍問(wèn)題
就是說(shuō)Paxos只有在一個(gè)可信的計(jì)算環(huán)境中才能成立，
這個(gè)環(huán)境是不會(huì)被入侵所破壞的饱普。
關(guān)于Paxos的具體描述可以在Wiki中找到：
http://zh.wikipedia.org/zh-cn/Paxos算法状共。
網(wǎng)上關(guān)于Paxos分析的文章也很多。
這里希望用最簡(jiǎn)單的方式加以描述并建立起Paxos和ZKServer的對(duì)應(yīng)關(guān)系冯袍。
Paxos描述了這樣一個(gè)場(chǎng)景碾牌，有一個(gè)叫做Paxos的小島(Island)上面住了一批居民，島上面所有的事情由一些特殊的人決定舶吗，他們叫做議員(Senator)誓琼。
議員的總數(shù)(SenatorCount)是確定的，不能更改腹侣。島上每次環(huán)境事務(wù)的變更都需要通過(guò)一個(gè)提議(Proposal)，
每個(gè)提議都有一個(gè)編號(hào)(PID)今穿，這個(gè)編號(hào)是一直增長(zhǎng)的伦籍，不能倒退腮出。
每個(gè)提議都需要超過(guò)半數(shù)((SenatorCount)/2+1)的議員同意才能生效芝薇。
每個(gè)議員只會(huì)同意大于當(dāng)前編號(hào)的提議，包括已生效的和未生效的馋劈。
如果議員收到小于等于當(dāng)前編號(hào)的提議晾嘶，他會(huì)拒絕，并告知對(duì)方：你的提議已經(jīng)有人提過(guò)了垒迂。
這里的當(dāng)前編號(hào)是每個(gè)議員在自己記事本上面記錄的編號(hào)机断，他不斷更新這個(gè)編號(hào)。
整個(gè)議會(huì)不能保證所有議員記事本上的編號(hào)總是相同的±艏椋現(xiàn)在議會(huì)有一個(gè)目標(biāo)：
**保證所有的議員對(duì)于提議都能達(dá)成一致的看法。
好她混，現(xiàn)在議會(huì)開始運(yùn)作旺拉，所有議員一開始記事本上面記錄的編號(hào)都是0棵磷。
有一個(gè)議員發(fā)了一個(gè)提議：將電費(fèi)設(shè)定為1元/度。
他首先看了一下記事本沉桌，嗯算吩，當(dāng)前提議編號(hào)是0，那么我的這個(gè)提議的編號(hào)就是1蔼夜，
于是他給所有議員發(fā)消息：1號(hào)提議压昼，設(shè)定電費(fèi)1元/度瘤运。
其他議員收到消息以后查了一下記事本匠题，哦，當(dāng)前提議編號(hào)是0韭山，
這個(gè)提議可接受钱磅，于是他記錄下這個(gè)提議并回復(fù)：我接受你的1號(hào)提議，
同時(shí)他在記事本上記錄：當(dāng)前提議編號(hào)為1续搀。
發(fā)起提議的議員收到了超過(guò)半數(shù)的回復(fù)，立即給所有人發(fā)通知：1號(hào)提議生效彪杉！
收到的議員會(huì)修改他的記事本牵咙，
將1好提議由記錄改成正式的法令，當(dāng)有人問(wèn)他電費(fèi)為多少時(shí)渴丸，他會(huì)查看法令并告訴對(duì)方：1元/度另凌。
現(xiàn)在看沖突的解決：
假設(shè)總共有三個(gè)議員S1-S3，S1和S2同時(shí)發(fā)起了一個(gè)提議:1號(hào)提議土童，設(shè)定電費(fèi)工坊。
S1想設(shè)為1元/度,S2想設(shè)為2元/度。結(jié)果S3先收到了S1的提議王污，于是他做了和前面同樣的操作。
緊接著他又收到了S2的提議昭齐，結(jié)果他一查記事本，咦泊业，這個(gè)提議的編號(hào)小于等于我的當(dāng)前編號(hào)1，
于是他拒絕了這個(gè)提議：對(duì)不起吁伺，這個(gè)提議先前提過(guò)了篮奄。
于是S2的提議被拒絕，S1正式發(fā)布了提議:1號(hào)提議生效窟却。
S2向S1或者S3打聽并更新了1號(hào)法令的內(nèi)容夸赫，然后他可以選擇繼續(xù)發(fā)起2號(hào)提議。
好茬腿，我覺(jué)得Paxos的精華就這么多內(nèi)容。
現(xiàn)在讓我們來(lái)對(duì)號(hào)入座握础，看看在ZKServer里面Paxos是如何得以貫徹實(shí)施的悴品。
小島(Island)——ZK Server Cluster
議員(Senator)——ZK Server
提議(Proposal)——ZNode Change(Create/Delete/SetData…)
提議編號(hào)(PID)——Zxid(ZooKeeper Transaction Id)
正式法令——所有ZNode及其數(shù)據(jù)
**
貌似關(guān)鍵的概念都能一一對(duì)應(yīng)上，但是等一下定枷，Paxos島上的議員應(yīng)該是人人平等的吧届氢，
而ZKServer好像有一個(gè)Leader的概念。
沒(méi)錯(cuò)贱迟，其實(shí)Leader的概念也應(yīng)該屬于Paxos范疇的絮供。
如果議員人人平等茶敏，在某種情況下會(huì)由于提議的沖突而產(chǎn)生一個(gè)“活鎖”
（所謂活鎖我的理解是大家都沒(méi)有死，都在動(dòng)贮乳，但是一直解決不了沖突問(wèn)題）。
Paxos的作者Lamport在他的文章”ThePart-TimeParliament“中闡述了這個(gè)問(wèn)題并給出了解決方案——在所有議員中設(shè)立一個(gè)總統(tǒng)亚茬，只有總統(tǒng)有權(quán)發(fā)出提議浓恳，如果議員有自己的提議，必須發(fā)給總統(tǒng)并由總統(tǒng)來(lái)提出颈将。
好晴圾，我們又多了一個(gè)角色：總統(tǒng)。
**總統(tǒng)——ZK ServerLeader
**
又一個(gè)問(wèn)題產(chǎn)生了死姚，總統(tǒng)怎么選出來(lái)的？oh, my god! It’s a long story.在淘寶核心系統(tǒng)團(tuán)隊(duì)的Blog上面有一篇文章是介紹如何選出總統(tǒng)的撒蟀，有興趣的可以去看看：http://rdc.taobao.com/blog/cs/?p=162
現(xiàn)在我們假設(shè)總統(tǒng)已經(jīng)選好了温鸽，下面看看ZK Server是怎么實(shí)施的。
**情況一：
**屁民甲(Client)到某個(gè)議員(ZKServer)那里詢問(wèn)(Get)某條法令的情況(ZNode的數(shù)據(jù))姑尺，議員毫不猶豫的拿出他的記事本(localstorage)蝠猬，查閱法令并告訴他結(jié)果，同時(shí)聲明：我的數(shù)據(jù)不一定是最新的柄粹。你想要最新的數(shù)據(jù)匆绣？沒(méi)問(wèn)題，等著堪夭，等我找總統(tǒng)Sync一下再告訴你。
**情況二：
**屁民乙(Client)到某個(gè)議員(ZKServer)那里要求政府歸還欠他的一萬(wàn)元錢恨豁，議員讓他在辦公室等著爬迟，自己將問(wèn)題反映給了總統(tǒng)，總統(tǒng)詢問(wèn)所有議員的意見(jiàn)付呕，多數(shù)議員表示欠屁民的錢一定要還凡涩，于是總統(tǒng)發(fā)表聲明，從國(guó)庫(kù)中拿出一萬(wàn)元還債活箕，國(guó)庫(kù)總資產(chǎn)由100萬(wàn)變成99萬(wàn)。屁民乙拿到錢回去了(Client函數(shù)返回)克蚂。
**情況三：
**總統(tǒng)突然掛了筋讨，議員接二連三的發(fā)現(xiàn)聯(lián)系不上總統(tǒng)，于是各自發(fā)表聲明赤屋，推選新的總統(tǒng)壁袄，總統(tǒng)大選期間政府停業(yè)，拒絕屁民的請(qǐng)求涩僻。
到此為止吧栈顷，當(dāng)然還有很多其他的情況，但這些情況總是能在Paxos的算法中找到原型并加以解決室抽。這也正是我們認(rèn)為Paxos是Zookeeper的靈魂的原因蛙卤。當(dāng)然ZKServer還有很多屬于自己特性的東西：Session,Watcher，Version等等等等神年，需要我們花更多的時(shí)間去研究和學(xué)習(xí)行嗤。
