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

#108 出神入化的用介面 第六集:Interface 與 Dependency Injection

第二集的內容中,我們用了一個極為簡化的例子來說明物件如何在大型軟體系統中移動.當時的做法是在 CommonLibrary 裡放了一個 static 的 Dictionary,讓各元件把自己實做好的物件「存」進去,其他元件再從這個 Dictionary 裡「取」出來使用.透過這樣的方式,ClassLibrary1 和 ClassLibrary2 彼此不需要互相認識 (不需要加 reference),就能使用對方所提供的功能.

這個做法雖然簡單好懂,但如果你在實際的專案中也這樣做的話,隨著系統越來越大,你會發現幾個問題:

第一,你必須自己管理這個 Dictionary,包括什麼時候該把物件放進去,key 要用什麼字串,以及取出來的時候要記得做型別轉換.第二,每個團隊都必須知道這個 Dictionary 的存在,並且要遵守一些潛規則,例如 key 不能重複,放入的順序不能搞錯等等.第三,當物件之間的相依關係越來越複雜時,手動管理這些註冊和取用的程式碼會變得相當繁瑣且容易出錯.

那麼,有沒有什麼方法可以把這些手動管理的工作交給別人來做呢?答案就是這一集要談的主題:Dependency Injection (DI).

先回顧第二集的做法

在第二集裡,CommonLibrary 提供了一個 ObjectContainer,裡面有一個 Dictionary 來儲存各元件的物件:

public class ObjectContainer
{
    public static Dictionary<string, IOperation> Operations = new Dictionary<string, IOperation>();
    public static Dictionary<string, Form> Dialogs = new Dictionary<string, Form>();
}

然後各元件在啟動時把自己的物件註冊進去:

// ClassLibrary2 的註冊
public static class Starter
{
    public static void Register()
    {
        ObjectContainer.Operations["operation2"] = new Operation2();
        ObjectContainer.Dialogs["library2"] = new Lib2WinForm1();
    }
}

最後在 WindowsFormsApp1 啟動的時候呼叫各元件的註冊方法:

static void Main()
{
    ClassLibrary1.Starter.Register();
    ClassLibrary2.Starter.Register();
    Application.Run(new Form1());
}

而 ClassLibrary1 要使用 ClassLibrary2 的功能時,就去 Dictionary 裡撈:

if (ObjectContainer.Operations.TryGetValue("operation2", out IOperation op))
{
    int result = op.AddIntOperation(5);
}

如果你仔細看這整個流程,你會發現它其實做了三件事情:第一,定義一份 interface 作為雙方的合約 (contract);第二,提供一個容器 (Dictionary) 來存放物件;第三,在程式啟動時把物件註冊到容器裡.這三件事情就是 Dependency Injection Container 的核心概念.換句話說,第二集的做法就是一個最原始的、手動版的 DI Container.

什麼是 Dependency Injection

Dependency Injection 這個名字聽起來很嚇人,但其實概念非常簡單.所謂的 "Dependency" 就是一個物件所依賴的其他物件.所謂的 "Injection" 就是把這個依賴的物件「注入」到需要它的地方.

舉個日常生活的例子,你去餐廳吃飯,你不需要自己跑到廚房去拿菜,服務生會把菜端到你的桌上.在這個比喻裡,菜就是你的 dependency,服務生把菜端給你就是 injection,而餐廳的出菜系統就是 DI Container.你只需要告訴服務生你要什麼菜 (透過菜單,也就是 interface),至於這道菜是哪個廚師做的、用什麼鍋子、幾點開始煮的,你完全不需要知道.

回到程式的世界,在第二集的做法裡,ClassLibrary1 要使用 IOperation 時,必須自己去 Dictionary 裡面找,要知道 key 是什麼,還要做型別的判斷.這就好像你去餐廳吃飯,還得自己走到廚房去翻鍋子找你點的菜一樣.而 DI 的做法則是讓框架自動把 IOperation 的實作送到 ClassLibrary1 手上,ClassLibrary1 只需要說「我需要一個 IOperation」就好了.

自己動手做一個簡單的 DI Container

在談現成的 DI 框架之前,讓我們先自己動手做一個極為簡化的 DI Container,這樣你就能完全理解它的運作原理.其實它的本質就是一個用 Type 當作 key 的 Dictionary,取代第二集裡用字串當作 key 的 Dictionary:

public class SimpleDIContainer
{
    // 用 Type 當作 key,存放的是「如何建立這個物件」的方法
    private Dictionary<Type, Func<object>> _registrations 
        = new Dictionary<Type, Func<object>>();

    // 註冊: 告訴 Container 「當有人要 TInterface 時,請建立 TImplementation」
    public void Register<TInterface, TImplementation>() 
        where TImplementation : TInterface, new()
    {
        _registrations[typeof(TInterface)] = () => new TImplementation();
    }

    // 取得: 根據 interface 的型別,自動建立並回傳對應的實作
    public TInterface Resolve<TInterface>()
    {
        if (_registrations.TryGetValue(typeof(TInterface), out var factory))
        {
            return (TInterface)factory();
        }

        throw new Exception($"Type {typeof(TInterface).Name} is not registered.");
    }
}

這個 SimpleDIContainer 做的事情和第二集的 ObjectContainer 非常相似,但有一個關鍵的不同:它用 Type 來當 key,而不是字串.這表示你不再需要記住每個物件對應的字串是什麼,也不會因為打錯字而導致找不到物件.

接著來看看怎麼用它.首先是註冊的部分:

static void Main()
{
    var container = new SimpleDIContainer();

    // 告訴 Container: 當有人需要 IOperation 時,請給他 Operation2 的實體
    container.Register<IOperation, Operation2>();

    // 取得 IOperation 的實作
    IOperation op = container.Resolve<IOperation>();
    int result = op.AddIntOperation(5);  // result = 7
}

對比一下第二集的做法:

// 第二集: 用字串當 key,手動放入和取出
ObjectContainer.Operations["operation2"] = new Operation2();
ObjectContainer.Operations.TryGetValue("operation2", out IOperation op);

// 這一集: 用 Type 當 key,透過泛型自動對應
container.Register<IOperation, Operation2>();
IOperation op = container.Resolve<IOperation>();

你可以看到,核心概念一模一樣,都是「先存再取」,只是手段從字串對應變成了型別對應,讓編譯器可以在編譯時就幫你檢查型別是否正確,不用等到執行時期才發現字串打錯.

讓 Container 自動注入到建構子

上面的 SimpleDIContainer 雖然已經比手動 Dictionary 好了一些,但使用者還是得自己呼叫 Resolve 來取得物件.真正的 DI 精神是讓 Container 自動把 dependency 注入到需要它的地方.最常見的方式就是透過建構子 (constructor) 來注入.

我們把 SimpleDIContainer 稍微加強一下,讓它能夠分析建構子的參數,並且自動注入對應的物件:

public class DIContainer
{
    private Dictionary<Type, Type> _registrations = new Dictionary<Type, Type>();

    public void Register<TInterface, TImplementation>() 
        where TImplementation : class, TInterface
    {
        _registrations[typeof(TInterface)] = typeof(TImplementation);
    }

    public T Resolve<T>()
    {
        return (T)Resolve(typeof(T));
    }

    private object Resolve(Type type)
    {
        // 如果有註冊,就找到對應的實作型別
        if (_registrations.TryGetValue(type, out Type implementationType))
        {
            return CreateInstance(implementationType);
        }

        // 如果沒有註冊但本身是可建立的類別,也嘗試建立
        if (!type.IsAbstract && !type.IsInterface)
        {
            return CreateInstance(type);
        }

        throw new Exception($"Type {type.Name} is not registered.");
    }

    private object CreateInstance(Type type)
    {
        // 找到建構子
        var constructor = type.GetConstructors().First();
        
        // 取得建構子的參數型別,並且遞迴地解析每一個參數
        var parameters = constructor.GetParameters()
            .Select(p => Resolve(p.ParameterType))
            .ToArray();

        // 用解析好的參數來建立物件
        return Activator.CreateInstance(type, parameters);
    }
}

這個加強版的 Container 會做一件很重要的事:當它要建立一個物件時,它會去看這個物件的建構子需要哪些參數,然後遞迴地把每一個參數對應的物件也建立出來並且注入進去.

於是 ClassLibrary1 的程式碼可以寫成這樣:

public class Lib1WinForm1 : Form
{
    private readonly IOperation _operation;

    // Container 會自動把 IOperation 的實作注入到這個建構子
    public Lib1WinForm1(IOperation operation)
    {
        _operation = operation;
        InitializeComponent();
    }

    private void button2_Click(object sender, EventArgs e)
    {
        // 直接使用,不需要再去 Dictionary 裡面找
        int i = 5;
        richTextBox1.Text += $"int starts at {i}\n";
        i = _operation.AddIntOperation(5);
        richTextBox1.Text += $"int becomes {i} after Operation2\n";

        string s = "aBc";
        richTextBox1.Text += $"string starts as {s}\n";
        s = _operation.ChangeStringOperation(s);
        richTextBox1.Text += $"string becomes {s} after Operation2";
    }
}

注意看 Lib1WinForm1 的建構子,它宣告了一個 IOperation 的參數.當 DI Container 要建立 Lib1WinForm1 的時候,它會看到這個建構子需要一個 IOperation,於是就自動去找已經註冊好的 Operation2 來注入.這就是 "Dependency Injection" 這個名字的由來.

對比第二集的做法,ClassLibrary1 不再需要知道 Dictionary 的 key 是什麼字串,不需要做 TryGetValue,也不需要處理找不到的情況.它只需要在建構子裡說「我需要一個 IOperation」,Container 就會自動把正確的實作塞給它.這就像你在餐廳只需要看菜單點菜,不需要自己去廚房找菜一樣.

三種常見的注入方式

上面的例子是透過建構子來注入,這是最常見也是最推薦的方式,叫做 Constructor Injection.除此之外,還有另外兩種方式:

第一種是 Property Injection,就是透過設定屬性來注入:

public class Lib1WinForm1 : Form
{
    // 透過 Property 注入
    public IOperation Operation { get; set; }
}

第二種是 Method Injection,就是透過方法的參數來注入:

public class Lib1WinForm1 : Form
{
    public void DoSomething(IOperation operation)
    {
        // 透過方法參數注入
        int result = operation.AddIntOperation(5);
    }
}

在實務上,Constructor Injection 是最被推薦的方式,因為它可以確保物件在被建立的時候就已經擁有它所需要的所有 dependency,不會有遺漏的情況.而且透過建構子的參數,你可以一眼就看出這個類別依賴了哪些其他物件,程式碼的意圖很明確.

物件的生命週期

