[[409590]]

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

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

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

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

Leader和Lock

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

• 一個數(shù)據(jù)庫partition中只能有一個節(jié)點是leader

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

• 一個用戶名只能由用戶注冊，因為它必須唯一。

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

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

Fencing Tokens

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

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

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

拜占庭問題（ByzantineFaults）

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

我們可以簡單認為在一個有拜占庭問題的系統(tǒng)中，可能會有那么一兩個節(jié)點給出的消息是不可靠的。這種不可靠可能是因為:

• 機器的memory或者CPU registry中的數(shù)據(jù)因為一些原因出了問題。比如說我們讀registry的時候出錯了，就返回一個default值，或者任意的值等等。

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

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

減少謊言的存在

 雖然我們認為有謊言的節(jié)點是很少的。但是假如我們能夠有一些機制去探測或者保護節(jié)點，那顯然會更好，比如：

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

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

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

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

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

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

同步模型

所謂同步模型就是指你知道網(wǎng)絡延時，process的暫停和時鐘的漂移不會超過某一個限制值。當然不是說沒有網(wǎng)絡延時，只是說你知道它不會超過一個界限。當然這種模型其實在現(xiàn)實中是不現(xiàn)實的，因為總有意料之外的延時會發(fā)生。

部分同步模型

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

異步模型

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

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

Crash-stop錯誤

這種模型下，算法認為一個節(jié)點出問題了，比如不響應了，就再也不會回來了。

Crash-Recovery錯誤

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

拜占庭錯誤  

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

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

算法的正確性

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

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

唯一性

沒有任何兩個請求得到的token是一樣的。

單調(diào)遞增

假如請求x的token是tx，請求y的token是ty，x在y前面，那么tx<ty。

可靠性

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

安全和活力

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

總結(jié)

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