#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 Proof 或 Merkle 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 不僅能幫助你更深入了解這些系統的運作原理，也能在設計需要資料驗證的系統時，提供一個優雅且高效的解決方案。

閱讀全文

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

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

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

• 這筆交易發生了嗎？
• 這筆交易發生在另一筆交易之前還是之後？
• 現在大家的餘額資料庫裡，最新的狀態是什麼？

如果其中一台機器認為轉帳成功了，而另一台認為失敗了，那整個系統就會陷入精神分裂般的混亂。

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

閱讀全文

#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 帶給我們最珍貴的啟發。

閱讀全文

#101 重新回顧 B-Tree: 資料庫引擎快速搜尋的基石

 B-Tree（Balanced Tree 的縮寫）是計算機科學中最具影響力的資料結構之一，特別是在資料庫系統中。其設計確保了高效的資料儲存、檢索和修改，使資料庫引擎能夠更快速地執行查詢操作。本文將探討 B-Tree 的歷史、構建方法、操作原理及其變體，提供對其在資料庫優化中作用的全面理解。

閱讀全文

#100 這是第 100 篇文章...

 這是第一百篇文章，不是學術理論文章，也不是工程技術說明，只是一個單純的生活回顧文.

這幾年的變化很大，對許多年輕人來說，看部落格應該不是件流行的事情．對我這個老人來說，用文字方式來表達想法，是一個比較嚴謹的方式，畢竟是腦筋思考過，文字修飾過的產物．除此之外，還能練習自己的中文寫作能力，讓自己的頭腦繼續保持對文字寫作的熱情．

從 2019 年開始，我的工作和生活有些改變，所以讓我沒有太多空餘時間能整理自己的腦袋來寫部落格的文章，特別是那種圖文並茂的技術說明文章．回顧來看，前面許多文章都是我用小畫家或是 Powerpoint 一個框一個箭頭去畫下來，然後再上傳到 Github 做儲存空間．這一路走來，我收到了一些讀者回應，大部份的人都是來謝謝我寫出那些文章，幫助他們了解背後的原理．非常感謝這些讀者們的回應．誠如第 0 篇文章所說的，這個部落格的目的就是希望把我走過的路，看到的事與物紀錄下來，我以前跌倒過的地方，我相信後面的人也很可能會遇到．如果我能留下一些蛛絲馬跡讓後面的人在 google 答案時能為他的工作或人生有一點啟發，我想這也是我為大家做出一點小小的貢獻.

2019 年開始，尤其嚴峻的工作挑戰和責任，再加上我收了一位小徒弟，當時他是一位國中二年級的學生，擁有優於常人的數學頭腦．從那時起，我平日時間幾乎都是工作 12 小時以上，星期六下午則是小徒弟的上課時間，星期日不是家庭時間就是工作時間，所以比較少有力氣和精神來寫部落格文章了．一年半後，工作上終於有個很成功的回報，同時小徒弟也考上建中．這兩件事情是我在 2020 年最值得寫在人生記錄上的事情．

小徒弟考上建中後，仍維持每個星期六下午來上課，我差不多把我知道的資料結構，演算法等大大小小都告訴他了．我會的當然是一部份而己，為了補不足，我也特別去買了許多課外書給小徒弟自己念，然後我們再一起討論．在那過程中，其實我也學了不少．這就是最典型的，教學相長．當時本來心想要鼓勵小徒弟要不要放棄課業，全力學習寫程式去拼資訊的奧林匹克獎．但是，我後來退縮了．想想我自己也沒做過的事，要我小徒弟去拼，我可能也幫不上什麼忙．打消這種想法，重心還是放在學校功課上，寫程式就當課後興趣．同時，他班上也有幾個興趣相同的同學們，常常討論一些問題的解法以及一些特別的資料結構，在這過程中，我也跟他學習了．

