本章討論構(gòu)建分布式系統(tǒng)的相關(guān)算法和協(xié)議，類似于事務(wù)，構(gòu)建分布式容錯系統(tǒng)也需要建立一套通用的抽象機(jī)制和與之對應(yīng)的技術(shù)保證。
共識：所有節(jié)點(diǎn)對某項(xiàng)提議達(dá)成一致，解決共識問題可以解決許多應(yīng)用需求，例如主節(jié)點(diǎn)的選取。
一致性保證
最終一致性：如果停止更新并等待一定長度（未知長度）的時(shí)間，所有讀請求會返回相同的內(nèi)容，意味著所有副本最終收斂于相同的值。最終一致性是非常弱的保證，未保證合適會收斂。
本章將探索比最終一致性更強(qiáng)的一致性模型，首先討論線性化，之后討論順序關(guān)系，最后討論如何自動提交分布式事務(wù)，解決共識問題。
可線性化
可線性化：讓一個系統(tǒng)看起來只有一個數(shù)據(jù)副本，保證讀取到最近最新的值
如上圖所示，由于不同副本復(fù)制完成的時(shí)間不同，Alice和Bob先后讀取不同的副本，但是后讀取的Bob卻讀取到了更舊的數(shù)據(jù)。
如何達(dá)到可線性化？
多個客戶端讀取數(shù)據(jù)庫的同一條數(shù)據(jù)，如果不加限制，只要讀操作與寫操作存在一定的重疊，那么讀取結(jié)果可能是寫入前結(jié)果，也可能是寫入后結(jié)果。
為了實(shí)現(xiàn)線性化，可以添加約束：一旦某個讀操作讀到新值后，之后所有的讀操作都需要返回新值。
上圖中引入了原子比較-設(shè)置操作（Compare and Set, CAS），而客戶端B的最后一個讀操作因?yàn)榕c客戶端C的最后一個CAS操作有時(shí)間上的重疊，導(dǎo)致返回值不滿足可線性化。上圖中可以看到，請求順序、數(shù)據(jù)庫處理順序、響應(yīng)順序互相之間呈弱相關(guān)，這是由網(wǎng)絡(luò)延遲導(dǎo)致的，另外可線性化模型沒有假定事務(wù)之間是具有隔離的。
線性化的依賴條件
線性化在某些場景下，對于保障系統(tǒng)正常工作至關(guān)重要
加鎖和主節(jié)點(diǎn)選取
集群中選取主節(jié)點(diǎn)必須嚴(yán)格保證只有一個主節(jié)點(diǎn)，否則會產(chǎn)生腦裂，選舉主節(jié)點(diǎn)可以視為每個節(jié)點(diǎn)都嘗試獲得鎖，但只有一個可以成功。etcd、zookeeper可以用來實(shí)現(xiàn)分布式鎖和主節(jié)點(diǎn)選舉。
約束與唯一性保證
某些約束需要嚴(yán)格的線性化，例如不應(yīng)當(dāng)有相同的用戶ID，銀行賬戶余額不應(yīng)當(dāng)為負(fù)值。
跨通道的時(shí)間依賴
上圖所示為圖片調(diào)整服務(wù)架構(gòu)，理想的運(yùn)行狀態(tài)為圖片上傳后由數(shù)據(jù)庫存儲，再將處理任務(wù)消息發(fā)送至隊(duì)列，最終由調(diào)整模塊收到消息后讀取圖片進(jìn)行最終的調(diào)整。但是由于網(wǎng)絡(luò)原因，可能導(dǎo)致保存過慢，處理模塊收到消息時(shí)圖片仍為保存完成。
實(shí)現(xiàn)線性化系統(tǒng)
不同復(fù)制方案是否滿足可線性化：
主從復(fù)制（部分滿足可線性化）
共識算法（可線性化）
多主復(fù)制（不可線性化）
無主復(fù)制（可能不線性化）
線性化與quorum
如上圖所示，quorum并不能保證一致性，這是因?yàn)椴煌?jié)點(diǎn)復(fù)制完成的時(shí)間不一致。
線性化的代價(jià)
如圖所示為兩個互相復(fù)制的數(shù)據(jù)中心，如果網(wǎng)絡(luò)發(fā)生中斷，則會面臨可用性和可線性化的抉擇。
CAP理論
可線性化、可用性、分區(qū)容錯性的三選二，不過CAP理論只考慮了一種一致性模型即線性化模型和一種錯誤模型即網(wǎng)絡(luò)分區(qū)。
可線性化與網(wǎng)絡(luò)延遲
雖然線性化是個很有用的保證，但是很少有系統(tǒng)真正滿足線性化，甚至因?yàn)橹噶钪嘏诺仍騿螜C(jī)上的內(nèi)存都未必滿足可線性化。當(dāng)今的數(shù)據(jù)庫傾向于犧牲一致性來提高系統(tǒng)的容錯性。
順序保證
可線性化意味著操作按照某種順序執(zhí)行，順序、可線性化、共識之間存在深刻的聯(lián)系。
順序與因果關(guān)系
保證順序的一大意義在于，保證一系列操作的因果關(guān)系。如果系統(tǒng)服從因果關(guān)系規(guī)定的順序，則稱之為因果一致性。
因果順序并非全序
全序/偏序：集合內(nèi)元素支持/不支持比較。對于可線性化系統(tǒng)中，各個操作總能指出先后順序；如果兩個事件為并發(fā)，則無法比較兩者的因果關(guān)系，并發(fā)意味著時(shí)間線的分支與合并，不同分支上的操作無法直接比較。
可線性化強(qiáng)于因果一致性
可線性化是因果一致性的充分條件，但線性化并不是保證因果一致性的唯一方式。
捕獲因果依賴關(guān)系
對于事件之間的因果關(guān)系進(jìn)行邏輯分析。
序列號排序
相比于檢測因果關(guān)系，使用序列號或者時(shí)間戳對于事件進(jìn)行排序是更好的方法，對于主從復(fù)制數(shù)據(jù)庫，主節(jié)點(diǎn)可以簡單的遞增計(jì)數(shù)器，為每個復(fù)制日志分配一個單調(diào)遞增的序列號，從節(jié)點(diǎn)按照主節(jié)點(diǎn)日志的順序進(jìn)行同步操作，從而結(jié)果一定滿足因果一致性。
非因果序列發(fā)生器
如果主節(jié)點(diǎn)不唯一，產(chǎn)生單調(diào)遞增的序列號就不那么容易了，有一些序列號產(chǎn)生方法，但是這些方法并不能滿足產(chǎn)生單調(diào)遞增遞增的序列號，例如：每個節(jié)點(diǎn)特定產(chǎn)生奇數(shù)或偶數(shù)的序列號，利用墻上時(shí)鐘作為序列號，預(yù)先給不同節(jié)點(diǎn)分配序列號范圍，但是以上方法都不能嚴(yán)格保證因果關(guān)系。
Lamport時(shí)間戳
Lamport時(shí)間戳要求每個節(jié)點(diǎn)保存自己已經(jīng)處理的請求總數(shù)與ID信息，每個客戶端和節(jié)點(diǎn)都跟蹤迄今為止所見過的最大計(jì)數(shù)器數(shù)值，從而確保了全序關(guān)系。
時(shí)間戳排序依然不夠
僅僅依賴Lamport時(shí)間戳，無法解決唯一性約束的問題。
全序關(guān)系廣播
全序關(guān)系廣播通常指節(jié)點(diǎn)間交換消息的某種協(xié)議，滿足兩個基本的安全屬性：
可靠發(fā)送：如果消息發(fā)送到了某個節(jié)點(diǎn)，則一定要發(fā)送到所有節(jié)點(diǎn)
嚴(yán)格有序：消息總是以相同順序發(fā)送
即使網(wǎng)絡(luò)或節(jié)點(diǎn)發(fā)生故障，全序關(guān)系廣播算法的實(shí)現(xiàn)也必須保證以上兩條
使用全序關(guān)系廣播
ZooKeeper，etcd等實(shí)現(xiàn)了全序關(guān)系廣播，全序關(guān)系廣播和共識之間存在密切的聯(lián)系。全序關(guān)系廣播可以用來實(shí)現(xiàn)可串行化事務(wù)，提供fencing鎖服務(wù)。
采用全序關(guān)系廣播實(shí)現(xiàn)線性化存儲
采用線性化存儲實(shí)現(xiàn)全序關(guān)系廣播
分布式事務(wù)與共識
許多場景需要集群節(jié)點(diǎn)達(dá)成某種一致：
主節(jié)點(diǎn)選?。哄e誤的共識將導(dǎo)致腦裂
原子事務(wù)提交：為了維護(hù)分布式事務(wù)的原子性，需要對事務(wù)的結(jié)果達(dá)成一致
原子提交與兩階段提交
原子性防止失敗的事務(wù)破壞系統(tǒng)。
從單節(jié)點(diǎn)到分布式的原子提交
單個節(jié)點(diǎn)事務(wù)的原子性依賴于嚴(yán)格的執(zhí)行順序，多個節(jié)點(diǎn)的事務(wù)和單個節(jié)點(diǎn)的事務(wù)具有顯著區(qū)別。
兩階段提交
2PC引入了協(xié)調(diào)者，并將提交/中止過程分成兩個階段，在任何階段來自于任何節(jié)點(diǎn)的否定回答都會中止事務(wù)。
系統(tǒng)的承諾
在2PC中存在兩個“不歸路”：
階段1中參與者的做出肯定提交的承諾
階段2中協(xié)調(diào)者做出提交決定
如果這兩個承諾發(fā)生，那么即便出現(xiàn)故障也會不斷重試而不會中止。
協(xié)調(diào)者發(fā)生故障
協(xié)調(diào)者的崩潰導(dǎo)致參與者只能一直等待協(xié)調(diào)者的消息，除非協(xié)調(diào)者恢復(fù)。
三階段提交
2PC也被稱為阻塞式原子提交協(xié)議，3PC作為2PC的替代方案假定有限的
