高并发限流算法

引言

在高并发系统中，面对超出系统承载极限的突发流量（如秒杀活动、恶意的 DDOS 爬虫），如果不对流量进行控制，很容易导致数据库连接池耗尽、服务器 CPU 满载进而导致整个系统雪崩。限流（Rate Limiting）是保障系统可用性的最后一道防火墙。

经典限流算法解析

1. 固定窗口计数器算法 (Fixed Window)

原理：将时间划分为固定大小的窗口（如 1 分钟），并在窗口内维护一个计数器。当请求进来时计数器加一，若超出设定的阈值则拒绝服务；进入下一窗口时，计数器清零。
致命缺点：临界问题（Spike）。如果在前一分钟的最后一秒和后一分钟的第一秒各有上限值的流量涌入，在极短的 2 秒内会承受两倍的极限流量，从而可能压垮系统。

2. 滑动窗口计数器算法 (Sliding Window)

原理：为了解决固定窗口的临界突刺，滑动窗口将时间窗口细分为更小的区间（如将 1 分钟细分为 6 个 10 秒）。随着时间推移，窗口向前滑动，每次计算限流都是统计当前时刻之前一整个窗口内的总请求数。这种细粒度的统计可以平滑流量。

3. 漏桶算法 (Leaky Bucket)

原理：可以把漏桶想象成一个底部有小孔的桶，水（请求）流入桶的速率是随意的，但从小孔流出（处理请求）的速率是恒定不变的。如果水流速度过快，桶装满了，多余的水就会直接溢出（被拒绝）。
特点：强行保证系统处理请求的速率绝对平滑，但无法应对突发流量（Burst Traffic）。

4. 令牌桶算法 (Token Bucket)

原理：系统以恒定的速率向“令牌桶”中放入令牌，桶满时多余的令牌溢出。当请求进来时，必须先从桶中拿到一个令牌，只有拿到令牌的请求才被允许处理，否则被拦截。
特点：不仅能够限制平均传输速率，还允许在桶内有积累令牌的情况下，应对一定程度的突发流量。因此在后端工程（如 Guava RateLimiter、Sentinel）中被最为广泛采用。

分布式限流的落地实践

在分布式微服务架构下，单机限流无法限制全局总流量。推荐使用 Redis + Lua 脚本的方式实现分布式令牌桶或滑动窗口限流：

local key = KEYS[1]
local limit = tonumber(ARGV[1])
local current = tonumber(redis.call('get', key) or "0")

if current + 1 > limit then
    return 0
else
    redis.call("INCRBY", key, 1)
    redis.call("EXPIRE", key, 1) -- 1秒过期
    return 1
end

利用 Redis 执行 Lua 脚本的原子性，可以避免多节点并发下的线程安全问题。

引言

经典限流算法解析

1. 固定窗口计数器算法 (Fixed Window)

原理：将时间划分为固定大小的窗口（如 1 分钟），并在窗口内维护一个计数器。当请求进来时计数器加一，若超出设定的阈值则拒绝服务；进入下一窗口时，计数器清零。

致命缺点：临界问题（Spike）。如果在前一分钟的最后一秒和后一分钟的第一秒各有上限值的流量涌入，在极短的 2 秒内会承受两倍的极限流量，从而可能压垮系统。

2. 滑动窗口计数器算法 (Sliding Window)

原理：为了解决固定窗口的临界突刺，滑动窗口将时间窗口细分为更小的区间（如将 1 分钟细分为 6 个 10 秒）。随着时间推移，窗口向前滑动，每次计算限流都是统计当前时刻之前一整个窗口内的总请求数。这种细粒度的统计可以平滑流量。

3. 漏桶算法 (Leaky Bucket)

原理：可以把漏桶想象成一个底部有小孔的桶，水（请求）流入桶的速率是随意的，但从小孔流出（处理请求）的速率是恒定不变的。如果水流速度过快，桶装满了，多余的水就会直接溢出（被拒绝）。

特点：强行保证系统处理请求的速率绝对平滑，但无法应对突发流量（Burst Traffic）。

4. 令牌桶算法 (Token Bucket)

原理：系统以恒定的速率向“令牌桶”中放入令牌，桶满时多余的令牌溢出。当请求进来时，必须先从桶中拿到一个令牌，只有拿到令牌的请求才被允许处理，否则被拦截。

特点：不仅能够限制平均传输速率，还允许在桶内有积累令牌的情况下，应对一定程度的突发流量。因此在后端工程（如 Guava RateLimiter、Sentinel）中被最为广泛采用。

分布式限流的落地实践

在分布式微服务架构下，单机限流无法限制全局总流量。推荐使用 Redis + Lua 脚本的方式实现分布式令牌桶或滑动窗口限流：

local key = KEYS[1] local limit = tonumber(ARGV[1]) local current = tonumber(redis.call('get', key) or "0") if current + 1 > limit then return 0 else redis.call("INCRBY", key, 1) redis.call("EXPIRE", key, 1) -- 1秒过期 return 1 end

利用 Redis 执行 Lua 脚本的原子性，可以避免多节点并发下的线程安全问题。