分布式系統與原理?一緻性問題是分布式領域最重要、最基礎的問題，今天小編就來說說關于分布式系統與原理?下面更多詳細答案一起來看看吧!

分布式系統與原理

無聊預警：本文又長又幹，又沒有圖

一緻性問題

一緻性問題是分布式領域最重要、最基礎的問題。

一緻性/Consistency,是說在有多個服務節點的情況下，執行一些列操作，在約定協議的保障下，使得他們對外的處理結果，能達到一定程度的協同。

規範的說，理想的分布式系統一緻性應該滿足：

• 可終止性（Termination）：一緻的結果在有限時間内能完成；
• 共識性（Consensus）：不同節點最終完成決策的結果應該相同；
• 合法性（Validity）：決策的結果必須是其它進程提出的提案。

第一點很容易理解

第二點看似容易，但是隐藏了一些潛在信息。算法考慮的是任意的情形，凡事一旦推廣到任意情形，就往往有一些驚人的結果。例如現在就剩一張票了，中關村和西單的電影院也分别剛确認過這張票的存在，然後兩個電影院同時來了一個顧客要買票，從各自“觀察”看來，自己的顧客都是第一個到的……怎麼能達成結果的共識呢？記住我們的唯一秘訣：核心在于需要把兩件事情進行排序，而且這個順序還得是大家都認可的。

第三點看似繞口，但是其實比較容易理解，即達成的結果必須是節點執行操作的結果。仍以賣票為例，如果兩個影院各自賣出去一千張，那麼達成的結果就是還剩八千張，決不能認為票售光了。

做過分布式系統的讀者應該能意識到，絕對理想的強一緻性（Strong Consistency）代價很大。除非不發生任何故障，所有節點之間的通信無需任何時間，這個時候其實就等價于一台機器了。實際上，越強的一緻性要求往往意味着越弱的性能。

一般的，強一緻性（Strong Consistency）主要包括下面兩類：

順序一緻性：限制了各進程内指令的偏序關系，但不在進程間按照物理時間進行全局排序

線性一緻性：在順序一緻性前提下加強了進程間的操作排序，形成唯一的全局順序

強一緻的系統往往比較難實現。很多時候，人們發現實際需求并沒有那麼強，可以适當放寬一緻性要求，降低系統實現的難度。例如在一定約束下實現所謂最終一緻性（Eventual Consistency），即總會存在一個時刻（而不是立刻），系統達到一緻的狀态，這對于大部分的 Web 系統來說已經足夠了。這一類弱化的一緻性，被籠統稱為弱一緻性（Weak Consistency）。

共識算法

實踐中，要保障系統滿足不同程度的一緻性，往往需要通過共識算法來達成。

共識算法解決的是分布式系統對某個提案（Proposal），大部分節點達成一緻意見的過程。

理論上，如果分布式系統中各個節點都能保證以十分強大的性能（瞬間響應、高吞吐）無故障的運行，則實現共識過程并不複雜，簡單通過多播過程投票即可。

很可惜的是，現實中這樣“完美”的系統并不存在，如響應請求往往存在時延、網絡會發生中斷、節點會發生故障、甚至存在惡意節點故意要破壞系統。

一般地，把故障（不響應）的情況稱為“非拜占庭錯誤”，惡意響應的情況稱為“拜占庭錯誤”（對應節點為拜占庭節點）。

常見算法

對于非拜占庭錯誤的情況，已經存在不少經典的算法，包括 Paxos（1990 年）、Raft（2014 年）及其變種等。這類容錯算法往往性能比較好，處理較快，容忍不超過一半的故障節點。

對于要能容忍拜占庭錯誤的情況，包括 PBFT（Practical Byzantine Fault Tolerance，1999 年）為代表的确定性系列算法、PoW（1997 年）為代表的概率算法等。确定性算法一旦達成共識就不可逆轉，即共識是最終結果；而概率類算法的共識結果則是臨時的，随着時間推移或某種強化，共識結果被推翻的概率越來越小，最終成為事實上結果。拜占庭類容錯算法往往性能較差，容忍不超過 1/3 的故障節點。

此外，XFT（Cross Fault Tolerance，2015 年）等最近提出的改進算法可以提供類似 CFT 的處理響應速度，并能在大多數節點正常工作時提供 BFT 保障。

Algorand 算法（2017 年）基于 PBFT 進行改進，通過引入可驗證随機函數解決了提案選擇的問題，理論上可以在容忍拜占庭錯誤的前提下實現更好的性能（1000 TPS）。

FLP不可能原理

FLP 不可能原理告訴我們，不要浪費時間，去試圖為異步分布式系統設計面向任意場景的共識算法。

異步：導緻我們無法判斷某個消息遲遲沒有被響應是哪裡出了問題（節點故障還是傳輸故障？）

學術研究，往往考慮地是數學和物理意義上理想化的情形，很多時候現實世界要穩定得多（感謝這個世界如此魯棒！）。例如，上面例子中描述的最壞情形，每次都發生的概率其實并沒有那麼大。工程實現上某次共識失敗，再嘗試幾次，很大可能就成功了。

