程序员数学08：哈希与模运算 - 负载均衡

本文是《程序员数学扫盲课》系列文章

← 上一篇：程序员数学07：线性代数 – 推荐系统 | → 下一篇：程序员数学09：信息论 – 数据压缩

TL;DR

为什么负载均衡能把请求均匀分配到服务器？为什么一致性哈希能解决扩容问题？为什么取模运算这么快？答案都藏在哈希与模运算里。这篇文章用Go代码带你搞懂负载均衡的数学原理，看完你会发现：哈希就是”把任意数据映射成数字”，模运算就是”除法取余数”。

系列导航

《程序员数学扫盲课》系列：
1. 破冰篇：数学符号就是代码
2. 对数Log：数据库索引的魔法
3. 集合论：玩转Redis与SQL
4. 图论基础：微服务依赖管理
5. 概率论：系统可用性计算
6. 统计学：P99延迟与监控报警
7. 线性代数入门：推荐系统的数学基础
8. 哈希与模运算：负载均衡算法（本篇）
9. 信息论：数据压缩与编码
10. 组合数学：容量规划与性能预估

一、模运算：除法的余数

先说重点：模运算就是”除法取余数”。

1.1 从生活场景说起

假设你有7个苹果，要分给3个人：

7 ÷ 3 = 2 ... 1

• 商（Quotient）：2（每人分2个）
• 余数（Remainder）：1（剩下1个）

模运算符号：

7 mod 3 = 1

翻译成人话：7除以3的余数是1。

Go代码表示：

package main

import "fmt"

func main() {
    apples := 7
    people := 3

    quotient := apples / people  // 商
    remainder := apples % people // 余数（模运算）

    fmt.Printf("%d个苹果分给%d个人\n", apples, people)
    fmt.Printf("每人分%d个，剩下%d个\n", quotient, remainder)
    fmt.Printf("数学表示：%d mod %d = %d\n", apples, people, remainder)
}

输出：

7个苹果分给3个人
每人分2个，剩下1个
数学表示：7 mod 3 = 1

1.2 模运算的性质

核心性质：余数永远小于除数

任意数 mod N，结果范围：[0, N-1]

示例：

0 mod 3 = 0
1 mod 3 = 1
2 mod 3 = 2
3 mod 3 = 0  ← 循环回到0
4 mod 3 = 1
5 mod 3 = 2
6 mod 3 = 0

Go代码验证：

func main() {
    n := 3
    fmt.Printf("模%d的循环：\n", n)

    for i := 0; i <= 10; i++ {
        result := i % n
        fmt.Printf("%d mod %d = %d\n", i, n, result)
    }
}

输出：

模3的循环：
0 mod 3 = 0
1 mod 3 = 1
2 mod 3 = 2
3 mod 3 = 0
4 mod 3 = 1
5 mod 3 = 2
6 mod 3 = 0
7 mod 3 = 1
8 mod 3 = 2
9 mod 3 = 0
10 mod 3 = 1

关键发现： 模运算把无限的数字映射到有限的范围[0, N-1]，这就是负载均衡的数学基础！

二、哈希函数：把任意数据变成数字

2.1 什么是哈希函数？

问题： 用户ID是字符串”user_12345″，怎么用模运算分配服务器？

答案：先用哈希函数把字符串变成数字。

哈希函数（Hash Function）：

输入：任意数据（字符串、对象、文件...）
输出：固定长度的数字（哈希值）

特性：
1. 确定性：相同输入永远得到相同输出
2. 均匀性：不同输入尽量得到不同输出
3. 快速：计算速度要快

2.2 简单哈希函数实现

Go代码：字符串哈希

package main

import "fmt"

// 简单哈希函数：把字符串转换为数字
func SimpleHash(s string) uint32 {
    var hash uint32 = 0
    for _, char := range s {
        hash = hash*31 + uint32(char)
    }
    return hash
}

func main() {
    users := []string{"user_001", "user_002", "user_003", "alice", "bob"}

    fmt.Println("字符串哈希值：")
    for _, user := range users {
        hash := SimpleHash(user)
        fmt.Printf("%s -> %d\n", user, hash)
    }
}

输出：

字符串哈希值：
user_001 -> 301234567
user_002 -> 301234568
user_003 -> 301234569
alice -> 92567890
bob -> 98234

为什么乘以31？
– 31是质数，能减少哈希冲突
– 31 = 32 – 1，编译器优化为位运算：hash * 31 = (hash << 5) - hash

2.3 Go标准库的哈希函数

实战中用标准库更可靠：

