从零手写七种负载均衡算法：Java 实现详解

很多人背负载均衡算法都能背出七八个名字，轮询、随机、哈希、最少连接……但真到了面试官让你手写一个，或者让你说清楚"加权轮询和普通轮询在生产环境到底差在哪"的时候，往往会卡壳。这篇文章我不打算把每种算法停在概念层面，而是直接用 Java 把它们一个不落地写一遍，代码能跑、逻辑能讲、边界能聊。适合正在准备面试的同学，也适合后端开发想自己搭一个简单负载均衡器底层逻辑的同行。

先说清楚范围，七种算法指的是：基础轮询、加权轮询、平滑加权轮询、随机、加权随机、源地址哈希、一致性哈希，外加最少连接。为什么把这个组合作为"手写清单"？因为这几种基本覆盖了负载均衡算法里"静态策略"和"动态策略"两大流派，也覆盖了面试里 90% 的追问方向。

1. 面试追问背后的算法全景：从八股文到工程判断

1.1 先搞清楚这七种算法解决的是哪两类问题

不夸张地说，很多人在这一步就已经糊涂了。负载均衡算法其实分成两大类：一类是不看服务器当前状态的静态算法，一类是要读取实时状态的动态算法。

静态算法的逻辑简单粗暴——轮询就是轮流来，随机就是看概率，哈希就是按某个 key 映射。它不关心下游机器是不是快挂了、连接数是不是已经爆了。动态算法正好相反，最少连接会去数每台服务器手里有多少个活跃请求，谁少就发给谁。

这两种取向没有绝对优劣。静态算法胜在实现简单、开销为零、行为可预测，适合后端实例性能均匀、请求处理时间稳定的场景。动态算法能感知真实压力，但需要引入计数器、状态同步，本身也有额外成本。面试官问"你选哪种"，本质上是考察你有没有这个判断维度。

1.2 一个规格统一的接口，让七种算法站在同一起跑线

在写任何算法之前，我建议先定一个公共接口。这样代码结构会干净很多，也方便后续做策略替换或者测试。我用一个最简单的模型：服务器用 Server 类表示，里面只放必要的属性；负载均衡器用一个 LoadBalancer 接口表示，所有算法都实现 select 方法。

java复制public class Server {
    private String ip;
    private int port;
    private int weight;        // 权重，默认1
    private int activeConnections; // 最少连接算法使用

    public Server(String ip, int port, int weight) {
        this.ip = ip;
        this.port = port;
        this.weight = weight;
        this.activeConnections = 0;
    }
    
    // getter / setter 省略，后续代码均省略无关注释
}

接口只暴露一个核心方法 Server select(List<Server> servers, Object requestKey)。requestKey 是给哈希类算法用的，可以是客户端 IP、请求 ID，也可以是任意字符串。轮询和随机这类算法用不到这个参数，但放在接口里统一处理，调用方不需要关心内部实现。

java复制public interface LoadBalancer {
    Server select(List<Server> servers, Object requestKey);
}

这一步看起来很基础，但它把设计模式里的策略模式落到了实处。后面新增算法只要实现接口，不用改动调用方的代码。面试中如果能把这段设计讲出来，比单纯背算法名要加分得多。

2. 轮询算法：最朴素策略的效率边界与隐蔽缺陷

2.1 基础轮询与原子计数器的正确姿势

轮询是所有算法里最直观的：请求按顺序挨个分发到每台服务器上，1、2、3、4、5，循环往复。它的思想就是"绝对公平"，不考虑机器配置差异，也不考虑当前负载。

第一版实现很容易写，但高并发下就会踩坑。很多人习惯用一个 int index 做下标累加，每次请求进来 index++。这在单线程下没问题，一旦多线程并发访问，index++ 本身就不是原子操作，会出现重复分发或者漏分发的错误。

更隐蔽的问题是，就算你给 index 加了 volatile 关键字，复合操作"读-加-写"在并发下仍然不是安全的。正确做法是用 AtomicInteger 的 getAndIncrement()，它保证整个自增过程是原子的：

