网络算法 #02：最小连接数

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

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

目录

问题背景

轮询的隐含假设

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

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

• 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)

加权最小连接数（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)

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

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

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

仍选 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 计数，连接可能仍然保持

适用场景

异常与边界场景分析

场景 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

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

与轮询对比

选型原则：

• 请求处理时间均匀（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) 近似最优，理论分析论文