The two most important days in your life are the day you were born and the day you find out why. -Mark Twain

#105 出神入化的用介面 第五集:Interface 與 Unit Test — 讓你的程式可以被測試

在前幾集的內容裡,我們透過寄信程式的例子說明了 Interface 如何幫助不同的團隊在不互相 "認識" 的情況下一起工作,也說明了當 Interface 需要修改時,該如何用繼承的方式讓新舊版本都能正常運作。這一集,我們繼續用同一個寄信程式的故事,但要切入一個完全不同的角度 — Unit Test。


你的程式,有辦法被測試嗎?

先問你一個問題。假設你今天寫好了第一集裡那個 SendEmail() method,你怎麼確認它有正確地執行呢?也許你會說,我執行程式,看一下信箱,如果信收到了,就代表它是對的。這個方法當然可行,但你有沒有想過,這樣的驗證方式有幾個很明顯的問題。

問題一,每次你改了 SendEmail() 裡的任何一行程式碼,你就得再跑一次整個程式,然後去信箱確認,這很麻煩。

問題二,如果你的測試信件伺服器今天不穩定或是連不上,你的測試就失敗了,但這個失敗並不是你的程式有問題,而是外部環境的問題,這樣的結果讓人很困惑。

問題三,如果你的程式有五十個 method,難道每一個都要用手動的方式去驗證嗎?

相信你在業界工作久了,應該對 Unit Test 這個詞不陌生。Unit Test 的精神就是讓每一個 method 都可以用程式碼自動驗證,讓你不需要靠手動的方式來確認程式有沒有正確執行。而 Interface,就是讓 Unit Test 變得可行的關鍵工具之一。


問題的根源 — 直接依賴 Class 讓測試變得很痛

讓我們回頭看第一集裡的寄信程式。在最原始的版本裡,SendEmail() 長這樣:

public void SendEmail(IMailContent mail)
{
    EmailServer server = new EmailServer();
    server.IP = "1.1.1.1";
    server.Username = "admin";
    server.Password = "password";
    server.Connect();
    server.Send(mail.ReceipentEmail, mail.HtmlContent, mail.Subject, mail.Importance);
    server.Close();
}

你看到第一行的 new EmailServer() 了嗎?這一行,就是讓這個 method 難以被測試的根本原因。

當 SendEmail() 裡面直接 new 出一個 EmailServer,這就代表你的程式和 EmailServer 這個 class 是緊緊綁在一起的,用業界的說法叫做 hard dependency。只要你呼叫 SendEmail(),它就一定會去嘗試連線到那台 IP 是 1.1.1.1 的 email 伺服器。如果你想寫一個 Unit Test 來驗證 SendEmail() 有沒有正確執行,你就被迫要依賴那台真實的伺服器。一旦那台伺服器不在,或是你的測試環境根本連不到那個 IP,你的 Unit Test 就永遠無法正常跑完,這樣的 Unit Test 是沒有意義的。


解法: 用 Interface 把「怎麼寄」抽離出來

從前幾集的內容,相信你已經能猜到解法的方向了。既然直接依賴 EmailServer class 是問題的根源,那麼我們就把 EmailServer 的行為抽成一個 Interface。

public interface IEmailServer
{
    void Connect(string ip, string username, string password);
    void Send(string receipent, string content, string subject, bool importance);
    void Close();
}

然後讓真正的 EmailServer 去實作這個 Interface:

public class EmailServer : IEmailServer
{
    public void Connect(string ip, string username, string password)
    {
        // 真正的連線邏輯
    }

    public void Send(string receipent, string content, string subject, bool importance)
    {
        // 真正的寄信邏輯
    }

    public void Close()
    {
        // 真正的關閉連線邏輯
    }
}

接下來,把原本的寄信程式改造一下。我們把它包成一個 class,並且讓 IEmailServer 從外面傳進來,而不是在 method 裡面直接 new:

public class EmailSender
{
    private readonly IEmailServer _server;

    public EmailSender(IEmailServer server)
    {
        _server = server;
    }

    public void SendEmail(IMailContent mail)
    {
        _server.Connect("1.1.1.1", "admin", "password");
        _server.Send(mail.ReceipentEmail, mail.HtmlContent, mail.Subject, mail.Importance);
        _server.Close();
    }
}

你有沒有注意到,EmailSender 現在完全不知道傳進來的 IEmailServer 到底是哪一個 object,它只認得 IEmailServer 這個 Interface 的長相。


做一個假的 EmailServer

因為 EmailSender 現在依賴的是 IEmailServer 而不是真正的 EmailServer,所以在寫 Unit Test 的時候,我們完全可以自己做一個假的 EmailServer object 傳進去。這個假的 object 業界通常叫做 Mock 或是 Fake。

public class FakeEmailServer : IEmailServer
{
    public bool ConnectWasCalled { get; private set; }
    public bool SendWasCalled { get; private set; }
    public string LastReceipent { get; private set; }

    public void Connect(string ip, string username, string password)
    {
        ConnectWasCalled = true;
    }

    public void Send(string receipent, string content, string subject, bool importance)
    {
        SendWasCalled = true;
        LastReceipent = receipent;
    }

    public void Close() { }
}

這個 FakeEmailServer 不會真的連線到任何伺服器,也不會真的把信寄出去。它做的事情非常簡單,就是記錄「有沒有被呼叫過」以及「傳進來的值是什麼」。也許你現在覺得這樣的 class 感覺很蠢,但等一下你就會看到它的用途。


