★ FEATURED ARTICLE 1. 为什么还要手写负载均衡算法负载均衡这个词在后端开发里早就被聊烂了。Nginx、Spring Cloud LoadBalancer、Dubbo、gRPC甚至 Kubernetes 的 Service全都内置了现成的负载均衡能力——配置一个策略名字剩下的交给框架处理好像完全没有手写的必要。但如果你真的在业务代码里排查过线上问题或者自己搭过一套小型微服务骨架大概率会遇到几个现成组件搞不定的场景。比如某个节点刚重启完内存里还是冷的请求却一股脑地压过来比如某个上游服务响应时间异常飙升但它的 404 率和连接数都正常健康检查机制根本察觉不到又比如你只想根据当前请求的特征用户 ID、渠道、商品区域把流量稳定地路由到固定的一组节点上而开箱即用的轮询和随机根本做不到这种粘性。这时候你就会发现所谓“负载均衡”并不是一个黑盒它本质上就是一段可以自己掌控的调度逻辑。手写的意义不在于“比 Nginx 更牛”而在于深入理解负载均衡的底层原理而不是停留在配置项的层面在标准框架不适配的业务场景里能有自己改造和扩展的能力面试时能把算法细节讲清楚而不是只会说“我配过 Nginx 的权重轮询”这篇文章我会从零开始把负载均衡最核心的几类算法手写一遍。代码用 Java 实现但算法思路和代码结构是语言无关的看懂以后用 Go、Python、C 都能复刻。整个过程中我会把每一步的“为什么”讲透包括权重怎么归一化、一致性哈希的虚拟节点数量怎么选、滑窗统计怎么做才不消耗太多内存以及我在实际项目中踩过的坑。先给一个整体的算法谱系后面逐个展开算法核心思路适用场景主要缺陷随机概率均等天然分布请求量大、节点性能接近短时间可能偏斜轮询按序循环绝对均匀无状态、节点同质无权重适应性加权轮询按权重分配比例节点规格不同权重突刺问题平滑加权轮询权重平滑过渡生产环境默认首选实现稍复杂一致性哈希请求特征映射节点缓存、状态ful场景虚拟节点调参最少活跃数动态感知负载长耗时请求混合需要请求计数2. 核心算法逐个击破与代码实现2.1 随机与轮询最朴素但最容易被忽视的细节随机算法是所有负载均衡策略里最基础的版本核心思想就是让每个节点被选中的概率均等。代码写起来极其简单public class RandomLoadBalancer implements LoadBalancer { private final ListServer serverList; private final ThreadLocalRandom random ThreadLocalRandom.current(); public RandomLoadBalancer(ListServer serverList) { this.serverList serverList; } Override public Server select(Request request) { if (serverList.isEmpty()) { throw new NoAvailableServerException(no server available); } int index random.nextInt(serverList.size()); return serverList.get(index); } }这里有两个细节值得注意。第一用ThreadLocalRandom而不是new Random()因为后者在多线程环境下会有竞争和种子生成的性能损耗前者每个线程独立的实例在并发量上来后性能差距非常明显。第二nextInt(n)的语义是 [0, n) 区间永远不会取到 n所以直接拿返回的整数当索引是安全的不需要再减一。轮询算法则在随机的基础上保证了“绝对均匀”每一轮循环下来每个节点都会被选中恰好一次public class RoundRobinLoadBalancer implements LoadBalancer { private final ListServer serverList; private final AtomicInteger position new AtomicInteger(0); public RoundRobinLoadBalancer(ListServer serverList) { this.serverList serverList; } Override public Server select(Request request) { if (serverList.isEmpty()) { throw new NoAvailableServerException(no server available); } int index position.getAndIncrement() % serverList.size(); return serverList.get(index); } }注意这里的AtomicInteger是必要的。假如你用普通的int position配合synchronized在高并发下会带来锁竞争假如你直接volatile int然后用position这个操作本身就不是原子的多个线程可以同时读到同一个值导致流量全部打到一个节点上。getAndIncrement()本身就是原子的所以这里既保证了并发安全又没有显式加锁性能损耗极小。还有一种变化是用ThreadLocalInteger为每个线程维护独立的计数器可以进一步提升并发性能。但代价是单线程内连续的请求不会均匀分布极端情况下某个线程的计数起点恰好相同就会导致一轮流量全打在同一节点上。所以除非你明确知道并发模型的特性否则不建议这么做。2.2 加权轮询从固定比例到平滑过渡的升级加权轮询解决的核心问题是节点性能不均。比如三台机器配置分别是 4C8G、8C16G、16C32G如果仍然用等概率轮询性能最强的机器只能分到三分之一流量资源就是浪费的。第一版加权轮询实现思路非常直白每台机器有一个 weight每轮累加一个 currentWeight当 currentWeight 超过某个阈值时选中该机器。这个方案在流量波动大的场景下会出现“权重突刺”。举个例子你就明白了假设 A、B、C 三台机器的权重是 5、1、1。第一轮A 的 currentWeight 从 0 变成 5B 变成 1C 变成 1选中 A第二轮A 从 5 变成 10B 从 1 变成 2C 从 1 变成 2还是选中 A。如果一直这样下去A 会连续被选中 5 次B 和 C 才各自被选中一次——这就是“突刺”流量不是平滑分布而是像水龙头一样开了又关。平滑加权轮询算法也叫 Nginx 平滑加权轮询就是专门解决这个问题的。它的核心规则是public class SmoothWeightedRoundRobinLoadBalancer implements LoadBalancer { private final ListServer serverList; private final int totalWeight; public SmoothWeightedRoundRobinLoadBalancer(ListServer serverList) { this.serverList serverList; this.totalWeight serverList.stream().mapToInt(Server::getWeight).sum(); } Override public synchronized Server select(Request request) { if (serverList.isEmpty()) { throw new NoAvailableServerException(no server available); } Server selected null; int maxCurrentWeight Integer.MIN_VALUE; for (Server server : serverList) { // 每次调用currentWeight 累加自身权重 server.setCurrentWeight(server.getCurrentWeight() server.getWeight()); // 选出 currentWeight 最大的节点 if (server.getCurrentWeight() maxCurrentWeight) { maxCurrentWeight server.getCurrentWeight(); selected server; } } if (selected null) { throw new NoAvailableServerException(no server available); } // 选中的节点 currentWeight 减去总权重使其下一轮不会再被选中 selected.setCurrentWeight(selected.getCurrentWeight() - totalWeight); return selected; } }仍然拿 A5, B1, C1 举例走一遍流程初始 currentWeight 都是 0totalWeight 7第一轮A 变成 5B 变成 1C 变成 1选 AA 的 currentWeight 变成 5-7 -2第二轮A 变成 -25 3B 变成 11 2C 变成 11 2选 AA 变成 3-7 -4第三轮A 变成 -45 1B 变成 21 3C 变成 21 3选 B或 C取决于遍历顺序B 变成 3-7 -4第四轮A 变成 15 6B 变成 -41 -3C 变成 31 4选 AA 变成 6-7 -1第五轮A 变成 -15 4B 变成 -31 -2C 变成 41 5选 CC 变成 5-7 -2结果五轮下来A 被选 3 次B 被选 1 次C 被选 1 次比例恰好是 5:1:1而且分布是 A, A, B, A, C 这种相对平滑的序列不再有连续 5 次全打 A 的极端情况。这里有两个要注意的工程细节。其一synchronized是必需的。因为currentWeight的更新是“读改写”三步不是原子操作多个线程并发调用会导致权重计算错乱。如果你对性能要求非常苛刻可以退而求其次用一个ReentrantLock或者干脆让 select 方法的外层调用方保证串行——比如放在单线程的调度线程里。其二不过是重要的currentWeight是带状态的所以这个均衡器不是线程安全的静态工具类不能像 Spring 的单例 Bean 那样在多个请求线程之间共享select方法的同时不加固锁。每次调用都必须保证进入同步区域。很多新手在这个地方踩坑把currentWeight存在一个共享对象里而不加锁线上流量越高、分布越乱。2.3 一致性哈希让请求稳定落在固定节点一致性哈希解决的是“有状态场景”的负载均衡问题比如 Session 粘滞、缓存 key 路由、用户维度的数据分片。假设你有 10 台缓存节点需要根据用户 ID 或订单 ID 把请求路由到固定节点这样命中率才高。如果简单用hash(userId) % 10一旦节点数量变成 11几乎所有 key 的映射都会漂移缓存直接大面积失效——这就是所谓的“缓存雪崩”风险。一致性哈希的思路是把所有节点和数据 key 都映射到一个圆环上0 到 2^32-1 的哈希空间然后数据 key 顺时针找到第一个节点绑定到那个节点上。当节点数量变化时只有该节点逆时针方向的一段数据需要迁移其他数据完全不受影响。直接看实现public class ConsistentHashLoadBalancer implements LoadBalancer { private final TreeMapLong, Server hashRing new TreeMap(); private final int virtualNodeCount; public ConsistentHashLoadBalancer(ListServer serverList, int virtualNodeCount) { this.virtualNodeCount virtualNodeCount; for (Server server : serverList) { addServer(server); } } private void addServer(Server server) { for (int i 0; i virtualNodeCount; i) { String virtualKey server.getIp() # i; long hash hash(virtualKey); hashRing.put(hash, server); } } Override public Server select(Request request) { if (hashRing.isEmpty()) { throw new NoAvailableServerException(no server available); } long keyHash hash(request.getClientIp()); // 返回大于等于 keyHash 的最小 hash 值对应的节点 Map.EntryLong, Server entry hashRing.ceilingEntry(keyHash); if (entry null) { // 如果超出了环的最大值则回到环的第一个节点 entry hashRing.firstEntry(); } return entry.getValue(); } private long hash(String key) { // MurmurHash 或 MD5也可以直接用 128 位哈希的低 64 位 // 这里用简单的 FNV1_64 作为示例 long hash 0xcbf29ce484222325L; for (char c : key.toCharArray()) { hash ^ c; hash * 0x100000001b3L; } return hash Long.MAX_VALUE; } }这里为什么用TreeMap因为ceilingEntry方法天然实现了“在环上找下一个节点”的逻辑O(log n) 的时间复杂度完全够用。如果用数组扫描每次请求都是 O(n)节点多了以后性能下降明显。关于虚拟节点数量我的经验是节点数少于 10 个时虚拟节点建议 100~200 个节点数在 10~50 个之间50~100 个即可超过 50 个节点20~50 个就够了。虚拟节点太少会导致 hash 环上的节点分布不均某些节点承载的 key 范围远超其他节点——这在节点数少比如 3 台时尤其明显用 200 个虚拟节点能明显改善分布。虚拟节点的 hash 计算方法需要注意如果直接用ip # i作为 hash key那么同一个物理节点的虚拟节点在环上的位置可能会聚集在一起因为ip部分完全相同只有后缀#1、#2改变。建议在 key 里混入一个全局随机盐值比如ip # i # salt这样虚拟节点在环上的分布会更均匀。2.4 最少活跃数与自适应负载均衡最少活跃数的核心思想是根据当前每个节点正在处理的请求数来动态调度让负载最轻的节点接新请求。这个算法适合请求处理时间波动很大的场景比如某个接口偶尔执行 50ms偶尔执行 3s如果用轮询或加权轮询3s 的请求会一直占着节点导致后续请求堆积。实现上需要维护一个节点到“当前活跃请求数”的映射public class LeastActiveLoadBalancer implements LoadBalancer { private final ListServer serverList; private final ConcurrentHashMapServer, AtomicInteger activeCount new ConcurrentHashMap(); public LeastActiveLoadBalancer(ListServer serverList) { this.serverList serverList; for (Server server : serverList) { activeCount.put(server, new AtomicInteger(0)); } } Override public Server select(Request request) { Server leastActiveServer null; int minActive Integer.MAX_VALUE; for (Server server : serverList) { int current activeCount.get(server).get(); if (current minActive) { minActive current; leastActiveServer server; } } if (leastActiveServer null) { throw new NoAvailableServerException(no server available); } // 选中之后立刻把活跃数加一 activeCount.get(leastActiveServer).incrementAndGet(); return leastActiveServer; } public void decrement(Server server) { activeCount.get(server).decrementAndGet(); } }实际使用中必须配套一个拦截器或回调机制请求发起时incrementAndGet()请求结束时无论是正常返回还是异常返回decrement()。如果你的代码里漏掉了finally块中的decrement()活跃数会只增不减最终所有请求都会被错误地路由到活跃数最小的节点上——这个 bug 在压测时几乎发现不了因为活跃数本来就小等到某个节点出现异常后整个均衡器就彻底失灵了。上线后需要重点关注一个细节活跃数只能代表“发出了多少请求还没结束”但不能区分“这些请求是快还是慢”。比如 A 节点上 10 个请求都只要 10msB 节点上 5 个请求每个需要 2s按最少活跃数算法会把新请求全部发给 B但实际 A 的处理能力远超 B。这个问题在 Dubbo 的 leastactive 实现中也存在业界做法是结合节点响应时间的 EWMA指数加权移动平均来综合打分这属于更进阶的自适应负载均衡有兴趣可以自己扩展。3. 从算法到工程落地一套可平滑扩展的负载均衡器框架手写算法的代码跑通很容易但直接扔到生产环境里就会立刻暴露问题。你总不能每次接一个新协议HTTP、gRPC、自定义 TCP就改一遍算法逻辑吧也不能每次新增一种均衡策略就重写一遍请求分发逻辑吧所以工程化的第一步是抽象出稳定的接口层。我的做法是把负载均衡拆成两层第一层是策略层只负责“从一组节点中选一个”完全不知道上层是什么协议第二层是调度层负责从注册中心拉取节点、维护节点健康状态、调用策略层选节点、发起实际请求、处理异常和超时。对应的接口设计如下public interface LoadBalancer { Server select(Request request); } public class LoadBalancerFactory { public static LoadBalancer create(String strategy, ListServer serverList, Properties config) { switch (strategy.toLowerCase()) { case random: return new RandomLoadBalancer(serverList); case roundrobin: return new RoundRobinLoadBalancer(serverList); case weighted: return new SmoothWeightedRoundRobinLoadBalancer(serverList); case consistenthash: int virtualNodes Integer.parseInt(config.getProperty(virtual.nodes, 100)); return new ConsistentHashLoadBalancer(serverList, virtualNodes); case leastactive: return new LeastActiveLoadBalancer(serverList); default: throw new IllegalArgumentException(unknown strategy: strategy); } } }这里有个非常关键的设计决策策略对象被创建后应尽量不持有节点列表的可变状态。比如轮询算法里那个AtomicInteger position它在多线程下反复getAndIncrement会导致同一个策略对象状态不断变化一旦某个节点宕机被移除你必须在所有并发线程的访问路径上安全地替换策略对象。这个在 Java 里最容易出的问题就是“并发替换时旧对象正在被使用”。我的建议是给LoadBalancer加一个rebuild(ListServer newServers)方法每次节点列表变化时生成一个新的策略实例然后通过volatile引用原子替换。这个模式写多了以后你会发现负载均衡的核心难点根本不在算法本身而在于节点列表的动态变化和策略对象的状态一致性。另外真实业务里的节点不是固定的每次服务发布、扩缩容、故障摘除都会导致节点列表变动。所以一个工程化实现还必须包含节点注册与注销通过注册中心比如 Nacos、Zookeeper 或自己写的服务发现监听节点列表变化节点健康检查定期对节点做心跳检测或 HTTP 探活失败节点从可用列表移除节点权重动态调整支持根据监控数据动态调整权重比如某节点 CPU 超过 80% 就临时降权故障转移策略选出节点后如果调用失败自动尝试下一个节点并记录失败次数触发熔断这部分在架构设计时就要考虑好否则算法写得再完美一上生产就废。4. 避坑指南手写负载均衡最常见的九个坑坑 1hash 分布不均导致一致性哈希节点倾斜解决办法增加虚拟节点数量并在虚拟节点的 hash key 中加入随机盐值。只要节点数量大于 5100 个虚拟节点基本能保证分布比 10 个虚拟节点好一个数量级。坑 2轮询计数器的并发安全被忽略用int position就是典型的非原子操作必须使用AtomicInteger或者加锁。如果你在压测时发现某个节点的流量异常高先检查是不是这里出了问题。坑 3加权轮询的权重值没有归一化权重比例是相对的A 权重 5、B 权重 1 和 A 权重 500、B 权重 100 效果完全一样。但如果你把权重当作绝对值使用比如在负载上报时直接乘以权重会导致监控数据偏差。建议统一归一化到 0~100 范围。坑 4平滑加权轮询没有加锁导致 currentWeight 错乱只要你的均衡器被多线程共享就必须对权重更新加锁。不想加锁的唯一办法是像上面说的那样每次节点列表变化时重建策略对象并用 volatile 整体替换。坑 5请求结束后忘记递减活跃数在发起请求的 try-finally 块里做decrement()并且一定要确保异常路径也执行。线上排查时可以用一张表记录每个节点的活跃数变化曲线异常飙升的节点通常就是漏减的。坑 6一致性哈希没有考虑节点失效后的容错某个节点挂了按一致性哈希算法它负责的那段 key 会全量漂移到它的下一个节点这个节点可能瞬间被打垮。工程上需要做“虚拟节点失效转移”当选中节点不在可用列表时继续向顺时针方向查找下一个可用节点并限制最大查找次数避免死循环。坑 7预热节点被流量压垮新启动的节点 JIT 编译还没完成、缓存还没建立直接进入负载均衡池会被打爆。建议新节点接入时先以低权重运行几分钟再逐步提升权重。这个“预热”逻辑在 Kubernetes 滚动发布时尤其重要。坑 8只做负载均衡不做全局限流负载均衡只能解决“流量分给谁”的问题不能解决“流量太多怎么办”的问题。手写负载均衡时一定要同步考虑限流、熔断、降级否则某个节点被流量打满后均衡器只会把流量打向其他节点最终整组全挂。坑 9只测试了 happy path没有压测节点剔除和恢复算法写完后一定要在压测环境中演练“随机杀掉一个节点”“随机恢复一个节点”“清空某个节点的连接池”等混沌场景。你手写的算法只有在这种考验下才能暴露问题而不是只测“10 万 QPS 正常情况”。5. 手写负载均衡在真实业务中的选型建议选型不是“哪个算法最先进”而是“哪个算法最适合你的业务模型”。这里给一组基于实际经验的选型参考业务场景推荐算法理由无状态 HTTP API 网关平滑加权轮询简单稳定节点规格不一也适用缓存集群一致性哈希key 级别路由节点变化影响最小长连接推送服务最少活跃数连接耗时差异大活跃数更能反映真实负载短视频/直播上行一致性哈希 最少活跃数组合既要 key 粘滞又要动态避让异步消息处理消费者集群随机或加权轮询无状态随机分布天然平滑RPC 微服务调用最少活跃数 EWMA 权重重置动态感知慢节点自动调整权重有一条纯经验判断标准如果你不确定选什么先用平滑加权轮询然后在监控里观察节点负载曲线。99% 的情况下平滑加权轮询都能给出一个相当好的基线后续再用监控数据针对性地微调。另外一个大家在选型时容易忽略的点业务闭环的反馈延迟。如果你的系统像订单一样有明确的分库分表而且读多写少那么写路径上用轮询、读路径上用一致性哈希可能有更好的效果。这些也是手写负载均衡比纯配置项更有价值的地方——你可以按业务维度做多个均衡器每个均衡器用不同策略甚至在同一请求内分段路由。6. 手写负载均衡代码的测试策略算法手写完成后我强烈建议写一套确定性测试而不是只依赖随机测试。所谓“确定性”就是针对算法的每一个分支写明确的输入输出断言而不是“跑 1 万次看看分布有没有异常”。举个例子测试平滑加权轮询时可以这样验证序列Test public void testSmoothWeightedRoundRobinSequence() { ListServer servers Arrays.asList( new Server(A, 5), new Server(B, 1), new Server(C, 1) ); LoadBalancer balancer new SmoothWeightedRoundRobinLoadBalancer(servers); MapString, Integer count new HashMap(); int total 70; // 10 轮完整循环 for (int i 0; i total; i) { Server server balancer.select(null); count.put(server.getIp(), count.getOrDefault(server.getIp(), 0) 1); } assertEquals(50, count.get(A).intValue()); assertEquals(10, count.get(B).intValue()); assertEquals(10, count.get(C).intValue()); }这里 total 取 70 是因为 5:1:1 的最小完整循环是 7 次511跑 10 个循环正好 70 次。一致性哈希的测试更关键需要验证“节点增减时受影响 key 的比例”Test public void testConsistentHashAffectedKeys() { ListServer original Arrays.asList( new Server(node1, 1), new Server(node2, 1), new Server(node3, 1) ); ConsistentHashLoadBalancer origin new ConsistentHashLoadBalancer(original, 200); // 生成 1000 个 key 并记录初始映射 MapString, String mapping new HashMap(); for (int i 0; i 1000; i) { mapping.put(key i, origin.select(new Request(key i)).getIp()); } // 移除 node1 ListServer scaled Arrays.asList( new Server(node2, 1), new Server(node3, 1) ); ConsistentHashLoadBalancer scaledBalancer new ConsistentHashLoadBalancer(scaled, 200); int changed 0; for (int i 0; i 1000; i) { String newAddr scaledBalancer.select(new Request(key i)).getIp(); if (!mapping.get(key i).equals(newAddr)) { changed; } } // 一致性哈希只影响约 1/3 的 key assertTrue(changed ratio (changed / 1000.0), changed 200 changed 500); }这个测试能直接验证一致性哈希的“最小迁移”特性。如果节点从 3 个减到 2 个受到影响的比例应该大约是 1/3而不是 100%。测试最好在 CI 里持续跑配合随机种子固定做模糊测试。手写算法最大的风险其实是“改了一个小地方影响了一大片”——没有回归测试兜底你根本不敢动。7. 最后的工程实感我个人在实际操作中的一个核心认知是负载均衡算法不是越复杂越好而是越可控越好。在大量生产实践中证明大部分系统用平滑加权轮询就足够了一致性哈希解决有状态问题最少活跃数解决慢节点问题——三个算法吃遍 95% 的场景。手写的过程最大的价值是让你获得对流量调度这件事的“手感”你会开始理解为什么某些框架默认选择某个策略为什么某个参数默认值是那样。还有一个容易被忽略的点手写的负载均衡算法一定要配套可视化监控。节点流量分布、单节点 QPS、响应时间、活跃连接数、错误数这些指标一出来算法的实际效果一目了然。没有监控就上线等于闭着眼睛开车算法写得再精致也没有意义。如果你现在正打算在项目里动手写一套我建议你从平滑加权轮询开始练手。它足够简单但包含的状态和并发细节足够让你踩一遍关键坑踩完你再来写一致性哈希就会顺手很多。把这套东西写明白之后无论是自己搭网关、做 RPC 框架还是面试讲架构你的底气都会完全不一样。最后分享一个我压箱底的小技巧手写算法时先把所有状态变量的可见性和具体语义写进注释比如“currentWeight 代表这个节点在下次选中的优先度数值越大越优先”。一旦状态语义模糊后续维护的人大概率会改出一堆隐蔽 bug。好的注释不是解释代码在做什么而是解释代码为什么要这样做——这一点在手写负载均衡这种“少代码多状态”的算法里比什么都重要。
阅读完成 · 觉得有帮助？
