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

问题背景

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

限流的发生

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

  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。