圖靈獎得主論文解讀：區塊鏈的「生物鐘」長啥樣？

原文標題：《區塊鏈的「生物鐘」長啥樣？》
原文來源： stakefish

「時間」是歲月更迭中的永恆話題。圍繞時間的探討一直在區塊鏈以及其他分佈式系統中進行。時間連接起進程與節點，我們也用時間的「粒度」來衡量連塊成鏈的去中心化網絡。

分佈式系統中關於時間的難題在於，不同參與者的「物理時鐘」很難達成完全一致。分佈式系統大師 Lamport 提供了去中心化的方法，將問題轉化爲時間與順序的聯繫，提出了邏輯時鐘的概念，就像爲包括區塊鏈在內的分佈式系統引入了「生物鐘」。

stakefish 編譯 Vac 分析師、ENS 開發者 Dean Eigenmann 的一篇文章，介紹 Lamport 關於時間、時鐘和順序的論述，爲大家提示理解區塊鏈和分佈式系統時間另一個角度。

關於分佈式系統的系列文章，用哪個話題開篇比較合適呢？以太坊的隱私交易協議 AZTEC？以難以掌握著稱的 Paxos 算法？這些話題還是留在以後寫。今天，我選了一個基礎話題作爲開篇：分佈式系統的時間話題。

本文解讀的是圖靈獎得主、計算機大師 Leslie Lamport 的知名論文《分佈式系統內的時間、時鐘和事件順序（Time, clocks, and the ordering of events in a distributed system）》。很久之後重讀這篇文章並提煉關鍵概念，另有一番趣味。

不熟悉 Leslie Lamport 的朋友可以大概瞭解一下，他以創造 LaTeX、TLA+、Paxos 而聞名，還論述了拜占庭將軍問題。當然還有 Lamport 時鐘（第一個邏輯時鐘），在本文中我們也將對其基本概念進行介紹。

先來看看分佈式系統的定義。Lamport 給出的定義是這樣的：

「如果一個系統內信息傳遞的延遲，與單一進程裏的事件間隔的時間相比是不能忽略不計的，則稱之爲分佈式系統。」

我喜歡這個定義，因爲其專注在發出和收取消息之間的延遲上。

明確了定義，我們開始正式介紹。

順序

爲事件排序在本地再簡單不過了。你只需在發生的時候爲每一個事件賦予一個時間戳就好了。我們能夠獲得所有事件的總體順序，也就意味着，所有事件都能夠按照特定順序排列。

但這個問題在分佈式系統的情境下就困難多了。爲什麼呢？

一切皆因分佈式系統的一個非常簡單的性質：在節點之間傳遞的消息在發出之後，在未來的任何時間點都可能到達 0 次、1 次或多次。這樣的話，分佈式系統的各個節點之間就不能就時間達成一致。舉例來說：

一個節點可以向另一個節點發送一條消息標註當前時間是 12:00:00，但是接收者不知道消息用了多長時間傳遞，也就沒辦法確認到達時是否仍爲 12:00:00。如果這樣，節點之間來來回回傳一整天消息也無法確定信息是否同步。如果不能在時間上達成一致，我們也就不能在事件順序上達成共識。

那怎麼解決這個問題？

在分佈式系統內，多個節點通過互相發送信息進行交流。節點收到信息首先確認這個信息，然後執行他的下一個事件。這樣的順序，本來就顯示了一種「因果關係」：信息必須先被髮出，才能被收到。

譯註：這種因果關係是一種時序關係，不是邏輯上的原因和結果的關係。

那麼根據因果關係就能得出順序：發消息肯定在被他被接收之前。單看 A、B 兩個事件，我們就能給出「發生在……之前（happens before）」的關係來描述順序了。

現在，無需系統物理時間概念就可以識別這種關係：如果 A 對 B 造成了因果影響，事件 A 肯定發生在事件 B 之前。因果關係讓我們確定系統中相關事件的順序，是一種偏序（partial order）。

偏序也有一個侷限性：如果不能確定相關性，我們可能不知道系統中每個事件的確切順序。因爲可能有許多事件會在整個系統內併發（concorrent），並非所有節點都知道這些事件的發生。

時鐘

不過既然我們已經有了偏序，接下來把時鐘添加到系統中，就能獲取系統中的所有事件的總序（total order）。

剛纔我們已經知道了在分佈式系統裏使用物理時鐘是不可行的，那麼我們就需要使用邏輯時鐘。邏輯時鐘本質上是一個函數，能夠給事件分配一個數字。這個數字表示事件發生的時間（從現在開始我們將把這個數字稱爲時間），與物理時間沒有任何關係。

我們假設在這個分佈式系統裏的每個節點都有一個時鐘。這個時鐘隨着在執行的事件間滴答行進，但時鐘的行進並不被視爲系統中的事件。對於系統中某個節點上發生的每個事件，邏輯時鐘都會爲該事件分配一個數字。根據這個假設，我們可以滿足以下時鐘條件：

∀a、b→⟹C b (a) <C (b)

以上表達式代表什麼意思呢？

箭頭「→」表示「發生在……之前（happened before）」，而 C 代表時鐘函數，可簡單的理解爲時間。所以要表達意思就是：對於每一個事件 a,b，如果 a 發生在 b 之前，那麼 a 的時間要小於 b 的時間。

但反推不成立，僅因爲一個事件的時間比另一個事件的時間小，並不能說這個事件發生在前，他們可以是併發的。

在上面的圖片中，我們可以看到節點α上，時間 1 和時間 2 各發生了 1 個事件；節點β在自己的時間 1 發生了 1 個事件。在節點α的時間 1 和時間 2 發生的事件，與在節點β的時間 1 發生的事件是併發的，沒有因果聯繫。

如果 a 和 b 是單個節點上的兩個事件，且 a 發生在 b 之前，則 a 的時間應該小於 b 的時間。

如果 a 是一個發送消息的節點，b 是另一收到消息的節點，那麼 a 的時間仍然應該小於 b 的時間。

節點需要在事件之間讓時鐘進行計時。如果不是，則必須將時鐘調快到比從其他節點接收到的任何消息中包含的時間更晚的時間。b 就可以在時鐘調快之後發生了。

現在好啦，我們可以使用滿足這些條件的時鐘，建立整個分佈式系統的總序啦，這裏只是簡單的根據各個事件的時鐘給出的時間來排序。

用例

最後我們設置一個狀態機來看看邏輯時鐘的用法。比如我們有一個分佈式系統，多個節點都想訪問其中的共享資源，每次只能訪問一個節點。狀態機需要滿足以下條件：

條件 1：可以訪問資源的節點必須先釋放資源，然後其他節點才能訪問他。

條件 2：對資源的請求必須按照發出請求的順序被授予訪問權。

條件 3：如果每個被授予訪問權的節點最終都釋放了資源，那麼每個請求最終都會被授權。

爲什麼不引入一箇中間協調者呢？因爲這樣的話，如果發生較早的請求卻較晚到達，就不能滿足條件 2 了；另一個原因是，我們希望採取去中心化的解決方案。

所以我們還是要構建條件，滿足這個邏輯時鐘。如何滿足條件呢？

Lamport 爲我們提供了一個去中心化解決方案。首先，我們要讓所有節點儲存一個請求隊列。其次，要滿足一些簡單的假設：

假設 1：所有消息都按發送的順序接收。

假設 2：所有消息最終都被接收。

假設 3：每個節點都可以直接向系統中的所有其他節點發送消息。

如果有更復雜的算法和協議，可以忽略以上假設。

現在我們可以定義滿足這 3 個條件的算法，並在實踐中展示時鐘的功能：

1、如果一個節點想要請求一個資源，他會用當前時間創建一個請求，將他添加到他的隊列中，並將他發送給其他每個節點。

2、所有其他節點將這個請求放入他們的隊列中併發迴響應消息。

3、釋放資源的節點發送帶有當前時間的釋放消息，並從其隊列中刪除原來的請求。

4、當節點收到釋放的消息時，他將從自己的隊列中清除相關請求。

5、當一個節點在他的隊列中有自己的排在任何其他請求之前請求時（按照時間總序），他可以自由地訪問該資源，並且他在該時間之後從所有其他節點接收到消息。

上述算法是完全由各個節點獨立執行的去中心化算法，他利用時鐘來對請求按總序進行排序，從而實現對資源的訪問和節點間的協調。

好啦，我們通過文章大概瞭解到如何使用這些邏輯時鐘對分佈式系統中的事件進行排序，並分析了分佈式系統訪問資源時確定順序的實際應用問題。歡迎大家的意見反饋，我將繼續更新更多關於分佈式系統的文章。

原文標題：Time, clocks, and order
作者：Dean Eigenmann
編譯：stakefish

原文來源：weixin.qq.com

歡迎加入律動 BlockBeats 官方社群：

Telegram 訂閱群：https://t.me/theblockbeats

Telegram 交流群：https://t.me/BlockBeats_App

Twitter 官方帳號：https://twitter.com/BlockBeatsAsia