去年，小徒弟在學測後考上了交大資工．他的分數排不上台大資工，而清大資工和交大資工是非常有機會的，湊巧清大交大的面試考試時間又衝突，這擺明了逼高中生只能選一間，於是我建議小徒弟選擇交大資工．後來，緣份來了，交大資工考上了，果然是全村的希望．小徒弟上了大學後，我仍會詢問課程修了什麼，內容學了些什麼．從他學習的內容中，可以看到現在資工系學的東西比我們以前那年代好很多了，尤其是在寫程式這一塊．小徒弟未來想走人工智慧的相關領域，這也可想而見．這兩年來，AI 相關題材相當熱門．其實，AI 一直都在，只不過是 ChatGPT 的出現讓 AI 這個名詞有如中樂透一夜致富的感覺，就像十年寒窗無人問，一舉成名天下知的情況．這兩年來，大大小小的 AI 模型如雨後春荀般的出現，許多相關的工具也是前後相繼的出現，也因為這些 AI 模型和相關的工具鏈的出現，讓一般不是 AI 專長的軟體工程師有機會能做出一些很有趣的 AI 應用，包括我自己也是．同時，也帶來許多新的挑戰，因為你可能已經發現了，ChatGPT 寫出來的程式碼幾乎可以輕易地打敗你寫出來的程式碼了．對軟體工程師來說，這是一個警訊，也是一個機會，就看你如何讓這些 AI 工具成為你的助手，而不是害你成為失業的人．當時，Github copilot 剛問世時，我鼓勵我所有的工程師們一定要學習如何使用它，我們不需要擔心是不是會被 AI 取代，我們要擔心的是別人都會了，而你卻不會!

回首來時路，山高無坦途．

這句話是我在許多登山界的影片裡常會聽到的一句話．人生跟登山也是類似的過程，有時上坡，有時下坡，有時陽光，有時陰雨．對大部份的人來說，生活處處充滿挑戰，因為人們心中都有個夢想，所以才願意時時接受挑戰．挑戰沒成功，這是正常的事情．無論如何，生活還是要過下去，明天還是要繼續活下去，bug 還是要解的.

而我呢? 接下來，我的工作更多了，也很難擠出時間寫更多文章．我常在想，ChatGPT 知道了很多知識，我可以把部落格的文章改成我和 ChatGPT 的對話內容，透過一問一答的方式來讓讀者了解我的思路，讓 ChatGPT 來產生簡單易懂的答案，不知道讀者們會喜歡這想法嗎 ?

閱讀全文

#99 一個特別的資料結構 K-D 樹

前陣子和團隊成員討論工作內容時，看到了一位特別的資料結構．老實說，我以前不知道這個結構，因此特別去查了資料，然後將它的內容寫在這裡．

在電腦科學中，組織數據的方式對於快速查找和使用數據至關重要。其中一種特別的數據結構稱為 K-D 樹（K-Dimension tree），主要用於在多維空間中組織點，非常適合應用於機器學習、電腦圖形和資料庫搜索等領域。現在，讓我們來看看 K-D 樹是什麼、為什麼被發明、它可以解決哪些問題，以及如何編寫 K-D 樹的程式碼。

假設你有一組在 2 維空間中的點（例如地圖上的座標），地圖是由 X, Y 軸所組成的．當你希望快速找到某個位置的最近點，K-D 樹就是一個很好的工具．K-D 樹是一種二元搜尋樹，它在具有 k 維空間中將點組織起來的能力。每一層代表一個維度，並且通過交替各個維度的分割，可以使得在空間內找到鄰近點變得更加容易。

所以, K 代表的是維度數，以地圖來說，K=2．

假設你有一組城市地標的座標，並希望快速找到離給定位置最近的地標，假設你有台北 101 的座標，要尋找附近著名的景點座標。在沒有任何其他資料結構的幫助下，每次搜尋都需要比較每一個地點，計算距離，然後依照 "附近" 的定義來決定那些景點的座標符合要求．如果一個地圖裡有成千上萬甚至數百萬個景點座標時，則尋找會非常耗時。K-D 樹就是為了解決這個問題而發明的。它的核心理念是將座標進行合理的排列，以便在搜尋時可以排除大量不相關的點。K-D 樹最早由 Jon Bentley 在 1975 年發明，並在需要快速搜尋和排序空間數據的應用中廣泛使用，例如 最近鄰搜尋（找到最近的點）。

接下來談談 K-D 樹如何建立以及如何利用它來搜尋.

1.建立過程 - 首先選擇一個維度作為 "分割" 維度。為了簡單起見，假設在 2D 空間中，所以我們有兩個維度：X 和 Y。 - 在樹的根節點上，根據 X 座標分割點。 - 找到 X 值的中位數，並將其作為 "支點" (pivot) 來劃分。把其他座標點 X 大於中位數的放在左邊，小於中位數的放在右邊。 - 接下來，在每一層上交替進行維度分割。下一層使用 Y 座標進行分割，然後再回到 x 座標，以此類推。

因此，樹的每一層就是由不同的維度來形成，以地圖為例，就是 X , Y , X , Y 以此類推，一直到把所有的資料都寫入到樹裡.

