你可能并不真正了解分布式系統(tǒng)

global clock

我們先說說全局時鐘 —— global clock。它是分布式系統(tǒng)諸多難題的根源之一。

在單機系統(tǒng)里，無論是 SMP 還是 NUMA，有且只有唯一的全局時鐘，這個很容易辦到。

時間是什么?拋開相對論，在狹義的局部時空中，時間是因果的表象 —— 一個 cause 引發(fā)了一個 effect，這種因果產(chǎn)生了時間的概念：用時間(過去，現(xiàn)在，未來)可以更好地描繪因果。我們在 t0 執(zhí)行一條指令，t1 得到結(jié)果，這結(jié)果不可能出現(xiàn)在指令執(zhí)行之前，這便是時間帶給我們的確定性。所以，一個系統(tǒng)有一致的，大家都認可和遵循的時間，非常重要。

在分布式系統(tǒng)里，每個系統(tǒng)都有自己的時鐘，即便用 NTP(Network Time Protocol)同步，大家也無法嚴格步調(diào)一致;就算時鐘的差異小到可以忽略不計，但取決于帶寬，當時的擁塞程度，CPU 的繁忙程度，多個系統(tǒng)互相之間發(fā)送消息的延遲還是非常地不確定。就跟一個團隊去會議室開會一樣，如果都根據(jù)自己的手表來決定進入會議室的時間，那么肯定會不一致;即便手表時間一致，大家的走路的速度不同，最終進入會議室的時間，也是不一致。這種不一致會帶來很多問題，比如說 out of sync —— 大家都散會了，Alice 才抵達會場，所以她缺失了很多狀態(tài)的更新，于是她不知道手上的下一件事該做還是不該做。所以在分布式系統(tǒng)里很多時候我們需要一致性，來確保某些東西是有序的，大家在同一個 page，否則這個系統(tǒng)會走入歧途。

要解決因為時鐘不同，步調(diào)不一致而導致的 out of sync 的問題，我們需要設(shè)法形成一個邏輯上的「時鐘」，讓大家都認可這個「時鐘」而不是自己的時鐘。這個邏輯時鐘的第一個實現(xiàn)是 Lamport timestamps(請記住 Lamport 這位圖靈獎獲得者，分布式系統(tǒng)的先驅(qū)，下文他還會上鏡)。Lamport timestamps 學術(shù)價值大于實際價值，并沒有系統(tǒng)實際使用，然而在它之上演進出的 vector clock 廣泛被 AWS S3，DynamoDB，Riak 等系統(tǒng)采用，用于確保同一個 object 的因果關(guān)系。我們看看 vector clock 的實現(xiàn)：

這個算法的思想很簡單：所有 node 都有一個包含所有 timestamp 的 vector，這是個邏輯「時鐘」。每個獨立的 node 自行處置屬于自己的 timestamp，使其有序;但當需要 coordinate 的時候(A 發(fā)消息給 B)，node A 要發(fā)送自己對「時鐘」的掌握情況，node B 收到后，更新 vector 里所有比自己已知更大的 timestamp。算法如下(請自行 wiki 以獲得更準確的信息)：

每個 node 都有一個 timestamp vector，初始化為全 0。

如果某個 node k發(fā)生了某個事件，將其對應(yīng)的 vector[k] + 1。

如果 node k 給 node j 發(fā)消息，那么先將 node k 自己的 vector[k] + 1，然后將整個 vector 連同 message 一起發(fā)給 node j，node j 將自己原有的 vector[j] + 1，再把 node k 發(fā)來的 vector 和自己合并(找最大值)。

通過 vector clock，雖然沒有絕對的 global clock，但是我們在分布式系統(tǒng)里能夠保證因果，從而消滅了在這個維度上的不確定性(還有其他不確定性!)。

