令牌桶限流算法 Go语言

1. 限流

限流又称为流量控制（流控），通常是指限制到达系统的并发请求数。

我们生活中也会经常遇到限流的场景，比如：某景区限制每日进入景区的游客数量为8万人；地铁站早高峰限制同一时间进入车站的旅客数量等。

限流虽然会影响部分用户的使用体验，但是却能在一定程度上报障系统的稳定性，不至于崩溃。

互联网上类似需要限流的业务场景也有很多，比如电商系统的秒杀、微博上突发热点新闻、双十一购物节、12306抢票等等。这些场景下的用户请求量通常会激增，远远超过平时正常的请求量，此时如果不加任何限制很容易就会将后端服务打垮，影响服务的稳定性。

此外，一些厂商公开的API服务通常也会限制用户的请求次数，比如百度地图开放平台等会根据用户的付费情况来限制用户的请求数等。

2. 漏桶算法

微服务中常用的服务限流策略：漏桶、令牌桶。

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

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

对于令牌桶的Go语言实现，大家可以参照 github.com/juju/ratelimit 库。这个库支持多种令牌桶模式，并且使用起来也比较简单。

创建令牌桶的方法：

// 创建指定填充速率和容量大小的令牌桶
func NewBucket(fillInterval time.Duration, capacity int64) *Bucket
// 创建指定填充速率、容量大小和每次填充的令牌数的令牌桶
func NewBucketWithQuantum(fillInterval time.Duration, capacity, quantum int64) *Bucket
// 创建填充速度为指定速率和容量大小的令牌桶
// NewBucketWithRate(0.1, 200) 表示每秒填充20个令牌
func NewBucketWithRate(rate float64, capacity int64) *Bucket

取出令牌的方法如下：

// 取token（非阻塞）
func (tb *Bucket) Take(count int64) time.Duration
func (tb *Bucket) TakeAvailable(count int64) int64

// 最多等maxWait时间取token
func (tb *Bucket) TakeMaxDuration(count int64, maxWait time.Duration) (time.Duration, bool)

// 取token（阻塞）
func (tb *Bucket) Wait(count int64)
func (tb *Bucket) WaitMaxDuration(count int64, maxWait time.Duration) bool

虽说是令牌桶，但是我们没有必要真的去生成令牌放到桶里，我们只需要每次来取令牌的时候计算一下，当前是否有足够的令牌就可以了，具体的计算方式可以总结为下面的公式：

当前令牌数 = 上一次剩余的令牌数 + (本次取令牌的时刻-上一次取令牌的时刻)/放置令牌的时间间隔 * 每次放置的令牌数

github.com/juju/ratelimit 这个库中关于令牌数计算的源代码如下：

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

func (tb *Bucket) adjustavailableTokens(tick int64) {
 if tb.availableTokens >= tb.capacity {
  return
 }
 tb.availableTokens += (tick - tb.latestTick) * tb.quantum
 if tb.availableTokens > tb.capacity {
  tb.availableTokens = tb.capacity
 }
 tb.latestTick = tick
 return
}

获取令牌的TakeAvailable()函数关键部分的源代码如下：

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
}

大家从代码中也可以看到其实令牌桶的实现并没有很复杂。

gin 框架使用限流中间件

在gin框架构建的项目中，我们可以将限流组件定义成中间件。

这里使用令牌桶作为限流策略，编写一个限流中间件如下：

func RateLimitMiddleware(fillInterval time.Duration, cap int64) func(c *gin.Context) {
 bucket := ratelimit.NewBucket(fillInterval, cap)
 return func(c *gin.Context) {
  // 如果取不到令牌就中断本次请求返回 rate limit...
  if bucket.TakeAvailable(1) < 1 {
   c.String(http.StatusOK, "rate limit...")
   c.Abort()
   return
  }
  c.Next()
 }
}

对于该限流中间件的注册位置，我们可以按照不同的限流策略将其注册到不同的位置，例如：

• 如果要对全站限流就可以注册成全局的中间件。
• 如果是某一组路由需要限流，那么就只需将该限流中间件注册到对应的路由组即可。