Unit Test 實際長什麼樣子

有了 FakeEmailServer,我們就可以寫出一個完全不依賴真實伺服器的 Unit Test:

[TestMethod]
public void SendEmail_ShouldCallSendOnServer_WithCorrectReceipent()
{
    // Arrange — 準備測試所需的物件
    var fakeServer = new FakeEmailServer();
    var sender = new EmailSender(fakeServer);
    var mail = new MailContent
    {
        ReceipentEmail = "test@example.com",
        HtmlContent = "<p>Hello</p>",
        Subject = "Test Subject",
        Importance = false
    };

    // Act — 執行你要測試的動作
    sender.SendEmail(mail);

    // Assert — 驗證結果是否符合預期
    Assert.IsTrue(fakeServer.ConnectWasCalled);
    Assert.IsTrue(fakeServer.SendWasCalled);
    Assert.AreEqual("test@example.com", fakeServer.LastReceipent);
}

Unit Test 通常會分成三個階段,分別是 Arrange、Act、Assert,這三個階段在業界也常被簡稱為 AAA。Arrange 是準備測試所需的物件和資料,Act 是執行你想要測試的動作,Assert 則是驗證執行結果是否符合你的預期。

在這個例子裡,你可以看到 fakeServer 被傳進 EmailSender,當 sender.SendEmail(mail) 被呼叫後,我們透過 fakeServer 裡記錄的狀態來確認 Connect() 有被呼叫、Send() 有被呼叫,而且傳進去的收件人 email 也是正確的。整個測試過程完全不需要真實的伺服器,你在任何一台電腦上跑這個 test,結果都會是一致的。


這一集的重點

回頭看一下整個過程,其實我們做的事情並不複雜。我們把第一集的寄信程式稍微整理了一下,用 Interface 把對 EmailServer 的依賴抽離出來,然後透過建構子把 IEmailServer 從外面傳進去。光是這兩個動作,就讓原本難以測試的程式碼變成可以被自動驗證的程式碼。

記得第一集說過的一句話嗎?「一個 object 可以有多個外衣」。EmailServer 和 FakeEmailServer 都穿著 IEmailServer 這件外衣,對 EmailSender 來說,它完全看不出來傳進來的是哪一個,也不需要知道。在正式環境裡,你傳進去的是真正的 EmailServer;在測試環境裡,你傳進去的是 FakeEmailServer。程式碼一行都不用改,行為卻可以完全不同,這就是 Interface 帶給你的自由。

Interface 帶來的好處,遠遠不只是讓元件之間 decouple 而已。可測試性只是其中一個受益者,而且在實務上,這個好處往往是最直接讓你感受到程式品質提升的地方。如果你的程式裡有很多直接 new 出來的 class,不妨試著問自己一個問題:這個 class,有辦法換成 Interface 嗎?

Share:

#104 資料完整性的守護者 - 淺談 Merkle Tree

當你在使用 Git 版本控制時,當你在下載 BitTorrent 檔案時,當你在使用區塊鏈應用時,有一個默默運作的資料結構正在背後確保你拿到的資料是正確的、完整的、沒有被竄改的。這個資料結構就是 Merkle Tree,它的發明者是密碼學家 Ralph Merkle,因此也有人稱它為 Hash Tree。

Merkle Tree 要解決什麼問題?

想像你正在從網路上下載一個 10GB 的電影檔案。下載完成後,你怎麼知道這個檔案是完整的?沒有在傳輸過程中損壞?更重要的是,沒有被惡意竄改?

最直覺的做法是什麼?對,就是計算整個檔案的 hash 值,例如 SHA-256,然後跟官方公布的 hash 值比對。如果一致,就代表檔案是完整且正確的。這方法聽起來不錯,但有個致命的缺點:如果下載到一半發現檔案損壞了,你得重新下載整個 10GB 的檔案。

再進一步想,如果你是從 P2P 網路下載檔案,檔案被切成了數千個小區塊 (chunk),分別從不同的節點下載。你要怎麼確保每一個區塊都是正確的?難道要為每一個區塊都儲存一個 hash 值嗎?如果有 10,000 個區塊,你就得儲存 10,000 個 hash 值,這也是個很大的負擔。

Merkle Tree 就是為了解決這個問題而生的。它讓你能夠:

  1. 快速驗證某一小塊資料是否正確,而不需要下載或檢查整個檔案
  2. 用相對少量的 hash 值就能驗證大量的資料區塊
  3. 當資料有問題時,能快速定位出是哪一塊出了問題

Merkle Tree 的結構

Merkle Tree 本質上就是一種二元樹 (Binary Tree),但它有一個很特別的性質:每一個節點都儲存了一個 hash 值。

讓我們從最簡單的例子開始。假設你有四筆資料:A, B, C, D。

第一步:計算葉節點 (Leaf Nodes) 的 hash

  • Hash(A) = h_A
  • Hash(B) = h_B
  • Hash(C) = h_C
  • Hash(D) = h_D

第二步:兩兩配對,計算父節點的 hash

  • Hash(h_A + h_B) = h_AB
  • Hash(h_C + h_D) = h_CD

第三步:繼續往上,計算根節點 (Root) 的 hash

  • Hash(h_AB + h_CD) = h_ABCD
