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: