系統效能與可擴展性

作者:

Big O 符號是用於描述演算法的執行時間或空間需求，如何隨著輸入資料量 (n) 的增長而變化的數學標記法。它關注的是演算法效能的增長趨勢與最差情況，而非精確的執行時間。

  • O(1) – 恆定時間: 執行時間固定，完全不受輸入大小影響。無論處理 10 筆還是 100 萬筆資料，所需時間都相同。
    • 範例: 從陣列中透過索引存取元素、從雜湊表中讀取特定鍵的值。
  • O(log n) – 對數時間: 效率極高。每次操作都能使需要處理的資料規模減半，常見於「分而治之」的演算法。
    • 範例: 在已排序的陣列中進行二分搜尋、在平衡二元搜尋樹中查找元素。
  • O(n) – 線性時間: 執行時間與輸入大小成正比。資料量增加一倍，執行時間也約略增加一倍。
    • 範例: 遍歷一個列表以尋找特定元素（線性搜尋）、對未排序的資料找出最大值。
  • O(n log n) – 線性對數時間: 非常高效的排序演算法所能達到的平均時間複雜度。它比 O(n²) 快得多。
    • 範例: 快速排序 (Quicksort) 的平均情況、合併排序 (Merge Sort)。
  • O(n²) – 二次時間: 執行時間隨輸入大小的平方增長。當資料量變大時，效能會急劇下降，應盡量避免用於大規模資料。
    • 範例: 冒泡排序 (Bubble Sort)、使用兩層嵌套迴圈對列表中的每個元素進行兩兩比較。
Arrays[ ] 陣列

Arrays[ ]  陣列

  • 記憶體模型： 將資料儲存在連續的記憶體區塊中。
  • 存取速度： 使用索引的恆定時間存取 constant-time access (O(1))
  • 插入/刪除： 如果在末尾以外的任何地方添加/刪除元素，則需要移動數據 ，從而使這些操作成為 operations  O(n) 。

最佳化： 大小固定或透過索引頻繁存取資料 。

鏈結串列 Linked List<T>

  • 記憶體模型： 使用指標分隔連接的節點 ，允許靈活的記憶體分配。
  • 存取速度： 需要線性搜尋 O(n) 才能到達元素，較慢(遍歷列表)。
  • 插入/刪除： 如果已知指向節點的指針， 則新增 Add.Last( )或刪除 Remove( ) 元素的時間為 O(1) 。
  • 最佳化： 資料頻繁變化 ，例如在任意位置插入或刪除元素 。

堆疊 Stack<T> – Last In, First Out

  • 工作原理： 將項目添加 Push( ) (O(1))到頂部，並從頂部移除 Pop( ) (O(1))。

最佳化：  需要後進先出行為(巢狀結構)，輸出順序會是由新往舊輸出 ，例如撤銷功能、遞歸函數呼叫、解析表達式 。

佇列 Queue<T> – First In, First Out

  • 工作原理： 從最後面新增 Enqueue( ) (O(1)) 物品並從第一個元素移除 Dequeue( ) (O(1))。

最佳化：  需要先進先出處理(順序處理) ，例如處理 API 請求、管理後台任務、列印作業排程、處理訊息 、廣度優先搜尋 (BFS)。

雜湊表 Hash Table

假設有一間超級大的倉庫，裡面存放著數百萬個包裹（值），每個包裹上都貼有一個唯一的收件人姓名（鍵）。

  • 如果用陣列，你得從頭到尾找一遍，速度很慢。
  • 如果用雜湊表，倉庫管理員會使用一個「轉換公式」（即雜湊函數），將收件人姓名（鍵）瞬間轉換成一個精確的儲存地址（索引），然後直接走到那個位置取出包裹。

雜湊表主要由兩個關鍵部分組成：

  1. 陣列 (Array / Bucket Array)

這是一個實際儲存資料的結構，雜湊表中的所有值都儲存在這個陣列的特定索引位置上。

  1. 雜湊函數 (Hash Function)

這是一個數學函數，它接收一個鍵 (Key) 作為輸入，並輸出一個固定範圍的數字作為索引 (Index)。

# Index=HashFunction(Key)

  • 插入資料 (Insertion)：當你要儲存 (“Apple”, 5) 時，雜湊函數將 “Apple” 轉換為一個數字，例如 15。5 就被儲存到陣列的索引 15 處。
  • 查找資料 (Lookup)：當你要找 “Apple” 的值時，你不需要遍歷整個陣列。你只需將 “Apple” 再次輸入到雜湊函數，得到 15，然後直接到陣列索引 15 處取出值 5。

雜湊碰撞 (Hash Collision)

雜湊函數的目標是將無限的輸入鍵映射到有限的陣列索引上。這就必然會產生一個問題：不同的鍵可能會被映射到同一個索引位置。

例如：HashFunction(“Banana”) 也輸出 15。這時，“Apple” 和 “Banana” 就會撞在一起。

解決方法

  1. 鏈接法 (Chaining)：
    • 在發生碰撞的索引位置上，不只儲存一個值，而是儲存一個連結串列 (Linked List)。
    • 如果 “Apple” 和 “Banana” 都映射到 15，那麼在索引 15 處的連結串列中，會同時儲存這兩個鍵值對。
  2. 開放定址法 (Open Addressing)：
    • 如果一個索引位置被佔用，就尋找陣列中的下一個空位來儲存新的鍵值對。

Binary Tree 二元樹 :

就像你家族的族譜，每個成員（節點 Node）最多只能有兩位直屬晚輩。

    • 根節點 (Root)： 樹的最頂端，是所有節點的起點。
    • 節點 (Node)： 樹中的每一個數據元素。
    • 邊 (Edge)： 連接節點之間的線，表示從父輩到子輩的關係。
    • 最多兩個孩子： 任何一個節點，最多只能有兩個子節點，分別稱為 左子節點 (Left Child) 和 右子節點 (Right Child)。
  • 用途：二元樹本身是一個通用的結構，用於組織數據，例如表達數學表達式（算術樹）或作為更複雜樹結構的基礎。

Binary Search Tree (BST) 二元搜尋樹 :

是從二元樹升級而來的，它最大的特點就是排序，能夠高效地搜尋、插入和刪除資料。

  • 左小於父： 任何節點的 左子樹 中所有節點的值，都小於該節點本身的值。
  • 右大於父： 任何節點的 右子樹 中所有節點的值，都大於該節點本身的值。
  • 遞迴遵守： 左、右子樹本身也必須是一棵 BST。

用途：

  • 高效查詢： 是許多資料庫和檔案系統索引的基礎。
  • 排序： 只要對 BST 進行中序遍歷 (In-order Traversal)，就能得到一個由小到大排序的結果。

Preorder 前序遍歷 (Root → Left → Right) :  首先訪問根節點，然後探索左子樹和右子樹，對於必須在子項之前處理根的任務很有用，例如建立資料夾結構的備份。

Inorder 中序遍歷 (Left → Root → Right) : 先處理左子樹，然後處理根，最後處理右子樹，通常用於二元搜尋樹（BST）中按排序順序檢索資料。

Postorder 後序遍歷 (Left → Right → Root) : 在訪問根之前探索左孩子和右孩子，適合需要在處理父級之前處理子級的操作，例如目錄刪除。

Level-Order 層次遍歷 (Breadth-First Search – BFS) : 從上到下逐級存取節點，用於分層處理，如組織結構圖和網路廣播。

平衡樹 (AVL Tree) :

它的目標就是消除 BST 中最差情況 O(n) 的風險，永遠將樹保持在一個平衡的狀態，確保搜尋效率始終是 O(logn)。

  • BST 規則： 它首先必須滿足所有 BST 的規則（左小於父、右大於父）。
  • 平衡因子： 任何節點的 左子樹高度 和 右子樹高度 的差值（即平衡因子），絕對不能超過 1 (只能是 1,0,−1)。

旋轉 (Rotation) : 當你插入或刪除一個節點，導致某個節點的平衡因子變成 2 或 −2 時（也就是樹「失衡」了），AVL 樹會立即執行一個或多個聰明的 旋轉 (Rotation) 操作（例如：左旋、右旋、左右旋、右左旋）。

這些旋轉操作會重新調整節點的位置，在不破壞 BST 的排序規則的前提下，將樹重新拉直、重新變矮，讓它再次達到平衡！

用途：

  • 性能： 需要嚴格保證高效能的系統，例如對查詢速度有極高要求的記憶體資料庫或索引系統。
  • 穩定的日誌記錄： 在數據量大且操作頻繁的場景中，提供穩定且可預期的性能。

圖 Graph :

是一種非線性的資料結構，用來模擬現實世界中節點 (Nodes/Vertices) 與 連線 (Edges) 之間的關係。

  • 節點 (Node/Vertex)： 地圖上的地點、城市、人物、網頁等。
  • 連線 (Edge)： 連接這些地點的道路、關係、連結、飛行路線等。
Bubble Sort 冒泡排序

Bubble Sort 冒泡排序

比較相鄰的兩個元素，如果順序不對(例如，希望小的在前面，但後面的比前面的小)，就把它們交換。

這個過程會不斷地重複，直到最大的或最小的元素像氣泡一樣「浮」到它最終的位置。

時間複雜度 (Time Complexity) : 

  • 最差 O(n2) : 元素完全反序，需要大量交換。
  • 最佳 O(n) : 數組已經排好序，只需走訪一次。

空間複雜度 (Space Complexity)

  • O(1) : 只需幾個額外的變數來進行交換，所以是原地 (In-place) 排序。

用途：適用於小型資料集或當簡單性優先於效能時。

Quicksort 快速排序

採用分而治之的方法，選一個元素作為「基準點 (Pivot)」，然後把所有比它小的元素放到左邊，比它大的放到右邊。

基準點的位置確定後，它會對左邊和右邊的子數組遞迴地重複這個過程，直到整個數組都有序。

時間複雜度 (Time Complexity) : 

  • 最差 O(n2) : 如果每次都選到數組中的最大或最小元素作為基準點（例如數組已經排好序），性能會急劇下降。
  • 平均 O(nlogn) : 數組已經排好序，只需走訪一次。

空間複雜度 (Space Complexity)

  • O(logn) (遞迴堆疊) : 遞迴調用會佔用棧空間。

用途：適合對大量數據進行即時排序。

Merge Sort 合併排序

也是採用「分而治之 (Divide and Conquer)」策略，它會先將數組不斷地從中間分割成兩半，直到每個子數組都只剩下一個元素（一個元素當然是有序的）。

然後，它再將這些有序的子數組兩兩地合併起來，合併時會仔細比較兩個子數組中的元素，並按照正確的順序放回新的數組中，直到所有元素都合併回一個完整的有序數組。

時間複雜度 (Time Complexity) : 

  • 平均 O(nlogn) : 無論數據如何分佈，它都能保持一致的高效率，非常穩定。

空間複雜度 (Space Complexity)

  • O(n) : 合併過程需要一個與原數組大小相近的輔助數組來暫存合併結果。

用途：對需要穩定性的大型資料集進行排序 。（例如磁碟上的文件排序）。

Linear Search (線性搜尋)

Linear Search (線性搜尋)

線性搜尋是最直覺、最簡單的尋找方式，就像我們從頭到尾翻閱書架上的每一本書，直到找到目標為止。

時間複雜度 (Time Complexity) : 

  • 最差 O(n) : 最差情況是你找的目標在最後一個，或是根本不在列表中，你必須檢查 n 個元素。
  • 最佳 O(1) : 你找的目標剛好就在第一個位置。

空間複雜度 (Space Complexity)

  • O(1) : 只需要幾個額外的變數來追蹤索引，是原地 (In-place) 算法。

用途：未排序的資料、數據量很小

Binary Search 二分搜尋

二分搜尋就像是你在查字典：你不會一頁一頁翻，而是先翻到中間，看看中間的字比你要找的字大還是小，然後立刻排除掉一半的頁面。

時間複雜度 (Time Complexity) : 

  • 最佳 O(logn) : 這是因為每做一次判斷，數據規模就減半。logn 是一個非常快的增長速度。

空間複雜度 (Space Complexity)

  • O(1) : 只需幾個變數來追蹤 low, high, mid。

用途：已排序的大型數據集、需要快速尋找的場景。

名稱排序方式(a->z) : users.Sort((a, b) => a.Username.CompareTo(b.Username));

# (z -> a) b.Username.CompareTo(a.Username));

Breadth-First Search (BFS) 廣度優先搜尋

一層一層地往外探索。就像在湖面丟了一顆石頭，波紋會一圈一圈地向外擴散。

  • 機制 : 從起點出發，先走訪所有鄰近的節點（第一層），然後再走訪所有鄰近節點的鄰近節點（第二層），以此類推。
  • 資料結構 : 使用 佇列 (Queue) 來儲存接下來要造訪的節點，體現「先進先出」的廣度特性。
  • 用途 : 尋找最短路徑 (因為它是按照層級擴散的，第一個找到的路徑就是最短的)。

BFS 程式碼骨架 (迭代版)

from collections import deque

def bfs(graph, start_node):

    visited = {start_node} # 已造訪集合

    queue = deque([start_node]) # 佇列，儲存待造訪的節點

    while queue:

        # 取出佇列中最前面的節點 (先進入的先出去)

        current_node = queue.popleft() 

        print(f”造訪節點: {current_node}”)

        # 遍歷所有鄰近節點

        for neighbor in graph[current_node]:

            # 如果鄰近節點還沒被造訪

            if neighbor not in visited:

                # 標記為已造訪

                visited.add(neighbor)

                # 將鄰近節點加入佇列 (留待後面造訪)

                queue.append(neighbor)

Depth-First Search (DFS) 深度優先搜尋

一條路走到底。就像走迷宮一樣，先選擇一個方向，盡可能地走到底，直到無路可走才回溯 (Backtrack)，嘗試另一個方向。

  • 機制 : 從起點出發，選擇一條分支不斷往下走，直到達到末端節點 (Leaf Node)，然後返回 (Backtrack) 到上一個有未探索分支的節點，繼續向下。
  • 資料結構 : 使用 堆疊 (Stack) 或遞迴 (Recursion) 來儲存待造訪的節點，體現「後進先出」的深度特性。
  • 用途 : 檢查圖的連通分量、拓撲排序、尋找所有可能路徑等。

DFS 程式碼骨架 (遞迴版)

def dfs(graph, start_node, visited):

    # 標記當前節點為已造訪

    visited.add(start_node)

    print(f”造訪節點: {start_node}”) 

    # 遍歷所有鄰近節點

    for neighbor in graph[start_node]:

        # 如果鄰近節點還沒被造訪

        if neighbor not in visited:

            # 遞迴呼叫，繼續深入探索這條分支

            dfs(graph, neighbor, visited)

貪婪演算法 (Greedy Algorithms)

貪婪演算法 (Greedy Algorithms)

它在每一步都做出當前看來是最佳的選擇，希望這一系列的局部最佳選擇能最終導致全局的最佳結果。

局部最佳 (Local Optimal Choice)：在每一步選擇中，只考慮當前步驟的最佳利益，不考慮未來可能產生的後果。

不可回溯 (Irrevocable)：一旦做出選擇，就不能撤銷。

簡單快速：實作相對簡單，運算速度通常很快。

貪婪演算法只有在問題具有以下特性時才能保證找到全局最佳解：

  1. 貪婪選擇性質 (Greedy Choice Property)：局部最佳選擇可以導致全局最佳解。
  2. 最佳子結構性質 (Optimal Substructure)：問題的最佳解包含其子問題的最佳解。

動態規劃 (Dynamic Programming, DP)

它適用於具有重疊子問題 (Overlapping Subproblems) 和最佳子結構特性的複雜問題。

分解子問題：將一個複雜的大問題分解成更小的、相互關聯的子問題。

儲存結果 (Memoization / Tabulation)：DP 的關鍵在於它會將每個子問題的解儲存起來。這樣當遇到重複的子問題時，就可以直接查詢結果，而不需要重新計算。這就是解決「重疊子問題」的機制。

從底向上 (Bottom-Up)：通常從最簡單的子問題開始解決，然後用這些解來構建和解決更大的子問題，直到最終解決整個問題。

當問題滿足以下條件時，應該考慮使用動態規劃：

  1. 重疊子問題 (Overlapping Subproblems)：許多子問題會被重複計算多次。
  2. 最佳子結構性質 (Optimal Substructure)：問題的最佳解是透過其子問題的最佳解組合而成的。

排程演算法 (Scheduling Algorithms)

排程演算法是用來分配資源的規則，在伺服器環境中，它確保工作負載在多個工作處理單元之間得到公平或優化的分配。

  1. 作業系統 (OS Level)：決定 CPU 核心如何分配給不同的執行緒或程序（例如輪詢、先到先服務）。
  2. 負載平衡器 (Load Balancer Level)：決定傳入的網路請求應被分配到哪個後端伺服器。
  • 常見策略 (用於負載平衡器)：
    • 輪詢 (Round-Robin)：按順序將請求分配給伺服器，簡單且公平。
    • 最少連線 (Least Connection)：將請求發送給當前連線數最少的伺服器。
    • 加權輪詢 (Weighted Round-Robin)：根據伺服器的處理能力（權重）來分配請求。

均衡資源利用 : 防止任何單一伺服器過載，確保所有伺服器的資源得到平均利用。

提高響應時間 : 透過將請求發送到最空閒的伺服器，可以顯著減少請求的等待時間。

提高容錯性 : 如果一個伺服器發生故障，排程器可以自動將流量重定向到其他健康的伺服器。

In-Memory Caching 記憶體快取

In-Memory Caching  記憶體快取

  • 將經常存取的資料暫時儲存在 RAM 中，以便快速檢索。
  • 適合小規模應用程序，快取經常存取的數據，如電子商務產品列表、計算結果、使用者對話、最近觀看影片、熱門項目資料、搜尋結果。

可擴展性有限：在單一伺服器上運行，限製成長。

資料持久性：伺服器重啟時遺失快取資料。

Distributed Caching  分散式快取

  • 跨多個伺服器儲存快取數據，提高可擴充性和可用性。
  • 適用於需要快速、可靠地存取共享資料的基於雲端的應用程式和微服務。

延遲：由於網路通信，比記憶體快取稍慢。

複雜性：需要額外的基礎設施和管理。

Absolute Expiration 絕對過期 : 無論存取頻率如何，資料都會在固定時間後過期。

  • 設定1分鐘後就過期。
  • string key = “absolute-key”;
  • string value = “This is an absolute expiration item.”;
  • await db.StringSetAsync(key, value);
  • db.KeyExpire(key, TimeSpan.FromMinutes(1));
  • 1分鐘後就會變成null
  • Console.WriteLine($”Cached Value after expiration: {await db.StringGetAsync(key)}”);

Sliding Expiration 滑動過期 : 每次存取資料時，過期計時器都會重設，確保用戶在活動時保持登入狀態，但在不活動後將其登出。

  • string slidingkey = “sliding-key”;

string slidingvalue = “Sliding expiration data”;

儲存30秒

await db.StringSetAsync(slidingkey, slidingvalue, TimeSpan.FromSeconds(30));