2. 尋找過程 - 若要找到最近的鄰居，將目標點與樹的每一層進行比較，根據點是更接近左子樹還是右子樹來選擇路徑。 - 當搜尋到 LEAF 節點時，檢查距離以確認它是否為目前發現的最近點。 - 通過使用樹的結構，我們不需要查看每一個點，這使得搜尋比直接比較更快。

我們將上述的想法利用程式碼來呈現時，它看起來如下:

以下是使用 KD 權的程式碼範例

K-D 樹是一種強大的資料結構，可以幫助我們在多維空間中快速找到點。通過有效組織數據，K-D 樹使得進行最近鄰搜尋和範圍搜尋變得更快。當你在地理位置相關的應用中尋找附近的選項時，K-D 樹很可能就在背後默默運作。

閱讀全文

#98 淺談機器學習

人工智慧在電腦科學的領域不是一個新主題，已經存在很長的時間．其目的是希望電腦可以做出接近人腦一樣的決策，甚至希望比人腦更好．從以前到現在曾試過了數種不同的方式，從 90 年代開始，機器學習成為了人工智慧裡主流的方式，革新了我們處理數據分析、自動化和決策的方式。這文章將討論機器學習的基礎概念，淺談其不同類型、訓練模型等．

機器學習是近二三十年來人工智慧裡流行的方法，專注於開發能夠基於數據的了解並做出預測或決策的演算法。它涉及創建模型和使用模型，這些模型可以找到模式、做出決策，並且隨著時間的推移提高其準確性。機器學習的廣泛分類可以分為 3 大類：監督學習 (supervised learning), 非監督學習 (non-supervised learning) 和半監督學習 (semi-supervised learning)。這一區分主要基於用在開發模型的訓練數據是否包含要預測的結果的答案。

在監督學習中，模型在標籤化的數據集上訓練，也就是說每一筆訓練資料都已經附上了正確答案，也就是標籤，這也代表了每一筆訓練資料都有正確輸入和輸出配對，通常來說，這是基於人類的決策來決定是否正確，所以早期的機器學習專案都需要依賴大量人力的介入來為每個數據給予正確答案，也就是標籤化的動作。模型學習從輸入數據中預測輸出答案，並且可以根據已知結果來衡量其性能。舉個例子，你要做一個能自動辦別貓或狗的程式，你收集了許多有關狗和貓的照片，假設超過了一萬張各式各樣的貓狗照片．並且每一個照片你都給出了正確答案，如第一張是貓，第二張是狗，第三張是貓等等．機器學習裡最重要的任務就是為你的程式產生出一個數學公式 (function)，公式的輸入數據就是照片, 公式的輸出結果是答案，貓或狗. 所以，機器學習就是要產生這樣的 數學公式給你的程式來使用. 我們先跳過製作數學公式的細節過程，這個數學公式的行為是從現有的一萬張照片裡 “學習” 而來的，因此，你可以想成用過去的照片，找出一個模式，然後去預測未來的照片． 因此，只要訓練時輸入的照片別太少，在預測的效果就不會太差. 預測準確率也是評估該數學公式表現好壞的重要指標，也常是用來衝量該數學公式的效果好壞. 所以，機器學習裡講的模型就是在訓練過程後產生的數學公式．因為每一張照片都搭配著正確答案，所以這種方式稱為監督學習，也就是說，每個訓練資料的輸入和輸出的關係都是由人類預先定義好．如果每張照片並沒有搭配著正確答案，這種方式則稱為非監督學習。如果訓練的數據裡有部份有標籤，而部份沒有，則這種方式稱為半監督學習。

既便你完全沒接觸過任何的機器學習演算法，單純地從上述的說明加上你對基本演算法的認識，你一定能推斷出監督學習和非監督學習是兩種完全不同的方式．監督學習的訓練資料已經有答案，所以你需要的演算法是在輸入 (照片) 和輸出 (貓狗) 之間找出關係，而非監督學習沒有答案，所以比較適合把 “類似” 的輸入聚合在一起，所謂的 "類似" 可依照功能來區別，讓人們可以很直覺地知道為何這些資料會被放一起．舉個例子，產品推薦功能，在現在許多電子商務或是影音平台網站上都會常見到這樣的功能，網站裡有許多的商品和影片，一開始沒人會知道你想買些什麼．一旦資料越來越多後，許多客戶隨著時間會建立出許多訂單，從訂單的產品裡可以整理出一套 “類似” 的規則．舉例，常買烤雞的客戶也常買牛排，常看搞笑影片的客戶比較少看知識型的影片，這些 “類似” 規則的建立就是非監督學習的成品.

