您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

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

时间:2020-09-17 10:01:27  来源:  作者:

以下文章来源于李文周 ,作者李文周

限流

限流又称为流量控制(流控),通常是指限制到达系统的并发请求数。

我们生活中也会经常遇到限流的场景,比如:某景区限制每日进入景区的游客数量为 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
}

上面的代码根据记录每次请求的间隔时间和上一次请求的时刻来计算当次请求需要阻塞的时间——sleepFor,这里需要留意的是sleepFor的值可能为负,在经过间隔时间长的两次访问之后会导致随后大量的请求被放行,所以代码中针对这个场景有专门的优化处理。maxSlack默认值可以通过创建限制器的New函数看到。

func New(rate int, opts ...Option) Limiter {
 l := &limiter{  perRequest: time.Second / time.Duration(rate),  maxSlack:   -10 * time.Second / time.Duration(rate),
 } for _, opt := range opts {
  opt(l) } if l.clock == nil {
  l.clock = clock.New() } return l
}

令牌桶

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

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

 

令牌桶原理

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

对于令牌桶的 Go 语言实现,大家可以参照https://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时间取tokenfunc (tb *Bucket) TakeMaxDuration(count int64, maxWait time.Duration) (time.Duration, bool)
// 阻塞的取tokenfunc (tb *Bucket) Wait(count int64)func (tb *Bucket) WaitMaxDuration(count int64, maxWait time.Duration) bool

虽说是令牌桶,但是我们没有必要真的去生成令牌放到桶里,我们只需要每次来取令牌的时候计算一下,当前是否有足够的令牌可以使用就可以了,具体的计算公式如下。

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

github.com/juju/ratelimit这个库中关于令牌数计算的具体实现如下:

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) {
  // 如果取不到令牌就返回响应  if bucket.TakeAvailable(1) == 0 {
   c.String(http.StatusOK, "rate limit...")
   c.Abort()
   return  }  c.Next()
 }}

对于该限流中间件的注册位置,我们可以按照不同的限流策略将其添加到不同的地方,例如:

  1. 如果要对全站限流就可以添加成全局的中间件。
  2. 如果是某一组路由需要限流,那么就只需添加到对应的路由组即可。


Tags:令牌桶限流算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,不构成投资建议。投资者据此操作,风险自担。如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除。
▌相关推荐
漏桶、令牌桶限流算法的Go语言实现
限流又称为流量控制(流控),通常是指限制到达系统的并发请求数。我们生活中也会经常遇到限流的场景,比如:某景区限制每日进入景区的游客数量为 8 万人;沙河地铁站早高峰通过站外排队逐一放行的方式限制同一时间进入车站的旅...【详细内容】
2020-09-17  Tags: 令牌桶限流算法  点击:(339)  评论:(0)  加入收藏
▌简易百科推荐
运动规划之搜索算法:前端规划、后端轨迹生成到状态求解
背景:16-18年做过一阵子无人驾驶,那时候痴迷于移动规划;然而当时可学习的资料非常少,网上的论文也不算太多。基本就是Darpa的几十篇无人越野几次比赛的文章,基本没有成系统的文章...【详细内容】
2023-11-30  自动驾驶之心  微信公众号  Tags:算法   点击:(12)  评论:(0)  加入收藏
聊聊常见的限流算法有哪些?
前言今天来分享一道比较好的面试题,“常见的限流算法有哪些?”对于这个问题,我们一起看看考察点和比较好的回答吧! 考察点限流算法是一种用于限制流量请求的频率或速率的算法,其...【详细内容】
2023-11-28  程序员的故事  微信公众号  Tags:算法   点击:(19)  评论:(0)  加入收藏
业务模型 VS 算法模型,到底该怎么用?
提到数据,就必须提到各种模型。小伙伴们经常有疑惑:从4P、SWOT、RFM到线性回归、决策数、Kmean聚类,都有人管它们叫模型,那这些模型到底有啥区别?今天一文讲清,大家看完再也不迷路...【详细内容】
2023-11-27  接地气的陈老师  微信公众号  Tags:算法   点击:(15)  评论:(0)  加入收藏
哈希表底层算法与哈希值计算方法的选择与比较
哈希表是一种常用的数据结构,用于高效地存储和查找数据。在哈希表中,每个元素都有一个对应的键和值,通过计算键的哈希值,将其映射到数组的特定位置上。哈希值的计算是哈希表的关...【详细内容】
2023-11-27  王建立    Tags:算法   点击:(28)  评论:(0)  加入收藏
内部人担忧“威胁人类生存”!OpenAI的神秘重大突破“Q*算法”究竟是什么?
 据报道,Q*可能具备GPT-4所不具备的基础数学能力,或意味着与人类智能相媲美的推理能力,网友推测,这可能代表OpenAI朝着其设定的AGI目标迈出了一大步。  随着OpenAI CEO奥特曼...【详细内容】
2023-11-24    华尔街见闻  Tags:Q*算法   点击:(44)  评论:(0)  加入收藏
无监督学习中的聚类算法综述
无监督学习是机器学习领域中的一个重要分支,其目标是从未标记的数据中发现隐藏的模式和结构。聚类算法作为无监督学习的核心方法之一,被广泛应用于数据分析、模式识别和信息检...【详细内容】
2023-11-24  毛晓峰    Tags:算法   点击:(31)  评论:(0)  加入收藏
揭秘 Linux 调度策略与 CFS 调度算法:解锁内核的奥秘
引言在当今计算机领域,Linux操作系统扮演着至关重要的角色,而其中的调度策略和内核结构体更是它多任务处理的核心。本文将引领你深入探索Linux中的调度策略,理解不同策略如何影...【详细内容】
2023-11-23  囧囧妹  微信公众号  Tags:算法   点击:(34)  评论:(0)  加入收藏
遗传算法在优化问题求解中的应用研究
优化问题是在众多可能解中寻找最优解的问题,而遗传算法是一种模拟生物进化过程的优化算法。遗传算法通过模拟自然选择、交叉和变异等过程,不断优化解的质量。本文将探讨遗传算...【详细内容】
2023-11-21  一曲一场叹家    Tags:遗传算法   点击:(25)  评论:(0)  加入收藏
无监督聚类算法在数据挖掘中的新突破
数据挖掘作为一种从大规模数据中提取有用信息的技术,已经在各个领域中得到广泛应用。而无监督聚类算法作为数据挖掘的重要工具之一,近年来在新的突破方面取得了显著进展。本文...【详细内容】
2023-11-21  无心生活    Tags:聚类算法   点击:(28)  评论:(0)  加入收藏
聚类算法在大规模数据分析中的效果评估
在大规模数据分析中,聚类算法是一种常用的数据挖掘技术,用于将数据集划分为具有相似特征的群组。然而,对于大规模数据集,评估聚类算法的效果变得尤为重要。本文将探讨聚类算法在...【详细内容】
2023-11-21  职场小达人欢晓    Tags:聚类算法   点击:(31)  评论:(0)  加入收藏
相关文章
    无相关信息
站内最新
站内热门
站内头条