江苏龙网

  1. 主页 > 生活百科 > >

漏桶、令牌桶限流算法的Go语言实现

以下文章来源于李文周，作者李文周
限流限流又称为流量控制（流控），通常是指限制到达系统的并发请求数 。
【漏桶、令牌桶限流算法的Go语言实现】我们生活中也会经常遇到限流的场景，比如：某景区限制每日进入景区的游客数量为 8 万人；沙河地铁站早高峰通过站外排队逐一放行的方式限制同一时间进入车站的旅客数量等 。
限流虽然会影响部分用户的使用体验，但是却能在一定程度上保障系统的稳定性，不至于崩溃（大家都没了用户体验） 。
而互联网上类似需要限流的业务场景也有很多，比如电商系统的秒杀、微博上突发热点新闻、双十一购物节、12306 抢票等等 。这些场景下的用户请求量通常会激增，远远超过平时正常的请求量，此时如果不加任何限制很容易就会将后端服务打垮，影响服务的稳定性 。
此外，一些厂商公开的 API 服务通常也会限制用户的请求次数，比如百度地图开放平台等会根据用户的付费情况来限制用户的请求数等 。
漏桶、令牌桶限流算法的Go语言实现

文章插图
 
常用的限流策略漏桶漏桶法限流很好理解，假设我们有一个水桶按固定的速率向下方滴落一滴水，无论有多少请求，请求的速率有多大，都按照固定的速率流出，对应到系统中就是按照固定的速率处理请求 。
漏桶、令牌桶限流算法的Go语言实现

文章插图
 
漏桶算法原理
漏桶法的关键点在于漏桶始终按照固定的速率运行，但是它并不能很好的处理有大量突发请求的场景，毕竟在某些场景下我们可能需要提高系统的处理效率，而不是一味的按照固定速率处理请求 。
关于漏桶的实现，uber 团队有一个开源的https://github.com/uber-go/ratelimit实现 。使用方法也比较简单，Take() 方法会返回漏桶下一次滴水的时间 。
import ( "fmt" "time" "go.uber.org/ratelimit")func main() {    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}它的源码实现也比较简单，这里大致说一下关键的地方，有兴趣的同学可以自己去看一下完整的源码 。
限制器是一个接口类型，其要求实现一个Take()方法：
type Limiter interface { // Take方法应该阻塞已确保满足 RPS Take() time.Time}实现限制器接口的结构体定义如下，这里可以重点留意下maxSlack字段，它在后面的Take()方法中的处理 。
type limiter struct { sync.Mutex                // 锁 last       time.Time      // 上一次的时刻 sleepFor   time.Duration  // 需要等待的时间 perRequest time.Duration  // 每次的时间间隔 maxSlack   time.Duration  // 最大的富余量 clock      Clock          // 时钟}limiter结构体实现Limiter接口的Take()方法内容如下：
// Take 会阻塞确保两次请求之间的时间走完// Take 调用平均数为 time.Second/rate.func (t *limiter) Take() time.Time { t.Lock() defer t.Unlock() now := t.clock.Now() // 如果是第一次请求就直接放行 if t.last.IsZero() {  t.last = now  return t.last } // sleepFor 根据 perRequest 和上一次请求的时刻计算应该sleep的时间 // 由于每次请求间隔的时间可能会超过perRequest, 所以这个数字可能为负数，并在多个请求之间累加 t.sleepFor += t.perRequest - now.Sub(t.last) // 我们不应该让sleepFor负的太多，因为这意味着一个服务在短时间内慢了很多随后会得到更高的RPS 。 if t.sleepFor < t.maxSlack {  t.sleepFor = t.maxSlack } // 如果 sleepFor 是正值那么就 sleep if t.sleepFor > 0 {  t.clock.Sleep(t.sleepFor)  t.last = now.Add(t.sleepFor)  t.sleepFor = 0 } else {  t.last = now } return t.last}


推荐阅读


上一篇：理解卷积神经网络中的自注意力机制

下一篇：微软提交补丁，用Linux替代Hyper-V根分区的Win