后端常用算法¶

学习目标¶

学完本章后，学习者应该能够：

理解 LRU、布隆过滤器、一致性哈希的工程用途。
区分固定窗口、滑动窗口、令牌桶、漏桶限流。
理解雪花算法、时间轮、BitMap、HyperLogLog 的适用场景。
能在系统设计中说明为什么选择某种算法。

LRU¶

LRU 是 Least Recently Used，最近最少使用。

核心思想：如果缓存空间满了，优先淘汰最久没有被访问的数据。

常见实现：

map：按 key O(1) 查找节点。
双向链表：维护访问顺序。

应用场景：

本地缓存。
页面缓存。
热点数据缓存。

LRU 适合“最近访问过的数据更可能再次访问”的场景。

布隆过滤器¶

布隆过滤器用于判断一个元素“一定不存在”或“可能存在”。

特点：

空间效率高。
查询快。
有误判率。
不能直接删除元素，除非使用变体。

典型场景：缓存穿透防护。

如果用户查询一个不存在的 ID，直接打数据库会造成压力。可以先用布隆过滤器判断：

一定不存在：直接返回。
可能存在：继续查缓存或数据库。

一致性哈希¶

一致性哈希用于在节点变化时减少 key 的迁移量。

普通取模：

node = hash(key) % N

当 N 变化时，大量 key 会重新映射。

一致性哈希把节点和 key 放在一个哈希环上，节点增加或减少时，只影响相邻区间的 key。

应用场景：

分布式缓存。
分库分表路由。
负载分配。

工程中通常还会加入虚拟节点，避免数据倾斜。

限流算法¶

固定窗口¶

按固定时间窗口计数，例如每分钟最多 100 次。

优点：实现简单。
缺点：窗口边界可能出现突刺。

滑动窗口¶

把时间窗口细分，统计最近一段时间的请求数。

优点：比固定窗口平滑。
缺点：实现复杂度和存储成本更高。

令牌桶¶

系统按固定速率生成令牌，请求需要拿到令牌才能通过。

优点：允许一定突发流量。
适合：API 限流、网关限流。

漏桶¶

请求进入桶中，以固定速率流出。

优点：输出速率稳定。
缺点：对突发流量不如令牌桶灵活。

雪花算法¶

雪花算法用于生成分布式唯一 ID。

常见组成：

时间戳。
机器 ID。
序列号。

优点：

趋势递增。
不依赖数据库自增。
性能高。

注意点：

时钟回拨。
机器 ID 分配。
ID 暴露业务规模。

时间轮¶

时间轮用于高效管理大量定时任务。

如果每个定时任务都用一个独立定时器，任务量很大时开销会很高。时间轮把时间划分为槽，把任务挂到对应槽位，到时间后批量触发。

应用场景：

延迟任务。
连接超时管理。
消息重试。
定时回调。

BitMap 与 HyperLogLog¶

BitMap 适合表示大量布尔状态。

场景：

用户签到。
是否访问过。
权限位。

HyperLogLog 用于基数估计，比如估算 UV。

特点：

占用空间小。
结果是近似值。
适合统计，不适合精确查询。

Go 后端实际应用例子¶

例子一：本地 LRU 缓存热点配置¶

Feature Flag、API Key 权限、租户配置这类数据通常读多写少，可以在服务进程内维护一层本地 LRU 缓存，减少 Redis 或数据库访问。

type Config struct {
    Key   string
    Value string
}

type ConfigStore interface {
    Get(key string) (Config, bool)
}

生产实现要同时考虑容量、过期时间、并发安全和配置变更通知。LRU 只解决“容量满了淘汰谁”，不解决“数据是否过期”和“配置变更后如何失效”。

例子二：用 Redis 固定窗口限流¶

固定窗口可以用 Redis INCR 和过期时间实现：

func RateLimitKey(userID string, minute int64) string {
    return "rate:user:" + userID + ":" + strconv.FormatInt(minute, 10)
}

基本流程：

根据用户 ID 和当前分钟生成 key。
执行 INCR key。
第一次创建 key 时设置 60 到 70 秒过期时间。
如果计数超过阈值，拒绝请求。

真实生产中建议用 Lua 脚本保证 INCR 和 EXPIRE 的原子性，避免服务在 INCR 后崩溃导致 key 没有过期。

例子三：用 BitMap 做用户签到¶

用户签到可以用 Redis BitMap 表示某天是否签到：

SETBIT checkin:2026-05 user_index 1
GETBIT checkin:2026-05 user_index

如果用户 ID 很稀疏，不能直接拿用户 ID 当 offset，需要先映射成紧凑下标，否则空间会被极大浪费。

常见误区¶

误区一：布隆过滤器可以准确判断存在。

它只能判断一定不存在或可能存在，存在误判。

误区二：所有限流都用一种算法。

不同场景适合不同限流算法。网关 API 常用令牌桶，严格平滑输出更适合漏桶。

误区三：分布式 ID 只要唯一就够。

还要考虑趋势递增、可用性、时钟回拨、信息泄露和存储索引效率。

实战任务¶

设计一个 API 限流器：

要求：

支持按用户 ID 限流。
每个用户每分钟最多访问 100 次。
说明使用固定窗口还是滑动窗口。
说明如何用 Redis 实现。
思考窗口边界突刺如何缓解。

参考答案

简单版本可以使用固定窗口。key 按用户 ID 和分钟拼接：

func RateLimitKey(userID string, now time.Time) string {
    minute := now.Unix() / 60
    return "rate:user:" + userID + ":" + strconv.FormatInt(minute, 10)
}

Redis 流程：

count = INCR key
if count == 1:
    EXPIRE key 70
if count > 100:
    reject
else:
    allow

生产中应使用 Lua 脚本保证 INCR 和 EXPIRE 原子执行，避免服务在 INCR 后崩溃导致 key 没有过期。

固定窗口的边界突刺问题：用户可能在上一分钟最后一秒请求 100 次，又在下一分钟第一秒请求 100 次。缓解方式包括滑动窗口、令牌桶，或把窗口切成多个小桶做近似滑动统计。

面试题¶

1. LRU 通常如何实现？¶

参考答案

LRU 通常用 map 加双向链表实现。map 负责根据 key O(1) 找到节点，双向链表负责维护访问顺序。每次访问节点时，把节点移动到链表头部；缓存满时，从链表尾部淘汰最久未访问的节点。

这种组合可以让 get 和 put 都接近 O(1)。单独使用 slice 或链表都难以同时满足快速查找和快速调整顺序。

2. 布隆过滤器为什么会误判？¶

参考答案

布隆过滤器通过多个哈希函数把元素映射到位数组上。不同元素可能把相同位置置为 1，因此查询某个从未加入的元素时，它对应的位可能都已经被其他元素置为 1，从而误判为“可能存在”。

但如果某个位置是 0，就能确定元素一定不存在。因此它适合过滤不存在的数据，但不能作为精确存在判断。

3. 一致性哈希解决什么问题？¶

参考答案

一致性哈希解决节点数量变化时大量 key 重新分布的问题。普通取模在节点增减时会导致大量 key 映射变化，而一致性哈希只影响哈希环上相邻区间的 key。

它常用于分布式缓存、分片路由和负载分配。实际使用中通常加入虚拟节点减少数据倾斜。

4. 令牌桶和漏桶有什么区别？¶

参考答案

令牌桶按固定速率生成令牌，请求拿到令牌即可通过，桶里有积累令牌时允许一定突发流量。漏桶把请求放入桶中，以固定速率流出，更强调输出平滑。

API 网关限流常用令牌桶，因为它能兼顾平均速率和短时突发。需要严格平滑处理速率时，漏桶更合适。

5. 雪花算法需要注意哪些问题？¶

参考答案

雪花算法需要注意时钟回拨、机器 ID 唯一性、序列号溢出、趋势递增对业务规模的暴露，以及不同语言或服务间 ID 格式一致性。

在生产环境中，时钟回拨是重点风险。常见处理方式包括等待时钟追上、使用备用序列、引入时钟回拨告警，或者使用中心化 ID 服务。