P2C（Power of Two Choices）

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

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

目录

问题背景

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

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

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

核心思想

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

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

数学原理

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

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

选 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，权重越高的服务器在相同负载下更容易被选中。

工程细节

负载度量的选择

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

抖动与峰值处理

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

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

服务器列表更新

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

与其他算法对比

选型建议：微服务之间的 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)）