微信讀書：從Paxos到Zookeeper：分布式一致性原理與實(shí)踐（閱讀摘錄）
CAP理論
CAP理論告訴我們，一個(gè)分布式系統(tǒng)不可能同時(shí)滿足一致性(C：Consistency)、可用性(A：Availability)和分區(qū)容錯(cuò)性(P：Partition tolerance)這三個(gè)基本需求，最多只能同時(shí)滿足其中的兩項(xiàng)。
BASE理論
BASE是Basically Available（基本可用）、Soft state（軟狀態(tài)）和Eventually consistent （最終一致性）三個(gè)短語的簡(jiǎn)寫，是由來自eBay的架構(gòu)師Dan Pritchett在其文章BASE：An Acid Alternative[插圖]中第一次明確提出。
2PC與3PC
2PC
2PC，是Two-Phase Commit的縮寫，即二階段提交，是計(jì)算機(jī)網(wǎng)絡(luò)尤其是在數(shù)據(jù)庫領(lǐng)域內(nèi)，為了使基于分布式系統(tǒng)架構(gòu)下的所有節(jié)點(diǎn)在進(jìn)行事務(wù)處理過程中能夠保持原子性和一致性而設(shè)計(jì)的一種算法。通常，二階段提交協(xié)議也被認(rèn)為是一種一致性協(xié)議，用來保證分布式系統(tǒng)數(shù)據(jù)的一致性。目前，絕大部分的關(guān)系型數(shù)據(jù)庫都是采用二階段提交協(xié)議來完成分布式事務(wù)處理的，利用該協(xié)議能夠非常方便地完成所有分布式事務(wù)參與者的協(xié)調(diào)，統(tǒng)一決定事務(wù)的提交或回滾，從而能夠有效地保證分布式數(shù)據(jù)一致性，因此二階段提交協(xié)議被廣泛地應(yīng)用在許多分布式系統(tǒng)中。
3PC
3PC，是Three-Phase Commit的縮寫，即三階段提交，是2PC的改進(jìn)版，其將二階段提交協(xié)議的“提交事務(wù)請(qǐng)求”過程一分為二，形成了由CanCommit、PreCommit和do Commit三個(gè)階段組成的事務(wù)處理協(xié)議。
Paxos算法
拜占廷將軍問題
拜占庭帝國有許多支軍隊(duì)，不同軍隊(duì)的將軍之間必須制訂一個(gè)統(tǒng)一的行動(dòng)計(jì)劃，從而做出進(jìn)攻或者撤退的決定，同時(shí)，各個(gè)將軍在地理上都是被分隔開來的，只能依靠軍隊(duì)的通訊員來進(jìn)行通訊。然而，在所有的通訊員中可能會(huì)存在叛徒，這些叛徒可以任意篡改消息，從而達(dá)到欺騙將軍的目的。
這就是著名的“拜占廷將軍問題”。從理論上來說，在分布式計(jì)算領(lǐng)域，試圖在異步系統(tǒng)和不可靠的通道上來達(dá)到一致性狀態(tài)是不可能的，因此在對(duì)一致性的研究過程中，都往往假設(shè)信道是可靠的。而事實(shí)上，大多數(shù)系統(tǒng)都是部署在同一個(gè)局域網(wǎng)中的，因此消息被篡改的情況非常罕見；另一方面，由于硬件和網(wǎng)絡(luò)原因而造成的消息不完整問題，只需一套簡(jiǎn)單的校驗(yàn)算法即可避免——因此，在實(shí)際工程實(shí)踐中，可以假設(shè)不存在拜占庭問題，也即假設(shè)所有消息都是完整的，沒有被篡改的。那么，在這種情況下需要什么樣的算法來保證一致性呢？
ZooKeeper的ZAB協(xié)議
ZooKeeper并沒有完全采用Paxos算法，而是使用了一種稱為ZooKeeper Atomic Broadcast（ZAB，ZooKeeper原子消息廣播協(xié)議）的協(xié)議作為其數(shù)據(jù)一致性的核心算法。
ZAB協(xié)議的核心是定義了對(duì)于那些會(huì)改變ZooKeeper服務(wù)器數(shù)據(jù)狀態(tài)的事務(wù)請(qǐng)求的處理方式，即：
所有事務(wù)請(qǐng)求必須由一個(gè)全局唯一的服務(wù)器來協(xié)調(diào)處理，這樣的服務(wù)器被稱為L(zhǎng)eader服務(wù)器，而余下的其他服務(wù)器則成為Follower服務(wù)器。Leader服務(wù)器負(fù)責(zé)將一個(gè)客戶端事務(wù)請(qǐng)求轉(zhuǎn)換成一個(gè)事務(wù)Proposal（提議），并將該P(yáng)roposal分發(fā)給集群中所有的Follower服務(wù)器。之后Leader服務(wù)器需要等待所有Follower服務(wù)器的反饋，一旦超過半數(shù)的Follower服務(wù)器進(jìn)行了正確的反饋后，那么Leader就會(huì)再次向所有的Follower服務(wù)器分發(fā)Commit消息，要求其將前一個(gè)Proposal進(jìn)行提交。
ZooKeeper的Watcher的特性
一次性
客戶端串行執(zhí)行
輕量
ZooKeeper的ACL機(jī)制
ZooKeeper的ACL權(quán)限控制和Unix/Linux操作系統(tǒng)中的ACL有一些區(qū)別，讀者可以從三個(gè)方面來理解ACL機(jī)制，分別是：權(quán)限模式(Scheme)、授權(quán)對(duì)象(ID)和權(quán)限(Permission)，通常使用“scheme：id：permission”來標(biāo)識(shí)一個(gè)有效的ACL信息。
ZooKeeper的會(huì)話激活
為了保持客戶端會(huì)話的有效性，在ZooKeeper的運(yùn)行過程中，客戶端會(huì)在會(huì)話超時(shí)時(shí)間過期范圍內(nèi)向服務(wù)端發(fā)送PING請(qǐng)求來保持會(huì)話的有效性，我們俗稱“心跳檢測(cè)”。
單機(jī)版ZooKeeper服務(wù)器啟動(dòng)流程
集群版ZooKeeper服務(wù)器啟動(dòng)流程
Leader
在接收到來自其他服務(wù)器的投票后，針對(duì)每一個(gè)投票，服務(wù)器都需要將別人的投票和自己的投票進(jìn)行PK，PK的規(guī)則如下。
優(yōu)先檢查ZXID。ZXID比較大的服務(wù)器優(yōu)先作為L(zhǎng)eader。
如果ZXID相同的話，那么就比較myid。myid比較大的服務(wù)器作為L(zhǎng)eader服務(wù)器。
一旦Leader所在的機(jī)器掛了，那么整個(gè)集群將暫時(shí)無法對(duì)外服務(wù)，而是進(jìn)入新一輪的Leader選舉。
簡(jiǎn)單地說，通常哪臺(tái)服務(wù)器上的數(shù)據(jù)越新，那么越有可能成為L(zhǎng)eader，原因很簡(jiǎn)單，數(shù)據(jù)越新，那么它的ZXID也就越大，也就越能夠保證數(shù)據(jù)的恢復(fù)。當(dāng)然，如果集群中有幾個(gè)服務(wù)器具有相同的ZXID，那么SID較大的那臺(tái)服務(wù)器成為L(zhǎng)eader。
Quorum：過半機(jī)器數(shù)
這是整個(gè)Leader選舉算法中最重要的一個(gè)術(shù)語，我們可以把這個(gè)術(shù)語理解為是一個(gè)量詞，指的是ZooKeeper集群中過半的機(jī)器數(shù)，如果集群中總的機(jī)器數(shù)是n的話，那么可以通過下面這個(gè)公式來計(jì)算quorum的值：
例如，如果集群機(jī)器總數(shù)是3，那么quorum就是2。
請(qǐng)求處理鏈
使用責(zé)任鏈模式來處理每一個(gè)客戶端請(qǐng)求是ZooKeeper的一大特色。
Foller
從角色名字上可以看出，F(xiàn)ollower服務(wù)器是ZooKeeper集群狀態(tài)的跟隨者，其主要工作有以下三個(gè)。
處理客戶端非事務(wù)請(qǐng)求，轉(zhuǎn)發(fā)事務(wù)請(qǐng)求給Leader服務(wù)器。
參與事務(wù)請(qǐng)求Proposal的投票。
參與Leader選舉投票。
Observer
Observer是ZooKeeper自3.3.0版本開始引入的一個(gè)全新的服務(wù)器角色。從字面意思看，該服務(wù)器充當(dāng)了一個(gè)觀察者的角色——其觀察ZooKeeper集群的最新狀態(tài)變化并將這些狀態(tài)變更同步過來。Observer服務(wù)器在工作原理上和Follower基本是一致的，對(duì)于非事務(wù)請(qǐng)求，都可以進(jìn)行獨(dú)立的處理，而對(duì)于事務(wù)請(qǐng)求，則會(huì)轉(zhuǎn)發(fā)給Leader服務(wù)器進(jìn)行處理。和Follower唯一的區(qū)別在于，Observer不參與任何形式的投票，包括事務(wù)請(qǐng)求Proposal的投票和Leader選舉投票。簡(jiǎn)單地講，Observer服務(wù)器只提供非事務(wù)服務(wù)，通常用于在不影響集群事務(wù)處理能力的前提下提升集群的非事務(wù)處理能力。
ZooKeeper的消息類型
ZooKeeper的消息類型大體上可以分為四類，分別是：數(shù)據(jù)同步型、服務(wù)器初始化型、請(qǐng)求處理型和會(huì)話管理型。