在第二集的做法中,我們把 Operation2 的實體放進 Dictionary 以後,它就一直待在那裡直到整個程式結束.但在真實的系統中,不同的物件可能需要不同的生命週期.有些物件只需要一個就夠了 (例如設定檔的管理),有些物件每次使用都需要一個新的 (例如資料庫的連線),還有些物件在同一個請求範圍內需要共用同一個實體.

一般來說,常見的 DI Container 都會提供以下三種生命週期的管理:

Singleton: 整個應用程式只會建立一個實體,所有人共用同一個.以第二集的做法來說,物件放進 Dictionary 之後就不會再變了,所以等同於 Singleton 的概念.

Transient: 每次有人要求時都建立一個全新的實體.如果你的物件有狀態,而且不同的使用者不應該共用這個狀態,就適合使用 Transient.

Scoped: 在同一個範圍內共用一個實體,離開這個範圍後就銷毀.例如在一個 Web 應用中,同一次 HTTP Request 裡面的所有程式碼共用同一個實體,下一次 Request 進來時再建立一個新的.

如果你的系統需要更細膩的生命週期控管,手動用 Dictionary 來管理就會變得很痛苦,這時候 DI Container 的價值就顯現出來了.

Interface 在 DI 中扮演的角色

從第一集到第二集再到現在,Interface 一直都是整個架構的核心.它的角色就是定義合約 (contract),讓提供服務的一方和使用服務的一方之間有一份共同的協議,而雙方不需要直接認識彼此.

在 DI 的架構中,Interface 更是不可或缺的角色.因為 DI Container 的運作原理就是:你告訴 Container「當有人要求 Interface A 的時候,請提供 Class B 的實體」.Container 就像是一個仲介,它認識所有的 interface 和實作之間的對應關係,而使用者只需要跟 Container 說他需要什麼 interface,Container 就會在 runtime 時把正確的實作注入進去.

這樣做最大的好處就是,如果有一天 ClassLibrary2 團隊決定把 Operation2 替換成 Operation2V2,只需要改一行註冊的程式碼就好:

// 原本
container.Register<IOperation, Operation2>();

// 替換成新版本,只改這一行
container.Register<IOperation, Operation2V2>();

ClassLibrary1 團隊的程式碼完全不需要改動,因為它從頭到尾只認識 IOperation 這個 interface,至於背後是誰實做的,它不知道也不需要知道.在第二集的做法中,如果要替換實作,你也需要改一行程式碼,但你還得確保 Dictionary 的 key 沒有變、其他使用這個 key 的地方也都要對應到,這些在大型系統中是容易出差錯的地方.

從手動管理到自動管理

讓我們把第二集和這一集做一個對照,你會更清楚看到兩者之間的關係:

在第二集中,CommonLibrary 提供了 ObjectContainer (一個用字串當 key 的 Dictionary),各元件在啟動時手動將自己的物件註冊到 Dictionary 裡,使用的一方再手動從 Dictionary 裡用字串取出物件來用.這整個流程中的「註冊」和「取用」都是手動完成的.

而在 DI 的做法中,DI Container 用 Type 來當 key (取代字串),各元件透過泛型方法來註冊 interface 和實作的對應關係,使用的一方只需要在建構子宣告 interface 參數,Container 就會在 runtime 自動注入正確的實作.「註冊」仍然是手動的 (你需要告訴 Container 誰對應誰),但「取用」變成自動的了.

所以本質上,DI Container 就是一個進化版的 Dictionary,它把第二集中我們手動做的事情包裝起來,讓整個流程更自動化、更不容易出錯、也更好維護.

實務上的 DI 框架

上面我們自己手寫了一個簡化版的 DI Container 來說明原理,但在實務的專案中,你不需要自己造輪子,幾乎所有主流的程式語言和框架都有提供現成的 DI Container 可以直接使用.

在 C# 的世界裡,除了框架本身內建的 DI 機制以外,也有像 Autofac、Ninject、Unity 等老牌的 DI Container 套件可以選擇,它們各自提供了更多進階的功能,如自動掃描組件來註冊、模組化的註冊、攔截器 (interceptor) 等.在 Java 的世界裡,Spring Framework 的 IoC Container 是最經典的代表,它的概念和我們今天談的完全一樣.在 Python 中也有像 dependency-injector 這類的套件.不管是哪一種語言或框架,DI 的核心精神都是一樣的:透過 interface (或抽象類別) 定義合約,讓 Container 在 runtime 自動注入正確的實作.

值得一提的是,DI 和 IoC (Inversion of Control,控制反轉) 這兩個名詞常常被放在一起談.IoC 是一個比較抽象的設計原則,意思是「把控制權交出去」.在沒有 DI 的時候,一個物件需要什麼 dependency,它就自己去 new 一個出來,控制權在物件自己手上.而用了 DI 之後,物件不再自己建立 dependency,而是由外部 (Container) 來提供,控制權就「反轉」了.所以你可以把 DI 理解為實現 IoC 原則的一種具體做法.

小結

DI Container 帶來的好處包括:不需要手動管理 key 和 Dictionary、物件的生命週期可以被統一管理、替換實作只需要改一行註冊的程式碼、以及程式碼的可測試性大幅提升 (因為你可以很容易地在測試時注入 mock 物件).

如果你還沒有在專案中使用 DI,我會建議你從小地方開始嘗試.先在一個新的小功能中試著用 DI Container 來管理物件的建立和注入,慢慢地你就會體會到它的好處,然後你再也不會想回到手動管理 Dictionary 的日子了.

Share:

#107 分散式系統的「通訊錄」— 淺談服務發現 (Service Discovery)

為什麼分散式系統需要一本「通訊錄」?

在前幾篇文章裡談論了分散式系統中的時間與順序、共識演算法,以及資料分片等重要的基礎知識。如果你跟著這系列文章一路讀過來,你應該已經能感受到,分散式系統就是一群電腦在一起合作達成目標的過程,而這個過程中有非常多需要被解決的問題。今天我們要來聊另一個看似簡單、但在實務上極其重要的事情:在一個擁有成百上千個電腦的分散式系統裡,一個電腦到底要怎麼知道它應該去找誰?

先用一個生活中的例子來了解這問題。想像你剛到一家大型企業上班,這家公司有上千名員工分佈在不同的辦公室和樓層。你的第一個任務要找到「會計部的小陳」幫你處理報帳的事情。問題是,你不知道小陳坐在哪裡,你甚至不知道會計部在哪一層樓。該怎麼辦?最直覺的方式就是翻開公司的通訊錄,上面清楚地寫著每個部門、每個人的座位位置和分機號碼。有了通訊錄,你就能快速地找到小陳,而不需要一間一間辦公室去敲門詢問。

分散式系統裡的「服務發現」(Service Discovery) 就是在做這件事情。在現代的軟體架構中,特別是所謂的微服務 (Microservices),一個大型的應用程式會被拆分成許多個小型的、獨立運行的服務。例如,一個電商網站可能會有「使用者服務」負責處理登入和帳號管理、「商品服務」負責管理商品資訊、「訂單服務」負責處理訂單、「付款服務」負責處理金流等等。這些服務各自運行在不同的機器上,它們之間需要透過網路溝通來完成一個完整的業務流程。當使用者下了一筆訂單,「訂單服務」需要去呼叫「商品服務」確認庫存,然後再去呼叫「付款服務」來扣款。

在只有少數幾台機器的時代,這件事情不難。工程師可以把每台機器的 IP 直接寫在設定檔。就好像你的手機通訊錄只有五個人,你閉著眼睛都記得每個人的號碼。但在現代的雲端環境裡,情況完全不同了。一個服務可能同時有十幾個甚至上百個實例 (Instance) 在運行,這些實例會因為自動擴展 (Auto-Scaling) 動態地增加或減少,機器 IP 位址會因此而變化。在這種情況下,如果你還把 IP 寫死在程式碼或設定檔裡,很快就會出問題,因為你通訊錄上的號碼全部都過期了。

所以,分散式系統需要一個「動態的通訊錄」,這個通訊錄能夠即時地反映系統中每個服務的最新位置和狀態。用一個簡單的圖來表示,這個動態通訊錄長這樣:

+-----------------------------------------------------------+
|                  Service Registry (通訊錄)                 |
+-----------------------------------------------------------+
|  Service Name  |  Instance          |  Status             |
|----------------|--------------------|---------------------|
|  payment       |  10.0.0.1:8080     |  healthy            |
|  payment       |  10.0.0.2:8080     |  healthy            |
|  order         |  10.0.1.1:8080     |  healthy            |
|  order         |  10.0.1.2:8080     |  unhealthy (removed)|
|  product       |  10.0.2.1:8080     |  healthy            |
+-----------------------------------------------------------+

這就是服務發現機制要解決的核心問題。

Naming 和 Discovery 是不同的事情

在深入服務發現的細節之前,有一個觀念值得先釐清:「命名」(Naming) 和「發現」(Discovery) 雖然經常被放在一起談,但它們是兩件不同的事情。

Naming 解決的是「名稱到位址的對應」。你有一個服務叫做 "order-service",Naming 機制告訴你它的 IP 位址是 192.168.1.100。這就像你知道一個人的名字,然後在通訊錄裡查到他的電話號碼。DNS 就是最典型的 Naming 機制,你輸入 www.google.com,DNS 幫你解析出對應的 IP 位址。

Discovery 解決的是更進一步的問題:「在多個候選者中,找到一個目前可用的、健康的實例」。它不只告訴你這個服務在哪裡,還告訴你目前哪些實例是活的、哪些是掛掉的、應該把請求發給誰。這就像你不只是要找到會計部小陳的分機號碼,你還需要知道小陳今天有沒有來上班、他現在是不是正在忙、如果小陳不在的話還有誰可以幫你處理。

傳統的 DNS 基本上只做 Naming 的工作。它可以告訴你一個域名對應到哪些 IP,但它不會去檢查這些 IP 後面的服務是不是還健康。像 Consul、etcd 這類工具則同時涵蓋了 Naming 和 Discovery 兩個面向,它們不僅維護名稱與位址的對應關係,還會主動監測每個實例的健康狀況,確保查詢者拿到的位址是真正可用的。理解這個區別很重要,因為它會影響你在設計系統時對工具的選擇。如果你只需要簡單的名稱解析,DNS 可能就夠了;但如果你需要動態的、有健康檢查的服務發現,你就需要更完整的解決方案。

服務發現的三個核心元素

在我們深入了解那些有名的工具之前,先來理解一個完整的服務發現機制需要那些元素。很多人一聽到服務發現,直覺就想到「服務註冊表」,覺得只要有一個中央資料庫記錄所有服務的位址就行了。但實際上,一個完整的服務發現機制至少包含三個不可或缺的元素:Service Registry(服務註冊表)、Health Model(健康模型)、以及 Resolution / Routing(解析與路由策略)。