科學告訴你什麼是不可能的；工程則告訴你，付出一些代價，可以把它變成可行。

這就是科學和工程不同的魅力。FLP 不可能原理告訴大家不必浪費時間去追求完美的共識方案，而要根據實際情況設計可行的工程方案。

那麼，退一步講，在付出一些代價的情況下，共識能做到多好？

回答這一問題的是另一個很出名的原理：CAP 原理。

CAP原理

該原理被認為是分布式系統領域的重要原理之一，深刻影響了分布式計算與系統設計的發展。

CAP 原理：分布式系統無法同時确保一緻性（Consistency）、可用性（Availability）和分區容忍性（Partition），設計中往往需要弱化對某個特性的需求。

一緻性、可用性和分區容忍性的具體含義如下：

• 一緻性（Consistency）：任何事務應該都是原子的，所有副本上的狀态都是事務成功提交後的結果，并保持強一緻；
• 可用性（Availability）：系統（非失敗節點）能在有限時間内完成對操作請求的應答；
• 分區容忍性（Partition）：系統中的網絡可能發生分區故障（成為多個子網，甚至出現節點上線和下線），即節點之間的通信無法保障。而網絡故障不應該影響到系統正常服務。

CAP 原理認為，分布式系統最多隻能保證三項特性中的兩項特性。

比較直觀地理解，當網絡可能出現分區時候，系統是無法同時保證一緻性和可用性的。要麼，節點收到請求後因為沒有得到其它節點的确認而不應答（犧牲可用性），要麼節點隻能應答非一緻的結果（犧牲一緻性）。

由于大部分時候網絡被認為是可靠的，因此系統可以提供一緻可靠的服務；當網絡不可靠時，系統要麼犧牲掉一緻性（多數場景下），要麼犧牲掉可用性。

注意：網絡分區是可能存在的，出現分區情況後很可能會導緻發生“腦裂”現象。

關鍵就在于網絡，網絡大部分情況是可靠的，但也總是不可靠的。

所以，cap可以簡單理解為，因為網絡總會出故障，當網絡故障時，我們保一緻性，還是要可用性。

要可用性：例如網站靜态頁面内容、實時性較弱的查詢類數據庫等，簡單分布式同步協議如 Gossip，以及 CouchDB、Cassandra 數據庫等，都為此設計。

要一緻性：對結果一緻性很敏感的應用，例如銀行取款機，當系統故障時候會拒絕服務。MongoDB、Redis、MapReduce 等為此設計。Paxos、Raft 等共識算法，主要處理這種情況。在 Paxos 類算法中，可能存在着無法提供可用結果的情形，同時允許少數節點離線。

ACID 原則與多階段提交

ACID，即 Atomicity（原子性）、Consistency（一緻性）、Isolation（隔離性）、Durability（持久性）四種特性的縮寫。

ACID 原則描述了分布式數據庫需要滿足的一緻性需求，同時允許付出可用性的代價。

與 ACID 相對的一個原則是 eBay 技術專家 Dan Pritchett 提出的 BASE（Basic Availability，Soft-state，Eventual Consistency）原則。BASE 原則面向大型高可用分布式系統，主張犧牲掉對強一緻性的追求，而實現最終一緻性，來換取一定的可用性。

兩階段提交

對于分布式事務一緻性的研究成果包括著名的兩階段提交算法（Two-phase Commit，2PC）和三階段提交算法（Three-phase Commit，3PC）。

兩階段提交算法，其基本思想十分簡單，既然在分布式場景下，直接提交事務可能出現各種故障和沖突，那麼可将其分解為預提交和正式提交兩個階段，規避沖突的風險。

• 預提交：協調者（Coordinator）發起提交某個事務的申請，各參與執行者（Participant）需要嘗試進行提交并反饋是否能完成；
• 正式提交：協調者如果得到所有執行者的成功答複，則發出正式提交請求。如果成功完成，則算法執行成功。

在此過程中任何步驟出現問題（例如預提交階段有執行者回複預計無法完成提交），則需要回退。

兩階段提交算法因為其簡單容易實現的優點，在關系型數據庫等系統中被廣泛應用。當然，其缺點也很明顯。整個過程需要同步阻塞導緻性能一般較差；同時存在單點問題，較壞情況下可能一直無法完成提交；另外可能産生數據不一緻的情況（例如協調者和執行者在第二個階段出現故障）。

三階段提交

三階段提交針對兩階段提交算法第一階段中可能阻塞部分執行者的情況進行了優化。具體來說，将預提交階段進一步拆成兩個步驟：嘗試預提交和預提交。

完整過程如下：

• 嘗試預提交：協調者詢問執行者是否能進行某個事務的提交。執行者需要返回答複，但無需執行提交。這就避免出現部分執行者被無效阻塞住的情況。
• 預提交：協調者檢查收集到的答複，如果全部為真，則發起提交事務請求。各參與執行者（Participant）需要嘗試進行提交并反饋是否能完成；
• 正式提交：協調者如果得到所有執行者的成功答複，則發出正式提交請求。如果成功完成，則算法執行成功。

