限流算法
- 计数器算法 维护一个 counter，规定在单位时间内 counter 的大小不能超过最大值，每隔固定时间就将 counter 的值置零。如果这个 counter 大于设定的阈值，那么系统就拒绝请求
- 漏桶算法
- 漏桶算法维护一个固定容量的桶，这个桶会按照指定的速度漏水。请求到达系统就类似于将水加入桶中，这个速度可以是匀速的也可以是瞬间的，如果这个桶满了，就会忽略后面的请求，直到这个桶可以存放多余的水。
好处：可以将系统的处理能力维持在一个比较平稳的水平
缺点：瞬间流量过来时，如果满了就会拒绝后面的请求流量 - 令牌桶算法
令牌桶算法系统按照指定的速度往桶中添加 token，每来一个请求，就从桶里拿走一个 token，如果没有 token 就拒绝服务
好处：控制系统的处理速度，通过统计信息实时优化令牌桶的大小与漏桶算法的区别：
令牌桶算法由于在令牌桶里攒了很多令牌，因此在大流量到达的瞬间可以一次性将队列中所有的请求都处理完，然后按照恒定的速度处理请求
漏桶算法是一直有一个恒等阈值，在大流量到达的时候，也会将多余的请求拒绝
限流实践
guava 的 concurrent 中有一个限流工具类 RateLimiter，其实现了单机限流，使用了令牌桶算法，它支持两种令牌获取接口：获取不到一直阻塞；在指定时间内获取不到就阻塞，超过这个时间就返回获取失败
- 使用 RateLimiter，单机限流
//初始化令牌桶大小，初始大小为2000 private RateLimiter ratelimiter = RateLimiter.create(2000); public void process() { //获取令牌，获取不到就阻塞 rateLimiter.acquire(); //执行业务操作，例如写数据库 bizLogic(); }
如果请求可以丢弃，防止大量请求过来耗尽系统资源，可以使用 tryAcquire()方法，和带超时的 tryAcquire()，在指定时间内获取不到令牌就返回 false
private RateLimiter rateLimiter = RateLimiter.create(2000); if(rateLimiter.tryAcquire()) { doSomething(); } else { doSomethingElse(); }
RateLimiter 详细分析可见：https://www.jianshu.com/p/362d261115e7
- 使用 Redis, 分布式限流
比如 1 秒内请求数量限制在 2000 内
- 使用 Redis 实现计数器算法
设置 redis 可以的过期时间为 1 秒，每次请求过来 value 加 1，如果 value 超过 2000 就拒绝访问，使用 Lua 脚本实现 incr 和 expire 的原子性
local key =KEYS\[1\] local expire_time =ARGV\[1\] local count =redis.call("INCR", key, 1) if count == 1then redis.call("EXPIRE", key, expire_time) end return count
- 使用 Redis 实现令牌桶算法
使用 Redis 的 List 结构实现 定时任务执行，使用 rightPush 放入令牌，并保证令牌的唯一性
// 1S 的速率往令牌桶中添加 UUID，只为保证唯一性 @Scheduled(fixedDelay = 1000,initialDelay = 0) public void setIntervalTimeTask(){ redisTemplate.opsForList().rightPush("limit_list",UUID.randomUUID().toString()); }
使用 leftPop 获取令牌
public Response limitFlow(Long id){ Object result = redisTemplate.opsForList().leftPop("limit_list"); if(result == null){ return Response.ok("当前令牌桶中无令牌"); } return Response.ok(articleDescription); }