從上面的說明你可以看到不論是那一種方式的機器學習方法都需要足夠多的資料，建立出來的模型也都是依照過去資料的累積而建立出來的，至少這個模型能不能拿來用在未來的預測上，這實在很難保證．舉例，貓狗照片的辦識應該沒太大問題，畢竟十年後二十年後，貓狗的長相都還是會一樣 (除非他們都成了變種貓狗了)，但同一家購物商店的商品推薦功能在十年後二十年後還能用嗎? 這沒人敢保證，畢竟商品推薦的模型是用過去數年的客戶訂單資料所建立出來的，裡面都是這些客戶的行為，如果整個社區的住戶全部都換了，你覺得你還能拿一樣的模型來用嗎 ? 答案可能可以，也可能不行．

在監督學習裡所建立出來的模型基本上都是依照你給的新輸入來算出預測的答案. 一般來說，會有兩種不同的情況，要看答案本身之間的關係．舉例，以貓狗照片辦識來說，輸入的數據是貓或狗或是其他動物的照片，模型的輸出是貓或狗或其他，答案本身是一種固定在三個值的變數，我們把這種答案稱為 “分類型” (Classification) ．舉另外一個例子，某公司下個月的銷售量預測，輸入的數據是每個月的銷售量，季節因素，經濟好壞等數據，而模型的輸出是一個預測銷售量數字，這些答案並不是固定在幾個固定值的變數，而且會隨著時間和許多其他不同因素變動時而變動的數字，我們把這種答案稱為 “回歸型” (Regression)．不同答案類型所需要的演算法或統計法也是不同的．同理也能用在非監督學習裡，答案也可分為 “群組型” (Cluster) 和 “資料探勘型” (Data mining)．其實，不論是那一種方法，都是在從你給的輸入數據裡依照你要的答案找出一個數學公式。我們要把輸入資料能 “座標化”，然後數學公式就是在這座標系統裡一個 n 維度的線或面，透過把輸入數據傳給該數學公式後就能推導出答案.

我們來用另一個例子, 假設我們得到十個病人的身高體重資料，而我們要的答案是從這些病人的資料來學習 (預測) 某一個人會不會有高血壓．假設，我們知道每一個病人有沒有高血壓，也就是說我們有答案，我們將身高體重座標化，體重是 x 軸，身高是 y 軸，呈現如下,

因為我們知道那些病人有高血壓 (紅色圈標記) ，因此，我們很容易能找一個能區分有高血壓和沒高血壓的直線或曲線. (線條的選擇或建立就是機器學習課本裡的重點．)

以上是透過 SVM 演算法所製作出來的直線，它就是一個數學公式．因此，當你有新的病人數據進入到這個直線時，我們就能知道這新病人是否有高血壓，因為只要看新輸入數據的座標是在直線的左邊或右邊就能得到答案，左邊沒有高血壓，右邊則有．以上只是一個單純的例子，真實情況下，病人的輸入參數絕對不會只有身高和體重，有意義且足夠多的參數才能幫助產生更好的預測．現在你知道機器學習模型就是在座標系統裡的一條線或是一個面．問題越複雜時，我們需要提供的參數將越多，也代表座標系統的維度越高．這些高維度的座標系統運算在數學上用矩陣來表示，方便閱讀，也方便寫程式，因此在執行機器學習專案時才會需要擅長矩陣運算的 GPU 來執行座標系統裡相關的計算.

另一種情況是我們不知道有那些病人有高血壓，這表示我們要採用非監督學習的方式. 例如，採用 K-means 並將 cluster 數量設定為 2，會得到以下的圖型，

K-means 演算法把十個病人分成兩群組, 5,6,1,7,3是一組, 9,2,8,10,4 是一種. 可想而知，這是一個失敗的數學公式，因為和真實答案相比有很高的錯誤率．在這例子裡會有這種情況是很正常的，畢竟資料太少，只有十個人，資料維度也不夠，只有身高和體重，所以很難在這麼少的數據下得到些結論. 從這個簡單的例子也可以知道有正確答案的監督學習是處在多麼有利的位置．所以，在建立機器學習模型前的資料數據整理和答案標記是對模型的建立和準確率有很大的幫助.

