限流器

参考

系统自适应限流

5种限流算法，7种限流方式，挡住突发流量

限流

通过对一个时间窗口内的请求量进行限制来保障系统的正常运行。如果我们的服务资源有限、处理能力有限，就需要对调用我们服务的上游请求进行限制，以防止自身服务由于资源耗尽而停止服务。

阈值：在一个单位时间内允许的请求量。

拒绝策略：超过阈值的请求的拒绝策略，常见的拒绝策略有直接拒绝、排队等。

常见限流算法(静态)

1.固定窗口算法

固定窗口算法又叫计数器算法，是一种简单方便的限流算法。主要通过一个支持原子操作的计数器来累计1秒内的请求次数，当一秒内计数达到限流阈值时触发拒绝策略。每过1秒，计数器重置为0。

2.滑动窗口算法

滑动窗口是对固定窗口算法的改进。在一个窗口内分段，不能从根本上解决时间窗口的临界突变问题。

3.滑动日志算法

记录下所有的请求时间点，新请求到来时先判断最近置顶时间范围内的请求数量是否超过指定阈值，由此来确定是否达到限流，这种方式没有了时间窗口突变的问题，限流比较准确，但是因为要记录每次请求的时间点，所以占用的内存较多。

4.漏桶算法

漏桶算法中的漏桶是一个形象的比喻，这里可以用生产者消费者模式进行说明，请求是一个生产者，每一个请求都如一滴水，请求到来后放到一个队列（漏桶）中，桶底有一个孔，不断漏出水滴，如消费者在消费队列中的内容，消费的速率（漏出的速度）等于限流阈值。漏桶的大小，就如队列的容量，当请求堆积超过指定容量时，会触发拒绝策略。

5.令牌桶算法

令牌桶的实现思路类似于生产者和消费者的关系。系统服务作为生产者，按照指定频率向桶中添加令牌，如果桶中令牌数量达到阈值，则不在添加。请求执行作为消费者，每个请求都需要去桶中拿取一个令牌，取到令牌则继续执行，如果桶中无令牌可取，则触发拒绝策略，可以是超时等待，也可以直接拒绝本次请求。

• Todo 令牌生成算法

  // 限流器结构体
  type Limiter
    // 构建一个限流器，r 是每秒放入的令牌数量，b 是桶的大小
    func NewLimiter(r Limit, b int) *Limiter
    // 分别返回 b 和 r 的值
    func (lim *Limiter) Burst() int
    func (lim *Limiter) Limit() Limit
    // token 消费方法
    func (lim *Limiter) Allow() bool
    func (lim *Limiter) AllowN(now time.Time, n int) bool
    func (lim *Limiter) Reserve() *Reservation
    func (lim *Limiter) ReserveN(now time.Time, n int) *Reservation
    func (lim *Limiter) Wait(ctx context.Context) (err error)
    func (lim *Limiter) WaitN(ctx context.Context, n int) (err error)
    // 动态流控
    func (lim *Limiter) SetBurst(newBurst int)
    func (lim *Limiter) SetBurstAt(now time.Time, newBurst int)
    func (lim *Limiter) SetLimit(newLimit Limit)
    func (lim *Limiter) SetLimitAt(now time.Time, newLimit Limit)

6.Redis分布式限流

Redis单线程，内存操作，速度快

1. 固定窗口限流：使用incr命令实现，使用时间戳为key。使用lua保证incr和expire是原子操作。

   local count = redis.call("incr",KEYS[1])
   if count == 1 then
     redis.call('expire',KEYS[1],ARGV[2])
   end
   if count > tonumber(ARGV[1]) then
     return 0
   end
   return 1

2. 滑动窗口限流：zset有序集合实现滑动窗口。lua保证原子性。

   --KEYS[1]: 限流 key
   --ARGV[1]: 时间戳 - 时间窗口
   --ARGV[2]: 当前时间戳（作为score）
   --ARGV[3]: 阈值
   --ARGV[4]: score 对应的唯一value
   -- 1. 移除时间窗口之前的数据
   redis.call('zremrangeByScore', KEYS[1], 0, ARGV[1])
   -- 2. 统计当前元素数量
   local res = redis.call('zcard', KEYS[1])
   -- 3. 是否超过阈值
   if (res == nil) or (res < tonumber(ARGV[3])) then
    redis.call('zadd', KEYS[1], ARGV[2], ARGV[4])
    return 1
   else
    return 0
   end