其實，無論兩階段還是三階段提交，都隻是一定程度上緩解了提交沖突的問題，并無法一定保證系統的一緻性。首個有效的算法是後來提出的 Paxos 算法。

Paxos 算法

Paxos 問題是指分布式的系統中存在故障（crash fault），但不存在惡意（corrupt）節點的場景（即可能消息丢失或重複，但無錯誤消息）下的共識達成問題。這也是分布式共識領域最為常見的問題。

Paxos 是首個得到證明并被廣泛應用的共識算法，其原理類似 兩階段提交 算法，進行了泛化和擴展，通過消息傳遞來逐步消除系統中的不确定狀态。zookeeper中有使用。

作為後來很多共識算法（如 Raft、ZAB 等）的基礎，Paxos 算法基本思想并不複雜。

基本原理

算法中存在三種邏輯角色的節點，在實現中同一節點可以擔任多個角色。

• 提案者（Proposer）：提出一個提案，等待大家批準（Chosen）為結案（Value）。系統中提案都擁有一個自增的唯一提案号。往往由客戶端擔任該角色。（隻有是被提案者提出的提案才可能被最終批準）
• 接受者（Acceptor）：負責對提案進行投票，接受（Accept）提案。往往由服務端擔任該角色。
• 學習者（Learner）：獲取批準結果，并幫忙傳播，不參與投票過程。可為客戶端或服務端。

基本思路類似兩階段提交：

多個提案者先要争取到提案的權利（得到大多數接受者的支持）；

成功的提案者發送提案給所有人進行确認，得到大部分人确認的提案成為批準的結案。

Raft 算法

Paxos 算法雖然給出了共識設計，但并沒有讨論太多實現細節，也并不重視工程上的優化，因此後來在學術界和工程界出現了一些改進工作，包括 Fast Paxos、Multi-Paxos，Zookeeper Atomic Broadcast（ZAB）和 Raft 等。這些算法重點在于改進執行效率和可實現性。

Raft 算法的主要設計思想與 ZAB 類似，通過先選出領導節點來簡化流程和提高效率。實現上分解了領導者選舉、日志複制和安全方面的考慮，并通過約束減少了不确定性的狀态空間。

算法包括三種角色：領導者（Leader）、候選者（Candidate） 和跟随者（Follower），每個任期内選舉一個全局的領導者。領導者角色十分關鍵，決定日志（log）的提交。每個日志都會路由到領導者，并且隻能由領導者向跟随者單向複制。

典型的過程包括兩個主要階段：

• 領導者選舉：開始所有節點都是跟随者，在随機超時發生後未收到來自領導者或候選者消息，則轉變角色為候選者（中間狀态），提出選舉請求。最近選舉階段（Term）中得票超過一半者被選為領導者；如果未選出，随機超時後進入新的階段重試。領導者負責從客戶端接收請求，并分發到其他節點；
• 同步日志：領導者會決定系統中最新的日志記錄，并強制所有的跟随者來刷新到這個記錄，數據的同步是單向的，确保所有節點看到的視圖一緻。

此外，領導者會定期向所有跟随者發送心跳消息，跟随者如果發現心跳消息超時未收到，則可以認為領導者已經下線，嘗試發起新的選舉過程。

拜占庭問題

拜占庭是古代東羅馬帝國的首都，由于地域寬廣，假設其守衛邊境的多個将軍（系統中的多個節點）需要通過信使來傳遞消息，達成某些一緻決定。但由于将軍中可能存在叛徒（系統中節點出錯），這些叛徒将向不同的将軍發送不同的消息，試圖幹擾共識的達成。

拜占庭問題即讨論在此情況下，如何讓忠誠的将軍們能達成行動的一緻。

在大多數的分布式系統中，拜占庭的場景并不多見。然而在特定場景下存在意義，例如允許匿名參與的系統（如比特币），或是出現欺詐可能造成巨大損失的情況。

根據 FLP 不可能原理，這個問題無通用解。

拜占庭問題之所以難解，在于任何時候系統中都可能存在多個提案（因為提案成本很低），并且在大規模場景下要完成最終确認的過程容易受幹擾，難以達成共識。

比特币網絡在設計時使用了 PoW（Proof of Work）的概率型算法思路，從如下兩個角度解決大規模場景下的拜占庭容錯問題。

首先，限制一段時間内整個網絡中出現提案的個數（通過工作量證明來增加提案成本）；其次是丢掉最終确認的約數，約定好始終沿着已知最長的鍊進行拓展。共識的最終确認是概率意義上的存在。這樣，即便有人試圖惡意破壞，也會付出相應的經濟代價（超過整體系統一半的工作量）。

後來的各種 PoX 系列算法，也都是沿着這個思路進行改進，采用經濟博弈來制約攻擊者。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!