在監督學習和非監督學習之間存在一個灰色區域，稱為半監督學習，也就是指有部份的輸入數據有了正確答案，其中模型在部分標籤化的數據上訓練。當獲取數據的標籤昂貴或耗時時，這種方法很有用。舉個例子，當你有一萬張的動物照片時，你要建立一個機器學習模型能辦識出照片裡是那一種動物，為了讓模型得到最好的辦識結果，你希望採用監督學習方式進行，也就是要將正確答案準備好．但你可以沒有足夠的時間金錢或是其他原因導致無法將一萬張照片標示好正確答案，可能只有三千張照片能完成正確答案標示，另外七千張照片沒有正確答案．此時，可以用一個簡單的方法，將三千張有正確答案標示的照片先進行模型訓練，訓練後得到的模型用於七千張沒正確答案照片的預測，然後再將七千張照片的預測視為正確答案和三千張已有正確答案的照片再重新訓練出一個模型，半監督學習的方法有好幾種，這只是其中一種簡單好懂的．如果這個程過是循序漸進的，則模型還可以適時地改變，這樣就能漸漸地得到更好的模型，這也是所謂的增強學習 (reinforcement learning)。從這個方法延伸下去還可以有許多的理論和應用產生.

機器學習是一個動態且快速發展的領域，具有廣泛的應用範圍。理解不同類型的機器學習、如何訓練模型以及最新進展對於任何希望利用這項強大技術的人來說都至關重要。隨著機器學習繼續融入各個行業，它對社會的影響勢必增長，使其成為一個令人興奮的研究和創新領域。

閱讀全文

#97 Segment Tree

在 binary tree 的文章時曾提到從 tree 開始後的資料結構文章將會開啟另一個大門，看來許多問題可以透過 tree 結構來解決．今天要介紹的 segment tree 就是一個例子．

試想一個情況，在現實生活中一定常常會遇到一個工作，一堆資料裡面，在某一個特定範圍依照某一個資料特徵來尋找資料．例如，在公司組織結構裡，找出 A 老闆底下的員工數總和．假設你已經有了員工組織樹狀結構，第一件要做的事情便是尋找 A 老闆節點，找到 A 老闆節點後，再從這裡出發將所有子節點計算個數，便能得到答案．一旦這樣的查詢工作常常發生的話，你會發現前面說的動作並不能馬上回應答案，因為還是要對員工組織樹狀結構進行 traversal 的動作．公司員工組織樹狀結構有一個特別的特性，員工的流動率正常來說都是小的．一家正常的公司不可能每天有很大比例的人員異動．公司員工組織樹狀結構不需要常常更新，並且需要更新時，也都是小比例的更新．當問題有這樣的特性時，segment tree 便是一個很好的資料結構用來解決這問題。

首先，為了簡單起見，讓我把上面描述的問題簡化，將人名變成一個數字的 array, 然後將非 leaf 的 node 變成是將兩個小孩節點之值的總和，因此，相對應的題目就變成在這個 array 裡面某個連續的空間找出值的總和。這個過程是一個特別的 reduction，專為這個題目做的一個轉換。

Segment tree 是一種 binary tree，它的 leaf node 就是 array element 的值，如下圖，

將它製做成 segment tree，其長相如下，

在中間節點的值就是底下兩個小孩節點的值總和。所以，在上圖中最左邊的 leaf node 是14 和15，他們的上一層節點就是14+15=29，依此類推。同時，在每個節點裡有一個特別的資料，用橘色來表示。橘色的字串代表的是一組位置，array 的index 編號的開始編號與結束編號。例如，上面提的29節點，它的橘色字串為1-2，代表了29的值是從array element 的第一個加到第二個，依此類推。再舉個例子，當你需要第三個到第六個的值時，你只需要找到兩個節點，3-4和5-6這兩個，就可以得到答案。當這個 segment tree 變得很大時，就省下了不少 traversal 步驟，以節省時間。

當 array 的某一個 element 的值改變了時，也只需要更新這個 leaf node 往上的值，一路更新到 root 即可，並不是全部的 tree node 都要更新。

以上談的 segment tree 雖然是用數字來作為例子，但實務上是可以有許多變化的，例如，每個node 的值不一定是數字,也可以是其他種類的資料型別，只要在往上資料彙聚的過程中可以用一個不複雜的方式將下一層的資料會聚在一起寫在上一層的結果。同時，這些結果一定要對你需要的搜尋結果有意義就行了。

Hope it helps,

閱讀全文

#96 分散式系統介紹

