1.為什么分布式火

隨著摩爾定律碰到瓶頸沛简，越來越多的系統(tǒng)要依靠分布式集群架構(gòu)來實(shí)現(xiàn)海量數(shù)據(jù)處理和可擴(kuò)展計(jì)算能力杆勇。

2.分布式的核心問題

參考資料：https://yeasy.gitbooks.io/blockchain_guide/content/distribute_system/problem.html

2.1一致性問題

多個(gè)節(jié)點(diǎn)在協(xié)議（往往通過某種共識算法）保障下贪壳，試圖使得它們對處理結(jié)果達(dá)成某種程度的一致。
要求;1.Termination蚜退，有限時(shí)間完成 2.Consensus 不同節(jié)點(diǎn)結(jié)果一致 3.Validity 合法性闰靴，決策的記過必須是其他進(jìn)程提出的提案

帶約束的一致性
首先明確：一致性約束和性能只能平衡，不能同時(shí)精確关霸。就跟物理的測不準(zhǔn)性質(zhì)一樣
強(qiáng)一致性：
順序一致性（[Sequential Consistency]：保證局部的一致性传黄，類比于java 的并發(fā)，某個(gè)線程的a before b
線性一致性（[Linearizability Consistency]：這個(gè)相當(dāng)于保證了全局一致性队寇，需要用全局的時(shí)鐘或鎖實(shí)現(xiàn)
弱一致性：weak consisitency膘掰，放寬一致性要求，實(shí)現(xiàn)效率Eventual Consistency

2.2 共識算法

問題挑戰(zhàn)：
把故障（不響應(yīng)）的情況稱為“非拜占庭錯(cuò)誤”佳遣，惡意響應(yīng)的情況稱為“拜占庭錯(cuò)誤”（對應(yīng)節(jié)點(diǎn)為拜占庭節(jié)點(diǎn)）识埋。

tip: 1： FLP 不可能性原理

FLP 不可能原理：在網(wǎng)絡(luò)可靠，存在節(jié)點(diǎn)失效（即便只有一個(gè)）的最小化異步模型系統(tǒng)中零渐，不存在一個(gè)可以解決一致性問題的確定性算法窒舟。

不要浪費(fèi)時(shí)間去為異步分布式系統(tǒng)設(shè)計(jì)在任意場景下都能實(shí)現(xiàn)共識的算法。

e.g.三個(gè)人在不同房間诵盼，進(jìn)行投票（投票結(jié)果是 0 或者 1）惠豺。三個(gè)人彼此可以通過電話進(jìn)行溝通，但經(jīng)常會有人時(shí)不時(shí)地睡著风宁。比如某個(gè)時(shí)候洁墙，A 投票 0，B 投票 1戒财，C 收到了兩人的投票热监，然后 C 睡著了。A 和 B 則永遠(yuǎn)無法在有限時(shí)間內(nèi)獲知最終的結(jié)果饮寞。如果可以重新投票孝扛，則類似情形每次在取得結(jié)果前發(fā)生：
FLP 原理實(shí)際上說明對于允許節(jié)點(diǎn)失效情況下，純粹異步系統(tǒng)無法確保一致性在有限時(shí)間內(nèi)完成幽崩。

物理和數(shù)學(xué)研究確定了問題的極端情況苦始，即邊界的情形，但工程通過多次重復(fù)等方式慌申，達(dá)到可以接受的的效果陌选，就像物理的不確定性原理，粒子的位置和速度不能同時(shí)確定，但仍然能進(jìn)行量子研究應(yīng)用

tip 2：CAP原理

在一個(gè)分布式系統(tǒng)中柠贤，（互相連接和共享數(shù)據(jù)），不可能同時(shí)確保一致性（Consistency）类缤、可用性（Availablity）和分區(qū)容忍性（Partition）臼勉，設(shè)計(jì)中往往需要弱化對某個(gè)特性的保證
這里的分區(qū)容忍性（Partition）指：網(wǎng)絡(luò)可能發(fā)生分區(qū)，即節(jié)點(diǎn)之間的通信不可保障餐弱。
系統(tǒng)如果不能在時(shí)限內(nèi)達(dá)成數(shù)據(jù)一致性宴霸，就意味著發(fā)生了分區(qū)的情況

