[[409590]]

我們知道分布式系統(tǒng)中各個(gè)服務(wù)器都是通過網(wǎng)路進(jìn)行連接的，這樣導(dǎo)致的結(jié)果就是你很難知道各個(gè)服務(wù)器的真實(shí)狀況，比如你判斷另外一臺(tái)服務(wù)器是否有問題的唯一辦法就是發(fā)送一個(gè)請(qǐng)求給他，只有收到了回應(yīng)，你就認(rèn)為它是好的，假如沒有收到回應(yīng)，你就很難判斷對(duì)面的服務(wù)器是否有問題，因?yàn)檫@個(gè)沒有回應(yīng)很可能是發(fā)生了網(wǎng)絡(luò)故障，也可能是對(duì)端機(jī)器真的出問題了。 因此，在分布式系統(tǒng)中我們?nèi)绾蝸頊?zhǔn)確判斷這些問題呢？ 本文就來詳細(xì)介紹相關(guān)的方法。

基于多數(shù)的（Majority）事實(shí)

很多時(shí)候我們一個(gè)節(jié)點(diǎn)可能不是真的有問題，比如說它正在進(jìn)行 GC ，那么在 GC 的這段時(shí)間內(nèi)它就不能回應(yīng)任何請(qǐng)求，這個(gè)時(shí)候從節(jié)點(diǎn)本身的來看，它自己是很 ok 的，沒有任何問題。 然而從 別的節(jié)點(diǎn)來看，這個(gè) GC 的節(jié)點(diǎn)就和出問題的節(jié)點(diǎn)一模一樣，發(fā)請(qǐng)求它不回，重試也沒有反應(yīng)。 所以別的節(jié)點(diǎn)就會(huì)認(rèn)為它是有問題的。 從這個(gè)角度來看，節(jié)點(diǎn)本身其實(shí)也是很難知道自己是否問題的。

現(xiàn)在比較流行判斷節(jié)點(diǎn)是否有問題的算法都是基于多數(shù)的決策，比如說我有5個(gè)節(jié)點(diǎn)，那么大家一起來投票，假如有超過一定數(shù)量的節(jié)點(diǎn)（一般來說超過半數(shù)，這里就是有三個(gè)節(jié)點(diǎn)）認(rèn)為它有問題，那么我們就認(rèn)為這個(gè)節(jié)點(diǎn)是真的有問題。哪怕這個(gè)節(jié)點(diǎn)本身是沒有問題的，但是只要有多數(shù)認(rèn)為有問題，我們就認(rèn)為它有問題。這里使用多數(shù)來決定是因?yàn)槎鄶?shù)就意味著不會(huì)有沖突，因?yàn)橐粋€(gè)系統(tǒng)中不可能存在兩個(gè)多數(shù)，只可能有一個(gè)。

Leader和Lock

為什么我們要去判斷一個(gè)節(jié)點(diǎn)是否有問題呢？事實(shí)上，在分布式系統(tǒng)中，有很多場(chǎng)景會(huì)使用到一個(gè)只能一個(gè)的概念，比如：

• 一個(gè)數(shù)據(jù)庫(kù)partition中只能有一個(gè)節(jié)點(diǎn)是leader

• 為了防止同時(shí)寫，只能有一個(gè)transaction或者client允許hold 某個(gè)object的lock。

• 一個(gè)用戶名只能由用戶注冊(cè)，因?yàn)樗仨毼ㄒ弧?/p>

這些場(chǎng)景都需要我們?cè)谠O(shè)計(jì)的時(shí)候小心一點(diǎn)，比如說即使一個(gè)節(jié)點(diǎn)認(rèn)為它自己是這個(gè)選中的唯一（比如認(rèn)為它自己的leader，認(rèn)為它拿到這個(gè)object的lock等等），也可能大多數(shù)別的節(jié)點(diǎn)認(rèn)為它有問題，這個(gè)時(shí)候假如設(shè)計(jì)不好的話，就會(huì)出問題，我們來看下面這個(gè)例子：