第一個元素是 Service Registry,也就是我們的「通訊錄」本體。所有的服務在啟動時都會向它「報到」,告訴它自己的名字、IP 位址和 Port 號碼;在服務關閉時,也會向它「登出」。Service Registry 必須是高可用的,而且資料必須保持一致,否則整個服務發現就失去了意義。

第二個元素是 Health Model。光是知道「這個服務曾經在這裡註冊過」是不夠的,你還需要一個機制來持續判斷每個已註冊的實例是否仍然健康、能夠正常處理請求。Health Model 定義了什麼叫做「健康」、用什麼方式去檢查、以及多久檢查一次。

第三個元素是 Resolution / Routing。當用戶端需要呼叫某個服務時,它要如何從多個可用的實例中選擇一個?這涉及到負載平衡 (Load Balancing) 策略、路由規則,甚至是 failover(故障轉移)的邏輯。它們共同構成了一個完整的服務發現機制。只有 Registry 沒有 Health Model,你可能會把請求送給已經掛掉的實例;只有 Registry 和 Health Model 而沒有 Routing,你的用戶端就不知道該怎麼從一堆健康的實例中做出明智的選擇。

服務發現的兩種基本模式

了解了三個核心元素之後,我們來看服務發現在架構上有哪些做法。大致上,服務發現可以分成兩種基本的模式:用戶端發現 (Client-Side Discovery) 和伺服器端發現 (Server-Side Discovery)。讓我們用兩張對比圖來看它們的差異。

模式一:Client-Side Discovery(用戶端發現)


重點:Client 負責查詢 Registry、選擇 Instance、直接呼叫

模式二:Server-Side Discovery(伺服器端發現)


重點:Client 不知道 Instance 位址,由中間層負責路由,多一層 Network Hop,但 Client 邏輯簡單

用戶端發現的模式比較像是你自己查通訊錄。在這種模式下,每個想要呼叫其他服務的用戶端(也就是發起請求的那一方)會自己去查詢 Service Registry,拿到目標服務所有可用實例的位址清單,然後用戶端自己決定要呼叫清單中的哪一個實例。

聽起來好像很簡單?但在實務上,用戶端需要處理的事情遠比「查 Registry 然後挑一個」複雜得多。首先是負載平衡策略的選擇。最簡單的是 Round Robin(輪流),但這完全不考慮每個實例的實際負載狀況。好一點的做法是 Least Connections(最少連線數),把請求送給目前手上工作最少的實例;或是 Latency-Based(基於延遲),利用類似 EWMA(指數加權移動平均)的方法追蹤每個實例的回應時間,優先把請求送給回應最快的實例;又或者是 Weighted Routing(加權路由),根據每個實例的硬體規格或其他因素分配不同的權重。

常見的 Load Balancing 策略:

1. Round Robin (輪流)
   請求順序:A → B → C → A → B → C → ...
   優點:最簡單    缺點:不考慮實際負載

2. Least Connections (最少連線數)
   Instance A: 5 個連線中
   Instance B: 2 個連線中  ← 下一個請求送這裡
   Instance C: 8 個連線中
   優點:考慮負載  缺點:需追蹤連線狀態

3. Latency-Based / EWMA (基於延遲)
   Instance A: 平均回應 15ms
   Instance B: 平均回應  5ms ← 優先選擇
   Instance C: 平均回應 30ms
   優點:最佳體驗  缺點:實作複雜度高

4. Weighted Routing (加權路由)
   Instance A (8 CPU):  權重 40%
   Instance B (4 CPU):  權重 20%
   Instance C (8 CPU):  權重 40%
   優點:適應異質環境  缺點:權重需手動設定

除了負載平衡以外,用戶端還需要處理 Retry(重試)邏輯:當請求失敗時,要不要自動重試?重試幾次?要不要換一個實例重試?還有 Timeout(逾時)設定:等多久算是對方沒有回應?以及 Circuit Breaker(斷路器)模式:當某個實例連續失敗太多次時,自動暫時停止對它發送請求,避免持續浪費資源在一個明顯有問題的實例上。

這些邏輯全部都要內建在用戶端的 SDK 裡面,這讓用戶端的複雜度大幅提升。如果你的系統裡有用 Java、Go、Python、Node.js 等不同語言寫的服務,每種語言都得實作一套這樣的 SDK,而且還要確保它們的行為一致。這是用戶端發現模式最大的痛點。

伺服器端發現的模式則比較像是你打電話給公司總機,告訴總機你要找會計部,然後總機幫你轉接過去。在這種模式下,用戶端不需要知道服務的具體位址,它只要把請求送到一個中間的負載平衡器或路由器 (Router),再由這個中間層去查詢 Service Registry,找到目標服務的可用實例,然後把請求轉發過去。用戶端只需要知道這個中間層的位址就好,其他的事情都不用操心。這種模式的好處是用戶端非常單純,不需要內建任何發現邏輯。缺點是多了一個中間層,增加了一次跳轉,而且這個中間層本身也可能成為系統的瓶頸或單點故障 (Single Point of Failure),所以中間層自己也得做到高可用 (High Availability)。

不論採用那一種模式,負載平衡和服務發現是強耦合的。你選擇了什麼樣的服務發現模式,就在很大程度上決定了負載平衡的邏輯要放在哪裡、由誰來執行。這兩者必須被放在一起考慮。

etcd:Kubernetes 背後的功臣

如果你有接觸過容器化 (Containerization) 和容器編排 (Container Orchestration) 的技術,你一定聽過 Kubernetes(k8s)。Kubernetes 是目前業界最主流的容器編排平台,而在 Kubernetes 的核心裡,負責儲存所有叢集狀態和設定資料的元件,就是 etcd。

etcd 是一個分散式的鍵值儲存系統 (Distributed Key-Value Store)。你可以把它想像成一個功能非常強大、而且高度可靠的字典。你給它一個 key(鍵),它就回傳對應的 value(值)。例如,你可以存入 key 是 "/services/payment/instance1",value 是 "192.168.1.100:8080",這樣其他服務就能透過查詢這個 key 來找到付款服務的第一個實例的位址。

etcd 最重要的特點,也是它與一般的鍵值儲存系統最大的不同之處,就在於它使用了 Raft 共識演算法來保證資料的一致性和高可用性。如果你還記得「分散式系統的開會藝術 — 淺談共識演算法」那篇文章裡介紹的 Raft 演算法,你就能很容易地理解 etcd 的運作方式。讓我們用一張圖來回顧 Raft 在 etcd 裡的運作:


重點:寫入只能透過 Leader,超過半數 (Quorum) 確認即算成功,5 台掛 2 台仍可運作 (3 > 5/2)

etcd 叢集通常由奇數台機器組成(例如三台或五台),其中一台會被選為 Leader(領導者),所有的寫入操作都必須經過 Leader。當 Leader 收到一個寫入請求時,它會先把這個操作寫入自己的日誌,然後將日誌複製給其他的 Follower(跟隨者)。只要超過半數的節點確認收到了這筆日誌,這個寫入操作就被視為成功。

這種機制讓 etcd 能夠容忍一定數量的節點故障。一個五台機器的 etcd 叢集,即使有兩台機器同時掛掉,剩下的三台仍然能正常運作,因為三台已經超過了五台的一半。這正是我們之前文章裡提到的 Quorum(多數決)的概念。所以你可以看到,我們之前介紹的共識演算法並不是紙上談兵的理論,它是真真切切被使用在每天支撐著全世界無數服務運行的基礎設施裡。

除了基本的讀寫操作以外,etcd 還提供了一個非常實用的功能叫做 Watch。你可以對某個 key 或某個 key 的前綴路徑設定 Watch,當這個 key 的值發生變化時(例如有新的服務實例註冊進來,或者某個實例被移除了),etcd 會主動通知你。這個功能對於服務發現來說非常重要,因為用戶端不需要每隔幾秒就去輪詢 (Polling) 一次來檢查有沒有變化,它只要設定好 Watch,然後等著接收通知就好。這大幅減少了不必要的網路流量,也讓服務發現的反應速度更快。值得一提的是,etcd 的 Watch 機制底層是基於 MVCC(Multi-Version Concurrency Control,多版本並行控制)的 revision 來追蹤變更的,而不是單純的事件通知,這使得即使用戶端暫時斷線重連,也能從上次的 revision 繼續接收後續的變更,不會遺漏任何更新。

在 Kubernetes 裡,etcd 扮演的角色不僅僅是服務發現。所有關於叢集的資訊都存放在 etcd 裡面,包括有哪些節點、每個節點上運行了什麼容器、目前系統的期望狀態是什麼等等。你可以說 etcd 就是整個 Kubernetes 叢集的大腦和記憶體。沒有 etcd,Kubernetes 就什麼都不知道了。

Consul:功能全面的服務發現方案

如果說 etcd 是一把精緻的瑞士刀,Consul 就比較像是一個完整的工具箱。Consul 是由 HashiCorp 公司開發的,它不僅僅是一個分散式鍵值儲存,它從一開始就是專門為了服務發現和服務管理而設計的。

Consul 在內部也使用了 Raft 共識演算法來保證 Server 節點之間的資料一致性。你可以看到,Raft 演算法在現代分散式系統中的應用有多麼廣泛。Consul 的架構分成 Server 和 Client(或稱為 Agent)兩種角色:

                      Consul 架構

         +---------------------------------------+
         |        Server Cluster (Raft)          |
         |  +--------+ +--------+ +--------+     |
         |  |Server 1| |Server 2| |Server 3|     |
         |  |(Leader)| |(Follow)| |(Follow)|     |
         |  +--------+ +--------+ +--------+     |
         +---------------------------------------+
                ▲            ▲            ▲
                |            |            |
         +------+-----+-----+-----+------+-------+
         |            |            |             |
    +---------+  +---------+  +---------+  +---------+
    | Agent   |  | Agent   |  | Agent   |  | Agent   |
    | (Node1) |  | (Node2) |  | (Node3) |  | (Node4) |
    +---------+  +---------+  +---------+  +---------+
    | Service |  | Service |  | Service |  | Service |
    |    A    |  |    B    |  |    A    |  |    C    |
    +---------+  +---------+  +---------+  +---------+
         ↕            ↕            ↕            ↕
    Health Check  Health Check Health Check Health Check

    Agent 負責:1. 將本機服務註冊到 Server
                2. 執行本機服務的 Health Check
                3. 回報健康狀態給 Server

Server 節點負責維護叢集的狀態,使用 Raft 來達成共識;Client 節點(Agent)部署在每一台運行服務的機器上,負責將本機上的服務資訊註冊到 Server,同時也負責執行 Health Check。

