此篇介绍一下常见的几种限流算法。

问题背景

在突发流量增长的情况下,由于系统准备不足,很难通过短期扩容来应对 。此时,进行限流是最常用的手段,限流也是服务稳定性治理重要的手段之一。

限流的发生

限流可能发生在多个层面:

  1. 用户网络层:突发的流量场景如热点事件流量(秒杀事件、热门抢购,微博热搜),恶意刷流,竞对爬虫等。
  2. 内部应用层:上游服务的异常调用,脚本异常请求,失败重试策略造成流量突发。

实现限流的方案

常用的限流方法主要有三种:计数器算法,漏斗桶算法,令牌桶算法。

计数器算法

  1. 单机限流:使用全局内存计数
  2. 分布式系统限流:使用redis等公共存储计数,用incr可以保障原子性操作。

注意使用固定窗口还是滑动窗口优化的问题。

漏斗桶算法

  1. Uber提供了基于漏斗桶的算法实现可以参考:https://github.com/uber-go/ratelimit
  2. redis4.0提供了限流模块,redis-cell。该模块使用漏斗算法,并提供原子限流指令。

漏斗桶更像是对流量进行整形Traffic Shaping,所有流量过来都要进行排队,依次出去,可用于做一些论坛博客发帖频率限制。
由于出口处理速率是匀速的,短时有大量突发请求,即使负载压力不大,请求仍需要在队列等待处理。

令牌桶算法

  1. 当访问量小时,令牌桶可以积累令牌到桶满,而当短时突发流量,积累的令牌能保障大量请求可以立刻拿到令牌,令牌用完了,请求会依赖于新令牌申请速度,这时会退化成类似漏斗桶算法。
  2. 具体实现上可以使用redis的list,启动任务向list匀速放置数据,当有请求时从list取数据,取到代表通过,否则被限流。这么实现有个弊端,就是需要不断操作list,浪费内存空间,实际上可以使用实时算法计算的方式来计算可用令牌数。
  3. 还有更多可实现细节如预热桶、一次性放入多个令牌、一次性取多个令牌。同时由于原子性问题,通过redis+lua脚本操作(lua实现令牌桶)会更好。
  4. 令牌桶既能够将所有请求平均分布到时间区间内,又能接受突发请求,因此是使用最广泛的限流算法。

部署方式

  1. 集中部署统一的限流中心
  2. 限流部署在接入层
  3. 服务中心与单机限流结合

限流配置

  1. 接口粒度
  2. 时间粒度
  3. 最大限流数

命中限流后的处理

  1. 限流后处理方式可以做服务降级(返回默认值、默认页面)、请求丢弃(拒绝请求)、请求排队(阻塞请求)、发送报警人工介入处理等。
  2. 也有直接结合服务降级熔断的如Sentinel、Hystrix。