首先我們考慮P，分區(qū)容忍性的前提是分區(qū)情況的發(fā)生膏蚓，由于網(wǎng)絡(luò)情況是無法預(yù)測的瓢谢，所以你必須保證分區(qū)容忍性。
那么我們的選擇有2個(gè)驮瞧，CP和AP氓扛，即網(wǎng)絡(luò)可能出現(xiàn)分區(qū)時(shí)候，系統(tǒng)是無法同時(shí)保證一致性和可用性的
CP是什么论笔？
出現(xiàn)分區(qū)情況時(shí)采郎，節(jié)點(diǎn)收到請求后因?yàn)闆]有得到其他人的確認(rèn)就不應(yīng)答
AP是什么？
出現(xiàn)分區(qū)情況時(shí)狂魔，節(jié)點(diǎn)只能應(yīng)答非一致的結(jié)果

實(shí)際應(yīng)用場景
既然 CAP 不可同時(shí)滿足蒜埋，則設(shè)計(jì)系統(tǒng)時(shí)候必然要弱化對某個(gè)特性的支持。

弱化一致性
對結(jié)果一致性不敏感的應(yīng)用最楷，可以允許在新版本上線后過一段時(shí)間才更新成功整份，期間不保證一致性。
例如網(wǎng)站靜態(tài)頁面內(nèi)容籽孙、實(shí)時(shí)性較弱的查詢類數(shù)據(jù)庫等怯伊，CouchDB、Cassandra 等為此設(shè)計(jì)婿脸。

弱化可用性
對結(jié)果一致性很敏感的應(yīng)用咽弦，例如銀行取款機(jī)，當(dāng)系統(tǒng)故障時(shí)候會拒絕服務(wù)胎挎。Redis 等為此設(shè)計(jì)沟启。
Paxos、Raft 等算法犹菇，主要處理這種情況德迹。

弱化分區(qū)容忍性
現(xiàn)實(shí)中，網(wǎng)絡(luò)分區(qū)出現(xiàn)概率減小揭芍，但較難避免胳搞。某些關(guān)系型數(shù)據(jù)庫、ZooKeeper 即為此設(shè)計(jì)。
實(shí)踐中肌毅，網(wǎng)絡(luò)通過雙通道等機(jī)制增強(qiáng)可靠性筷转，達(dá)到高穩(wěn)定的網(wǎng)絡(luò)通信。

tip 3：Paxos和Raft

故事背景是古希臘 Paxon 島上的多個(gè)法官在一個(gè)大廳內(nèi)對一個(gè)議案進(jìn)行表決悬而，如何達(dá)成統(tǒng)一的結(jié)果呜舒。他們之間通過服務(wù)人員來傳遞紙條，但法官可能離開或進(jìn)入大廳笨奠，服務(wù)人員可能偷懶去睡覺袭蝗。
Paxos 被廣泛應(yīng)用在 Chubby、ZooKeeper 這樣的系統(tǒng)
參考資料：https://yeasy.gitbooks.io/blockchain_guide/content/distribute_system/paxos.html
重要概念般婆，proposer：提出提案到腥，acceptor：負(fù)責(zé)投票，learner：被告知提案結(jié)果

需要保證 safety：決議是proposer提出的蔚袍，且無歧義和liveness：有限時(shí)間

當(dāng)獲取的acceptor支持超過一半時(shí)乡范，即發(fā)送結(jié)果給所有人進(jìn)行確認(rèn)，因此當(dāng)超過1/2的正常節(jié)點(diǎn)存在時(shí)啤咽，系統(tǒng)可以達(dá)成共識篓足，如果在proposer提案時(shí)故障，則可通過超時(shí)機(jī)制闰蚕，加重新新一輪提案加以解決栈拖。

需要兩階段提交

Why

在于只有一個(gè)階段的話，在多提案+多接收者情況下没陡，無法確認(rèn)是否獲得通過的提案是最終結(jié)果涩哟，可能還有后續(xù)的提案繼續(xù)提交通過。
所以引入新的一個(gè)階段盼玄，在proposer前一階段拿到反饋后贴彼，判斷這個(gè)提案是否被大多數(shù)接受，需要對其進(jìn)行最終確認(rèn)

how

準(zhǔn)備階段解決大家對哪個(gè)提案進(jìn)行投票的問題埃儿，提交階段解決確認(rèn)最終值的問題器仗。

prepare階段：
proposer：發(fā)送提案和編號到acceptor試探是否獲取多數(shù)接受者的支持
acceptor：保留接受到的提案的最大編號和接受的最大提案，時(shí)刻更新當(dāng)前的最大提案號童番，不接受下雨最大提案號的提案（一般來說精钮，算法當(dāng)中，越是后提交的剃斧，即新的提案轨香，編號越大，使用時(shí)間戳等方式）

