限流算法

予早 2025-08-31 14:59:19
Categories： Tags：

限流算法

https://blog.csdn.net/sco5282/article/details/131828513

流量方向

按流量方向，请求分为：

限流则根据不同需求会对入站请求或者出站请求限流。

入站请求限流

限流方案

为什么要进行限流？

  1. 当流量突增，服务无法处理过来，于是多余请求会排队，排队也会占用服务资源造成恶性循环（请求处理不过来->额外请求占用资源->资源不够请求处理不过来），直至服务宕机。限流是为了断臂求生，抛弃实在处理不过来的流量，保证服务不宕机，仍然可用。
  2. 当服务流量承载有限，若某一个用户的请求频繁，导致其他用户的请求无法被服务处理，此时就会因为一个用户的体验而牺牲其他多个用户的体验，所以，需要给每个用户限流。在B2B业务中，通常会根据客户合作级别进行接口调用额度限制，一个月调用不超过多少次或者QPS限制在多少，或两者共同限制。

以上，总结一下就是，限流是为了保证某部分流量突增时服务依然可用。

限流解决了什么问题

保证服务高可用，牺牲一部分的流量，换取服务的可用性。对于被限流器直接作用的应用来说，除了保证自身不被流量击垮，还保护了依赖它的下游应用。

出站请求限流

调第三方发短信接口，在业务峰值的时候，经常会有些短信没有发出去。找第三方排查之后发现，发短信接口接口限流了。原因是，发短信接口要求我们传一套账号密码，这个账号密码是第三方提供的。第三方针对这个账号密码做了限流，一套账号密码只有20QPS。

公司最近在做一个项目，需要调用第三方的接口获取订单数据。但是第三方系统提供出来的接口有调用限制，每秒只能被请求6次，如果超过这个限制，就会报异常。需求要求在保证效率的前提下（每秒调用6次需要打满），还需要这个功能高可用（少报错甚至不报错）。

方案一：找第三方提高限流阈值，通常这类接口属于B2B业务，企业会付费服务，一般情况，三方企业会设置不同付费级别（会员体系）来设置不同的限流级别，优先考虑让三方企业提高阈值。

方案二：使用更多账号，若单个三方账号不能或者不容易提高阈值，那么可以考虑申请多个三方账号，保证QPS总量提高，这样会有一个账号池，从账号池中获取一个账号进行请求，如果该账号被限流可以换一个重试，推荐将账号池以队列结构组织，每次从队列中获取一个账号，发送请求后，将该账号入队，这样可以将请求打到每个账号，充分利用账号的QPS资源。不过这种分账号的方案也有限制，例如接口访问的这个资源属于一个账号，尽管可以在这个账号下分配子账号，单限流是针对整个账号体系进行的，这样就不太合适，本方案适用于短信邮件发送等资源相同但比较独立的功能。

上面两种方案是用来突破限流的，不被限流是最好的解决限流的方案，下面还有一些被限流的优雅处理方案，但被限流的事实并没有被改变。。

方案三：将本服务的请求封装为一个异步功能，例如A服务调用B服务，B服务负责对接三方接口，但由于三方接口可能限流，于是，将B服务的接口作异步处理，A接口访问B服务后，创建一个任务，这个任务负责请求三方服务以及进行被限流时的重试，对A服务返回一个回调地址，这样对于A服务而言，感知不到限流，也是一种处理方式。不过并没有改变被限流的事实。

方案四：重试

如果要求同步调用，那么最简单直接的方案就是根据三方限流速率设置合理重试方案进行重试。

方案五：重试的最大问题在于不会区分用户流量，例如A和B会调用C的接口，其中C服务负责对接三方服务，那么有可能A服务会将三方接口资源QPS占满，这样B服务就无法调用，于是这种情况下必须要在C服务按照服务粒度或者更细粒度进行限流。

根据应用场景选择合适的限流算法，如：

流量均匀：使用漏桶算法。
流量突发：使用令牌桶算法。
资源受限：使用容器限流。
3.2 考虑限流粒度
限流粒度包括：

IP限流：限制单个IP的请求速率。
用户限流：限制用户的请求速率。
接口限流：限制接口的请求速率。

限流带来的问题

任何技术都是双刃剑，没有绝对的好用，能带来优点必然也会带来问题。

设计限流组件本身需要考虑的点

如果我来设计限流组件，我大致会确认如下几个点：

1.明确限流器的目的：

2.明确限流器的维度，例如 IP 维度，用户授权 token 维度，API 维度等

3.怎么保证限流组件的高可用？

4.怎么解决使用限流组件后带来的一致性问题？

5.怎么缩小限流器的粒度，实现平滑限流？

流量受限通用处理策略

突发流量”（Bursting）

是否允许速率受限后以排队形式承载一部分突发流量

限流算法

固定窗口算法

核心思路

在一个固定时间范围内，允许一定访问次数，超过该访问次数，就拒绝多余访问。

从第一次请求开始（假定为t时进行请求），创建一个计数器，用于记录[t, t + w)内请求的次数（w为固定时间范围），只要超过指定的访问次数，就拒绝新的请求。当时间超过t+w时，重置计数器，记录[t+w, t + 2w) 内的请求，依此类推。

实现方案

Redis + Lua
-- 获取调用脚本时传入的第一个 key 值（用作限流的 key）
local key = KEYS[1]
-- 获取调用脚本时传入的第一个参数值（限流大小）
local limit = tonumber(ARGV[1])
-- 获取计数器的限速区间 TTL
local ttl = tonumber(ARGV[2]

-- 获取当前流量大小
local curentLimit = tonumber(redis.call('get', key) or "0")

-- 是否超出限流
if curentLimit + 1 > limit then
    -- 返回 (拒绝)
    return 0
else
    -- 没有超出 value + 1
    redis.call('INCRBY', key, 1)
    -- 如果 key 中保存的并发计数为 0，说明当前是一个新的时间窗口，它的过期时间设置为窗口的过期时间
    if (current_permits == 0) then
            redis.call('EXPIRE', key, ttl)
      end
    -- 返回 (放行)
    return 1
end

注意事项

固定窗口算法的问题在于窗口边界的流量突刺

故使用固定窗口算法时，应当在合理范围内尽可能使得时间窗口更小，这样流量突刺会多而小。

滑动窗口算法

核心思路

在一个滑动时间范围内，允许一定访问次数，超过该访问次数，就拒绝多余访问。

从第一次请求开始（假定为t时进行请求），创建一个计数器，用于记录(t - w, t]内请求的次数（w为固定时间范围，now为），只要超过指定的访问次数，就拒绝新的请求。当新的请求开始时（假定为t1进行请求），那么该计数器统计(t1 - 2, t1] 内的请求次数，每次请求时统计的窗口会随着该次请求时间发生滑动，依此类推。

实现方案

Redis + Lua

Zset（有序集合）在Redis中用来实现滑动窗口限流的主要思路是利用其自动排序和可过期成员的特点：

初始化及数据结构选择：

为需要限流的接口或服务创建一个唯一的键（key）对应一个Zset。
Zset中的每个成员通常是请求的唯一标识符（如UUID或其他唯一字符串），用于区分不同的请求。
Zset的score字段用来存储每个请求的时间戳，由于Redis中的score支持浮点数，通常会存储Unix时间戳（秒级或毫秒级精度）。
添加请求记录：

当有新的请求到来时，将当前时间戳作为score，添加到Zset中，同时成员可以是任意唯一标识符，或者是省略，仅保留score的有序排列。
检查窗口内的请求数量：

根据限流策略（比如每分钟100次），计算出当前时间戳对应的窗口开始时间（当前时间减去窗口长度）。
使用Zset的ZCARD命令，查找score在窗口范围内的元素数量。
如果数量超过设定的阈值，则拒绝新请求。
移除过期请求记录：

可以结合Zset的过期功能（TTL）来自动清理超时的请求记录，也可以在每次处理请求时手动清理窗口开始时间之前的所有记录，这样能确保Zset只包含当前窗口内的请求。
原子操作与并发控制：

在高并发场景下，为了保证限流逻辑的正确执行，可以通过编写Lua脚本来实现一系列操作的原子性执行，避免因并发问题造成的计数不准确。

注意事项

漏桶算法，Leaky Bucket

核心思路

  1. 水龙头中的水向漏桶中注入（请求不断向服务器请求队列中发起）
  2. 漏桶中存储若干来不及漏出的水（服务器请求队列中存储若干来不及处理的请求）
  3. 漏桶中的水以恒定速率漏出（请求队列中请求以恒定速率交由服务器处理）
  4. 漏桶满后新流入的水直接溢出（请求队列满后新的请求被直接抛弃不予处理）

注：

实现方案

基于 nginx 自身的漏桶算法

漏桶算法可以根据用户的IP进行限流，可以设置每秒访问的请求数，我们可以配合nginx来完成漏桶算法

http {
limit_req_zone $binary_remote addr zone=servicelRateLimit:10m rate=10r/s
server {
listen 80;
server_name localhost;

location /{
limit_req_zone = servicelRateLimit burst=20 nodelay;
proxy_pass http://targetserver;
}
}
}
语法：limit_req_zone key zone rate

key:定义限流对象，binary_remote_addr就是一种key，基于客户端ip限流

Zone：定义共享存储区来存储访问信息，10m可以存储16wip地址访问信息

Rate：最大访问速率，rate=10r/s 表示每秒最多请求10个请求

burst=20：相当于桶的大小

Nodelay：快速处理

使用 nginx 做限流

nginx 提供了基于漏桶算法的限流，

 limit_req_zone  $arg_sku_id  zone=skuzone:10m      rate=6r/m;
  limit_req_zone  $http_user_id  zone=userzone:10m      rate=6r/m;
  limit_req_zone  $binary_remote_addr  zone=perip:10m      rate=6r/m;
  limit_req_zone  $server_name        zone=perserver:1m   rate=6r/m;

注意事项

漏桶算法中漏桶漏出速率通常是该接口平均请求速率，其适用场景在于流量整形，可以将突发流量整形为平均请求速率，这样来保证该接口以及下游接口稳定。

由于漏桶算法将该接口速率强行整流为不超过平均请求速率，致使该接口无法跑满性能，是一种牺牲性能换取可用性的方案。

令牌桶算法

核心思路

令牌：每次请求都需要消耗若干令牌

令牌桶：令牌的容器，容器大小决定可容纳令牌数量，

令牌填充：令牌会按照一定速率被新增到令牌桶中，当令牌桶满不再新增

令牌消耗：每请求一次，就消耗桶中若干令牌，若桶中没有令牌，则请求被丢弃或者进入等待队列

实现方案

Redis + Lua
-- key
local key = KEYS[1]
-- 最大存储的令牌数
local max_permits = tonumber(KEYS[2])
-- 每秒钟产生的令牌数
local permits_per_second = tonumber(KEYS[3])
-- 请求的令牌数
local required_permits = tonumber(ARGV[1])

-- 下次请求可以获取令牌的起始时间
local next_free_ticket_micros = tonumber(redis.call('hget', key, 'next_free_ticket_micros') or 0)

-- 当前时间
local time = redis.call('time')
-- time[1] 返回的为秒，time[2] 为 ms
local now_micros = tonumber(time[1]) * 1000000 + tonumber(time[2])

-- 查询获取令牌是否超时（传入参数，单位为 微秒）
if (ARGV[2] ~= nil) then
    -- 获取令牌的超时时间
    local timeout_micros = tonumber(ARGV[2])
    local micros_to_wait = next_free_ticket_micros - now_micros
    if (micros_to_wait> timeout_micros) then
        return micros_to_wait
    end
end

-- 当前存储的令牌数
local stored_permits = tonumber(redis.call('hget', key, 'stored_permits') or 0)
-- 添加令牌的时间间隔（1000000ms 为 1s）
-- 计算生产 1 个令牌需要多少微秒
local stable_interval_micros = 1000000 / permits_per_second

-- 补充令牌
if (now_micros> next_free_ticket_micros) then
    local new_permits = (now_micros - next_free_ticket_micros) / stable_interval_micros
    stored_permits = math.min(max_permits, stored_permits + new_permits)
    -- 补充后，更新下次可以获取令牌的时间
    next_free_ticket_micros = now_micros
end

-- 消耗令牌
local moment_available = next_free_ticket_micros
-- 两种情况：required_permits<=stored_permits 或者 required_permits>stored_permits
local stored_permits_to_spend = math.min(required_permits, stored_permits)
local fresh_permits = required_permits - stored_permits_to_spend;
-- 如果 fresh_permits>0，说明令牌桶的剩余数目不够了，需要等待一段时间
local wait_micros = fresh_permits * stable_interval_micros

-- Redis 提供了 redis.replicate_commands() 函数来实现这一功能，把发生数据变更的命令以事务的方式做持久化和主从复制，从而允许在 Lua 脚本内进行随机写入
redis.replicate_commands()
-- 存储剩余的令牌数：桶中剩余的数目 - 本次申请的数目
redis.call('hset', key, 'stored_permits', stored_permits - stored_permits_to_spend)
redis.call('hset', key, 'next_free_ticket_micros', next_free_ticket_micros + wait_micros)
redis.call('expire', key, 10)

-- 返回需要等待的时间长度
-- 返回为 0（moment_available==now_micros）表示桶中剩余的令牌足够，不需要等待
return moment_available - now_micros

在redis中，为了避免重复发送脚本数据浪费网络资源，可以使用script load命令进行脚本数据缓存，并且返回一个哈希码作为脚本的调用句柄，

每次调用脚本只需要发送哈希码来调用即可。

redis-cell

redis-cell，令牌桶限流：https://blog.csdn.net/yzf279533105/article/details/111310685

注意事项

分布式限流器降级处理

分布式限流器发生故障时，需要将分布式限流器降级处理为本地限流器。例如，基于 Redis + Lua 实现的分布式限流器，若Redis 宕机，会使得所有请求超时，此时必须主动降级为本地限流器。

使用 Redis 作为限流工具时，确实需要考虑其服务的稳定性。尽管 Redis 是一个高可用、高性能的键值数据库，但在实际生产环境中，任何服务都可能因为各种原因（如硬件故障、网络问题、软件错误等）出现暂时不可用的情况。针对 Redis 崩溃或不可用的情况，可以采取以下几种策略来应对：

  1. 冗余与高可用部署：
    • 主从复制：配置 Redis 主从架构，确保数据在多个节点间同步。当主节点崩溃时，可以通过自动或手动切换到已同步数据的从节点继续提供服务。
    • 哨兵模式（Sentinel）：使用 Redis Sentinel 提供自动故障检测和主节点切换功能，进一步提升系统的自我恢复能力。
    • 集群模式：部署 Redis 集群，将数据和负载分散在多个节点上，即使部分节点不可用，整个集群仍能继续提供服务。
  2. 客户端容错与重试：
    • 连接池管理：在客户端实现连接池管理，当连接失败时能够自动重新建立连接或从池中获取其他可用连接。
    • 重试策略：对于因 Redis 临时不可用导致的失败操作，实施合理的重试策略。比如，短暂延迟后重试（指数退避或固定间隔重试），避免短时间内频繁重试加重 Redis 服务器负担。
    • 降级策略：在 Redis 不可用时，客户端可以暂时执行降级逻辑，如放宽限流条件、允许一定比例的请求通过（牺牲一部分限流效果），或者暂时禁用限流功能，确保服务的基本可用性。
  3. 本地缓存与兜底逻辑：
    • 本地计数：在客户端（如应用程序服务器）维持一个本地计数器，用于在短时间内（如几秒钟）进行限流。这样，在 Redis 短暂不可用期间，可以依赖本地计数器进行限流，待 Redis 恢复后，再将本地计数同步回 Redis。
    • 熔断与降级：在客户端或服务治理框架中设置熔断机制，当连续检测到 Redis 服务不可用时，触发熔断状态，直接拒绝部分非关键请求或返回默认值，防止请求堆积导致系统雪崩。
  4. 监控与报警：
    • 实时监控：对 Redis 服务的运行状态、性能指标、故障事件进行实时监控，及时发现异常情况。
    • 报警通知：设置警报阈值和通知机制，一旦 Redis 出现故障或性能下降，立即通知运维人员进行干预。
k8s (copy) (copy)
Consul