1. 项目背景详细介绍

在分布式系统中，负载均衡器负责将客户端请求分发到后端服务器集群，以提升系统吞吐、降低单点压力并提高可用性。常见策略包括轮询、最少连接、随机等；而当后端服务器性能不一致、或者需要按能力比例分配流量时，简单策略难以满足需求。

加权随机法（Weighted Random）是在随机算法基础上，结合每台服务器的权重（如 CPU 频率、内存大小、网络带宽或在线程度等）进行随机抽样，使得权重更高的服务器被选中的概率更大，却又保持随机涌入的“抖动”特性，避免热点积累。它既能兼顾按比例分配，又无需维护严格的轮询指针，适合多后端资源异构、流量分布要求灵活的场景。

本项目将以 Java 为语言，完整实现加权随机负载均衡器，涵盖从需求分析、技术选型、核心算法设计，到代码实现、性能测试和后续扩展的全过程，帮助读者掌握加权随机策略的原理与工程实践。

---

2. 项目需求详细介绍

2.1 功能需求

1. 后端服务器管理

   • 添加服务器及其权重：addServer(String backend, int weight)

   • 删除服务器：removeServer(String backend)

   • 获取列表快照：listServers()，返回含 backend 与 weight 的结构

2. 加权随机调度

   • 方法签名：String selectWeightedServer()

   • 按服务器权重比例随机选择后端

3. 可插拔随机源

   • 接口 RandomGenerator，默认支持 java.util.Random 和 SecureRandom

   • 支持用户传入自定义实现

4. 会话亲和（可选）

   • 基于客户端标识（如 IP、SessionID）做简单缓存，短期内同一客户映射同一后端

5. 命令行与 API 演示

   • Main 类演示添加多台服务器后进行多次加权随机调度

   • 提供 Java API，方便在应用中调用

6. 测试用例

   • 使用 JUnit5 编写：

     • 大样本测试权重比例近似正确

     • 并发安全测试

     • 异常场景测试（空列表、负权重等）

2.2 非功能需求

1. 性能要求

   • selectWeightedServer() 在百台服务器场景下调用延迟应低于微秒级

   • 添加/删除服务器操作应在毫秒级内完成

2. 可维护性

   • 模块清晰：服务器管理、随机生成、调度算法分离

   • 完整 JavaDoc 注释

3. 可测试性

   • 单元测试覆盖率 ≥ 90%

   • 性能基准测试（可选 JMH）

4. 线程安全

   • 并发读写安全，选路性能不被写操作阻塞

5. 可扩展性

   • 后续可支持动态权重调整、按请求类型分流、健康检查剔除

6. 文档与示例

   • README.md：项目说明、使用示例、性能数据

   • UML 类图、流程图

---

3. 相关技术详细介绍

3.1 Java 并发与集合

• 写时复制快照（Copy-On-Write）或原子引用

  • AtomicReference<List<ServerEntry>> 管理服务器快照，写时复制保证并发安全

• 锁机制

  • 对写操作可使用 ReentrantReadWriteLock，读操作无锁

3.2 随机数生成

• java.util.Random

  • 线性同余算法，速度快，均匀性足够

• java.security.SecureRandom

  • 安全随机，适合对随机性有更高要求场景

• 自定义接口

  • RandomGenerator 统一暴露 nextInt(int bound)

3.3 加权随机算法

• 前缀和 + 二分查找

  1. 维护前缀权重数组 prefix[i] = w[0] + … + w[i]

  2. total = prefix[last]

  3. 生成 [1, total] 范围内随机数 r

  4. 二分查找第一个 prefix[idx] ≥ r，返回 servers[idx]

• 水塘抽样（可选）

  • 在线算法，适合权重变动频繁且列表过大时

3.4 单元测试与性能基准

• JUnit5

  • 功能测试：比对大样本抽样结果与理论分布

  • 并发测试：多线程同时选路

• JMH（可选）

  • 基准测试不同规模服务器列表和随机源下的吞吐与延迟

3.5 构建与质量控制

• Maven

  • 管理依赖、插件、打包

• Checkstyle / SpotBugs

  • 静态检查、风格一致性

---

4. 实现思路详细介绍

4.1 模块划分

com.example.weightedbalancer
│
├─ RandomGenerator            // 随机数生成器接口
│   ├─ DefaultRandomGenerator // java.util.Random
│   └─ SecureRandomGenerator  // SecureRandom
│
├─ BackendManager             // 管理后端服务器和权重
│   └─ ServerEntry
│
├─ WeightedRandomBalancer     // 加权随机调度实现
│   ├─ 构建 prefixSum 缓存
│   └─ selectWeightedServer()
│
└─ Main                       // 命令行演示

4.2 核心流程

1. 构建快照

   • 从 BackendManager 获取 List<ServerEntry> 快照，包含 (backend, weight)

2. 计算前缀和

   • 遍历列表计算 prefixSum 数组：prefixSum[i] = prefixSum[i-1] + weight[i]

3. 生成随机数

   • 调用 rnd.nextInt(totalWeight) + 1，得到 r

4. 二分查找

   • 在 prefixSum 上二分查找第一个 >= r 的索引 idx

5. 返回结果

   • return servers.get(idx).backend

4.3 并发处理

• 读多写少

  • selectWeightedServer 只读快照和本地 prefixSum，无需加锁

  • addServer / removeServer 写时复制列表并重建缓存

4.4 性能优化

• 缓存前缀和

  • 每次服务器列表变更时重建 prefixSum，选路时只做二分查找

• 随机源复用

  • 单例 RandomGenerator，避免每次创建对象

// ======================= 文件：RandomGenerator.java =======================
package com.example.weightedbalancer;

/**
 * 随机数生成器接口
 */
public interface RandomGenerator {
    /**
     * 返回 [0, bound) 之间的随机整数
     */
    int nextInt(int bound);
}

// ======================= 文件：DefaultRandomGenerator.java =======================
package com.example.weightedbalancer;

import java.util.Random;

/**
 * 基于 java.util.Random 的默认随机数生成器
 */
public class DefaultRandomGenerator implements RandomGenerator {
    private final Random rnd = new Random();

    @Override
    public int nextInt(int bound) {
        return rnd.nextInt(bound);
    }
}

// ======================= 文件：SecureRandomGenerator.java =======================
package com.example.weightedbalancer;

import java.security.SecureRandom;

/**
 * 基于 SecureRandom 的强随机数生成器
 */
public class SecureRandomGenerator implements RandomGenerator {
    private final SecureRandom rnd = new SecureRandom();

    @Override
    public int nextInt(int bound) {
        return rnd.nextInt(bound);
    }
}

// ======================= 文件：BackendManager.java =======================
package com.example.weightedbalancer;

import java.util.List;
import java.util.concurrent.atomic.AtomicReference;
import java.util.ArrayList;

/**
 * 后端服务器管理：维护线程安全的服务器列表快照
 */
public class BackendManager {
    private final AtomicReference<List<ServerEntry>> snapshot =
        new AtomicReference<>(new ArrayList<>());

    public void addServer(String backend, int weight) {
        if (weight <= 0) {
            throw new IllegalArgumentException("权重必须为正整数");
        }
        updateList(list -> list.add(new ServerEntry(backend, weight)));
    }

    public void removeServer(String backend) {
        updateList(list -> list.removeIf(e -> e.backend.equals(backend)));
    }

    public List<ServerEntry> listServers() {
        return snapshot.get();
    }

    private void updateList(java.util.function.Consumer<List<ServerEntry>> mutator) {
        List<ServerEntry> old = snapshot.get();
        List<ServerEntry> copy = new ArrayList<>(old);
        mutator.accept(copy);
        snapshot.set(copy);
    }

    /** 内部用来关联权重 */
    public static class ServerEntry {
        public final String backend;
        public final int weight;
        public ServerEntry(String backend, int weight) {
            this.backend = backend;
            this.weight = weight;
        }
    }
}

// ======================= 文件：WeightedRandomBalancer.java =======================
package com.example.weightedbalancer;

import java.util.List;

/**
 * 加权随机负载均衡器
 */
public class WeightedRandomBalancer {
    private final BackendManager manager;
    private final RandomGenerator rnd;
    private volatile int[] prefixSum;      // 前缀和缓存
    private volatile String[] backends;    // 对应后端列表

    public WeightedRandomBalancer(BackendManager manager, RandomGenerator rnd) {
        this.manager = manager;
        this.rnd = rnd;
        rebuild(); // 初始构建
    }

    /**
     * 添加服务器后重建前缀和和后端快照
     */
    public void addServer(String backend, int weight) {
        manager.addServer(backend, weight);
        rebuild();
    }

    /**
     * 删除服务器后重建前缀和和后端快照
     */
    public void removeServer(String backend) {
        manager.removeServer(backend);
        rebuild();
    }

    /**
     * 根据权重随机选择后端
     */
    public String selectWeightedServer() {
        int[] ps = prefixSum;
        String[] bs = backends;
        if (ps.length == 0) throw new IllegalStateException("无可用后端");
        int total = ps[ps.length - 1];
        int r = rnd.nextInt(total) + 1;  // [1, total]
        int idx = java.util.Arrays.binarySearch(ps, r);
        if (idx < 0) {
            idx = -idx - 1;
        }
        return bs[idx];
    }

    /**
     * 重建前缀和数组和后端快照
     */
    private void rebuild() {
        List<BackendManager.ServerEntry> list = manager.listServers();
        int n = list.size();
        int[] ps = new int[n];
        String[] bs = new String[n];
        int sum = 0;
        for (int i = 0; i < n; i++) {
            BackendManager.ServerEntry e = list.get(i);
            sum += e.weight;
            ps[i] = sum;
            bs[i] = e.backend;
        }
        prefixSum = ps;
        backends = bs;
    }
}

// ======================= 文件：Main.java =======================
package com.example.weightedbalancer;

/**
 * 命令行演示
 */
public class Main {
    public static void main(String[] args) {
        BackendManager mgr = new BackendManager();
        mgr.addServer("10.0.0.1:80", 5);
        mgr.addServer("10.0.0.2:80", 1);
        mgr.addServer("10.0.0.3:80", 1);

        WeightedRandomBalancer bal = new WeightedRandomBalancer(mgr, new DefaultRandomGenerator());

        System.out.println("加权随机分配：");
        for (int i = 0; i < 10; i++) {
            System.out.println(bal.selectWeightedServer());
        }
    }
}

// ======================= 文件：WeightedRandomBalancerTest.java =======================
package com.example.weightedbalancer;

import org.junit.jupiter.api.Test;
import java.util.concurrent.*;
import static org.junit.jupiter.api.Assertions.*;

public class WeightedRandomBalancerTest {

    @Test
    public void testWeightedDistribution() {
        BackendManager mgr = new BackendManager();
        mgr.addServer("A", 5);
        mgr.addServer("B", 1);
        WeightedRandomBalancer bal = new WeightedRandomBalancer(mgr, new DefaultRandomGenerator());
        int countA = 0, total = 6000;
        for (int i = 0; i < total; i++) {
            if ("A".equals(bal.selectWeightedServer())) countA++;
        }
        // A 期望概率 5/6，允许 5% 误差
        assertTrue(Math.abs(countA / (double) total - 5.0 / 6) < 0.05);
    }

    @Test
    public void testConcurrentSelect() throws Exception {
        BackendManager mgr = new BackendManager();
        mgr.addServer("X", 2);
        mgr.addServer("Y", 3);
        WeightedRandomBalancer bal = new WeightedRandomBalancer(mgr, new DefaultRandomGenerator());
        ExecutorService pool = Executors.newFixedThreadPool(10);
        Callable<Void> task = () -> {
            for (int i = 0; i < 1000; i++) {
                bal.selectWeightedServer();
            }
            return null;
        };
        for (int i = 0; i < 10; i++) pool.submit(task);
        pool.shutdown();
        assertTrue(pool.awaitTermination(5, TimeUnit.SECONDS));
    }

    @Test
    public void testEmptyBackend() {
        BackendManager mgr = new BackendManager();
        WeightedRandomBalancer bal = new WeightedRandomBalancer(mgr, new DefaultRandomGenerator());
        assertThrows(IllegalStateException.class, bal::selectWeightedServer);
    }

    @Test
    public void testInvalidWeight() {
        BackendManager mgr = new BackendManager();
        assertThrows(IllegalArgumentException.class, () -> mgr.addServer("Z", 0));
    }
}