除了服務發現以外,Consul 還內建了 Key-Value Store、多資料中心 (Multi-Datacenter) 支援,以及一個叫做 Consul Connect 的功能可以做服務間的加密通訊和存取控制 (Service Mesh)。如果你需要一個開箱即用、功能齊全的服務發現方案,Consul 會是一個不錯的選擇。

不過,也必須誠實地說,隨著 Kubernetes 生態系的不斷壯大,Consul 在雲原生環境中的使用比例正在下降。在 Kubernetes 的世界裡,k8s 本身已經透過內建的 Service 和 Endpoints 機制提供了基本的服務發現功能,而更進階的需求則可以透過 Service Mesh(例如 Istio 搭配 Envoy)來解決。對於已經全面擁抱 Kubernetes 的團隊來說,額外引入 Consul 可能反而增加了系統的複雜度。但在非 Kubernetes 的環境裡,或者需要跨多個資料中心的混合架構中,Consul 仍然有它獨特的價值。Consul 還提供了 DNS 介面和 HTTP API 兩種查詢方式。DNS 介面讓你可以直接用 DNS 查詢的方式來發現服務,對於一些較老舊系統的整合非常方便。而 HTTP API 則提供了更豐富的查詢功能和更多的服務詳細資訊。

Health Check:通訊錄上的號碼還能打得通嗎?

在前面談服務發現的三個核心元素時,我們提到了 Health Model 的重要性。現在讓我們更深入地來聊聊 Health Check 這件事,因為它是整個服務發現機制中最容易被低估、但也最容易出問題的環節。

想像一下,你翻開公司通訊錄,找到了會計部小陳的分機號碼,撥了過去,結果一直沒人接。可能小陳今天請假了,可能小陳被調到其他部門了,也可能小陳的電話壞了。不管是什麼原因,如果通訊錄不能即時反映出「這個號碼目前是不是能打得通」的狀態,那它的實用性就大打折扣了。

在分散式系統裡也是一樣的道理。一個服務實例即使已經向 Service Registry 報到了,也不代表它隨時都是健康的。它可能因為記憶體不足而變得極度緩慢,可能因為它依賴的資料庫掛了而無法提供服務,也可能因為程式的 Bug 而進入了一個不正常的狀態。這些情況下,服務實例的程序本身可能還在運行中(所以它不會從 Registry 上消失),但它實際上已經無法正常工作了。

Health Check 就是用來解決這個問題的。它的概念很簡單:定期地去檢查每個服務實例是否還「健康」。如果一個實例被判定為不健康,服務發現機制就會把它從可用的清單中移除,這樣其他的服務就不會再把請求發送給它,直到它恢復健康為止。讓我們用一張圖來看這個流程:

                Health Check 流程與結果

  Health Checker                     Service Instances
  (定期檢查)
       |
       |--- HTTP GET /health --->  Instance A  ---> 200 OK      ✓ healthy
       |
       |--- HTTP GET /health --->  Instance B  ---> (timeout)   ✗ unhealthy
       |
       |--- HTTP GET /health --->  Instance C  ---> 200 OK      ✓ healthy
       |
       ▼
  更新 Service Registry:
  +------------------+----------+
  | Instance         | Status   |
  |------------------|----------|
  | A (10.0.0.1)     | 可用     |
  | B (10.0.0.2)     | 已移除   |  ← 不再接收新請求
  | C (10.0.0.3)     | 可用     |
  +------------------+----------+

  其他服務查詢時,只會拿到 Instance A 和 C 的位址

常見的 Health Check 方式有幾種。第一種是 HTTP Health Check,也是最常見的方式。每個服務實例會提供一個特定的 HTTP 端點(通常是類似 /health 或 /healthz 這樣的路徑),Health Check 機制會定期對這個端點發送 HTTP GET 請求。如果回傳的狀態碼是 200(代表一切正常),就認為這個實例是健康的;如果回傳其他的錯誤碼,或者在一定時間內沒有回應,就認為它不健康。這種方式的好處是服務可以在這個端點的處理邏輯裡做一些自訂的檢查,例如檢查資料庫連線是否正常、檢查磁碟空間是否足夠等等,而不只是簡單地回傳「我還活著」。第二種是 TCP Health Check。這種方式更為單純,它只是嘗試與服務實例建立一個 TCP 連線。如果連線成功,就認為實例是健康的;如果連線失敗,就認為它不健康。這種方式適用於那些不是 HTTP 服務的情況,例如一個自定義協定的 TCP 伺服器或資料庫。第三種是 Script/Command Health Check。這種方式允許你定義一個自訂的腳本或指令,Health Check 機制會定期執行這個腳本。如果腳本的結束碼 (Exit Code) 是 0,就代表健康;非 0 就代表不健康。這種方式的彈性最大,你可以在腳本裡做任何你想做的檢查邏輯。

前面提到的 Consul 在 Health Check 方面做得特別出色,它原生就支援了上述所有的 Health Check 方式,而且這些 Health Check 是由部署在每台機器上的 Consul Agent 來執行的。這意味著 Health Check 的流量是分散的,不會集中在某一台機器上造成瓶頸。當 Agent 偵測到本機上的某個服務實例不健康時,它會立即通知 Consul Server,Server 會更新 Service Registry,其他查詢這個服務的用戶端就能立刻知道要避開這個不健康的實例。

Health Check 不是萬靈丹

雖然 Health Check 非常重要,但我必須提醒你一件事情:Health Check 通過,不代表服務真的「沒問題」。這個觀念非常關鍵,在實務中卻經常被忽略。

         Health Check 通過 ≠ 服務真的沒問題

  +-----------------------+-----------------------------------+
  | Health Check 能判斷   | Health Check 無法判斷              |
  |-----------------------|-----------------------------------|
  | 程序是否還在運行       | 回應延遲是否在可接受範圍 (效能)      |
  | 網路 Port 是否還在監聽 | 回傳的資料是否正確 (正確性)          |
  | 基本的依賴是否連得上   | 是否能在合理時間內完成工作 (可用性)   |
  +-----------------------+-----------------------------------+

  實際案例:
  +-----------------------------------------------------------------+
  | 訂單服務的 /health 端點回傳 200 OK                                |
  | 但底層 DB 查詢延遲從 5ms 暴增到 3000ms                            |
  | Health Check 判定:✓ healthy                                    |
  | 實際狀況:所有請求都在等待 DB 回應,使用者體驗極差                  |
  | 結果:請求堆積 → 記憶體耗盡 → 系統崩潰                             |
  +-----------------------------------------------------------------+

Health Check 不等於可用性 (Availability)。一個服務的 Health Check 端點可能每次都回傳 200 OK,但如果它處理每個請求都要花三十秒,對用戶端來說這和掛掉幾乎沒有差別。Health Check 只是告訴你「我還活著」,但「活著」和「能在合理的時間內正確地完成工作」是兩回事。

Health Check 不等於正確性 (Correctness)。一個服務可能通過了所有的健康檢查,但它回傳的資料卻是錯誤的。也許它讀到的是舊的快取資料,也許它的商業邏輯有 Bug。Health Check 不會檢查這些事情。

Health Check 不等於效能 (Performance)。讓我舉一個很實際的例子。假設你的訂單服務依賴一個資料庫,而這個資料庫因為某些原因,查詢延遲從平常的 5 毫秒暴增到了 3 秒。你的 Health Check 端點在檢查資料庫連線時,只是確認「能不能連上」,而不管連線後的回應速度。所以 Health Check 仍然回傳 200 OK,你的服務在 Service Registry 裡仍然被標記為健康。但實際上,所有打到這個服務的請求都會變得極度緩慢,用戶端會因為等待而超時,最終整個系統可能因為請求堆積而崩潰。

所以,請記住:Health Check 只是一種「最低限度的判斷」。它能幫你過濾掉那些明確已經掛掉的實例,但它無法保證通過檢查的實例就一定能正常為你服務。

不是所有的服務發現都是強一致的

在前面介紹 etcd 和 Consul 時,我們提到它們都使用了共識演算法來保證資料的一致性。這意味著當你向這些系統查詢一個服務的位址時,你能得到強一致 (Strong Consistency) 的結果:只要資料被成功寫入了,所有後續的讀取都能看到最新的值。

在實務中,並不是所有的服務發現機制都提供這種強一致性的保證。最明顯的例子就是基於 DNS 的服務發現。DNS 天生就是一個最終一致 (Eventual Consistency) 的系統。當你更新了一筆 DNS 記錄,這個更新需要一段時間才能傳播到全球所有的 DNS 伺服器。在這段傳播的時間窗口裡,不同地方的用戶端查到的結果可能不一樣,有的拿到了新的位址,有的還在看舊的位址。DNS 的 TTL(Time To Live)設定決定了這個不一致的窗口有多長。

更需要注意的是,即使你用的是像 etcd 這樣的強一致系統,用戶端這一側的快取 (Cache) 也可能導致資料過期的問題。很多用戶端 SDK 為了提升效能,會把從 Registry 查到的結果快取起來,不會每次都去 Registry 做即時查詢。這意味著即使 Registry 裡的某個實例已經被移除了,用戶端可能因為快取還沒過期而繼續把請求送給那個已經不存在的實例。

理解這一點很重要,因為它會影響你對系統行為的預期。在一個使用 DNS 做服務發現的架構裡,當你下線一台機器時,你不能期望其他服務「立刻」就不再向它發送請求。你可能需要等到 DNS TTL 過期之後,流量才會完全切換。這也是為什麼在做服務下線 (Graceful Shutdown) 時,通常需要先將服務從 Registry 移除,然後等一段時間(讓快取過期、讓正在處理的請求完成),最後才真正關閉服務程序。

現代趨勢:從 Client-Side Discovery 到 Service Mesh

在前面談用戶端發現模式時,我們提到它的一大痛點是用戶端的 SDK 需要內建大量的邏輯:服務發現、負載平衡、Retry、Timeout、Circuit Breaker 等等。而且如果系統裡有多種程式語言,每種語言都得實作一套。這個問題在微服務架構越來越普遍之後變得更加嚴重。

為了解決這個問題,近年來出現了一個重要的架構趨勢:Service Mesh(服務網格)。Service Mesh 的核心思想是把所有與網路通訊相關的邏輯(服務發現、負載平衡、Retry、加密、觀測等等)從應用程式碼中抽離出來,放到一個獨立的基礎設施層。

     演進趨勢:從 Client-Side Discovery 到 Service Mesh

     === 傳統 Client-Side Discovery ===

     +--------------------------------------------+
     | Application Code                           |
     |  +---------------------------------------+ |
     |  | 商業邏輯                               | |
     |  +---------------------------------------+ |
     |  | SDK: Discovery + LB + Retry + Timeout | |  ← 全部塞在應用程式裡
     |  |      + Circuit Breaker + ...          | |
     |  +---------------------------------------+ |
     +--------------------------------------------+

     每個語言都要實作一套 SDK,維護成本高

     === Service Mesh (Sidecar 模式) ===

     

     應用只管商業邏輯,網路通訊的一切交給 Sidecar Proxy,所有服務共用同一套基礎設施

