[Go语言] Go实现各类限流的方法

X-RateLimit-Limit: 60     //每秒60次请求
X-RateLimit-Remaining: 22   //当前还剩下多少次
X-RateLimit-Reset: 1612184024 //限制重置时间

   

• 计数器   
  
• 滑动窗口   
  
• 漏桶   
  
• 令牌桶
  

　　计数器是一种最简单限流算法，其原理就是：在一段时间间隔内，对请求进行计数，与阀值进行比较判断是否需要限流，一旦到了时间临界点，将计数器清零。这个就像你去坐车一样，车厢规定了多少个位置，满了就不让上车了，不然就是超载了，被交警叔叔抓到了就要罚款的，如果我们的系统那就不是罚款的事情了，可能直接崩掉了。

   

• 可以在程序中设置一个变量 count，当过来一个请求我就将这个数+1，同时记录请求时间。   
  
• 当下一个请求来的时候判断 count 的计数值是否超过设定的频次，以及当前请求的时间和第一次请求时间是否在 1 分钟内。   
  
• 如果在 1 分钟内并且超过设定的频次则证明请求过多，后面的请求就拒绝掉。   
  
• 如果该请求与第一个请求的间隔时间大于计数周期，且 count 值还在限流范围内，就重置 count。
  

package main
 
import (
  "log"
  "sync"
  "time"
)
 
type Counter struct {
  rate  int       //计数周期内最多允许的请求数
  begin time.Time   //计数开始时间
  cycle time.Duration //计数周期
  count int       //计数周期内累计收到的请求数
  lock  sync.Mutex
}
 
func (l *Counter) Allow() bool {
  l.lock.Lock()
  defer l.lock.Unlock()
 
  if l.count == l.rate-1 {
    now := time.Now()
    if now.Sub(l.begin) >= l.cycle {
      //速度允许范围内， 重置计数器
      l.Reset(now)
      return true
    } else {
      return false
    }
  } else {
    //没有达到速率限制，计数加1
    l.count++
    return true
  }
}
 
func (l *Counter) Set(r int, cycle time.Duration) {
  l.rate = r
  l.begin = time.Now()
  l.cycle = cycle
  l.count = 0
}
 
func (l *Counter) Reset(t time.Time) {
  l.begin = t
  l.count = 0
}
 
func main() {
  var wg sync.WaitGroup
  var lr Counter
  lr.Set(3, time.Second) // 1s内最多请求3次
  for i := 0; i < 10; i++ {
    wg.Add(1)
    log.Println("创建请求:", i)
    go func(i int) {
      if lr.Allow() {
        log.Println("响应请求:", i)
      }
      wg.Done()
    }(i)
 
    time.Sleep(200 * time.Millisecond)
  }
  wg.Wait()
}

　　2021/02/01 21:16:12 创建请求: 0
2021/02/01 21:16:12 响应请求: 0
2021/02/01 21:16:12 创建请求: 1
2021/02/01 21:16:12 响应请求: 1
2021/02/01 21:16:12 创建请求: 2
2021/02/01 21:16:13 创建请求: 3
2021/02/01 21:16:13 创建请求: 4
2021/02/01 21:16:13 创建请求: 5
2021/02/01 21:16:13 响应请求: 5
2021/02/01 21:16:13 创建请求: 6
2021/02/01 21:16:13 响应请求: 6
2021/02/01 21:16:13 创建请求: 7
2021/02/01 21:16:13 响应请求: 7
2021/02/01 21:16:14 创建请求: 8
2021/02/01 21:16:14 创建请求: 9

type LeakyBucket struct {
  rate     float64 //固定每秒出水速率
  capacity   float64 //桶的容量
  water    float64 //桶中当前水量
  lastLeakMs int64   //桶上次漏水时间戳 ms
  lock sync.Mutex
}
func (l *LeakyBucket) Allow() bool {
  l.lock.Lock()
  defer l.lock.Unlock()
  now := time.Now().UnixNano() / 1e6
  eclipse := float64((now - l.lastLeakMs)) * l.rate / 1000 //先执行漏水
  l.water = l.water - eclipse                //计算剩余水量
  l.water = math.Max(0, l.water)               //桶干了
  l.lastLeakMs = now
  if (l.water + 1) < l.capacity {
    // 尝试加水,并且水还未满
    l.water++
    return true
  } else {
    // 水满，拒绝加水
    return false
  }
}
func (l *LeakyBucket) Set(r, c float64) {
  l.rate = r
  l.capacity = c
  l.water = 0
  l.lastLeakMs = time.Now().UnixNano() / 1e6
}

   

• 漏桶具有固定容量，出水速率是固定常量（流出请求）   
  
• 如果桶是空的，则不需流出水滴   
  
• 可以以任意速率流入水滴到漏桶（流入请求）   
  
• 如果流入水滴超出了桶的容量，则流入的水滴溢出（新请求被拒绝）
  

type TokenBucket struct {
  rate     int64 //固定的token放入速率, r/s
  capacity   int64 //桶的容量
  tokens     int64 //桶中当前token数量
  lastTokenSec int64 //桶上次放token的时间戳 s
  lock sync.Mutex
}
func (l *TokenBucket) Allow() bool {
  l.lock.Lock()
  defer l.lock.Unlock()
  now := time.Now().Unix()
  l.tokens = l.tokens + (now-l.lastTokenSec)*l.rate // 先添加令牌
  if l.tokens > l.capacity {
    l.tokens = l.capacity
  }
  l.lastTokenSec = now
  if l.tokens > 0 {
    // 还有令牌，领取令牌
    l.tokens--
    return true
  } else {
    // 没有令牌,则拒绝
    return false
  }
}
func (l *TokenBucket) Set(r, c int64) {
  l.rate = r
  l.capacity = c
  l.tokens = 0
  l.lastTokenSec = time.Now().Unix()
}

   

• 令牌按固定的速率被放入令牌桶中   
  
• 桶中最多存放 B 个令牌，当桶满时，新添加的令牌被丢弃或拒绝   
  
• 如果桶中的令牌不足 N 个，则不会删除令牌，且请求将被限流（丢弃或阻塞等待）