引言

在分佈式系統中，我們經常需要實現負載均衡、流量分配、A/B 測試等功能。這些場景的核心問題是：如何按照預設的權重比例，在多個候選項中進行隨機選擇？ 更具挑戰性的是，當多個進程同時運行、隨時可能加入或退出時，如何保證整體的選擇分佈仍然符合預期的權重比例？

本文將從最簡單的均勻隨機選擇開始，逐步深入到加權隨機選擇，最後解決多進程環境下的分佈一致性問題，並給出嚴格的數學證明。

完整代碼：https://go.dev/play/p/0h97DRfph-2

第一步：簡單隨機選擇

需求 1.0：從列表中隨機選一個

假設我們有一個服務器列表：[A, B, C, D]，需要隨機選擇其中一個來處理請求。

樸素實現：

func SimpleSelect(candidates []string) string {
    n := len(candidates)
    idx := rand.Intn(n)  // 生成 [0, n) 的隨機整數
    return candidates[idx]
}

這種方法簡單直接，每個候選項被選中的概率都是 $\frac{1}{n}$，即均勻分佈。

問題

但現實場景中，不同服務器的性能往往不同。高性能服務器應該承擔更多流量，低性能服務器應該承擔較少流量。均勻分佈無法滿足這個需求。

第二步：加權隨機選擇

需求 2.0：按權重選擇

現在我們給每個服務器分配一個權重：

總權重 $W = 5 + 3 + 2 + 1 = 11$

我們希望服務器 A 被選中的概率是 $\frac{5}{11}$，服務器 B 被選中的概率是 $\frac{3}{11}$，以此類推。

算法 2.0：累積權重法

核心思想：將權重值看作一條數軸上的線段長度，生成隨機數落在哪個線段，就選擇對應的候選項。

服務器:  A  A  A  A  A  B  B  B  C  C  D
數軸:   [0-------------5--------8-----10-11)
累積:    0             5        8    10 11

算法步驟：

1. 計算累積權重數組：$CW = [w_1, w_1+w_2, w_1+w_2+w_3, ..., W]$

   • 對於示例：$CW = [5, 8, 10, 11]$
2. 生成 $[0, W)$ 範圍內的隨機數 $r$
3. 找到第一個滿足 $CW[i] > r$ 的索引 $i$，返回候選項 $i$

為什麼這樣能保證權重比例？

對於候選項 $i$（權重為 $w_i$），被選中的條件是：

$$CW[i-1] \leq r < CW[i]$$

這個區間的長度恰好是 $w_i$，因此被選中的概率為：

$$P(\text{選中}\ i) = \frac{w_i}{W}$$

完美符合權重比例！

優化：二分查找

累積權重數組是單調遞增的，可以用二分查找將查找複雜度從 $O(n)$ 降低到 $O(\log n)$：

func BinarySearchSelect(cumWeights []int64, totalWeight int64) int {
    r := rand.Int63n(totalWeight)  // [0, totalWeight)
    left, right := 0, len(cumWeights)-1
    
    for left < right {
        mid := left + (right - left) / 2
        if cumWeights[mid] <= r {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}

第三步：多進程環境的挑戰

需求 3.0：分佈式場景

現在問題變得複雜了：

• 系統部署了多個進程（或服務實例），每個進程都獨立執行選擇算法
• 進程數量動態變化：可能隨時有新進程啓動，或者舊進程崩潰退出
• 沒有中心化的協調服務（如果有的話，就失去了分佈式的意義）

核心問題：如何保證在這種動態、分佈式的環境下，總體的選擇分佈仍然符合權重比例？

可能的擔憂

1. 同步問題：多個進程同時選擇，會不會相互干擾？
2. 分佈偏差：進程 1 可能恰好多選了 A，進程 2 多選了 B，總體會不會偏離？
3. 動態變化：新進程加入時，會不會打破已有的分佈？

第四步：解決方案 —— 獨立同分布採樣

設計原則

關鍵洞察：如果每個進程都獨立地按照相同的權重分佈進行採樣，那麼無論有多少進程、進程如何變化，總體分佈在統計意義上一定收斂到權重比例。

實現要點

1. 配置共享，狀態獨立

   • 所有進程共享相同的候選列表和權重配置（可以通過配置文件、環境變量等方式）
   • 但每個進程的隨機數生成是完全獨立的，不依賴共享狀態

2. 加密安全的隨機數

   • 使用 crypto/rand 而非 math/rand
   • 保證每個進程的隨機數序列高質量且彼此獨立

3. 無狀態設計

   • 不需要記錄"已經選了多少次 A"
   • 不需要進程間通信
   • 每次選擇都是獨立事件

完整代碼實現

type WeightedSelector struct {
    candidates  []Candidate
    totalWeight int64
    cumWeights  []int64  // 累積權重數組
}

func (ws *WeightedSelector) Select() (Candidate, error) {
    // 使用加密安全的隨機數生成器
    randomNum, err := rand.Int(rand.Reader, big.NewInt(ws.totalWeight))
    if err != nil {
        return Candidate{}, err
    }
    
    randValue := randomNum.Int64()
    
    // 二分查找
    left, right := 0, len(ws.cumWeights)-1
    for left < right {
        mid := left + (right - left) / 2
        if ws.cumWeights[mid] <= randValue {
            left = mid + 1
        } else {
            right = mid
        }
    }
    
    return ws.candidates[left], nil
}

第五步：數學證明

現在我們給出嚴格的數學證明，説明為什麼這個算法在多進程環境下是正確的。

符號定義

• 候選項集合：$\{C_1, C_2, ..., C_n\}$
• 權重集合：$\{w_1, w_2, ..., w_n\}$，其中 $w_i > 0$
• 總權重：$W = \sum_{i=1}^{n} w_i$
• 進程數量：$k$（可以動態變化）
• 第 $j$ 個進程的選擇次數：$m_j$
• 總選擇次數：$M = \sum_{j=1}^{k} m_j$

定理：多進程獨立採樣的分佈一致性

定理：在多進程獨立同分布採樣的情況下，候選項 $C_i$ 被選中的總次數 $N_i$ 滿足：

$$\lim_{M \to \infty} \frac{N_i}{M} = \frac{w_i}{W} \quad \text{(依概率)}$$

即，當總選擇次數 $M$ 足夠大時，候選項 $i$ 的實際選擇比例依概率收斂到其權重比例。

證明

第一步：單次選擇的概率

根據算法設計，每次選擇時，候選項 $C_i$ 被選中當且僅當隨機數 $r \in [CW_{i-1}, CW_i)$，其中 $CW_0 = 0$。

該區間長度為 $w_i$，因此：

$$P(C_i \text{ 被選中}) = \frac{w_i}{W}$$

第二步：單個進程的期望

設第 $j$ 個進程執行 $m_j$ 次選擇，令 $X_{ji}$ 為該進程中 $C_i$ 被選中的次數。

由於每次選擇是獨立的，$X_{ji}$ 服從二項分佈 $B(m_j, \frac{w_i}{W})$，其期望為：

$$E[X_{ji}] = m_j \cdot \frac{w_i}{W}$$

第三步：多進程的總期望

所有進程中 $C_i$ 被選中的總次數為：

$$N_i = \sum_{j=1}^{k} X_{ji}$$

由期望的線性性質：

$$E[N_i] = \sum_{j=1}^{k} E[X_{ji}] = \sum_{j=1}^{k} m_j \cdot \frac{w_i}{W} = M \cdot \frac{w_i}{W}$$

這説明，無論進程數量如何變化，只要總選擇次數是 $M$，$C_i$ 被選中的期望次數總是 $M \cdot \frac{w_i}{W}$。

第四步：大數定律保證收斂

由於 $X_{ji}$ 都是獨立同分布的隨機變量（每個進程獨立採樣），我們可以應用弱大數定律：

$$\lim_{M \to \infty} P\left(\left|\frac{N_i}{M} - \frac{w_i}{W}\right| > \epsilon\right) = 0 \quad \forall \epsilon > 0$$

即，當 $M$ 足夠大時，$\frac{N_i}{M}$ 以高概率接近 $\frac{w_i}{W}$。

第五步：方差分析（可選）

為了更精確地刻畫收斂速度，我們計算方差：

$$\text{Var}(N_i) = \sum_{j=1}^{k} \text{Var}(X_{ji}) = \sum_{j=1}^{k} m_j \cdot \frac{w_i}{W} \cdot \left(1 - \frac{w_i}{W}\right)$$

$$= M \cdot \frac{w_i}{W} \cdot \left(1 - \frac{w_i}{W}\right)$$

標準差為：

$$\sigma(N_i) = \sqrt{M \cdot \frac{w_i}{W} \cdot \left(1 - \frac{w_i}{W}\right)}$$

相對誤差的標準差為：

$$\frac{\sigma(N_i)}{E[N_i]} = \sqrt{\frac{1}{M} \cdot \frac{W - w_i}{w_i}} = O\left(\frac{1}{\sqrt{M}}\right)$$

這説明，誤差以 $\frac{1}{\sqrt{M}}$ 的速度遞減，收斂速度是根號級別的。

推論：進程動態變化的影響

推論 1（進程加入）：新進程加入相當於增加 $M$，會加快收斂速度，但不改變期望分佈。

推論 2（進程退出）：進程退出不影響已產生的樣本，只是減少了未來的採樣次數。由於已有樣本仍然有效，總體分佈不受影響。

推論 3（進程組合無關性）：無論是 10 個進程各選 100 次，還是 1 個進程選 1000 次，或者任意其他組合，只要 $M = 1000$，期望分佈和收斂性質完全相同。

關鍵假設的驗證

我們的證明依賴於以下假設，現在驗證它們在實現中是否滿足：

1. 獨立性：✓ 每個進程使用獨立的 crypto/rand.Reader，隨機數序列互不相關
2. 同分布：✓ 所有進程加載相同的配置，使用相同的算法
3. 正整數權重：✓ 代碼中檢查 w > 0
4. 足夠大的 $M$：✓ 在實際應用中，選擇次數通常達到成千上萬次

實驗驗證

我們進行了三組實驗來驗證理論：

實驗 1：單進程，10,000 次選擇

結論：誤差在 ±1% 以內，符合預期。

實驗 2：10 進程，每進程 1,000 次（共 10,000 次）

結論：多進程結果與單進程幾乎一致，證明進程數量不影響分佈。

實驗 3：100 進程，每進程 1,000 次（共 100,000 次）

結論：隨着 $M$ 增加到 100,000，誤差降低到 ±0.1% 以內，完美驗證了 $O(\frac{1}{\sqrt{M}})$ 的收斂速度。

總結

本文從簡單的均勻隨機選擇出發，逐步引入權重、多進程等複雜因素，最終設計出一個既簡單又嚴謹的分佈式加權隨機選擇算法。

核心要點

1. 算法設計：累積權重 + 二分查找，時間複雜度 $O(\log n)$
2. 分佈式原則：獨立同分布採樣，無需進程間同步
3. 數學保證：大數定律確保收斂性，方差分析預測誤差
4. 實踐驗證：實驗結果與理論完全吻合

適用場景

• 負載均衡（根據服務器性能分配流量）
• A/B 測試（按比例分配用户到不同版本）
• 分佈式限流（按權重分配配額）
• 隨機抽獎（按中獎概率分配獎品）

關鍵優勢

✓ 無狀態：不需要記錄歷史，每次選擇都是獨立的
✓ 高性能：$O(\log n)$ 時間複雜度，適合高頻調用
✓ 分佈式友好：天然支持多進程，無需協調
✓ 數學嚴謹：有完整的理論保證和實驗驗證
✓ 加密安全：使用 crypto/rand，適合安全敏感場景

這個算法的美妙之處在於：複雜性隱藏在數學之中，實現卻極其簡單。只要遵循獨立同分布的原則，複雜的多進程協調問題就自然而然地解決了。