這個(gè)例子中，我們?yōu)榱朔乐褂卸鄠€(gè)client訪問同樣的數(shù)據(jù)，會(huì)要求每個(gè)client在寫之后要先抓一下鎖。這個(gè)鎖是一個(gè)lease的鎖，就是超時(shí)會(huì)釋放的。這里你可以看到Client1首先申請(qǐng)了這個(gè)鎖，但是很不幸，在拿到這個(gè)鎖之后，它立即發(fā)生了一個(gè)GC，而這個(gè)GC發(fā)生的時(shí)候超過了lease的timeout，這就導(dǎo)致這個(gè)鎖在lease超時(shí)之后被釋放了，而client2就拿到了這個(gè)鎖，做了一個(gè)更新。而client1在GC回來之后認(rèn)為它是拿著這個(gè)鎖的，所以它直接也去寫了，這個(gè)時(shí)候就出現(xiàn)問題了。這里的問題就是GC回來之后，client1錯(cuò)誤地認(rèn)為它自己還是拿著鎖的。

Fencing Tokens

那么如何處理上面這種錯(cuò)誤認(rèn)知呢？一個(gè)常見的技術(shù)是fencing。如下圖所示：

這里做的改變就是每次我們?nèi)ツ面i的時(shí)候會(huì)返回一個(gè)token值給client，這個(gè)token每次拿到鎖的時(shí)候都會(huì)遞增。這樣在client寫的時(shí)候必須同時(shí)把這個(gè)token也發(fā)送回來。這樣一來storage就可以可根據(jù)這個(gè)token來判斷是否reject舊的token的寫。

一個(gè)常見的實(shí)現(xiàn)方式就是使用ZooKeeper的TransactionID或者node version來作為fencingToken。

拜占庭問題（ByzantineFaults）

上文中說的FencingToken有一個(gè)前提，就是client發(fā)過來的token是它真正收到，你可以想象假如client在寫的時(shí)候發(fā)送的token是一個(gè)假的token，那么顯然fencingToken就也會(huì)有問題了。所以對(duì)于分布式系統(tǒng)來說，假如有節(jié)點(diǎn)說謊，那么問題就會(huì)變得更加復(fù)雜，我們稱這種情況為拜占庭問題，也就是我們常說的拜占庭將軍問題。

我們可以簡(jiǎn)單認(rèn)為在一個(gè)有拜占庭問題的系統(tǒng)中，可能會(huì)有那么一兩個(gè)節(jié)點(diǎn)給出的消息是不可靠的。這種不可靠可能是因?yàn)?

• 機(jī)器的memory或者CPU registry中的數(shù)據(jù)因?yàn)橐恍┰虺隽藛栴}。比如說我們讀registry的時(shí)候出錯(cuò)了，就返回一個(gè)default值，或者任意的值等等。

• 比如說有一些cheat或者attack發(fā)生。這種情況下節(jié)點(diǎn)就是不可信的。

當(dāng)然，在現(xiàn)實(shí)中，我們認(rèn)為這種不可信的問題它發(fā)生在比較少的節(jié)點(diǎn)，而不是大多數(shù)或者所有。所以假如有任何不可信的事情發(fā)生在多數(shù)節(jié)點(diǎn)上（比如有個(gè)code的bug，總是把收到的token加一個(gè)隨機(jī)數(shù)），那么相應(yīng)的算法也是沒有辦法解決這個(gè)問題的。

減少謊言的存在

 雖然我們認(rèn)為有謊言的節(jié)點(diǎn)是很少的。但是假如我們能夠有一些機(jī)制去探測(cè)或者保護(hù)節(jié)點(diǎn)，那顯然會(huì)更好，比如：

• 網(wǎng)絡(luò)的包，我們會(huì)加一些checksum來檢測(cè)它是否正確。

• 對(duì)用戶的輸入值加一些檢查，比如看是否在一個(gè)合理的范圍內(nèi)。

• NTP的客戶端連接多個(gè)地址，然后看majority的反饋來決定真實(shí)的時(shí)間等。

系統(tǒng)模型和現(xiàn)實(shí)