我們可以看到，vector clock 的算法嚴重依賴于節(jié)點間的信任，所以它只適用于一個可信賴的分布式環(huán)境。而作為運行在節(jié)點間互相并不信任的 P2P 網(wǎng)絡(luò)上的 bitcoin，無法確保這一點。那么，類似 bitcoin 這樣的分布式系統(tǒng)，是怎么決定時間(因果)的呢?中本聰在 bitcoin 的設(shè)計中，巧妙地應(yīng)用了 PoW 的產(chǎn)物，block 來作為系統(tǒng)的邏輯時間：

The solution we propose begins with a timestamp server. A timestamp server works by taking a hash of a block of items to be timestamped and widely publishing the hash， such as in a newspaper or Usenet post [2-5]. The timestamp proves that the data must have existed at the time， obviously， in order to get into the hash. Each timestamp includes the previous timestamp in its hash， forming a chain， with each additional timestamp reinforcing the ones before it.

所以，blockchain 不但承載了 ledger 的功能，chain 上的一個個 block 還是一個個 timestamp，代表著這個系統(tǒng)的過去，現(xiàn)在，以及未來，從而協(xié)調(diào)整個分布式系統(tǒng)步調(diào)一致地前進(且讓我再奶一下聰哥)。

看到這里，我相信很多人有個疑問 —— 程序君，為什么我做的分布式系統(tǒng)既不用關(guān)心 vector clock，也不用 PoW，整個系統(tǒng)也木有 global clock，怎么還一樣運行得好好的?沒錯。你沒有感知，并不代表它不存在或者不重要 —— 你的系統(tǒng)里的 postgres，consul，kafka，或者說，分布式系統(tǒng)里一切看似中心化的部分，都使用了類似的機制，只不過它們幫你把這些細節(jié)屏蔽掉而已。

coordination / communication

好，了解了 lack of global clock 帶來的不確定性，以及如何應(yīng)對這種不確定性，我們再看分布式系統(tǒng)里下一個會引發(fā)不確定性的基礎(chǔ)組成部分：溝通協(xié)作。

單機系統(tǒng)，協(xié)作和溝通也是件輕而易舉的事情 —— 同一個線程，在 stack / register 上同步(取決于 ABI);不同線程，semaphore;不同 CPU，spin lock，memory barrier，反正大家生活在一個屋檐(時鐘)下，咋都有辦法。

分布式系統(tǒng)下就尷尬了。隔壁老王之所以被稱作隔壁老王，是因為你們兩家之間至少有一堵墻(住大 house 的有兩堵墻)，所以在無法四目相對的情況下，你們溝通基本靠吼。吼是個文言文，在現(xiàn)代計算機文明中，我們管它叫：發(fā)消息(message passing)。

發(fā)消息前先要確保有合適的信道，你得先確保這個信道建立成功并且可以信賴：

所謂可信賴，就是消息在網(wǎng)絡(luò)上不會丟失，我只要發(fā)了，對方的 application 就一定能收到(避免下圖所示的不確定性)：

而且既不會像下面這樣亂序，也不會把 partial message 交付給 application(保證消息的完整性)：

有了可信賴的信道，我們可以通過 message 來達成共識。我們先看兩個人達成共識會遇到什么障礙：

發(fā)送的節(jié)點或者接收的節(jié)點可能會 crash —— 即便網(wǎng)絡(luò)層保證了 application 一定會收到消息，但我們無法避免 application 在處理消息的時候掛掉。因而，message delivery 有兩種策略：at least once 或者 at most once。at least once 是指同一個消息會被傳輸 1 到 n 次，而 at most once 是指同一個消息會被傳輸 0 到 1 次。這很好理解，如果 messaging system 內(nèi)建了重傳機制，并且將消息持久化到磁盤中以保證即便進程崩潰消息依舊能夠送達，那么這就是 at least once。反之，如果沒有構(gòu)建任何上述的機制，消息送出后就并不理會，這是 at most once。在一個網(wǎng)絡(luò)環(huán)境中，消息的送達只能是上述兩種情況，不可能 exactly once，如果有人這么說，那么一定是在誤導。

