最小连接数

最小连接数算法解决请求处理时间不均匀场景下的负载均衡问题，将请求路由到当前活跃连接数最少的节点，被 Nginx least_conn、HAProxy、AWS ALB 等广泛采用。

相关文章：轮询与加权轮询 · Jump Consistent Hash · Rendezvous Hashing

目录

章节	说明
问题背景	轮询假设等耗时；长连接/慢查询导致节点积压
核心数据结构	active_connections 原子计数器，节点列表
基础最小连接数	select() O(N) 遍历，request_complete() 计数递减
加权最小连接数（Weighted Least Connections，WLC）	score = active_connections / weight，归一化比值
最少活跃请求变体（Least Active Requests）	A(5,w=4)、B(2,w=2)、C(8,w=8) 的 WLC 选择过程
异常与边界场景分析	区分连接数与活跃请求数，长连接池场景
Nginx least_conn 实现	连接数相同、节点宕机、连接泄漏、并发更新
与轮询对比	peer.conns、细粒度锁、与 fair 模块结合
与轮询对比	复杂度、负载均衡质量、适用场景
参考资料	论文、官方文档、书籍

问题背景

轮询的隐含假设

普通轮询和加权轮询假设每个请求的处理时间大致相同。在这个前提下，每个节点分配到相同数量的请求，负载自然均衡。

但现实中这个假设经常被打破：

• WebSocket 长连接：握手后保持数十分钟甚至数小时，连接数持续积累
• 数据库慢查询：部分 SQL 执行 5 秒，部分执行 5 毫秒，差异 1000 倍
• 文件下载：下载 1GB 文件的连接与下载 1KB 文件的连接同时存在
• 混合负载：同一服务既处理快速 API 请求，又处理耗时的批量导出

轮询失效示例

假设 3 个节点，已有连接分布：A=10、B=2、C=8。若使用轮询，下一请求路由到 A（按顺序），A 的积压进一步加剧；而 B 只有 2 个连接，完全有余力接收新请求。

最小连接数算法通过实时感知节点负载，始终将新请求路由到最空闲的节点。

核心数据结构

struct Server {
    id: string                      // 节点标识，如 "A", "B", "C"
    addr: string                    // 节点地址
    weight: int                     // 静态权重（加权版本使用），默认 1
    active_connections: AtomicInt   // 当前活跃连接数，原子整数，初始为 0
    alive: bool                     // 是否存活（健康检查维护）
}

struct LeastConnBalancer {
    servers: []Server               // 节点列表
    n: int                          // 节点总数
}

关键设计决策：active_connections 使用原子整数（AtomicInteger / atomic.Int64）而非普通整数，因为请求的建立和释放来自不同线程，必须保证计数操作的原子性，防止竞态条件导致计数错误。

基础最小连接数

完整伪代码

select()：选择连接数最少的节点

function select(balancer):
    if balancer.n == 0:
        return ERROR("no servers")

    best = null
    bestConn = MAX_INT

    for each server in balancer.servers:
        if not server.alive:
            continue
        conn = server.active_connections.get()
        if conn < bestConn:
            bestConn = conn
            best = server

    if best == null:
        return ERROR("all servers down")

    // 选中后立即递增，防止并发请求同时选中同一节点
    best.active_connections.incrementAndGet()
    return best

request_complete()：请求完成时递减

function request_complete(server):
    val = server.active_connections.decrementAndGet()
    if val < 0:
        // 防御性保护：计数不能为负，说明有泄漏 bug
        server.active_connections.set(0)
        log.warn("connection count underflow on server", server.id)

复杂度分析

• 时间复杂度：O(N)，每次选择都需遍历所有节点
• 空间复杂度：O(1) 额外空间
• 优化方向：当 N 很大时（如数百个节点），可用最小堆维护节点列表，将选择复杂度降至 O(log N)，但插入/更新仍需 O(log N)

执行追踪

初始状态：A(conn=0)、B(conn=0)、C(conn=0)

事件	A.conn	B.conn	C.conn	选中
初始	0	0	0	-
请求 1 到达	0→1	0	0	A（同为 0，取第一个）
请求 2 到达	1	0→1	0	B（同为 0，取第一个存活且最小）
请求 3 到达	1	1	0→1	C
请求 4 到达	1→2	1	1	A（同为 1，取先遍历到的）
请求 1 完成	2→1	1	1	-
请求 5 到达	1→2	1	1	A（同为 1，取先遍历到的，A 先遍历到）
请求 2 完成	2	1→0	1	-
请求 6 到达	2	0→1	1	B（conn=0 最小）

加权最小连接数（Weighted Least Connections，WLC）

问题背景

当节点性能不同时（如 A 是 32 核高性能机器、B 是 8 核普通机器），相同的连接数对两台机器的负载含义不同。A 有 8 个连接和 B 有 8 个连接，A 实际上更空闲。

加权最小连接数通过计算 score = active_connections / weight 归一化，使高权重节点能承接更多连接。

完整伪代码

function select_wlc(balancer):
    if balancer.n == 0:
        return ERROR("no servers")

    best = null
    bestScore = MAX_FLOAT

    for each server in balancer.servers:
        if not server.alive:
            continue
        if server.weight == 0:
            continue

        // 归一化得分：连接数 / 权重，值越小说明节点越空闲
        score = server.active_connections.get() / server.weight

        if score < bestScore:
            bestScore = score
            best = server
        // score 相同时，选序号靠前的节点（保证确定性，避免随机抖动）

    if best == null:
        return ERROR("all servers down or zero weight")

    best.active_connections.incrementAndGet()
    return best

执行追踪

节点配置：A(conn=5, w=4)、B(conn=2, w=2)、C(conn=8, w=8)

节点	active_connections	weight	score = conn/weight
A	5	4	5/4 = 1.25
B	2	2	2/2 = 1.00
C	8	8	8/8 = 1.00

B 和 C 的 score 同为 1.00，按遍历顺序选 B（序号靠前）。

选中 B，B.conn: 2 → 3。

假设随后请求继续到来，B 完成一个请求（B.conn: 3→2），下一请求重新计算：

节点	conn	weight	score
A	5	4	1.25
B	2	2	1.00
C	8	8	1.00

仍选 B（score 最小）。体现了权重高的节点（C 权重 8）能以更高的连接数"保持与低权重节点相同的 score"，从而承接更多请求。

最少活跃请求变体（Least Active Requests）

与连接数的区别

在长连接池（如数据库连接池、HTTP/2 多路复用）中：

• 连接数：客户端与服务端之间建立的 TCP 连接数量。一个连接可以承载多个并发请求（HTTP/2、gRPC）
• 活跃请求数：当前正在处理的请求数量，不等于连接数

struct LeastActiveServer {
    id: string
    active_requests: AtomicInt   // 当前正在处理的请求数（未完成的）
    connections: AtomicInt       // TCP 连接数（可能有多个空闲连接）
}

完整伪代码

function select_least_active(balancer):
    best = null
    bestActive = MAX_INT

    for each server in balancer.servers:
        if not server.alive:
            continue
        active = server.active_requests.get()
        if active < bestActive:
            bestActive = active
            best = server

    best.active_requests.incrementAndGet()
    return best

function on_request_start(server):
    server.active_requests.incrementAndGet()

function on_request_end(server):
    server.active_requests.decrementAndGet()
    // 注意：不影响 connections 计数，连接可能仍然保持

适用场景

场景	推荐指标
HTTP/1.1 短连接	连接数 ≈ 请求数，两者等价
HTTP/2 / gRPC 多路复用	活跃请求数更准确
数据库连接池	活跃请求数（一个连接同时只处理一个查询）
WebSocket	连接数（每个连接是一个持续会话）

异常与边界场景分析

场景 1：所有节点连接数相同（退化为轮询）

触发条件：系统启动初期，或流量极其均匀时，所有节点 active_connections 相等。

算法处理：遍历时按节点顺序取第一个，效果等同于轮询。无需特殊处理，算法天然退化为轮询语义，行为正确。

// 所有节点 conn=5，遍历到第一个节点 A 时，5 < MAX_INT，选中 A
// 后续节点 conn=5，不满足 < bestConn，不更新 best
// 结果：固定选 A，直到其他节点连接数更少

注意：若要避免固定选第一个节点，可在 score 相同时加入随机抖动或轮询因子：

if conn == bestConn and random() < 1/rank:   // 等概率随机
    best = server

场景 2：节点宕机

触发条件：健康检查检测到节点无响应，将其标记为 alive = false。

算法处理：

function on_server_down(server):
    server.alive = false
    // 正在进行的连接由连接本身的超时机制处理
    // 计数器保留，供监控观察；也可清零以便恢复时状态正确
    server.active_connections.set(0)

select() 的 if not server.alive: continue 跳过宕机节点，流量自动转移到存活节点。节点恢复后，将 alive = true，active_connections 归零，自然参与选择。

场景 3：连接泄漏（client 断开但服务端计数未减）

触发条件：客户端异常断开（网络中断、进程崩溃），服务端未触发 request_complete()，导致 active_connections 持续增大，该节点被误判为"最忙"而永久回避。

算法处理：引入心跳超时机制：

struct Connection {
    server: Server
    lastHeartbeat: Timestamp
    timeout: Duration            // 如 30s
}

// 后台清理协程
function cleanup_stale_connections():
    every 10 seconds:
        for each conn in active_connections_list:
            if now() - conn.lastHeartbeat > conn.timeout:
                log.warn("stale connection detected, cleaning up")
                conn.server.active_connections.decrementAndGet()
                remove(conn from active_connections_list)

场景 4：并发更新计数的竞争

触发条件：多个 goroutine/线程同时调用 select()，同时读到某节点 conn=2 为最小，同时对其执行 increment，实际结果 conn=4 而非 conn=3。

算法处理：使用原子操作（AtomicInteger / sync/atomic）：

// Java
AtomicInteger active_connections = new AtomicInteger(0);
int prev = active_connections.incrementAndGet();  // CAS 原子递增

// Go
var activeConns int64
atomic.AddInt64(&activeConns, 1)   // 原子加
atomic.AddInt64(&activeConns, -1)  // 原子减

对于更严格的"读取-判断-递增"原子性（防止 TOCTOU），可用带锁的 select：

mutex.lock()
best = findMinConnServer()
best.active_connections.incrementAndGet()
mutex.unlock()

Nginx 就是采用这种方案（细粒度锁，每个 peer 一把锁）。

Nginx least_conn 实现

核心数据结构

// nginx/src/http/ngx_http_upstream_round_robin.h
typedef struct ngx_http_upstream_rr_peer_s {
    ngx_uint_t  weight;               // 静态权重
    ngx_uint_t  effective_weight;     // 有效权重（含健康度衰减）
    ngx_int_t   current_weight;       // 平滑 WRR 用的动态权重
    ngx_uint_t  conns;                // 当前活跃连接数 ← least_conn 核心字段
    ngx_uint_t  fails;                // 失败次数
    time_t      accessed;             // 最近访问时间
    ngx_msec_t  response_time;        // 响应时间（fair 模块使用）

    ngx_http_upstream_rr_peer_t  *next;   // 链表指针
    ngx_atomic_t                  lock;   // 细粒度锁（每个 peer 独立）
} ngx_http_upstream_rr_peer_t;

选择逻辑

// 简化版，参考 nginx/src/http/modules/ngx_http_upstream_least_conn_module.c
ngx_http_upstream_rr_peer_lock(peers, peer);   // 加锁

best = NULL;
for (peer = peers->peer; peer; peer = peer->next) {
    if (peer->down) continue;

    // score = conns * totalWeight / effective_weight（整数除法，避免浮点）
    n = peer->conns * peers->total_weight;
    m = best->conns * peers->total_weight;

    if (n * best->effective_weight < m * peer->effective_weight) {
        best = peer;
    }
}

best->conns++;
ngx_http_upstream_rr_peer_unlock(peers, best);   // 解锁

细粒度锁：Nginx 对每个 peer 使用独立的 ngx_atomic_t lock，而非全局锁，减少锁竞争。

与 fair 模块结合

Nginx 的 ngx_http_upstream_fair_module（第三方模块）在 least_conn 的基础上加入响应时间因子：

score = (active_connections + 1) * response_time_avg

响应时间慢的节点得分更高，被选择的概率更低，综合考量了节点负载和性能。

与轮询对比

维度	轮询（Round Robin）	最小连接数（Least Conn）
假设前提	请求处理时间相同	请求处理时间差异显著
select() 复杂度	O(1)	O(N)，堆优化后 O(log N)
负载感知	无，只感知请求数量	有，实时感知活跃连接数
状态维护	O(1) currentIndex	O(N) active_connections 数组
适用场景	RESTful API、静态资源	WebSocket、DB 代理、文件下载
突发长连接	节点积压，无法自动均衡	自动转移到空闲节点
实现复杂度	极低	中（需原子计数器 + 计数维护）
权重支持	原生（WRR）	conn / weight 归一化

选型原则：

• 请求处理时间均匀（API 网关、微服务）→ 平滑加权轮询（O(1)，无状态开销）
• 请求耗时差异大、有长连接（DB 代理、WebSocket、文件下载）→ 加权最小连接数
• N 很大（数百节点）且需要最小连接数 → 最小堆维护，O(log N) 选择
• 节点性能差异大且请求耗时不均 → 加权最小连接数（score = conn / weight）

参考资料

1. Nginx least_conn 源码：nginx/src/http/modules/ngx_http_upstream_least_conn_module.c — least_conn 核心实现，peer.conns 字段维护逻辑
2. Nginx upstream 数据结构：nginx/src/http/ngx_http_upstream_round_robin.h — peer 结构体定义，conns、lock 字段
3. Nginx 官方文档：Upstream least_conn 指令说明 — https://nginx.org/en/docs/http/ngx_http_upstream_module.html#least_conn
4. HAProxy 负载均衡算法文档：leastconn 算法描述 — https://www.haproxy.com/documentation/haproxy/load-balancing/
5. AWS ALB 最小连接路由：Application Load Balancer 路由算法 — https://docs.aws.amazon.com/elasticloadbalancing/latest/application/load-balancer-target-groups.html
6. 《深入理解 Nginx》，陶辉，机械工业出版社 — 第 5 章 upstream 机制，least_conn 模块实现详解
7. "The Power of Two Choices in Randomized Load Balancing"，Mitzenmacher，2001 — 随机选两个节点取最小连接数，O(1) 近似最优，理论分析论文