负载均衡算法详解
约 1805 字大约 6 分钟
load-balancingalgorithms
2025-06-04
概述
负载均衡是分布式系统中将请求合理分发到多个服务实例的关键技术。不同的负载均衡算法在公平性、性能、复杂度等方面各有权衡。本文详细分析常见的负载均衡算法原理和适用场景,并对比L4与L7负载均衡的差异。
常见算法
轮询(Round Robin)
最简单的负载均衡算法,按顺序依次将请求分配给每个后端节点。
public class RoundRobinBalancer {
private final List<String> servers;
private final AtomicInteger counter = new AtomicInteger(0);
public RoundRobinBalancer(List<String> servers) {
this.servers = new ArrayList<>(servers);
}
public String nextServer() {
int index = counter.getAndIncrement() % servers.size();
// 处理整数溢出
if (index < 0) {
counter.set(0);
index = 0;
}
return servers.get(index);
}
}优点: 实现简单,无状态 缺点: 假设所有节点处理能力相同
加权轮询(Weighted Round Robin)
为不同性能的节点分配不同权重,性能强的节点获得更多请求。Nginx使用的是平滑加权轮询算法。
public class SmoothWeightedRoundRobin {
private final List<WeightedServer> servers;
static class WeightedServer {
String address;
int weight; // 配置权重
int currentWeight; // 当前权重(动态变化)
WeightedServer(String address, int weight) {
this.address = address;
this.weight = weight;
this.currentWeight = 0;
}
}
public String nextServer() {
int totalWeight = servers.stream().mapToInt(s -> s.weight).sum();
// 1. 每个节点的currentWeight += weight
WeightedServer selected = null;
for (WeightedServer server : servers) {
server.currentWeight += server.weight;
if (selected == null || server.currentWeight > selected.currentWeight) {
selected = server;
}
}
// 2. 选中节点的currentWeight -= totalWeight
selected.currentWeight -= totalWeight;
return selected.address;
}
// 示例: A(weight=5), B(weight=1), C(weight=1), totalWeight=7
// Round 1: A=5,B=1,C=1 → 选A → A=-2,B=1,C=1
// Round 2: A=3,B=2,C=2 → 选A → A=-4,B=2,C=2
// Round 3: A=1,B=3,C=3 → 选B → A=1,B=-4,C=3
// Round 4: A=6,B=-3,C=4 → 选A → A=-1,B=-3,C=4
// Round 5: A=4,B=-2,C=5 → 选C → A=4,B=-2,C=-2
// 序列: A,A,B,A,C,A,A → 分布平滑!
}最少连接(Least Connections)
将请求分配给当前活跃连接数最少的节点,适合长连接场景。
public class LeastConnectionsBalancer {
private final Map<String, AtomicInteger> connectionCounts = new ConcurrentHashMap<>();
public String nextServer() {
return connectionCounts.entrySet().stream()
.min(Comparator.comparingInt(e -> e.getValue().get()))
.map(Map.Entry::getKey)
.orElseThrow();
}
public void onConnectionStart(String server) {
connectionCounts.get(server).incrementAndGet();
}
public void onConnectionEnd(String server) {
connectionCounts.get(server).decrementAndGet();
}
}加权最少连接
结合权重和连接数:选择 activeConnections / weight 最小的节点。
IP哈希(IP Hash)
根据客户端IP的哈希值选择后端节点,相同IP的请求总是路由到同一节点,保证会话粘性。
public class IPHashBalancer {
private final List<String> servers;
public String nextServer(String clientIP) {
int hash = Math.abs(clientIP.hashCode());
return servers.get(hash % servers.size());
}
}适用场景: 需要会话保持(Session Affinity)但不使用分布式Session的场景 缺点: 节点增减会导致大量映射变化(可用一致性哈希改进)
一致性哈希(Consistent Hashing)
将请求和节点都映射到哈希环上,请求路由到顺时针方向最近的节点。节点增减只影响少量请求。详见一致性哈希。
随机(Random)
随机选择一个节点。当节点数量足够多时,随机策略接近均匀分布。
public class RandomBalancer {
private final List<String> servers;
private final ThreadLocalRandom random = ThreadLocalRandom.current();
public String nextServer() {
return servers.get(random.nextInt(servers.size()));
}
}Power of Two Choices(P2C)
随机选择两个节点,然后选择负载较低的那个。这个看似简单的策略在数学上被证明能将最大负载从O(log n / log log n)降低到O(log log n)。
public class PowerOfTwoChoicesBalancer {
private final List<String> servers;
private final Map<String, AtomicInteger> loads;
private final Random random = new Random();
public String nextServer() {
// 随机选两个
int idx1 = random.nextInt(servers.size());
int idx2 = random.nextInt(servers.size());
while (idx2 == idx1 && servers.size() > 1) {
idx2 = random.nextInt(servers.size());
}
String s1 = servers.get(idx1);
String s2 = servers.get(idx2);
// 选负载较低的
return loads.get(s1).get() <= loads.get(s2).get() ? s1 : s2;
}
}应用: gRPC默认使用P2C + EWMA(指数加权移动平均)进行负载均衡。
自适应算法
根据后端节点的实时状态(响应时间、错误率等)动态调整权重。
public class AdaptiveBalancer {
private final Map<String, ServerStats> stats = new ConcurrentHashMap<>();
static class ServerStats {
double avgResponseTime; // 平均响应时间
double errorRate; // 错误率
int activeConnections; // 活跃连接数
double score() {
// 综合评分(越低越好)
return avgResponseTime * (1 + errorRate) * (1 + activeConnections * 0.1);
}
}
public String nextServer() {
return stats.entrySet().stream()
.min(Comparator.comparingDouble(e -> e.getValue().score()))
.map(Map.Entry::getKey)
.orElseThrow();
}
// 更新统计信息
public void recordResponse(String server, long responseTimeMs, boolean success) {
ServerStats s = stats.get(server);
// 使用EWMA更新平均响应时间
double alpha = 0.1;
s.avgResponseTime = alpha * responseTimeMs + (1 - alpha) * s.avgResponseTime;
s.errorRate = alpha * (success ? 0 : 1) + (1 - alpha) * s.errorRate;
}
}算法对比
| 算法 | 复杂度 | 需要状态 | 公平性 | 适用场景 |
|---|---|---|---|---|
| 轮询 | O(1) | 计数器 | 中 | 节点性能相同 |
| 加权轮询 | O(N) | 权重表 | 好 | 节点性能不同 |
| 最少连接 | O(N) | 连接计数 | 好 | 长连接场景 |
| IP哈希 | O(1) | 无 | 中 | 会话粘性 |
| 一致性哈希 | O(log N) | 哈希环 | 好 | 缓存场景 |
| 随机 | O(1) | 无 | 中 | 大量节点 |
| P2C | O(1) | 负载信息 | 很好 | 通用推荐 |
| 自适应 | O(N) | 实时统计 | 最好 | 异构环境 |
L4 vs L7负载均衡
| 特性 | L4 | L7 |
|---|---|---|
| 工作层次 | TCP/UDP | HTTP/gRPC/WebSocket |
| 性能 | 极高(百万级并发) | 高(十万级并发) |
| 内容感知 | 否 | 是 |
| SSL终止 | 可选 | 通常在此终止 |
| 健康检查 | TCP连接检查 | HTTP健康端点 |
| 会话保持 | 源IP | Cookie/Header |
| 适用场景 | 数据库、Redis等 | Web服务、API网关 |
实际配置示例
Nginx
upstream backend {
# 加权轮询(默认)
server 10.0.1.1:8080 weight=5;
server 10.0.1.2:8080 weight=3;
server 10.0.1.3:8080 weight=1;
server 10.0.1.4:8080 backup; # 备份节点
# 或使用最少连接
# least_conn;
# 或使用IP哈希
# ip_hash;
# 健康检查(Nginx Plus)
# health_check interval=5s fails=3 passes=2;
}
server {
listen 80;
location / {
proxy_pass http://backend;
proxy_next_upstream error timeout http_502 http_503;
proxy_next_upstream_tries 3;
}
}Envoy
clusters:
- name: order-service
type: EDS
lb_policy: LEAST_REQUEST # P2C的变体
load_assignment:
cluster_name: order-service
endpoints:
- lb_endpoints:
- endpoint:
address:
socket_address:
address: 10.0.1.1
port_value: 8080
load_balancing_weight: 5总结
负载均衡算法的选择取决于具体场景。对于大多数场景,加权轮询或P2C是较好的默认选择。P2C以极低的开销实现了接近最优的负载分布,是现代RPC框架(如gRPC)的首选。在需要会话粘性的场景使用一致性哈希,在长连接场景使用最少连接。自适应算法虽然效果最好,但实现复杂,适合对延迟敏感的关键服务。L4和L7负载均衡各有所长,通常在实际架构中组合使用。
贡献者
更新日志
9f6c2-feat: organize wiki content and refresh site setup于