分散式系統是我念書過程裡最喜歡的課程之一，也是以前我的研究領域．這一門課通常開設在碩博士班的課程裡，因為這門課需要不少基礎的課程，如果開在大學部的話，也一定是屬於大四選修課的內容．它的先修課程包含了作業系統, 演算法, 資料庫理論, 網路理論，網路程式設計等．它有一個兄弟課程叫分散式演算法．這兩門課蠻接近的，對我而言，分散式系統是比較以工程實作導向來討論分散式系統，而分散式演算法是以數學和演算法更嚴謹的電腦理論來談許多分散式系統裡所需要的運作細節. 我剛好都修過這兩門課，所以都清楚這兩個課程的內容．由於這個部落格的目的是將較不好懂的電腦理論用較白話易懂的方式來介紹給大家，所以在分散式系統的文章裡，不會著重在分散式演算法的內容．這是分散式系統系列文章的第一篇，所以會用一個較宏觀的角度來說明什麼是分散式系統.

在 1980 年代以前，電腦科學的理論已經發展的很快了，但實際上的 "商業化產品" 並還沒有大量地出現．然後在 80 年代開始，個人電腦漸漸地普及，並且 Internet 也開始大量地商業化．因此，從這個年代開始漸漸地有商業的分散式系統出現. 我們先簡單定義一下什麼是分散式系統． 用一個不是很精確的定義，分散式系統是由一群電腦一起互相合作然後達成一個共同目標或任務．舉個例子, email．發電子郵件對現在的你來說是幾乎每天都會做的事情．當你在電腦上打開郵件程式，編寫一封 email，寄給在其他位置的使用者．這封信件會從你的電腦傳送到你對應的 email server，然後再從你對應的 email server 一路展轉到目地端的 email server， 最後收件人打開他的郵件程式再把這封 email 下載到他的電腦上．所以, 整個電子郵件就是一種分散式系統，它需要一堆電腦，這些電腦可以連線用來傳送訊息，進而達成讓人們溝通的目的．分散式系統就是在討論這麼多電腦在彼此互相合作達成某個任務或目的時會遇到的問題以及相關的基礎知識和解決方式.

從這樣的定義你可以了解到現在的時代 (2022) 裡有許許多多的分散式系統．例如，WWW 可說是目前全世界最大的分散式系統. 還有許多 online game 也是分散式系統的一種. 像台灣人常用的 LINE 也是分散式系統的一種. 現在因為處理器能力大增加上軟體工具的進步，所以 AI 的應用可以漸漸地在生活上看見．如果那一天你發現某一個計程車行推出了自動駕駛計程車，不需要司機操作，完全由系統自行決定如何運行，從被客人呼叫，載客，到個計程車之間的行程調派等．這也是分散式系統的一種. 再舉另外一個例子，如果某一個國家或公司發展出先進的飛彈系統，這些飛彈能在發射之後，在空中彼此溝通，彼此協調目標，然後把所有的目標都命中． 不在是傳統的一個飛彈飛到一個固定的點或目標．別懷疑，這也是分散式系統的一種．

從這些例子，我相信你可以強烈地感受到什麼是分散式系統．這門學問基本上就是一種討論如何 "打群架" (多台電腦協同運作)，用一台電腦打不過 (達不成目標)，那只好找一堆電腦來一起打．要叫一台電腦做一件事，這是簡單的，但要叫一堆電腦一起做事來達成一個共同目標，這就顯的複雜許多．這也呼應了一開始所說的，分散式系統的先修科目有作業系統, 演算法, 資料庫，網路等等. 

因此，你可以知道，分散式系統是一堆電腦透過網路連線能彼此溝通進而達成一個任務．電腦不局限是電腦，也可以看成是某一個電腦程式．網路不局限於有線或無線，也不局限於區域網路或廣域網路．概念上，分散式系統的定義是可以很廣泛的．不同的任務所需要底層知識會有差別．例如，email 是一種分散式系統，不論你是用那一種電腦系統，不論你的 email 程式是用什麼語言寫的，也不論你的 email server 在世界上的什麼地方，這些都不應該是障礙．所以，為了讓某一個分散式系統能夠商業化地運行下去，必須定義許多 "標準" 好讓不同的軟體廠商可以依這些標準來產生可行的工具，這樣這個分散式系統才能成功．所以，不同分散式系統的應用就能看到不同的標準．例如, email 系統要定義出 email address 的合法格式，要定義出 email 內容的合法規格，要定義出 server 和 server 之間的溝通方式和通訊協定等，也要定義 server 和 mail client 之間的溝通方式等．從 email 系統的例子，你可以看到光是網路通信就有很多標準要完成．有許多的分散式系統不見得需要走向標準化．因為一些商業考量，有些公司喜歡有自己的應用，例如早期的 ICQ, MSN messenger, 到現在的 LINE．這類似的分散式系統是相對較封閉的分散式系統，因為是由某一家公司自己主導與開發，所以每家公司所使用的 "標準" 就不見得是一致的，各家都可能不一樣.