最終的結構會長這樣:
           h_ABCD (Root Hash)
          /                \
       h_AB                h_CD
      /    \              /    \
    h_A    h_B          h_C    h_D
     |      |            |      |
     A      B            C      D

這個最頂端的 h_ABCD 就是 Merkle Root,它代表了整棵樹的 hash 值。只要底下任何一筆資料改變了,Merkle Root 也會跟著改變。

如何建立 Merkle Tree

建立 Merkle Tree 的演算法其實很簡單,步驟如下:

  1. 準備資料區塊:將原始資料切成固定大小的區塊。如果資料總數不是 2 的次方,可以用空白資料或重複最後一個區塊來補齊。
  2. 計算葉節點 hash:對每一個資料區塊計算 hash 值,這些 hash 值就是葉節點。
  3. 向上建構:將相鄰的兩個節點配對,將它們的 hash 值串接後再做一次 hash,得到父節點的 hash 值。
  4. 重複第三步:繼續往上層建構,直到只剩下一個節點,這就是 Merkle Root。

讓我們看一個簡單的 Python 實作概念:

import hashlib

def hash_data(data):
    """計算資料的 SHA-256 hash"""
    return hashlib.sha256(data.encode()).hexdigest()

def build_merkle_tree(data_blocks):
    """建立 Merkle Tree"""
    # 第一層:葉節點
    current_level = [hash_data(block) for block in data_blocks]
    
    # 向上建構,直到剩下一個根節點
    while len(current_level) > 1:
        next_level = []
        # 兩兩配對
        for i in range(0, len(current_level), 2):
            left = current_level[i]
            # 如果是奇數個節點,最後一個自己跟自己配對
            right = current_level[i + 1] if i + 1 < len(current_level) else left
            # 計算父節點的 hash
            parent_hash = hash_data(left + right)
            next_level.append(parent_hash)
        current_level = next_level
    
    # 回傳 Merkle Root
    return current_level[0]

# 使用範例
data = ["區塊 A", "區塊 B", "區塊 C", "區塊 D"]
merkle_root = build_merkle_tree(data)
print(f"Merkle Root: {merkle_root}")

建立一棵 n 個葉節點的 Merkle Tree,時間複雜度是 O(n),因為每一個節點只需要計算一次 hash。空間複雜度也是 O(n),因為總共會有大約 2n 個節點(葉節點 n 個,內部節點約 n 個)。

Merkle Tree 的應用場景

Merkle Tree 在許多分散式系統和需要資料完整性驗證的場景中都有重要的應用。

1. P2P 檔案分享系統

在 BitTorrent 這類的 P2P 檔案分享系統中,Merkle Tree 扮演了關鍵角色。檔案被切成數千個小區塊,分散在網路上不同的節點。當你下載這些區塊時,系統會用 Merkle Tree 來驗證每一個區塊的正確性。

傳統方法需要為每個區塊儲存一個 hash 值。如果有 10,000 個區塊,你就需要儲存 10,000 個 hash(假設每個 hash 是 32 bytes,就是 320KB)。但使用 Merkle Tree,你只需要儲存一個 Merkle Root(32 bytes)以及驗證時需要的路徑 hash 值即可。

2. 分散式資料庫

在分散式資料庫系統中,不同節點上的資料需要保持一致性。Merkle Tree 可以快速比較兩個節點的資料是否相同。如果兩個節點的 Merkle Root 相同,代表它們的資料完全一致;如果不同,可以從樹的上層往下層比較,快速找出哪些資料區塊不一致,只需同步這些不一致的部分即可。

Apache Cassandra 和 DynamoDB 等 NoSQL 資料庫就使用 Merkle Tree 來進行副本之間的資料同步。

3. 區塊鏈技術

在區塊鏈中,每一個區塊都包含了許多筆交易記錄。這些交易記錄會被組織成一棵 Merkle Tree,區塊的標頭 (Header) 只需要儲存 Merkle Root 即可。這帶來兩個好處:

  • 輕量級節點 (Light Client) 只需下載區塊標頭,就能驗證某筆交易是否存在於區塊中
  • 任何一筆交易被竄改,都會導致 Merkle Root 改變,立即被發現

4. Git 版本控制系統

Git 內部使用了類似 Merkle Tree 的結構(雖然不完全相同)來追蹤檔案的變更。每一個 commit 物件都包含了一個指向檔案樹的 hash,確保了程式碼的完整性和不可竄改性。

以 P2P 檔案傳輸為例說明 Merkle Tree 運作

讓我們用一個具體的例子來看 Merkle Tree 如何在 P2P 檔案傳輸中運作。

假設 Alice 想要從 P2P 網路下載一個檔案,這個檔案被切成 8 個區塊:D0, D1, D2, D3, D4, D5, D6, D7。

步驟一:建立 Merkle Tree

                      Root
                    /      \
                H01          H23
               /  \          /  \
           H01a  H01b    H23a  H23b
           /  \   /  \    /  \   /  \
          L0  L1 L2 L3  L4  L5 L6  L7
          |   |  |  |   |   |  |   |
          D0  D1 D2 D3  D4  D5 D6  D7

檔案的提供者(種子節點)會先建立這個檔案的 Merkle Tree:


