轮询与加权轮询

发布于 2026-06-04 04:33 · 最后编辑于 2026-07-31 15:54 · 字数 4,218 👁 95 次阅读

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

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

章节	说明
普通轮询（Round Robin）	currentIndex 循环递增，O(1) 绝对均匀
朴素加权轮询（Weighted Round Robin，Naive）	按权重展开列表，存在连续命中同一节点问题
平滑加权轮询（Smooth Weighted Round Robin，Nginx 实现）	Nginx 实现，current_weight 动态调整，请求均匀分散
一致性哈希轮询（Consistent Hashing）	按 key 路由，适合有状态服务
异常与边界场景分析	节点宕机、动态权重、权重为零、单节点集群
Nginx upstream 实现	ip_hash、least_conn、weighted 内部结构
与最小连接数对比	不同场景下的算法选择
参考资料	论文、文档、书籍

普通轮询（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

请求	计算过程	currentIndex	选中节点
第 1 次	(-1+1) % 3 = 0	0	A
第 2 次	(0+1) % 3 = 1	1	B
第 3 次	(1+1) % 3 = 2	2	C
第 4 次	(2+1) % 3 = 0	0	A
第 5 次	(0+1) % 3 = 1	1	B
第 6 次	(1+1) % 3 = 2	2	C

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

图解

round robin

特性分析

时间复杂度：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

请求	currentIndex	选中节点
第 1 次	0	A
第 2 次	1	A
第 3 次	2	A
第 4 次	3	B
第 5 次	4	B
第 6 次	5	C

问题

分配序列：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

轮次	Step1: current += weight	Step2: 选最大	Step3: 被选 -= 6	选中
1	A=3, B=2, C=1	A(3最大)	A=3-6=-3	A
2	A=0, B=4, C=2	B(4最大)	B=4-6=-2	B
3	A=3, B=0, C=3	A(3,C也是3，取先遍历到的A)	A=3-6=-3	A
4	A=0, B=2, C=4	C(4最大)	C=4-6=-2	C
5	A=3, B=4, C=-1	B(4最大)	B=4-6=-2	B
6	A=0, B=-4+2=-2→A=3,B=-4+2,C=-2+1	重算: A=3+(-3+3)=0+3...

重新精确追踪：

轮次	A.cur	B.cur	C.cur	加后 A	加后 B	加后 C	选中	减后被选
初始	0	0	0	-	-	-	-	-
1	+3→3	+2→2	+1→1	3	2	1	A(max=3)	A: 3-6=-3
2	-3+3=0	2+2=4	1+1=2	0	4	2	B(max=4)	B: 4-6=-2
3	0+3=3	-2+2=0	2+1=3	3	0	3	A(max=3,先到)	A: 3-6=-3
4	-3+3=0	0+2=2	3+1=4	0	2	4	C(max=4)	C: 4-6=-2
5	0+3=3	2+2=4	-2+1=-1	3	4	-1	B(max=4)	B: 4-6=-2
6	3+3=6	-2+2=0	-1+1=0	6	0	0	A(max=6)	A: 6-6=0

分配序列：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

与普通轮询的区别

特性	普通轮询	一致性哈希
路由依据	全局顺序计数器	请求 key 的哈希值
同一客户端	可能路由到不同节点	始终路由到同一节点
节点宕机影响	全局重新分配	仅影响该节点的请求
适用场景	无状态服务	有状态服务（Session、Cache）
实现复杂度	极低	中等

异常与边界场景分析

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

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

与最小连接数对比

维度	轮询（WRR）	最小连接数（Least Conn）
假设前提	所有请求处理时间相等	请求处理时间差异显著
状态维护	O(1) currentWeight	O(n) 实时连接数
适用场景	RESTful API、静态资源	数据库连接、WebSocket、文件下载
突发流量	可能瞬时不均匀（朴素WRR）	自动适应，连接数少的节点多接请求
实现复杂度	低	中（需原子计数器）
权重支持	原生支持	`active / weight` 归一化

选型原则：

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

参考资料

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

← 返回列表

暂无评论，来留下第一条吧。

登录或注册后才能发表评论

轮询与加权轮询

目录

普通轮询（Round Robin）

问题背景

核心数据结构

完整伪代码

执行追踪

图解

特性分析

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

问题背景

核心数据结构

构建过程

完整伪代码

执行追踪

问题

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

问题背景

核心数据结构

完整伪代码

算法直觉

执行追踪

正确性证明（归纳）

一致性哈希轮询（Consistent Hashing）

问题背景

核心数据结构

完整伪代码

与普通轮询的区别

异常与边界场景分析

场景 1：节点宕机

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

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

场景 4：单节点集群

场景 5：并发竞争

Nginx upstream 实现

weighted（平滑 WRR，默认）

ip_hash（一致性哈希变体）

least_conn（最小连接数）

与最小连接数对比

参考资料

评论 (0)