本文是讀ZooKeeper: Wait-free coordination for Internet-scale systems的筆記楷兽，從第一手資料了解zookeeper
概述
什么是zookeeper已慢？
a service for coordinating(協(xié)調(diào)) processes of distributed applications跋涣，是一個(gè)重要的基礎(chǔ)服務(wù)潮尝，目標(biāo)是從更底層提供一個(gè)簡(jiǎn)單菱阵、高性能的服務(wù)乳蓄，用來(lái)按需構(gòu)建同步服務(wù)
zookeeper（動(dòng)物管理員），為什么叫這個(gè)名字聂宾？
zookeeper是Hadoop和Hbase的重要組件，hadoop里面各種組件都是以動(dòng)物命名的诊笤，而zookeeper相當(dāng)于這動(dòng)物園的管理員了
zookeeper特點(diǎn)是什么系谐？
提供了一組通用（generic）的，無(wú)等待的（wait-free）api讨跟，同時(shí)提供了兩個(gè)重要的特性：
保證每個(gè)客戶端請(qǐng)求FIFO
所有寫(xiě)請(qǐng)求串行進(jìn)行
結(jié)果是讀請(qǐng)求能夠讀本地纪他，從而能夠滿足可擴(kuò)展性
介紹
大的分布式系統(tǒng)對(duì)coordination提出了各種各樣的需求:
Con?guration：包括靜態(tài)的操作數(shù)組和動(dòng)態(tài)的配置參數(shù)
Group membership：哪些server還存活著
leader election：每個(gè)server都負(fù)責(zé)什么
解決上述coordination需求的一種方案是：為每種coordination需求都開(kāi)發(fā)專門的服務(wù)。但是我們要知道一個(gè)道理：更powerful primitives的實(shí)現(xiàn)可以用于less powerful primitives晾匠，所以基于這個(gè)假設(shè)我們?cè)谠O(shè)計(jì)coordination的服務(wù)上：我們不在實(shí)現(xiàn)具體的primitives茶袒，而是提供通用（generic）的API來(lái)實(shí)現(xiàn)滿足個(gè)性化的primitives，一旦作出這種決策凉馆，帶來(lái)的好處有兩點(diǎn)：
coordination kernel幫助我們?cè)诓桓淖兎?wù)核心的情況下實(shí)現(xiàn)新的primitives
根據(jù)應(yīng)用需求提供更多樣化的primitives
在設(shè)計(jì)ZooKeeper的API的時(shí)候薪寓，我們移除了阻塞primitives，如鎖澜共，基于的考慮有如下兩點(diǎn)：
阻塞primitives會(huì)導(dǎo)致處理慢的客戶端影響相對(duì)較快的客戶端
由于請(qǐng)求在處理上依賴于其他客戶端的響應(yīng)和失敗的檢查向叉，那ZooKeeper本身實(shí)現(xiàn)上也會(huì)更復(fù)雜
ZooKeeper由于實(shí)現(xiàn)了wait-free的數(shù)據(jù)對(duì)象，從而和其他基于阻塞語(yǔ)義（blocking primitives）有了顯著的區(qū)別嗦董，ZooKeeper在組織wait-free的數(shù)據(jù)對(duì)象借鑒了文件系統(tǒng)的思路母谎，將wait-free的數(shù)據(jù)對(duì)象按層級(jí)組織起來(lái)，不同只是移除了open和close這種阻塞方法京革。
僅僅靠wait-free來(lái)實(shí)現(xiàn)coordination是不夠的奇唤，還需要提供操作的有序保證（order guarantees）：每個(gè)客戶端FIFO匹摇，所有寫(xiě)請(qǐng)求linearizable咬扇。
ZooKeeper實(shí)現(xiàn)了pipelined architecture，提高了系統(tǒng)的吞吐来惧∪呃酰客戶端可以同時(shí)發(fā)出多個(gè)請(qǐng)求，異步執(zhí)行，同時(shí)保證請(qǐng)求的FIFO隅居。
為了實(shí)現(xiàn)寫(xiě)請(qǐng)求linearizable钠至，實(shí)現(xiàn)了Zab協(xié)議，一個(gè)leader-based atomic broadcast protocol胎源，但是對(duì)于讀請(qǐng)求棉钧，我們不適用Zab，只是本地讀涕蚤，這樣能很方便的擴(kuò)展系統(tǒng)宪卿。
在客戶端緩存數(shù)據(jù)可以有效的提高系統(tǒng)性能，但是緩存的數(shù)據(jù)怎么更新呢万栅？ZooKeeper使用watch機(jī)制佑钾，不直接操作客戶端緩存，這是因?yàn)椋河捎贑hubby直接管理客戶端緩存烦粒，一旦某個(gè)客戶端處理慢了（可能是掛了）休溶，會(huì)導(dǎo)致阻塞數(shù)據(jù)更新。針對(duì)這個(gè)問(wèn)題扰她，Chubby使用租期來(lái)解決兽掰，一旦某個(gè)客戶端有錯(cuò)誤，不會(huì)影響更新操作太長(zhǎng)時(shí)間徒役，但這也只是確定了影響的上限孽尽，無(wú)法避免，而ZooKeeper的watches可以徹底解決改問(wèn)題忧勿。
總結(jié)起來(lái)杉女，本篇論文的主要內(nèi)容是：
Coordination kernel：基礎(chǔ)設(shè)施，提出了wait-free的方案
Coordination recipes：應(yīng)用狐蜕，個(gè)性化primitives的實(shí)現(xiàn)
Experience with Coordination：心得宠纯，具體案例和評(píng)測(cè)
Zookeeper服務(wù)
ZooKeeper提供了client library來(lái)訪問(wèn)服務(wù)，client library主要做兩件事：
管理client和ZooKeeper之間的網(wǎng)絡(luò)連接
提供ZooKeeper的api
術(shù)語(yǔ)：
client：a user of the ZooKeeper service
server：a process providing the ZooKeeper service
znode：an in-memory data node in the ZooKeeper data
data tree：像文件系統(tǒng)一樣按層級(jí)組織的命名空間
update层释，write：改變data tree狀態(tài)的操作
session：client和ZooKeeper之間的網(wǎng)絡(luò)連接
Service overview
ZooKeeper給客戶端提供了znode的抽象婆瓜，客戶端通過(guò)api來(lái)操作znode中存儲(chǔ)的數(shù)據(jù)，znode的地址類似文件系統(tǒng)中的path贡羔，像上圖中節(jié)點(diǎn)p_1就通過(guò)路徑/app1/p_1來(lái)訪問(wèn)廉白，客戶端可以創(chuàng)建兩種znode：
Regular: 需要客戶端顯式的創(chuàng)建和刪除
ephemeral: 客戶端創(chuàng)建，也可以刪除乖寒，也可以當(dāng)會(huì)話終止時(shí)候讓系統(tǒng)自動(dòng)刪除
除此之外猴蹂，創(chuàng)建的時(shí)候可以帶sequential的flag，此時(shí)創(chuàng)建znode p楣嘁，則會(huì)自動(dòng)帶上一個(gè)下標(biāo)n磅轻，n是一個(gè)單調(diào)遞增的數(shù)珍逸，并且滿足seq(parent)>= max(children)，意思是新建的node聋溜，其下標(biāo)總是大于其父節(jié)點(diǎn)下面創(chuàng)建過(guò)的所有node的最大n谆膳。
watches怎么創(chuàng)建？
讀請(qǐng)求上設(shè)置watch參數(shù)
watches作用撮躁？
客戶端不必輪詢服務(wù)器獲取數(shù)據(jù)漱病，當(dāng)數(shù)據(jù)發(fā)生改變的時(shí)候，通知客戶端
watches什么時(shí)候失效把曼？
當(dāng)數(shù)據(jù)發(fā)生改變通知客戶端后
session關(guān)閉
watches通知了什么杨帽？
watches通知只是告知狀態(tài)改變了，但是不提供改變的數(shù)據(jù)
數(shù)據(jù)模型
如圖一所示：類似于文件系統(tǒng)嗤军，但是znodes不是用來(lái)做數(shù)據(jù)存儲(chǔ)的注盈，而是用來(lái)跟實(shí)際的應(yīng)用映射的，像圖1中叙赚，有兩個(gè)應(yīng)用app1,app2当凡，app1下面實(shí)現(xiàn)了個(gè)簡(jiǎn)單的group membership protocol。
雖然znode設(shè)計(jì)之初不是為了存儲(chǔ)數(shù)據(jù)纠俭，但是也可以存儲(chǔ)一些meta-data或者con?guration信息，同時(shí)znode本身會(huì)存儲(chǔ)time stamps 和 version counters等元信息
會(huì)話（sessions）
代表client和ZooKeeper之間的網(wǎng)絡(luò)連接浪慌，作用有：
server端可以通過(guò)sessions超時(shí)來(lái)判斷客戶端是否健在
客戶端可以通過(guò)sessions觀察其操作的一連串變化
sessions使得client的連接可以從一個(gè)server透明的轉(zhuǎn)移到另一個(gè)server冤荆，因此可以持續(xù)的提供client服務(wù)
Client API
create(path, data, flags)
delete(path, version) //if znode.version = version, then delete
exists(path, watch)
getData(path, watch)
setData(path, data, version) //if znode.version = version, then update
getChildren(path, watch)
sync()
以上所有操作有syn和asyn兩個(gè)版本。ZooKeeper的客戶端保證所有寫(xiě)操作是完全有序的权纤，寫(xiě)操作后其他client的寫(xiě)能看到钓简。
在訪問(wèn)的znode的時(shí)候都是通過(guò)完整的path來(lái)訪問(wèn)的，而不是像文件系統(tǒng)那樣通過(guò)open,close來(lái)操作文件句柄汹想，大大簡(jiǎn)化了servers端的復(fù)雜度外邓，不需要保存額外的信息了。
ZooKeeper guarantees
Linearizable writes：所有寫(xiě)請(qǐng)求有序
FIFO client order：每個(gè)客戶端請(qǐng)求FIFO
考慮場(chǎng)景：leader election
當(dāng)新的leader產(chǎn)生的時(shí)候古掏，需要改變大量的配置后损话，通知其他processes，需要滿足兩個(gè)要求：
新leader改變配置的時(shí)候槽唾，其他processes不能讀取不完整的配置
新leader在改變配置過(guò)程中掛了丧枪，其他processes不能使用這個(gè)不完整的配置
通過(guò)鎖能滿足第一個(gè)需求，zookeeper的實(shí)現(xiàn)：
新leader改變前刪除 ready znode
改變配置（通過(guò)pipeline加速）
新建 ready znode
因?yàn)閷?xiě)順序的保證庞萍，其他客戶端能看到ready的時(shí)候拧烦，肯定新配置也生效了，如果在更改配置中l(wèi)eader掛了钝计，就不會(huì)有ready恋博。
上面仍然有一個(gè)問(wèn)題：如果process先是看到了ready齐佳，此時(shí)在讀取之前，leader刪除了ready债沮，開(kāi)始更改配置炼吴，那process會(huì)讀取到不完整的配置了，怎么解決呢秦士？
這是通過(guò)對(duì)通知的順序性保證解決的：
if a client is watching for a change, the client will see the noti?cation event before it sees the new state of the system after the change is made.Consequently, if the process that reads the ready znode requests to be noti?ed of changes to that znode, it will see a noti?cation informing the client of the change before it can read any of the new con?guration.
客戶端將會(huì)在看到改變后的狀態(tài)之前收到通知事件缺厉，因此，當(dāng)process可以讀取ready新?tīng)顟B(tài)之前隧土，會(huì)先收到狀態(tài)改變的通知
另一個(gè)可能的問(wèn)題是：客戶端之間除了ZooKeeper之外提针，還有別的通信通道，場(chǎng)景是：
A和B在ZooKeeper上有共享數(shù)據(jù)曹傀，A改變數(shù)據(jù)后辐脖，通過(guò)其他通信手段告訴B數(shù)據(jù)改變了，此時(shí)B去讀取數(shù)據(jù)皆愉，可能會(huì)讀取不到改變的數(shù)據(jù)嗜价，因?yàn)閆ooKeeper集群可能存在的主從延遲，解決方案是：B讀之前先發(fā)個(gè)sync請(qǐng)求幕庐，類似于文件系統(tǒng)中的flush操作久锥，讓數(shù)據(jù)同步給各個(gè)server。
除此之外异剥，ZooKeeper還有兩個(gè)保證：
高可用瑟由，只要大多數(shù)機(jī)器還存活，就能提供服務(wù)
數(shù)據(jù)可靠：只要ZooKeeper回復(fù)寫(xiě)成功冤寿，則數(shù)據(jù)最終一定會(huì)存在在服務(wù)器上
Examples of primitives
配置管理
約定
群管理（Group Membership）
鎖
最簡(jiǎn)單的鎖就是在特定path里檢測(cè)有沒(méi)有znode歹苦，沒(méi)有則acquire lock，新建ephemeral znode督怜。release的時(shí)候刪除該znode殴瘦。但這么做會(huì)有問(wèn)題，如果有很多個(gè)client在等待鎖号杠，那么當(dāng)鎖釋放的時(shí)候會(huì)產(chǎn)生驚群效應(yīng)(herd effect)蚪腋。第二點(diǎn)是這只能實(shí)現(xiàn)排他鎖（exclusive locking）
Lock
1 n = create(l + “/lock-”, EPHEMERAL|SEQUENTIAL)
2 C = getChildren(l, false)
3 if n is lowest znode in C, exit
4 p = znode in C ordered just before n
5 if exists(p, true) wait for watch event
6 goto 2
Unlock
1 delete(n)
只有seq numeber最低的znode能夠acuqire鎖，不然就等待姨蟋，每次只通知一個(gè)client
- 讀寫(xiě)鎖
Write Lock
1 n = create(l + “/write-”, EPHEMERAL|SEQUENTIAL)
2 C = getChildren(l, false)
3 if n is lowest znode in C, exit
4 p = znode in C ordered just before n
5 if exists(p, true) wait for event
6 goto 2
Read Lock
1 n = create(l + “/read-”, EPHEMERAL|SEQUENTIAL)
2 C = getChildren(l, false)
3 if no write znodes lower than n in C, exit
4 p = write znode in C ordered just before n
5 if exists(p, true) wait for event
6 goto 3
寫(xiě)鎖和前面的一樣
讀鎖需要等待seq num小的znode里沒(méi)有寫(xiě)操作辣吃，讀可以并發(fā)
ZooKeeper Applications
The Fetching Service
Katta
Yahoo! Message Broker
ZooKeeper Implementation
圖4是Zookeeper的組件，如果用raft來(lái)理解的話芬探，就包括下面幾部分
一致性協(xié)議（Zab）
狀態(tài)機(jī)（Database）
Log（日志持久化）