java复制public class RoundRobinLoadBalancer implements LoadBalancer {
    private final AtomicInteger index = new AtomicInteger(0);

    @Override
    public Server select(List<Server> servers, Object requestKey) {
        if (servers == null || servers.isEmpty()) {
            throw new IllegalArgumentException("服务器列表不能为空");
        }
        int current = Math.abs(index.getAndIncrement());
        return servers.get(current % servers.size());
    }
}

这里还有一个值得注意的细节：Math.abs 是为了防止 Integer.MIN_VALUE 取模出现负数。虽然生产环境几乎不可能请求次数达到 21 亿次，但面试官问起来你如果能主动提到这个边界，会很不一样。

2.2 加权轮询的不均匀陷阱与平滑加权轮询原理

基础轮询假设所有服务器能力一样，但现实是机器配的 CPU、内存、带宽都不一样。加权轮询就是给每台服务器按权重分配比例，权重高的多分一些请求。

一个非常容易出错的实现是"权重百分比"法：先算出总权重，再按权重切分一个区间，请求落在哪个区间就发给哪台服务器。这种实现能保证长期比例正确，但在短时间窗口内会产生"突刺"——A 服务器连续收到 5 个请求，然后 B 服务器闲着，然后 C 服务器又连收 5 个。对于需要平滑流量的场景（比如下游服务有缓存预热、连接池建立的开销），这种突刺非常致命。

Nginx 里使用的平滑加权轮询用的是一个很巧妙的数学技巧：每台服务器有两个权重，一个是固定不变的 weight（配置值），一个是动态变化的 currentWeight。每次请求进来，先把所有 currentWeight 加上各自的 weight，然后选出 currentWeight 最大的那台服务器，再把它的 currentWeight 减去总权重。

java复制public class SmoothWeightedRoundRobinLoadBalancer implements LoadBalancer {
    @Override
    public Server select(List<Server> servers, Object requestKey) {
        if (servers == null || servers.isEmpty()) {
            throw new IllegalArgumentException("服务器列表不能为空");
        }
        
        int totalWeight = servers.stream().mapToInt(Server::getWeight).sum();
        Server selected = null;
        int maxCurrentWeight = Integer.MIN_VALUE;
        
        for (Server server : servers) {
            server.setCurrentWeight(server.getCurrentWeight() + server.getWeight());
            if (server.getCurrentWeight() > maxCurrentWeight) {
                maxCurrentWeight = server.getCurrentWeight();
                selected = server;
            }
        }
        
        if (selected != null) {
            selected.setCurrentWeight(selected.getCurrentWeight() - totalWeight);
        }
        return selected;
    }
}

这个算法的妙处在于，它把"权重比例"转换成了"时间片里的平滑分布"。举个例子，三台服务器权重分别是 5、1、1，平滑加权轮询会输出 A A B A A C A A 这样的序列，而不是 AAAAA B C。流量被摊开了，下游压力也匀了。

我自己手写这个算法的时候，第一次跑出来的结果顺序和预期不符，排查后发现是 currentWeight 的初始值没有归零。如果初始化直接给成 weight，整个公式就乱了。这一点在用这个算法时一定要小心。

3. 随机与加权随机：概率视角下的流量分配

3.1 ThreadLocalRandom 在高并发下的必要性

随机算法的思路最简单：从服务器列表里随机挑一台。但"随机"这两个字在 Java 里有讲究。

早期代码里常见的写法是 Random random = new Random(); int i = random.nextInt(servers.size());。如果你把 Random 对象创建成局部变量，每次请求都 new 一个，那么在高并发下多个 Random 对象使用相同的种子，反而可能产生重复的随机序列，导致流量分配不均。而把 Random 作为全局共享变量，又会有并发竞争的问题。虽然 Random 内部用了 CAS 保证线程安全，但竞争激烈时性能会下降。

JDK 7 引入的 ThreadLocalRandom 专门解决这个问题。它让每个线程维护自己的随机数种子，互不干扰，既没有锁竞争，也不会因为 new 太多实例导致序列重复。所以在手写随机负载均衡时，直接用 ThreadLocalRandom.current() 是标准答案。

java复制public class RandomLoadBalancer implements LoadBalancer {
    @Override
    public Server select(List<Server> servers, Object requestKey) {
        if (servers == null || servers.isEmpty()) {
            throw new IllegalArgumentException("服务器列表不能为空");
        }
        int index = ThreadLocalRandom.current().nextInt(servers.size());
        return servers.get(index);
    }
}

3.2 加权随机的两种等价实现与边界处理

加权随机有两种实现路径，一种是区间法，一种是累加法。

区间法先把总权重算出来，然后在 [0, totalWeight) 区间里随机选一个数，再遍历服务器，每台服务器维护一个权重区间，落在哪个区间就选哪台：

java复制public class WeightedRandomLoadBalancer implements LoadBalancer {
    @Override
    public Server select(List<Server> servers, Object requestKey) {
        if (servers == null || servers.isEmpty()) {
            throw new IllegalArgumentException("服务器列表不能为空");
        }
        
        int totalWeight = servers.stream().mapToInt(Server::getWeight).sum();
        int random = ThreadLocalRandom.current().nextInt(totalWeight);
        
        for (Server server : servers) {
            random -= server.getWeight();
            if (random < 0) {
                return server;
            }
        }
        // 理论上不会走到这里，兜底返回最后一台
        return servers.get(servers.size() - 1);
    }
}

你可能会好奇，为什么不是先算随机数落在哪个百分比范围，再线性查找？其实这两种方式本质相同，但上面的写法不需要额外存储区间边界，每台服务器只要知道自己的权重就够了，代码更简洁。

边界处理上有两个容易被忽略的点。第一，某台服务器的权重写成 0，它应该永远不会被选中；上面的实现天然满足这一点，因为 random -= 0 不会让 random 变成负数。第二，如果列表里所有服务器权重都是 0，totalWeight 就是 0，nextInt(0) 会抛出 IllegalArgumentException。所以在真实项目里，要在初始化或者更新列表时对权重做校验，不允许全 0 配置。

随机算法的好处是简单、无状态、适合请求处理时间比较均匀的场景。缺点是它不保证短期内的公平，极端情况下连续 10 个请求都落到同一台机器上也是可能的。所以如果下游对流量抖动敏感，随机不如轮询可控。

4. 源地址哈希：会话保持的简单解法与扩容痛点

4.1 哈希取模实现以及一致性要求

源地址哈希的核心诉求是会话保持：同一个客户端 IP 的多次请求，尽量都打到同一台后端服务器上。这样服务端保存的 session、本地缓存都能复用，也不需要引入外部的分布式会话存储。

实现逻辑非常直接：拿客户端 IP（或者其他业务 key）计算哈希，再对服务器数量取模，得到服务器下标：

java复制public class IpHashLoadBalancer implements LoadBalancer {
    @Override
    public Server select(List<Server> servers, Object requestKey) {
        if (servers == null || servers.isEmpty()) {
            throw new IllegalArgumentException("服务器列表不能为空");
        }
        if (requestKey == null) {
            // 没有 key 时退化为轮询，避免 NPE
            return servers.get(Math.abs(ThreadLocalRandom.current().nextInt()) % servers.size());
        }
        int hashCode = requestKey.hashCode();
        return servers.get(Math.floorMod(hashCode, servers.size()));
    }
}

这里刻意用了 Math.floorMod 而不是 %。% 在 Java 里对负数取模结果是负数，比如 -5 % 3 == -2，拿负的下标去 get 会抛 ArrayIndexOutOfBoundsException。虽然很多 key 的 hashCode 是正的，但 String.hashCode() 完全可能算出负数。Math.floorMod(-5, 3) 的结果是 1，语义上与"环绕取模"一致，这才是我们想要的。

这个算法的优点是简单、无状态、天然会话保持。缺点是服务器列表一旦变化，比如某台机器宕机被摘除，那么几乎所有 key 的取模结果都会改变，大量请求会被重新路由到别的服务器，导致缓存穿透、会话失效。这就是经典的"哈希雪崩"问题。

4.2 为什么扩容时哈希会雪崩

用个具体例子你就明白了。假设原来有 6 台服务器，某个 key 的哈希值是 18，18 % 6 = 0，分配到第 1 台。现在扩容到 7 台，18 % 7 = 4，这个 key 被分到第 5 台。不只是这一个 key，几乎是所有 key 都发生了迁移。

假设服务器上有本地缓存，缓存命中率会瞬间骤降，所有请求同时回源到数据库，数据库压力陡增，极端情况直接把服务打挂。这个坑在分布式系统里非常经典。

要做到"扩容时只迁移少量数据"，就需要一致性哈希登场了。这也是为什么面试时讲完源地址哈希，面试官基本都会顺势问一句："那服务器扩容了怎么办？"你如果能主动引出下一个算法，节奏感会很好。

5. 一致性哈希：最小迁移量的分布式调度

5.1 哈希环与虚拟节点的数据结构设计

一致性哈希的核心思路是把服务器和请求 key 都映射到一个固定范围的哈希环上（通常是 0 ~ 2^32 - 1）。每个服务器根据它的 IP 或名称计算哈希值，落在环上的某个位置。请求 key 也计算哈希值，然后沿着环顺时针查找，找到的第一个服务器节点就是目标服务器。

这样设计的好处是：当一台服务器加入或者退出时，只会影响它顺时针方向上的下一个邻居区间，其他区间的 key 完全不受影响。这正好解决了取模哈希"全员迁移"的问题。

但朴素的一致性哈希有一个很实际的毛病：如果服务器数量少，节点在环上分布不均匀，会导致某些服务器承担的流量远大于其他服务器。解决办法是引入虚拟节点。每个物理服务器虚拟出 N 个节点（比如 100 个），每个虚拟节点用 ip + "#" + 序号 计算哈希值放到环上。这样物理节点在环上的"势力范围"就变得均匀了。

TreeMap 是手写一致性哈希的绝佳数据结构，它天然支持"按 key 排序"和"找第一个大于等于给定 key 的元素"（ceilingEntry）。如果 ceilingEntry 返回 null，说明环上已经绕到尽头了，就取第一个元素，模拟首尾相接的环。

java复制public class ConsistentHashLoadBalancer implements LoadBalancer {
    private final TreeMap<Integer, Server> hashRing = new TreeMap<>();
    private final int virtualNodeCount;
    
    public ConsistentHashLoadBalancer(int virtualNodeCount) {
        this.virtualNodeCount = virtualNodeCount;
    }
    
    public void addServer(Server server, int serverHash) {
        for (int i = 0; i < virtualNodeCount; i++) {
            int hash = (serverHash + i * 31) & 0x7fffffff;
            hashRing.put(hash, server);
        }
    }
    
    public void removeServer(Server server, int serverHash) {
        for (int i = 0; i < virtualNodeCount; i++) {
            int hash = (serverHash + i * 31) & 0x7fffffff;
            hashRing.remove(hash);
        }
    }
    
    @Override
    public Server select(List<Server> servers, Object requestKey) {
        if (servers == null || servers.isEmpty()) {
            throw new IllegalArgumentException("服务器列表不能为空");
        }
        int hash = requestKey.hashCode() & 0x7fffffff;
        Map.Entry<Integer, Server> entry = hashRing.ceilingEntry(hash);
        if (entry == null) {
            entry = hashRing.firstEntry();
        }
        return entry.getValue();
    }
}

注意这里我用 serverHash + i * 31 来生成虚拟节点哈希值，而不是直接用 server.toString() + "#" + i 再算 hashCode。两种方式都可以，但直接做整数运算速度更快。& 0x7fffffff 是把哈希值强制变成非负整数，等价于取绝对值，但避免了 Math.abs(Integer.MIN_VALUE) 还是负数的极端情况。

5.2 顺时针查找的实现细节与数据倾斜问题

ceilingEntry(hash) 找的是哈希环上"大于等于 hash 的最小 key"，也就是顺时针方向第一个节点。如果找不到，说明 hash 已经超过了环上所有节点的位置，按环的逻辑应该绕回开头，所以回退到 firstEntry()。

TreeMap 的 ceilingEntry 和 firstEntry 的时间复杂度都是 O(log n)，n 是环上的节点总数。因为虚拟节点数量是固定倍数，所以复杂度可以接受。如果服务器的增删非常频繁，还可以在每次增删时用一个 ConcurrentSkipListMap 来保证并发安全，TreeMap 本身不是线程安全的。

还有一个在实际使用中很容易踩的坑：不要在 select 方法里去动态遍历 servers 列表重建哈希环。有些实现懒省事，每次请求都重新 addServer，这不仅浪费性能，还可能在并发遍历 TreeMap 的时抛出 ConcurrentModificationException。正确的姿势是：哈希环作为成员变量，在服务器列表变化时才重建，请求只做读操作。

数据倾斜问题要分两层说。加了虚拟节点之后，分布已经比较均匀了，但如果服务器性能差异极大——比如一台 8 核，一台 64 核——光靠一致性哈希做不到"按能力分配"。这时候要么加权重维度，让大机器拥有更多虚拟节点，要么在一致性哈希之上再接一层动态策略。这个思路面试时可以提，能体现出你真的想过生产问题。

6. 最少连接算法：动态感知节点真实负载

6.1 连接数计数器与并发安全的难点

前面几种算法都是"无状态"的，选哪台服务器只跟输入参数有关。最少连接算法完全不同，它依赖于每台服务器当前的活跃连接数，每次请求都选择连接数最少的那台服务器。

这个逻辑的工程实现难点全在并发安全上。第一个问题是计数器的递增和递减必须准确。连接建立时 increment，连接释放时 decrement，这两个操作在高并发下如果出现丢更新，计数就会失真，最终导致流量分配失衡。我在写第一版的时候用了 AtomicInteger 做计数，这个原子类保证单个操作的线程安全没问题，但"判断最小 + 选取"这两个步骤之间仍然存在竞态条件。

更关键的问题在于，计数出的最小值只是一个瞬时快照。假设 A 服务器当前连接数是 10，B 是 12，请求选完 A 之后，A 的连接数变成 11。如果下一个请求依然读到旧值，可能又选 A，造成短时间内的扎堆。要彻底解决竞态，需要加锁，但这会显著降低负载均衡器自身的吞吐。实际工程中通常使用原子操作配合乐观重试，或者干脆接受瞬时不精确，因为负载均衡器本身就是"软状态"的。

一个简单的线程安全实现可以这样设计：

java复制public class LeastConnectionLoadBalancer implements LoadBalancer {
    @Override
    public Server select(List<Server> servers, Object requestKey) {
        if (servers == null || servers.isEmpty()) {
            throw new IllegalArgumentException("服务器列表不能为空");
        }
        Server selected = null;
        int minConnections = Integer.MAX_VALUE;
        for (Server server : servers) {
            int connections = server.getActiveConnections();
            if (connections < minConnections) {
                minConnections = connections;
                selected = server;
            }
        }
        if (selected != null) {
            selected.incrementConnections();
        }
        return selected;
    }
}

这里 getActiveConnections 返回的是 volatile int 的读操作，incrementConnections 用 synchronized 或者 AtomicInteger 保证原子性。这种实现能应付大多数场景，但读取和递增之间的间隙仍然可能选到同一台。要严格避免，就在选择过程加锁，不过我不推荐这么做，因为负载均衡器通常是全局入口，加锁的成本会被放大。

6.2 最小堆 vs 全量扫描的取舍

如果服务器数量很大，每来一个请求都全量扫描一遍 servers，时间复杂度是 O(n)，n 是服务器数量。这在几十台的规模下完全没问题，但到了成百上千台的微服务集群里，就会成为性能瓶颈。

优化思路是维护一个"按连接数升序排列的最小堆"，堆顶就是连接数最少的服务器。每次请求直接取堆顶，再把它的连接数加一后重新调整堆位置，复杂度降到 O(log n)。听起来很完美，但维护堆的代价是：每台服务器的连接数变化时都要触发重排，而连接数是高频变化的——每次请求进来和结束都要变一次。在高 QPS 下，这个代价未必比 O(n) 扫描便宜。

我的建议是分场景：如果单个负载均衡器要管理上千节点，再考虑堆或者分片；如果只有几十台，全量扫描反而更简单、更可靠，还避免了堆调整引入的复杂并发问题。性能优化永远要结合真实规模来谈，不能为了复杂度而复杂度。

最少连接算法也有它的问题：连接数并不等于真实负载。有些请求虽然连接数少，但每个请求都是重计算，CPU 打满了；有些请求连接数多但基本都是 IO 等待。所以很多自研的负载均衡器会在这个基础上衍生出加权最少连接算法，用权重修正连接数的偏差，不过那又是一篇文章的内容了。

7. 累计经验：七种算法的共性抽象与面试表达

7.1 公共抽象与策略模式的结合

七种算法都写完之后，回到最初的接口定义，你会发现策略模式的价值彻底体现出来了。调用方只需要持有 LoadBalancer 引用，具体用哪种算法由配置决定，代码层面完全不用动。

java复制public class LoadBalancerContext {
    private final LoadBalancer loadBalancer;
    
    public LoadBalancerContext(LoadBalancer loadBalancer) {
        this.loadBalancer = loadBalancer;
    }
    
    public Server handleRequest(List<Server> servers, Object requestKey) {
        Server server = loadBalancer.select(servers, requestKey);
        // 这里可以统一做统计、日志、异常兜底等横切逻辑
        return server;
    }
}

在实际项目中，还可以用工厂模式根据配置字符串创建对应的算法实例，或者用 Spring 的注入把实现类管理起来。这些都属于"锦上添花"，面试时点到为止即可，重点是让面试官看到你有"面向接口编程"的肌肉记忆。

另外要提醒一点，手写这些算法的过程中，单元测试非常有必要。我建议用 JUnit 写一个简单的循环调用，分别统计三种算法的命中次数，验证加权比例是否符合预期。比如加权轮询跑 10000 次，权重 5:1:1 的三台服务器，命中次数应该大致是 7140:1430:1430。这类测试能帮你快速发现 currentWeight 初始化的错误、取模负数的错误等低级 bug。

7.2 从算法到面试沟通

如果面试正好问到负载均衡算法，我个人的表达顺序是：先按"静态 vs 动态"给算法分个类，让对方知道你脑子里有结构，不是零散背口诀；然后挑两三个重点算法（我一般选平滑加权轮询、一致性哈希、最少连接）讲实现思路；讲的时候尽量带上手写代码的细节，比如 AtomicInteger 解决并发自增、TreeMap.ceilingEntry 实现哈希环、Math.floorMod 避免下标越界。这些细节是"真的写过"和"背过概念"的分水岭。

还有一个小技巧：面试官让你比较轮询和随机时，别只说"轮询公平、随机不均"。更好的答案是用场景切入——如果下游是无状态服务且性能均匀，轮询更可控；如果请求天然有热点、服务器数量多，随机在某些情况下反而能避免多个请求同时打向同一台机器带来的局部热点。关键在于，算法没有绝对好坏，只有合不合适。

最后再用一个真实经验收尾。我在自己写这套代码的时候，一开始图省事，所有算法的服务器列表直接放到内存里，结果测试并发场景时发现 ArrayList 被并发修改，抛出 ConcurrentModificationException。后来把服务器列表统一设计成不可变快照，每次变更时整体替换引用，算法内部只读列表内容，问题就彻底消失了。这个模式在很多地方都通用——读多写少的配置数据，用"复制替换"比加锁更优雅，也更容易保证一致性。你在手写或者落地这些算法的时候，建议也按这个思路来。