commit：
proposer：如果收到大多數(shù)的回復(fù)幼东，則可準(zhǔn)備發(fā)送帶有提案號的接收消息臂容。如果收到的回復(fù)不帶有新的提案科雳，則說明鎖定成功，使用自己的提案脓杉；如果收到的回復(fù)帶有新的內(nèi)容，則替換為編號更大的提案球散；如果沒有收到足夠多的請求蚌堵，則再次發(fā)出請求
acceptor：接受消息后，如果發(fā)現(xiàn)提案號不小于已接受的最大提案號沛婴，則接受該提案，并更新最大提案號

一旦多數(shù)接受了共同的提案值督赤，則形成決議嘁灯，成為最終確認(rèn)的提案

Raft

是Paxos的簡化實(shí)現(xiàn)。
包括三種角色：leader躲舌、candidate 和 follower丑婿，其基本過程為：

Leader 選舉：每個(gè) candidate 隨機(jī)經(jīng)過一定時(shí)間都會提出選舉方案，最近階段中得票最多者被選為 leader没卸；
同步 log：leader 會找到系統(tǒng)中 log 最新的記錄羹奉，并強(qiáng)制所有的 follower 來刷新到這個(gè)記錄；
注：此處 log 并非是指日志消息约计，而是各種事件的發(fā)生記錄诀拭。

tip 2：拜占庭問題和算法

拜占庭將軍（Byzantine Generals Problem）問題，是 Leslie Lamport 1982 年提出用來解釋一致性問題的一個(gè)虛構(gòu)模型煤蚌。拜占庭是古代東羅馬帝國的首都耕挨，由于地域?qū)拸V，守衛(wèi)邊境的多個(gè)將軍（系統(tǒng)中的多個(gè)節(jié)點(diǎn)）需要通過信使來傳遞消息尉桩，達(dá)成某些一致的決定筒占。但由于將軍中可能存在叛徒（系統(tǒng)中節(jié)點(diǎn)出錯(cuò)），這些叛徒將努力向不同的將軍發(fā)送不同的消息蜘犁，試圖會干擾一致性的達(dá)成翰苫。

對于拜占庭問題來說，假如節(jié)點(diǎn)總數(shù)為 N这橙，叛變將軍數(shù)為 F奏窑，則當(dāng)N≥3F+1時(shí)，問題才有解屈扎，即 Byzantine Fault Tolerant (BFT) 算法良哲。
最簡單的
例如，N=3,F=1 時(shí)助隧。
提案人不是叛變者筑凫，提案人發(fā)送一個(gè)提案出來滑沧，叛變者可以宣稱收到的是相反的命令。則對于第三個(gè)人（忠誠者）收到兩個(gè)相反的消息巍实，無法判斷誰是叛變者滓技，則系統(tǒng)無法達(dá)到一致。

提案人是叛變者棚潦，發(fā)送兩個(gè)相反的提案分別給另外兩人令漂，另外兩人都收到兩個(gè)相反的消息，無法判斷究竟誰是叛變者丸边，則系統(tǒng)無法達(dá)到一致叠必。
更一般的推到了解即可

新的解決思路

拜占庭問題之所以難解，在于任何時(shí)候系統(tǒng)中都可能存在多個(gè)提案（因?yàn)樘岚赋杀竞艿停┟媒眩⑶乙瓿勺罱K的一致性確認(rèn)過程十分困難纬朝，容易受干擾。但是一旦確認(rèn)骄呼，即為最終確認(rèn)共苛。

比特幣的區(qū)塊鏈網(wǎng)絡(luò)在設(shè)計(jì)時(shí)提出了創(chuàng)新的 PoW（Proof of Work） 算法思路。一個(gè)是限制一段時(shí)間內(nèi)整個(gè)網(wǎng)絡(luò)中出現(xiàn)提案的個(gè)數(shù)（增加提案成本）蜓萄，另外一個(gè)是放寬對最終一致性確認(rèn)的需求隅茎，約定好大家都確認(rèn)并沿著已知最長的鏈進(jìn)行拓寬。系統(tǒng)的最終確認(rèn)是概率意義上的存在嫉沽。這樣辟犀，即便有人試圖惡意破壞，也會付出很大的經(jīng)濟(jì)代價(jià)（付出超過系統(tǒng)一半的算力）绸硕。

后來的各種 PoX 系列算法踪蹬，也都是沿著這個(gè)思路進(jìn)行改進(jìn)，采用經(jīng)濟(jì)上的懲罰來制約破壞者