限流

1. 漏桶限流

• 水（请求）先进入到漏桶里，漏桶以一定的速度出水，当水流入速度过大会直接溢出(过多的请求直接抛弃或者降级)，可以看出漏桶算法能强行限制数据的传输速率。

• 对于很多应用场景来说，除了要求能够限制数据的平均传输速率外，还要求允许某种程度的突发传输。这时候漏桶算法可能就不合适了，令牌桶算法更为适合。如图2所示，令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌，而如果请求需要被处理，则需要先从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务。

2. 令牌桶限流

类库 time/rate (rate:速率)

• 令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌，而如果请求需要被处理，则需要先从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务或降级。

  

3. 漏桶和令牌桶的区别

1. 漏桶限流是匀速的, 而令牌桶可以添加缓冲区,令牌桶同样可以做到匀速
2. 对于很多应用场景来说，除了要求能够限制数据的平均传输速率外，还要求允许某种程度的突发传输。这时候漏桶算法可能就不合适了，令牌桶算法更为适合。
3. 一般限流都是通过令牌桶限流

time/rate

1. 简单使用

• 构造限流器

  limiter := rate.NewLimiter(limit, burst)

  • 第一个参数是 r Limit。代表每秒可以向 Token 桶中产生多少 token。Limit 实际上是 float64 的别名。
  • 第二个参数是 b int。b 代表 Token 桶的容量大小

• Wait/WaitN 获取不到等待

  • Wait 实际上就是 WaitN(ctx,1)

  • 当使用 Wait 方法消费 Token 时，如果此时桶内 Token 数组不足 (小于 N)，那么 Wait 方法将会阻塞一段时间，直至 Token 满足条件。如果充足则直接返回。

  • Wait 方法有一个 context 参数, 可以设置 context 的 Deadline 或者 Timeout，来决定此次 Wait 的最长时间。

• Allow/AllowN 判断当前是否可以取到token

  • Allow 实际上就是 AllowN(time.Now(),1)。
  • AllowN 方法表示，截止到某一时刻，目前桶中数目是否至少为 n 个，满足则返回 true，同时从桶中消费 n 个 token。 反之返回不消费 Token，false。

• Reserve/ReserveN 返回等待时间(预估), 再去取token

  • Reserve 相当于 ReserveN(time.Now(), 1)
  • ReserveN 的用法就相对来说复杂一些，当调用完成后，无论 Token 是否充足，都会返回一个 Reservation * 对象。
  • 可以调用该对象的 Delay() 方法，该方法返回了需要等待的时间。如果等待时间为 0，则说明不用等待。 必须等到等待时间之后，才能进行接下来的工作。
  • 或者，如果不想等待，可以调用 Cancel() 方法，该方法会将 Token 归还。

	/*
 * @date: 2021/12/9
 * @desc: ...
 */

package main

import (
	"context"
	"golang.org/x/time/rate"
	"log"
	"testing"
	"time"
)

func TestRateLimiter(t *testing.T) {
	l := rate.NewLimiter(1, 5)
	log.Println(l.Limit(), l.Burst())
	for i := 0; i < 100; i++ {
		//阻塞等待直到，取到一个token
		log.Println("before Wait")
		c, _ := context.WithTimeout(context.Background(), time.Second*2)
		if err := l.Wait(c); err != nil {
			log.Println("limiter wait err:" + err.Error())
		}
		log.Println("after Wait")

		// 返回需要等待多久才有新的token,这样就可以等待指定时间执行任务
		r := l.Reserve()
		log.Println("reserve Delay:", r.Delay())

		//判断当前是否可以取到token
		a := l.Allow()
		log.Println("Allow:", a)
	}
}

/*
2021/12/09 16:59:59 1 5
2021/12/09 16:59:59 before Wait     // 第一次请求
2021/12/09 16:59:59 after Wait     
2021/12/09 16:59:59 reserve Delay: 0s  // 第二次请求
2021/12/09 16:59:59 Allow: true       //3请求
2021/12/09 16:59:59 before Wait       // 4
2021/12/09 16:59:59 after Wait      
2021/12/09 16:59:59 reserve Delay: 0s  // 5
2021/12/09 16:59:59 Allow: false       // 6
2021/12/09 16:59:59 before Wait        //7
... //..
*/

2. 动态调整速率

1. SetLimit(Limit) 改变放入 Token 的速率
2. SetBurst(int) 改变 Token 桶大小

实现原理

• Token的消费方式有三种。但其实在内部实现，最终三种消费方式都调用了reserveN函数来生成和消费Token。

• 我们看下reserveN函数的具体实现，整个过程非常简单。在正式讲之前，我们先了解一个简单的概念：

  • 在time/rate中，NewLimiter的第一个参数是速率limit，代表了一秒钟可以产生多少Token。 那么简单换算一下，我们就可以知道一个Token的生成间隔是多少。

  • 有了这个生成间隔，我们就可以轻易地得到两个数据： **1. 生成N个新的Token一共需要多久。**time/rate中对应的实现函数 durationFromTokens **2. 给定一段时长，这段时间一共可以生成多少个Token。**time/rate中对应的实现函数为tokensFromDuration

• reserveN实现过程如下：

  1. 计算从上次取Token的时间到当前时刻，期间一共新产生了多少Token：

     • 我们只在取Token之前生成新的Token，也就意味着每次取Token的间隔，实际上也是生成Token的间隔。我们可以利用tokensFromDuration, 轻易的算出这段时间一共产生Token的数目。 那么，当前Token数目 = 新产生的Token数目 + 之前剩余的Token数目 - 要消费的Token数目。

  2. 如果消费后剩余Token数目大于零，说明此时Token桶内仍不为空，此时Token充足，无需调用侧等待。 如果Token数目小于零，则需等待一段时间。 那么这个时候，我们可以利用durationFromTokens将当前负值的Token数转化为需要等待的时间。

  3. 将需要等待的时间等相关结果返回给调用方。

     • 从上面可以看出，其实整个过程就是利用了Token数可以和时间相互转化的原理。 而如果Token数为负，则需要等待相关时间即可。

     • **注意：**如果当消费时，Token桶中的Token数目已经为负值了，依然可以按照上述流程进行消费。随着负值越来越小，等待的时间将会越来越长。 从结果来看，这个行为跟用Timer+BlockQueue实现是一样的。

     • 此外，整个过程为了保证线程安全，更新令牌桶相关数据时都用了mutex加锁。

• 我们模拟下请求与Token数变化的关系：

  1. 当某一时间，桶内Token数为3, 此时A线程请求5个Token。那么此时桶内Token不足，因此A线程需要等待2个Token的时间。且此时桶内Token数变为-2。
  2. 同时，B线程请求4个Token，此时桶内Token数为-2，因此B线程需要等待2+4=6个Token的时间，且此时桶内Token数变为-6。

• 对于Allow函数实现时，只要判断需要等待的时间是否为0即可，如果大于0说明需要等待，则返回False，反之返回True。

• 对于Wait函数，直接t := time.NewTimer(delay)，等待对应的时间即可。

参考: https://www.cyhone.com/articles/analisys-of-golang-rate/