具體的做法是,在每個服務實例旁邊部署一個叫做 Sidecar Proxy 的輕量級代理程式(最常見的就是 Envoy)。所有從這個服務發出的請求,以及所有進到這個服務的請求,都會經過這個 Sidecar Proxy。Proxy 負責處理所有的服務發現、負載平衡、Retry、Circuit Breaker 等邏輯,而應用程式本身只需要把請求發到 localhost(本機)就好,完全不需要知道目標服務在哪裡、有幾個實例、要怎麼做負載平衡。

在 Kubernetes 的生態系裡,Istio 搭配 Envoy 是目前最常見的 Service Mesh 方案。這種架構把服務發現的複雜度從應用程式(Application Layer)往下推到了基礎設施層(Infrastructure Layer),讓開發者可以專注在商業邏輯上,而不用擔心網路通訊的各種細節。這是一個從 Client-Side Discovery 走向 Infrastructure Abstraction(基礎設施抽象化)的演進過程。

限制與現實

在結束這篇文章之前,我想做一個重要的提醒。服務發現是分散式系統中不可或缺的一塊基礎建設,但它不是銀彈 (Silver Bullet),它不能解決所有的問題。

服務發現不能保證完全正確。Registry 的資料可能有短暫的過期、Health Check 可能無法偵測到所有類型的故障、用戶端的快取可能導致請求被送到已經失效的實例。服務發現不能保證即時一致。不論是 DNS 的 TTL、用戶端的快取、還是 Health Check 的間隔,都會造成系統在某些時間點上的狀態不一致。服務發現也不能保證無錯誤路由。

服務發現真正做到的事情是:在一個動態的、不斷變化的分散式環境裡,大幅降低了「找到對的服務」這件事的複雜度。它把原本需要人工維護的靜態設定,變成了自動化的動態機制;它讓系統能夠在一定程度上自動適應節點的上線和下線。但最終,你仍然需要在應用層做好防護:Retry、Timeout、Circuit Breaker、Graceful Degradation(優雅降級)。這些機制和服務發現一起配合,才能構成一個真正健壯的分散式系統。

希望這篇文章能幫助你理解服務發現的基本概念、常用工具、實務風險,以及它和我們之前談過的共識演算法之間的關聯。

Share:

#106 分散式系統的「搬家」難題 — 淺談資料分片 (Sharding)

想像一下,你開了一間很受歡迎的早餐店。一開始,只有一個廚師、一個收銀機、一本手寫的訂單記錄本,生意好好的,什麼都很順。隨著口碑越來越好,客人越來越多,有一天你發現那本訂單記錄本已經快寫滿了,翻找某一天的訂單也越來越費時,光是整理那本子就開始讓廚師頭痛。這個時候,「找一本更大的本子」也許是個辦法,但如果生意繼續成長,遲早還是會面臨一樣的問題。更根本的解法,是把訂單記錄分散到多本本子上管理。

這個比喻,幾乎完美地描述了大型系統在面對「資料量暴增」時所遭遇的難題。

在資料庫的世界裡,當一個資料庫表格的資料量成長到幾千萬甚至幾億筆,光是一台資料庫伺服器可能就撐不住了。磁碟空間不夠、記憶體放不下索引、查詢速度越來越慢,這些問題都會接踵而來。通常工程師會先嘗試「垂直擴展(vertical scaling)」,也就是換一台更強的機器,加更多的 RAM、更快的 SSD、更多的 CPU。這個方法簡單直接,而且通常有效。但硬體的規格是有上限的,而且價格往往不是線性成長,越頂規的機器,通常貴得不成比例。

當垂直擴展已經到了極限,或者成本實在太高的時候,工程師就必須考慮「水平擴展(horizontal scaling)」,也就是把資料分散到多台機器上儲存和處理。這種技術,就叫做資料分片(Sharding)(我不確定這翻譯是否適當,所以列出英文)。

Sharding 這個字的字面意思是「碎片」,在資料庫的脈絡下,我們把一張大表格切成多個小塊,每一塊就是一個 shard,每個 shard 存放在不同的機器上。概念聽起來很美好,但實作起來,「要怎麼切」這個問題,卻大有學問。

最直覺的方式:Range Sharding(範圍分片)

Range Sharding,顧名思義,就是依照某個欄位(通常是主鍵或日期)的「範圍」來切割資料。舉個例子,假設你有一個電商平台,裡面有一張「訂單」表格,主鍵是訂單編號。你可以這樣切:

  • 節點 A:存放訂單編號 1 到 1,000,000
  • 節點 B:存放訂單編號 1,000,001 到 2,000,000
  • 節點 C:存放訂單編號 2,000,001 到 3,000,000
  • 以此類推……

這種方式最大的優點是直覺易懂,而且對於「範圍查詢(range query)」非常友善。比如說你想查「2024 年 1 月份的所有訂單」,如果是用日期當分片鍵,系統馬上就知道要去哪個節點找,不需要把所有節點都掃一遍。這在資料分析、報表系統裡非常實用。

但 Range Sharding 有一個非常致命的缺點:熱點問題(hot spot)

以電商訂單為例,剛剛建立的新訂單,編號一定是最大的,所以永遠都被分配到最後一個節點。這台機器要承受所有的新寫入流量,其他機器反而閒閒沒事。這種情況下,分片非但沒有解決問題,反而製造了一個「超載的節點」,讓整個系統的瓶頸更加明顯。就像你開了四間倉庫,結果所有貨都只堆到第四間,前三間都空著,這做法只分散了資料,但沒有分散工作負擔,這並不是真正意義上的分散。

如果用時間當分片鍵,這個現象更嚴重。因為永遠是「最近的時間分片」在承擔所有的讀寫流量,舊的分片反而幾乎沒有人去動。

所以 Range Sharding 適合什麼場合呢?適合那些讀取模式是以範圍掃描為主、並且寫入流量相對均勻分佈的情境。例如地理位置(依照郵遞區號分片)、或者確定每段範圍的資料量大致平均的場合。如果你的情境不符合這些條件,就要考慮下一種方法了。

用雜湊打散資料:雜湊分片(Hash Sharding)

Hash Sharding 的出發點,就是要解決 Range Sharding 的熱點問題。它的做法很簡單:對分片鍵做一個雜湊運算(hash function),然後用結果除以節點數量取餘數,來決定這筆資料要放到哪個節點。

公式大概是這樣:

node = hash(key) mod N

其中 N 是節點的總數量。舉個例子,假設有 4 個節點(編號 0 到 3),現在要決定訂單 ID 為 12345 的資料要放哪裡:

hash(12345) = 987654321  (某個雜湊值)
987654321 mod 4 = 1
→ 放到節點 1

雜湊函數的特性是「輸入稍微不同,輸出就會差很多」,所以就算訂單編號是連續的,經過雜湊之後會散落到各個節點,不會集中在同一台機器上。這樣就有效地解決了 Range Sharding 的熱點問題。

Hash Sharding 的優點是資料分佈均勻,對於以主鍵查詢(point query)為主的情境非常有效。你知道一個使用者 ID 或一個訂單 ID,馬上就能算出它在哪台機器,查詢速度很快。

不過,天下沒有白吃的午餐。Hash Sharding 的缺點有兩個:

第一,範圍查詢效率極差。因為資料被打散了,如果你想查「所有 2024 年 1 月的訂單」,系統沒有辦法只去一台機器找,必須把所有節點都查一遍,再把結果合併起來。這種操作叫做 scatter-gather,在節點數量多的時候,效能開銷非常大。

第二,也是更棘手的問題:節點增減的時候,資料幾乎全部要搬移。這就是本文標題所說的「搬家難題」。

假設原本有 4 台節點,某天流量大增,你決定加一台,變成 5 台。那麼公式就從 mod 4 變成了 mod 5。原本 hash(key) mod 4 = 1 的資料,現在 hash(key) mod 5 可能是 2 或 3。幾乎所有資料的「預期位置」都改變了,這意味著你要把幾乎全部的資料都從原來的節點搬到新的節點。對於一個存有幾十 TB 資料的系統來說,這是一個非常痛苦、耗時,又充滿風險的過程。

更糟的是,資料搬移本身會消耗大量的網路頻寬和磁碟 I/O。在「搬家」進行的這段時間裡,這些資源都在忙著搬資料,真正來自使用者的查詢請求反而要排隊等待,造成服務延遲明顯上升。如果搬移速度太慢、持續太久,整個叢集甚至可能觸發連鎖反應,讓系統陷入更大的麻煩。這種在擴充期間特別容易發生的故障連鎖,正是分散式系統工程師最害怕遇到的「雪崩效應(cascading failure)」。

那有沒有一種方法,能夠兼顧「資料分佈均勻」又能讓「節點增減時只需要搬移少量資料」呢?

一致性雜湊:讓搬家的痛苦降到最低

一致性雜湊(Consistent Hashing) 就是為了解決這個問題而生的。這個方法的設計非常巧妙,但只要跟著例子一步一步走,你會發現它其實並不難懂。

從一個生活比喻開始:接力賽的交接區

在正式介紹技術之前,先想像一個情境。

你的班級要舉辦一個「管理公告欄」的輪值任務。班上目前有三個同學負責:小明、小華、小美,他們三個人圍成一個圓圈站好(想像成一個時鐘的圓盤)。現在老師手上有一疊佈告,每張佈告上面有一個號碼(例如 42 號、17 號、88 號……),規則是:號碼落在哪個區間,就交給站在那個區間終點的同學管理

一開始,三個人把圓圈分成三段:

0 ~ 33 號  → 小明
34 ~ 66 號 → 小華
67 ~ 99 號 → 小美

某天,班上轉來一個新同學小強,老師安排他在小華和小美之間。現在圓圈變成四段,小強負責原本屬於小美的前半段(67 ~ 82 號)。所以只有那些 67 ~ 82 號的佈告,需要從小美那裡轉交給小強。小明和小華管的佈告完全不動,小美也只需要把一部分交出去,整個「搬家」的動作非常小。

這個圓圈輪值的概念,就是一致性雜湊的核心精神。接下來我們用真正的技術語言來描述它。

把節點和資料都放到同一個「環」上

一致性雜湊的核心工具叫做「雜湊環(hash ring)」。