希望這一篇短文能幫助你了解什麼是分散式系統，下一篇文章，我們將介紹分散式系統裡會面臨到的挑戰，而整個系列文章將會圍繞在這些挑戰來介紹相關的解決方案.

閱讀全文

#95 Priority Queue 是不是 Queue ?

 在日常生活的情況中，排隊是一件很常見的事．原因是提供資源的人少，而使用資源的人多．例如，一堆人到便利商站買東西，買完後要結帳，而櫃檯人員只有一個，所以結帳得一個一個來，因此買商品的人就得排隊．在此時，如果出現一個文化水準低落的人來插隊，想必你一定會很生氣去跟對方說．在便利商店的排隊結帳來說，插隊通常不是件好事，但日常生活裡，某些特殊情況下，插隊是需要的，比如在醫院的急診室，或是馬路上遇到救護車救火車之類的，這種特殊情況，不緊急的必須先讓給緊急的．

當我們撰寫程式碼時，一般情況下我們會使用 Queue 資料結構來達成 "排隊" 的目的，然後，因應需求，如同急診室或救護車的例子，我們必須提供一個方法讓 "插隊" 可以成真．試著想一下，如果我們要用 Queue 結構的概念來達成插隊這件事，該怎麼做呢 ? 

假設我們用 Linked list 來實現 Queue 結構,

 

source: https://en.wikipedia.org/wiki/Linked_list

上面的 List 一共有三個元素，當實做 Enqueue() 時，我們可以把最新的元素加到最後面，這個動作的時間複雜度是 O(n)，n 是元素數量，當實做 Dequeue() 時，我們把前最面的元素讀取出來，然後第二個元素將變成第一個元素，時間複雜度是 O(1)．當我們要實做 "插隊" 時，我們該怎麼插隊呢 ? 首先，我們需要了解如何定義優先順序．以 List 而言，它的 index 位置就是優先順序 (Priority)，因為排在越前面會越先被 dequeue．假設我希望有一個元素能插隊在第二個位置，這表示我們得走到第二個元素，然後做插入的動作．這樣子有一個小缺點，我們必須知道每個元素的優先順序才能正確給出位置．如果我們必須先知道優先順序，這表示我們需要了解每一個元素的內容，這樣才能幫助你決定正確插入的位置是什麼．這顯然有點缺點，因為我們還得寫更多的程式碼來記錄每一個元素的意義，然後來決定該元素是重要還是不重要．

另外一個方法，我們可以將元素的內容改成兩個東西，一個是元素值和另一個是優先順序值．

上面的數字代表優先順序值，下面的數字是原來的元素值．當我們需要 Enqueue() 時，優先順序值就必須先指定．執行時間一久之後，你就會發現這方法也是有問題，因為若我們要將新元素指定到最後面，優先順序值就必須不斷新增，總有一天，這個數字將會超過 integer 的範圍．因此，用這個方法並不好，原因就在於我們必須指定優先順序值．如果我們不要指定優先順序值，同時有這樣的效果，那豈不是更好嗎 ? 此時，你就該了解到用  Queue 結構來實做並不是個好方法．

在資料結構的世界裡，有那一個結構能做到 Queue 的行為並且能定義優先順序的能力呢 ? 有的，它的名字叫 Heap，其範例如下圖所示:

source: https://en.wikipedia.org/wiki/Heap_(data_structure)

Heap 是一種特別的 Tree結構，它有一個很重要的特性，任何一個節點的值都必須大於等於或小於等於該節點以下所有的節點值．以上圖為例，這是一個大於等於的例子，意思就是每一個節點值都會比在它之下所有的節點值還要大或一樣．我們稱它為 max heap，若是小於等於，稱為 min heap．

節點值就是優先順序，只要我們能將需求面的優先順序定義清楚，就能把每一個工作 (節點) 建立 (Enqueue)  max heap，而建立的時間複雜度是 O(lg n)，其中 n 是所有節點的數量，這樣效能就比前面說的 Linked list 要來的好．取資料時 (Dequeue)，就直接將 root 取出，因為當下 root 是最大值的節點，然後再從 root 的子節點中挑出一個較大的節點做為新的 root 即可，以上圖例子而言將是 36，取出的時間複雜度是 O(1)．

