1. 一致性概念
分布式系統(tǒng)通常由異步網(wǎng)絡(luò)連接的多個節(jié)點(diǎn)構(gòu)成，每個節(jié)點(diǎn)有獨(dú)立的計(jì)算和存儲，節(jié)點(diǎn)之間通過網(wǎng)絡(luò)通信進(jìn)行協(xié)作。分布式一致性指多個節(jié)點(diǎn)對某一變量的取值達(dá)成一致，一旦達(dá)成一致，則變量的本次取值即被確定[12]。
在分布式存儲系統(tǒng)中，通常以多副本冗余的方式實(shí)現(xiàn)數(shù)據(jù)的可靠存儲。同一份數(shù)據(jù)的多個副本必須保證一致，而數(shù)據(jù)的多個副本又存儲在不同的節(jié)點(diǎn)中，這里的分布式一致性問題就是存儲在不同節(jié)點(diǎn)中的數(shù)據(jù)副本（或稱為變量）的取值必須一致。不僅如此，因?yàn)樽兞渴强勺兊?，變量會有多次取值，變量的多次取值?gòu)成一個序列，分布式一致性還要求多個節(jié)點(diǎn)對該變量的取值序列必須一致。
在大量客戶端并發(fā)請求讀/寫的情況下，維護(hù)數(shù)據(jù)多副本的一致性無疑非常重要，且富有挑戰(zhàn)。作為分布式一致性系列文章的第一篇，本文主要介紹相關(guān)基礎(chǔ)理論，后續(xù)篇章將重點(diǎn)介紹Paxos、Raft、ZAB等有著廣泛應(yīng)用的一致性協(xié)議。
2. 時(shí)間、事件和順序
一致性問題隱含了一個非常重要的要素：時(shí)間。比如多副本一致性在考慮時(shí)間要素后可描述為：在某一個時(shí)間點(diǎn)，多個節(jié)點(diǎn)上看到的數(shù)據(jù)副本其取值必須達(dá)成一致。數(shù)據(jù)取值（或稱為變量取值）通常由某個事件（如客戶端的寫請求）先行觸發(fā)，之后因節(jié)點(diǎn)之間消息延時(shí)之長短差異，先后將數(shù)據(jù)取值依次更新到分布式系統(tǒng)中的多個節(jié)點(diǎn)。
分布式系統(tǒng)中時(shí)間、事件、順序等概念在Leslie Lamport于1978年發(fā)表的論文“Time Clocks and the Ordering of Events in a Distributed System”中有系統(tǒng)性論述。Lamport自述其靈感源于以狹義相對論的角度從事物本質(zhì)上去理解分布式系統(tǒng)中使用消息時(shí)間戳來表述事件的全序關(guān)系。狹義相對論告訴我們時(shí)空中的事件不存在一個始終如一的全序關(guān)系，事件之間的先后關(guān)系完全取決于事件間的因果關(guān)系（即事件2是由事件1引起的），希望通過時(shí)間戳來描述事件的全序關(guān)系本質(zhì)上與事件間因果關(guān)系是一致的。文中，Lamport提出了邏輯時(shí)鐘（logical clock）的概念，并給出定義事件全序關(guān)系的算法，Lamport聲稱基于這樣的算法可以實(shí)現(xiàn)任意的分布式系統(tǒng)。
??? 分布式系統(tǒng)中，事件之間的順序至關(guān)重要。舉例說，假設(shè)分布式存儲系統(tǒng)由三個節(jié)點(diǎn)s1、s2和s3構(gòu)成，現(xiàn)有兩個客戶端c1和c2，客戶端c1首先發(fā)起寫請求x=v1希望將變量x的值從v0更新為v1，緊接著c2發(fā)起請求讀取變量x的值。變量x在節(jié)點(diǎn)s1、s2、s3上都有副本，c2可能從任意節(jié)點(diǎn)讀取x的值。考慮到網(wǎng)絡(luò)延時(shí)的影響，c2的讀請求消息可能先于c1的寫請求到達(dá)節(jié)點(diǎn)s3，如果沒有全局的順序控制，c2就有可能讀到變量x的舊值，這顯然是不希望看到的。
3. 基礎(chǔ)理論
ACID、CAP和BASE等理論是探討分布式環(huán)境下一致性相關(guān)問題的基礎(chǔ)。
3.1 ACID
ACID是數(shù)據(jù)庫（DBMS）事務(wù)正確執(zhí)行所必須滿足的四個特性的首字母縮寫。
Atomicity（原子性）：一個事務(wù)的所有操作，要么全部完成，要么全部不完成。所謂事務(wù)，是指由一系列數(shù)據(jù)操作所組成的完整邏輯過程。比如銀行轉(zhuǎn)賬事務(wù)由兩個操作組成：從源賬戶扣除金額，以及向目標(biāo)賬戶增加金額。
Consistency（一致性）：指事務(wù)開始之前和事務(wù)結(jié)束之后，數(shù)據(jù)的完整性約束沒有被破壞。包含兩層含義：a)數(shù)據(jù)庫機(jī)制層面，事務(wù)執(zhí)行前后，數(shù)據(jù)能符合設(shè)置的約束，如唯一約束、外鍵約束；b)業(yè)務(wù)層面，由應(yīng)用開發(fā)人員保證業(yè)務(wù)一致性。還是以銀行轉(zhuǎn)賬為例，A、B兩個賬號，轉(zhuǎn)賬之前和之后，A、B兩個賬號余額總額必須一致。
Isolation（隔離性）：數(shù)據(jù)庫能夠防止由于多個并發(fā)事務(wù)交叉執(zhí)行而導(dǎo)致數(shù)據(jù)的不一致。
Durability（持久性）：指事務(wù)結(jié)束后，對數(shù)據(jù)的修改是永久的，不會回滾到之前的狀態(tài)。
3.2 BASE
Eric Brewer和他在Inktomi公司的同事于1988年提出BASE設(shè)計(jì)理念，其初衷是為了抓住當(dāng)時(shí)逐漸出現(xiàn)的一些針對高可用性的設(shè)計(jì)思路。BASE縮寫定義如下：
●? BasicallyAvailable：基本可用
●? Soft State：軟狀態(tài)
●? Eventual consistent：最終一致性
其中Soft State和Eventual
consistent兩種策略主要用于解決網(wǎng)絡(luò)分區(qū)引起的問題，從而提高系統(tǒng)可用性。Soft State是服務(wù)端狀態(tài)設(shè)計(jì)的一種策略，介于stateful和stateless之間，服務(wù)端無狀態(tài)（stateless）設(shè)計(jì)可簡化網(wǎng)絡(luò)通信正常之后的分區(qū)恢復(fù)過程，更多描述可參考REST[8]。對Eventually consistent的理解可參考3.5小節(jié)。
Brewer在2000年P(guān)ODC（Principles Of Distributed Computing）大會所做“Towards Robust Distributed Systems”主題演講，其中就有BASE和ACID做了比較，如下：
BASE和ACID代表兩種截然相反的設(shè)計(jì)理念，ACID注重一致性，是傳統(tǒng)關(guān)系型數(shù)據(jù)庫的設(shè)計(jì)思路，BASE關(guān)注高可用性。當(dāng)今大規(guī)模、跨數(shù)據(jù)中心的分布式系統(tǒng)（如云計(jì)算）大多同時(shí)采用這兩種設(shè)計(jì)理念，并在兩者之間尋求平衡。
3.3 CAP
3.3.1 CAP基本概念
BASE理念在提出之初還不怎么被人們接受，主要是大家看到ACID的優(yōu)點(diǎn)而不愿意放棄。為了證明有必要開闊設(shè)計(jì)思路，Brewer于1998年秋季提出更為系統(tǒng)的CAP理論，次年正式發(fā)表[6]，并于2000年在PODC大會上做主題演講[7]。
CAP理論主張基于網(wǎng)絡(luò)的數(shù)據(jù)共享系統(tǒng)，都最多只能擁有以下三條中的兩條：
●? Consistency：指數(shù)據(jù)一致性，也就是開篇第1節(jié)所討論的分布式一致性概念。Brewer對Consistency的描述為“等同于所有節(jié)點(diǎn)訪問同一份最新的數(shù)據(jù)副本”
●? Available：對數(shù)據(jù)更新具備高可用性
●? Partitions tolerance：指容忍網(wǎng)絡(luò)分區(qū)
CAP“三選二”模式指AP、CP和AC。假設(shè)在分區(qū)模式下，有兩個節(jié)點(diǎn)分別位于分區(qū)兩側(cè)，如果為了可用性就必須允許其中一個節(jié)點(diǎn)更新數(shù)據(jù)，然而因?yàn)榫W(wǎng)絡(luò)分區(qū)兩個節(jié)點(diǎn)無法通信，所以會導(dǎo)致兩個節(jié)點(diǎn)數(shù)據(jù)不一致，即無法做到C(Consistency)；而為了保證數(shù)據(jù)一致性，只能將分區(qū)一側(cè)的節(jié)點(diǎn)設(shè)置為不可用，則又無法做到A(Available)。只有兩個節(jié)點(diǎn)能夠通信，才能同時(shí)保證Available和Consistency，這又違背了分區(qū)容忍P(Partitions tolerance)的特性。
3.3.2 CAP設(shè)計(jì)參考
在分布式環(huán)境中，容忍網(wǎng)絡(luò)分區(qū)被認(rèn)為是分布式系統(tǒng)必須滿足的特性，然而如果認(rèn)為要保證P以致于A、C只能二選一，那其實(shí)是對CAP理論的誤解。Brewer本人更是于十二年后發(fā)文[9]闡述，認(rèn)為應(yīng)該正確看待網(wǎng)絡(luò)分區(qū)并進(jìn)行策略性處理。
首先，因?yàn)榫W(wǎng)絡(luò)分區(qū)發(fā)生概率很小，那么在系統(tǒng)不存在分區(qū)的情況下，應(yīng)同時(shí)保證A和C；其次，因?yàn)榇嬖诜謪^(qū)的可能，所以應(yīng)主動探測分區(qū)發(fā)生并進(jìn)入分區(qū)模式；最后，在通信恢復(fù)后啟動分區(qū)恢復(fù)過程。圖3是從分區(qū)探測到分區(qū)模式再到分區(qū)恢復(fù)全過程的簡單示意。
顯然分區(qū)是問題根源，CAP理論對分布式系統(tǒng)設(shè)計(jì)的主要價(jià)值也在于指導(dǎo)如何分析并解決分區(qū)以及分區(qū)引起的相關(guān)問題，具體包括以下三方面內(nèi)容：
●? 如何探測到分區(qū)
●? 在分區(qū)模式下，允許或限制哪些操作，跟蹤或記錄哪些信息用于分區(qū)恢復(fù)
●? 分區(qū)恢復(fù)過程如何使分區(qū)兩側(cè)最終實(shí)現(xiàn)一致性
分區(qū)探測
網(wǎng)絡(luò)分區(qū)導(dǎo)致兩側(cè)節(jié)點(diǎn)無法正常通信，表現(xiàn)為一側(cè)節(jié)點(diǎn)發(fā)出的請求遲遲沒有收到另一側(cè)節(jié)點(diǎn)的回復(fù)，或者超出預(yù)定的時(shí)間仍未收到對方的消息(如心跳檢測)，此類現(xiàn)象本質(zhì)上是由延時(shí)(網(wǎng)絡(luò)超時(shí))引起，類似的原因還有程序異常、節(jié)點(diǎn)宕機(jī)等等。
所以分區(qū)探測核心是處理響應(yīng)時(shí)間的策略，設(shè)定合理時(shí)限，一旦響應(yīng)時(shí)間超過時(shí)限，即進(jìn)入分區(qū)模式。時(shí)限越短，進(jìn)入分區(qū)模式越頻繁，相應(yīng)地分區(qū)恢復(fù)也會頻繁執(zhí)行，而時(shí)限越長則可能會影響用戶體驗(yàn)。
?分區(qū)模式
分區(qū)模式設(shè)計(jì)要點(diǎn)主要有以下兩點(diǎn)：
●?基于“不變性約束”決定限制、推遲或允許哪些操作
●?跟蹤操作歷史用以數(shù)據(jù)一致性恢復(fù)
比如“表中鍵的唯一性”就是一種不變性約束，由于重復(fù)鍵易于發(fā)現(xiàn)與合并，因此可以考慮在分區(qū)模式下放寬要求，允許有重復(fù)的鍵。又比如網(wǎng)中購場景的“信用卡扣費(fèi)”，因?yàn)榱鞒讨忻鞔_含有“訂單處理中”的狀態(tài)，所以可以將扣費(fèi)操作推遲到分區(qū)結(jié)束，即以用戶不易察覺的方式犧牲了可用性。
分區(qū)模式設(shè)計(jì)重點(diǎn)是列舉所有操作以及不變性約束，分析每一項(xiàng)操作和約束相沖突的地方，對于存在沖突的情況，決定是否限制、推遲或修改相應(yīng)的操作。
跟蹤操作歷史的目的是合并分區(qū)兩側(cè)的操作并用于恢復(fù)一致性，一種優(yōu)選方案是使用版本向量，向量的元素是[節(jié)點(diǎn)，邏輯時(shí)間]數(shù)值對，分別表示執(zhí)行數(shù)據(jù)更新操作的節(jié)點(diǎn)和最后更新的時(shí)間。
?分區(qū)恢復(fù)
一旦網(wǎng)絡(luò)通信恢復(fù)，分區(qū)模式結(jié)束，系統(tǒng)進(jìn)入分區(qū)恢復(fù)過程，有兩個關(guān)鍵問題需要解決：
●?分區(qū)兩側(cè)的狀態(tài)最終必須實(shí)現(xiàn)一致，即最終一致性(Eventually Consistency)
●?補(bǔ)償分區(qū)期間產(chǎn)生的錯誤
恢復(fù)狀態(tài)一致最簡單的辦法是回退到分區(qū)開始的狀態(tài)，以特定的方式推進(jìn)兩側(cè)的一系列操作，逐步合并更新，并在過程中一直保持一致的狀態(tài)。因?yàn)榭赡艽嬖谝恍┎荒茏詣雍喜⒌臎_突，因此系統(tǒng)設(shè)計(jì)可選擇在分區(qū)模式下限制部分操作，以便分區(qū)恢復(fù)的時(shí)候能夠自動合并狀態(tài)。
3.3.3 CAP vs?ACID
雖然CAP和ACID縮寫中都有C、和A，但是它們分別所代表的概念是不同的，CAP與ACID之間的對比主要有以下幾點(diǎn)：
1、? ACID中的A指原子性，CAP中的A指可用性，但二者并不沖突，沒有理由為了可用性而改變分區(qū)兩側(cè)的原子性，而原子操作實(shí)際上會簡化分區(qū)恢復(fù)過程。
2、? ACID中的C指的是事務(wù)不能破壞任何數(shù)據(jù)庫規(guī)則，比如鍵的唯一性。相比之下CAP中的C僅僅指數(shù)據(jù)的多個副本必須一致。顯然ACID的C包含的含義更廣，而CAP中的C只是其中一個子集。
3、? ACID中的I（隔離性）在分區(qū)期間只能在分區(qū)一側(cè)維持操作，理由是事務(wù)的可串行性（serializability）要求全局通信，而網(wǎng)絡(luò)分區(qū)時(shí)無法做到這點(diǎn)。
4、? ACID的D（持久性操作）在分區(qū)期間可在分區(qū)兩側(cè)各自 進(jìn)行，待分區(qū)結(jié)束，在分區(qū)恢復(fù)過程中，根據(jù)每個分區(qū)提供的持久化記錄進(jìn)行一致性恢復(fù)。
總之，分區(qū)期間，分區(qū)兩側(cè)盡可能滿足ACID特性將有助于分區(qū)恢復(fù)過程中的一致性恢復(fù)以及錯誤補(bǔ)償。
4. 一致性模型
嚴(yán)格意義上的一致性，是指某個數(shù)據(jù)被更新的“瞬間”，其它節(jié)點(diǎn)讀取到的就是更新過的值，或者說，任何在某個數(shù)據(jù)上的讀操作，都能返回對該數(shù)據(jù)的最近一次寫操作的結(jié)果，然而這樣嚴(yán)格一致性（Strict Consistency）并不存在。從數(shù)據(jù)被更新后，到更新后的數(shù)值能夠被正確讀取到，這中間存在一個時(shí)間片段，在這個時(shí)間段內(nèi)，數(shù)據(jù)的一致性不能保證。換句話說，所謂的一致性都是有附加條件的，而一致性模型主要討論在滿足什么樣的條件下即可認(rèn)為達(dá)到一致性。不同的應(yīng)用場景對一致性要求不一樣，因此也就有了不同的一致性模型。下面介紹常見的一致性模型，雖然這些一致性模型大多在上世紀(jì)基于multi-processor或shared memory等應(yīng)用場景進(jìn)行討論，但本質(zhì)上都屬于一種廣義上的分布式系統(tǒng)，仍然能夠指導(dǎo)和約束今天的分布式系統(tǒng)設(shè)計(jì)。
4.1Sequential Consistency順序一致性
Lamport于1979年在論文How to Make a Multiprocessor Computer That Correctly Executes
Multiprocess Programs [1]中提出Sequential
Consistency。Lamport給出的定義是：
”…theresult of any execution is the same as ifthe
operations of all the processorswere executedin some sequential order, and the operations of each individualprocessor appear in this sequence in the order specified by its program.”
定義較為抽象，先舉個例子。假設(shè)兩個processor（p1和p2），有兩個初始值都為0的全局共享變量x、y。p1、p2程序指令分別為：
P1：{x=1；r1=y}
P2：{y=1；r2=x}
因?yàn)閮蓚€processor并行交錯執(zhí)行，所以程序可能會有如下執(zhí)行順序：
Execution1：{x=1;? r1=y;?y=1;? r2=x;}? 執(zhí)行結(jié)果：{r1==0;? r2==1}
Execution2：{ y=1;? r2=x;?x=1;? r1=y;}? 執(zhí)行結(jié)果：{r1==1;? r2==0}
Execution3：{x=1;? y=1;??r1=y;? r2=x;}? 執(zhí)行結(jié)果：{r1==1;? r2==1}
程序還可能會有其他執(zhí)行順序，但是不可能會有第四種執(zhí)行結(jié)果，這里我們以這三種執(zhí)行順序?yàn)槔?/p>
Sequential Consistency規(guī)定了兩點(diǎn)：
1)???????? 每個processor按照程序指定的順序（program order）執(zhí)行操作。（單個processor視角）
2)???????? Processor并行交錯的情況下，程序執(zhí)行順序可以任意，但所有processor看到的執(zhí)行順序必須一致，即所謂的順序一致性。（多processor構(gòu)成的程序全局視角）
第1)點(diǎn)說明process1中，x=1必須先于r1=y執(zhí)行。第2)點(diǎn)說明p1和p2看到的程序執(zhí)行順序必須是一樣的，如果p1看到的程序執(zhí)行順序是Execution1，那么p2看到的程序執(zhí)行順序也必須是Execution1，而不能是Execution2或Execution3。
再看圖4所示例子。P1、P2先后更新變量x的值，P3、P4讀取x的值。圖中(a)符合Sequential Consistency，而(b)則不符合Sequential Consistency，因?yàn)镻3、P4看到的程序順序不一致。
4.2 Linearizable Consistency線性一致性
Herlihy和Wing于1990年在論文“Linearizability: A correctness
condition for concurrent objects.”[3]中提出Linearizability。
Sequential Consistency僅定義了每個processor看到的程序執(zhí)行順序必須是一致的，并沒有限制在多processor并行交叉執(zhí)行的情況下，某個processor上某一操作必須在另外一processor的某個操作之前或之后，意即Sequential Consistency并不關(guān)心時(shí)間順序。Linearizability則關(guān)心時(shí)間順序，它在Sequential Consistency模型基礎(chǔ)上，為每個操作增加了時(shí)間戳，并定義：如果操作1的時(shí)間戳小于（意即早于）操作2的時(shí)間戳，那么操作1應(yīng)該在操作2之前完成。因此Linearizable
Consistency一致性要求強(qiáng)于Sequential Consistency。
圖1中(a)滿足Sequential Consistency但不滿足linearizability，因?yàn)閣rite(x=a)操作先于write(x=b)，而read操作卻先讀到x=b的值。
隊(duì)列的FIFO特性適用于解釋linearizability。即使多個進(jìn)程在同一隊(duì)列上進(jìn)行操作，也必須滿足隊(duì)列FIFO特性。E(x) A表示進(jìn)程A執(zhí)行元素x的入隊(duì)列操作，D(x) B表示進(jìn)程B執(zhí)行出隊(duì)列操作，得到元素x。圖5中(a)、(c)符合linearizability，(b)、(d)不符合linearizability，因?yàn)?b)、(d)中元素x早于y入隊(duì)列，而y卻先出隊(duì)列。
實(shí)現(xiàn)Linearizable Consistency模型需借助于全局時(shí)鐘，如Google Spanner利用原子鐘和GPS接收器，實(shí)現(xiàn)了較為精準(zhǔn)的全局時(shí)鐘，即TrueTime。
4.3?Causal Consistency因果一致性
Causal Consistency[4]要求對于有因果關(guān)系（causally related）的若干操作，在所有節(jié)點(diǎn)上看到的執(zhí)行順序都必須一致，而沒有因果關(guān)系的并行操作，在不同節(jié)點(diǎn)上可以看到不同的執(zhí)行順序。
以分布式數(shù)據(jù)讀寫操作為例解釋因果關(guān)系。假設(shè)一個事務(wù)由先讀后寫的兩個操作構(gòu)成，寫操作創(chuàng)建的值依賴于讀操作讀取到值，我們說該讀和寫操作具有因果關(guān)系。
圖6是因果一致性的例子，因?yàn)檫M(jìn)程P3上的讀操作R3(x)依賴于P2的寫操作W2(x)，進(jìn)程P4上的讀操作R4(x)依賴進(jìn)程P1的寫操作W1(x)，而P1和P2上的并行（沒有因果關(guān)系）寫操作W1(x)、W2(x)在進(jìn)程P3、P4上看到的順序是不一樣的。
圖7所示的場景則違反了因果一致性。圖中進(jìn)程P2讀操作R2(x)依賴進(jìn)程P1的寫操作W1(x)，即R2(x)、W1(x)具有因果關(guān)系，所有進(jìn)程上都應(yīng)該看到W1(x)先于R2(x)，同時(shí)根據(jù)進(jìn)程P2的Program order，R2(x)應(yīng)先于W2(x)，所以可以推導(dǎo)出W1(x)應(yīng)先于W2(x)，而實(shí)際上進(jìn)程P3卻不是這樣的順序。
4.4 PRAM Consistency
PRAM（Pipelined Random Access Memory）管道式存儲器，是Lipton和Sandberg于1988年在學(xué)術(shù)報(bào)告”
PRAM: A scalable shared memory”[5]中提出。如前所述，Sequential
Consistency要求所有進(jìn)程看到的程序執(zhí)行順序必須一致，而Causal Consistency降低了一致性要求，它要求有因果關(guān)系的操作在所有進(jìn)程上看到必須一致，而PRAM Consistency進(jìn)一步降低一致性要求。先看PRAM定義：
“…Writesdone by a single process are received by all other processes in the order inwhich they were issued, but writes from different processes may be seen in adifferent order by different processes.”
意即在PRAM中，不同進(jìn)程可以看到不同的程序執(zhí)行順序，但在某一進(jìn)程上的多個寫操作，在所有進(jìn)程上看到的順序必須一致，而不同進(jìn)程上的寫操作在不同進(jìn)程上看起來其執(zhí)行順序則可以不一致。
圖8所示場景中，進(jìn)程P1、P2分別可以看到如下執(zhí)行順序S1、S2：
S1 = w1(x)0; w2(x)1; r1(x)1
S2 = w2(x)1; w1(x)0; r2(x)0
因?yàn)閷懖僮鱳1(x)、w2(x)分別在進(jìn)程P1、P2中，它們在S1、S2中可以有不同的順序，因此圖5所示場景符合PRAM一致性。
5. 失效模型
???????探討分布式一致性算法通常需要先明確分布式環(huán)境的失效模型，這里我們先介紹常見的失效模型。
5.1?fault、error和failure
討論失效模型之前，先區(qū)分fault、error、failure三者含義的不同：
●?fault：導(dǎo)致系統(tǒng)或功能失效的異常條件，可譯為“缺陷”
●?error：由fault造成系統(tǒng)處于錯誤狀態(tài)，是一種中間狀態(tài)，當(dāng)系統(tǒng)能夠修復(fù)，回到正確的狀態(tài)，則可以避免發(fā)生failure。Error通常譯為“錯誤”
●?failure：指系統(tǒng)的行為偏離其原先定義好的規(guī)格，意即跟預(yù)期輸出不符的異常行為，可譯為“失效”
三者之間的關(guān)系，通俗來講就是：缺陷（fault）發(fā)生了，會導(dǎo)致錯誤（error），錯誤有可能造成系統(tǒng)功能失效（failure）。
5.2 失效模型
在分布式系統(tǒng)中，進(jìn)程和網(wǎng)絡(luò)通信都有可能失效（failure），即它們可能偏離被認(rèn)為是正確或所期望的行為。失效模型（failure
modes）定義失效可能發(fā)生的方式，以便理解失效所產(chǎn)生的影響。
按照不同的標(biāo)準(zhǔn)，有不同的劃分失效類型的方法，這里按照Cristian、Hadzilacos和Toueg提供的分類方法[10,11]介紹幾種主要的失效模型。
●?Fail-stop failure（異常失效并停止服務(wù)）：即節(jié)點(diǎn)失效后立即停止接收和發(fā)送所有消息，故障不會恢復(fù)。節(jié)點(diǎn)失效狀態(tài)能夠被其它節(jié)點(diǎn)檢測到。
●?Crash failure（崩潰性失效）：屬于突然失效以至于無法提前發(fā)出一些通告性消息，導(dǎo)致其它節(jié)點(diǎn)無法檢測到自己已經(jīng)失效。電源掉電或操作系統(tǒng)死機(jī)都會導(dǎo)致崩潰性失效。
●?Omission failure（遺漏性失效）：是指節(jié)點(diǎn)不能執(zhí)行預(yù)期的動作。表現(xiàn)為對某些輸入請求沒有響應(yīng)，可能是因?yàn)槭詹坏秸埱?，也可能是處理請求之后在發(fā)送響應(yīng)時(shí)出錯。
●?Arbitrary failure（隨意性失效）：可形象的比喻為“不按常理失效”，一種隨機(jī)性失效，時(shí)而正常，時(shí)而異常，節(jié)點(diǎn)也可能不按程序邏輯執(zhí)行，錯誤難以定位，拜占庭失效（byzantine failure）就屬于這一類。
參考
[1] LAMPORT, L. Time, clocks,and the ordering of events in a distributed system. Communications of the ACM21, 7 (July 1978), 558–565.15
[2] Lamport, Leslie (Sep1979). "How to make a multiprocessor computer that correctly executes multi-process programs.". Computers, IEEE Transactions C–28 (9): 690–691.
[3] Herlihy, Maurice P.;Jeannette M. Wing (July 1990). ""Linearizability: A correctnesscondition for concurrent objects." ACM Transactions on ProgrammingLanguages and Systems". ACM Transactions on Programming Languages andSystems 12 (3): 463–492.
[4] Mustaque Ahamad , GilNeiger , James E. Burns , Prince Kohli , P.W. Hutto: "Causal emory: Definitions, Implementation and Programming". 1994.
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.3356
[5] Lipton, R.J.; J.S.Sandberg. (1988). PRAM: A scalable shared memory (Technical report). PrincetonUniversity. CS-TR-180-88.
[6] Armando Fox and EricBrewer, “Harvest, Yield and Scalable Tolerant Systems”, Proc. 7th Workshop HotTopics in Operating Systems (HotOS 99), IEEE CS, 1999, pg. 174-178.
[7] Eric Brewer (2000),"Towards Robust Distributed Systems"
[8] Fielding, Roy Thomas (2000). Architectural Styles and the Design of Network-based Software
Architectures (Ph.D.). University of California, Irvine.
[9] Eric Brewer, “CAP TwelveYears Later How the Rules Have Changed”,
https://www.infoq.com/articles/cap-twelve-years-later-how-the-rules-have-changed
[10] Cristian F.: “UnderstandingFault-Tolerant Distributed Systems”, Communications of the ACM, Vol.34, No.2,pp.56-78, Feb. 1991.
[11] Hadzilacos V. and Toueg S.:“Fault-Tolerant Broadcasts and Related Problems”, In Mullender S.(ed.),Distributed Systems, pp.97-145, Wokingham: Addison-Wesley, 2nd ed., 1993.
[12] https://raft.github.io/
