打造支援過載自適應與動態擴容的負載均衡服務：演算法與實作全解析

問題場景

一組伺服器提供同一服務，需求：

1. 客戶端請求**均勻分散**到各節點。
2. 某節點**過載/宕機**時自動減少分派，恢復後自動回歸。
3. **動態新增/移除**節點時，無需重啟服務，自動重新平衡。

核心演算法：一致性雜湊環 + 虛擬節點

採用「大盒子」概念：建立固定大小的雜湊環（如 1000 格），將每台實體伺服器映射為多個**虛擬節點**均勻分佈於環上。請求以隨機數或金鑰雜湊落點，順時針尋找最近的虛擬節點所屬伺服器。

優勢

• 新增/移除節點**僅影響鄰近區段**請求，避免全量重新分佈（雪崩效應）。
• 虛擬節點數可依權重調整，實現異構硬體負載比例分配。
• 過載節點標記為「警告」，路由邏輯跳過並轉向下一個健康節點。

核心介面設計

public abstract class HashBase
{
    protected int _maxHashItemCount;
    protected readonly object _syncRoot = new object();
    protected Dictionary _ring;          // 雜湊環：位置 -> 節點
    protected Dictionary _loadWarning;  // 節點 -> 是否過載

    protected abstract int GetRandom();                    // 隨機數/雜湊值產生
    protected abstract T SelectOtherUnLoadWarningItem(T current); // 過載時選擇備援節點

    public HashBase(int maxHashItemCount, IList items) => Init(maxHashItemCount, items);

    protected void Init(int maxHashItemCount, IList items)
    {
        lock (_syncRoot)
        {
            _maxHashItemCount = maxHashItemCount;
            _ring = new Dictionary(maxHashItemCount);
            // 簡易輪詢分佈（生產建議用 Ketama 演算法）
            for (int i = 0; i < maxHashItemCount; i++)
                _ring[i] = items[i % items.Count];

            _loadWarning = items.ToDictionary(k => k, v => false);
        }
    }

    public T GetItem()
    {
        int pos = GetRandom();
        lock (_syncRoot)
        {
            T node = _ring[pos];
            if (_loadWarning[node]) node = SelectOtherUnLoadWarningItem(node);
            return node;
        }
    }

    public void SetLoadWarning(T node) => lock (_syncRoot) _loadWarning[node] = true;
    public void UnsetLoadWarning(T node) => lock (_syncRoot) _loadWarning[node] = false;

    public virtual void ReConfig(int maxHashItemCount, IList items) => Init(maxHashItemCount, items);
}

具體實作：SimpleHashImp

public class SimpleHashImp : HashBase
{
    private readonly Random _random;
    public SimpleHashImp(int seed, int maxHashItemCount, IList items)
        : base(maxHashItemCount, items) => _random = new Random(seed);

    protected override int GetRandom() => _random.Next(_maxHashItemCount);

    protected override string SelectOtherUnLoadWarningItem(string current)
    {
        foreach (var kv in _loadWarning)
            if (!kv.Value) return kv.Key;
        throw new ApplicationException("503: All nodes overloaded");
    }

    public override void ReConfig(int maxHashItemCount, IList items)
    {
        base.Init(maxHashItemCount, items); // 重建環
    }
}

壓力測試與行為驗證

static void Main()
{
    var nodes = new List { "A", "B", "C" };
    var lb = new SimpleHashImp(10, 20, nodes); // 20 格環

    for (int i = 0; i < 100; i++)
    {
        if (i == 10) { lb.SetLoadWarning("A"); Console.WriteLine(">>> Node A OVERLOAD"); }
        if (i == 20) { lb.UnsetLoadWarning("A"); Console.WriteLine(">>> Node A RECOVERED"); }
        if (i == 30) { nodes.Add("D"); lb.ReConfig(100, nodes); Console.WriteLine(">>> ADD Node D, RESIZE RING"); }

        Console.WriteLine($"Req {i:D3} -> {lb.GetItem()}");
        Thread.Sleep(100);
    }
}

輸出觀察點：

• 前 10 次請求均勻分佈 A/B/C。
• 第 11~20 次請求**完全跳過 A**，僅落在 B/C。
• 第 21 次起 A 恢復分派。
• 第 31 次環擴大為 100 格，新節點 D 開始接收請求，分佈再次均勻。

生產環境關鍵優化

總結

本文實作了一個**可擴充、可觀測、生產就緒**的負載均衡核心：

1. 雜湊環 + 虛擬節點實現平滑擴縮容。
2. 過載標記與備援路由保證高可用。
3. 抽象基底類別便於替換演算法 (Random → Ketama → Rendezvous Hashing)。

實際專案建議直接採用成熟框架（NGINX、HAProxy、Envoy、YARP、Polly + HttpClientFactory），並在應用層實作業務級熔斷與重試。