其中:

  • L0 = Hash(D0), L1 = Hash(D1), ..., L7 = Hash(D7) ← 葉節點(Leaf)
  • H01a = Hash(L0 + L1), H01b = Hash(L2 + L3), H23a = Hash(L4 + L5), H23b = Hash(L6 + L7) ← 第二層
  • H01 = Hash(H01a + H01b), H23 = Hash(H23a + H23b) ← 第三層
  • Root = Hash(H01 + H23) ← 根節點

種子節點只需要公布 Merkle Root 給所有想下載檔案的節點。

步驟二:下載資料區塊

Alice 開始從不同的節點下載檔案區塊。假設她從節點 Bob 那裡下載了區塊 D2。

步驟三:驗證資料完整性

為了驗證 D2 是否正確,Alice 需要什麼?她不需要下載所有的資料區塊,她只需要:

  1. D2 本身
  2. D2 的 "姐妹節點" L3(D3 的 hash)
  3. D2 父節點的姐妹節點 H01a
  4. 第三層的姐妹節點 H23
  5. Merkle Root(這個她早就知道了)
驗證過程如下:(驗證 D2)
                      Root (已知)
                    /      \
                H01          H23 (需要)
               /  \          
           H01a    H01b (計算)
                    /  \
                   L2   L3 (需要)
                  (計算)  
                   |   
                   D2 (下載的資料)  
  
  1. Alice 計算 L2 = Hash(D2)
  2. Bob 同時提供 L3(D3 的 hash)給 Alice
  3. Alice 計算 H01b = Hash(L2 + L3)
  4. Bob 提供 H01a 給 Alice
  5. Alice 計算 H01 = Hash(H01a + H01b)
  6. Bob 提供 H23 給 Alice
  7. Alice 計算 Root' = Hash(H01 + H23)
  8. 比較 Root' 是否等於 Root

如果 Root' == Root,代表 D2 是正確的!整個驗證過程,Alice 只需要額外接收三個 hash 值(L3、H01a 和 H23),而不需要下載其他 7 個資料區塊。

步驟四:持續下載與驗證

Alice 繼續從不同節點下載其他區塊,每次都用類似的方法驗證。如果某個區塊驗證失敗,她知道這個區塊有問題(可能損壞或被竄改),可以向其他節點重新請求這個特定的區塊,而不用重新下載整個檔案。

為什麼這個方法有效?

關鍵在於 hash 函數的特性:

  1. 確定性:相同的輸入永遠產生相同的輸出
  2. 不可逆:無法從 hash 值反推原始資料

輸入的微小改變會導致 hash 值完全不同。所以,如果 D2 被竄改了哪怕一個位元,計算出來的 L2 就會完全不同,最終計算出來的 Root' 也會不同,驗證就會失敗。

Merkle Proof:驗證的效率

在上面的例子中,為了驗證 D2,Alice 需要接收 log₂(n) 個額外的 hash 值(其中 n 是資料區塊總數)。在我們的例子中,n = 8,所以需要 log₂(8) = 3 個額外的 hash(L3, H01a, H23,加上 Root 本身已知)。

這組用來驗證某個資料區塊的 hash 值集合,稱為 Merkle ProofMerkle Path

假設每個 hash 是 32 bytes(SHA-256),那麼:

  • 傳統方法:需要儲存 8 個 hash = 256 bytes
  • Merkle Tree:只需要 3 個 hash = 96 bytes

當資料區塊數量增加時,這個優勢更加明顯:

  • 1,024 個區塊:傳統方法 32KB vs Merkle Tree 320 bytes(log₂(1024) = 10)
  • 1,048,576 個區塊:傳統方法 32MB vs Merkle Tree 640 bytes(log₂(1048576) = 20)

這就是為什麼 Merkle Tree 在大規模分散式系統中如此重要且有效率。了解 Merkle Tree 不僅能幫助你更深入了解這些系統的運作原理,也能在設計需要資料驗證的系統時,提供一個優雅且高效的解決方案。


Share:

#103 分散式系統的「開會」藝術 - 淺談共識演算法

 上一篇文章聊到了在沒有統一時鐘的分散式世界裡,如何利用 Lamport Timestamp 這樣的邏輯時鐘來替事件排出先後順序。知道了「順序」固然重要,但這只是第一步。在現實的分散式系統中,往往有一群機器需要協同工作,它們不僅要知道誰先誰後,更需要對「某件事」達成一致的看法。

想像一下,一個由五台伺服器組成的資料庫叢集。當一個使用者送出請求:「把我的帳戶餘額扣除 100 元,轉給小明」。這五台機器必須對這個操作達成共識:

  • 這筆交易發生了嗎?
  • 這筆交易發生在另一筆交易之前還是之後?
  • 現在大家的餘額資料庫裡,最新的狀態是什麼?
如果其中一台機器認為轉帳成功了,而另一台認為失敗了,那整個系統就會陷入精神分裂般的混亂。

讓一群不可靠的機器(可能會當機、網路會延遲或斷線)對某個值達成一致的過程,就是著名的「共識問題」(Consensus Problem)而解決這個問題的方法,就稱為「共識演算法」。共識演算法是分散式系統中最困難、也最迷人的主題之一。這篇文章就用最淺顯的方式來揭開它的內容。

Share:

#102 - 分散式系統的基礎建設 - 時間與順序

為什麼時間在分散式系統中如此重要

