负载均衡算法：P2C / EWMA / 平滑加权轮询

负载均衡看似简单——把请求分给后端就行了嘛。但当你真正面对 10K 个后端节点、毫秒级延迟要求、节点随时可能宕机的场景时，才会发现这里面处处是坑。

本文从最基础的轮询算法出发，一路讲到 P2C、EWMA、一致性哈希、Maglev，再到工程实践中的 subsetting、健康检查、熔断集成。最后给出一个完整的 C 语言 P2C+EWMA 实现。

一、负载均衡要解决什么问题

负载均衡器（Load Balancer）位于客户端和一组后端服务器（backend pool）之间，核心目标是：

最大化吞吐：让每个后端都尽量满载工作，不出现”忙的忙死，闲的闲死”。
最小化延迟：把请求分配给响应最快的节点，而不是随机撞运气。
容错：当节点宕机或变慢时，能自动避开。
公平性：对不同权重的后端按比例分配。
亲和性：同一个 key 的请求尽量打到同一个节点（缓存友好）。

这五个目标互相矛盾。轮询能做到公平，但不关心延迟；最小连接数关心负载，但不关心亲和性；一致性哈希关心亲和性，但不关心负载。没有银弹，只有 trade-off。

在理论模型中，我们通常用球-箱模型（balls-into-bins）来分析：将 n 个请求（球）随机投入 n 个后端（箱），关心的是最大负载 （max load，即最满的那个箱子里有多少球）。

策略	最大负载（高概率）
随机投球（d=1）	O(ln n / ln ln n)
P2C（d=2）	O(ln ln n)
完美均衡	1

从 O(ln n / ln ln n) 到 O(ln ln n)，仅仅多看一眼，就产生了指数级的改善。这就是 “power of two choices” 的核心洞察。

二、轮询与加权轮询

2.1 简单轮询

最朴素的方法：维护一个计数器，每次请求 counter++ % n。

// 简单轮询
int round_robin(int *counter, int n) {
    int idx = (*counter) % n;
    *counter = (*counter + 1);
    return idx;
}

优点：实现简单，绝对公平。缺点：完全不考虑后端的实际处理能力差异。

2.2 加权轮询（Weighted Round-Robin）

给每个后端分配一个权重 w_i，权重越大，分到的请求越多。朴素做法是”展开法”：权重为 5 的节点在列表中出现 5 次。问题是分配不均匀——可能出现前 5 个请求全打到同一节点。

2.3 Nginx 平滑加权轮询

Nginx 在 2011 年引入了平滑加权轮询（Smooth Weighted Round-Robin），确保请求在时间维度上均匀分散。算法如下：

初始化：每个节点 current_weight = 0

每次选择：
  1. 对所有节点：current_weight += effective_weight
  2. 选出 current_weight 最大的节点 best
  3. best.current_weight -= total_weight
  4. 返回 best

其中 total_weight = sum(effective_weight)。

以三个节点 {A:5, B:1, C:1} 为例，7 次选择的过程：

轮次	选择前 current_weight	选中	选择后 current_weight
1	{5, 1, 1}	A	{-2, 1, 1}
2	{3, 2, 2}	A	{-4, 2, 2}
3	{1, 3, 3}	B	{1, -4, 3}
4	{6, -3, 4}	A	{-1, -3, 4}
5	{4, -2, 5}	C	{4, -2, -2}
6	{9, -1, -1}	A	{2, -1, -1}
7	{7, 0, 0}	A	{0, 0, 0}

结果：A 出现 5 次，B 出现 1 次，C 出现 1 次，比例正好 5:1:1，且分布均匀（不会连续 5 次选 A）。

#include <stdio.h>
#include <string.h>

#define MAX_BACKENDS 64

typedef struct {
    const char *name;
    int         weight;           // 配置权重
    int         effective_weight; // 有效权重（可因故障降低）
    int         current_weight;   // 当前权重
} sw_backend_t;

typedef struct {
    sw_backend_t backends[MAX_BACKENDS];
    int          count;
    int          total_weight;
} sw_pool_t;

void sw_pool_init(sw_pool_t *pool, const char *names[], const int weights[], int n) {
    pool->count = n;
    pool->total_weight = 0;
    for (int i = 0; i < n; i++) {
        pool->backends[i].name             = names[i];
        pool->backends[i].weight           = weights[i];
        pool->backends[i].effective_weight = weights[i];
        pool->backends[i].current_weight   = 0;
        pool->total_weight += weights[i];
    }
}

int sw_pool_next(sw_pool_t *pool) {
    int best = -1;
    int max_cw = -1 << 30;

    for (int i = 0; i < pool->count; i++) {
        sw_backend_t *b = &pool->backends[i];
        b->current_weight += b->effective_weight;

        if (b->current_weight > max_cw) {
            max_cw = b->current_weight;
            best = i;
        }
    }

    if (best < 0) return -1;
    pool->backends[best].current_weight -= pool->total_weight;
    return best;
}

该算法的时间复杂度为 O(n)，空间复杂度为 O(n)，其中 n 为后端数量。在 Nginx 中通过 ngx_http_upstream_rr_peer_t 结构体实现。

三、最小连接数与加权最小连接数

3.1 最小连接数（Least Connections）

思路很直接：把请求分给当前活跃连接数最少的后端。

int least_connections(int active_conns[], int n) {
    int best = 0;
    for (int i = 1; i < n; i++) {
        if (active_conns[i] < active_conns[best]) {
            best = i;
        }
    }
    return best;
}

3.2 加权最小连接数（Weighted Least Connections）

考虑权重后，比较的不是绝对连接数，而是 active_conns[i] / weight[i]。连接数相同时，权重大的优先。

int weighted_least_connections(int active_conns[], int weights[], int n) {
    int best = 0;
    for (int i = 1; i < n; i++) {
        // 避免浮点：交叉相乘比较
        if (active_conns[i] * weights[best] < active_conns[best] * weights[i]) {
            best = i;
        }
    }
    return best;
}

3.3 局限性

最小连接数有一个隐含假设：连接数能准确反映负载。但在 gRPC 这种长连接多路复用的场景下，一个连接可能承载成千上万个并发 RPC， “连接数”这个指标完全失效。

这也是为什么 gRPC 社区选择了 P2C+EWMA 而非最小连接数。

四、Power of Two Random Choices（P2C）

4.1 理论基础

1996 年，Michael Mitzenmacher 在其博士论文 “The Power of Two Choices in Randomized Load Balancing” 中证明了一个惊人的结论：

将 n 个球放入 n 个箱子，每次随机选 d=2 个箱子，把球放进较空的那个。最大负载从 O(ln n / ln ln n) 降到 O(ln ln n)。

当 n = 1,000,000 时： - 随机：最大负载约 20（ln n / ln ln n 约 4.8，但常数较大） - P2C：最大负载约 3.8（ln ln n 约 2.9）

仅仅从”随机选 1 个”变成”随机选 2 个，挑更好的”，就产生了指数级的改善。选 3 个（d=3）也有改善，但边际收益递减。

4.2 算法伪代码

function p2c_pick(backends):
    i = random(0, len(backends))
    j = random(0, len(backends))
    while j == i:
        j = random(0, len(backends))
    if load(backends[i]) <= load(backends[j]):
        return backends[i]
    else:
        return backends[j]

4.3 为什么不选更多

直觉上，选 d 个应该更好。理论也证明了 d >= 2 时最大负载为 O(ln ln n / ln d + 1)。但实际工程中：

d=2 已经够好：从 d=2 到 d=3，改善是 ln ln n / ln 2 到 ln ln n / ln 3，在 n=10K 时差距不到 1。
更多选择 = 更多信息获取成本：在分布式系统中，获取每个节点的负载信息需要网络通信或共享内存，d 越大开销越大。
d=2 的实现最简单：两次随机 + 一次比较，没有排序。

五、P2C + EWMA：gRPC 的默认选择

5.1 问题：用什么度量”负载”

P2C 需要一个”负载”指标来比较两个候选节点。常见选择：

指标	优点	缺点
活跃连接数	实时	gRPC 多路复用下失效
CPU 使用率	反映真实负载	需要上报，延迟大
请求延迟	反映端到端体验	波动大，需要平滑
活跃 RPC 数	gRPC 友好	不反映处理时间

gRPC 的 pick_first 和 round_robin 策略不够好，社区最终选择了延迟作为指标，用 EWMA 来平滑。

5.2 EWMA（指数加权移动平均）

EWMA 对新数据赋予更高权重，对旧数据指数衰减：

EWMA_new = alpha * sample + (1 - alpha) * EWMA_old

其中 alpha 为衰减因子，越大越敏感。通常用半衰期来设置 alpha：经过半衰期时间后，旧值的影响减半。

alpha = 1 - exp(-dt / tau)

其中 dt 是距上次更新的时间间隔，tau 是时间常数（tau = half_life / ln(2)）。

5.3 gRPC 中的实现逻辑

gRPC 的 weighted_round_robin 和 pick_first 之外，社区维护了一个 P2C+EWMA 的负载均衡策略，逻辑大致如下：

对每个后端维护：
  - ewma_latency: EWMA 延迟
  - inflight:     当前在途请求数
  - last_update:  上次更新时间

pick():
  随机选两个后端 a, b
  score(x) = ewma_latency(x) * inflight(x)
  返回 score 较小的那个

on_request_complete(backend, latency):
  dt = now - backend.last_update
  alpha = 1 - exp(-dt / tau)
  backend.ewma_latency = alpha * latency + (1 - alpha) * backend.ewma_latency
  backend.inflight--
  backend.last_update = now

on_request_start(backend):
  backend.inflight++

注意 score = ewma_latency * inflight，这个乘积同时考虑了延迟和并发，是一个非常优雅的综合指标：

延迟高但空闲的节点：score 不一定大（inflight 低）
延迟低但繁忙的节点：score 也不一定小（inflight 高）

5.4 冷启动问题

新加入的节点没有延迟数据，EWMA 值为 0，会导致所有请求瞬间涌向新节点。解决方案：

预热惩罚：新节点的 score 设为一个较大的初始值，逐渐衰减。
最小 inflight：即使没有历史数据，inflight 为 0 的节点也不会比 inflight=100 的节点更有吸引力。
慢启动（slow start）：Envoy 支持对新节点设置 slow start 窗口，在窗口期内逐步增加权重。

六、一致性哈希与有界负载

6.1 经典一致性哈希（Karger 1997）

将后端和请求都映射到一个哈希环上，请求顺时针找到第一个后端。优点：增删节点时只影响相邻区间。

hash_ring:  0 ----A---- 0.25 ----B---- 0.5 ----C---- 0.75 ----D---- 1.0
request:    hash(key) = 0.3  -->  落在 B 的区间  -->  路由到 B

为了均匀分布，通常每个后端映射 100-200 个虚拟节点。

6.2 问题：热点

一致性哈希不保证负载均衡。如果某些 key 特别热（如热门商品），对应的后端会过载。

6.3 有界负载一致性哈希（Google 2017）

Mirrokni、Thorup、Zadimoghaddam 在 2017 年提出了 Consistent Hashing with Bounded Loads。

核心思想：给每个节点设置一个容量上限 cap = mean_load * (1 + epsilon)。当目标节点已满时，顺时针继续查找下一个未满的节点。

function bounded_hash_pick(key, backends, epsilon):
    mean_load = total_requests / len(backends)
    cap = ceil(mean_load * (1 + epsilon))
    start = hash(key) 在环上的位置
    for node in ring_clockwise_from(start):
        if node.load < cap:
            return node
    // 所有节点都满（不应出现）
    return fallback

epsilon 控制均衡程度： - epsilon = 0：完美均衡，但亲和性最差 - epsilon 越大：亲和性越好，但均衡性越差 - 实践中 epsilon = 0.25 是一个好的起点

Google 的 Vimeo 和 HAProxy 都实现了这个算法。 Envoy 从 1.8 版本开始支持 RING_HASH + bounded loads。

七、Maglev 哈希

7.1 背景

Google 在 2016 年发表了 “Maglev: A Fast and Reliable Software Network Load Balancer”。 Maglev 是 Google 的四层负载均衡器，处理 Google 几乎所有的外部流量。

7.2 算法核心

Maglev 哈希使用一个固定大小的查找表（lookup table），通常为质数大小 M （论文中 M = 65537）。每个后端通过两个哈希函数计算一个偏好排列 （preference list），然后所有后端按轮次填充查找表。

对每个后端 i，计算：
  offset[i] = h1(name_i) mod M
  skip[i]   = h2(name_i) mod (M-1) + 1

后端 i 的偏好序列：
  permutation[i][j] = (offset[i] + j * skip[i]) mod M

填充算法：

function maglev_populate(backends, M):
    table = [-1] * M
    next = [0] * len(backends)  // 每个后端在偏好序列中的位置
    filled = 0

    while filled < M:
        for i in range(len(backends)):
            // 找到后端 i 下一个空位
            c = permutation[i][next[i]]
            while table[c] != -1:
                next[i]++
                c = permutation[i][next[i]]
            table[c] = i
            next[i]++
            filled++
            if filled == M:
                break

    return table

7.3 特性

特性	说明
查找复杂度	O(1)，直接 table[hash(key) % M]
构建复杂度	O(M * n)，n 为后端数量
最小干扰	增删一个后端，约 1/n 的 key 重新映射
均匀性	每个后端占据约 M/n 个槽位，偏差很小
空间	O(M)，M 通常为 65537

与一致性哈希（虚拟节点）相比，Maglev 的优势在于： 1. 查找是 O(1)，不需要二分搜索环上的节点。 2. 均匀性更好，不依赖虚拟节点数量。 3. 干扰更小，增删节点时重映射的 key 比例更低。

Envoy、Katran（Facebook）、IPVS 都支持 Maglev 哈希。

八、C 语言实现：P2C + EWMA 负载均衡器

下面是一个完整的 C 语言实现，包含 EWMA 延迟跟踪、P2C 选择、 inflight 计数和冷启动惩罚。

/*
 * p2c_ewma.c - Power of Two Choices with EWMA latency load balancer
 *
 * Build: cc -O2 -o p2c_ewma p2c_ewma.c -lm
 * Usage: ./p2c_ewma
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <errno.h>

/* --------------- 配置 --------------- */
#define MAX_BACKENDS      128
#define EWMA_HALF_LIFE_NS 10000000000LL  /* 10 秒 */
#define PENALTY_INIT_MS   500.0          /* 冷启动惩罚延迟 */
#define PENALTY_DECAY_NS  5000000000LL   /* 惩罚衰减周期 */

/* --------------- 时间工具 --------------- */
static inline int64_t now_ns(void) {
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return (int64_t)ts.tv_sec * 1000000000LL + ts.tv_nsec;
}

/* --------------- EWMA --------------- */
static const double LN2 = 0.693147180559945;

/* 计算 EWMA 衰减因子 alpha，基于时间间隔 dt 和半衰期 */
static inline double ewma_alpha(int64_t dt_ns, int64_t half_life_ns) {
    double tau = (double)half_life_ns / LN2;
    return 1.0 - exp(-(double)dt_ns / tau);
}

/* --------------- 后端节点 --------------- */
typedef struct {
    char     name[64];
    int      weight;          /* 配置权重 */
    double   ewma_latency;    /* EWMA 延迟（毫秒） */
    int64_t  last_update_ns;  /* 上次 EWMA 更新时间 */
    int      inflight;        /* 当前在途请求 */
    bool     healthy;         /* 健康状态 */
    int64_t  first_seen_ns;   /* 首次加入时间（冷启动用） */
    uint64_t total_requests;  /* 总请求计数 */
    uint64_t total_errors;    /* 总错误计数 */
} p2c_backend_t;

/* --------------- 负载均衡器 --------------- */
typedef struct {
    p2c_backend_t backends[MAX_BACKENDS];
    int           count;
    uint64_t      total_picks;
} p2c_balancer_t;

/* 初始化均衡器 */
void p2c_init(p2c_balancer_t *lb) {
    memset(lb, 0, sizeof(*lb));
}

/* 添加后端 */
int p2c_add_backend(p2c_balancer_t *lb, const char *name, int weight) {
    if (lb->count >= MAX_BACKENDS) return -1;
    p2c_backend_t *b = &lb->backends[lb->count];
    snprintf(b->name, sizeof(b->name), "%s", name);
    b->weight         = weight > 0 ? weight : 1;
    b->ewma_latency   = 0.0;
    b->last_update_ns = 0;
    b->inflight       = 0;
    b->healthy        = true;
    b->first_seen_ns  = now_ns();
    b->total_requests = 0;
    b->total_errors   = 0;
    return lb->count++;
}

/* 计算节点得分：越低越好 */
static double backend_score(const p2c_backend_t *b, int64_t now) {
    double latency = b->ewma_latency;

    /* 冷启动惩罚：新节点加入后一段时间内施加额外延迟 */
    if (b->total_requests < 10) {
        int64_t age = now - b->first_seen_ns;
        if (age < PENALTY_DECAY_NS) {
            double decay = exp(-(double)age / (double)(PENALTY_DECAY_NS / 3));
            latency += PENALTY_INIT_MS * decay;
        }
    }

    /* 确保延迟至少为 1ms，避免 score 为 0 */
    if (latency < 1.0) latency = 1.0;

    /* score = 延迟 * (在途请求 + 1) / 权重 */
    double score = latency * (double)(b->inflight + 1) / (double)b->weight;
    return score;
}

/* P2C 选择：随机选两个，返回 score 较低的 */
int p2c_pick(p2c_balancer_t *lb) {
    if (lb->count == 0) return -1;
    if (lb->count == 1) return 0;

    int64_t now = now_ns();

    /* 过滤出健康节点 */
    int healthy[MAX_BACKENDS];
    int hn = 0;
    for (int i = 0; i < lb->count; i++) {
        if (lb->backends[i].healthy) {
            healthy[hn++] = i;
        }
    }
    /* 无健康节点时退化为全量选择 */
    if (hn == 0) {
        hn = lb->count;
        for (int i = 0; i < lb->count; i++) healthy[i] = i;
    }
    if (hn == 1) return healthy[0];

    /* 随机选两个不同的 */
    int a_idx = rand() % hn;
    int b_idx = rand() % (hn - 1);
    if (b_idx >= a_idx) b_idx++;

    int a = healthy[a_idx];
    int b = healthy[b_idx];

    double sa = backend_score(&lb->backends[a], now);
    double sb = backend_score(&lb->backends[b], now);

    int chosen = (sa <= sb) ? a : b;
    lb->backends[chosen].inflight++;
    lb->backends[chosen].total_requests++;
    lb->total_picks++;

    return chosen;
}

/* 请求完成，更新 EWMA */
void p2c_on_complete(p2c_balancer_t *lb, int idx, double latency_ms, bool success) {
    if (idx < 0 || idx >= lb->count) return;
    p2c_backend_t *b = &lb->backends[idx];

    int64_t now = now_ns();

    /* 更新 EWMA 延迟 */
    if (b->last_update_ns == 0) {
        b->ewma_latency = latency_ms;
    } else {
        int64_t dt = now - b->last_update_ns;
        double alpha = ewma_alpha(dt, EWMA_HALF_LIFE_NS);
        b->ewma_latency = alpha * latency_ms + (1.0 - alpha) * b->ewma_latency;
    }
    b->last_update_ns = now;

    /* 减少在途计数 */
    if (b->inflight > 0) b->inflight--;

    /* 记录错误 */
    if (!success) b->total_errors++;

    /* 被动健康检查：错误率超过 50% 且请求数足够时标记为不健康 */
    if (b->total_requests > 20) {
        double error_rate = (double)b->total_errors / (double)b->total_requests;
        if (error_rate > 0.5) {
            b->healthy = false;
        }
    }
}

/* 打印状态 */
void p2c_dump(const p2c_balancer_t *lb) {
    printf("%-12s %6s %10s %8s %7s %8s\n",
           "Backend", "Weight", "EWMA(ms)", "Inflight", "Health", "Requests");
    printf("---------------------------------------------------------------\n");
    for (int i = 0; i < lb->count; i++) {
        const p2c_backend_t *b = &lb->backends[i];
        printf("%-12s %6d %10.2f %8d %7s %8lu\n",
               b->name, b->weight, b->ewma_latency,
               b->inflight, b->healthy ? "OK" : "FAIL",
               (unsigned long)b->total_requests);
    }
    printf("Total picks: %lu\n", (unsigned long)lb->total_picks);
}

/* --------------- 模拟测试 --------------- */
static double simulate_latency(const char *name) {
    /* 模拟不同后端的延迟特征 */
    if (strcmp(name, "fast-1") == 0)   return 2.0 + (rand() % 30) * 0.1;
    if (strcmp(name, "fast-2") == 0)   return 3.0 + (rand() % 40) * 0.1;
    if (strcmp(name, "medium-1") == 0) return 10.0 + (rand() % 100) * 0.1;
    if (strcmp(name, "slow-1") == 0)   return 50.0 + (rand() % 200) * 0.1;
    return 5.0 + (rand() % 50) * 0.1;
}

int main(void) {
    srand((unsigned)time(NULL));

    p2c_balancer_t lb;
    p2c_init(&lb);

    /* 添加后端：2 个快节点，1 个中速，1 个慢节点 */
    p2c_add_backend(&lb, "fast-1",   5);
    p2c_add_backend(&lb, "fast-2",   5);
    p2c_add_backend(&lb, "medium-1", 3);
    p2c_add_backend(&lb, "slow-1",   1);

    printf("=== P2C + EWMA Load Balancer Simulation ===\n\n");

    /* 模拟 10000 次请求 */
    for (int i = 0; i < 10000; i++) {
        int chosen = p2c_pick(&lb);
        if (chosen < 0) break;

        double lat = simulate_latency(lb.backends[chosen].name);
        bool ok = (rand() % 100) < 98;  /* 2% 错误率 */

        p2c_on_complete(&lb, chosen, lat, ok);
    }

    printf("After 10000 requests:\n\n");
    p2c_dump(&lb);

    return 0;
}

编译与运行：

cc -O2 -o p2c_ewma p2c_ewma.c -lm
./p2c_ewma

预期输出示例：

=== P2C + EWMA Load Balancer Simulation ===

After 10000 requests:

Backend       Weight   EWMA(ms) Inflight  Health Requests
---------------------------------------------------------------
fast-1             5       3.45        0      OK     3521
fast-2             5       4.12        0      OK     3398
medium-1           3      11.23        0      OK     2467
slow-1             1      58.76        0      OK      614
Total picks: 10000

可以看到 P2C+EWMA 自动将更多流量分配给了延迟更低的节点，同时权重也起到了作用。

九、Subsetting：当你有 10K 个后端

9.1 问题

在大规模微服务架构中（Google、Meta、字节跳动），一个服务可能有上万个实例。如果每个客户端都维护对所有后端的连接，连接数将是 O(clients * backends)，这在内存和文件描述符上都不可接受。

例如：1000 个客户端，10000 个后端，每个连接占 30KB 内存，全连接需要 1000 * 10000 * 30KB = 300 GB 内存。

9.2 Random Subsetting

最简单的方法：每个客户端随机选 K 个后端（通常 K = 20-100）。问题：由于”生日悖论”效应，某些后端会被选中远超平均次数，而某些后端可能完全没被选中。

9.3 Deterministic Subsetting

按客户端 ID 排序，将后端列表分成大小为 K 的连续子集，循环分配给客户端。

backends: [B0, B1, B2, B3, B4, B5, B6, B7, B8, B9]
K = 3

client 0 -> [B0, B1, B2]
client 1 -> [B3, B4, B5]
client 2 -> [B6, B7, B8]
client 3 -> [B9, B0, B1]  // wrap around

9.4 Deterministic Aperture（Twitter/Finagle）

Twitter 的 Finagle 框架实现了 Deterministic Aperture 算法。核心思想是在一致性哈希环上，每个客户端”打开”一个固定宽度的窗口（aperture），只与窗口内的后端建立连接。

通过调整 aperture 的宽度和位置，保证： 1. 每个后端被约相同数量的客户端选中 2. 增减客户端时，连接变动最小 3. 子集之间有适当重叠，避免”命运共同体”问题

aperture 大小 = max(min_aperture, ceil(backends / clients * factor))

9.5 如何选择 K

考量	影响
K 太小（如 5）	负载均衡效果差，容错能力弱
K 太大（如 1000）	连接数爆炸，subsetting 失去意义
推荐范围	K = 20 到 100，视场景调整
Google SRE 推荐	K = max(20, sqrt(backends))

十、健康检查：被动 vs 主动

10.1 被动健康检查（Passive Health Check）

基于实际请求的响应来判断后端是否健康：

维护每个后端的滑动窗口：
  - 连续失败次数 >= threshold  ->  标记为不健康
  - 错误率 > ratio             ->  标记为不健康
  - 超时率 > ratio             ->  标记为不健康

优点：零额外开销，实时反映真实流量。缺点：需要有流量才能检测；新节点或低流量节点无法及时发现故障。

10.2 主动健康检查（Active Health Check）

定时向后端发送探针请求：

类型	探针内容	适用场景
TCP	建立 TCP 连接即成功	四层负载均衡
HTTP	GET /health，检查状态码	七层负载均衡
gRPC	grpc.health.v1.Health/Check	gRPC 服务

typedef struct {
    int    interval_ms;        /* 检查间隔 */
    int    timeout_ms;         /* 超时时间 */
    int    healthy_threshold;  /* 连续成功 N 次标记为健康 */
    int    unhealthy_threshold;/* 连续失败 N 次标记为不健康 */
    char   http_path[256];     /* HTTP 健康检查路径 */
    int    expected_status;    /* 预期 HTTP 状态码 */
} health_check_config_t;

10.3 熔断集成（Circuit Breaker）

健康检查通常与熔断器配合使用：

状态机：
  CLOSED  --错误率超标-->  OPEN  --超时-->  HALF_OPEN  --探针成功-->  CLOSED
                                            --探针失败-->  OPEN

关键参数：

参数	典型值	说明
错误率阈值	50%	触发熔断的错误率
观测窗口	10 秒	统计错误率的时间窗口
熔断时长	30 秒	OPEN 状态持续时间
半开探针数	3	HALF_OPEN 状态下放行的请求数
最小请求数	20	触发熔断判断的最小请求数

10.4 Outlier Detection（Envoy）

Envoy 的 outlier detection 是一种高级的被动健康检查：

连续 5xx：连续收到 5 个 5xx 响应，弹出节点
成功率统计：统计窗口内成功率，低于平均值减去标准差的节点被弹出
延迟统计：P99 延迟超过阈值的节点被弹出

被弹出的节点经过一段时间（指数退避）后自动恢复。如果一个节点被反复弹出，退避时间会越来越长。

十一、实战：Envoy / gRPC / Nginx

11.1 Envoy 的负载均衡策略

Envoy 作为云原生时代最流行的数据面代理，支持丰富的 LB 策略：

# Envoy CDS 配置示例
clusters:
  - name: my_service
    type: EDS
    lb_policy: LEAST_REQUEST  # P2C 变体

    # 或者使用一致性哈希
    # lb_policy: RING_HASH
    # ring_hash_lb_config:
    #   minimum_ring_size: 1024
    #   maximum_ring_size: 8388608

    # 或者 Maglev
    # lb_policy: MAGLEV
    # maglev_lb_config:
    #   table_size: 65537

    common_lb_config:
      healthy_panic_threshold:
        value: 50  # 健康节点少于 50% 时恐慌模式，使用所有节点

    health_checks:
      - timeout: 1s
        interval: 5s
        unhealthy_threshold: 3
        healthy_threshold: 2
        http_health_check:
          path: /healthz

    outlier_detection:
      consecutive_5xx: 5
      interval: 10s
      base_ejection_time: 30s
      max_ejection_percent: 50

Envoy 各策略对比：

策略	适用场景	特点
ROUND_ROBIN	默认场景	简单可靠，支持权重
LEAST_REQUEST	延迟敏感	P2C 实现，考虑活跃请求数
RING_HASH	缓存亲和	一致性哈希，支持有界负载
MAGLEV	缓存亲和（高性能）	O(1) 查找，均匀性好
RANDOM	测试/基准	纯随机，作为对照组
CLUSTER_PROVIDED	xDS 控制面指定	灵活性最高

11.2 gRPC 负载均衡

gRPC 的负载均衡架构比较独特，分为客户端侧和代理侧：

客户端侧 LB（通过 Name Resolver + LB Policy）：

应用 --> gRPC Channel --> Name Resolver --> LB Policy --> SubChannel --> 后端
                          (DNS/xDS)        (pick_first/
                                            round_robin/
                                            weighted_round_robin)

内置策略： - pick_first：连接第一个可用地址，简单但不均衡 - round_robin：轮询所有地址 - weighted_round_robin：带权重的轮询（根据后端上报的 ORCA 负载信息）

xDS LB（与 Envoy/Istio 集成）：

控制面（istiod） --> xDS --> gRPC 客户端 --> EDS 端点列表 --> 本地 LB 策略

xDS 模式下，gRPC 客户端直接消费 EDS（Endpoint Discovery Service）数据，在本地执行负载均衡，无需经过代理。

11.3 Nginx upstream

Nginx 的 upstream 模块支持以下策略：

# 加权轮询（默认）
upstream backend {
    server 10.0.0.1:8080 weight=5;
    server 10.0.0.2:8080 weight=3;
    server 10.0.0.3:8080 weight=1;
}

# 最小连接数
upstream backend_lc {
    least_conn;
    server 10.0.0.1:8080;
    server 10.0.0.2:8080;
}

# IP 哈希（会话保持）
upstream backend_hash {
    ip_hash;
    server 10.0.0.1:8080;
    server 10.0.0.2:8080;
}

# 通用哈希（一致性哈希）
upstream backend_chash {
    hash $request_uri consistent;
    server 10.0.0.1:8080;
    server 10.0.0.2:8080;
}

# 健康检查（需要 nginx_upstream_check_module 或 Nginx Plus）
upstream backend_hc {
    server 10.0.0.1:8080 max_fails=3 fail_timeout=30s;
    server 10.0.0.2:8080 max_fails=3 fail_timeout=30s;
    server 10.0.0.3:8080 backup;  # 备用节点
}

Nginx 的限制：

不支持 P2C，需要自行用 Lua（OpenResty）实现
健康检查功能有限（被动为主），主动健康检查需要商业版或第三方模块
不支持 EWMA 延迟感知

十二、工程踩坑总结与个人观点

12.1 踩坑一览表

坑	症状	解决方案
新节点雪崩	新节点上线瞬间收到大量请求	冷启动惩罚 / slow start
全部标记不健康	健康检查过于敏感，所有节点被标记为不健康	panic threshold，至少保留 N% 节点
长尾效应	P99 延迟极高但 P50 正常	使用 P2C 自动避开慢节点
哈希倾斜	一致性哈希中某些节点承担过多流量	增加虚拟节点数 / 使用 Maglev
重试风暴	客户端重试导致后端进一步过载	限制重试次数，退避策略，重试预算
连接风暴	subsetting 切换导致大量新连接	渐进切换，保留旧连接一段时间
EWMA 过时	低流量节点 EWMA 值很旧，不代表当前状态	设置 EWMA 最大有效期，过期后重置
权重不生效	配置了权重但流量分布不对	检查 LB 策略是否支持权重
DNS 缓存	后端 IP 变化但客户端仍连接旧地址	合理设置 DNS TTL，使用服务发现
跨机房延迟	跨机房请求延迟高但 LB 不感知	zone-aware LB，优先同机房
错误码误判	将业务错误当作后端故障	区分可重试错误（5xx）和不可重试错误（4xx）
容量不对称	不同机型的后端处理能力不同	使用 ORCA 上报实际负载，动态调权

12.2 选择指南

需要缓存亲和性？
  |
  +-- 是 --> 后端数量 > 1000？
  |           |
  |           +-- 是 --> Maglev
  |           +-- 否 --> 一致性哈希（虚拟节点）
  |
  +-- 否 --> 延迟敏感？
              |
              +-- 是 --> P2C + EWMA
              +-- 否 --> 后端权重差异大？
                          |
                          +-- 是 --> 平滑加权轮询
                          +-- 否 --> 简单轮询 / P2C

12.3 个人观点

关于 P2C：P2C 是我目前最推荐的通用负载均衡算法。它实现简单（不到 50 行核心代码），理论基础坚实（Mitzenmacher 1996），工程效果优秀（gRPC、Envoy 都在用）。如果你不知道选什么，选 P2C 不会错。

关于 EWMA：EWMA 的半衰期选择非常关键。太短则 EWMA 值波动剧烈，负载均衡器频繁切换后端（抖动）；太长则对后端状态变化反应迟钝。我的经验是半衰期设为 P99 延迟的 10-50 倍比较合适。如果 P99 是 100ms，半衰期设为 1-5 秒。

关于一致性哈希：一致性哈希的使用场景比很多人想象的要窄。只有当你的业务确实需要”同一个 key 总是打到同一个后端”时才需要它（例如缓存场景）。如果不需要这个特性，P2C 几乎总是更好的选择。

关于 subsetting：如果你的后端数量在 100 以内，不需要 subsetting。 100-1000 之间，可以考虑随机 subsetting。超过 1000，一定要做 deterministic subsetting 或 aperture。Google 的 SRE Book 专门有一章讲这个问题，说明它在大规模系统中有多重要。

关于健康检查：不要只依赖主动健康检查。主动探针和真实流量走的路径不同， /healthz 返回 200 不代表服务真的能正常处理请求。一定要结合被动健康检查（基于实际请求的错误率和延迟）。

关于 Maglev：如果你在做四层负载均衡（L4 LB），强烈推荐 Maglev 哈希。它的 O(1) 查找和极好的均匀性非常适合高性能网络设备。但对于七层 LB（如 Envoy、Nginx），环形一致性哈希通常就够了。

一句话总结：负载均衡不是选一个算法就完事了。它是算法选择 + 健康检查 + 熔断 + 重试 + subsetting + 可观测性的组合工程。每一个环节都可能出问题，每一个参数都需要根据实际流量调优。

参考资料

Mitzenmacher, M. (1996). The Power of Two Choices in Randomized Load Balancing. PhD thesis, UC Berkeley.
Azar, Y., Broder, A. Z., Karlin, A. R., & Upfal, E. (1999). Balanced Allocations. SIAM Journal on Computing.
Eisenbud, D. E., et al. (2016). Maglev: A Fast and Reliable Software Network Load Balancer. NSDI.
Mirrokni, V., Thorup, M., & Zadimoghaddam, M. (2018). Consistent Hashing with Bounded Loads. SODA.
Karger, D., et al. (1997). Consistent Hashing and Random Trees. STOC.
gRPC Load Balancing: https://grpc.io/blog/grpc-load-balancing/
Envoy Load Balancing: https://www.envoyproxy.io/docs/envoy/latest/intro/arch_overview/upstream/load_balancing/
Google SRE Book, Chapter 20: Load Balancing in the Datacenter.
Deterministic Aperture: https://twitter.github.io/finagle/guide/Clients.html

上一篇: 限流算法 下一篇: 路由算法

相关阅读: - 一致性哈希 - MPMC Channel

目录