從分布式一致性演算法到區塊鏈共識演算法（一）
本文主要參考書籍：區塊鏈原理、設計與應用第二版
一致性問題
一致性問題是分布式領域最為基礎也是最重要的問題， 如果分布式系統能實作“一致”， 對外就可以呈現為一個完美的、可擴展的“虛擬節點”，相對物理節點具備更優越性能和穩 定性 ， 這也是分布式系統希望能實作的最終目標，
一致性要求
- 可終止性（ termination ）：一致的結果在有限時間內能完成；
- 約同性（ agreement）：不同節點最終完成決策的結果是相同的；
- 合法性（ validity）：決策的結果必須是某個節點提出的提案 ，
帶約束的一致性
要實作絕對理想的嚴格一致性（ strict consistency）代價很大 ， 除非系統不發生任何故障，而且所有節點之間的通信無需任何時間，這個時候整個系統其實就等價于一臺機器了 ，
實際上，越強的一致性要求往往會造成越弱的處理性能，以及越差的可擴展性 ，一般來講，強一致性（ strong consistency）主要包括下面兩類：
- 順序一致性（ sequential consistency) : Leslie Lamport 在 1979 年的經典論文 《 How toMake a Multiprocessor Computer That Correctly Executes
Multiprocess Programs 》 中提出，是一種比較強的約束，保證所有行程看到的全域執行順序（ total order ）
一致，并且每個行程看自身的執行順序（ local order）跟實際發生順序一致， 例如，某行程第 4 重分布式系統核心問題 令 37先執行
A ，后執行 B ，則實際得到的全域結果中就應該為 A 在 B 前面，而不能反過來 ， 同時所有其他行程在全域上也應該看到這個順序 ，
順序一致性實際上限制了各行程內指令的偏序關系，但不在行程間按照物理時間進行全域排序；- 線性一致性（ linearizability consistency) : Maurice P. Herlihy 與 Jeannette M. Wing 在1990 年的經典論文 《 Linearizability: A Correctness
Condition for Concurrent Objects
中共同提出，在順序一致性前提下加強了行程間的操作排序，形成唯一的全域順序（系統等價于是順序執行，所有行程看到的所有操作的序列順序都一致，并且跟實際發生順序一致），是很強的原子性保證，
但是比較難實作，目前基本上要么依賴于全 局的時鐘或鎖，要么通過一些復雜演算法實作，性能往往不高 ，由于強一致性的系統往往比較難實作，而且很多時候，實際需求并沒有那么嚴格需要 強一致性 ， 因此，可以適當地放寬對一致性的要求，從而降低系統實作的難度 ， 例如在一定約束下實作所謂最終一致性（ eventual
consistency），即總會存在一個時刻（而不是立刻），讓系統達到一致的狀態 ， 大部分 Web 系統實作的都是最終一致性 ，
相對強一致性，這一類在某些方面榷訓的一致性都籠統稱為弱一致性（weak consistency ） ，FLP不可能定理
定義
FLP 不可能原理： 在網路可靠，但允許節點失效（即便只有一個）的最小化異步模型 系統中，不存在一個可以解決一致性問題的確定性共識演算法（ No completely asynchronous consensus
protocol can tolerate even a single unannounced process death ） ，FLP 不可能原理實際上告訴人們，不要浪費時間，去為異步分布式系統設計在任意場 景下都能實作共識的演算法，
正確理解
FLP不可能定理的最大適用前提是異步網路模型，何為同步、異步模型呢？
- 所謂異步模型，是說從一個節點到另一個節點的訊息延遲是有限的，但可能是無界的（finite but can be unbounded），這就意味著如果一個節點沒有收到訊息，它無法判斷訊息到底是丟失了，還是只是延遲了，也就是說，我們無法通過超時時間來判斷某個節點是否故障，
- 所謂同步模型，是說訊息傳遞的延遲是有限的，且是有界的，這就意味著我們可以通過經驗或采樣精確估算訊息的最大可能延遲，從而可以通過超時時間來確定訊息是否丟失、節點是否故障，
綜上所述，在分布式系統中，同步和異步這兩個術語存在特殊的含義 ， 同步是指系統中的各個節點的時鐘誤差存在上限；并且訊息傳遞必須在一定時間
內完成， 否則認為失敗 ；同時各個節點完成處理訊息的時間是一定的 ， 對于同步系統，可以很容易地判斷訊息是否丟失 ，
異步是指系統中各個節點可能存在較大的時鐘差異，同時訊息傳輸時間是任意長的，各節點對訊息進行處理的時間也可能是任意長的，這就造成無法判斷某個訊息遲遲沒有被回應是哪里出了問題（節點故障還是傳輸故障？）
，如何規避“FLP不可能定理”
研究者們通過調整問題模型來規避“FLP 不可能定理”從而尋找工程上可行的共識演算法, 比如位元幣系統中通過假定網路為弱同步性, 即網路節點間可以快速同步,以及礦工在一個區塊上投入有限的時間等來規避“FLP
不可能定理”，通過調整問題模型規避“FLP 不可能定理”, 使得共識演算法存在“工程解”，CAP定理
定義
分布式系統無法同時滿足一致性 (Consistency)、可用性(Availability)和磁區容忍性(Partition Tolerance), 最多只能同時滿足其中兩個特性, 如下圖所示，
- 一致性是指分布式系統中所有節點在同一時刻持有同樣的資料資訊，而且任何操作應該都是原子的，發生在后面的事件能看到前面事件發生導致的結果，注意這里指的是強一致性；
- 可用性是指系統處于服務狀態, 當客戶端發出請求, 服務端能在有效的時間內回傳結果；
- 磁區容忍性是指允許網路中部分節點不與其他節點通信,即允許網路發生磁區(不同區域之間的節點不能建立通信)，
應用場景
- 榷訓一致性
對結果一致性不敏感的應用，可以允許在新版本上線后過一段時間才最終更新成功， 期間不保證一致性 ， 例如網站靜態頁面內容 、 實時性較弱的查詢類資料庫等，簡單分布式同步協議如 Gossip ，以及 CouchDB 、 Cassandra 資料庫等，都是為此設計的 ，- 榷訓可用性
對結果 一 致性很敏感的應用，例如銀行取款機，當系統故障時候會拒絕服務 ， MongoDB 、 Redis 、MapReduce 等是為此設計的 ， Paxos 、 Raft 等共識演算法，主要處理這種情況 ，在 Paxos
類演算法中，可能存在著無法提供可用結果的情形，同時允許少數節點離線 ，- 榷訓磁區容忍性
現實中，網路磁區出現概率較小，但較難完全避免， 兩階段的提交演算法，某些關系型 資料庫及 ZooKeeper 主要考慮了這種設計， 實踐中，網路可以通過雙通道等機制增強可靠性，達到高穩定的網路通信，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/278134.html
標籤：區塊鏈
上一篇：對稱加密和非對稱加密