网络算法 #01：轮询与加权轮询

轮询算法解决多节点负载均衡问题，将请求依次或按权重分发给后端服务器，被 Nginx、HAProxy、Kubernetes 等广泛采用。

相关文章：最小连接数 · Jump Consistent Hash · Rendezvous Hashing

目录

普通轮询（Round Robin）

问题背景

当后端有多个性能相同的节点时，需要将请求均匀分配给每个节点，避免某台服务器过载而其他服务器空闲。普通轮询是最简单的解决方案：依次将请求分发给每个节点，循环往复。

核心数据结构

struct RoundRobinBalancer {
    servers: []Server      // 服务器列表，索引 0..n-1
    currentIndex: int      // 当前指向的服务器索引，初始值 -1
    n: int                 // 服务器总数
}

struct Server {
    id: string             // 服务器标识，如 "A", "B", "C"
    addr: string           // 服务器地址
    alive: bool            // 是否存活
}

完整伪代码

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

    tries = 0
    while tries < balancer.n:
        balancer.currentIndex = (balancer.currentIndex + 1) % balancer.n
        server = balancer.servers[balancer.currentIndex]
        if server.alive:
            return server
        tries += 1

    return ERROR("all servers down")

执行追踪

初始状态：servers = [A, B, C]，currentIndex = -1，n = 3

分配结果：A, B, C, A, B, C — 绝对均匀，每节点各 1/3。

图解

特性分析

• 时间复杂度：O(1)（正常情况），O(n)（遍历查找存活节点时）
• 空间复杂度：O(1) 额外空间
• 优点：实现极简，绝对均匀
• 缺点：不考虑节点性能差异，性能强弱节点分配相同请求数

朴素加权轮询（Weighted Round Robin，Naive）

问题背景

当后端节点性能不同时（如 A 机器 16 核、B 机器 8 核、C 机器 4 核），需要按性能比例分配请求。朴素加权轮询通过将节点按权重展开为列表来实现。

核心数据结构

struct WeightedServer {
    id: string
    weight: int            // 权重，如 A=3, B=2, C=1
}

struct NaiveWRRBalancer {
    expandedList: []string // 按权重展开后的列表
    currentIndex: int      // 当前位置
}

构建过程

function buildExpandedList(servers):
    list = []
    for server in servers:
        repeat server.weight times:
            list.append(server.id)
    return list

示例：A=3, B=2, C=1 → expandedList = [A, A, A, B, B, C]

完整伪代码

function buildNaiveWRR(servers):
    balancer.expandedList = buildExpandedList(servers)
    balancer.currentIndex = -1
    balancer.n = len(balancer.expandedList)
    return balancer

function next(balancer):
    if balancer.n == 0:
        return ERROR("no servers")
    balancer.currentIndex = (balancer.currentIndex + 1) % balancer.n
    return balancer.expandedList[balancer.currentIndex]

执行追踪

expandedList = [A, A, A, B, B, C]，n = 6

问题

分配序列：A, A, A, B, B, C — 同一节点连续出现，前 3 个请求全部命中 A，在短时间窗口内造成 A 过载。这就是朴素加权轮询的缺陷，平滑加权轮询解决了这个问题。

平滑加权轮询（Smooth Weighted Round Robin，Nginx 实现）

问题背景

朴素加权轮询导致同一节点连续命中，在高并发场景下会造成瞬时不均衡。Nginx 在 2016 年引入平滑加权轮询算法，通过动态调整 current_weight 使请求均匀分散，避免突发流量集中到单一节点。

核心数据结构

struct SmoothServer {
    id: string
    weight: int            // 静态配置权重（不变）
    currentWeight: int     // 动态当前权重（每轮动态调整）
}

struct SmoothWRRBalancer {
    servers: []SmoothServer
    totalWeight: int       // 所有节点 weight 之和
}

完整伪代码

function next(balancer):
    if balancer.servers is empty:
        return ERROR("no servers")

    // Step 1: 每个节点 currentWeight += weight
    for each server in balancer.servers:
        server.currentWeight += server.weight

    // Step 2: 选出 currentWeight 最大的节点
    best = null
    for each server in balancer.servers:
        if best == null or server.currentWeight > best.currentWeight:
            best = server

    // Step 3: 被选中节点 currentWeight -= totalWeight
    best.currentWeight -= balancer.totalWeight

    return best

算法直觉

• 每轮所有节点的 currentWeight 总和 = 上一轮总和 + totalWeight - totalWeight = 恒定
• 被选中的节点"受到惩罚"，减去 totalWeight，短期内不会再次被选中
• 权重高的节点虽然受到更大惩罚，但每轮增量也更大，长期被选频率等于 weight/totalWeight

执行追踪

初始：A(weight=3, current=0)，B(weight=2, current=0)，C(weight=1, current=0)，totalWeight=6

重新精确追踪：

分配序列：A, B, A, C, B, A — 请求均匀分散，A 出现 3 次（权重3/6=50%），B 出现 2 次（33%），C 出现 1 次（17%），且不连续。

正确性证明（归纳）

经过一个完整周期（6轮）后，所有节点 currentWeight 均归零，系统回到初始状态，下一周期重复同样分配模式。

一致性哈希轮询（Consistent Hashing）

问题背景

对于有状态服务（如 Session、Cache），同一客户端的请求必须路由到同一节点，普通轮询无法满足。一致性哈希通过对请求 key（如 IP、用户 ID）哈希，将其映射到固定节点。

核心数据结构

struct ConsistentHashBalancer {
    ring: SortedMap<int, Server>  // 哈希环：虚拟节点哈希值 → 服务器
    virtualNodes: int              // 每个真实节点对应的虚拟节点数（默认 150）
    hashFunction: Function         // 哈希函数，如 MurmurHash
}

完整伪代码

function addServer(balancer, server):
    for i in range(balancer.virtualNodes):
        key = hashFunction(server.id + "#" + i)
        balancer.ring[key] = server

function removeServer(balancer, server):
    for i in range(balancer.virtualNodes):
        key = hashFunction(server.id + "#" + i)
        delete balancer.ring[key]

function route(balancer, requestKey):
    if balancer.ring is empty:
        return ERROR("no servers")
    hash = hashFunction(requestKey)
    // 在环上顺时针找到第一个 >= hash 的虚拟节点
    entry = balancer.ring.ceilingEntry(hash)
    if entry == null:
        entry = balancer.ring.firstEntry()  // 环绕到开头
    return entry.server

与普通轮询的区别

异常与边界场景分析

场景 1：节点宕机

触发条件：健康检查发现某节点无响应。

算法处理（平滑 WRR）：

function markServerDown(balancer, serverId):
    server = findServer(balancer, serverId)
    server.alive = false
    // 将其 weight 和 currentWeight 置零
    balancer.totalWeight -= server.weight
    server.weight = 0
    server.currentWeight = 0

宕机节点 currentWeight 永远为 0，Step2 永远不会选中它；totalWeight 减小，其他节点惩罚变小，相对权重自动重新均衡。

场景 2：动态权重调整（热更新）

触发条件：运维人员在线调整某节点权重（如从 2 调整为 4）。

算法处理：

function updateWeight(balancer, serverId, newWeight):
    server = findServer(balancer, serverId)
    balancer.totalWeight += (newWeight - server.weight)
    server.weight = newWeight
    // currentWeight 不重置，平滑过渡

currentWeight 不归零，算法在接下来的几轮内自然过渡到新权重比例，不会产生突变。

场景 3：所有权重为 0（防除零）

触发条件：配置错误，或所有节点权重被动态调整为 0。

算法处理：

function next(balancer):
    if balancer.totalWeight == 0:
        // 降级：退化为普通轮询，均等对待所有节点
        return balancer.servers[currentIndex++ % n]

或直接返回错误，由上层熔断处理。不可执行 currentWeight -= 0，避免无限循环选同一节点。

场景 4：单节点集群

触发条件：集群缩容到只剩 1 台服务器。

算法处理：普通轮询：(currentIndex+1) % 1 = 0，永远返回 index=0 的节点，正确。平滑 WRR：每轮 currentWeight += weight，然后 -= totalWeight（= weight），currentWeight 恒为 0，始终返回唯一节点，正确。

场景 5：并发竞争

触发条件：多线程同时调用 next()。

算法处理：currentIndex 和 currentWeight 是共享状态，必须加锁（互斥锁）或使用 CAS 原子操作。Nginx 使用全局互斥锁保护 upstream 选择。

Nginx upstream 实现

Nginx 的 ngx_http_upstream_module 支持多种负载均衡策略，内部数据结构如下：

weighted（平滑 WRR，默认）

// nginx/src/http/ngx_http_upstream_round_robin.h
typedef struct {
    ngx_http_upstream_rr_peer_t   *peer;       // 服务器链表
    ngx_uint_t                     current;    // 当前 current_weight 最大节点
} ngx_http_upstream_rr_peers_t;

typedef struct ngx_http_upstream_rr_peer_s {
    ngx_uint_t                     weight;         // 静态权重
    ngx_int_t                      current_weight; // 动态当前权重
    ngx_uint_t                     effective_weight; // 有效权重（含健康度）
    ngx_uint_t                     fails;          // 失败次数
    time_t                         accessed;       // 最近访问时间
    ngx_http_upstream_rr_peer_t   *next;           // 下一节点
} ngx_http_upstream_rr_peer_t;

选择逻辑：遍历链表，执行 peer->current_weight += peer->effective_weight，选 current_weight 最大者，被选者执行 peer->current_weight -= total_weight。

ip_hash（一致性哈希变体）

// 基于客户端 IP 的哈希
hash = (ip[0] * 89 + ip[1]) * 89 + ip[2]
index = hash % n  // n 为上游服务器数

注意：ip_hash 不是严格一致性哈希，节点增减时重新取模，会导致大量 key 迁移；需要真正一致性哈希时应使用 hash $variable consistent 指令（Ketama 算法）。

least_conn（最小连接数）

// 选择 active_connections / weight 最小的节点
for each peer:
    score = peer.active_connections * totalWeight / peer.weight
    if score < bestScore:
        best = peer

适合请求处理时间差异较大的场景（如混合短连接和长连接）。

与最小连接数对比

选型原则：

• 请求体量均匀（API 网关、微服务）→ 平滑 WRR
• 请求耗时差异大（DB 代理、长连接）→ 最小连接数
• 需要 Session 粘性 → 一致性哈希（ip_hash 或 Ketama）
• 节点性能差异大且请求耗时不均 → 加权最小连接数（Least Conn + Weight）

参考资料

1. Nginx 平滑加权轮询提交：Nginx 官方 commit，作者 Glebius Friedman，2016年。"Upstream: smooth weighted round-robin balancing." — https://nginx.org/en/docs/http/ngx_http_upstream_module.html
2. Nginx 源码：src/http/ngx_http_upstream_round_robin.c — upstream 负载均衡核心实现
3. Karger et al., 1997："Consistent Hashing and Random Trees"，STOC 1997 — 一致性哈希原始论文
4. HAProxy 文档：Load Balancing Algorithms — https://www.haproxy.com/documentation/haproxy/load-balancing/
5. 《深入理解 Nginx》，陶辉，机械工业出版社 — 第 5 章 upstream 机制详解
6. Kubernetes kube-proxy：iptables/IPVS 模式下的负载均衡实现 — https://kubernetes.io/docs/concepts/services-networking/service/#proxy-mode-ipvs