轮询Round Robin和加权轮询Weighted Round Robin是我在实际项目里用得非常频繁的两类基础算法。之前在做某订单服务的多实例部署时三台后端节点如果直接裸奔接收请求很快就会出现一台机器 CPU 打满、另外两台空闲的情况原因就是缺少一层分发控制。当时我用 Java 手写了一个简单的负载均衡器核心就是轮询和加权轮询。这篇文章会从零开始把两种算法的思路、Java 实现、并发处理、平滑加权轮询的原理推导以及工程落地时容易踩的坑一次讲清楚。适合正在做网关、注册中心、RPC 客户端负载均衡的同学或者准备面试时被问到“负载均衡算法怎么实现”的开发者。1. 先从真实场景说起为什么需要轮询和加权轮询1.1 多实例部署下的请求分发问题假设你有一个订单服务部署了三台实例它们对外暴露的是同一个接口。客户端请求进来之后需要一个入口组件来决定“这次请求到底打到哪台实例”。如果这个分发逻辑写得不合适比如永远打第一台那第一台机器很快就会被流量打垮另外两台却在摸鱼。轮询算法解决的就是这种“雨露均沾”的需求请求按顺序轮流分发到每一台实例。第 1 个请求发给 A第 2 个发给 B第 3 个发给 C第 4 个又回到 A周而复始。这样只要实例规格差不多、接口处理耗时也差不多流量就会被均匀分摊掉。1.2 两种算法的核心适用边界轮询的假设是“所有节点能力一样”。但生产环境里很少有规格完全相同的机器。我当时遇到的情况是一台新采购的机器性能明显更强另外两台是旧机器如果把流量平均分给三台旧机器很快会被拖垮新机器反而吃不饱。这时候就需要加权轮询。给每台机器分配一个权重权重代表它能承受的流量比例。比如新机器权重 4旧机器权重 1那新机器应该接收大约 4/5 的流量旧机器各接收 1/5。加权轮询要解决的核心问题就是在保证比例正确的前提下请求顺序还要平滑不能出现“新机器连续被调用 10 次旧机器 10 次里只轮到 2 次”这种集中突刺。这个点后续章节会专门展开。2. 朴素轮询实现与它的两个致命问题2.1 第一版用取模实现的轮询最直观的做法是保存一个计数器每次请求来的时候计数加一然后对节点数量取模。代码很简单public class RoundRobin { private final ListString servers; private int index; public RoundRobin(ListString servers) { this.servers servers; } public String select() { // 这里 index 不是线程安全的 String server servers.get(index % servers.size()); index; return server; } }用一个ArrayList保存节点地址index记录当前访问到的位置每次select都取余。第一次请求拿servers.get(0)第二次拿servers.get(1)到末尾之后重新回到头部。这个版本能工作但只是“单线程环境里能工作”。2.2 并发下的线程安全问题与加锁方案一旦接口并发上来index就会出问题。这个操作在 JVM 里不是原子的它本质上是“读取-加一-写回”三步。两个线程同时读到index0都执行加一最后可能都写回 1结果是两次请求打到同一个节点另一个节点被跳过。最简单的修复方式就是加锁public class RoundRobin { private final ListString servers; private int index; public RoundRobin(ListString servers) { this.servers servers; } public synchronized String select() { String server servers.get(index % servers.size()); index; return server; } }用synchronized修饰方法保证同一时刻只有一个线程能执行这段逻辑。这个方案在节点数量不多、并发量几百的情况下完全够用。缺点是锁的粒度太大所有的请求都串行化去抢同一把锁。如果你的负载均衡模块本身就是在单线程分发器里调用的那这把锁几乎没有开销但如果你的分发模块是多线程直接调用的高并发下synchronized可能成为瓶颈。2.3 取模边界、数据溢出与原子整数方案index的另一个隐患是整数溢出。虽然取模运算对负数也成立但当你用index做数组下标之前取模时Integer.MIN_VALUE % size的结果可能是负数直接拿去做下标就会抛出ArrayIndexOutOfBoundsException。稳妥的做法是让index永远保持非负。一个常见的优化是改用AtomicInteger既解决了并发问题也能避免负数下标import java.util.concurrent.atomic.AtomicInteger; public class RoundRobinAtomic { private final ListString servers; private final AtomicInteger index new AtomicInteger(0); public RoundRobinAtomic(ListString servers) { this.servers servers; } public String select() { int current index.getAndIncrement(); int size servers.size(); // 用 Math.floorMod 保证结果非负 return servers.get(Math.floorMod(current, size)); } }getAndIncrement()是原子的由 CPU 的 CAS 指令保证不需要加锁。这里用Math.floorMod而不是%是因为%在第一个参数为负数时也会返回负数而Math.floorMod永远返回非负结果。如果想进一步减少 CAS 失败带来的自旋开销还可以引入ThreadLocal每个线程维护自己的计数器再配合一个全局的随机起点来错开分布。但我的建议是除非你的负载均衡模块本身就是被高并发直接调用否则AtomicInteger版本已经足够稳健了。面试时能把这个演进思路讲清楚比直接给出最优解更有价值。3. 加权轮询从权重展开到平滑分发3.1 最简单的加权轮询权重展开法假设有三台机器权重分别是 4、2、1。最直觉的做法是把权重展开成一个数组A 出现 4 次B 出现 2 次C 出现 1 次然后对这个数组做普通轮询。public class WeightedRoundRobinNaive { private final ListString expandedServers; private final AtomicInteger index new AtomicInteger(0); public WeightedRoundRobinNaive(MapString, Integer weightMap) { expandedServers new ArrayList(); weightMap.forEach((server, weight) - { for (int i 0; i weight; i) { expandedServers.add(server); } }); } public String select() { int current index.getAndIncrement(); return expandedServers.get(Math.floorMod(current, expandedServers.size())); } }这个实现的问题有两个。第一是空间浪费。如果权重是 10000 和 1那数组会被展开成一万零一个元素为了选一台机器维护一个大数组实在不优雅。第二是流量不平滑。展开后的数组前 4 个元素全是 A轮询的时候会连续四次把请求打到 A。如果 A 正好在处理一个比较重的请求这四个连续请求会直接把它压垮。所以权重展开法适合权重值小、对平滑性要求不高的场景但不适合真实网关。3.2 平滑加权轮询算法原理与推导平滑加权轮询解决了“比例正确”和“请求平滑”两个问题。它的思想是给每个节点维护两个权重值固定权重weight和当前权重currentWeight。初始时所有节点的currentWeight都是 0。每次请求前把每个节点的currentWeight加上它自己的weight。选出currentWeight最大的节点。把选中的节点的currentWeight减去所有节点的weight之和。以 A(4)、B(2)、C(1) 为例总权重 total7初始 currentWeight 都是 0。请求次数累加后 currentWeight选中节点选中后 currentWeight1A:4, B:2, C:1AA:-3, B:2, C:12A:1, B:4, C:2BA:1, B:-3, C:23A:5, B:-1, C:3AA:-2, B:-1, C:34A:2, B:1, C:4CA:2, B:1, C:-35A:6, B:3, C:-2AA:-1, B:3, C:-26A:3, B:5, C:-1BA:3, B:-2, C:-17A:7, B:0, C:0AA:0, B:0, C:0得到的选择序列是 A、B、A、C、A、B、A。看这个顺序A 出现了 4 次B 出现 2 次C 出现 1 次比例正好是 4:2:1。而且分布得很均匀同一个节点不会被连续选中多次。这就是平滑的意义——拿“选中后减去总权重”来补偿其他节点让用得多的节点在下一轮里暂时降低优先级。3.3 平滑加权轮询的 Java 实现先定义一个节点类public class WeightedNode { private final String server; private final int weight; private int currentWeight; public WeightedNode(String server, int weight) { this.server server; this.weight weight; this.currentWeight 0; } }然后实现选择逻辑public class SmoothWeightedRoundRobin { private final ListWeightedNode nodes; private final int totalWeight; public SmoothWeightedRoundRobin(MapString, Integer weightMap) { nodes new ArrayList(); weightMap.forEach((server, weight) - nodes.add(new WeightedNode(server, weight))); totalWeight weightMap.values().stream().mapToInt(Integer::intValue).sum(); } public synchronized String select() { WeightedNode selected null; // 1. 每个节点 currentWeight weight for (WeightedNode node : nodes) { node.currentWeight node.weight; } // 2. 选出 currentWeight 最大的节点 for (WeightedNode node : nodes) { if (selected null || node.currentWeight selected.currentWeight) { selected node; } } // 3. 选中节点 currentWeight - totalWeight selected.currentWeight - totalWeight; return selected.server; } }这里有个细节需要注意select方法加了synchronized。因为整个“累加-比较-扣减”的过程必须是一个原子操作如果多个线程同时进来两个线程可能选到同一个节点还可能把currentWeight算乱。对于节点数量不多的负载均衡加锁完全可接受如果节点数量很大且并发极高可以再考虑用ReentrantLock或者把节点选择放到单线程的调度器里执行。每次请求的时间复杂度是 O(n)n 是节点数量空间复杂度是 O(1)。和权重展开法相比这个算法不需要根据权重值展开数组权重多大都不影响内存占用这是它最大的优势。4. 工程落地动态权重、故障摘除与选型对比4.1 动态权重更新与节点管理真实系统里权重不会写死在代码里。它可能来自注册中心、配置中心或者动态的监控指标比如根据节点 CPU 使用率动态调整。如果只是更新WeightedNode里的weight字段需要注意当前权重currentWeight还保留着上一轮留下来的偏移量。如果不重置更新权重后的若干次请求内分布会偏向某个节点。我在项目里的做法是更新权重后把该节点的currentWeight清零。更稳妥的是把整个集群所有节点的currentWeight全部清零相当于重新开始一轮调度。结合上一节的例子如果你在某个时刻把 A 的权重从 4 改成 10但 A 的currentWeight还是 -3那它要连续累加很多次才能追上来中间几个请求会被 B 和 C 抢走比例会短暂失真。代码上可以用volatile修饰weight字段方便其他线程随时读取更新后的值。4.2 健康检查与故障摘除轮询和加权轮询本身都不关心节点是否存活。如果一个节点已经挂了算法还是会把请求分给它只不过每次都会超时然后由调用方重试。所以工程上一定要配合健康检查。我在项目里使用的方案是负载均衡模块启动一个定时任务周期性地对节点列表做探活。探活失败的节点从候选列表里移除探活恢复后再放回去。如果使用平滑加权轮询最简单的摘除方式是直接修改节点列表如果节点对象上有active字段在遍历累加和选择时跳过active false的节点即可。有一点要特别注意不要频繁地改节点列表。每次synchronized块里对列表做增删没问题但如果你把列表改成不可变快照再整体替换就需要考虑替换的原子性。我的习惯是节点数量少时直接用ArrayList synchronized维持简单可靠节点数量超过几百个时再考虑并发安全的容器。4.3 轮询、加权轮询与其他策略的选型对比有一次做技术方案评审同事问我为什么不用一致性哈希。我说看场景如果是无状态的 HTTP 接口服务轮询和加权轮询完全可以如果有会话保持需求比如用户登录状态只在本地缓存那才需要一致性哈希。我把常用的几种策略整理成了下面这个表格方便你选型时快速参考策略核心特点适用场景轮询实现简单请求均匀节点规格一致、无状态服务加权轮询普通按权重分配比例实现简单节点异构、但对平滑性要求不高平滑加权轮询比例正确且分布平滑节点异构、对流量抖动敏感最少连接数动态感知当前连接数长连接、请求处理耗时差异大的服务一致性哈希请求按 key 映射到固定节点有缓存、有会话保持需求我的经验是大多数接口服务优先选择平滑加权轮询。它比普通加权轮询只多几行代码却能避免权重大的节点被连续请求打穿。只有在节点规格完全一样或者你想追求更动态的负载感知时才去考虑最少连接数或一致性哈希。5. 常见问题与排查技巧实录5.1 并发场景下计数错乱的处理很多人用AtomicInteger实现轮询但压测时发现两个线程偶尔会选到同一个节点。这通常不是AtomicInteger的问题而是你可能在选择之前先读了一次index然后又用这个值去拿节点中间没有保证一致性。正确做法是像前面代码那样把getAndIncrement()的返回值直接用来取模并且用Math.floorMod做下标运算。另外如果你在select方法里还做了其他耗时操作比如查数据库判断节点存活那一定不能只靠原子类跨过整个方法该加锁还是要加锁。5.2 权重比例正确但流动不平滑权重展开法最大的问题就是“连续打同一个节点”。真实案例里我曾见过一个配置了权重 10:1 的服务展开数组后权重大的节点连续被调用 10 次这 10 次里面如果有一次请求包含了一个耗时的 SQL后面 9 个请求就会排队造成接口响应时间飙升。改成平滑加权轮询之后问题立刻消失了。如果你看到流量统计终值比例是对的但某个节点的瞬时负载经常冲高优先检查是不是用了普通的权重展开轮询。5.3 调试与压测方法建议建议在本地写一个简单的压测程序循环调用select十万次用MapString, Integer统计每个节点被选中的次数。对平滑加权轮询还可以把所有选择的顺序打印出来肉眼观察有没有连续出现 3 次以上同一个节点的情况。我自己的测试习惯是权重配置成 4:2:1十万次请求后A 的占比应该在 57% 左右B 在 28.5% 左右C 在 14.3% 左右。同时统计连续命中间隔平滑算法的表现应该是每个请求都不会连续选择同一个节点。这里有一个边界情况如果只有一个节点或者某个节点权重是 0算法依然要正常工作。权重为 0 的节点永远选不中但它的currentWeight仍然会参与累加所以要在累加时跳过weight 0的节点避免无意义计算。6. 个人实操体会与一个小技巧最后分享一点我自己的实操体会。刚开始实现平滑加权轮询的时候总觉得它不如权重展开法直观因为每次要维护那么多步骤。但真正跑上压测之后我才意识到“平滑”在真实流量下有多重要。权重差距越大的场景平滑算法的优势越明显。如果你是在做网关或者 RPC 客户端负载均衡建议直接把平滑加权轮询作为默认策略没有坏处。一个小技巧把平滑加权轮询的选择顺序打出来用一个小脚本把它画成散点图节点相同颜色就会聚在一起。我测试过很多配置只要看到同一个节点连续出现两次基本可以断定代码里的totalWeight算错了或者currentWeight重置时机不对。这个调试方式比单纯看统计数字直观得多也能帮你快速向同事解释为什么要用平滑加权轮询而不是普通版。如果你在自己实现时遇到分布不平滑或者并发计数错乱的问题欢迎拿具体现象来交流。