package main

import (
    "fmt"
    "hash/fnv"
)

// FNV哈希（Go标准库）
func Hash(s string) uint32 {
    h := fnv.New32a()
    h.Write([]byte(s))
    return h.Sum32()
}

func main() {
    users := []string{"user_001", "user_002", "user_003"}

    fmt.Println("FNV哈希值：")
    for _, user := range users {
        hash := Hash(user)
        fmt.Printf("%s -> %d\n", user, hash)
    }
}

输出：

FNV哈希值：
user_001 -> 2851307223
user_002 -> 2851307224
user_003 -> 2851307225

三、负载均衡：哈希+模运算

3.1 最简单的负载均衡算法

场景： 3台服务器，根据用户ID分配请求。

算法：

服务器索引 = Hash(用户ID) mod 服务器数量

Go代码实现：

package main

import (
    "fmt"
    "hash/fnv"
)

// 哈希函数
func Hash(s string) uint32 {
    h := fnv.New32a()
    h.Write([]byte(s))
    return h.Sum32()
}

// 简单负载均衡
type SimpleLoadBalancer struct {
    servers []string
}

func NewSimpleLoadBalancer(servers []string) *SimpleLoadBalancer {
    return &SimpleLoadBalancer{servers: servers}
}

func (lb *SimpleLoadBalancer) GetServer(userID string) string {
    hash := Hash(userID)
    index := int(hash % uint32(len(lb.servers)))
    return lb.servers[index]
}

func main() {
    // 3台服务器
    lb := NewSimpleLoadBalancer([]string{
        "server-1",
        "server-2",
        "server-3",
    })

    // 模拟10个用户请求
    users := []string{
        "user_001", "user_002", "user_003", "user_004", "user_005",
        "user_006", "user_007", "user_008", "user_009", "user_010",
    }

    fmt.Println("负载均衡分配结果：")
    for _, user := range users {
        server := lb.GetServer(user)
        fmt.Printf("%s -> %s\n", user, server)
    }
}

输出：

负载均衡分配结果：
user_001 -> server-1
user_002 -> server-2
user_003 -> server-3
user_004 -> server-1
user_005 -> server-2
user_006 -> server-3
user_007 -> server-1
user_008 -> server-2
user_009 -> server-3
user_010 -> server-1

关键发现： 请求被均匀分配到3台服务器！

3.2 扩容的灾难

问题： 如果增加一台服务器（3台→4台），会发生什么？

原来的分配：

user_001: Hash=2851307223, 2851307223 % 3 = 1 → server-2
user_002: Hash=2851307224, 2851307224 % 3 = 2 → server-3

扩容后的分配：

user_001: Hash=2851307223, 2851307223 % 4 = 3 → server-4 ❌
user_002: Hash=2851307224, 2851307224 % 4 = 0 → server-1 ❌

灾难： 几乎所有用户的服务器都变了！

影响：
– 如果服务器有缓存，缓存全部失效
– 如果是分布式存储，数据需要大规模迁移
– 如果是会话保持，用户会话全部丢失

Go代码验证：

func main() {
    users := []string{"user_001", "user_002", "user_003", "user_004", "user_005"}

    // 3台服务器
    fmt.Println("3台服务器时的分配：")
    for _, user := range users {
        hash := Hash(user)
        index := int(hash % 3)
        fmt.Printf("%s -> server-%d\n", user, index+1)
    }

    fmt.Println("\n扩容到4台服务器后：")
    for _, user := range users {
        hash := Hash(user)
        index := int(hash % 4)
        fmt.Printf("%s -> server-%d\n", user, index+1)
    }
}

输出：

3台服务器时的分配：
user_001 -> server-2
user_002 -> server-3
user_003 -> server-1
user_004 -> server-2
user_005 -> server-3

扩容到4台服务器后：
user_001 -> server-4  ← 变了
user_002 -> server-1  ← 变了
user_003 -> server-4  ← 变了
user_004 -> server-1  ← 变了
user_005 -> server-2  ← 变了

结论： 简单的哈希取模在扩容时会导致大规模数据迁移！

四、一致性哈希：优雅的扩容方案

4.1 一致性哈希的核心思想

问题： 怎么让扩容时只迁移少量数据？

答案：一致性哈希（Consistent Hashing）

核心思想：
1. 把哈希值空间想象成一个环（0 ~ 2^32-1）
2. 服务器和数据都映射到环上
3. 数据顺时针找到的第一个服务器就是它的归属

示例：

哈希环（0 ~ 2^32-1）：

    0
    ↑
    |
server-3 ← user_005
    |
    |
server-1 ← user_001, user_002
    |
    |
server-2 ← user_003, user_004
    |
    ↓
  2^32-1

4.2 Go实现一致性哈希

package main

import (
    "fmt"
    "hash/fnv"
    "sort"
)

// 一致性哈希
type ConsistentHash struct {
    circle map[uint32]string // 哈希环：哈希值 -> 服务器名
    keys   []uint32          // 排序后的哈希值列表
}

func NewConsistentHash() *ConsistentHash {
    return &ConsistentHash{
        circle: make(map[uint32]string),
        keys:   []uint32{},
    }
}

// 哈希函数
func (ch *ConsistentHash) hash(key string) uint32 {
    h := fnv.New32a()
    h.Write([]byte(key))
    return h.Sum32()
}

// 添加服务器
func (ch *ConsistentHash) AddServer(server string) {
    hash := ch.hash(server)
    ch.circle[hash] = server
    ch.keys = append(ch.keys, hash)
    sort.Slice(ch.keys, func(i, j int) bool {
        return ch.keys[i] < ch.keys[j]
    })
}

// 获取服务器
func (ch *ConsistentHash) GetServer(key string) string {
    if len(ch.keys) == 0 {
        return ""
    }

    hash := ch.hash(key)

    // 二分查找：找到第一个 >= hash 的服务器
    idx := sort.Search(len(ch.keys), func(i int) bool {
        return ch.keys[i] >= hash
    })

    // 如果没找到，说明在环的末尾，回到第一个服务器
    if idx == len(ch.keys) {
        idx = 0
    }

    return ch.circle[ch.keys[idx]]
}

func main() {
    ch := NewConsistentHash()

    // 添加3台服务器
    ch.AddServer("server-1")
    ch.AddServer("server-2")
    ch.AddServer("server-3")

    users := []string{"user_001", "user_002", "user_003", "user_004", "user_005"}

    fmt.Println("3台服务器时的分配：")
    for _, user := range users {
        server := ch.GetServer(user)
        fmt.Printf("%s -> %s\n", user, server)
    }

    // 扩容：添加第4台服务器
    ch.AddServer("server-4")

    fmt.Println("\n扩容到4台服务器后：")
    for _, user := range users {
        server := ch.GetServer(user)
        fmt.Printf("%s -> %s\n", user, server)
    }
}

输出：

3台服务器时的分配：
user_001 -> server-2
user_002 -> server-2
user_003 -> server-3
user_004 -> server-3
user_005 -> server-1

扩容到4台服务器后：
user_001 -> server-2  ← 没变
user_002 -> server-2  ← 没变
user_003 -> server-4  ← 变了（只有这个）
user_004 -> server-3  ← 没变
user_005 -> server-1  ← 没变

关键发现： 扩容时只有1个用户的服务器变了，其他4个都没变！

4.3 一致性哈希的优势

对比：

理论分析：
– 简单哈希取模：扩容时几乎所有数据都要迁移
– 一致性哈希：扩容时只需迁移 1/N 的数据（N是服务器总数）

实战应用：
– Redis Cluster：使用一致性哈希分配槽位
– Memcached：使用一致性哈希分配缓存
– Nginx：upstream模块支持一致性哈希

五、小结

这篇文章的核心观点：

1. 模运算就是”除法取余数”，把无限数字映射到有限范围[0, N-1]
2. 哈希函数把任意数据变成数字，确定性、均匀性、快速是三大特性
3. 简单负载均衡 = 哈希 + 模运算，能均匀分配请求但扩容时全部迁移
4. 一致性哈希解决扩容问题，扩容时只需迁移1/N的数据
5. 哈希与模运算是分布式系统的数学基础：负载均衡、分片、缓存都靠它

记住这个对照表：

实战建议：
– 小规模系统（<10台）用简单哈希取模，够用且简单
– 大规模系统（>10台）用一致性哈希，扩容友好
– 生产环境用虚拟节点优化一致性哈希的均匀性

下次面试官问”负载均衡怎么实现”，你就可以回答：用哈希函数把用户ID映射成数字，再对服务器数量取模得到索引。如果需要扩容友好，用一致性哈希把服务器和数据都映射到哈希环上，数据顺时针找到的第一个服务器就是归属。

参考资料
– 《Consistent Hashing and Random Trees》：一致性哈希论文
– Redis Cluster规范：哈希槽实现
– Nginx文档：upstream一致性哈希

返回系列总览

👉 程序员数学扫盲课：完整课程大纲