尧图网页设计 
手写负载均衡算法这件事我在面试候选人的时候几乎必问。不是因为我喜欢刁难人而是这个题目能一次性考察至少三样东西你对分布式系统基础的理解、你的代码功底、以及你设计代码时有没有工程意识。好多人能把负载均衡这个词挂在嘴边但真让他们在白板上写一个轮询算法能把边界条件处理明白的都算少见更别说平滑加权轮询和一致性哈希这种进阶版本了。这篇文章我就把这七种算法的 Java 实现从头到尾拆一遍每个算法都会给出可直接运行的完整代码解释背后的设计思路和适用场景。不论你是在准备面试还是想在项目里落地一个轻量级的客户端负载均衡器这篇都能给你一个完整的参考骨架。1. 整体设计与思路拆解1.1 为什么非要手写这七种算法市面上现成的负载均衡组件太多了Nginx、Spring Cloud LoadBalancer、Dubbo 内部都自带各种策略那自己手写一遍的价值在哪里我的观点是写一遍和用一遍对算法的理解深度完全是两码事。你用 Nginx 配一个weighted策略三分钟就搞定但你不看源码的话永远不会知道加权轮询在权重动态变化时会踩到什么坑也不会理解为什么 Nginx 要用平滑加权轮询而不是简单的加权轮询。手写的价值不在造轮子而在拆轮子——把一个看似简单的策略拆到代码层面你才能真正把握它的适用边界。另外还有一个非常现实的原因面试。翻翻大厂的 Java 面试题手写负载均衡算法几乎成了八股文标配。轮询、随机是最基础的入场题平滑加权轮询和一致性哈希则是拉开差距的进阶题。与其临时抱佛脚去背题不如静下心来把这七种算法一次性写透面试时你不仅能写出代码还能把每种算法的设计动机和优缺点讲明白这绝对是加分项。1.2 公共接口与核心数据结构设计手写一套负载均衡算法第一步不是急着实现而是把公共接口抽出来。一个好的接口抽象能让你后续新增算法变得非常轻松。public interface LoadBalancer { /** * 从服务列表中选定一个可用节点 * * param servers 可用节点列表 * param sourceIp 来源IP一致性哈希算法会用到 * return 选中的节点 */ Invoker select(ListInvoker servers, String sourceIp); }这里我用了一个Invoker类来抽象节点信息它承载的字段直接决定了下层算法的实现空间public class Invoker { /** 节点的唯一标识ip:port */ private final String id; /** 节点权重加权类算法会用到 */ private final int weight; /** 当前活跃连接数最少连接算法会用到 */ private final AtomicInteger activeCount; public Invoker(String id, int weight) { this.id id; this.weight weight; this.activeCount new AtomicInteger(0); } public String getId() { return id; } public int getWeight() { return weight; } public AtomicInteger getActiveCount() { return activeCount; } Override public String toString() { return id (weight weight ); } }为什么用AtomicInteger来记录活跃连接数因为负载均衡器往往是多线程并发的场景多个请求同时进来如果用普通的int自增就会出现线程安全问题统计出来的连接数不准整个最少连接算法也就失去了意义。这里直接用AtomicInteger既保证线程安全代码也简洁。定义一个选择方法时我特意带上了sourceIp,有人可能觉得冗余——轮询、随机这些算法确实不需要它但一致性哈希必须要用到请求来源的特征值来做哈希映射。接口统一带上这个参数后续扩展就不会面临又要改接口的窘境。2. 七种核心算法逐一拆解2.1 轮询与加权轮询最朴素的分配策略轮询Round Robin是负载均衡世界里的Hello World它做的事情就是按照服务器列表的顺序依次把请求分发到每一台服务器上。张三、李四、王五轮流来谁也不多谁也不少。public class RoundRobinLoadBalancer implements LoadBalancer { private final AtomicInteger index new AtomicInteger(0); Override public Invoker select(ListInvoker servers, String sourceIp) { if (servers null || servers.isEmpty()) { throw new IllegalArgumentException(服务器列表不能为空); } int current Math.abs(index.getAndIncrement() % servers.size()); return servers.get(current); } }这段代码只有三行核心逻辑但有两个细节值得你细品。第一个细节是为什么要用Math.abs()。取模运算在 Java 中遇到负数会得到负结果而index是AtomicInteger如果并发量极大getAndIncrement()的值溢出变成负数直接取模就会得到负下标导致IndexOutOfBoundsException。用Math.abs()包一层可以规避这个问题但不能完全依赖它——因为Integer.MIN_VALUE取绝对值会溢出变成负数,这是Math.abs()的一个著名坑。更稳妥的写法是(index.getAndIncrement() Integer.MAX_VALUE) % servers.size()。不过实际上AtomicInteger 溢出到负数要几十亿次请求多数场景下Math.abs()够用了但面试时你能主动提出来 Integer.MIN_VALUE 会溢出这就是一个让面试官眼前一亮的细节。第二个细节是关于AtomicInteger的getAndIncrement()它保证的是取值再自增这个组合操作的原子性。高并发下多个线程同时调用拿到的值各不相同这样请求才会均匀地分散到不同服务器上。如果换成int index this.index并发就瞬间崩了多个线程拿到同一个值请求全打在同一台服务器上负载均衡就变成了负载倾斜。手写算法时并发安全是必须跨过的一道坎。轮询的优点是简单、无状态缺点是它假设了所有服务器的处理能力是一样的。但现实世界里一台 8 核 16G 的机器和一台 2 核 4G 的机器处理能力能一样吗显然不能。于是就有了加权轮询——给每台机器配一个权重权重高的分到更多的请求。加权轮询的实现思路有两种我先写最简单的那一种public class WeightedRoundRobinLoadBalancer implements LoadBalancer { private final AtomicInteger index new AtomicInteger(0); Override public Invoker select(ListInvoker servers, String sourceIp) { if (servers null || servers.isEmpty()) { throw new IllegalArgumentException(服务器列表不能为空); } int totalWeight servers.stream().mapToInt(Invoker::getWeight).sum(); if (totalWeight 0) { return new RoundRobinLoadBalancer().select(servers, sourceIp); } int current Math.abs(index.getAndIncrement() % totalWeight); for (Invoker server : servers) { current - server.getWeight(); if (current 0) { return server; } } // 理论上不会走到这里 return servers.get(0); } }这段代码的核心逻辑是把所有节点的权重累加成一个总区间[0, totalWeight)然后拿计数器取模得到一个随机落点再从第一个节点开始逐个减去权重直到落入某个节点的权重区间。这个方案确实能实现权重越高、被选中的概率越大。但接下来我要讲一个它解决不了的问题它会产生连续请求集中打到某个节点上的现象。假设服务器 A 的权重是 5服务器 B 的权重是 1那么计数器连续取模得到的落点会落在 A 的区间里好多次导致短时间内 A 会被连续命中 5 次B 要等好久才被轮到一次。这不算错但资源利用率并不均衡——理想情况应该是 A 和 B 交替被选中只是 A 的出现频次更高而不是 A 连着处理 5 个请求、B 闲着。这个问题的真正解法就是后面要讲的平滑加权轮询Nginx 官方用的就是这种策略。这里先按下不表。2.2 随机与加权随机概率的艺术随机算法的思路就更直接了从服务器列表里随机挑一个。在请求量足够大的时候随机算法的效果会趋近于轮询因为大数定律会帮你把概率拉平。但它的好处是天然避免了连续集中的问题——你无法预测下一个请求会落到哪台机器上整体流量却又是均衡的。public class RandomLoadBalancer implements LoadBalancer { Override public Invoker select(ListInvoker servers, String sourceIp) { if (servers null || servers.isEmpty()) { throw new IllegalArgumentException(服务器列表不能为空); } int index ThreadLocalRandom.current().nextInt(servers.size()); return servers.get(index); } }这里有一个细节我用了ThreadLocalRandom而不是Random。在高并发场景下Random内部的 CAS 操作会成为一个竞争热点多个线程抢同一个种子性能会急剧下降。ThreadLocalRandom把随机种子放到了每个线程自己的 ThreadLocal 里各个线程各用各的种子互不干扰并发性能比Random好一大截。这是一个 Java 并发编程的经典优化点也是我在代码审查时一眼就能看出来的是否懂并发的分水岭。加权随机的实现逻辑和加权轮询非常像区别只在于一个是计数器取模一个是随机数取模public class WeightedRandomLoadBalancer implements LoadBalancer { Override public Invoker select(ListInvoker servers, String sourceIp) { if (servers null || servers.isEmpty()) { throw new IllegalArgumentException(服务器列表不能为空); } int totalWeight servers.stream().mapToInt(Invoker::getWeight).sum(); if (totalWeight 0) { return new RandomLoadBalancer().select(servers, sourceIp); } int random ThreadLocalRandom.current().nextInt(totalWeight); for (Invoker server : servers) { random - server.getWeight(); if (random 0) { return server; } } return servers.get(0); } }加权随机和加权轮询共享了同一个区间落点模型所以我建议你在设计代码时把这段区间落点的逻辑抽成一个公共方法四个算法(加权轮询、加权随机、平滑加权轮询)都能复用。这不仅仅是代码美观的问题更是工程素养的体现——面试官看你写代码不只是看你写不写得对更看你能不能识别出公共抽象层。2.3 最少连接让忙碌者休息让空闲者上岗前面几种算法都是事前分配——根据固定的权重或序号把请求平均分出去。但真实的线上场景里每个请求的处理难度是不一样的。有的请求只是查个缓存毫秒级返回有的请求要查多个数据库、调多个外部接口可能要几百毫秒甚至更久。按权重分配请求数的策略在这种场景下就失灵了——分配得再均匀服务器收到的工作量也可能很不均匀。最少连接算法Least Connections的思路是事后调度谁手里的活最少就把新请求派给谁。它不再关注你分到了多少个请求而是关注你当前正在处理多少个请求。public class LeastConnectionLoadBalancer implements LoadBalancer { Override public Invoker select(ListInvoker servers, String sourceIp) { if (servers null || servers.isEmpty()) { throw new IllegalArgumentException(服务器列表不能为空); } Invoker leastActiveInvoker null; int leastActiveCount Integer.MAX_VALUE; for (Invoker server : servers) { int currentActive server.getActiveCount().get(); if (currentActive leastActiveCount) { leastActiveCount currentActive; leastActiveInvoker server; } } return leastActiveInvoker; } }这段代码的核心是一个线性扫描找出活跃连接数最小的节点。但如果你想在真实项目里用它光有这段代码是不够的——你必须在请求开始处理时对节点的activeCount做incrementAndGet()在请求处理完毕时做decrementAndGet()这个钩子怎么接我一般会在业务代码的过滤器Filter或拦截器Interceptor里统一处理。Spring Boot 项目可以写一个OncePerRequestFilter在doFilter之前给选中的节点加一在finally块里减一。这样能保证即使请求抛出异常计数也能正确释放不会出现连接数越积越多的内存泄漏式bug。最少连接算法的缺点也很明显它要求负载均衡器能实时掌握每个节点的连接状态这在高并发场景下本身就是一个不小的性能开销。另外如果所有请求的处理时长差异巨大——比如一百个快请求和五个慢请求——最少连接依然可能出现抖动。所以它更适合那些请求处理时间分布不均匀、但对实时性要求较高的中间件场景。像 Dubbo 的负载均衡里就有LeastActiveLoadBalance和这个原理基本一致只是他加上了权重来计算预热时的修正值面试的时候能提一嘴我看过 Dubbo 源码含金量会高很多。2.4 一致性哈希解决分布式缓存的命中率问题前面讲的算法都是与请求内容无关的——同一个用户的请求可能这次被分到 A 节点下次就被分到 B 节点。大部分业务场景下这没什么问题但如果节点后面挂着的是本地缓存或者 Session 会话问题就来了用户在 A 节点登录了下次请求却被路由到 B 节点B 节点没有他的会话数据要么重新登录要么缓存失效重新查库。解决这个问题最经典的方案就是一致性哈希Consistent Hashing。它的核心思想是把整个哈希值空间组织成一个虚拟的环节点通过哈希函数分布在环上请求也通过哈希函数映射到环上然后顺时针找最近的节点这样同一个客户端请求始终会路由到同一个节点。public class ConsistentHashLoadBalancer implements LoadBalancer { private static final int VIRTUAL_NODE_COUNT 160; private final TreeMapLong, Invoker hashRing new TreeMap(); public ConsistentHashLoadBalancer(ListInvoker servers) { for (Invoker server : servers) { addNode(server); } } public void addNode(Invoker invoker) { for (int i 0; i VIRTUAL_NODE_COUNT; i) { long hash hash(invoker.getId() -vn- i); hashRing.put(hash, invoker); } } public void removeNode(Invoker invoker) { for (int i 0; i VIRTUAL_NODE_COUNT; i) { long hash hash(invoker.getId() -vn- i); hashRing.remove(hash); } } Override public Invoker select(ListInvoker servers, String sourceIp) { if (sourceIp null || sourceIp.isEmpty()) { throw new IllegalArgumentException(一致性哈希需要来源IP作为路由依据); } if (hashRing.isEmpty()) { throw new IllegalArgumentException(哈希环为空请先添加节点); } long hash hash(sourceIp); // 找到第一个哈希值大于等于该请求哈希值的节点 Map.EntryLong, Invoker entry hashRing.ceilingEntry(hash); if (entry null) { // 如果超出环的末尾则取环的第一个节点 entry hashRing.firstEntry(); } return entry.getValue(); } private long hash(String key) { MessageDigest md; try { md MessageDigest.getInstance(MD5); } catch (NoSuchAlgorithmException e) { throw new RuntimeException(MD5算法不可用, e); } byte[] digest md.digest(key.getBytes(StandardCharsets.UTF_8)); return ((long) (digest[3] 0xFF) 24) | ((long) (digest[2] 0xFF) 16) | ((long) (digest[1] 0xFF) 8) | (digest[0] 0xFF); } }这里面有几个非常关键的设计决策我得逐个讲清楚。首先是 TreeMap 的选择。它有序且支持ceilingEntry()操作可以快速找到不小于给定 key 的最小 entry这正好就是哈希环上顺时针找下一个节点的定义。如果用 HashMap你得自己遍历所有 key 去比较大小效率低不说代码还会很啰嗦。其次是虚拟节点的作用。如果只有真实的节点映射到哈希环上节点数量少的时候会出现严重的分布不均——假设三个节点哈希后挤在环的同一个半区那落在另外半个区的请求会全部路由到某一个节点负载就偏了。虚拟节点的思路是把每个真实节点复制出多个虚拟副本均匀地分布在环上让每个真实节点负责的环段长度趋于一致。我这边选了 160 个虚拟节点这个数字不是拍脑袋定的——Dubbo 里的一致性哈希默认也是 160。虚拟节点太少分布可能不均太多又会浪费内存。160 是一个经过生产验证的合理值。第三是哈希函数的选择。计算虚拟节点哈希时我没有用hashCode()而是用了 MD5 取 32 位。String.hashCode()的分布性不够好在节点少时容易产生哈希碰撞MD5 算法虽然老化但当哈希函数时它的雪崩效应和均匀性依然很出色。取 32 位是为了能用long来直接放在 TreeMap 里没必要取完整的 128 位。一致性哈希的最大优点是当新增或移除节点时只有环上相邻的那一小段请求会被重新路由其他绝大部分请求的映射关系保持不变。这正好解决了分布式缓存场景下的缓存雪崩问题——如果拿普通的加权轮询扩容一台机器所有请求的缓存映射全变了大量缓存同时失效数据库瞬间被冲垮这是生产事故级别的问题。2.5 平滑加权轮询Nginx 官方的平滑之道终于到了我最喜欢的算法。前面讲加权轮询的时候我留下了一个悬念简单加权轮询会引起连续请求集中在高权重节点那么 Nginx 是怎么解决这个问题的答案在 Nginx 官方文档里写得清清楚楚平滑加权轮询Smooth Weighted Round Robin。这个算法的精妙之处在于它通过动态调整节点的当前权重让请求在宏观上按权重比例分布微观上却尽可能分散不会出现一台机器被连续打完才轮到下一台的尴尬局面。算法只有四步极其简洁每次请求到来时把每个节点的当前权重currentWeight加上它的原始权重weight从所有节点中选出当前权重最大的节点作为本次请求的目标把选中的节点当前的权重减去所有节点的原始权重之和totalWeight重复以上步骤。public class SmoothWeightedRoundRobinLoadBalancer implements LoadBalancer { private final MapString, Integer currentWeightMap new ConcurrentHashMap(); Override public synchronized Invoker select(ListInvoker servers, String sourceIp) { if (servers null || servers.isEmpty()) { throw new IllegalArgumentException(服务器列表不能为空); } int totalWeight servers.stream().mapToInt(Invoker::getWeight).sum(); if (totalWeight 0) { return new RoundRobinLoadBalancer().select(servers, sourceIp); } Invoker selected null; int maxCurrentWeight Integer.MIN_VALUE; for (Invoker server : servers) { int weight server.getWeight(); int currentWeight currentWeightMap.getOrDefault(server.getId(), 0) weight; currentWeightMap.put(server.getId(), currentWeight); if (currentWeight maxCurrentWeight) { maxCurrentWeight currentWeight; selected server; } } // 选中的节点减去总权重 currentWeightMap.put(selected.getId(), currentWeightMap.get(selected.getId()) - totalWeight); return selected; } }来我们用一个具体的例子演算一遍。假设 A 的权重是 5B 的权重是 1两个节点原始权重总数为 6。第 1 个请求A 的当前权重为 055B 的当前权重为 011选 AA 的当前权重变为 5-6-1。此时 A-1B1。第 2 个请求A 的当前权重为 -154B 的当前权重为 112选 AA 的当前权重变为 4-6-2。此时 A-2B2。第 3 个请求A 的当前权重为 -253B 的当前权重为 213当前权重相同。选谁呢按我代码的逻辑currentWeight maxCurrentWeight才会更新所以会选到先遍历到的节点假设是 AA 的当前权重变为 3-6-3。此时 A-3B3。第 4 个请求A 的当前权重为 -352B 的当前权重为 314选 BB 的当前权重变为 4-6-2。此时 A2B-2。第 5 个请求A257B-21-1选 AA 重置为 7-61。第 6 个请求A156B-110选 AA 重置为 6-60。6 个请求的序列是A, A, A, B, A, A。A 被选了 5 次B 被选了 1 次权重比例 5:1 完全正确但是 B 在第 4 个请求就被选中了而不是傻等到前 5 个请求全打完再轮到自己。这就是平滑二字的真正含义——高权重的节点依然承担更多流量但低权重节点不会被饿死它会周期性地插入到请求序列中。我在实现里给select方法加了synchronized这是因为currentWeightMap的读取和更新不是一个原子操作高并发下如果不加锁多个线程同时读到同一个currentWeight值就会选出同一个节点。这又是并发安全的一个细节。你也可以用AtomicInteger来存当前权重配合 CAS 操作来消除锁但代码复杂度会上升。在这个算法的场景下加锁完全够用毕竟它本身要遍历所有节点做权重计算锁的粒度并不会成为性能瓶颈。3. 实测对比与场景选型3.1 七种算法的核心指标横向对比代码写完了接下来我把七种算法放在一张表格里做个横向对比这样你在面试时或者实际选型时可以一目了然算法平均性实现复杂度是否感知节点状态是否保持会话粘滞典型应用场景轮询优极低否否无状态服务、请求处理时长相近的场景加权轮询优低否否服务器配置差异明显的静态集群随机良极低否否请求量足够大的无状态服务加权随机良低否否服务器配置差异较大且请求量大的场景最少连接优中是否请求处理时长波动大的场景一致性哈希良高否是本地缓存、分布式Session、状态ful服务平滑加权轮询优中否否Nginx默认策略、网关层流量分发平均性这个指标我要单独解释一下。轮询的平均性最好因为它是严格的轮流制加权轮询的平均性也好但它好得太机械短时间窗口内请求会集中打在权重最高的节点上加权随机的平均性取决于随机数质量在请求量不够大时短时间窗口内可能出现偏差。最少连接的平均性则是按需分配它能自动纠偏但需要额外的状态维护成本。3.2 真实业务场景中怎么选这些算法到底怎么选我给你几个真实案例做参考。微服务网关层选型。网关是所有请求的入口流量大、要求分配均匀、无状态。这种情况下我首推平滑加权轮询——它能在权重比例正确的前提下做到请求序列平滑交错不会出现某台机器一会儿忙死一会儿闲死的情况。如果服务节点的处理能力强弱差别不大也可以直接用最基础的轮询简单可靠排障方便。分布式缓存场景选型。如果节点后面挂着 Redis 本地缓存或者进程内缓存那就不用考虑了直接用一致性哈希。否则每次扩容缩容都会引发缓存大面积失效数据库会被瞬时流量打崩。我在上家公司就踩过这个坑——缓存集群扩容之前用的是加权轮询扩容那天下班前还好好的第二天一早数据库直接挂了因为 30% 的请求都穿透到数据库了。后来把负载均衡策略改成一致性哈希扩容再也没出过事。RPC 调用场景选型。Dubbo、gRPC 这类 RPC 框架的负载均衡我建议用最少连接或自适应算法。因为 RPC 调用往往是嵌套的、有依赖的有的调用要等下游服务响应很久连接数能更真实地反映节点的繁忙程度。Dubbo 的官方实现里也是把LeastActive作为推荐的负载均衡策略之一这和生产环境验证过的经验是一致的。请求处理时长相对稳定的内部 API 服务选型。轮询就够了。我曾经把一个内部服务的负载均衡策略从轮询换成平滑加权轮询效果提升不明显反而因为引入了权重配置而增加了运维成本。很多场景里最朴素的算法恰恰是最合适的。别为了炫技而选型这是我在这个领域踩了几年坑之后最深的体会。4. 高频面试题与避坑指南4.1 面试官最爱追问的六个问题手写负载均衡算法只是面试的第一关写完之后面试官一定会做一轮连环追问。我整理了六个高频问题把参考回答一并给出。第一个问题Nginx 默认的负载均衡算法是加权轮询还是平滑加权轮询如果你答加权轮询大概率会被追问那你说说它有什么缺点。这个问题的标准答案我建议这样组织Nginx 默认支持两种轮询不带权重的是普通轮询带权重的是平滑加权轮询。值得注意的是Nginx 源码里对带权重的轮询采用了平滑算法而不是教科书里那种简单的按权重区间分段分配。这也是为什么 Nginx 的流控在权重差异比较大的时候依然能保持比较好的平滑性。第二个问题为什么要用虚拟节点不用行不行不用虚拟节点节点数量少时哈希环的分布会严重不均匀假设三台机器的哈希值都落在环的上半区下半区的请求就会全部打到同一台机器上。虚拟节点把每个真实节点复制为多个虚拟副本散布在环上使得每个节点负责的环段长度趋于均匀。面试时你还可以补充一句虚拟节点的数量也有讲究我从 Dubbo 源码里看到的默认值是 160取值太低会不均匀取值太高浪费内存。第三个问题一致性哈希遇到高并发时那个用于选择节点的 TreeMap 会被并发访问吗会。所以在真实项目里要么加锁保护 TreeMap 的读操作要么用ConcurrentSkipListMap替代 TreeMap。我曾经在一个高并发项目里用过 TreeMap 的ceilingEntry方法发现并发读写时偶尔会抛ConcurrentModificationException排查了很久才意识到问题出在节点动态增删和请求路由同时发生时。换成ConcurrentSkipListMap之后问题就消失了它内部用跳表实现支持并发安全的导航方法复杂度也只是 O(log n)。第四个问题最少连接算法里如果所有节点的活跃连接数都是 0会发生什么直接返回第一个节点。这在所有节点都没有流量时会形成一个热点每次请求都打到第一个节点上。所以我一般会建议在活跃连接数相同的情况下做一次加权随机或轮询兜底避免随机固定到第一台的尴尬。第五个问题平滑加权轮询算法的平滑是怎么实现的它的本质是让每个节点的当前权重在一个动态区间内波动选中的节点会被惩罚——减去总权重让它的下一次竞争力变弱没选中的节点会被鼓励——加上自己的原始权重慢慢积累竞争力。这样权重高的节点不会被连续选中太多轮权重低的节点也能周期性地被选中宏观比例正确微观节奏均匀。第六个问题你刚才实现的是客户端负载均衡还是服务端负载均衡两者有什么区别服务端负载均衡比如 Nginx是在请求进入服务端之前由独立的负载均衡器分发客户端负载均衡比如 Ribbon、Dubbo 的负载均衡是在发起 RPC 调用时由调用方自己从服务注册中心拉取服务列表再按某种策略选择一个节点发起调用。我这个代码实现的是客户端负载均衡的思路因为它直接面向服务提供者列表做选择而 Nginx 还需要处理连接管理、健康检查等额外的逻辑。4.2 手写实现中的常见坑与排查思路代码写完并不代表万事大吉。这几个坑是我自己在实际项目中踩过的或者帮别人 review 代码时反复看到的你一定要当心。第一个坑Math.abs(index.getAndIncrement()) % servers.size()在极端情况下会出现负下标。Math.abs(Integer.MIN_VALUE)的结果还是负数这是 Java 语言层面的隐藏坑。解决办法是用Math.floorMod()或者先与Integer.MAX_VALUE做位与操作再取模。虽然要触发Integer.MIN_VALUE需要几十亿次请求但作为有经验的开发者你应该主动写出更健壮的取模表达式。第二个坑加权轮询的节点列表在运行时动态变化时计数器取模的totalWeight必须实时计算。如果你把它缓存到一个静态变量里新增节点后缓存没更新新节点永远分不到流量。我的建议是每次select时都重新计算totalWeight或者在你更新节点列表时同步刷新缓存并且保证这两个操作之间没有并发窗口。第三个坑最少连接算法的计数器必须在 finally 块里递减。如果请求发生异常导致activeCount没有减回去这个节点的活跃连接数就会永远偏大导致它再也分不到新请求——实际上形成了一种引用泄漏。这个 bug 在测试环境不容易暴露因为流量小但一旦上生产遇到异常流量一冲某几个节点就假死了。排查方法是监控每个节点的activeCount是否长期居高不下。第四个坑一致性哈希在节点增删时需要重建虚拟节点映射。如果你直接用构造函数传入初始节点列表后续节点扩容时忘记调用addNode那么新节点永远不会出现在哈希环上。我建议把节点管理的逻辑单独封装成一个NodeManager提供register和unregister方法内部自动维护哈希环的一致性。调用方只需要关心节点注册和反注册不需要关心哈希环的细节。第五个坑不正确地使用ConcurrentHashMap存储当前权重。ConcurrentHashMap的每个操作是线程安全的但是先读后写再读这个复合操作不是原子的。平滑加权轮询的整个流程里多个线程同时执行读取 currentWeight 并加上 weight会导致计算结果互相覆盖。我见过不少人以为用了ConcurrentHashMap就万事大吉了结果高并发下一测就发现权重计算错误。要么在select方法上加锁要么用compute方法配合原子操作来完成读改写。第六个坑负载均衡算法本身没有对节点做健康检查。如果一台机器已经宕机了但它还在服务列表里轮询算法照样会把它选出来导致请求失败。真实项目里一定要配合健康检查机制——定期探活、把不健康的节点从列表里摘除。我在代码示例里没有加这个逻辑是为了让算法部分更聚焦但你在落地时一定要补上这个环节。收尾把代码变成你自己的七种算法到这里就全部写完了。如果你只是看着代码觉得嗯挺简单的然后就把文章关掉那这些代码并不属于你。我的建议是你打开 IDE新建一个LoadBalancer接口然后把七种算法逐个敲一遍敲的过程中尝试回答下面几个问题轮询算法的并发安全靠什么保证平滑加权轮询为什么要用 synchronized如果你来设计你会怎么优化一致性哈希的虚拟节点数量敲完之后你还可以做一件更有意思的事写一个简单的测试类模拟 100 万个请求分别用七种算法做分发统计每台节点收到的请求数量和分布曲线。然后你可能会发现理论分析和真实的随机分布之间确实存在差距——这个差距就是你对算法的理解从看得懂变成讲得清的关键一步。最后分享一个我自己的小习惯每次新接手一个分布式系统的项目我做的第一件事就是看它的负载均衡配置和实现。负载均衡是系统的流量入口从它入手你不仅能理解系统的容量设计思路还能快速发现潜在的性能瓶颈。把这七种算法吃透你看任何一款中间件的负载均衡源码都会轻松很多。 Java手写负载均衡算法：七种策略详解与代码实现
手写负载均衡算法这件事我在面试候选人的时候几乎必问。不是因为我喜欢刁难人而是这个题目能一次性考察至少三样东西你对分布式系统基础的理解、你的代码功底、以及你设计代码时有没有工程意识。好多人能把负载均衡这个词挂在嘴边但真让他们在白板上写一个轮询算法能把边界条件处理明白的都算少见更别说平滑加权轮询和一致性哈希这种进阶版本了。这篇文章我就把这七种算法的 Java 实现从头到尾拆一遍每个算法都会给出可直接运行的完整代码解释背后的设计思路和适用场景。不论你是在准备面试还是想在项目里落地一个轻量级的客户端负载均衡器这篇都能给你一个完整的参考骨架。1. 整体设计与思路拆解1.1 为什么非要手写这七种算法市面上现成的负载均衡组件太多了Nginx、Spring Cloud LoadBalancer、Dubbo 内部都自带各种策略那自己手写一遍的价值在哪里我的观点是写一遍和用一遍对算法的理解深度完全是两码事。你用 Nginx 配一个weighted策略三分钟就搞定但你不看源码的话永远不会知道加权轮询在权重动态变化时会踩到什么坑也不会理解为什么 Nginx 要用平滑加权轮询而不是简单的加权轮询。手写的价值不在造轮子而在拆轮子——把一个看似简单的策略拆到代码层面你才能真正把握它的适用边界。另外还有一个非常现实的原因面试。翻翻大厂的 Java 面试题手写负载均衡算法几乎成了八股文标配。轮询、随机是最基础的入场题平滑加权轮询和一致性哈希则是拉开差距的进阶题。与其临时抱佛脚去背题不如静下心来把这七种算法一次性写透面试时你不仅能写出代码还能把每种算法的设计动机和优缺点讲明白这绝对是加分项。1.2 公共接口与核心数据结构设计手写一套负载均衡算法第一步不是急着实现而是把公共接口抽出来。一个好的接口抽象能让你后续新增算法变得非常轻松。public interface LoadBalancer { /** * 从服务列表中选定一个可用节点 * * param servers 可用节点列表 * param sourceIp 来源IP一致性哈希算法会用到 * return 选中的节点 */ Invoker select(ListInvoker servers, String sourceIp); }这里我用了一个Invoker类来抽象节点信息它承载的字段直接决定了下层算法的实现空间public class Invoker { /** 节点的唯一标识ip:port */ private final String id; /** 节点权重加权类算法会用到 */ private final int weight; /** 当前活跃连接数最少连接算法会用到 */ private final AtomicInteger activeCount; public Invoker(String id, int weight) { this.id id; this.weight weight; this.activeCount new AtomicInteger(0); } public String getId() { return id; } public int getWeight() { return weight; } public AtomicInteger getActiveCount() { return activeCount; } Override public String toString() { return id (weight weight ); } }为什么用AtomicInteger来记录活跃连接数因为负载均衡器往往是多线程并发的场景多个请求同时进来如果用普通的int自增就会出现线程安全问题统计出来的连接数不准整个最少连接算法也就失去了意义。这里直接用AtomicInteger既保证线程安全代码也简洁。定义一个选择方法时我特意带上了sourceIp,有人可能觉得冗余——轮询、随机这些算法确实不需要它但一致性哈希必须要用到请求来源的特征值来做哈希映射。接口统一带上这个参数后续扩展就不会面临又要改接口的窘境。2. 七种核心算法逐一拆解2.1 轮询与加权轮询最朴素的分配策略轮询Round Robin是负载均衡世界里的Hello World它做的事情就是按照服务器列表的顺序依次把请求分发到每一台服务器上。张三、李四、王五轮流来谁也不多谁也不少。public class RoundRobinLoadBalancer implements LoadBalancer { private final AtomicInteger index new AtomicInteger(0); Override public Invoker select(ListInvoker servers, String sourceIp) { if (servers null || servers.isEmpty()) { throw new IllegalArgumentException(服务器列表不能为空); } int current Math.abs(index.getAndIncrement() % servers.size()); return servers.get(current); } }这段代码只有三行核心逻辑但有两个细节值得你细品。第一个细节是为什么要用Math.abs()。取模运算在 Java 中遇到负数会得到负结果而index是AtomicInteger如果并发量极大getAndIncrement()的值溢出变成负数直接取模就会得到负下标导致IndexOutOfBoundsException。用Math.abs()包一层可以规避这个问题但不能完全依赖它——因为Integer.MIN_VALUE取绝对值会溢出变成负数,这是Math.abs()的一个著名坑。更稳妥的写法是(index.getAndIncrement() Integer.MAX_VALUE) % servers.size()。不过实际上AtomicInteger 溢出到负数要几十亿次请求多数场景下Math.abs()够用了但面试时你能主动提出来 Integer.MIN_VALUE 会溢出这就是一个让面试官眼前一亮的细节。第二个细节是关于AtomicInteger的getAndIncrement()它保证的是取值再自增这个组合操作的原子性。高并发下多个线程同时调用拿到的值各不相同这样请求才会均匀地分散到不同服务器上。如果换成int index this.index并发就瞬间崩了多个线程拿到同一个值请求全打在同一台服务器上负载均衡就变成了负载倾斜。手写算法时并发安全是必须跨过的一道坎。轮询的优点是简单、无状态缺点是它假设了所有服务器的处理能力是一样的。但现实世界里一台 8 核 16G 的机器和一台 2 核 4G 的机器处理能力能一样吗显然不能。于是就有了加权轮询——给每台机器配一个权重权重高的分到更多的请求。加权轮询的实现思路有两种我先写最简单的那一种public class WeightedRoundRobinLoadBalancer implements LoadBalancer { private final AtomicInteger index new AtomicInteger(0); Override public Invoker select(ListInvoker servers, String sourceIp) { if (servers null || servers.isEmpty()) { throw new IllegalArgumentException(服务器列表不能为空); } int totalWeight servers.stream().mapToInt(Invoker::getWeight).sum(); if (totalWeight 0) { return new RoundRobinLoadBalancer().select(servers, sourceIp); } int current Math.abs(index.getAndIncrement() % totalWeight); for (Invoker server : servers) { current - server.getWeight(); if (current 0) { return server; } } // 理论上不会走到这里 return servers.get(0); } }这段代码的核心逻辑是把所有节点的权重累加成一个总区间[0, totalWeight)然后拿计数器取模得到一个随机落点再从第一个节点开始逐个减去权重直到落入某个节点的权重区间。这个方案确实能实现权重越高、被选中的概率越大。但接下来我要讲一个它解决不了的问题它会产生连续请求集中打到某个节点上的现象。假设服务器 A 的权重是 5服务器 B 的权重是 1那么计数器连续取模得到的落点会落在 A 的区间里好多次导致短时间内 A 会被连续命中 5 次B 要等好久才被轮到一次。这不算错但资源利用率并不均衡——理想情况应该是 A 和 B 交替被选中只是 A 的出现频次更高而不是 A 连着处理 5 个请求、B 闲着。这个问题的真正解法就是后面要讲的平滑加权轮询Nginx 官方用的就是这种策略。这里先按下不表。2.2 随机与加权随机概率的艺术随机算法的思路就更直接了从服务器列表里随机挑一个。在请求量足够大的时候随机算法的效果会趋近于轮询因为大数定律会帮你把概率拉平。但它的好处是天然避免了连续集中的问题——你无法预测下一个请求会落到哪台机器上整体流量却又是均衡的。public class RandomLoadBalancer implements LoadBalancer { Override public Invoker select(ListInvoker servers, String sourceIp) { if (servers null || servers.isEmpty()) { throw new IllegalArgumentException(服务器列表不能为空); } int index ThreadLocalRandom.current().nextInt(servers.size()); return servers.get(index); } }这里有一个细节我用了ThreadLocalRandom而不是Random。在高并发场景下Random内部的 CAS 操作会成为一个竞争热点多个线程抢同一个种子性能会急剧下降。ThreadLocalRandom把随机种子放到了每个线程自己的 ThreadLocal 里各个线程各用各的种子互不干扰并发性能比Random好一大截。这是一个 Java 并发编程的经典优化点也是我在代码审查时一眼就能看出来的是否懂并发的分水岭。加权随机的实现逻辑和加权轮询非常像区别只在于一个是计数器取模一个是随机数取模public class WeightedRandomLoadBalancer implements LoadBalancer { Override public Invoker select(ListInvoker servers, String sourceIp) { if (servers null || servers.isEmpty()) { throw new IllegalArgumentException(服务器列表不能为空); } int totalWeight servers.stream().mapToInt(Invoker::getWeight).sum(); if (totalWeight 0) { return new RandomLoadBalancer().select(servers, sourceIp); } int random ThreadLocalRandom.current().nextInt(totalWeight); for (Invoker server : servers) { random - server.getWeight(); if (random 0) { return server; } } return servers.get(0); } }加权随机和加权轮询共享了同一个区间落点模型所以我建议你在设计代码时把这段区间落点的逻辑抽成一个公共方法四个算法(加权轮询、加权随机、平滑加权轮询)都能复用。这不仅仅是代码美观的问题更是工程素养的体现——面试官看你写代码不只是看你写不写得对更看你能不能识别出公共抽象层。2.3 最少连接让忙碌者休息让空闲者上岗前面几种算法都是事前分配——根据固定的权重或序号把请求平均分出去。但真实的线上场景里每个请求的处理难度是不一样的。有的请求只是查个缓存毫秒级返回有的请求要查多个数据库、调多个外部接口可能要几百毫秒甚至更久。按权重分配请求数的策略在这种场景下就失灵了——分配得再均匀服务器收到的工作量也可能很不均匀。最少连接算法Least Connections的思路是事后调度谁手里的活最少就把新请求派给谁。它不再关注你分到了多少个请求而是关注你当前正在处理多少个请求。public class LeastConnectionLoadBalancer implements LoadBalancer { Override public Invoker select(ListInvoker servers, String sourceIp) { if (servers null || servers.isEmpty()) { throw new IllegalArgumentException(服务器列表不能为空); } Invoker leastActiveInvoker null; int leastActiveCount Integer.MAX_VALUE; for (Invoker server : servers) { int currentActive server.getActiveCount().get(); if (currentActive leastActiveCount) { leastActiveCount currentActive; leastActiveInvoker server; } } return leastActiveInvoker; } }这段代码的核心是一个线性扫描找出活跃连接数最小的节点。但如果你想在真实项目里用它光有这段代码是不够的——你必须在请求开始处理时对节点的activeCount做incrementAndGet()在请求处理完毕时做decrementAndGet()这个钩子怎么接我一般会在业务代码的过滤器Filter或拦截器Interceptor里统一处理。Spring Boot 项目可以写一个OncePerRequestFilter在doFilter之前给选中的节点加一在finally块里减一。这样能保证即使请求抛出异常计数也能正确释放不会出现连接数越积越多的内存泄漏式bug。最少连接算法的缺点也很明显它要求负载均衡器能实时掌握每个节点的连接状态这在高并发场景下本身就是一个不小的性能开销。另外如果所有请求的处理时长差异巨大——比如一百个快请求和五个慢请求——最少连接依然可能出现抖动。所以它更适合那些请求处理时间分布不均匀、但对实时性要求较高的中间件场景。像 Dubbo 的负载均衡里就有LeastActiveLoadBalance和这个原理基本一致只是他加上了权重来计算预热时的修正值面试的时候能提一嘴我看过 Dubbo 源码含金量会高很多。2.4 一致性哈希解决分布式缓存的命中率问题前面讲的算法都是与请求内容无关的——同一个用户的请求可能这次被分到 A 节点下次就被分到 B 节点。大部分业务场景下这没什么问题但如果节点后面挂着的是本地缓存或者 Session 会话问题就来了用户在 A 节点登录了下次请求却被路由到 B 节点B 节点没有他的会话数据要么重新登录要么缓存失效重新查库。解决这个问题最经典的方案就是一致性哈希Consistent Hashing。它的核心思想是把整个哈希值空间组织成一个虚拟的环节点通过哈希函数分布在环上请求也通过哈希函数映射到环上然后顺时针找最近的节点这样同一个客户端请求始终会路由到同一个节点。public class ConsistentHashLoadBalancer implements LoadBalancer { private static final int VIRTUAL_NODE_COUNT 160; private final TreeMapLong, Invoker hashRing new TreeMap(); public ConsistentHashLoadBalancer(ListInvoker servers) { for (Invoker server : servers) { addNode(server); } } public void addNode(Invoker invoker) { for (int i 0; i VIRTUAL_NODE_COUNT; i) { long hash hash(invoker.getId() -vn- i); hashRing.put(hash, invoker); } } public void removeNode(Invoker invoker) { for (int i 0; i VIRTUAL_NODE_COUNT; i) { long hash hash(invoker.getId() -vn- i); hashRing.remove(hash); } } Override public Invoker select(ListInvoker servers, String sourceIp) { if (sourceIp null || sourceIp.isEmpty()) { throw new IllegalArgumentException(一致性哈希需要来源IP作为路由依据); } if (hashRing.isEmpty()) { throw new IllegalArgumentException(哈希环为空请先添加节点); } long hash hash(sourceIp); // 找到第一个哈希值大于等于该请求哈希值的节点 Map.EntryLong, Invoker entry hashRing.ceilingEntry(hash); if (entry null) { // 如果超出环的末尾则取环的第一个节点 entry hashRing.firstEntry(); } return entry.getValue(); } private long hash(String key) { MessageDigest md; try { md MessageDigest.getInstance(MD5); } catch (NoSuchAlgorithmException e) { throw new RuntimeException(MD5算法不可用, e); } byte[] digest md.digest(key.getBytes(StandardCharsets.UTF_8)); return ((long) (digest[3] 0xFF) 24) | ((long) (digest[2] 0xFF) 16) | ((long) (digest[1] 0xFF) 8) | (digest[0] 0xFF); } }这里面有几个非常关键的设计决策我得逐个讲清楚。首先是 TreeMap 的选择。它有序且支持ceilingEntry()操作可以快速找到不小于给定 key 的最小 entry这正好就是哈希环上顺时针找下一个节点的定义。如果用 HashMap你得自己遍历所有 key 去比较大小效率低不说代码还会很啰嗦。其次是虚拟节点的作用。如果只有真实的节点映射到哈希环上节点数量少的时候会出现严重的分布不均——假设三个节点哈希后挤在环的同一个半区那落在另外半个区的请求会全部路由到某一个节点负载就偏了。虚拟节点的思路是把每个真实节点复制出多个虚拟副本均匀地分布在环上让每个真实节点负责的环段长度趋于一致。我这边选了 160 个虚拟节点这个数字不是拍脑袋定的——Dubbo 里的一致性哈希默认也是 160。虚拟节点太少分布可能不均太多又会浪费内存。160 是一个经过生产验证的合理值。第三是哈希函数的选择。计算虚拟节点哈希时我没有用hashCode()而是用了 MD5 取 32 位。String.hashCode()的分布性不够好在节点少时容易产生哈希碰撞MD5 算法虽然老化但当哈希函数时它的雪崩效应和均匀性依然很出色。取 32 位是为了能用long来直接放在 TreeMap 里没必要取完整的 128 位。一致性哈希的最大优点是当新增或移除节点时只有环上相邻的那一小段请求会被重新路由其他绝大部分请求的映射关系保持不变。这正好解决了分布式缓存场景下的缓存雪崩问题——如果拿普通的加权轮询扩容一台机器所有请求的缓存映射全变了大量缓存同时失效数据库瞬间被冲垮这是生产事故级别的问题。2.5 平滑加权轮询Nginx 官方的平滑之道终于到了我最喜欢的算法。前面讲加权轮询的时候我留下了一个悬念简单加权轮询会引起连续请求集中在高权重节点那么 Nginx 是怎么解决这个问题的答案在 Nginx 官方文档里写得清清楚楚平滑加权轮询Smooth Weighted Round Robin。这个算法的精妙之处在于它通过动态调整节点的当前权重让请求在宏观上按权重比例分布微观上却尽可能分散不会出现一台机器被连续打完才轮到下一台的尴尬局面。算法只有四步极其简洁每次请求到来时把每个节点的当前权重currentWeight加上它的原始权重weight从所有节点中选出当前权重最大的节点作为本次请求的目标把选中的节点当前的权重减去所有节点的原始权重之和totalWeight重复以上步骤。public class SmoothWeightedRoundRobinLoadBalancer implements LoadBalancer { private final MapString, Integer currentWeightMap new ConcurrentHashMap(); Override public synchronized Invoker select(ListInvoker servers, String sourceIp) { if (servers null || servers.isEmpty()) { throw new IllegalArgumentException(服务器列表不能为空); } int totalWeight servers.stream().mapToInt(Invoker::getWeight).sum(); if (totalWeight 0) { return new RoundRobinLoadBalancer().select(servers, sourceIp); } Invoker selected null; int maxCurrentWeight Integer.MIN_VALUE; for (Invoker server : servers) { int weight server.getWeight(); int currentWeight currentWeightMap.getOrDefault(server.getId(), 0) weight; currentWeightMap.put(server.getId(), currentWeight); if (currentWeight maxCurrentWeight) { maxCurrentWeight currentWeight; selected server; } } // 选中的节点减去总权重 currentWeightMap.put(selected.getId(), currentWeightMap.get(selected.getId()) - totalWeight); return selected; } }来我们用一个具体的例子演算一遍。假设 A 的权重是 5B 的权重是 1两个节点原始权重总数为 6。第 1 个请求A 的当前权重为 055B 的当前权重为 011选 AA 的当前权重变为 5-6-1。此时 A-1B1。第 2 个请求A 的当前权重为 -154B 的当前权重为 112选 AA 的当前权重变为 4-6-2。此时 A-2B2。第 3 个请求A 的当前权重为 -253B 的当前权重为 213当前权重相同。选谁呢按我代码的逻辑currentWeight maxCurrentWeight才会更新所以会选到先遍历到的节点假设是 AA 的当前权重变为 3-6-3。此时 A-3B3。第 4 个请求A 的当前权重为 -352B 的当前权重为 314选 BB 的当前权重变为 4-6-2。此时 A2B-2。第 5 个请求A257B-21-1选 AA 重置为 7-61。第 6 个请求A156B-110选 AA 重置为 6-60。6 个请求的序列是A, A, A, B, A, A。A 被选了 5 次B 被选了 1 次权重比例 5:1 完全正确但是 B 在第 4 个请求就被选中了而不是傻等到前 5 个请求全打完再轮到自己。这就是平滑二字的真正含义——高权重的节点依然承担更多流量但低权重节点不会被饿死它会周期性地插入到请求序列中。我在实现里给select方法加了synchronized这是因为currentWeightMap的读取和更新不是一个原子操作高并发下如果不加锁多个线程同时读到同一个currentWeight值就会选出同一个节点。这又是并发安全的一个细节。你也可以用AtomicInteger来存当前权重配合 CAS 操作来消除锁但代码复杂度会上升。在这个算法的场景下加锁完全够用毕竟它本身要遍历所有节点做权重计算锁的粒度并不会成为性能瓶颈。3. 实测对比与场景选型3.1 七种算法的核心指标横向对比代码写完了接下来我把七种算法放在一张表格里做个横向对比这样你在面试时或者实际选型时可以一目了然算法平均性实现复杂度是否感知节点状态是否保持会话粘滞典型应用场景轮询优极低否否无状态服务、请求处理时长相近的场景加权轮询优低否否服务器配置差异明显的静态集群随机良极低否否请求量足够大的无状态服务加权随机良低否否服务器配置差异较大且请求量大的场景最少连接优中是否请求处理时长波动大的场景一致性哈希良高否是本地缓存、分布式Session、状态ful服务平滑加权轮询优中否否Nginx默认策略、网关层流量分发平均性这个指标我要单独解释一下。轮询的平均性最好因为它是严格的轮流制加权轮询的平均性也好但它好得太机械短时间窗口内请求会集中打在权重最高的节点上加权随机的平均性取决于随机数质量在请求量不够大时短时间窗口内可能出现偏差。最少连接的平均性则是按需分配它能自动纠偏但需要额外的状态维护成本。3.2 真实业务场景中怎么选这些算法到底怎么选我给你几个真实案例做参考。微服务网关层选型。网关是所有请求的入口流量大、要求分配均匀、无状态。这种情况下我首推平滑加权轮询——它能在权重比例正确的前提下做到请求序列平滑交错不会出现某台机器一会儿忙死一会儿闲死的情况。如果服务节点的处理能力强弱差别不大也可以直接用最基础的轮询简单可靠排障方便。分布式缓存场景选型。如果节点后面挂着 Redis 本地缓存或者进程内缓存那就不用考虑了直接用一致性哈希。否则每次扩容缩容都会引发缓存大面积失效数据库会被瞬时流量打崩。我在上家公司就踩过这个坑——缓存集群扩容之前用的是加权轮询扩容那天下班前还好好的第二天一早数据库直接挂了因为 30% 的请求都穿透到数据库了。后来把负载均衡策略改成一致性哈希扩容再也没出过事。RPC 调用场景选型。Dubbo、gRPC 这类 RPC 框架的负载均衡我建议用最少连接或自适应算法。因为 RPC 调用往往是嵌套的、有依赖的有的调用要等下游服务响应很久连接数能更真实地反映节点的繁忙程度。Dubbo 的官方实现里也是把LeastActive作为推荐的负载均衡策略之一这和生产环境验证过的经验是一致的。请求处理时长相对稳定的内部 API 服务选型。轮询就够了。我曾经把一个内部服务的负载均衡策略从轮询换成平滑加权轮询效果提升不明显反而因为引入了权重配置而增加了运维成本。很多场景里最朴素的算法恰恰是最合适的。别为了炫技而选型这是我在这个领域踩了几年坑之后最深的体会。4. 高频面试题与避坑指南4.1 面试官最爱追问的六个问题手写负载均衡算法只是面试的第一关写完之后面试官一定会做一轮连环追问。我整理了六个高频问题把参考回答一并给出。第一个问题Nginx 默认的负载均衡算法是加权轮询还是平滑加权轮询如果你答加权轮询大概率会被追问那你说说它有什么缺点。这个问题的标准答案我建议这样组织Nginx 默认支持两种轮询不带权重的是普通轮询带权重的是平滑加权轮询。值得注意的是Nginx 源码里对带权重的轮询采用了平滑算法而不是教科书里那种简单的按权重区间分段分配。这也是为什么 Nginx 的流控在权重差异比较大的时候依然能保持比较好的平滑性。第二个问题为什么要用虚拟节点不用行不行不用虚拟节点节点数量少时哈希环的分布会严重不均匀假设三台机器的哈希值都落在环的上半区下半区的请求就会全部打到同一台机器上。虚拟节点把每个真实节点复制为多个虚拟副本散布在环上使得每个节点负责的环段长度趋于均匀。面试时你还可以补充一句虚拟节点的数量也有讲究我从 Dubbo 源码里看到的默认值是 160取值太低会不均匀取值太高浪费内存。第三个问题一致性哈希遇到高并发时那个用于选择节点的 TreeMap 会被并发访问吗会。所以在真实项目里要么加锁保护 TreeMap 的读操作要么用ConcurrentSkipListMap替代 TreeMap。我曾经在一个高并发项目里用过 TreeMap 的ceilingEntry方法发现并发读写时偶尔会抛ConcurrentModificationException排查了很久才意识到问题出在节点动态增删和请求路由同时发生时。换成ConcurrentSkipListMap之后问题就消失了它内部用跳表实现支持并发安全的导航方法复杂度也只是 O(log n)。第四个问题最少连接算法里如果所有节点的活跃连接数都是 0会发生什么直接返回第一个节点。这在所有节点都没有流量时会形成一个热点每次请求都打到第一个节点上。所以我一般会建议在活跃连接数相同的情况下做一次加权随机或轮询兜底避免随机固定到第一台的尴尬。第五个问题平滑加权轮询算法的平滑是怎么实现的它的本质是让每个节点的当前权重在一个动态区间内波动选中的节点会被惩罚——减去总权重让它的下一次竞争力变弱没选中的节点会被鼓励——加上自己的原始权重慢慢积累竞争力。这样权重高的节点不会被连续选中太多轮权重低的节点也能周期性地被选中宏观比例正确微观节奏均匀。第六个问题你刚才实现的是客户端负载均衡还是服务端负载均衡两者有什么区别服务端负载均衡比如 Nginx是在请求进入服务端之前由独立的负载均衡器分发客户端负载均衡比如 Ribbon、Dubbo 的负载均衡是在发起 RPC 调用时由调用方自己从服务注册中心拉取服务列表再按某种策略选择一个节点发起调用。我这个代码实现的是客户端负载均衡的思路因为它直接面向服务提供者列表做选择而 Nginx 还需要处理连接管理、健康检查等额外的逻辑。4.2 手写实现中的常见坑与排查思路代码写完并不代表万事大吉。这几个坑是我自己在实际项目中踩过的或者帮别人 review 代码时反复看到的你一定要当心。第一个坑Math.abs(index.getAndIncrement()) % servers.size()在极端情况下会出现负下标。Math.abs(Integer.MIN_VALUE)的结果还是负数这是 Java 语言层面的隐藏坑。解决办法是用Math.floorMod()或者先与Integer.MAX_VALUE做位与操作再取模。虽然要触发Integer.MIN_VALUE需要几十亿次请求但作为有经验的开发者你应该主动写出更健壮的取模表达式。第二个坑加权轮询的节点列表在运行时动态变化时计数器取模的totalWeight必须实时计算。如果你把它缓存到一个静态变量里新增节点后缓存没更新新节点永远分不到流量。我的建议是每次select时都重新计算totalWeight或者在你更新节点列表时同步刷新缓存并且保证这两个操作之间没有并发窗口。第三个坑最少连接算法的计数器必须在 finally 块里递减。如果请求发生异常导致activeCount没有减回去这个节点的活跃连接数就会永远偏大导致它再也分不到新请求——实际上形成了一种引用泄漏。这个 bug 在测试环境不容易暴露因为流量小但一旦上生产遇到异常流量一冲某几个节点就假死了。排查方法是监控每个节点的activeCount是否长期居高不下。第四个坑一致性哈希在节点增删时需要重建虚拟节点映射。如果你直接用构造函数传入初始节点列表后续节点扩容时忘记调用addNode那么新节点永远不会出现在哈希环上。我建议把节点管理的逻辑单独封装成一个NodeManager提供register和unregister方法内部自动维护哈希环的一致性。调用方只需要关心节点注册和反注册不需要关心哈希环的细节。第五个坑不正确地使用ConcurrentHashMap存储当前权重。ConcurrentHashMap的每个操作是线程安全的但是先读后写再读这个复合操作不是原子的。平滑加权轮询的整个流程里多个线程同时执行读取 currentWeight 并加上 weight会导致计算结果互相覆盖。我见过不少人以为用了ConcurrentHashMap就万事大吉了结果高并发下一测就发现权重计算错误。要么在select方法上加锁要么用compute方法配合原子操作来完成读改写。第六个坑负载均衡算法本身没有对节点做健康检查。如果一台机器已经宕机了但它还在服务列表里轮询算法照样会把它选出来导致请求失败。真实项目里一定要配合健康检查机制——定期探活、把不健康的节点从列表里摘除。我在代码示例里没有加这个逻辑是为了让算法部分更聚焦但你在落地时一定要补上这个环节。收尾把代码变成你自己的七种算法到这里就全部写完了。如果你只是看着代码觉得嗯挺简单的然后就把文章关掉那这些代码并不属于你。我的建议是你打开 IDE新建一个LoadBalancer接口然后把七种算法逐个敲一遍敲的过程中尝试回答下面几个问题轮询算法的并发安全靠什么保证平滑加权轮询为什么要用 synchronized如果你来设计你会怎么优化一致性哈希的虚拟节点数量敲完之后你还可以做一件更有意思的事写一个简单的测试类模拟 100 万个请求分别用七种算法做分发统计每台节点收到的请求数量和分布曲线。然后你可能会发现理论分析和真实的随机分布之间确实存在差距——这个差距就是你对算法的理解从看得懂变成讲得清的关键一步。最后分享一个我自己的小习惯每次新接手一个分布式系统的项目我做的第一件事就是看它的负载均衡配置和实现。负载均衡是系统的流量入口从它入手你不仅能理解系统的容量设计思路还能快速发现潜在的性能瓶颈。把这七种算法吃透你看任何一款中间件的负载均衡源码都会轻松很多。