【IT168 技術(shù)】長(zhǎng)期以來(lái)學(xué)習(xí)掌握分布式系統(tǒng)的知識(shí)非常龐雜混亂，本文將分布式算法歸納為幾種：計(jì)時(shí)模型timing model; 進(jìn)程間通訊interprocess communication和失敗模型failure model。

　　計(jì)時(shí)模型timing model

　　計(jì)時(shí)模型分同步 異步和部分同步三種，這幾種模型都有時(shí)間計(jì)時(shí)這個(gè)共同特點(diǎn)。

　　同步模型是直接調(diào)用執(zhí)行，組件之間同時(shí)按步驟執(zhí)行，這個(gè)模型的問(wèn)題是無(wú)法反映現(xiàn)實(shí)情況，甚至在分布式情況下很少有真正同步，比如過(guò)去RPC(遠(yuǎn)程過(guò)程調(diào)用)等都是兩個(gè)服務(wù)器之間的代碼方法直接相互調(diào)用，這種問(wèn)題帶來(lái)相互堵塞各種服務(wù)器進(jìn)程，現(xiàn)在服務(wù)器之間都是通過(guò)發(fā)送消息實(shí)現(xiàn)通訊，讓發(fā)送消息變成同步幾乎很難。同步模型好處是能完成理論上測(cè)試結(jié)果，比如，因?yàn)橥侥Ｐ陀袝r(shí)間上的保證，我們可以看看一個(gè)問(wèn)題在同步模型下是否能夠解決，如果在有時(shí)間保證的機(jī)制下都不能解決，意味著在沒(méi)有時(shí)間保證的機(jī)制也是不可能解決的。

　　異步模型有點(diǎn)復(fù)雜，組件之間的動(dòng)作是按照它們自己的順序要求進(jìn)行的，也不提供任何關(guān)于采取這些行動(dòng)的時(shí)間上與速度的保證，這個(gè)模型更接近于現(xiàn)實(shí)情況，但是也不是完美的，比如一個(gè)進(jìn)程會(huì)需要無(wú)限循環(huán)來(lái)響應(yīng)一個(gè)請(qǐng)求，在真實(shí)項(xiàng)目中，我們可能會(huì)強(qiáng)加一個(gè)計(jì)時(shí)timeout，一旦超過(guò)這個(gè)timeout，將會(huì)退出這個(gè)請(qǐng)求的處理，這就帶來(lái)了問(wèn)題，如果確保一個(gè)進(jìn)程活躍的條件?也就是說(shuō)，如何知道一個(gè)進(jìn)程是需要無(wú)限循環(huán)活躍的，而其他進(jìn)程則是不需要，需要timeout去中斷的，這里面哪個(gè)是業(yè)務(wù)需要，哪個(gè)是因?yàn)楣收蠈?dǎo)致的呢?

　　在部分同步模型中大部分訪問(wèn)同步時(shí)鐘，有關(guān)于傳遞消息有多長(zhǎng)的限制，有一個(gè)進(jìn)程執(zhí)行一個(gè)步驟需要多長(zhǎng)時(shí)間的限制。

　　進(jìn)程間通訊

　　進(jìn)程之間是如何通訊的，這里有消息傳遞模型和共享內(nèi)存模型，前者是通過(guò)消息發(fā)送通訊，后者是訪問(wèn)內(nèi)存中共享變量共享數(shù)據(jù)進(jìn)行通訊。這里進(jìn)程有服務(wù)器 節(jié)點(diǎn)的意思，一個(gè)進(jìn)程可能代表分布式場(chǎng)景的一臺(tái)服務(wù)器。

　　消息傳遞最難的是不能發(fā)送重復(fù)消息，每次只能精確一次傳遞，這里有很多設(shè)計(jì)，比如Perfect Links抽象可以保證，但是它不能正常反映現(xiàn)實(shí)世界，雖然不真實(shí)，但是有用，我們可以使用Perfect Links證明一個(gè)問(wèn)題不可能被解決，然后我們就知道其他相關(guān)問(wèn)題也沒(méi)有答案。消息傳遞總是可以被想象為FIFO之類隊(duì)列或堆棧。

　　共享內(nèi)存是我們編程常用的方式，需要在一臺(tái)服務(wù)器內(nèi)才能完成。我們可以使用消息傳遞算法完成分布式情況下的內(nèi)存共享對(duì)象，比如讀寫注冊(cè)器，調(diào)用一個(gè)服務(wù)之間需要查詢這個(gè)服務(wù)在哪個(gè)服務(wù)器上，負(fù)載平衡器也是一個(gè)讀寫注冊(cè)器，是一個(gè)全局共享的內(nèi)存。

　　失敗模型