想像一下,你和三個好朋友分別在台北、台中、高雄和花蓮,你們正在用手機的群組聊天軟體討論週末要去哪裡玩。每個人都在自己的手機上打字、傳送訊息,這些訊息會透過網路送到不同地方的伺服器,再轉發給其他人。這個看似簡單的聊天過程,其實就是一個「分散式系統」的例子。

在這個系統裡,時間扮演了一個至關重要的角色。當你看到聊天記錄時,你會期望訊息是「有順序的」。如果小明說「我們去墾丁好不好?」,小華回答「好啊,我贊成!」,但你的手機卻先顯示小華的回答,再顯示小明的提議,那就會讓人摸不著頭緒了。

時間問題在分散式系統中特別棘手,是因為這個世界上並沒有一個「絕對正確的時鐘」。每台電腦、每支手機、每個伺服器都有自己的時鐘,而這些時鐘可能快一點或慢一點。就像你家的掛鐘可能走得比學校的鐘快兩分鐘一樣,當你有上千台機器分散在世界各地時,要讓它們對「現在是幾點幾分」達成共識,是一件非常困難的事情。

讓我們看一個更嚴重的例子。想像你正在用網路銀行轉帳,你先在帳戶 A 存入一萬元,然後立刻從帳戶 A 轉帳五千元到帳戶 B。如果銀行系統搞錯了這兩個操作的順序,先處理轉帳再處理存款,那系統可能會以為你的帳戶沒有足夠的錢,導致轉帳失敗。更糟的是,如果系統允許你「先轉帳再存款」,那就等於讓你用了還沒存進去的錢,這在金融系統中是絕對不能發生的錯誤。

在資料庫系統中,時間的問題同樣關鍵。現代的大型網站通常會把資料複製到世界各地的多個資料中心,這樣才能讓使用者快速存取資料。當你在台北修改了一筆資料時,這個修改需要同步到美國、歐洲、日本的資料中心。如果有另一個使用者幾乎在同一時間也修改了同一筆資料,系統要如何判斷哪個修改應該被採用?如果不同地方的伺服器時鐘不一致,系統可能會做出錯誤的決定,導致資料錯亂。

除此之外,當分散式系統出現問題時,工程師需要查看各個伺服器的日誌檔案來找出原因。但如果這些日誌的時間戳記不準確,工程師可能會看到一個「不可能的」事件序列,例如系統先收到回應,然後才發送請求,這就像看一部倒著播放的電影,會讓人完全無法理解到底發生了什麼事。

所以,時間在分散式系統中之所以重要,是因為它直接影響到系統的正確性、可靠性和可維護性。沒有正確的時間概念,我們無法確保操作的順序、無法維護資料的一致性、無法進行有效的除錯。這就是為什麼,雖然時間看起來是個簡單的概念,但在分散式系統中卻是一個需要被認真對待的重大挑戰。

系統需要的是真實時間,還是順序?

在探討分散式系統的時間問題時,有一個很重要的觀念需要先釐清:系統真正需要的,究竟是「真實的時間」(例如現在是 2026 年 1 月 1 日下午三點二十分),還是只需要知道「事件的順序」(例如 A 事件發生在 B 事件之前)?這兩種需求看起來類似,但其實有著本質上的不同,而且需要用完全不同的方式來解決。

讓我們先從需要「真實時間」的情況開始談起。想像你正在開發一個股票交易系統,每天上午九點整開盤,下午一點半收盤。在這個系統中,時間不僅僅是用來排序交易的,它有著明確的「實際意義」。如果有人在早上八點五十分下單,系統必須要知道「開盤時間還沒到」,所以這筆交易要等到九點才能執行。又或者有人在下午一點三十五分想要下單,系統必須明確告訴他「市場已經收盤了」。在這種情況下,系統需要的是真實的、精確的時間,而不只是一個抽象的順序關係。

另一個需要真實時間的例子是日誌記錄和稽核。假設你的公司有一個規定,要求所有對重要資料的存取都必須被記錄下來,而且這些記錄必須保留七年。當監管單位來稽查時,他們可能會問:「在 2025 年 3 月 15 日下午兩點到四點之間,有誰存取過客戶的個人資料?」在這種情況下,系統需要能夠提供準確的時間資訊。如果你的日誌只記錄了「事件 A 發生在事件 B 之前」這樣的相對順序,而沒有記錄真實的時間,那就完全無法回答這個問題了。

金融交易也是一個對真實時間要求極高的領域。金融法規通常會規定,所有的交易都必須精確記錄到毫秒甚至微秒的層級。這不僅是為了合規性,也是為了公平性。在高頻交易的世界裡,晚了一毫秒可能就意味著錯過了一個獲利機會,或者在價格變動前來不及出場。更重要的是,當發生糾紛時,精確的時間戳記可以作為法律證據。例如,如果有人宣稱他在價格暴跌前就已經下了賣單,但交易系統顯示那筆賣單的時間戳記是在價格暴跌之後,那這個時間戳記就成為了判斷真相的關鍵證據。

然而,並不是所有的系統都需要真實的時間。在很多情況下,我們真正在意的只是「事件的順序」。讓我們回到一開始的聊天室例子。當你在看聊天記錄時,你在意的是訊息的順序是否合理,而不是每則訊息精確是在哪一秒發送的。如果小明說「我們去墾丁好不好?」,然後小華說「好啊」,接著小美說「+1」,你關心的是這三則訊息的順序,而不是它們是在下午兩點零三分十五秒、兩點零三分十八秒、還是兩點零三分二十秒發送的。事實上,就算這些訊息的發送時間只相差零點幾秒,在人類的感知中幾乎是「同時」,但我們仍然希望它們能按照正確的因果順序顯示。