at least once / at most once 并沒有解決不確定性的問題，所以我們還得再努努力 —— kafka / AWS kenisis / AWS SQS 實現(xiàn)了 essentially once 的 message delivery 機制。essentially once 是 at least once 的變種，它需要消息層和應(yīng)用層同心協(xié)力 —— 應(yīng)用層處理完消息，主動告知消息層，令其刪除對應(yīng)的消息。如果你用過 SQS，應(yīng)該能感受到這一點：SQS 保證當一個 application 在處理某個消息時，消息對分布式系統(tǒng)里的其他人是不可見的，如果 application crash，消息會在 visibility timeout 后重新可見，如果 application 處理完畢，需要顯式地刪除這條消息。

最終，我們可以通過消息傳遞的機制，來達成一致：

到目前為止，我們所談?wù)摰倪€主要是僅有你和老王參與的 message delivery 的問題。在一個分布式系統(tǒng)里，任意兩兩節(jié)點間都可能有消息往來，而由于缺乏全局的時鐘，我們無法保證消息是全局有序的(TCP 只能保證相同發(fā)起人發(fā)送的消息時有序的)，通過 vector clock 或者類似的機制，我們可以進一步保證消息在因果關(guān)系上是有序的。這在大多數(shù)情況下，已經(jīng)足夠好。

然而，在眾多參與者的情況下，即便我們保證了消息局部以及在因果關(guān)系上有序，我們還是無法保證所有參與者達成共識。如果大家就該不該做一件事情(比如來了一條數(shù)據(jù)，怎么寫，寫到哪，誰來寫等)無法達成共識，那么，這樣的系統(tǒng)依舊是不確定的。

于是有了 2PC(2 phase commit)，3PC，Paxos，Raft 等在可信環(huán)境下的共識機制;同樣的，對于 blockchain 所面臨的不可信環(huán)境下(Byzantine General probelm)，誕生了 BFT / PBFT，以及 PoW，PoS，DPoS，PoI，PoD，PoDDOS 等一堆 P 字輩靠譜或者不靠譜的共識算法(很快，P 都不夠用了)。限于篇幅，關(guān)于共識算法，我將另行撰文討論。

如果你更多了解消息系統(tǒng)及消息傳遞的 pattern，可以看看我之前的文章：ZeroMQ及其模式(再沉痛悼念一下 Pieter Hintjens)。

分布式系統(tǒng)中的坑

上文中我們已經(jīng)把分布式系統(tǒng)中最基本的要素過了一下。接下來我們踩踩坑。

坑一：network is reliable。我們在消息傳遞中，費盡心思做了很多事情，就是在跟并不 reliable 的 network 斗爭。其實 packet loss / out of order 是屬于還好解決的問題;不那么好解決的問題是：split brain(腦裂)。split brain 是基于 asymmetric consensus 的分布式系統(tǒng)(亦即常見的 master-slave cluster)的夢魘，一旦 master 過忙，導致 slave 認定它應(yīng)該卸任，slave 接管后，因為冷啟動，也變得太忙，于是又切換回去 —— 于是 master / slave 都在一定時間內(nèi)異常繁忙，replication 失敗，數(shù)據(jù)出現(xiàn)不一致，接下來雙方都認為對方 down 掉，自己成為 master。這就是 split brain。這種級別的問題，修復起來都麻煩(尤其是對于使用了 autoincrement，然后又被 foreign key 引用的數(shù)據(jù))。

坑二：消息傳遞的 latency 可以忽略不計。我們知道網(wǎng)絡(luò)的 latency 是大致等于兩點間距離除以光速。北京到舊金山，極其理想的情況下，一個 round trip 也要 63ms(9516 x 2 / 300， 000)，這是一個不小的時間了，如果使用停等的方式互相確認詳細，1s 僅僅能打十幾個來回。下圖是一個完整的計算機系統(tǒng)里各個部分的 latency 的量級的介紹，大家都應(yīng)該讀讀，心里有個譜：