使用 max/min heap 來做為具有優先順序功能的 Queue，就稱它為 Priority queue．在主要的程式語言裡 C++/Java 等的 library 都有實作 priority queue，所以讓大家可以直接用，方便許多．所以，當你需要一個有插隊功能的 queue 時，別忘了 priority queue．

閱讀全文

#94 演算法的 Backtracking 策略

 Backtracking 是一種演算法的策略，可用來解決三種面向的問題，分別是 Decision problem, Optimization problem, 以及 Enumeration problem．有關 Optimization problem 在前面的文章裡已經談過不少，這裡不多說明．一個 Decision problem 可能會有至少一個或一個以上的解答，這種問題我們通常只要找一個可用的解答．Enumeration problem 和 Optimization problem 蠻相近，就是要將所有解答找出來．舉個例子，之前講過的老鼠走迷宮是一種問題，如果我們要找一條可行的路，那麼老鼠走迷宮將是 Decision problem．如果我們要找出一條最短的路，此時便是 Optimization problem．如果要將所有可行的路找出來，這便是 Enumeration problem．不同的問題需要不同的解決策略．Backtracking 就這麼巧地可以用來做為這三種問題的解決策略．

以西洋棋裡 n-Queen 問題來說明，一般以 n = 8 為市面上較為熱門的題目，現在我們把 input size 縮小一點，將 n=4. 而棋盤和其中一個可行的解答如下:

Source: https://www.geeksforgeeks.org/backtracking-introduction/

n-Queen 問題的解決策略如果用最直覺的暴力法來做，其解法如下

1. 列出所有 Queen 的排列座標，例如

    Answer candidate 1: (0,0) (0,1) (0,2) (0,3)

    Answer candidate 2: (0,0) (0,1) (0,2) (1,3)

    Answer candidate 3: (0,0) (0,1) (0,2) (2,3)

    Answer candidate 4: (0,0) (0,1) (0,2) (3,3)

    Answer candidate 5: (0,0) (0,1) (1,2) (0,3)

    .... 以此類推， 一共有 4x4x4x4 = 256 種位置．

2. 然後將每一個候選答案放到一個檢查器．這個檢查器就是題目要求的，要讓每個皇后所在的位置不會影響到其他的皇后．這個檢查器要執行的程式碼就是問題本身所給出的限制．你我都知道，暴力法簡單粗暴，保證一定讓你能找到答案，但不保證能快速找到答案．這個問題的 "限制" 本身就是一個有點複雜的運算了．如果你忘了西洋棋的皇后走法，你需要複習一下才能知道這裡所說有點複雜運算的意思了．

如果是用 Backtracking 的策略，該怎麼做呢 ?

Backtracking 的策略在我看來和暴力法是有一點接近的．只是差別在於 Backtracking 不會一開始將所有可能列出來，然後再進行對每個輸入一一地檢查．Backtracking 的策略是在產生所有可能的排序方式過程中，就直接檢查了．如果在過程中不符合 "限制" 時，則中斷這條路，然後跳到下一組排列來做.

以上述的答案候選為例子:

一開始，第一個皇后放在 (0,0)，然後試著將第二個皇后放在 (0,1)，執行檢查器，這樣檢查器會回傳 false，因為棋盤上同一行只能有一個皇后．於是，後面答案候選裡面只要是 (0,0) (0,1) 開頭的組合便可跳過．前面兩個皇后的位置已經不合法了，所以後面的皇后也不用浪費時間檢查．若以程式的角度來看，某一層次的 for loop 將可以整個跳過去而不執行．所以，下一個要檢查的便是從 (0,0) (1,1) 開頭的答案. 

以上的過程的解題思考就是 Backtracking．

看到這裡，雖然我們沒有寫出細節的程式碼，但我相信你能感受到 Backtracking 的解題策略的精神是什麼了．Backtracking 適合用在需要 recursion 來解決的問題．在我們試著將所有的可能答案窮舉出來的過程中，就執行著 "檢查器"，一旦發現檢查器不通過，就直接跳開這一個層次的答案，直接轉往下一個層次，這就是 Backtracking 能夠省出時間的方式．上述的 n-Queen 是一個常見的例子，Sudoku 也是一個常見的例子. 我相信在你的工作中 Backtracking 能派上用場的時機點是很多的．

底下的程式碼是我小徒弟在數個月前練習解決 Sudoku 題目的程式碼，其解決策略是 Backtracking.

閱讀全文