　　分布式模型總是必須考慮進(jìn)程失敗的情況，在crash-stop失敗模型中，一個(gè)進(jìn)程假設(shè)為一直是正確，直至它崩潰，一旦它崩潰，就永遠(yuǎn)不會(huì)恢復(fù);也有crash-recovery 模型，進(jìn)程能夠在失敗以后恢復(fù)，在這種情況下，一些算法來(lái)保證進(jìn)程恢復(fù)到其失敗之前的狀態(tài)，這可以通過(guò)從持久層讀取狀態(tài)完成，或者通過(guò)和一個(gè)集群小組中的其他進(jìn)程通訊方式完成。注意這里有不同集群組算法，一個(gè)進(jìn)程崩潰后，恢復(fù)其狀態(tài)的進(jìn)程不會(huì)再被認(rèn)為是之前同樣的進(jìn)程，這取決于動(dòng)態(tài)組還是固定組這兩種算法。

　　失敗模型也包括：一個(gè)進(jìn)程如果無(wú)法接受和發(fā)送消息，被稱為遺漏omission failure mode，遺漏模型也有不同種類，一個(gè)進(jìn)程無(wú)法接受和發(fā)送消息很重要嗎?想象一組進(jìn)程實(shí)現(xiàn)一個(gè)分布式緩存，如果一個(gè)進(jìn)程無(wú)法回復(fù)同一組的其他進(jìn)程，即使能夠接受來(lái)自它們的請(qǐng)求，這也意味著這個(gè)進(jìn)程能夠接受外部消息更新自己的狀態(tài)，其實(shí)也就意味著它能回復(fù)來(lái)自客戶端的讀請(qǐng)求，也就是說(shuō)，雖然它自己不能主動(dòng)回復(fù)客戶端的請(qǐng)求，但是可以接受客戶端的主動(dòng)讀取請(qǐng)求。

　　一個(gè)復(fù)雜失敗模型是拜占庭Byzantine 或稱為任意失敗模型，進(jìn)程會(huì)發(fā)送錯(cuò)誤信息到對(duì)方，它們會(huì)模仿發(fā)送正確數(shù)據(jù)，但是實(shí)際已經(jīng)篡改了本地?cái)?shù)據(jù)庫(kù)的內(nèi)容。

　　設(shè)計(jì)分布式系統(tǒng)時(shí)，我們需要對(duì)付這些失敗模型。

　　失敗探測(cè)

　　我們希望在進(jìn)程崩潰失敗時(shí)及時(shí)發(fā)現(xiàn)，比如crash-stop失敗模型加上同步系統(tǒng)，我們能夠使用timeout;如果我們定期讓進(jìn)程ping到一個(gè)專門的失敗探測(cè)器，我們就能精確知道那個(gè)進(jìn)程是否正常，如果過(guò)了timeout時(shí)間沒(méi)有Ping訪問(wèn)，那么我們就可以認(rèn)為那臺(tái)進(jìn)程服務(wù)器崩潰了。

　　更真實(shí)情況是，假設(shè)一個(gè)消息到達(dá)目標(biāo)需要確定的時(shí)間，確定好一個(gè)進(jìn)程執(zhí)行一個(gè)步驟需要多長(zhǎng)時(shí)間，那么就可以使用timeout進(jìn)行衡量計(jì)算。

　　失敗模型探測(cè)有兩個(gè)屬性策略：

　　1. Strong Completeness強(qiáng)完整性：每個(gè)失敗的進(jìn)程會(huì)永久被其他正確進(jìn)程懷疑。

　　2.Eventual Strong Accuracy最終強(qiáng)精確度，沒(méi)有一個(gè)進(jìn)程被任何正確的進(jìn)程懷疑。

　　當(dāng)一個(gè)進(jìn)程被其他進(jìn)程懷疑時(shí)，這些進(jìn)程就不可能達(dá)成共識(shí)consensus ，而在分布式系統(tǒng)中使用異步模型是必須要達(dá)成共識(shí)，也就是每個(gè)進(jìn)程內(nèi)部狀態(tài)通過(guò)異步消息傳遞后，最終其他進(jìn)程的狀態(tài)會(huì)和最初發(fā)送消息的那個(gè)進(jìn)程內(nèi)部狀態(tài)一致，這稱為達(dá)成共識(shí)，但是因?yàn)橛羞M(jìn)程存在失敗崩潰的可能，所以，在這個(gè)達(dá)成共識(shí)的消息傳遞過(guò)程中，如何確保進(jìn)程之間的信任，不懷疑對(duì)方，從而確保消息傳遞成功，那么引入失敗探測(cè)器是可以規(guī)避這個(gè)問(wèn)題的。

　　領(lǐng)導(dǎo)人選舉LEADER ELECTION

　　這是通過(guò)決定某個(gè)進(jìn)程沒(méi)有崩潰失敗，能夠正常工作，那么這個(gè)進(jìn)程就可以被網(wǎng)絡(luò)中其他進(jìn)程信任，它就可以被認(rèn)為是領(lǐng)導(dǎo)人，負(fù)責(zé)協(xié)調(diào)分布式動(dòng)作，這種協(xié)議有Raft和Zab兩種。