版本控制系統是另一個只需要順序而不需要真實時間的例子。當你使用 Git 管理程式碼時,系統需要知道的是「哪個版本是基於哪個版本修改的」。假設你從版本 A 創建了一個分支,做了一些修改形成版本 B,然後又做了更多修改形成版本 C。在這個過程中,重要的是 A→B→C 這個順序關係,而不是每個版本精確是在什麼時候創建的。即使兩個版本在實際時間上只相差一秒鐘,只要我們知道哪個版本是基於哪個版本,就能正確地進行合併和衝突解決。

資料庫的因果一致性也是一個很好的例子。假設你在社群媒體上發了一則貼文,然後有人留言,接著又有人回覆那則留言。這裡有一個清楚的因果鏈:貼文必須先存在,才能有留言;留言必須先存在,才能有回覆。資料庫需要確保這個因果順序被正確維護,這樣使用者才不會看到「對一則不存在的貼文的留言」這種不合理的情況。但資料庫不需要知道貼文是在「下午三點零五分二十三秒」發布的,它只需要知道「貼文發生在留言之前」就夠了。

分散式系統中的互斥鎖(mutex)也只需要順序資訊。當多個程序想要同時存取同一個資源時,它們需要競爭一個鎖。系統需要決定「誰先取得鎖」,但這個「先」指的是邏輯上的先後順序,而不是實際時間上的先後。如果程序 A 和程序 B 幾乎同時請求鎖,可能程序 B 的請求在實際時間上早了零點零一秒,但因為網路延遲,程序 A 的請求先到達,那麼讓程序 A 先取得鎖是完全合理的。重要的是系統有一個一致的方式來判斷順序,而不是這個順序是否精確反映了「實際時間」。

這兩種需求的差異,也導致了完全不同的解決方案。當系統需要真實時間時,我們必須投資在精確的時鐘同步技術上,例如使用 GPS 衛星、原子鐘,或者像 Google 的 TrueTime 這樣的基礎設施。這些解決方案通常很昂貴,而且有其物理限制,例如光速限制了訊號傳遞的速度,所以不同地點的時鐘永遠無法做到「絕對同步」。

相反地,當系統只需要順序資訊時,我們可以用「邏輯時鐘」來解決問題。邏輯時鐘不依賴實際的物理時間,它只是一種為事件賦予順序的機制。這種方法的好處是,它完全不受物理時鐘誤差的影響。即使兩台機器的系統時鐘相差了一分鐘,邏輯時鐘仍然能正確地記錄事件的因果順序。而且邏輯時鐘的實作通常非常簡單,不需要昂貴的硬體或複雜的同步協定。

理解這個區別是非常重要的,因為它直接影響到系統的設計決策。如果你誤以為系統需要真實時間,但其實只需要順序,那你可能會花費大量的資源去建置精確的時鐘同步系統,卻發現這些投資其實是不必要的。反過來說,如果你的系統確實需要真實時間,卻只用邏輯時鐘來處理,那系統就無法滿足需求,可能會在稽核、合規或關鍵業務邏輯上出現問題。

所以,在設計分散式系統時,第一個要問的問題就是:我的系統真的需要知道「現在幾點」嗎?還是我只需要知道「誰先誰後」?回答這個問題,將會引導你走向完全不同的技術方案。

Lamport Timestamp:用邏輯建立秩序

在了解了系統有時候只需要順序而不需要真實時間之後,我們來看一個非常優雅的解決方案:Lamport Timestamp(Lamport 時間戳)。這個方法是由計算機科學家 Leslie Lamport 在 1978 年提出的,它的美妙之處在於,用一個極其簡單的機制,就解決了分散式系統中事件排序的難題。

Lamport Timestamp 要解決什麼問題?

讓我們先想像一個具體的情境。假設你正在開發一個多人協作的線上文件編輯系統,就像 Google Docs 那樣。當多個使用者同時編輯同一份文件時,每個人的修改都需要被同步到其他人那裡。假設小明在台北刪除了第三行的文字,幾乎同時,小華在高雄修改了第五行的文字。這兩個操作需要被同步到所有使用者的畫面上,但問題是:系統要如何決定這兩個操作的順序?

如果系統依賴各自電腦的時鐘,就會遇到麻煩。假設小明的電腦時鐘比標準時間快了兩秒,小華的電腦時鐘是準確的。小明在「他的時間」下午三點整進行刪除操作,小華在「他的時間」下午三點零一分進行修改操作。如果系統單純比較時間戳,會認為小明的操作發生在前。但實際上,因為小明的時鐘快了兩秒,他的操作在真實時間上可能是在下午兩點五十八分,而小華的操作是在下午三點零一分,所以小華的操作實際上晚了三分鐘。

更複雜的情況是,這兩個操作可能根本沒有因果關係。它們是兩個人在各自的電腦上獨立進行的操作,沒有誰影響誰。在這種情況下,不管以什麼順序執行,只要所有使用者看到的順序一致,系統就是正確的。Lamport 發現的關鍵洞察是:在分散式系統中,我們真正需要的不是「絕對的時間」,而是「因果關係」。如果事件 A 導致了事件 B(例如,小明發送了一則訊息,小華收到後回覆),那麼系統必須確保 A 被排在 B 之前。但如果兩個事件沒有因果關係(例如兩個人同時在不同地方編輯文件),那麼它們的順序其實並不重要,只要所有人看到的順序一致就好。