想像一個時鐘的圓形錶盤,但刻度不是 1 到 12,而是從 0 到 2^32 - 1(也就是 4,294,967,295)。然後把這個數字的頭尾相接,形成一個完整的環,這就是一致性雜湊的雜湊空間 [0, 2^32 - 1]。

第一步:把「節點」放上環。

對每一台伺服器節點的名稱做雜湊運算,得到一個數字,然後把這個節點「釘」在環上對應的位置。假設我們有三個節點 A、B、C,雜湊之後分別落在環上 12 點、4 點、8 點的位置(這只是示意,實際上是 0 到 2^32 之間的某個數字)。

         A(12點)
        /         \
  C(8點)       B(4點)

第二步:把「資料」放上環,並決定它的歸屬。

當一筆資料要決定要存到哪台伺服器時,對它的分片鍵做雜湊,得到一個數字,也標在環上。

接著,要決定這筆資料歸哪個節點管,規則是這樣的:

從資料的位置出發,沿著數字增大的方向前進,第一個碰到的節點,就是這筆資料的負責人。如果走到環的末端都沒碰到節點,就繞回環的起點繼續找。

換個角度來理解,其實每個節點負責的是環上的一段弧,從「上一個節點的位置(不包含)」到「自己的位置(包含)」這一段。所有落在這段弧裡的資料,都由這個節點負責。這樣想,是不是更清楚?

讓我們直接用數字來驗證。假設環的刻度是 0 到 99,節點和資料的位置如下:

節點 A 的雜湊值 = 10
節點 B 的雜湊值 = 40
節點 C 的雜湊值 = 75

資料 D1 的雜湊值 = 5
資料 D2 的雜湊值 = 15
資料 D3 的雜湊值 = 50
資料 D4 的雜湊值 = 60
資料 D5 的雜湊值 = 80

套用「每個節點負責前一個節點到自己這一段弧」的規則,先算出各節點的負責範圍:

節點 A(位置 10)→ 負責 76 ~ 10  (從 C 之後繞回來,包含 76、77、...、99、0、1、...、10)
節點 B(位置 40)→ 負責 11 ~ 40
節點 C(位置 75)→ 負責 41 ~ 75

再來看每筆資料落在哪個範圍:

  • D1(位置 5)→ 落在 76~10 這段弧 → 歸 A 管
  • D2(位置 15)→ 落在 11~40 這段弧 → 歸 B 管
  • D3(位置 50)→ 落在 41~75 這段弧 → 歸 C 管
  • D4(位置 60)→ 落在 41~75 這段弧 → 歸 C 管
  • D5(位置 80)→ 落在 76~10 這段弧(繞回起點那段)→ 歸 A 管

新增節點的時候,只需要搬一小部分

現在重點來了。假設系統需要擴充,我們加入一台新節點 X,它的雜湊值是 55,落在 B(40)和 C(75)之間。

(加入前)環上順序:... A(10) ... B(40) ... C(75) ...
(加入後)環上順序:... A(10) ... B(40) ... X(55) ... C(75) ...

現在再重新套用「從資料位置出發,找到的第一個節點」的規則,看看哪些資料的歸屬改變了:

  • D1(位置 5)→ 遇到 A(10)→ 歸 A 管。不變。
  • D2(位置 15)→ 遇到 B(40)→ 歸 B 管。不變。
  • D3(位置 50)→ 原本會遇到 C(75),但現在 X(55)插進來了,先遇到 X → 改歸 X 管!
  • D4(位置 60)→ 原本會遇到 C(75),但現在先遇到 X(55)→ 改歸 X 管!
  • D5(位置 80)→ 繞回去,遇到 A(10)→ 歸 A 管。不變。

結果只有 D3 和 D4 需要從 C 搬到 X,其他三筆資料完全待在原地不動!

相比之下,如果我們用普通的 Hash Sharding,節點從 3 台變成 4 台,幾乎每一筆資料的 hash(key) mod 3 和 hash(key) mod 4 的結果都不同,造成大量資料需要搬家。而 Consistent Hashing 的情況是:加一台新節點,只有新節點「身後那一段弧」的資料需要搬過來,大約是全部資料的 1/N(N 是節點總數)。節點越多,每次擴充需要搬的比例就越小。這就是它名字裡「一致性」的由來——節點增減時,大多數資料的歸屬「保持一致,不受影響」。

移除節點的邏輯完全對稱:如果 X 要下線,只有它負責的 D3、D4 需要轉移給 C,其他節點的資料完全不動。

虛擬節點:解決分佈不均的問題

Consistent Hashing 聽到這裡很美好,但有一個實務上很現實的問題:節點在環上分佈不均勻

假設一個特別情境,A、B、C 三個節點雜湊之後剛好都擠在環的同一側,例如全部落在 0 到 30 之間,那麼 30 到 99 這一大段弧幾乎都是 A(因為從 30 之後順時針繞一圈才會回到 A)。結果 A 要負責幾乎全部的資料,B 和 C 反而很閒。這樣分了等於沒分,甚至更糟。

解決方法是引入「虛擬節點(virtual node)」。

做法是這樣的:每一台實體伺服器,不是只在環上放一個點,而是放很多個點。例如,每台機器放 150 個虛擬節點,做法是對「節點名稱 + 編號」做雜湊,產生 150 個不同的位置:

節點 A 的虛擬節點:hash("A-1") = 5,  hash("A-2") = 38, hash("A-3") = 71, ...(共 150 個)
節點 B 的虛擬節點:hash("B-1") = 12, hash("B-2") = 49, hash("B-3") = 83, ...(共 150 個)
節點 C 的虛擬節點:hash("C-1") = 21, hash("C-2") = 55, hash("C-3") = 90, ...(共 150 個)

這 450 個虛擬節點散落在環上,由於數量夠多,統計上就會趨近於均勻分佈。而每個虛擬節點負責的實際資料,最終還是由它背後的那台真實機器來儲存。

虛擬節點還帶來另外兩個在實務上非常重要的好處。

第一個是應對異質性(heterogeneity)。現實中的機器叢集往往不是整齊劃一的:有些是舊機器(CPU 慢、記憶體小),有些是新機器(效能強)。如果強迫每台機器負責相同份量的資料,舊機器可能早就喘不過氣,新機器卻還很悠閒。有了虛擬節點,就可以彈性調整:效能強的機器配 200 個虛擬節點,效能弱的只配 50 個,讓每台機器承擔與自己能力相稱的負載。這種彈性,在需要混用新舊機器的維運環境中,是非常實用的特性。Amazon Dynamo 的原始論文中就明確指出,虛擬節點的設計正是為了處理這種「節點效能不一致」的問題。

第二個是故障時的負載分散。當一台機器突然故障下線時,它的多個虛擬節點會分別把資料轉移給環上各自的下一個節點,等於把負擔分散給了多台機器,而不是全部壓給同一台。如果沒有虛擬節點,一台機器掛掉,它的所有資料就全部湧向單一的下一台,那台機器的負載瞬間暴增,說不定也跟著掛掉,接著又觸發下一台……這正是前面提到的雪崩效應。

一致性雜湊搭配虛擬節點的組合,最早在 2007 年被 Amazon 發表的一篇名為「Dynamo: Amazon's Highly Available Key-value Store」的論文中系統性地提出,並完整描述了它在大規模生產系統中的應用。這篇論文後來被公認為分散式資料庫領域最具影響力的論文之一,直接啟發了 Apache Cassandra(Facebook 開發)等一代 NoSQL 資料庫的設計。現今 AWS 雲端服務上的 DynamoDB,雖然底層實作已經遠比當年複雜,但其核心概念——透過 Partition Key 進行雜湊分片、並在後台自動處理資料搬遷——仍然延續自 Dynamo 的設計哲學。

三種策略的比較

講了這麼多,讓我們來整理一下這三種方法的優缺點,方便日後查閱。

Range Sharding 的優點是範圍查詢效率高,資料的分佈邏輯直覺,容易調試和維運。缺點是容易產生熱點,資料分佈可能不均,增減節點時部分資料需要搬遷。適用情境是讀取以範圍掃描為主、寫入流量較均勻的場合,例如時間序列資料(log、監控指標)的歸檔系統。

Hash Sharding 的優點是資料分佈均勻,單鍵查詢速度快,有效避免熱點。缺點是範圍查詢需要掃全部節點,以及增減節點時幾乎所有資料都要搬移,代價極高。適用情境是查詢模式以 point query 為主、資料量穩定不常增刪節點的系統。

Consistent Hashing 的優點是增減節點時只搬少量資料,搭配虛擬節點後資料分佈均勻,非常適合動態擴縮容的分散式環境。缺點是範圍查詢同樣不友善,實作相對複雜,調試成本也比前兩者高一些。適用情境是需要頻繁動態擴縮的大型分散式系統,例如 Apache Cassandra 這類分散式 NoSQL 資料庫。

事實上,很多成熟的系統會混合使用這些策略,或是在這些策略上發展出變形。例如 MongoDB 同時支援 Range Sharding 和 Hash Sharding,工程師在建立 Sharded Cluster 時必須決定「分片鍵(Shard Key)」,一旦選定,分片策略就固定下來,無法任意更改,所以選對分片鍵是 MongoDB 維運中非常關鍵的決策。

Redis Cluster 則是一個有趣的案例。它官方文件明確寫道「Redis Cluster does not use consistent hashing」,而是採用了一套叫做雜湊槽(Hash Slots)的機制:將整個 key 空間切成固定的 16,384 個槽位,每個節點負責其中一部分槽位。擴充節點時,是把槽位從舊節點搬到新節點,而不是重新計算整個雜湊環。這個設計在邏輯上與 Consistent Hashing 非常相似,但因為槽位數量固定,對資料分佈的控制更精確,實作和維運工具也更易於管理。

Sharding 只是開始

Sharding 解決了「資料量太大放不下」的問題,但它同時也帶來了一系列新的複雜度。例如,跨 shard 的 JOIN 查詢怎麼做?跨 shard 的交易(transaction)如何保持一致性?如果一筆資料需要根據不同的查詢維度存放在不同的 shard(例如訂單既要依使用者 ID 查,又要依商品 ID 查),怎麼辦?

這些問題,每一個都是分散式系統裡的大哉問,每一個都有一整套的理論和工程實踐來對應。Sharding 是分散式資料儲存的入門門票,但要真正把一個大型分散式系統做好,還有非常漫長的路要走。

但至少現在,當你下次在面試被問到「系統資料量太大怎麼辦」的時候,你已經知道不只是「加一台更大的機器」這個答案了。你會知道怎麼「搬家」,也會知道怎麼讓搬家的過程痛苦少一點。

Share:

#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:

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

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

Share:

#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 來產生簡單易懂的答案,不知道讀者們會喜歡這想法嗎 ?


Share:

#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 樹很可能就在背後默默運作。

Share:

#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)。從這個方法延伸下去還可以有許多的理論和應用產生.

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


Share:

#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,

Share:

#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.這類似的分散式系統是相對較封閉的分散式系統,因為是由某一家公司自己主導與開發,所以每家公司所使用的 "標準" 就不見得是一致的,各家都可能不一樣.


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


Share:

#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.

Share:

#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.

Share:

#93 平衡樹系列 - AVL Tree

在前面的資料庫文章裡曾介紹過 B-tree,一種平衡的搜尋樹,利用樹狀的結構來達成快速尋找的目的,而且因為是平衡的,所以從 root 出發到每一個樹葉的尋找成本是一樣的,這也是必要的,畢竟資料庫引擎用公平的方式來對待所有的資料.然而,B-tree 的結構並非是 binary 的型式,因此這帶給它很大的彈性可以方便地達成一個完全平衡的狀態.在前幾篇的文章也談過了 binary search tree,若你看過的話,你會清楚地知道 binary search tree 和 binary tree 的不同.在 binary search tree 裡,因為在建立樹的過程中有一個很重要的特性,就是右邊子節點的值大於父節點,左邊子節點的值小於父節點,因此在建立樹或是尋找節點時,到達一個節點時,只需要選擇其中一邊,不是左邊就是右邊,所以也達到 "binary search" 的效果.如前面的文章所說,binary search tree 的特性並不保證樹結構本身是平衡的,所謂的平衡就是其結構會和 complete binary tree 很接近.因為 binary search tree 沒有這樣的特性,因此樹的結構很可能是 "歪" 的.

為了要防止這種 "歪" 的情況,在早期的電腦科學研究裡便出現了許多的點子和做法,其中一個稱為 AVL Tree.這是兩位前蘇聯時代的科學家所發明的方法.發明的時間都是在我們出生之前 (我猜想這部落格的讀者群應該沒人超過 60 歲).首先,先把 AVL tree 的時間複雜度列出來.

Search: O(log n), Insert: O(log n), Delete: O(log n),不論是 average case 或是 worst case 都是一樣的時間複雜度,超級完美的.這也是為什麼在上一篇章的 APCS 考題會拿像 binary search tree 的實做來用,因為就是這麼快.不論是刪除或插入,甚至尋找都是 O(log n),為什麼可以這麼快呢? 接下來將來說重點了.

AVL Tree 是一種 binary search tree 的特例,所謂的特例是指 binary search tree 再加上一些其他的特性之後就能變成 AVL tree.而這一個特性稱為 balance factor.每一個節點上都會有一個 balance factor,它代表的是一個值,其值是右邊子樹的高度減掉左邊子樹的高度.例如:

source: Wikipedia

節點 F ,右邊高度為 1,左邊高度為 2,所以 F 節點的 balance factor 為 1 -2 = -1,其他的節點也是用同樣的公式而得.AVL tree 定義了每個節點的 balance factor 必須為 -1 , 0 或 1.透過 balance factor 的限制,我們能知道這一個樹就 "比較" 不會那麼歪掉了,因為右邊子樹和左邊子樹的高度最多只能相差 1 而己.為了確保這個特性能發生,在插入節點或刪除節點的過程裡便需要採取一些動作.而這些動作如下:

1. 往左轉

source: www.tutorialspoint.com

如上圖,節點 A 的 balance factor 是 2,因此必須降低它,由於這是 binary search tree,所以 C 的值大於 B,而 B 的值又大於 A,因此,要把樹技折下來的話,拿中間者來當新的父節點最好,於是以 B 為中心將 A 往左轉,所以就變成了最右邊的圖,這樣就符合了 AVL tree 的特性.

2. 往右轉

source: www.tutorialspoint.com

往右轉的情況剛好是和第一種相似,只是換另一邊而己.

3. 往左再右
source: www.tutorialspoint.com
第三種情況其實是前面兩種情況的綜合體.若你看懂前面兩個為何要那樣轉的話,我相信你也一定看的懂第三種.其主要目的就是要讓 AVL tree 的特性可以滿足.
最後第四種,可想而知就是往右再往左.

4. 往右再往左

source: www.tutorialspoint.com
第四種情況就是第三種的另外一邊.只要你懂第三種情況,那麼第四種情況自然也不會是問題.

你可能會問我,像這種 AVL tree 要應用在什麼地方.老實說,到處都是,許多程式語言在他們的 standard libary/SDK 裡都會提供這種平衡的 binary search tree.我在工作上時常會用到這類型的資料結構以快速建立資料和尋找資料.前一篇 APCS 的解題就是靠類似 AVL tree 這種的平衡樹才能將時間複雜度降到 O(n log n).別以為 O(n2) 和 O(n log n) 相差不多,一旦輸入的數量到達數以萬計時,你的家用 CPU 就會告訴你他們之間有很大的差距了.

在 Wikipedia 上你也可以找到一個動態的圖來說明 AVL tree 在建立的過程中,這些節點是如何左轉或右轉來達成平衡.AVL tree 將達成平衡這件事分攤在節點插入和刪除的過程中,因為才使得插入節點,刪除節點和尋找節點都有相同的時間複雜度.這的確是很高明的做法,我們大家又再一次站在巨人的肩膀上來看見電腦科學的神奇之處.

Share:

#92 今年一月份 APCS 程式設計第三題 - 切割費用

前陣子,我的小徒弟去報名他人生第一次的 APCS 考試,可以說是他學習電腦科學以來第一次的正式上機考試.一共有四題的程式設計題目,前面兩題算是簡單的,第三題算中等,第四題比第三題再進階一點點.這篇文章就來談談第三題的解題思考.

完整的題目在 https://zerojudge.tw/ShowProblem?problemid=f607 ,首先,要解題之前,請先確定自已己經百分百了解題目.這一個題目的解決過程可以分成下列 2 個部份,

1. 讀取輸入參數,因為輸入參數並非按照切割次序而輸入的,我們要進行切割時是按照次序來切割的.因此,我們必須對輸入參數做處理,以讓沒有次序的參數集合變成有次序的參數集合.

2. 每一次切割時,都需要知道左右兩端的長度,這樣才能算出該次切割的費用,而知道左右兩端的長度,這需要一個快速的行為才能符合題目的要求.因為題目提到切割次數最多會到二十萬次,並且棍子的長度可以到 10 7 那麼長.

有關讀取輸入參數的內容,基本上有兩種做法,可以把切割資料全部讀進來之後,再以切割次序做排序.若是這樣做,這個動作將花費 O (n lg n)  ,假設是用 quick sort. 除此以外,我們可以換個角度思考,題目給的切割次序不會出錯,也就是說當切割資料讀進來時,切割次序就是一種 key,不會重覆,因為第 n 次切割只會發生一次.所以可以用 (key, value) 的 hash table 來存放切割資料.由於 hash table 的 set , get 都是 O(1) ,所以這讀取動作將花費 O(n).

因此,第一個部份的時間複雜度最小可以到 O(n).

接下來,第二部份是計算每一次切割的費用.可以想像正在發生第 k 次的切割,也就是我們要想一個快速的方法讓我們可以查到在第 k 次切割時,當時所在的位置往左邊和往右邊走碰到的第一個切割點. 假設一開始用一個 boolean array 來代表被切割的點,

index :  0    1    2    3    4    5  ......98   99  100    101    102    103  ........ n

value:   f     f     f     f    f     t  .....  t     f       f        f        t         f      .......  f

一開始 array 的都是 false ,被切割過的點就變成 true,假設第 k 次的點要切割在第 100 個位置,而 98 和 102 是 true,所以這一次的切割費用是 102 - 98 = 4.如果以程式的角度來看的話,你得寫一個 for loop 從 100 往右邊走,找到第一個 true ,然後再往左邊走找到第一個 true,然後再做減法.這樣的尋找方式是 O(n),而這個會發生在切割資料的迴圈裡,假設切割資料是 m 筆,因此這一段的時間複雜度是 O(nm),一旦 n 和 m 都很大時,這就相當於是 O(n*n).而 n 最大的值會到 20 萬,因此 O(n*n) 是不能接受的.因此,用 array 做搜尋是不合格的,所以我們必須用其他的資料結構,並且這個資料結構所花費的成本要小於 O(n) (比 array 一個一個找再快).

這時候,答案其實已很明顯了,能夠比 array O(n) 還要快的只有 binary search tree O(lg n) 或是 hash table O(1) .在這一個動作的過程中,我們需要能 "往左走" 和 "往右走" ,Hash table  顯然不會是個好選擇,因為 hash table 無法儲存元素之間的 "順序",因此,就剩下 binary search tree 了.binary search tree 在儲存的過程花費 O(lg n) 時間,而尋找的過程也是花費 O(lg n) 時間,而且 binary search tree 的特性讓我們可以 "往左走" "往右走" 來找到最近被切割過的位置.因此,採用 binary search tree 之後,時間複雜度可變成 O (m lg n) ,如果 m 和 n 都很大時,就是 O( n lg n),這個比剛剛的 O(n*n) 快上很多.

最後,以下的程式碼是我的小學徒提供的,在很大的測試資料下仍花費了 0.25 秒完成,雖然不是最快,但也符合了題目 2 秒內的要求.

Share:

#91 如何寫有影響力的履歷表

根據 Facebook 社團上的成員資料,目前三百多位成員裡有將近 40% 成員的年紀在 34 歲以下,因此,希望這篇文章可以提供年輕人有關撰寫履歷表內容時的參考.

一般來說,我會把履歷表的寫法分成兩種,一種是屬於年輕工程師的寫法,另一種是資深工程師的寫法,我將年資不到十年的人定義為年輕工程師,所以可能是在 32 - 36 歲之間,就看你在幾歲從學校畢業.在這年資以下的人,撰寫履歷表時應該要著重在技能的部份.也就是說,你得在履歷表上說明你用過了那些工具與方法來製造軟體系統,以及你運用了那些專業知識 (課本上學的) 在你的工作上.比如,某個年輕工程師從事電商系統前端功能的開發,屣歷表上就需要清楚說明用 Javascript/TypeScript 寫了什麼東西,是否用到其他的 framework,如 Angular 等等,並且做過那些功能,如購物車系統,付款流程,購物體驗等等.把這些東西寫清楚來,讓看履歷表的人明確知道你過去曾用過的工具以及熟悉的產業環境是什麼,這樣能幫助雇主加快認識你的速度.

為什麼年輕工程師要寫這樣的內容呢 ? 因為年輕工程師通常被給予的任務是小而明確的,如解 bug 或做一些小功能.履歷表上寫一些技能類的事情可以幫助未來的雇主知道你過去做過些什麼,也能幫助雇主評估是否要找你來進行面試.

