分布式系統(tǒng)中，保證集群中所有節(jié)點中的數(shù)據(jù)完全相同并能夠?qū)δ硞€提案（Proposal）達成一致抖剿，核心過程往往需要通過共識算法來達成分布式一致性。
區(qū)塊鏈系統(tǒng)是一個分布式系統(tǒng)，對于分布式多節(jié)點結(jié)構(gòu)片吊，首要問題就是保證一致性。
CAP理論
區(qū)塊鏈作為分布式系統(tǒng)协屡，因此也符合分布式計算領(lǐng)域公認的定理：CAP理論俏脊。
- CAP理論基本概念
CAP定理指出，一個分布式計算系統(tǒng)肤晓，不可能同時滿足以下三點：
1.一致性（Consistency）：更新操作成功并返回客戶端完成后爷贫，分布式的所有節(jié)點在同一時間的數(shù)據(jù)完全一致认然。任何操作應(yīng)該都是原子的，發(fā)生在后面的事件能看到前面事件發(fā)生導(dǎo)致的結(jié)果漫萄，注意這里指的是強一致性卷员。
2.可用性（Availability）：在有限時間內(nèi)，任何非失敗節(jié)點都能應(yīng)答請求腾务，但是不能保證獲取到的數(shù)據(jù)時最新的毕骡。
3.分區(qū)容錯性（Partition tolerance）：網(wǎng)絡(luò)可能發(fā)生分區(qū)，即節(jié)點之間的通信不可保障岩瘦。分布式系統(tǒng)即使在部分節(jié)點故障或者分區(qū)故障的情況下未巫，依然能夠?qū)ν馓峁┓?wù)（進行容錯處理）。- CA without P（弱化分區(qū)容錯性）
如果要保證C（強一致性）和A（可用性）启昧，則無法保證分區(qū)容錯性橱赠。但是分布式系統(tǒng)是無法避免分區(qū)的，兩階段的提交算法（如ZooKeeper等）主要考慮了這種設(shè)計箫津。 - CP without A（弱化可用性）
弱化A（可用性）狭姨，那么每個請求都需要在server之間保持強一致性，而分區(qū)的出現(xiàn)會導(dǎo)致節(jié)點之間數(shù)據(jù)同步時間延長苏遥，但是CP是可以保證的饼拍。例如對一致性比較敏感的應(yīng)用，例如ATM機田炭、電子支付等师抄，當(dāng)系統(tǒng)出現(xiàn)故障時，直接拒絕服務(wù)教硫。 - AP without C（弱化一致性）
要求高可用性并允許分區(qū)容錯叨吮，則需要弱化一致性。因為一旦一個節(jié)點或分區(qū)發(fā)生故障失去聯(lián)系瞬矩，為了保證高可用性茶鉴，每個節(jié)點只能使用本地數(shù)據(jù)庫提供服務(wù)，但這樣會導(dǎo)致各個節(jié)點的數(shù)據(jù)不一致。這種情況一般是對一致性不敏感的應(yīng)用，可以允許在新版本上線后過一段時間才最終更新完成灸撰，期間不保證一致。例如NoSQL割粮、DNS、web緩存都屬于此類媚污。
- CA without P（弱化分區(qū)容錯性）
PoW共識機制為AP模式舀瓢，犧牲強一致性，確保高可用性和分區(qū)容錯性耗美，從而達到最終一致性京髓。
如果區(qū)塊鏈要滿足一致性C（強一致性）航缀，即所有節(jié)點的操作的執(zhí)行順序都完全相同，一個節(jié)點提交更新操作需同時反映在其他節(jié)點朵锣。在異步網(wǎng)絡(luò)中，想要滿足CP模式甸私，則需要建立一個中心節(jié)點存儲所有數(shù)據(jù)诚些，其他節(jié)點與之相連，則更新和獲取數(shù)據(jù)的操作均從中心節(jié)點獲取皇型，但這與區(qū)塊鏈的去中心化相違背诬烹，因此區(qū)塊鏈不能滿足CAP理論的C。
FLP不可能原理
在網(wǎng)絡(luò)可靠弃鸦，存在節(jié)點失效（即便是一個）的最小化異步模型系統(tǒng)中绞吁，不存在一個可以解決一致性問題的確定性算法。
因此唬格，不存在一個在異步分布式系統(tǒng)中任何情況下都能達成一致共識的共識算法家破。
一致性模型
- 定義
分布式系統(tǒng)中各節(jié)點，執(zhí)行一些列操作后购岗，在約定協(xié)議下汰聋，對外呈現(xiàn)的狀態(tài)是一致的。即保證集群中所有節(jié)點中的數(shù)據(jù)完全相同并且能夠?qū)δ硞€提案(Proposal)達成一致喊积。
一致性不代表結(jié)果正確與否烹困，而是系統(tǒng)對外呈現(xiàn)的狀態(tài)一致與否。所有節(jié)點都達成失敗狀態(tài)也是一種一致乾吻。
分布式事務(wù)一致性
事務(wù)是數(shù)據(jù)庫管理系統(tǒng)執(zhí)行過程中的一個邏輯單元髓梅，由一個有限的數(shù)據(jù)庫操作序列構(gòu)成。
確保操作序列在多個服務(wù)節(jié)點中執(zhí)行的順序是一致的绎签。
分布式數(shù)據(jù)一致性
數(shù)據(jù)在多份副本中存儲時枯饿，各副本中的數(shù)據(jù)是一致的。
因此诡必，保證分布式事務(wù)一致性鸭你，也就保證了數(shù)據(jù)的一致性。
- 一致性要求
1.有限性：達成一致的結(jié)果在有限時間內(nèi)完成擒权。
2.約同性：不同節(jié)點最終完成決策的結(jié)果是相同袱巨。
3.合法性：決策的結(jié)果必須是某個節(jié)點提出的方案。
在分布式系統(tǒng)中碳抄，如果一個由節(jié)點提出的提案愉老，能夠在有限時間內(nèi)使得所有節(jié)點達成一致的結(jié)果，那么該提案達到了一致性剖效。
- 分類
按照一致性要求的不同嫉入，可以分為四大類：嚴格一致性焰盗、強一致性、弱一致性以及最終一致性咒林。
1.嚴格一致性（strict consistency）
對于數(shù)據(jù)項
X的任何讀操作將返回最近一次對X進行的寫操作所對應(yīng)的值熬拒。
嚴格一致性的問題在于其依賴于絕對的全局時間。對于進程來說垫竞，所有寫操作都是瞬間可見的澎粟，系統(tǒng)維持著一個絕對的全局時間。如果一個數(shù)據(jù)項被改變欢瞪，在數(shù)據(jù)項改變之后活烙，任何節(jié)點的任何進程隨時執(zhí)行讀操作，所有在該數(shù)據(jù)項上執(zhí)行的后續(xù)讀操作都將得到新數(shù)值遣鼓。
嚴格一致性是在系統(tǒng)不發(fā)生任何故障且所有節(jié)點之間的通信無需任何時間這種理想的條件下啸盏，才能達到。此時骑祟，整個分布式系統(tǒng)其實就等價于一臺機器』嘏常現(xiàn)實中是不可能達成的。
2.強一致性（strict consistency）
當(dāng)分布式系統(tǒng)更新操作完成后次企，任何多個進程或線程訪問系統(tǒng)都會獲得最新值粉怕。
??順序一致性（sequential consistency）
任何執(zhí)行結(jié)果都相同，所有進程對數(shù)據(jù)存儲的讀抒巢、寫操作是按照某種序列順序執(zhí)行贫贝，并且每個進程的操作按照程序所指定的順序出現(xiàn)在這個序列中。
??線性一致性（Linearizability）
??一種弱于嚴格一致性但強于順序一致性的一致性模型是線性一致性蛉谜。
假設(shè)操作具有一個全局有效的時間戳稚晚，但是這個時鐘僅具有有限的精度。要求時間戳在前的進程先執(zhí)行型诚。
??線性化是根據(jù)一系列同步時鐘確定序列順序客燕。
3.弱一致性（weak consistency）
系統(tǒng)并不保證后續(xù)進程或線程的訪問都會返回最新的更新值。系統(tǒng)在數(shù)據(jù)成功寫入后狰贯，不承諾立即可以讀到最新寫入的值也搓，也不會承諾多久之后可以讀取到。但會盡可能保證在某個時間級別（比如秒級別）之后涵紊，可以讓數(shù)據(jù)達到一致性狀態(tài)傍妒。
也就是說，如果能容忍后續(xù)的部分或者全部訪問不到摸柄，則是弱一致性颤练。
4.最終一致性（eventual consistency）
弱一致性的特定形式。系統(tǒng)保證在沒有后續(xù)更新的前提下驱负，系統(tǒng)最終返回上一次更新操作的值嗦玖。在沒有故障發(fā)生的前提下患雇，不一致窗口的時間主要受通信延遲，系統(tǒng)負載和復(fù)制副本的個數(shù)影響宇挫。
也就是說苛吱，如果經(jīng)過一段時間后要求能訪問到更新后的數(shù)據(jù)，則是最終一致性器瘪。
DNS是一個典型的最終一致性系統(tǒng)翠储。
??最終一致性的變型
- 因果一致性
如果A進程在更新后向B進程通知更新的完成，那么B的訪問操作將會返回更新的值娱局。沒有因果關(guān)系的C進程將會遵循最終一致性的原則彰亥。- 讀己所寫一致性
因果一致性的特定形式咧七。一個進程總可以讀到自己更新的數(shù)據(jù)衰齐。- 會話一致性
讀己所寫一致性的特定形式。進程在訪問存儲系統(tǒng)同一個會話內(nèi)继阻，系統(tǒng)保證該進程讀己所寫耻涛。- 單調(diào)讀一致性
如果一個進程已經(jīng)讀取到一個特定值，那么該進程不會讀取到該值以前的任何值瘟檩。- 單調(diào)寫一致性
系統(tǒng)保證對同一個進程的寫操作串行化抹缕。
上述最終一致性的不同方式可以進行組合，e.g. 單調(diào)讀一致性和讀己所寫一致性可以組合實現(xiàn)墨辛。組合后實現(xiàn)：讀取自己更新的數(shù)據(jù)卓研，和一旦讀到最新的版本就不會再讀到老版本，對于架構(gòu)上的程序開發(fā)睹簇，會少很多麻煩奏赘。
- 一致性問題場景
1.節(jié)點之間的網(wǎng)絡(luò)通信是不可靠的，包括消息延遲太惠、亂序和內(nèi)容錯誤等磨淌；
2.節(jié)點的處理時間無法保障，結(jié)果可能出現(xiàn)錯誤凿渊，甚至節(jié)點自身可能發(fā)生宕機梁只。
3.同步調(diào)用可以簡化設(shè)計，但會嚴重降低分布式系統(tǒng)的可擴展性埃脏。
共識性
- 定義
分布式系統(tǒng)中多個節(jié)點間搪锣，相互對某個狀態(tài)達成一致結(jié)果的過程。
??共識性與一致性的區(qū)別
一致性往往指分布式系統(tǒng)中多個副本對外呈現(xiàn)的數(shù)據(jù)的狀態(tài)彩掐。如順序一致性淤翔、線性一致性，描述了多個節(jié)點對數(shù)據(jù)狀態(tài)的維護能力佩谷。
共識性描述了分布式系統(tǒng)中多個節(jié)點之間旁壮，彼此對某個狀態(tài)達成一致結(jié)果的過程监嗜。
一致性描述的是結(jié)果狀態(tài)，共識則是達成一致性的一種手段抡谐、過程裁奇。達成某種共識并不意味著就保障了一致性（此處指強一致性）。只能說共識機制麦撵，能夠?qū)崿F(xiàn)某種程度上的一致性刽肠。
共識算法
共識算法解決的是對某個提案（Proposal），大家達成一致意見的過程免胃。提案的含義在分布式系統(tǒng)中十分寬泛音五，如多個事件發(fā)生的順序、某個鍵對應(yīng)的值羔沙、誰是領(lǐng)導(dǎo).....等等躺涝，可以認為任何需要達成一致的信息都是一個提案。
實踐中扼雏，一致性的結(jié)果往往還需要客戶端的特殊支持坚嗜，典型地通過訪問足夠多個服務(wù)節(jié)點來驗證確保獲取共識后的結(jié)果。
對于分布式系統(tǒng)來說诗充，各個節(jié)點通常都是相同的確定性狀態(tài)機模型（又稱為狀態(tài)機復(fù)制問題苍蔬，state-machine replication），從相同初始狀態(tài)開始接收相同順序的指令蝴蜓，則可以保證相同的結(jié)果狀態(tài)碟绑。因此，系統(tǒng)中多個節(jié)點最關(guān)鍵的是對多個事件的順序進行共識茎匠，即排序格仲。
拜占庭將軍問題
在分布式計算上，不同的計算機通過訊息交換汽抚，嘗試達成共識抓狭；但有時，系統(tǒng)上協(xié)調(diào)計算機（Coordinator / Commander）或 成員計算（Member / Lieutanent）可能因系統(tǒng)錯誤并交換錯的信息造烁，導(dǎo)致影響最終的系統(tǒng)一致性否过。即，在系統(tǒng)不同的機器之間會傳遞錯誤的消息惭蟋，這種情況即為拜占庭問題苗桂，與「網(wǎng)絡(luò)分割、機器崩潰」是不同的告组。
一般情況下煤伟，失敗、出現(xiàn)故障（非響應(yīng)）情況被稱為非拜占庭錯誤，偽造信息惡意響應(yīng)的情況被稱為拜占庭錯誤便锨，對應(yīng)的節(jié)點也稱為拜占庭節(jié)點围辙。
因此拜占庭錯誤問題討論的范圍更廣，它是討論在允許少數(shù)惡意節(jié)點的情況下達成一致的問題放案。
- 非拜占庭容錯類算法（Crash Fault Tolerance 「CFT」）
針對常見的非拜占庭錯誤（普通錯誤情況）姚建，已經(jīng)存在一些經(jīng)典的解決算法，包括Paxos吱殉、Raft及其變種等掸冤。這類容錯算法往往性能比較好，處理較快友雳，容忍不超過一半的故障節(jié)點稿湿。
Raft協(xié)議不能容忍拜占庭問題，但是能夠在非拜占庭錯誤情況下押赊，有網(wǎng)絡(luò)延遲饺藤、分區(qū)、丟包考杉、冗余和亂序等錯誤情況出現(xiàn)時策精，都可以保證其操作的正確性舰始。
- 拜占庭容錯類算法（Byzantine Fault Tolerance「BFT」）
對于要能容忍拜占庭的問題崇棠，一般包括PBFT（Practical Byzantine Fault Tolerance）為代表的確定性系列算法、PoW為代表的概率算法等丸卷。- 對于確定性算法，一旦達成對某個結(jié)果的共識就不可逆轉(zhuǎn)谜嫉，即共識是最終結(jié)果萎坷。
- 對于概率性算法，共識結(jié)果則是零時的沐兰，隨著時間的推移或某種強化哆档，共識結(jié)果被推翻的概率越來越小，成為事實上的最終結(jié)果住闯。
???拜占庭容錯算法往往性能較差瓜浸，容錯不超過1/3的故障節(jié)點。
接下來要對非拜占庭問題的一致性算法Paxos和Raft比原，以及拜占庭問題的一致性算法PoS插佛、PoW和DPoS進行學(xué)習(xí)。