Lamport Timestamp 的核心概念

Lamport 提出了一個叫做「發生在之前」(happens-before)的關係。這個關係用符號「→」來表示,讀作「A 發生在 B 之前」。這個關係有三個簡單的規則:

第一個規則是關於同一個程序內的事件。如果在同一台電腦、同一個程式裡,事件 A 在事件 B 之前執行,那麼 A→B。這是最直觀的規則,就像你先打開一個檔案,再編輯它,「打開」一定發生在「編輯」之前。

第二個規則是關於訊息傳遞。如果事件 A 是「發送一則訊息」,事件 B 是「接收這則訊息」,那麼 A→B。這也很直觀,你不可能在訊息被發送之前就收到它。這個規則建立了不同程序之間的因果關係。

第三個規則是遞移性。如果 A→B,而且 B→C,那麼 A→C。就像如果你知道小明比小華高,小華比小美高,那麼你就可以推論出小明比小美高。

如果兩個事件之間沒有 happens-before 關係,那麼它們就是「並發的」(concurrent)。注意,這裡的並發不一定表示它們在實際時間上同時發生,而是表示它們之間沒有因果關係,系統無法判斷誰先誰後。

Lamport Timestamp 的運作方式

有了 happens-before 的概念之後,Lamport 設計了一個非常簡單的演算法來給每個事件分配一個時間戳,而且這個時間戳能夠反映 happens-before 關係。這個演算法的規則簡單到令人驚訝:

每個程序維護一個本地的計數器,我們稱它為 C。這個計數器一開始是 0。每當這個程序要執行任何事件(不管是本地的計算、發送訊息、還是接收訊息),它都會先把計數器加 1,然後用新的計數器值作為這個事件的時間戳。

當程序發送訊息時,它會把當前的時間戳附加在訊息裡一起發送出去。當另一個程序接收到這則訊息時,它會看到訊息裡的時間戳,然後把自己的計數器更新為「自己的計數器」和「訊息的時間戳」中較大的那個,再加 1。

為什麼要取較大值再加 1 呢?這是為了確保接收訊息的時間戳一定大於發送訊息的時間戳,從而維持因果順序。讓我們用一個例子來說明。

假設有兩個程序 P1 和 P2。一開始,P1 的計數器是 0,P2 的計數器也是 0。P1 執行了一個本地事件,它把計數器加 1,所以這個事件的時間戳是 1。接著 P1 又執行了一個本地事件,計數器變成 2,時間戳是 2。然後 P1 發送一則訊息給 P2,發送前先把計數器加 1 變成 3,所以這則訊息帶著時間戳 3。

在 P2 這邊,它在收到訊息之前,自己的計數器還是 0。當它收到帶著時間戳 3 的訊息時,它會計算 max(0, 3) + 1 = 4,所以接收這則訊息的事件時間戳是 4。如果 P2 接下來執行一個本地事件,計數器會變成 5,時間戳就是 5。

這個機制保證了一個重要的性質:如果事件 A 發生在事件 B 之前(根據 happens-before 關係),那麼 A 的時間戳一定小於 B 的時間戳。在我們的例子中,P1 發送訊息(時間戳 3)確實發生在 P2 接收訊息(時間戳 4)之前,而 3 < 4,符合我們的期望。

用程式碼理解 Lamport Timestamp

讓我們用一段簡單的 Python 程式碼來實作 Lamport Timestamp,這樣能更具體地理解它的運作方式:

class LamportClock:
    def __init__(self, process_id):
        """初始化 Lamport 時鐘
        
        參數:
            process_id: 程序的識別編號,用於辨識是哪個程序
        """
        self.time = 0  # 本地時間戳計數器
        self.process_id = process_id
    
    def local_event(self):
        """處理本地事件(例如執行計算、修改資料)
        
        回傳:
            這個事件的時間戳
        """
        self.time += 1
        print(f"程序 {self.process_id}: 本地事件,時間戳 = {self.time}")
        return self.time
    
    def send_message(self, message_content):
        """發送訊息給其他程序
        
        參數:
            message_content: 訊息內容
            
        回傳:
            包含訊息內容和時間戳的元組
        """
        self.time += 1
        timestamp = self.time
        print(f"程序 {self.process_id}: 發送訊息 '{message_content}',時間戳 = {timestamp}")
        return (message_content, timestamp)
    
    def receive_message(self, message_content, received_timestamp):
        """接收來自其他程序的訊息
        
        參數:
            message_content: 訊息內容
            received_timestamp: 訊息攜帶的時間戳
            
        回傳:
            接收事件的時間戳
        """
        # 這是關鍵:取兩個時間戳的最大值,再加 1
        self.time = max(self.time, received_timestamp) + 1
        print(f"程序 {self.process_id}: 接收訊息 '{message_content}',時間戳 = {self.time}")
        return self.time
現在讓我們模擬兩個程序的互動:
# 建立兩個程序的 Lamport 時鐘
process_1 = LamportClock(1)
process_2 = LamportClock(2)

# 程序 1 執行一些本地事件
process_1.local_event()  # 時間戳 = 1
process_1.local_event()  # 時間戳 = 2

