分布式系统设计模式（荣耀典藏版）
?
?
目錄
前言
一、前置知識點
1、分類
2、特征
3、優(yōu)缺點
3.1優(yōu)點
3.2、缺點
4、應(yīng)用
4.1、并行
4.2、容錯應(yīng)用
4.3、固有的應(yīng)用
5、與計算機網(wǎng)絡(luò)異同
6、系統(tǒng)設(shè)計難點
二、分布式系統(tǒng)重要組成技術(shù)
1、布隆過濾器
2、一致性哈希
3、Quorum
4、領(lǐng)導(dǎo)者（Leader）和追隨者（Follower）
5、心跳
6、Fencing
7、WAL（預(yù)寫日志W(wǎng)rite-ahead Log）
8、分段日志
9、高水位線（High-Water mark）
10、租約（Lease）
11、Gossip協(xié)議
12、Phi 累計故障檢測（Phi Accrual Failure Detection）
13、腦裂
14、校驗和（checksum）
15、CAP定理
16、PACELEC定理
17、提示交接（Hinted Handoff）
18、讀取時修復(fù)
19、默克爾樹（Merkle Trees）
前言
? ? ? ? 1.什么是分布式系統(tǒng)？
????????在一個分布式系統(tǒng)中，一組獨立的計算機展現(xiàn)給用戶的是一個統(tǒng)一的整體，就好像是一個系統(tǒng)似的。系統(tǒng)擁有多種通用的物理和邏輯資源，可以動態(tài)的分配任務(wù)，分散的物理和邏輯資源通過計算機網(wǎng)絡(luò)實現(xiàn)信息交換。系統(tǒng)中存在一個以全局的方式管理計算機資源的分布式操作系統(tǒng)。
在計算機網(wǎng)絡(luò)中，這種統(tǒng)一性、模型以及其中的軟件都不存在。用戶看到的是實際的機器，計算機網(wǎng)絡(luò)并沒有使這些機器看起來是統(tǒng)一的。如果這些機器有不同的硬件或者不同的操作系統(tǒng)，那么，這些差異對于用戶來說都是完全可見的。如果一個用戶希望在一臺遠程機器上運行一個程序，那么，他必須登陸到遠程機器上，然后在那臺機器上運行該程序。
分布式系統(tǒng)和計算機網(wǎng)絡(luò)系統(tǒng)的共同點是：多數(shù)分布式系統(tǒng)是建立在計算機網(wǎng)絡(luò)之上的，所以分布式系統(tǒng)與計算機網(wǎng)絡(luò)在物理結(jié)構(gòu)上是基本相同的。
他們的區(qū)別在于：分布式操作系統(tǒng)的設(shè)計思想和網(wǎng)絡(luò)操作系統(tǒng)是不同的，這決定了他們在結(jié)構(gòu)、工作方式和功能上也不同。網(wǎng)絡(luò)操作系統(tǒng)要求網(wǎng)絡(luò)用戶在使用網(wǎng)絡(luò)資源時首先必須了解網(wǎng)絡(luò)資源，網(wǎng)絡(luò)用戶必須知道網(wǎng)絡(luò)中各個計算機的功能與配置、軟件資源、網(wǎng)絡(luò)文件結(jié)構(gòu)等情況，在網(wǎng)絡(luò)中如果用戶要讀一個共享文件時，用戶必須知道這個文件放在哪一臺計算機的哪一個目錄下；分布式操作系統(tǒng)是以全局方式管理系統(tǒng)資源的，它可以為用戶任意調(diào)度網(wǎng)絡(luò)資源，并且調(diào)度過程是“透明”的。當(dāng)用戶提交一個作業(yè)時，分布式操作系統(tǒng)能夠根據(jù)需要在系統(tǒng)中選擇最合適的處理器，將用戶的作業(yè)提交到該處理程序，在處理器完成作業(yè)后，將結(jié)果傳給用戶。在這個過程中，用戶并不會意識到有多個處理器的存在，這個系統(tǒng)就像是一個處理器一樣。?
內(nèi)聚性是指每一個數(shù)據(jù)庫分布節(jié)點高度自治，有本地的數(shù)據(jù)庫管理系統(tǒng)。透明性是指每一個數(shù)據(jù)庫分布節(jié)點對用戶的應(yīng)用來說都是透明的，看不出是本地還是遠程。在分布式數(shù)據(jù)庫系統(tǒng)中，用戶感覺不到數(shù)據(jù)是分布的，即用戶不須知道關(guān)系是否分割、有無副本、數(shù)據(jù)存于哪個站點以及事務(wù)在哪個站點上執(zhí)行等。?
一、前置知識點
1、分類
分布式計算機系統(tǒng)的體系結(jié)構(gòu)可用處理機之間的耦合度為主要標志來加以描述。耦合度是系統(tǒng)模塊之間互聯(lián)的緊密程度，它是數(shù)據(jù)傳輸率、響應(yīng)時間、并行處理能力等性能指標的綜合反映，主要取決于所選用體系結(jié)構(gòu)的互聯(lián)拓撲結(jié)構(gòu)和通信鏈路的類型。?[2]?
按地理環(huán)境衡量耦合度，分布式系統(tǒng)可以分為機體內(nèi)系統(tǒng)、建筑物內(nèi)系統(tǒng)、建筑物間系統(tǒng)和不同地理范圍的區(qū)域系統(tǒng)等，它們的耦合度依次由高到低按應(yīng)用領(lǐng)域的性質(zhì)決定耦合度，可以分成三類：?[2]?
第一種是面向計算任務(wù)的分布并行計算機系統(tǒng)和分布式多用戶計算機系統(tǒng)，它們要求盡可能高的耦合度，以便發(fā)展成為能分擔(dān)大型計算機和分時計算機系統(tǒng)所完成的工作。?[2]?
第二種是面向管理信息的分布式數(shù)據(jù)處理系統(tǒng)。耦合度可以適當(dāng)降低。?[2]?
第三種是面向過程控制的分布式計算機控制系統(tǒng)。耦合度要求適中，當(dāng)然對于某些實時應(yīng)用，其耦合度的要求可能很高。?[2]?
2、特征
分布式系統(tǒng)是多個處理機通過通信線路互聯(lián)而構(gòu)成的松散耦合的系統(tǒng)。從系統(tǒng)中某臺處理機來看，其余的處理機和相應(yīng)的資源都是遠程的，只有它自己的資源才是本地的。至今，對分布式系統(tǒng)的定義尚未形成統(tǒng)一的見解。一般認為，分布式系統(tǒng)應(yīng)具有以下四個特征：?[3]?
(1)分布性。分布式系統(tǒng)由多臺計算機組成，它們在地域上是分散的，可以散布在一個單位、一個城市、一個國家，甚至全球范圍內(nèi)。整個系統(tǒng)的功能是分散在各個節(jié)點上實現(xiàn)的，因而分布式系統(tǒng)具有數(shù)據(jù)處理的分布性。?[3]?
(2)自治性。分布式系統(tǒng)中的各個節(jié)點都包含自己的處理機和內(nèi)存，各自具有獨立的處理數(shù)據(jù)的功能。通常，彼此在地位上是平等的，無主次之分，既能自治地進行工作，又能利用共享的通信線路來傳送信息，協(xié)調(diào)任務(wù)處理。?[3]?
(3)并行性。一個大的任務(wù)可以劃分為若干個子任務(wù)，分別在不同的主機上執(zhí)行。?[3]?
(4)全局性。分布式系統(tǒng)中必須存在一個單一的、全局的進程通信機制，使得任何一個進程都能與其他進程通信，并且不區(qū)分本地通信與遠程通信。同時，還應(yīng)當(dāng)有全局的保護機制。系統(tǒng)中所有機器上有統(tǒng)一的系統(tǒng)調(diào)用集合，它們必須適應(yīng)分布式的環(huán)境。在所有CPU上運行同樣的內(nèi)核，使協(xié)調(diào)工作更加容易。?[3]?
3、優(yōu)缺點
3.1優(yōu)點
(1)資源共享。若干不同的節(jié)點通過通信網(wǎng)絡(luò)彼此互聯(lián)，一個節(jié)點上的用戶可以使用其他節(jié)點上的資源，如分布式系統(tǒng)允許設(shè)備共享，使眾多用戶共享昂貴的外部設(shè)備，如彩色打印機；允許數(shù)據(jù)共享，使眾多用戶訪問共用的數(shù)據(jù)庫；可以共享遠程文件，使用遠程特有的硬件設(shè)備（如高速陣列處理器），以及執(zhí)行其他操作。?[3]?
(2)加快計算速度。如果一個特定的計算任務(wù)可以劃分為若干個并行運行的子任務(wù)，則可把這些子任務(wù)分散到不同的節(jié)點上，使它們同時在這些節(jié)點上運行，從而加快計算速度。另外，分布式系統(tǒng)具有計算遷移功能，如果某個節(jié)點上的負載太重，則可把其中一些作業(yè)移到其他節(jié)點去執(zhí)行，從而減輕該節(jié)點的負載。這種作業(yè)遷移稱為負載平衡。?[3]?
(3)可靠性高。分布式系統(tǒng)具有高可靠性。如果其中某個節(jié)點失效了，則其余的節(jié)點可以繼續(xù)操作，整個系統(tǒng)不會因為一個或少數(shù)幾個節(jié)點的故障而全體崩潰。因此，分布式系統(tǒng)有很好的容錯性能。?[3]?
系統(tǒng)必須能夠檢測節(jié)點的故障，采取適當(dāng)?shù)氖侄?#xff0c;使它從故障中恢復(fù)過來。系統(tǒng)確定故障所在的節(jié)點后，就不再利用它來提供服務(wù)，直至其恢復(fù)正常工作。如果失效節(jié)點的功能可由其他節(jié)點完成，則系統(tǒng)必須保證功能轉(zhuǎn)移的正確實施。當(dāng)失效節(jié)點被恢復(fù)或者修復(fù)時，系統(tǒng)必須把它平滑地集成到系統(tǒng)中。?[3]?
(4)通信方便、快捷。分布式系統(tǒng)中各個節(jié)點通過一個通信網(wǎng)絡(luò)互聯(lián)在一起。通信網(wǎng)絡(luò)由通信線路、調(diào)制解調(diào)器和通信處理器等組成，不同節(jié)點的用戶可以方便地交換信息。在低層，系統(tǒng)之間利用傳遞消息的方式進行通信，這類似于單CPU系統(tǒng)中的消息機制。單CPU系統(tǒng)中所有高層的消息傳遞功能都可以在分布式系統(tǒng)中實現(xiàn)，如文件傳遞、登錄、郵件、Web瀏覽和遠程過程調(diào)用( Remote Procedure call，RPC)。?[3]?
分布式系統(tǒng)實現(xiàn)了節(jié)點之間的遠距離通信，為人與人之間的信息交流提供了很大方便不同地區(qū)的用戶可以共同完成一個項目，通過傳送項目文件，遠程登錄進入對方系統(tǒng)來運行程序，如發(fā)送電子郵件等，協(xié)調(diào)彼此的工作。?[3]?
3.2、缺點
盡管分布式系統(tǒng)具備眾多優(yōu)勢，但它也有自身的缺點，主要是可用軟件不足，系統(tǒng)軟件、編程語言、應(yīng)用程序以及開發(fā)工具都相對很少。此外，還存在通信網(wǎng)絡(luò)飽和或信息丟失和網(wǎng)絡(luò)安全問題，方便的數(shù)據(jù)共享同時意味著機密數(shù)據(jù)容易被竊取。雖然分布式系統(tǒng)存在這些潛在的問題，但其優(yōu)點遠大于缺點，而且這些缺點也正得到克服。因此，分布式系統(tǒng)仍是人們研究、開發(fā)和應(yīng)用的方向。
4、應(yīng)用
分布式系統(tǒng)被用在許多不同類型的應(yīng)用中。以下列出了一些應(yīng)用。對這些應(yīng)用而言，使用分布式系統(tǒng)要比其他體系結(jié)構(gòu)如處理機和共享存儲器多處理機更優(yōu)越：
4.1、并行
原則上，并行應(yīng)用也可以在共享存儲器多處理機上運行，但共享存儲器系統(tǒng)不能很好地擴大規(guī)模以包括大量的處理機。HPCC（高性能計算和通信）應(yīng)用一般需要一個可伸縮的設(shè)計，這種設(shè)計取決于分布式處理。
4.2、容錯應(yīng)用
因為每個PE是自治的，所以分布式系統(tǒng)更加可靠。一個單元或資源（軟件或硬件）的故障不影響其他資源的正常功能。
4.3、固有的應(yīng)用
許多應(yīng)用是固有分布式的。這些應(yīng)用是突發(fā)模式（burstmode）而非批量模式（bulk mode）。這方面的實例有事務(wù)處理和Internet Javad，程序。
這些應(yīng)用的性能取決于吞吐量（事務(wù)響應(yīng)時間或每秒完成的事務(wù)數(shù)）而不是一般多處理機所用的執(zhí)行時間。
對于一組用戶而言， 分布式系統(tǒng)有一個特別的應(yīng)用稱為計算機支持的協(xié)同工作（Computer Supported Cooperative Working，CSCW）或群件（groupware）， 支持用戶協(xié)同工作。另一個應(yīng)用是分布式會議， 即通過物理的分布式網(wǎng)絡(luò)進行電子會議。同樣，多媒體遠程教學(xué)也是一個類似的應(yīng)用。?
為了達到互操作性，用戶需要一個標準的分布式計算環(huán)境，在這個環(huán)境里，所有系統(tǒng)和資源都可用。
DCE（分布式計算環(huán)境）是OSF（開放系統(tǒng)基金會）開發(fā)的分布式計算技術(shù)的工業(yè)標準集。它提供保護和控制對數(shù)據(jù)訪問的安全服務(wù)、容易尋找分布式資源的名字服務(wù)、以及高度可伸縮的模型用于組織極為分散的用戶、服務(wù)和數(shù)據(jù)。D C E可在所有主要的計算平臺上運行， 并設(shè)計成支持異型硬件和軟件環(huán)境下的分布式應(yīng)用。
DCE已經(jīng)被包括TRANSVARL在內(nèi)一些廠商實現(xiàn)。TRANSVARL是最早的多廠商組（multi vendor team）的成員之一，它提出的建議已成為DCE體系結(jié)構(gòu)的基礎(chǔ)。在中可以找到利用DCE開發(fā)分布式應(yīng)用的指南。?
一些其它標準基于一個特別的模型，比如CORBA（公用對象請求代理程序體系結(jié)構(gòu)），它是由OMG （對象管理組）和多計算機廠商聯(lián)盟開發(fā)的一個標準。CORBA使用面向?qū)ο竽Ｐ蛯崿F(xiàn)分布式系統(tǒng)中的透明服務(wù)請求。
工業(yè)界有自己的標準，比如微軟的分布式構(gòu)件對象模型（DCOM）和Sun Microsystem公司的Java Beans。?
5、與計算機網(wǎng)絡(luò)異同
分布式計算機系統(tǒng)與計算機網(wǎng)絡(luò)既有類似之處又有不同點，其主要的異同如下：
(1)在計算機網(wǎng)絡(luò)中，每個用戶或任務(wù)通常只使用一臺計算機，若要利用網(wǎng)絡(luò)中的另一臺計算機，則需要遠程注冊。在分布式計算機系統(tǒng)中，用戶進程在系統(tǒng)內(nèi)各個計算機上動態(tài)調(diào)度，并根據(jù)運行情況由分布式操作系統(tǒng)動態(tài)地、透明地將機器分配給用戶進程或任務(wù)。
(2)在計算機網(wǎng)絡(luò)中，用戶知道它們的文件存放在何處，并用顯示的文件傳輸命令在機器之間傳送文件。在分布式計算機系統(tǒng)中，文件的放置由操作系統(tǒng)管理，用戶可用相同方式訪問系統(tǒng)中的所有文件而不管它們位于何處。
(3)在計算機網(wǎng)絡(luò)中，各結(jié)點計算機均有自己的操作系統(tǒng)，資源歸局部所有并被局部控制，網(wǎng)絡(luò)內(nèi)的進程調(diào)度是通過進程遷移和數(shù)據(jù)遷移實現(xiàn)的。在分布式計算機系統(tǒng)中，每個場點上運行一個局部操作系統(tǒng)，執(zhí)行的任務(wù)可以是獨立的，可以是某任務(wù)的一個部分，也可以是其他場點上的(部分)任務(wù)，且各場點相互協(xié)同，合作平衡系統(tǒng)內(nèi)的負載。
(4)在計算機網(wǎng)絡(luò)中，系統(tǒng)幾乎無容錯能力。在分布式計算機系統(tǒng)中有系統(tǒng)自動重構(gòu)、適度降級使用及錯誤恢復(fù)功能。
(5)兩者透明性的程度和級別不同。
(6)就資源共享而言，計算機網(wǎng)絡(luò)和分布式計算機系統(tǒng)是類似的。
6、系統(tǒng)設(shè)計難點
雖然分布式系統(tǒng)具有很多優(yōu)點，然而由于分布式系統(tǒng)自身的特點及應(yīng)用環(huán)境的復(fù)雜性，分布式系統(tǒng)設(shè)計有如下的很多難題需要解決:?[6]?
1.部分失效問題
由于分布式系統(tǒng)通常由若干部分組成，各個部分由于各種原因可能發(fā)生故障，如硬件故障、軟件錯誤及錯誤操作等。如果一個分布式系統(tǒng)不對這些故障進行有效的處理，系統(tǒng)某一組成部分的故障可能導(dǎo)致整個系統(tǒng)的癱瘓。?[6]?
2.性能和可靠性過分依賴于網(wǎng)絡(luò)
由于分布式系統(tǒng)是建立在網(wǎng)絡(luò)之上的，而網(wǎng)絡(luò)本身是不可靠的，可能經(jīng)常發(fā)生故障，網(wǎng)絡(luò)故障可能導(dǎo)致系統(tǒng)服務(wù)的終止。另外，網(wǎng)絡(luò)超負荷會導(dǎo)致性能的降低，增加系統(tǒng)的響應(yīng)時間。?[6]?
3.缺乏統(tǒng)一控制
一個分布式系統(tǒng)的控制通常是一個典型的分散控制，沒有統(tǒng)一的中心控制。因此，分布式系統(tǒng)通常需要相應(yīng)的同步機制來協(xié)調(diào)系統(tǒng)中各個部分的工作。設(shè)計與實現(xiàn)一個對用戶來說是透明的且具有容錯能力的分布式系統(tǒng)是一項具有挑戰(zhàn)性的工作，而且所需的機制和策略尚未成熟。因此什么樣的程序設(shè)計模型、什么樣的控制機制最適合分布式系統(tǒng)仍是需要繼續(xù)研究的課題。?[6]?
4.難以合理設(shè)計資源分配策略
在集中式系統(tǒng)中，所有的資源都由操作系統(tǒng)管理和分配，但在分布式系統(tǒng)中，資源屬于各節(jié)點，所以調(diào)度的靈活性不如集中式系統(tǒng)，資源的物理分布可能與用戶請求的分布不匹配，某些資源可能空閑，而另一些資源可能超載。?
5.安全保密性問題
開放性使得分布式系統(tǒng)中的許多軟件接口都提供給用戶，這樣的開放式結(jié)構(gòu)對于開發(fā)人員非常有價值，但同時也為破壞者打開了方便之門。?
針對分布式系統(tǒng)存在的上述難點，要保證一個分布式系統(tǒng)的正常運行，就必須對系統(tǒng)資源進行有效的管理，對計算機之間的通信、故障、安全等問題提供有效的處理手段和支持機制。?[6]?
用戶對分布式系統(tǒng)的要求是透明性、安全性、靈活性、簡單性、可靠性，也要求方便在局部失效時重構(gòu)系統(tǒng)，以及集成不均勻子系統(tǒng)的能力。
資源的分布性、缺乏全局狀態(tài)信息及傳輸延遲，意味著集中式操作系統(tǒng)的某些方法和技術(shù)不能應(yīng)用于分布式系統(tǒng)中。即使集中式系統(tǒng)中的某些技術(shù)滿足上面的要求，其實現(xiàn)通常也是要付出很大代價的。
二、分布式系統(tǒng)重要組成技術(shù)
1、布隆過濾器
Bloom過濾器是一種節(jié)省空間的概率數(shù)據(jù)結(jié)構(gòu)，用于測試元素是否為某集合的成員。它用于我們只需要檢查元素是否屬于對象的場景。
?在BigTable（和Cassandra）中，任何讀取操作都必須從組成Tablet的SSTable中讀取。如果這些SSTable不在內(nèi)存中，則讀取操作可能最終會執(zhí)行許多磁盤訪問以便讀取所需的SSTable。為了減少磁盤訪問次數(shù)，BigTable 使用Bloom過濾器。
2、一致性哈希
一致的哈希允許您輕松擴展，從而允許以有效的方式復(fù)制數(shù)據(jù)，從而實現(xiàn)更好的可用性和容錯能力。
通過對數(shù)據(jù)項的鍵進行哈希處理以產(chǎn)生其在環(huán)上的位置，然后順時針遍歷環(huán)以查找位置大于該項位置的第一個節(jié)點，將每個由鍵標識的數(shù)據(jù)項分配給節(jié)點。與節(jié)點關(guān)聯(lián)的節(jié)點是數(shù)據(jù)項的位置。
?
一致散列的主要優(yōu)點是增量穩(wěn)定性；節(jié)點離開或到達集群僅影響其直接鄰居，其他節(jié)點不受影響。
3、Quorum
在分布式環(huán)境中，quorum是在確認操作成功之前需要成功執(zhí)行此分布式操作的最小服務(wù)器數(shù)。
?
Cassandra，為了確保數(shù)據(jù)一致性，每個寫入請求都可以配置為僅當(dāng)數(shù)據(jù)已寫入至少一個quorum（或大多數(shù)）副本節(jié)點時才成功。
對于領(lǐng)導(dǎo)者選舉，Chubby使用Paxos，它使用quorum來確保強大的一致性。
Dynamo 將寫入復(fù)制到系統(tǒng)中其他節(jié)點的草率quorum，而不是像Paxos那樣的嚴格多數(shù)quorum。所有讀/寫操作都在首選項列表中的第一個NN正常節(jié)點上執(zhí)行，該節(jié)點可能并不總是在遍歷一致哈希環(huán)時遇到的第一個NN節(jié)點。
4、領(lǐng)導(dǎo)者（Leader）和追隨者（Follower）
為了在管理數(shù)據(jù)的系統(tǒng)中實現(xiàn)容錯，需要在多個服務(wù)器上復(fù)制數(shù)據(jù)。
在集群中選擇一個服務(wù)器作為領(lǐng)導(dǎo)者。領(lǐng)導(dǎo)者負責(zé)代表整個集群做出決策，并將決策傳播到所有其他服務(wù)器。
三到五個節(jié)點的集群，就像在實現(xiàn)共識的系統(tǒng)中一樣，領(lǐng)導(dǎo)者選舉可以在數(shù)據(jù)集群本身內(nèi)實施，而不依賴于任何外部系統(tǒng)。領(lǐng)導(dǎo)者選舉在服務(wù)器啟動時進行。每個服務(wù)器在啟動時都會啟動領(lǐng)導(dǎo)者選舉，并嘗試選舉領(lǐng)導(dǎo)者。除非選出領(lǐng)導(dǎo)者，否則系統(tǒng)不接受任何客戶端請求。
5、心跳
心跳機制用于檢測現(xiàn)有領(lǐng)導(dǎo)者是否失敗，以便可以啟動新的領(lǐng)導(dǎo)者選舉。
6、Fencing
在領(lǐng)導(dǎo)者-追隨者模式中，當(dāng)領(lǐng)導(dǎo)者失敗時，不可能確定領(lǐng)導(dǎo)者已停止工作。例如，慢速網(wǎng)絡(luò)或網(wǎng)絡(luò)分區(qū)可能會觸發(fā)新的領(lǐng)導(dǎo)者選舉，即使前一個領(lǐng)導(dǎo)者仍在運行并認為它仍然是活動的領(lǐng)導(dǎo)者。
屏蔽是指在以前處于活動狀態(tài)的領(lǐng)導(dǎo)者周圍設(shè)置圍欄，使其無法訪問集群資源，從而停止為任何讀/寫請求提供服務(wù)。
使用以下兩種技術(shù)：
-
資源屏蔽：系統(tǒng)會阻止以前處于活動狀態(tài)的領(lǐng)導(dǎo)者訪問執(zhí)行基本任務(wù)所需的資源。
-
節(jié)點屏蔽：系統(tǒng)會阻止以前處于活動狀態(tài)的領(lǐng)導(dǎo)者訪問所有資源。執(zhí)行此操作的常見方法是關(guān)閉節(jié)點電源或重置節(jié)點。
7、WAL（預(yù)寫日志W(wǎng)rite-ahead Log）
預(yù)寫日志記錄是解決操作系統(tǒng)中文件系統(tǒng)不一致的問題的高級解決方案。受數(shù)據(jù)庫管理系統(tǒng)的啟發(fā)，此方法首先將要執(zhí)行的操作的摘要記入“日志”中，然后再將其實際寫入磁盤。在發(fā)生崩潰的情況下，操作系統(tǒng)只需檢查此日志并從中斷的位置繼續(xù)。
8、分段日志
將日志拆分為多個較小的文件，而不是單個大文件，以便于操作。
單個日志文件在啟動時讀取時可能會增長并成為性能瓶頸。較舊的日志會定期清理，并且很難對單個大文件執(zhí)行清理操作。
單個日志拆分為多個段。日志文件在指定的大小限制后滾動。使用日志分段，需要有一種將邏輯日志偏移量（或日志序列號）映射到日志段文件的簡單方法。
9、高水位線（High-Water mark）
跟蹤領(lǐng)導(dǎo)者上的最后一個日志條目，該條目已成功復(fù)制到追隨者的quorum。日志中此條目的索引稱為高水位線索引。領(lǐng)導(dǎo)者僅公開到高水位線索引的數(shù)據(jù)。
Kafka：為了處理非可重復(fù)讀取并確保數(shù)據(jù)一致性，Kafka broker會跟蹤高水位線，這是特定分區(qū)的最大偏移量。使用者只能看到高水位線之前的消息。
10、租約（Lease）
租約就像一個鎖，但即使客戶端離開，它也能工作。客戶端請求有限期限的租約，之后租約到期。如果客戶端想要延長租約，它可以在租約到期之前續(xù)訂租約。
Chubby客戶端與領(lǐng)導(dǎo)者保持有時限的會話租約。在此時間間隔內(nèi)，領(lǐng)導(dǎo)者保證不會單方面終止會話。
11、Gossip協(xié)議
Gossip協(xié)議是點對點通信機制，其中節(jié)點定期交換有關(guān)自己和他們所知道的其他節(jié)點的狀態(tài)信息。
每個節(jié)點每秒啟動一輪Gossip回合，以與另一個隨機節(jié)點交換有關(guān)自己和其他節(jié)點的狀態(tài)信息。
?
12、Phi 累計故障檢測（Phi Accrual Failure Detection）
此算法使用歷史檢測信號信息使閾值自適應(yīng)。通用的應(yīng)計故障檢測器不會判斷服務(wù)器是否處于活動狀態(tài)，而是輸出有關(guān)服務(wù)器的可疑級別。
Cassandra使用Phi應(yīng)計故障檢測器算法來確定群集中節(jié)點的狀態(tài)。
13、腦裂
分布式系統(tǒng)具有兩個或多個活動領(lǐng)導(dǎo)者的場景稱為腦裂。
通過使用生成時鐘（Generation Clock）可以解決腦裂問題，生成時鐘只是一個單調(diào)遞增的數(shù)字，用于指示服務(wù)器的生成。
每次選出新領(lǐng)導(dǎo)者時，時鐘數(shù)字（generation number）都會增加。這意味著，如果舊領(lǐng)導(dǎo)者的時鐘數(shù)為“1”，則新領(lǐng)導(dǎo)人的時鐘數(shù)將為“2”。此時鐘號包含在從領(lǐng)導(dǎo)發(fā)送到其他節(jié)點的每個請求中。通過這種方式，節(jié)點現(xiàn)在可以通過簡單地信任具有最高數(shù)字的領(lǐng)導(dǎo)者來輕松區(qū)分真正的領(lǐng)導(dǎo)者。
Kafka：為了處理腦裂（我們可以有多個active controller broker），Kafka使用“紀元數(shù)”（Epoch number），這只是一個單調(diào)增加的數(shù)字來表示服務(wù)器的代次（generation）。
HDFS：ZooKeeper用于確保任何時候只有一個NameNode處于活動狀態(tài)。epoch編號作為每個事務(wù)ID的一部分進行維護，以反映NameNode的代次。
14、校驗和（checksum）
在分布式系統(tǒng)中，在組件之間移動數(shù)據(jù)時，從節(jié)點獲取的數(shù)據(jù)可能會損壞。
計算校驗和并將其與數(shù)據(jù)一起存儲。
要計算校驗和，請使用MD5、SHA-1、SHA-256或SHA-512等加密哈希函數(shù)。哈希函數(shù)獲取輸入數(shù)據(jù)并生成固定長度的字符串（包含字母和數(shù)字）；此字符串稱為校驗和。
當(dāng)系統(tǒng)存儲某些數(shù)據(jù)時，它會計算數(shù)據(jù)的校驗和，并將校驗和與數(shù)據(jù)一起存儲。當(dāng)客戶端檢索數(shù)據(jù)時，它會驗證從服務(wù)器接收的數(shù)據(jù)是否與存儲的校驗和匹配。如果沒有，則客戶端可以選擇從另一個副本檢索該數(shù)據(jù)。
HDFS和Chubby將每個文件的校驗和與數(shù)據(jù)一起存儲。
15、CAP定理
CAP定理指出，分布式系統(tǒng)不可能同時提供以下所有三個理想屬性：
一致性（C）、可用性（A）和分區(qū)容差（P）。
根據(jù)CAP定理，任何分布式系統(tǒng)都需要從三個屬性中選擇兩個。這三個選項是CA、CP和AP。
Dynamo：在CAP定理術(shù)語中，Dynamo屬于AP系統(tǒng)的類別，旨在犧牲強一致性為代價實現(xiàn)高可用性。
BigTable：就CAP定理而言，BigTable是一個CP系統(tǒng)，即它具有嚴格一致的讀取和寫入。
16、PACELEC定理
PACELC定理指出，在復(fù)制數(shù)據(jù)的系統(tǒng)中：
-
如果有一個分區(qū)（'P'），分布式系統(tǒng)可以在可用性和一致性（即'A'和'C'）之間進行權(quán)衡;
-
否則（'E'），當(dāng)系統(tǒng)在沒有分區(qū)的情況下正常運行時，系統(tǒng)可以在延遲（'L'）和一致性（'C'）之間進行權(quán)衡。
?
定理（PAC）的第一部分與CAP定理相同，ELC是擴展。整個論點假設(shè)我們通過復(fù)制來保持高可用性。因此，當(dāng)失敗時，CAP定理占上風(fēng)。但如果沒有，我們?nèi)匀槐仨毧紤]復(fù)制系統(tǒng)的一致性和延遲之間的權(quán)衡。
17、提示交接（Hinted Handoff）
如果節(jié)點關(guān)閉，系統(tǒng)會保留它們錯過的所有請求的提示（或注釋）。故障節(jié)點恢復(fù)后，將根據(jù)存儲的提示將請求轉(zhuǎn)發(fā)給它們。
當(dāng)節(jié)點關(guān)閉時，領(lǐng)導(dǎo)者會在本地磁盤上的文本文件中寫入提示。此提示包含數(shù)據(jù)及其所屬的節(jié)點信息。當(dāng)領(lǐng)導(dǎo)者意識到它為其保留提示的節(jié)點已恢復(fù)時，它會將每個提示的寫入請求轉(zhuǎn)發(fā)到該節(jié)點。
18、讀取時修復(fù)
在分布式系統(tǒng)中，數(shù)據(jù)跨多個節(jié)點復(fù)制，某些節(jié)點最終可能會擁有過時的數(shù)據(jù)。
在讀取操作期間修復(fù)過時的數(shù)據(jù)，因為此時，我們可以從多個節(jié)點讀取數(shù)據(jù)以進行比較并找到具有過時數(shù)據(jù)的節(jié)點。此機制稱為讀取修復(fù)。一旦已知具有舊數(shù)據(jù)的節(jié)點，讀取修復(fù)操作就會將較新版本的數(shù)據(jù)推送到具有較舊版本的節(jié)點。
Cassandra和Dynamo使用“讀取修復(fù)”將最新版本的數(shù)據(jù)推送到具有舊版本的節(jié)點。
19、默克爾樹（Merkle Trees）
“讀取修復(fù)”可在處理讀取請求時消除沖突。但是，如果某個副本明顯落后于其他副本，則可能需要很長時間才能解決沖突。
副本可以包含大量數(shù)據(jù)。單純地拆分整個范圍來計算校驗和進行比較并不是很可行；有太多的數(shù)據(jù)需要傳輸。相反，我們可以使用Merkle樹來比較一個范圍的副本。
Merkle樹是哈希的二叉樹，其中每個內(nèi)部節(jié)點是其兩個子節(jié)點的哈希，每個葉節(jié)點是原始數(shù)據(jù)一部分的哈希。
?
比較Merkle樹在概念上很簡單：
-
比較兩個樹的根哈希。
-
如果它們相等，請停止。
-
在左邊和右邊的孩子上遞歸檢查。
為了實現(xiàn)反熵和在后臺解決沖突，Dynamo使用Merkle樹。
?
總結(jié)
以上是生活随笔為你收集整理的分布式系统设计模式（荣耀典藏版）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： ZK（1）——分布式系统概念与ZK简介
- 下一篇： 分布式系统概念