for (int i = 0; i < 3; i++) {

確認有沒有活動

RedisValue cachedValue = await db.StringGetAsync(slidingkey);

if (!cachedValue.IsNullOrEmpty){

    Console.WriteLine($”Access {i + 1}: Cached Value: {cachedValue}”);

有活動就在加30秒重設時間，沒有就過期

    db.KeyExpire(slidingkey, TimeSpan.FromSeconds(30)); 

}else{

    Console.WriteLine($”Access {i + 1}: Key ‘{slidingkey}’ does not exist.”);

    break;  }

Dependent Expiration 依賴過期 : 當相關資料被更新或刪除時，快取資料將失效，當產品詳細資訊變更時更新，確保使用者始終看到最新資訊。，有助於確保庫存管理或分層資料的一致性。 

  • string parentKey = “product”;  

string childKey = “inventory”;

建立父子項目關係

await db.StringSetAsync(parentKey, “Product data”);

await db.StringSetAsync(childKey, “Inventory data”);

可以看資訊變化 : Console.WriteLine($”Parent Key: {await db.StringGetAsync(parentKey)}”);

當資訊有變化就會同步更新

await db.StringSetAsync(parentKey, “Updated product data”);

if (await db.StringGetAsync(parentKey) == “Updated product data”) {

    Console.WriteLine(“Parent updated. Expiring dependent entry…”);

    await db.KeyDeleteAsync(childKey); }

這時候子項目就會被刪除

Console.WriteLine($”Child Key: {await db.StringGetAsync(childKey)}”);

Manual Invalidation 手動失效：當發生更新時需要明確刪除快取項目。

  • cache.RemoveAsync(key)
  • 嚴格的一致性需求（例如定價更新）

Time-to-Live 生存時間 (TTL)：為每個緩存項目設置一個固定的絕對存活時間，一旦過了這個時間，項目就會被移除。

  • AbsoluteExpirationRelativeToNow = TimeSpan.FromMinutes(10)
  • 高波動性資料（例如股票價格）
擴展性原則

擴展性原則:

  • 水平擴展 (Horizontal Scaling): 透過增加更多普通的伺服器來分擔負載。這是現代雲端架構的主流，具備高彈性與容錯能力。
  • 垂直擴展 (Vertical Scaling): 增強單一伺服器的硬體資源 (CPU, RAM)。此方式有其物理與成本上限，且存在單點故障風險。
  • 彈性 (Elasticity): 系統能根據即時流量變化，自動化地增加或減少資源（伺服器數量），以達到效能與成本的最佳平衡。
  • 容錯 (Fault Tolerance): 系統在部分元件（如伺服器、資料庫）發生故障時，仍能透過備援機制維持整體運作，不影響使用者。

Microservices Architecture 微服務架構

將應用程式建構成一系列透過 API 進行通訊的小型獨立服務。

  • 獨立服務：每項服務專注於特定功能，並且可以獨立擴展。
  • API 通訊：輕量級 API 實作服務之間的無縫互動。
  • 每個服務一個資料庫：每個微服務都有自己的資料庫，以防止瓶頸並提高效率。
  • 故障隔離：一個服務的故障不會破壞整個系統。

Event-Driven Architecture (EDA) 事件驅動架構

過支援鬆散耦合服務之間的非同步通訊來增強可擴展性，讓系統能夠有效率地處理高負載，而不會因依賴關係而降低速度。

  • 生產者與消費者：生產者生成事件，消費者獨立地對其做出反應。
  • 訊息代理：非同步管理事件傳遞，確保資料流暢。
  • 解耦：服務獨立運行，從而可以輕鬆擴展各個元件。

非同步處理 (Asynchronous Processing):

  • 將耗時的任務（如發送電子郵件、生成報表、影片轉檔）從主請求流程中分離出來，交由背景工作佇列（如 RabbitMQ, Kafka）處理。這能讓 API 立即回應使用者，避免長時間等待，從而極大地提升使用者體驗與系統的吞吐量。

Load Balancing Concepts 負載平衡：

  • Load Balancer 負載平衡器：將傳入流量分配到多個伺服器以防止塞車。

  • Round Robin Algorithm 循環演算法 : 選擇循環策略以避免任何單一伺服器過載。

  • 健康檢查：定期檢查，如果伺服器發生故障，流量將被重新導向到健康的伺服器。

  • Sticky Sessions 黏性會話：在會話期間保持使用者連線到同一伺服器，確保線上購物車等服務的連續性。

Traffic Distribution Strategies 流量分配

  • Stateless Services 無狀態服務 : 應用程式邏輯是無狀態的，以允許水平擴展。

  • Least Connections 最少連接：將流量定向到具有最少活動連接的伺服器。

  • Weighted Round Robin 加權循環：根據伺服器容量分配不同的流量負載

  • IP 雜湊：根據使用者的 IP 位址路由流量，確保伺服器分配的一致性。

  • 任何會話資料都儲存在分散式快取中（例如 Redis）。

Caching Layer 快取層：

  • Redis 用於頻繁存取的數據，以減少資料庫負載。

API 速率限制 (Rate Limiting):

  • 目的: 限制單一使用者或 IP 在特定時間內的請求數量，是保護後端服務的重要防線。
  • 限流機制：常見的演算法有令牌桶 (Token Bucket) 或漏桶 (Leaky Bucket)。
    • 令牌桶：允許短時間內的高峰請求，只要桶內有令牌就可以通過。
    • 漏桶：以固定速率處理請求，多餘的請求會被丟棄或排隊。
  • 效益:
    • 防止惡意攻擊: 有效抵禦分散式阻斷服務 (DDoS) 攻擊和密碼暴力破解。
    • 確保資源公平分配: 防止少數惡意或行為異常的使用者耗盡所有系統資源，保障正常使用者的服務品質。

維護系統穩定性: 避免因突發的流量洪峰導致後端服務崩潰。

發佈留言