# 程序 2 也執行本地事件
process_2.local_event()  # 時間戳 = 1

# 程序 1 發送訊息給程序 2
message, timestamp = process_1.send_message("你好")  # 時間戳 = 3

# 程序 2 接收訊息
process_2.receive_message(message, timestamp)  # 時間戳 = max(1, 3) + 1 = 4

# 程序 2 繼續執行本地事件
process_2.local_event()  # 時間戳 = 5
執行這段程式碼會輸出:
程序 1: 本地事件,時間戳 = 1
程序 1: 本地事件,時間戳 = 2
程序 2: 本地事件,時間戳 = 1
程序 1: 發送訊息 '你好',時間戳 = 3
程序 2: 接收訊息 '你好',時間戳 = 4
程序 2: 本地事件,時間戳 = 5

從這個輸出可以看到,程序 2 在接收訊息時,它的時間戳從 1 跳到了 4。這是因為它需要確保接收事件的時間戳(4)大於發送事件的時間戳(3),從而維持因果順序。 一個更複雜的例子 讓我們看一個更複雜但更貼近實際情況的例子。假設有三個程序在協同工作:

# 建立三個程序
p1 = LamportClock(1)
p2 = LamportClock(2)
p3 = LamportClock(3)

# P1 執行一些工作
p1.local_event()  # P1: 1
p1.local_event()  # P1: 2

# P1 發送訊息給 P2
msg1, ts1 = p1.send_message("任務資料")  # P1: 3

# P2 在收到訊息前,也在做自己的工作
p2.local_event()  # P2: 1
p2.local_event()  # P2: 2

# P2 接收 P1 的訊息
p2.receive_message(msg1, ts1)  # P2: max(2, 3) + 1 = 4

# P2 處理後,發送結果給 P3
msg2, ts2 = p2.send_message("處理結果")  # P2: 5

# P3 一直在做自己的事
p3.local_event()  # P3: 1
p3.local_event()  # P3: 2
p3.local_event()  # P3: 3
p3.local_event()  # P3: 4

# P3 接收 P2 的訊息
p3.receive_message(msg2, ts2)  # P3: max(4, 5) + 1 = 6

在這個例子中,我們可以觀察到幾個重要的現象。首先,P1 的第二個本地事件(時間戳 2)和 P2 的第二個本地事件(也是時間戳 2)雖然有相同的時間戳,但它們是並發的,因為它們之間沒有訊息傳遞,也就沒有因果關係。Lamport Timestamp 並不會試圖區分這兩個事件的先後,因為在邏輯上,它們的順序並不重要。

其次,注意 P3 在接收訊息前已經執行了四個本地事件,時間戳到了 4。但當它接收到時間戳為 5 的訊息時,它的時間戳立刻跳到 6。這確保了「P2 發送訊息」(時間戳 5)這個事件,在因果順序上一定排在「P3 接收訊息」(時間戳 6)之前。

Lamport Timestamp 的優勢與限制

Lamport Timestamp 的最大優勢就是它的簡單性。每個程序只需要維護一個整數計數器,每次執行事件時加 1,接收訊息時做一個簡單的 max 運算。不需要任何複雜的同步協定,不需要存取全域的時鐘伺服器,也完全不依賴實際的物理時間。這使得它非常容易實作,而且不會有額外的網路通訊開銷。

這個方法保證了一個很強的性質:如果事件 A 發生在事件 B 之前(根據 happens-before 關係),那麼 A 的時間戳一定小於 B 的時間戳。這個性質讓我們可以用 Lamport Timestamp 來判斷因果順序,確保系統不會違反因果律,不會出現「先看到回覆,再看到原始訊息」這種不合理的情況。

然而,Lamport Timestamp 也有一個重要的限制:它只能保證單向的推論。也就是說,如果 A 發生在 B 之前,那麼時間戳(A) < 時間戳(B);但反過來說,如果時間戳(A) < 時間戳(B),我們不能推論 A 一定發生在 B 之前,因為它們也可能是並發的。

在我們之前的例子中,P1 的第二個本地事件(時間戳 2)和 P3 的第四個本地事件(時間戳 4),雖然 2 < 4,但這兩個事件其實是並發的,它們之間沒有因果關係。Lamport Timestamp 無法告訴我們這一點。如果你的系統需要能夠判斷「兩個事件是否並發」,那麼你需要使用更進階的方法,例如向量時鐘(Vector Clock)。

儘管有這個限制,Lamport Timestamp 在很多實際應用中已經足夠了。例如在分散式資料庫中,它可以用來實作因果一致性;在分散式互斥鎖中,它可以用來決定哪個程序應該先獲得鎖;在版本控制系統中,它可以用來追蹤修改的依賴關係。它的簡單性使得它成為許多系統的首選方案,而當需要更強的保證時,才會考慮使用更複雜的機制。

Lamport Timestamp 的出現,標誌著分散式系統理論的一個重要突破。它告訴我們,即使在沒有全域時鐘、沒有精確同步的情況下,我們仍然可以建立一個有序的世界。這個看似簡單的想法,影響了後來數十年的分散式系統設計,也為我們理解「時間」在分散式系統中的意義,提供了一個全新的視角。時間不再只是牆上的鐘錶指針,而是一種反映事件之間因果關係的邏輯結構。這種思維方式的轉變,正是 Lamport Timestamp 帶給我們最珍貴的啟發。

Share: