load-balancer-algorithm

Go 负载均衡算法实现

English Version

20250324:趁热输出了一篇关于负载均衡算法介绍的博客

希望帮助大家理解，有兴趣的同学可以看看，博客链接

这个项目用 Go 语言实现了几种常见的负载均衡算法，可用于分布式系统中的负载分配。

本项目参考了 @Zheaoli 的 Python 实现，并对算法进行了 Go 语言的重新实现和优化。

快速开始

go get github.com/catwithtudou/load-balancer-algorithm

这个仓库适合作为理解负载均衡策略的代码样例，也可以直接把 loadbalancer 包引入到实验项目里做对比验证。

实现的算法

本项目实现了以下四种负载均衡算法：

1. 随机选择 (Random Selection)
2. 轮询 (Round Robin)
3. 最小连接 (Least Connections)
4. Maglev 一致性哈希 (Consistent Hashing)

每种算法都支持加权和非加权版本，以适应不同场景下的负载均衡需求。

算法详解

1. 随机选择算法

随机选择算法是最简单的负载均衡策略之一，它随机从可用服务器池中选择一个服务器来处理请求。

特点：

• 实现简单，易于理解
• 支持加权随机选择，权重越大被选中的概率越高
• 过滤不可用（权重为0）的服务器

适用场景：

• 服务器性能相近
• 请求处理时间差异不大
• 请求分布相对均衡

2. 轮询算法

轮询算法按照顺序依次选择服务器，实现请求的平均分配。

特点：

• 按顺序循环选择服务器
• 支持加权轮询（平滑加权轮询算法），权重大的服务器处理更多请求
• 可以跳过不可用的服务器

适用场景：

• 服务器配置相近
• 请求负载均衡
• 适合长期运行的系统中保持均衡负载

3. 最小连接算法

最小连接算法选择当前活动连接数最少的服务器，优化资源利用率。

特点：

• 动态跟踪每台服务器的连接数
• 支持加权最小连接算法，考虑服务器权重和当前连接数的比值
• 在连接完成后释放资源
• 使用原子操作确保并发安全

适用场景：

• 请求处理时间差异大
• 服务器处理能力不同
• 需要动态平衡负载的场景

4. Maglev 一致性哈希算法

Maglev 一致性哈希算法是 Google 设计的高效一致性哈希算法，用于大规模分布式系统。

特点：

• 使用哈希表实现 O(1) 的查找性能
• 服务器变更时，最小化重新映射的请求数
• 支持加权一致性哈希，权重大的服务器处理更多请求
• 使用双哈希函数（murmur3 和 xxh3）提高随机性和分布均匀性

适用场景：

• 需要会话保持或缓存一致性的系统
• 服务器动态增减频繁的环境
• 大规模分布式系统

使用示例

package main

import (
    "fmt"
    "github.com/catwithtudou/load-balancer-algorithm/loadbalancer"
)

func main() {
    // 创建服务器
    servers := []*loadbalancer.Server{
        {Address: "192.168.1.1:8080", Weight: 1},
        {Address: "192.168.1.2:8080", Weight: 2},
        {Address: "192.168.1.3:8080", Weight: 3},
    }

    // 创建负载均衡器 (以一致性哈希为例)
    lb := loadbalancer.NewMaglevHashLoadBalancer()

    // 添加服务器
    for _, server := range servers {
        lb.AddServer(server)
    }

    // 使用负载均衡器选择服务器
    for i := 0; i < 5; i++ {
        key := fmt.Sprintf("user%d", i)
        server := lb.GetServer(key)
        fmt.Printf("请求 %s 被分配到服务器: %s\n", key, server.Address)
    }
}

性能测试与对比

各算法在不同场景下的性能对比：

算法	时间复杂度	空间复杂度	一致性	负载均衡性	适合场景
随机选择	O(1)	O(n)	低	中	简单系统，短连接
轮询	O(1)	O(n)	低	高	性能接近的服务器集群
最小连接	O(n)	O(n)	中	高	处理时间差异大的请求
Maglev哈希	O(1)	O(m)	高	中	需要会话保持的系统

项目结构

loadbalancer/
  ├── base.go           # 基础结构和接口定义
  ├── random.go         # 随机选择算法实现
  ├── round_robin.go    # 轮询算法实现
  ├── least_connections.go  # 最小连接算法实现
  └── consistent_hash.go    # Maglev一致性哈希算法实现