資料一致性的問題
目前基本生產環境中后臺系統都是分布式系統，比如說一個網路變更（組態檔或者其他內容）如何在分布式網路中得到一致的執行結果，這是一個問題。
cap原理及一致性演算法分類
在2000年 Principles of Distributed Computing大會上Eric Brewer發表了CAP理論。在2002年, Seth Gilbert和Nancy Lynch發表了更加正式的CAP理論論證。 cap原理中，有三個要素：
1. 一致性（Consistency）
2. 可用性（Availablity）
3. 磁區容忍性（Partition Tolerance）
分布式系統只能滿足其中兩個要素。對于分布式說系統而言，磁區容忍性是基本要求，設計分布式系統就是在一致性及可用性中取一個平衡。有兩種衡量一致性的方式，客戶端一致性：從開發者/客戶端的角度：他們如何觀察資料更新。服務器端一致性：從服務器端的角度：更新時如何流經系統，和系統對更新有和保證。
客戶端一致性
1. 強一致性：在更新操作完成之后，任何后續的訪問將回傳更新的值。
2. 弱一致性：系統不能保證后續訪問回傳更新的值。需要在一些條件滿足之后，更新的值才能回傳。從更新操作開始，到系統保證任何觀察者總是看到更新的值的這期間被稱為不一致視窗。
3. 最終一致性：這是弱一致性的特殊形式；存盤系統保證如果沒有對某個物件的新更新操作，最終所有的訪問將回傳這個物件的最后更新的值。
服務器端一致性
在服務器端，我們需要更加深入地分析更新是如何流經系統，并由此來理解什么驅動了不同模式。這些模式正是系統的開發者能夠體驗到的。讓我們先作如下定義。
1. N=存盤資料副本的結點數量
2. W=在更新完成之前，需要同時認可接收的副本數量
3. R=當讀操作訪問資料物件，需要訪問的副本數量
如果W+R>N, 那么寫集合和讀集合總是重疊并且能保證強一致性。 如在主備RDBMS中，如果使用了同步副本的方式，N=2，W=2和R=1。不管客戶端讀哪個副本，它總是獲得一致性結果。
如果W+R<=N, 那么不能保證強一致性，只能是弱一致性或最終一致性。如在主備RDBMS中，使用異步同步副本，并開啟從副本讀功能的方式，那么N=2, W=1和R=1。在這種情況下，R+W=N, 一致性不能得到保證。
兩階段提交演算法
待寫
Paxos演算法
Paxos演算法主要應用在不存在惡意節點，只存在故障節點的分布式系統。Paxos演算法把網路上所有節點分成三種角色：
1. Proposer：提出一個提案，等待大家批準為結案。往往是客戶端擔任該角色。
2. Accepter：負責對提案進行投票。往往是服務端擔任該角色。
3. Learner：被告知結案結果，并與之統一，不參與投票程序。可能是客戶端或服務端。
并缺演算法需要滿足安全性(saftey)和活性（liveness）兩方面的約束要求：
1. safety: 保證決議結果正確性。一次執行決議程序中，只批準一個最終決議，意味著多數接受的結果能成為決議。
2. liveness: 保證決議程序能在有限時間內完成。決議總會產生，并且learners能獲得被批準的決議。
Raft演算法
Raft演算法把網路上所有節點分成三種角色：
1. Leader: 處理所有與客戶端互動，日志復制，一般一次只有一個。
2. Follower: 類似選民，被動接收資訊。
3. Candidate: 類似Proposer，但可以被選為一個新的Leader。
Raft演算法分成兩個階段，第一階段是選舉程序，第二階段是在Leader帶領下進行操作，比如日志復制。假設網路上一共有N臺服務器，下面是具體工程：
1. 任何服務器都可以成為Candidate，它向其他服務器發出選擇自己的需求
2. 其他服務器回復同意，只要達到N/2＋1的票數，該服務器當選為Leader
3. Leader向其他服務器發送命令，如日志復制命令
4. Leader與Followers之間通過心跳維護通信
5. 一旦Leader失聯，Followers中等待一定時間超時后成為Candidate，然后重復前面的流程
具體程序可以看一下這個影片Raft Demo
POW
前面說的演算法更多是確定節點數分布式共識演算法，實際上在區塊鏈網路中有很多節點，而去節點數可變。在這里，我們把上述所說的決議變成記賬（兩者其實都是一樣），要在區塊鏈達成記賬一致性（共識），無非需要解決三個問題：
1. 誰擁有記賬權
2. 別的節點為什么需要采納提出節點的記賬結果
3. 記賬結果如何保證一致性
2009年，中本聰提出劃時代基于概率的POW（Proof Of Work,作業量證明）演算法，并運用到位元幣上。POW演算法原理比較簡單，先說比較簡單的情況，在一輪記賬程序中，全網會設定一個難度值，每個節點把區塊打包后不斷通過特定演算法算區塊hash值，直到找到比難度小的hash值則可以產生一個合法記賬，并廣播出去。其他節點接收到記賬后可以很方便驗證記賬合法性，合法后把帳記到自己本地賬本，同時讓自己進入下一輪記賬算力的競爭。由于合法記賬需要消耗大量的算力，需要消耗實際的電力，其他節點會傾向承認此次記賬。
雖然可以通過演算法大大降低特定時間內合法記賬的個數，但并不能保證沖突，比如在同一個競爭的周期中有兩筆合法記賬從而導致分叉。當其他節點接收到兩筆合法記賬的時候，可以通過特定策略（比如隨機選擇或者優先選擇先接收到），選取一塊合法記賬區塊，并在此基礎上繼續進行下一輪記賬算力競爭。由于合法記賬產出的隨記性，最終得到更快確認（比如6次確認）的記賬區塊會成為主鏈上的記賬區塊，分叉記賬區塊被拋棄。
POS
POW需要浪費大量的算力做無意義的運算來保障網路安全性，這是一直被詬病的地方。針對這一點，POS(Proof Of Stake，權益證明)演算法被提出，通過所有者權益證明來產生合法記賬。POS演算法原理就是在網路中擁有更多特定權益的人更多機會產生合法記賬，而由于擁有更多特定權益會傾向于維護網路的安全，同時引入一定的懲戒措施來保證作惡會受到制裁。
POS演算法中的權益有很多種實作方式，比如說引入“幣齡”的概念，也就是說持幣者持幣的時間越長，幣齡越長，所擁有的權益越大。同時為鼓勵更多人持幣，可引入利息制度，通過經濟上鼓勵，讓更多人忠于網路維護網路，保證網路安全。
同樣，產生合法記賬方式也有多種，比如通過權益大小適當降低計算難度進行快速產生一次合法記賬，或者在一群權益較高的節點中輪訓獲取記賬權益快速產生合法記賬。
通過引入權益為公信力進行背書，可以減少計算次數及提升出塊速度。
DPOS
在POS演算法基礎上衍生DPOS(Delegated Proof of Stake，股份授權證明機制)演算法。原理是讓所有持幣人都有機會選出自己的代表，比如全網有1萬個參與人，通過一定的演算法，參與人以自己的代幣為權益證明，選出101個代表，這些代表可以輪流或者采用PoS演算法加權的獲得記賬權，進行記賬。 DPoS理論上不要求選出的代表個體本身是權益所有人，看起來更民主，更開放。網路參與者做為選民有機會選出自己的代表，來給自己的利益代言。如果選出的代表不作為（輪到自己記賬時不記賬），或者作惡，可以把他們踢掉，如有必要進行懲罰（選民們也有可能被懲罰）。否則記賬者有機會獲得相應的獎勵，也有可能將獎勵發放給選出自己的民眾們。
PBFT
POW, POS, DPOS均是公有鏈上面最終一致性的共識演算法。由于公有鏈實際上是多節點連接網路，會存在通信延遲，網路故障等，因此會在同一個時間段內有很大概率存在多個節點獲得記賬權，產生多個合法記賬從而導致分叉。分叉的存在實際上就意味著當前的合法記賬區塊只是被暫時被接受，需要隨著時間推移，有更多合法記賬區塊對它進行確認才會更大概率的被接受而達到最終一致性（比如位元幣合法記賬區塊6次確認才能大概率正式成為主鏈上的區塊）。
實際中，一些業務場景需要達到強一致性，比如在商品消費場景中，一筆支付完成后馬上完成商品交割，這一筆支付后面不可能被推翻。為實作這種業務場景，可以采用更小規模的區塊鏈的方式，即是聯盟鏈的方式來進行。
聯盟鏈的業務場景中，大部分節點都是機構節點，數量有限，PBFT（Practical Byzantine Fault Tolerance）演算法可以很好的運用在聯盟鏈的場景中。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/43558.html
標籤：區塊鏈技術
上一篇：【視頻NO.50】齊愛民：東盟區塊鏈產業園投資將達百億
下一篇：區塊鏈需要掌握什么技術