如果 32 - 36 歲以上的工程師 (超過十年的業界經驗),理論上來說,在業界工作了十年應該要達到資深工程師的水準了.我猜想在台灣的公司對於職稱上的給定標準並沒有一致且較寬鬆,所以中小企業或是非資訊科技領域的公司做了三五年後就能得到資深工程師的職稱.在規模大且制度嚴謹的公司裡,要在三到五年內拼到資深工程師是件不容易的事情,資深工程師的履歷表就應該著重於有關 "影嚮力" 的事情,比如,製造一個付款交易系統,讓整個網站可以在一分鐘之內完成 n 筆交易,使得網站可以承受 m 個使用者的流量.再舉另一個例子,重新製造了購物車系統,讓原本客戶評價極差的用戶體驗變成零負評的新體驗,並且讓網站提升 n % 客戶滿意度.再舉另一個例子,製造了一套基礎建設程式庫用於處理公司內所有系統的溝通機制,將原本平均一分鐘執行時間的動作提升至十秒鐘完成.或是一個更利害的例子,製做了一個很利害的 open source software,放在 Github 上得到了 n 顆星星,造福了世界上許多的軟體工程師.透過這些簡單例子,我相信你一定明白我所謂的 "影響力" 是什麼意思了.

回過頭來,並不是說年輕工程師就不用寫影響力.對於年輕工程師而言,如果你可以寫出令人信服的影響力,一定要寫下來,因為那些都是能讓你換到新公司時談職位與薪水的利器.

不論你寫的是技能比較多或是影響力比較多,千萬要記得別亂寫或是誇大地寫.若有機會面試時,這些技能和影響力是很容易被檢查出來的,一旦面試官發現你在 "唬爛" 時,你有可能永遠不會出現在這公司的面試名單裡.

履歷表內容的基本上包含了你的個人基本資料,工作經歷,學歷,技能以及一些參考資料.以我的經驗來說,我會將影響力放在工作經歷的內容裡,所以每一個工作都會是一段描述,而不是一行文字只包含公司名稱,職位名稱和時間而己.通常來說,一到兩頁的履歷表就應該要把你自己說明清楚,過長的內容,雇主很容易跳過不看,因為有名的公司每天都會收到很多履歷資料,沒有人會把細節看完.同時也要告訴一些年輕的工程師,工作要慎選,常常換工作並不是一件好事情,技能的程度高低也許不會受到換工作的影響,但我相信影響力是需要時間累積的,若常常換工作,則很難說明與說服其他人你在短時間裡能在一家公司做出有影響力的事情! 所以,找新公司時要好好想清楚,工作經歷就像是學歷一樣無法抹去也無法作假的,因此,在換公司時也要好好想想你該如何在新公司做出影響力的事情.同時這個題目也可能當成你和你老闆一對一面談時間裡的內容.

Hope it helps,

Share:

#90 淺談 Dynamic Programming (2)

 前面說過 dynamic programming 的應用很多,這一篇文章來說明其中一種應用,Maximun subarray sum.這個問題是在一個整數的 array 裡找一個連續空間的元素,其元素的總和的值是最大的.如下圖:


source: https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/

從 index 2 到 index 6 之間的元素總和等於 7,這個區間是這個 array 裡最大的區間總和. 要解決這個問題其實不難,因為用最直接的暴力法就可以解決了,其程式結構如下:

這一個暴力法的時間複雜度是 O(n*n*n) ,n 是 array 的長度. 如果 n 很小,影嚮不大,但若 n 很大,這一個運算雖然在空間複雜度很表現的很好,但浪費許多 CPU 的運算資源,因為許多加法的計算是重覆了. 將這個問題的時間複雜度降低的方法不只一種,在這篇文章裡,我們用 dynamic programming 的策略來試著降低時間複雜度.如前一篇文章提過的內容,dynamic programming 的策略在於用空間換取時間,所以我們必須找出在什麼地方可以減少重覆的計算.要減少重覆計算之前,我們可以先從暴力法來看到底真正的計算是花在什麼地方了. 從上述的程式碼,你可以看到決定 subarray 的總和值是從最裡面的迴圈來運算的,所以第一圈會計算 start = 0 , end = 0 的總和值,第二圈會計算 start = 0, end = 1 的總和值, 第三圈會計算 start = 0, end = 2 的總和值,以此類推下去.透過觀察,你便能發現第二圈要計算的內容在第一圈已經算過了部份答案,第三圈要計算的內容在第二圈已經算過了部份的答案,因此,最裡面的迴圈其實是重覆了做了許多相加.

Loop 1: -2 

Loop 2: -2 + -3 = -5  (Loop 1 + -3)

Loop 3: -2 + -3 + 4 = -1 (Loop 2 + 4)

Loop 4: -2 + -3 + 4 + -1 = -2 (Loop 3 -1)

因此,透過以上的運算呈現,便能知道最後一個迴圈是可以去除的.我們只要將上一圈計算後的內容先暫存起來,留到下一圈時便能拿出來用,直接做一次加法就可以得到這一圈的答案了.因此,那個查表法的 "表" 也只不是一個臨時的變數,在空間複雜度上並沒有增加,而時間複雜度卻降了一階變成了 O(n*n),如下列的程式碼.

接著,或許你還會問,空間複雜度還仍再降嗎 ? 剛好這一個題目是可以的,它的名字是 Kadane's algorithm,這個演算法在許多讀者還沒出生之前就已經發明了,這演算法能用 O(n) 的時間複雜度解決這問題,而發明人是一位教授,現在已經非常高齡了. 若你晚些才看到這篇文章, Kadane 教授也許不在人世了,我們大家都是站在巨人的肩膀上.

最後,你可能會問這個演算法我們該用在那裡.這完全取決於你是否會遇到類似的題目.如果你遇到一個問題,而這問題剛好可以 Reduce 成 maximum subarray sum 時,Kadane's algorithm 便能幫助你寫一個超快速的程式來解決問題,例如,你老闆要你找出過去十年裡,那幾個連續的月份其營業額是最好的.

Dynamic programming 的策略確實應用在許多地方,未來介紹更多的主題時,一定都還會碰到 dynamic programming 策略所產生的解法.

Share:

#89 淺談 Dynamic Programing (1)

Dynamic programming 是大學部演算法課程裡相當重要的一個主題,也是典型用空間換取時間的策略.但奇怪的是,這個策略一點也不 dynamic ,一點也不 programming.老實說,我不知道為何這個策略叫 dynamic prograaming,我倒覺得它比較適合叫 "查表法". 接著就來看看為何說它是查表法.

Fibonacci number 是許多演算法課本用來解釋 dynamic programming 最簡單的例子.Fibonacci number 是以數學多項式來表達的數字集合,以數學式來表達就可以寫成如下:

F(n) = F(n-1) + F(n-2) 

也就是說求第 10 項 (n=10) 的答案時,你必須要先算出來第 9 項和第 8 項. 如果要求第 1 項呢 ? 難道要找出第 0 項和第 -1 項嗎 ? 在 Fibonacci number 上,我們會為這個 number 定義起始點,也就是說第 1 項和第 2 項的值是早被確定的,往後的項次皆由這兩項為基礎而算出來,所以不會有第 -1 項的情況. 假設, F(0) = 0, F(1) = 1 ,那麼數列的答案如下:

F(2) = F(1) + F(0) = 1 + 0 = 1

F(3) = F(2) + F(1) = 1 + 1 = 2

F(4) = F(3) + F(2) = 2 + 1 = 3 

F(5) = F(4) + F(3) = 3 + 2 = 5 

F(6) = F(5) + F(4) = 5 + 3 = 8  以此類推

當你要算第 n 項時,就按以上的方法一直算到第 n 項就能得到答案. 接著,數學公式 F(n) = F(n-1) + F(n-2) 寫出來了,那麼寫程式碼就變得相當簡單.

透過一個 recursive function 就能快速完成  Fibonacci number 第 n 項的計算程式.這一個程式碼沒有使用額外的記憶體空間,所以 space complexity 是 O(1),但仔細看一下 time complexity,卻發現超乎想像的大,因為有許多重覆的步驟:

            F(5)  
          /     \
       F(4)      F(3)
      /    \    /    \
   F(3)   F(2) F(2)  F(1)
   /  \
 F(2) F(1)

上圖是整個 recursive 的關係. 意思就是,當程式在 F(5) 那一個層次要往下呼叫時,程式會呼叫自己兩次,並傳送 4 和 3 為輸入參數,當第一個 recursive call 再進去時,又會再呼叫自己,並傳入 3 和 2 為輸入參數,以此類推.所以你可以看的出來,有許多重覆的計算在這 recursive 的過程中一直發生.以上圖來說,F(3) 發生了 2 次,F(2) 發生了 3 次.當 n 是一個大的數字時,你就可以發現比 n 越小的數字,重覆計算的次數越多,並且是以指數趨勢來增加.上述的程式碼雖然很簡單,但是 time complexity 卻是很可怕的.上述的程式碼是由上而下計算下來的,假設我們繼續用由上而下的計算方式,改良此程式碼的方法就是將 "重覆" 的計算步驟讓它不要重覆計算.如上圖,如果 F(3) 只真正地被計算了一次,而 F(2) 只真正地被計算了一次,那麼就不會有重覆計算的事情了.為了達成這目標,最簡單的方法便是把計算後的結果儲存下來,等到要計算一樣的內容時,去 "查表" 即可.也就是說第一次 F(3) 計算的結果儲存下來,當程式遇到第二次的 F(3) 時,直接去查詢,若有答案,直接將答案拿來使用,這樣就不用計算了.同時,為了確保不會造成過多的 time complexity,我們也需要確認答案的儲存和查詢所花費的 time complexity 要非常小,如 O(1).這種 "查表" 的精神也是 dynamic programming 所代表的策略.

若將上述的程式碼加入 "查表" 的功能,它將看起來如下:

或是直接改成由下往上計算

以上兩個程式碼雖然結構有點不太一樣,但都是用了一個 array 來記錄每一個項次計算的答案,因此 time complexity 省下來了,而且 space complexity 也增加了,但這樣的空間增加似乎是值得的.當然也可以再把上述的程式碼繼續改下去讓 space complexity 變的更小,不過這並不是這篇文章的重點.透過以上的簡單例子讓大家方便了解 dynamic programming 的 "查表" 意義是什麼.許多世界上有名的演算法都是基於 dynamic programming 的精神所發展出來的,例如你幾乎每天都在用的字串比對演算法就是基於 dynamic programming 所發明出來.

這篇文章用 Fibonacci number 的例子來說明 dynamic programming 的精神,這是相當簡單的例子,下篇文章我們用較難的例子來說明 dynamic programming 的用法.


Share: