网络算法 #08：P2C（Power of Two Choices）

P2C（Power of Two Choices）从服务器池中随机挑两台，选负载更低的那台转发请求；以 O(1) 时间实现接近最少连接算法的分布效果，是 Envoy、gRPC、Nginx Plus 的默认负载均衡策略。

相关文章：轮询与加权轮询 · 最小连接数 · Jump Consistent Hash

p2c selection

章节	说明
问题背景	随机与最少连接的两难
核心思想	随机选 2，比较取优
数学原理	为什么选 2 足够？指数改善定理
算法实现	Java 完整实现，带权重变体
工程细节	负载度量、抖动处理、健康检查
与其他算法对比	轮询、最少连接、P2C 横向比较
实际应用	Envoy、gRPC、Nginx Plus
参考资料	论文与文档

问题背景

负载均衡算法面临一个根本矛盾：

算法	时间复杂度	效果	问题
随机	O(1)	差	纯随机，短时间内可能严重不均
轮询	O(1)	中	忽略服务器实际负载
最少连接	O(N) 或 O(log N)	最优	需要全局扫描或维护有序结构

在节点数达到数百乃至数千的微服务场景下，O(N) 的最少连接算法开销不可忽视。

P2C 的洞察：不需要找全局最优，只需要"比随机好得多"——理论证明，随机选 2 个比较，效果就已接近全局最优。

核心思想

1. 从服务器池随机选 2 台（不重复）
2. 比较两台的当前负载（连接数 / 队列长度）
3. 将请求路由到负载更低的那台

就这三步，时间复杂度 O(1)，但均衡效果远超纯随机。

数学原理

指数改善定理（The Power of Two Choices）

Azar et al. 1994 年在球桶问题（balls-into-bins）上证明：

策略	最大负载（N 个球投入 N 个桶）
随机选 1 个	Θ(log N / log log N)
随机选 2 个取低	Θ(log log N)（指数改善！）
全局最优	Θ(log N / log log N) → Θ(1)

选 2 个相比选 1 个，最大负载从 O(log N / log log N) 降到 O(log log N)——一次对数的量级跳跃。选 3 个、4 个改善微乎其微，收益递减。

实践含义：100 台服务器，纯随机最坏某台承受约 5 倍平均负载；P2C 最坏约 3 倍，且随服务器数增加改善越明显。

算法实现

基础版

import java.util.List;
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.atomic.AtomicInteger;

public class P2CLoadBalancer {

    private final List<Server> servers;

    public P2CLoadBalancer(List<Server> servers) {
        this.servers = servers;
    }

    public Server choose() {
        int size = servers.size();
        if (size == 0) return null;
        if (size == 1) return servers.get(0);

        // 随机选 2 台（不重复）
        int i = ThreadLocalRandom.current().nextInt(size);
        int j;
        do {
            j = ThreadLocalRandom.current().nextInt(size);
        } while (j == i);

        Server a = servers.get(i);
        Server b = servers.get(j);

        // 取负载更低的（先检查健康状态）
        if (!a.isHealthy()) return b;
        if (!b.isHealthy()) return a;
        return a.activeConnections() <= b.activeConnections() ? a : b;
    }

    record Server(String id, AtomicInteger connections) {
        int activeConnections() { return connections.get(); }
        boolean isHealthy()     { return true; }   // 接入真实健康检查
    }
}

带权重的 P2C（Weighted P2C）

当服务器性能不均等时，用加权随机替换等概率随机：

// 权重影响被选中的概率，但最终仍比较两台的负载/权重比
double scoreA = a.activeConnections() / (double) a.weight();
double scoreB = b.activeConnections() / (double) b.weight();
return scoreA <= scoreB ? a : b;

Envoy 的实现使用 active_requests * weight 作为 score，权重越高的服务器在相同负载下更容易被选中。

工程细节

负载度量的选择

度量	优点	缺点	适用场景
活跃连接数	实时，无延迟	不区分请求复杂度	TCP 代理、DB 连接池
活跃请求数	更准确反映 CPU 压力	需要请求生命周期追踪	HTTP/gRPC
加权响应时间	反映服务器真实性能	有滞后（指数移动平均）	延迟敏感型

gRPC 的 pick_first 策略已被 round_robin、weighted_round_robin 取代，Envoy 默认使用活跃请求数。

抖动与峰值处理

当两台服务器负载完全相同时，随机选其中一台（避免哈希粘连）：

return (scoreA < scoreB) ? a : (scoreA > scoreB) ? b
       : ThreadLocalRandom.current().nextBoolean() ? a : b;

服务器列表更新

服务器动态上下线时，P2C 无需重建任何结构——直接在当前列表中随机即可，天然支持动态变更。

与其他算法对比

维度	随机	轮询	最少连接	P2C
时间复杂度	O(1)	O(1)	O(log N)	O(1)
负载均匀性	差	忽略实际负载	最优	接近最优
动态负载感知	❌	❌	✅	✅
动态扩缩容	✅	需重置	✅	✅
实现复杂度	极低	低	中	低
长尾请求保护	❌	❌	✅	✅

选型建议：微服务之间的 RPC 负载均衡首选 P2C；有状态会话（如 WebSocket）用一致性哈希；节点数 < 10 且请求均匀用轮询。

实际应用

Envoy Proxy

Envoy 将 P2C（称为 LEAST_REQUEST）作为其核心负载均衡策略之一：

默认 choice_count=2（可配置为 3、4，但实践无必要）
度量：活跃请求数（active_requests）
权重：支持 load_balancing_weight 差异化节点权重

gRPC

gRPC-Go、gRPC-Java 内置 least_connection 策略（即 P2C 的实现）：

客户端维护每个 subchannel 的活跃 RPC 数
新请求时随机两选一，选活跃 RPC 少的

Nginx Plus

Nginx Plus（商业版）的 least_conn 指令在连接数并列时使用加权随机，效果等同 P2C。

参考资料

参考资料

Azar et al., Balanced Allocations (SIAM Journal on Computing, 1999) — P2C 数学基础

轮询与加权轮询（对比：O(1) 但不感知负载）

最小连接数（对比：最优但 O(N)）