我們?cè)O(shè)計(jì)了很多算法來解決各種分布式系統(tǒng)中的問題。而這些算法都是基于一系列的軟件和硬件對(duì)的，也就是說有很多假設(shè)，而這些依賴就是我們俗稱的系統(tǒng)模型。

比如說我們談到時(shí)間假設(shè)，下面這三種就是常見的系統(tǒng)模型：

同步模型

所謂同步模型就是指你知道網(wǎng)絡(luò)延時(shí)，process的暫停和時(shí)鐘的漂移不會(huì)超過某一個(gè)限制值。當(dāng)然不是說沒有網(wǎng)絡(luò)延時(shí)，只是說你知道它不會(huì)超過一個(gè)界限。當(dāng)然這種模型其實(shí)在現(xiàn)實(shí)中是不現(xiàn)實(shí)的，因?yàn)榭傆幸饬现獾难訒r(shí)會(huì)發(fā)生。

部分同步模型

所謂部分同步模型就是我們認(rèn)為大多數(shù)時(shí)候是同步模型，就是不會(huì)超過一定的限制，但那是有時(shí)還是會(huì)超過這些限制。這個(gè)就是一個(gè)比較現(xiàn)實(shí)的模型。

異步模型

這種模型就是不做任何假設(shè)，甚至連時(shí)鐘多不信任，比如不是用超時(shí)。限制這種模型的限制就非常大。

除了上面的關(guān)于時(shí)間的假設(shè)，還有一個(gè)比較常見的問題就是節(jié)點(diǎn)失敗的假設(shè)，通常有下面這三種模型：

Crash-stop錯(cuò)誤

這種模型下，算法認(rèn)為一個(gè)節(jié)點(diǎn)出問題了，比如不響應(yīng)了，就再也不會(huì)回來了。

Crash-Recovery錯(cuò)誤

這種模型下，算法認(rèn)為一個(gè)節(jié)點(diǎn)出問題了，它一會(huì)還會(huì)回來。當(dāng)然什么回來不知道。這就要求節(jié)點(diǎn)可能需要一些能夠常見保存的介質(zhì)，比如很多東西寫到磁盤中去，這樣即使crash了之后還能恢復(fù)。

拜占庭錯(cuò)誤  

節(jié)點(diǎn)有可能發(fā)生任何事情，就像我們上面說的那樣。

我們?cè)诂F(xiàn)實(shí)中最常見的模型就是部分同步的crash-recovery錯(cuò)誤。那么分布式系統(tǒng)的算法如何使用這些模型呢？

算法的正確性

我們判斷算法的正確性的時(shí)候，需要使用一些屬性來判斷。比如一個(gè)從小到大的排序算法，輸出中的兩個(gè)不同的元素就需要滿足前面的比后面的小。這就是一個(gè)最簡(jiǎn)單的判斷方法。

同樣的，那么我們?nèi)绾闻袛喾植际较到y(tǒng)中的算法是否正確呢？我們還是以上面那個(gè)拿鎖為例，我們可以有下面這些屬性來進(jìn)行判斷：

唯一性

沒有任何兩個(gè)請(qǐng)求得到的token是一樣的。

單調(diào)遞增

假如請(qǐng)求x的token是tx，請(qǐng)求y的token是ty，x在y前面，那么tx<ty。

可靠性

假如有節(jié)點(diǎn)發(fā)送了請(qǐng)求，那么只要不crash它最終都能收到response。

安全和活力

這里我們需要區(qū)分兩個(gè)概念，一個(gè)是安全一個(gè)是活力（Liveness）。比如上面的例子中的唯一性和單調(diào)遞增就是安全，可靠性就是活力。簡(jiǎn)單區(qū)分這兩者就是安全一般指壞的不能發(fā)生，活力指好的最終會(huì)發(fā)生。區(qū)分這兩者有助于我們處理比較復(fù)雜的系統(tǒng)模型。

總結(jié)

本文詳細(xì)介紹了分布式系統(tǒng)中對(duì)真實(shí)的判斷和處理，希望大家能有一個(gè)大概的了解。