184 lines
7.1 KiB
Markdown
184 lines
7.1 KiB
Markdown
---
|
||
tags: [arch/microservice, load-balancing, consistent-hashing, spring-cloud-lb, round-robin]
|
||
create time: 2026-08-08 18:00
|
||
update time: 2026-08-08 18:00
|
||
---
|
||
|
||
# 负载均衡算法
|
||
|
||
## 概述
|
||
|
||
负载均衡将客户端请求分发到多个服务实例，是微服务架构中不可或缺的一环。本文对比客户端 vs 服务端两种负载均衡架构，详细讲解轮询、随机、一致性哈希、最少连接等核心算法，以及 Spring Cloud LoadBalancer 的实现原理。
|
||
|
||
## 核心原理
|
||
|
||
### 客户端负载均衡 vs 服务端负载均衡
|
||
|
||
```mermaid
|
||
graph TD
|
||
subgraph ClientLB["客户端负载均衡"]
|
||
C1[客户端/消费者] --> LB1[客户端负载均衡器]
|
||
LB1 --> SI1["实例A: :8081"]
|
||
LB1 --> SI2["实例B: :8082"]
|
||
LB1 --> SI3["实例C: :8083"]
|
||
C1 -.->|自己选实例| LB1
|
||
end
|
||
|
||
subgraph ServerLB["服务端负载均衡"]
|
||
C2[客户端/消费者] --> NLB[Nginx/LVS]
|
||
NLB --> SNI1["实例A: :8081"]
|
||
NLB --> SNI2["实例B: :8082"]
|
||
NLB --> SNI3["实例C: :8083"]
|
||
end
|
||
```
|
||
|
||
| 对比维度 | 客户端负载均衡 | 服务端负载均衡 |
|
||
|---------|--------------|--------------|
|
||
| 部署位置 | 与消费者同进程（如 Spring Cloud LoadBalancer） | 独立中间件（Nginx、LVS、F5） |
|
||
| 延迟 | 低（多一次网络跳） | 高（所有请求必经 LB 节点） |
|
||
| 故障隔离 | 好（失败不影响其他调用链路） | 差（LB 单点故障影响全部） |
|
||
| 语言耦合 | 需要为每种语言实现 SDK | 协议无关，通用性强 |
|
||
| 适用场景 | JVM 微服务体系 | 跨语言 / 流量入口层 |
|
||
|
||
> [!TIP]
|
||
> 面试高频：Netflix 为什么选择客户端负载均衡？因为他们的服务都是 Java，可以用 Ribbon（现已被 Spring Cloud LoadBalancer 替代）嵌入每个微服务，避免了反向代理成为瓶颈和单点故障。
|
||
|
||
### 轮询法（Round Robin）
|
||
|
||
最简单的策略：按顺序依次分发请求。适用于各实例配置相近的场景。
|
||
|
||
- **简单轮询**：`index = (index + 1) % n`，第 i 个请求发给第 i mod n 个实例。
|
||
- **加权轮询**（Weighted Round Robin）：为每个实例分配权重 wᵢ，权重高的获得更多请求。Nginx 的 smooth weighted round robin 用 `current_weight += weight`，每次选 current_weight 最大的，然后 `selected.weight -= total_weight`，保证长期均衡。
|
||
|
||
### 随机法
|
||
|
||
从健康实例列表中均匀随机选择一个。理论上 N 次请求后分布趋近均匀，但小样本下可能极端不均——例如连续两次命中同一个实例。加权随机在电商大促中常用：给大容量实例更高权重。
|
||
|
||
### 一致性哈希（Consistent Hashing）
|
||
|
||
传统哈希 `hash(instance) % n` 的问题在于实例增减时会导致大量请求重新路由（缓存穿透式抖动）。一致性哈希将其缓解到仅影响 `(1/n)` 的数据。
|
||
|
||
**核心思路**：将 hash 值空间映射到环上（0 ~ 2³²），服务和请求都 hash 到环上的同一点，请求顺时针找到最近的实例。
|
||
|
||
**虚拟节点解决数据倾斜**：一个物理实例对应环上的 k 个虚拟节点（k 通常取 100~200），使实例分布更均匀。
|
||
|
||
```mermaid
|
||
graph LR
|
||
H1[hash key: user_42] -->|"顺时针"| I3[实例C]
|
||
H2[hash key: user_99] -->|"顺时针"| I1[实例A]
|
||
H3[hash key: session_7] -->|"顺时针"| I2[实例B]
|
||
|
||
subgraph Ring["哈希环"]
|
||
VN1(VN-a1) --- VN2(VN-a2)
|
||
VN1 ---|"虚节" |VN2
|
||
VN3(VN-b1) --- VN4(VN-b2)
|
||
VN5(VN-c1) --- VN6(VN-c2)
|
||
end
|
||
```
|
||
|
||
```go
|
||
// 一致性哈希简化实现
|
||
type ConsistentHash struct {
|
||
hashes []uint64 // 虚拟节点的 hash 值排序
|
||
map map[uint64]int // hash -> 物理实例索引
|
||
k int // 每个实例的虚拟节点数
|
||
}
|
||
|
||
func NewConsistentHash(instances []string, k int) *ConsistentHash {
|
||
ch := &ConsistentHash{map: make(map[uint64]int), k: k}
|
||
for i, inst := range instances {
|
||
for v := 0; v < k; v++ {
|
||
h := murmur3.Sum64([]byte(fmt.Sprintf("%s-%d", inst, v)))
|
||
ch.hashes = append(ch.hashes, h)
|
||
ch.map[h] = i
|
||
}
|
||
}
|
||
sort.Slice(ch.hashes, func(i, j int) bool { return ch.hashes[i] < ch.hashes[j] })
|
||
return ch
|
||
}
|
||
|
||
func (ch *ConsistentHash) Get(key string) string {
|
||
h := murmur3.Sum64([]byte(key))
|
||
idx := sort.Search(len(ch.hashes), func(i int) bool {
|
||
return ch.hashes[i] >= h
|
||
})
|
||
if idx == len(ch.hashes) {
|
||
idx = 0 // 回到环首
|
||
}
|
||
return InstanceList[ch.map[ch.hashes[idx]]]
|
||
}
|
||
```
|
||
|
||
### 最少连接数法（Least Connections）
|
||
|
||
将请求发给当前活跃连接最少的实例，特别适合长连接场景（gRPC、WebSocket）。实现上需维护每个实例的活跃连接计数器，并发安全地读写。
|
||
|
||
### Spring Cloud LoadBalancer 实现原理
|
||
|
||
Spring Cloud LoadBalancer 取代了已停止维护的 Ribbon，核心机制：
|
||
|
||
1. **ServiceInstanceListSupplier**：从注册中心拉取实例列表并缓存。
|
||
2. **Reactively reactive**：基于 Reactor 响应式编程，返回 `Flux<ServiceInstance>`。
|
||
3. **RoundRobinLocator**：默认轮询策略，内部用 AtomicLong 做递增索引取模。
|
||
|
||
```java
|
||
// Spring Cloud LoadBalancer 核心接口
|
||
public interface LoadBalancerClient<S extends ServiceInstance> {
|
||
<T> Mono<T> execute(String serviceId, LoadBalancerRequest<T>, InstanceChooser);
|
||
ServiceInstance choose(String serviceId);
|
||
<T> Flux<T> getLazyLoadBalancerClient(String serviceId);
|
||
}
|
||
```
|
||
|
||
> [!NOTE]
|
||
> Spring Cloud LoadBalancer 不提供重试和熔断，这些能力由 Resilience4j 等库处理。它只管"选哪个实例"这一个动作。
|
||
|
||
## 代码示例
|
||
|
||
Go 中的加权轮询实现：
|
||
|
||
```go
|
||
type WeightedRR struct {
|
||
servers []*Server
|
||
totalW int
|
||
curIndex int
|
||
}
|
||
|
||
type Server struct {
|
||
Addr string
|
||
Weight int
|
||
CurWeight int
|
||
}
|
||
|
||
func (w *WeightedRR) Next() string {
|
||
maxW, best := -1, ""
|
||
for _, s := range w.servers {
|
||
s.CurWeight += s.Weight
|
||
if s.CurWeight > maxW {
|
||
maxW = s.CurWeight
|
||
best = s.Addr
|
||
}
|
||
}
|
||
for _, s := range w.servers {
|
||
s.CurWeight -= w.totalW
|
||
}
|
||
return best
|
||
}
|
||
```
|
||
|
||
## 实践场景
|
||
|
||
**秋招高频问题：**
|
||
|
||
- "一致性哈希为什么能减少数据迁移？" — 只有失效实例及其顺时针下一个实例之间的数据段会迁移。移除一个实例只影响其相邻的两个虚拟节点范围，而非全部数据。
|
||
- "什么时候不能用轮询？" — 实例规格差异大（如混部有强机和弱机），必须加权；或者存在长连接状态绑定（如 WebSocket 会话），需要一致性哈希来确保同一用户落到同一实例。
|
||
- "Spring Cloud 和 Nginx 的负载均衡有什么区别？" — Spring Cloud 在应用层做选择，感知注册中心变更（秒级）；Nginx 依赖 upstream 配置或 DNS 解析更新，变更延迟较大。
|
||
|
||
> [!WARNING]
|
||
> 一致性哈希不适合频繁增删实例的场景。如果实例每几分钟就变一次，virtual nodes 数量要调得更大（500+）才能维持稳定性，这增加了内存开销。
|
||
|
||
## 关联笔记
|
||
|
||
- [[服务注册与发现]]
|
||
- [[限流熔断降级]]
|