常见限流算法

参考文章

介绍

限流，也称流量控制。是指系统在面临高并发，或者大流量请求的情况下，限制新的请求对系统的访问，从而保证系统的稳定性。

常见限流算法有：

固定窗口/计数器
滑动窗口
限流桶
令牌桶

固定窗口/计数器

维护一个计数器，设置一个过期时间，例如：1min访问次数不能包括100次，有用户访问时，访问次数+1，超过阈值时拒绝该请求，每隔1min重制一次计数器。

但当用户第59s发送了100个请求和第61s发送了100个请求，此时因为计数器重制，所以会将这些请求放行

优点：实现简单

可以通过redis实现：设置过期时间，每次访问后值+1，同时判断下访问次数是否超过域值

滑动窗口

整个红色的矩形框表示一个时间窗口，举例的话，一分钟作为一个时间窗口，把它分割成6份，每份10s，过10s就把窗口向右移动一格，每个格子都有自己单独的计时器，当滑动窗口的格子划分的越多，那么滑动窗口的滚动就越平滑，限流的统计就会越精确

这样看的话，第一种方案其实是将1min作为一个窗口，即计数器是滑动窗口的一种特殊情况，所以也被称为固定窗口。

package limiter
// 代码摘自 https://juejin.cn/post/7056068978862456846

import (
   "errors"
   "sync"
   "time"
)

// SlidingWindowLimiter 滑动窗口限流器
type SlidingWindowLimiter struct {
   limit        int           // 窗口请求上限
   window       int64         // 窗口时间大小
   smallWindow  int64         // 小窗口时间大小
   smallWindows int64         // 小窗口数量
   counters     map[int64]int // 小窗口计数器
   mutex        sync.Mutex    // 避免并发问题
}

// NewSlidingWindowLimiter 创建滑动窗口限流器
func NewSlidingWindowLimiter(limit int, window, smallWindow time.Duration) (*SlidingWindowLimiter, error) {
   // 窗口时间必须能够被小窗口时间整除
   if window%smallWindow != 0 {
      return nil, errors.New("window cannot be split by integers")
   }

   return &SlidingWindowLimiter{
      limit:        limit,
      window:       int64(window),
      smallWindow:  int64(smallWindow),
      smallWindows: int64(window / smallWindow),
      counters:     make(map[int64]int),
   }, nil
}

func (l *SlidingWindowLimiter) TryAcquire() bool {
   l.mutex.Lock()
   defer l.mutex.Unlock()

   // 获取当前小窗口值
   currentSmallWindow := time.Now().UnixNano() / l.smallWindow * l.smallWindow
   // 获取起始小窗口值
   startSmallWindow := currentSmallWindow - l.smallWindow*(l.smallWindows-1)

   // 计算当前窗口的请求总数
   var count int
   for smallWindow, counter := range l.counters {
      if smallWindow < startSmallWindow {
         delete(l.counters, smallWindow)
      } else {
         count += counter
      }
   }

   // 若到达窗口请求上限，请求失败
   if count >= l.limit {
      return false
   }
   // 若没到窗口请求上限，当前小窗口计数器+1，请求成功
   l.counters[currentSmallWindow]++
   return true
}

漏桶

假设我们有一个水桶按固定的速率向下方滴落一滴水，无论有多少请求，请求的速率有多大，都按照固定的速率流出，对应到系统中就是按照固定的速率处理请求。如果桶的容量满了，就达到限流的阀值，就会丢弃水滴（拒绝请求）

关于漏桶的实现，uber团队有一个开源的 https://github.com/uber-go/ratelimit 实现。
使用方法也比较简单，Take() 方法会返回漏桶下一次滴水的时间。

package main

import (
    "fmt"
    "time"
    
    "go.uber.org/ratelimit"
)

func main() {
    // 限制每秒100次 -> 每隔10ms会放行一个请求
    rl := ratelimit.New(100) // per second

    prev := time.Now()
    for i := 0; i < 10; i++ {
        now := rl.Take()
        fmt.Println(i, now.Sub(prev))
        prev = now
    }

    // Output:
    // 0 0
    // 1 10ms
    // 2 10ms
    // 3 10ms
    // 4 10ms
    // 5 10ms
    // 6 10ms
    // 7 10ms
    // 8 10ms
    // 9 10ms
}

之后写一下这个库的详细介绍，在此不多赘述

令牌桶

令牌桶其实和漏桶的原理类似，令牌桶按固定的速率往桶里放入令牌，并且只要能从桶里取出令牌就能通过，令牌桶支持突发流量的快速处理。

对于从桶里取不到令牌的场景，我们可以选择等待也可以直接拒绝并返回。

实现时，我们不需要真正的每隔一段时间去发放令牌，记录下上次访问时间、上次访问令牌剩余数量，(当前时间-上次访问时间)*令牌生成速度+剩余令牌数得出当前令牌数

可以参考：https://github.com/juju/ratelimit ，部分代码如下

// 调整令牌数量
func (tb *Bucket) adjustavailableTokens(tick int64) {
    lastTick := tb.latestTick
    tb.latestTick = tick
    if tb.availableTokens >= tb.capacity {
        return
    }
    tb.availableTokens += (tick - lastTick) * tb.quantum
    if tb.availableTokens > tb.capacity {
        tb.availableTokens = tb.capacity
    }
    return
}

// 获取令牌，没有的话返回0，不阻塞(Take方法是会阻塞的)
func (tb *Bucket) takeAvailable(now time.Time, count int64) int64 {
    if count <= 0 {
        return 0
    }
    tb.adjustavailableTokens(tb.currentTick(now))
    if tb.availableTokens <= 0 {
        return 0
    }
    if count > tb.availableTokens {
        count = tb.availableTokens
    }
    tb.availableTokens -= count
    return count
}

func (tb *Bucket) currentTick(now time.Time) int64 {
    return int64(now.Sub(tb.startTime) / tb.fillInterval)
}

令牌桶算法能满足绝大部分服务器限流的需要, 是被广泛使用的限流算法, 不过其也有一些缺点:

令牌桶是没有优先级的，无法让重要的请求先通过
如果对服务限流进行缩容和扩容，需要人为手动去修改，运维成本比较大
令牌桶只能对局部服务端的限流, 无法掌控全局资源

限流的具体使用

网关限流：可以在nginx处做限流，参考文章 Nginx限流应用 & 漏桶/令牌桶算法原理
服务端限流：以gin框架为例，编写一个限流中间件，加入到需要限流的路由中即可
自适应限流：结合应用的 Load、CPU 使用率、总体平均 RT(请求成功的响应耗时)、入口 QPS 和并发线程数等几个维度的监控指标，通过自适应的流控策略，让系统的入口流量和系统的负载达到一个平衡，让系统尽可能跑在最大吞吐量的同时保证系统整体的稳定性。如Sentinel