坑三：網(wǎng)絡(luò)帶寬不是問題。在 cloud 里，帶寬不是問題。但由眾多家庭用戶參與的 P2P network，帶寬，尤其是上行帶寬是明顯受限的。我家的百兆網(wǎng)絡(luò)，上行經(jīng)常也就是 12Mbps。我在上一篇文章 比特幣淺析 里談到為何比特幣使用 1M block，是因為如果這個網(wǎng)絡(luò)的初衷是所有人都可以參與進來，那么，要考慮到普通用戶的帶寬承受能力。假設(shè)你的電腦費勁巴拉算出一個區(qū)塊，你要立刻將其廣播到 7 個鄰居，如果 30s 內(nèi)完成廣播，那么你需要 1.86 Mbps(1MB x 8bit x 7 peers / 30 sec)的帶寬;如果 block 是 8M，那么你需要 15 Mbps 的上行帶寬。所以，如果設(shè)計運行在 cloud 里(> 1Gbps)的分布式系統(tǒng)，可以不必太過在意帶寬，但是要做一個人人都用的起的 blockchain，起碼不要拍腦門設(shè)定 block 大小。

坑四：參與的節(jié)點是同構(gòu)的。像 bitcoin 這樣的分布式系統(tǒng)，參與的節(jié)點小到手機(錢包軟件)，大到專門開發(fā)的帶有 ASIC 或者 GPU 陣列的礦機，不一而足。它們所使用的網(wǎng)絡(luò)，從 wired，wireless 一路到 cellular，satellite。所以我們要考慮到區(qū)別如此之大，范圍如此之廣的參與者。礦機自然要獲取全部數(shù)據(jù)，但你讓手機用戶還下載 160G 的 chain，那就是強人所難。bitcoin 對此專門考慮到 blocker headers + merckle tree path + SPV 的方案，允許小型設(shè)備只需下載少量數(shù)據(jù)(幾百兆)，就可以充當錢包，驗證和自己相關(guān)的交易。這是我們需要學習的。

CAP 理論

分布式系統(tǒng)中，繞不過去的一個話題是 CAP 理論：即對于 Consistency，Availability 和 Partition tolerance，你只能保證其中兩個，而犧牲第三個。

我來簡單解釋一下：

Consistency：所有客戶端看到的同樣的數(shù)據(jù)。這里所說的 consistency，是指 atomic consistency (linearizability)。

Availability：每個客戶端任何時候都可以讀寫。

Partition tolerance：當網(wǎng)絡(luò)出現(xiàn) partition(split brain)時，系統(tǒng)仍舊可以工作。換句話說，為了能夠支持 Partition tolerance，系統(tǒng)需要能夠容忍任意多的消息的丟失。

談?wù)撘粋€系統(tǒng)是 CA，CP，還是 AP，其實是把復雜的問題過分簡化。但分類有分類的好處：它便于比較和記憶。

MongoDB 在上圖中被我歸到了 CP，這是因為寫入是缺省 safe=true，也就是犧牲了 Availability，只能寫入 master。然而，這種情況下，MongoDB 仍然難說是 Consistency 的，只有當 readConcern 設(shè)為 linearizability，才算得上 Consistency。所以，MongoDB 的 CP 屬性很勉強，不同的設(shè)置下很難將其歸屬到某一個分類中。

現(xiàn)在的分布式系統(tǒng)，其實對 CAP 三者都有考慮，只不過是優(yōu)先級的問題 —— 我更看重哪兩個，而愿意犧牲第三個?MySQL 在 master/slave 的配置下，犧牲了 partition tolerance，但我們也可以將其配置成 cluster，犧牲 Availability，才成全 Partition Tolerance。

考大家一個小問題：bitcoin 是 CA，還是 CP，還是 AP?

先寫到這里。有機會再寫本文沒有展開講的共識機制，它是分布式系統(tǒng)的基石。