　　這種機(jī)制會(huì)導(dǎo)致瓶頸集中在領(lǐng)導(dǎo)人那里，而且之前還需要領(lǐng)導(dǎo)人選舉，這些多余過(guò)程可能是我們不需要的。

　　一致共識(shí)CONSENSUS

　　共識(shí)是在獨(dú)立進(jìn)程之間達(dá)成一致的統(tǒng)一意見(jiàn)，這些進(jìn)程會(huì)就某個(gè)問(wèn)題建議一個(gè)數(shù)值，基于這個(gè)推薦的值會(huì)同意采取一致行動(dòng)，比如，一個(gè)轎車有各種傳感器提供制動(dòng)器溫度的信息，依賴于傳感器的精度，會(huì)有不同變化的數(shù)值，但是ABS計(jì)算機(jī)需要知道施加多大壓力到制動(dòng)器上，這種共識(shí)問(wèn)題每天生活中都發(fā)生。

　　一個(gè)進(jìn)程實(shí)現(xiàn)共識(shí)是通過(guò)暴露帶有推薦和決定功能的API實(shí)現(xiàn)的，一個(gè)進(jìn)程會(huì)推薦數(shù)值，由此開(kāi)始共識(shí)，然后它得基于一個(gè)數(shù)值決定，這個(gè)數(shù)值是在整個(gè)系統(tǒng)中被推薦了的，這些算法包括：Termination, Validity, Integrity 和Agreement.

　　1.Termination: 每個(gè)正確的進(jìn)程最終會(huì)決定某個(gè)數(shù)值。

　　2.Validity: 如果一個(gè)進(jìn)程決定了v，那么v會(huì)被其他進(jìn)程推薦。

　　3.Integrity: 沒(méi)有進(jìn)程能夠決定兩次

　　4.Agreement: 沒(méi)有兩個(gè)正確進(jìn)程有不同的決定。

　　法定人數(shù)QUORUMS

　　Quorums 是一個(gè)設(shè)計(jì)失敗容錯(cuò)分布式系統(tǒng)的工具，當(dāng)系統(tǒng)存在crash-failure模型時(shí)，總是有一個(gè)法定人數(shù)代表大多數(shù)意見(jiàn)從而進(jìn)行決策的，因?yàn)楸罎⑹〉目偸巧贁?shù)。

　　比如有N個(gè)進(jìn)程服務(wù)器，假設(shè)崩潰的進(jìn)程是少數(shù)，比如N/2-1個(gè)進(jìn)程崩潰，也就是49%的進(jìn)程崩潰，我們還是有51%的會(huì)投贊成票。Raft協(xié)議使用的是這種大多數(shù)策略，根據(jù)提交到系統(tǒng)的日志來(lái)判斷，

　　分布式系統(tǒng)的時(shí)間

　　理解時(shí)間和其導(dǎo)致的因果是分布式系統(tǒng)的大問(wèn)題，我們通常用事件這個(gè)概念代表生活中發(fā)生的那些事實(shí)，使用happened before順序約束定義這些事件，但是我們有很多進(jìn)程交換信息，共同訪問(wèn)共享資源等等，我們?nèi)绾胃嬖V某個(gè)進(jìn)程事件的happened before策略呢?也就是誰(shuí)在前誰(shuí)在后的順序呢?為了回答這個(gè)問(wèn)題，進(jìn)程需要共享一個(gè)同步的時(shí)鐘，精確知道它在網(wǎng)絡(luò)間移動(dòng)花費(fèi)多長(zhǎng)時(shí)間?包括CPU調(diào)度任務(wù)的時(shí)間等等，顯然這在真實(shí)世界是不可能實(shí)現(xiàn)的。

　　Time, Clocks, and the Ordering of Events in a Distributed System引入了邏輯時(shí)鐘概念，邏輯時(shí)鐘是一個(gè)分配一個(gè)數(shù)字給事件的方式，也就是說(shuō)，這些數(shù)字不是和實(shí)際時(shí)間有關(guān)，但是和一個(gè)節(jié)點(diǎn)的進(jìn)程事件有關(guān)。

　　有各種邏輯時(shí)鐘，比如 Vector Clocks向量時(shí)鐘或 Interval Tree Clocks.

　　理解分布式時(shí)間問(wèn)題，必須理解一個(gè)重要概念：同時(shí)性這個(gè)想法有時(shí)我們必須放棄(The idea of simultaneity is something we have to let go.)，這是有關(guān)“絕對(duì)知識(shí)”等舊哲學(xué)信條的問(wèn)題，他們認(rèn)為絕對(duì)知識(shí)是可以到達(dá)的，其實(shí)人的認(rèn)識(shí)是相對(duì)，永遠(yuǎn)不可能到達(dá)真正事物本質(zhì)，你以為的同時(shí)性并不是真正同時(shí)性，光線也是有速度的，即使最快的光線也是需要時(shí)間才從一個(gè)地方到達(dá)另外一個(gè)地方?？梢?jiàn)Inventing the Enemy發(fā)明敵人 一書中的“絕對(duì)與相對(duì)”。