设计负载均衡器

问题

如何用 Rust 实现不同策略的负载均衡器？

答案

负载均衡策略实现

use std::sync::atomic::{AtomicUsize, Ordering};
use std::sync::Arc;
use rand::Rng;

pub trait LoadBalancer: Send + Sync {
    fn select(&self) -> usize; // 返回后端索引
}

/// Round-Robin
pub struct RoundRobin {
    count: AtomicUsize,
    total: usize,
}

impl LoadBalancer for RoundRobin {
    fn select(&self) -> usize {
        self.count.fetch_add(1, Ordering::Relaxed) % self.total
    }
}

/// 加权 Round-Robin
pub struct WeightedRoundRobin {
    weights: Vec<u32>,
    current: AtomicUsize,
}

impl LoadBalancer for WeightedRoundRobin {
    fn select(&self) -> usize {
        let total_weight: u32 = self.weights.iter().sum();
        let pos = self.current.fetch_add(1, Ordering::Relaxed) as u32 % total_weight;

        let mut cumulative = 0;
        for (i, &weight) in self.weights.iter().enumerate() {
            cumulative += weight;
            if pos < cumulative {
                return i;
            }
        }
        0
    }
}

/// P2C（Power of Two Choices）
/// 随机选两个，取负载最小的
pub struct P2C {
    loads: Vec<AtomicUsize>, // 每个后端的当前负载
}

impl LoadBalancer for P2C {
    fn select(&self) -> usize {
        let mut rng = rand::thread_rng();
        let a = rng.gen_range(0..self.loads.len());
        let mut b = rng.gen_range(0..self.loads.len());
        while b == a {
            b = rng.gen_range(0..self.loads.len());
        }

        let load_a = self.loads[a].load(Ordering::Relaxed);
        let load_b = self.loads[b].load(Ordering::Relaxed);

        if load_a <= load_b { a } else { b }
    }
}

算法对比

算法	时间复杂度	优点	缺点
Round-Robin	O(1)	简单均匀	不考虑后端负载
加权 RR	O(n)	考虑后端性能差异	需要手动配置权重
最少连接	O(n)	动态感知负载	锁竞争
P2C	O(1)	自适应 + 低开销	随机性
一致性哈希	O(log n)	会话亲和	节点变更影响大

推荐

P2C（Power of Two Choices）是目前最推荐的算法——O(1) 时间复杂度，自适应负载，理论上在大规模系统中接近最优分发。gRPC 默认使用 P2C。

---

常见面试问题

Q1: P2C 为什么比随机选择好？

答案：

数学证明（Balls into Bins 问题）：

• 随机选择：最大负载约 $O(\frac{\log n}{\log \log n})$
• P2C：最大负载约 $O(\log \log n)$

P2C 只是多选了一次候选，就将负载不均衡指数级降低。这就是 "The Power of Two Choices" 的含义。

相关链接

• tower-balance
• The Power of Two Choices