一致性哈希中的溢出问题：为什么你的集群比你想象的更容易爆满

1. 环的建立：
   ┌─────────────────────────────────────┐
   │                 0                   │
   │         ┌───────────────┐          │
   │    3    │               │    1     │
   │         │   哈希环      │          │
   │         └───────────────┘          │
   │                 2                   │
   └─────────────────────────────────────┘

2. 服务器分配：
   - Server1 → Hash(Server1) → 位置 A
   - Server2 → Hash(Server2) → 位置 B
   - Server3 → Hash(Server3) → 位置 C

3. 数据定位：
   - Data1 → Hash(Data1) → 环上位置 X
   - 顺时针找到第一个服务器 → Server2
   - 存储到 Server2

传统方法：server_id = hash(key) % N

问题：当服务器数量 N 改变时，几乎所有数据都需要重新分配！

示例：
- 3 个服务器：key1 → hash=7 → 7%3=1 → Server1
- 增加到 4 个：key1 → hash=7 → 7%4=3 → Server3 [需要数据迁移！]

数据迁移率：~100% × (1 - 1/N_new)

添加/删除一个服务器时：
- 平均只影响 1/N 的数据
- 其他数据保持不动
- 对系统影响最小化

示例：
- 初始 3 个服务器
- 添加 Server4
- 只有 Server4 附近的数据需要重新分配
- 大约 25% 的数据受影响（而不是 100%）

示例计算：
┌──────────────────────────────────────┐
│ 数据项数 n = 10                       │
│ 服务器数 m = 5                        │
│ 每服务器容量 c = 4                    │
│                                      │
│ 总容量 = m × c = 5 × 4 = 20         │
│ 负载因子 α = 10 ÷ 20 = 0.5 (50%)    │
│                                      │
│ [看起来很安全（只用了一半容量）]     │
│ [实际溢出概率：16.37%]               │
└──────────────────────────────────────┘

预期情况（错误的直觉）：
    ══      ══      ══      ══      ══
    ║║      ║║      ║║      ║║      ║║
    ═2═     ═2═     ═2═     ═2═     ═2═
   杯子1   杯子2   杯子3   杯子4   杯子5

每个杯子恰好 2 个球 [这几乎不可能发生！]

实际情况（更可能）：
    ══      ══      ══      ══      ══
    ║4║     ║1║     ║0║     ║3║     ║2║
    ═══     ══      空      ═══     ═══
   杯子1   杯子2   杯子3   杯子4   杯子5

分布不均匀！如果杯子容量只有 3，杯子1 就溢出了。

场景对比：负载因子都是 0.5

┌─────────────────────────────────────────────────────────┐
│ 场景 A：多服务器 + 小容量                                │
│ ─────────────────────────────────────                  │
│ • 5 个服务器                                            │
│ • 每个容量 2                                            │
│ • 5 个数据项                                            │
│ • 总容量 = 5 × 2 = 10                                  │
│ • 负载因子 = 5/10 = 0.5                                │
│                                                        │
│ 溢出概率：26.33% [高风险]                              │
└─────────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────────┐
│ 场景 B：少服务器 + 大容量                                │
│ ─────────────────────────────────────                  │
│ • 2 个服务器                                            │
│ • 每个容量 5                                            │
│ • 5 个数据项                                            │
│ • 总容量 = 2 × 5 = 10                                  │
│ • 负载因子 = 5/10 = 0.5                                │
│                                                        │
│ 溢出概率：0% [安全]                                    │
└─────────────────────────────────────────────────────────┘

场景 A 的可能分布示例：

分布 1（均匀）：
[1] [1] [1] [1] [1]  → 无溢出 ✓
 1   1   1   1   1

分布 2（稍微不均）：
[2] [2] [1] [0] [0]  → 无溢出 ✓
 2   2   1   0   0

分布 3（不均匀）：
[3] [1] [1] [0] [0]  → 溢出！
 ↑
容量=2，但有3个数据

发生概率：约 26.33%

配置对比：总容量都是 20

┌──────────────────────────────────────┐
│ 配置 1：少而大                        │
│ • 5 服务器 × 容量 4                  │
│ • 10 数据项                          │
│ • 溢出概率：16.37%                   │
└──────────────────────────────────────┘
              VS
┌──────────────────────────────────────┐
│ 配置 2：多而小                        │
│ • 10 服务器 × 容量 2                 │
│ • 10 数据项                          │
│ • 溢出概率：26.30% [更高风险]       │
└──────────────────────────────────────┘

配置 2 的服务器数量翻倍，但溢出风险反而增加了 60%！

参数定义：
┌────────────────────────────────────────┐
│ n  = 球的数量（数据项）                 │
│ m  = 盒子数量（服务器）                 │
│ c  = 每个盒子的容量（服务器容量）        │
│                                        │
│ 规则：                                  │
│ • 每个球独立随机放入某个盒子            │
│ • 每个盒子被选中的概率：1/m             │
│ • 放置过程互相独立                      │
└────────────────────────────────────────┘

问题：P(至少一个盒子装了 > c 个球) = ?

初始：
  P(0, [0,0]) = 1.0

放第 1 个球：
  → [1,0]  概率 1/2
  → [0,1]  概率 1/2

  P(1, [1,0]) = 0.5
  P(1, [0,1]) = 0.5

放第 2 个球：
  从 [1,0] 可以到：
    → [2,0]  概率 0.5 × 1/2 = 0.25
    → [1,1]  概率 0.5 × 1/2 = 0.25

  从 [0,1] 可以到：
    → [1,1]  概率 0.5 × 1/2 = 0.25
    → [0,2]  概率 0.5 × 1/2 = 0.25

  P(2, [2,0]) = 0.25
  P(2, [1,1]) = 0.25 + 0.25 = 0.5
  P(2, [0,2]) = 0.25

放第 3 个球：
  从 [2,0] 可以到：
    → [3,0]  溢出！不计入
    → [2,1]  概率 0.25 × 1/2 = 0.125

  从 [1,1] 可以到：
    → [2,1]  概率 0.5 × 1/2 = 0.25
    → [1,2]  概率 0.5 × 1/2 = 0.25

  从 [0,2] 可以到：
    → [1,2]  概率 0.25 × 1/2 = 0.125
    → [0,3]  溢出！不计入

  P(3, [2,1]) = 0.125 + 0.25 = 0.375
  P(3, [1,2]) = 0.25 + 0.125 = 0.375

不溢出概率 = 0.375 + 0.375 = 0.75
溢出概率 = 1 - 0.75 = 0.25 (25%)

决策树：
┌─────────────────────────────────────────┐
│ 开始                                    │
└──────────┬──────────────────────────────┘
           │
           ↓
    m ≤ 15 且 n ≤ 50 ?
           │
    ┌──────┴──────┐
   是              否
    │              │
    ↓              ↓
使用精确        m × n ≤ 500 ?
动态规划            │
                ┌───┴───┐
               是       否
                │        │
                ↓        ↓
            使用近似    只能用
            （可靠）    泊松近似

// 计算一致性哈希溢出概率（精确）
function calculateOverflowProbability(numItems, numBins, binCapacity) {
    // 使用动态规划
    // dp[i][state] = 放置前 i 个球后，状态为 state 的概率

    // 简化：使用数组表示每个 bin 的当前球数
    // 状态空间太大时使用近似
    if (numBins > 20 || numItems > 100) {
        return calculateOverflowApprox(numItems, numBins, binCapacity);
    }

    // 初始化：0 个球，所有 bin 都是空的
    let states = new Map();
    states.set(Array(numBins).fill(0).join(','), 1.0);

    // 逐个放球
    for (let ball = 0; ball < numItems; ball++) {
        let newStates = new Map();

        for (let [stateKey, prob] of states) {
            let state = stateKey.split(',').map(Number);

            // 尝试将球放入每个 bin
            for (let bin = 0; bin < numBins; bin++) {
                if (state[bin] < binCapacity) {
                    let newState = [...state];
                    newState[bin]++;
                    let newKey = newState.join(',');
                    let newProb = prob / numBins;

                    newStates.set(newKey, (newStates.get(newKey) || 0) + newProb);
                }
            }
        }

        states = newStates;
    }

    // 计算不溢出的总概率
    let noOverflowProb = 0;
    for (let prob of states.values()) {
        noOverflowProb += prob;
    }

    return 1 - noOverflowProb;
}

// 泊松近似
function calculateOverflowApprox(numItems, numBins, binCapacity) {
    let lambda = numItems / numBins;

    // 单个 bin 不溢出的概率（泊松分布）
    let noOverflowSingle = 0;
    for (let k = 0; k <= binCapacity; k++) {
        noOverflowSingle += Math.pow(lambda, k) * Math.exp(-lambda) / factorial(k);
    }

    // 至少一个 bin 溢出
    return 1 - Math.pow(noOverflowSingle, numBins);
}

function factorial(n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

import math
from scipy.stats import poisson

def overflow_probability_exact(n_items, n_bins, capacity):
    """精确计算溢出概率（适用于小规模）"""
    # 使用递归 + 记忆化
    from functools import lru_cache

    @lru_cache(maxsize=None)
    def dp(balls_left, state):
        if balls_left == 0:
            return 1.0

        total_prob = 0.0
        for bin_idx in range(n_bins):
            if state[bin_idx] < capacity:
                new_state = list(state)
                new_state[bin_idx] += 1
                total_prob += dp(balls_left - 1, tuple(sorted(new_state))) / n_bins

        return total_prob

    initial_state = tuple([0] * n_bins)
    no_overflow_prob = dp(n_items, initial_state)
    return 1 - no_overflow_prob

def overflow_probability_approx(n_items, n_bins, capacity):
    """泊松近似（适用于大规模）"""
    lambda_val = n_items / n_bins

    # P(单个 bin 不溢出)
    no_overflow_single = poisson.cdf(capacity, lambda_val)

    # P(至少一个 bin 溢出)
    return 1 - no_overflow_single ** n_bins

# 示例
print(f"10 items, 5 bins, capacity 4:")
print(f"  Exact: {overflow_probability_exact(10, 5, 4):.4f}")
print(f"  Approx: {overflow_probability_approx(10, 5, 4):.4f}")