golang官方限流器rate包实践

日常开发中，对于某些接口有请求频率的限制。比如登录的接口、发送短信的接口、秒杀商品的接口等等。

官方的golang.org/x/time/rate包中实现了令牌桶的算法。

封装限流器可以将ip、手机号这种的作为限流器组的标识。

接下来就是实例化限流器和获取令牌函数的实现

package limiter

//component/limiter/limiter.go

import (

    "sync"

    "time"

    "golang.org/x/time/rate"

)

type Limiters struct {

    limiters map[string]*Limiter

    lock     sync.Mutex

}

type Limiter struct {

    limiter *rate.Limiter

    lastGet time.Time //上一次获取token的时间

    key     string

}

var GlobalLimiters = &Limiters{

    limiters: make(map[string]*Limiter),

    lock:     sync.Mutex{},

}

var once = sync.Once{}

func NewLimiter(r rate.Limit, b int, key string) *Limiter {

    once.Do(func() {

        go GlobalLimiters.clearLimiter()

    })

    keyLimiter := GlobalLimiters.getLimiter(r, b, key)

    return keyLimiter

}

func (l *Limiter) Allow() bool {

    l.lastGet = time.Now()

    return l.limiter.Allow()

}

func (ls *Limiters) getLimiter(r rate.Limit, b int, key string) *Limiter {

    ls.lock.Lock()

    defer ls.lock.Unlock()

    limiter, ok := ls.limiters[key]

    if ok {

        return limiter

    }

    l := &Limiter{

        limiter: rate.NewLimiter(r, b),

        lastGet: time.Now(),

        key:     key,

    }

    ls.limiters[key] = l

    return l

}

// 清除过期的限流器

func (ls *Limiters) clearLimiter() {

    for {

        time.Sleep(1 * time.Minute)

        ls.lock.Lock()

        for i, i2 := range ls.limiters {

            //超过1分钟

            if time.Now().Unix()-i2.lastGet.Unix() > 60 {

                delete(ls.limiters, i)

            }

        }

        ls.lock.Unlock()

    }

}

main.go结合gin框架实践：

package main

import (

    "gin/component/limiter"

    "time"

    "github.com/gin-gonic/gin"

    "golang.org/x/time/rate"

)

func main() {

    r := gin.Default()

    r.GET("/ceshi", Ceshi)

    r.Run(":8080")

}

func Ceshi(ctx *gin.Context) {

    l := limiter.NewLimiter(rate.Every(1*time.Second), 1, ctx.ClientIP())

    if !l.Allow() {

        ctx.JSON(400, "请求过于频繁")

        return

    }

    ctx.JSON(200, "请求正常")

}

/**************************************************/

一. 限流与time/rate基础
golang内部基于令牌桶算法提供了一个限流器time/rate位于golang.org/x/time/rate
在golang中,可以使用channel或者使用time/rate包实现并发控制, time/rate包是一个提供令牌桶算法的包，它可以实现对事件发生的速率进行限制和平滑,使用time/rate控制并发比使用channel控制并发的优点在于
time/rate只需要调用NewLimiter()函数,设置并发限制规则创建Limiter对象，然后在每个goroutine中调用Wait或者Allow方法来获取令牌即可,简单方便,channel需要创建一个缓冲区,然后在每个goroutine中通过向channel的缓冲区存放或获取数据来控制并发
time/rate可以更灵活地控制并发的速率,可以根据令牌桶的容量和填充速度来调整并发的上限和平均值,而channel只能根据缓冲区的大小来控制并发的上限,不能控制平均值
time/rate可以更容易地处理并发的异常情况，例如超时或者取消:提供了WaitN、Reserve、Context等方法来支持超时或者取消的场景,而channel需要额外的逻辑来处理超时或者取消，例如使用select语句或者context包
WaitN方法和Reserve方法都可以获取n个令牌,它们以后什么不同
WaitN方法会阻塞当前goroutine,直到获取到n个令牌,或者超时或者取消,它接收一个context参数,用于控制超时或者取消的行为,如果获取成功,它会返回nil,否则返回一个错误
Reserve方法会预定n个令牌,返回一个Reservation对象用于表示预定的结果,Reservation对象提供了Delay方法,用于获取预定的延迟时间,以及Cancel方法用于取消预定。如果预定成功它会返回一个非nil的Reservation对象否则返回nil
一般来说如果想要同步地等待令牌,或者不关心延迟时间,你可以使用WaitN方法,如果想要异步地等待令牌,或者想要知道延迟时间,你可以使用Reserve方法
time/rate常用的API概述:
NewLimiter(r Limit, b int) *Limiter: 创建一个新的限流器，r表示每秒可以向令牌桶中产生多少令牌，b表示最大容量
Limit() Limit: 返回限流器的最大事件频率
Burst() int: 返回限流器的最大突发大小,即一次可以消费的最大令牌数1
Allow() bool: 相当于AllowN(time.Now(), 1),表示是否可以消费一个令牌,可以返回true并消费一个令牌
AllowN(t time.Time, n int) bool: 表示是否可以消费n个令牌,可以则返回true并消费n个令牌
Reserve() Reservation: 相当于ReserveN(time.Now(), 1),表示预订一个令牌,并返回一个Reservation对象,该对象可以用来获取需要等待的时间或者取消预订
ReserveN(t time.Time, n int) Reservation: 表示预订n个令牌,并返回一个Reservation对象
Wait(ctx context.Context) (err error): 相当于WaitN(ctx, 1),表示等待直到可以消费一个令牌,或者通过ctx被取消
WaitN(ctx context.Context, n int) (err error): 表示等待直到可以消费n个令牌,或者通过ctx被取消
预订的令牌时,返回的Reservation结构体上常用的API:
Cancel(): 取消预订,将令牌归还给限流器
CancelAt(t time.Time): 在指定的时间取消预订,将令牌归还给限流器
Delay(): 返回需要等待的时间,相当于DelayFrom(time.Now())
DelayFrom(t time.Time): 返回从指定的时间开始需要等待的时间
OK()：返回预订是否有效,如果预订的令牌数超过了限流器的突发大小(也就是最大个数),预定无效返回false
time/rate基础使用示例
import (
    "context"
    "fmt"
    "github.com/gin-gonic/gin"
    "golang.org/x/time/rate"
    "log"
    "time"
)

func main() {
    //1.初始化 limiter 每秒10个令牌，令牌桶容量为20
    //第一个参数r Limit代表每秒可以向桶中产生多少令牌,Limit 实际上是 float64 的别名
    //第二个参数b int代表桶的容量大小,当前为20,如果桶中有20个令牌,
    //可以立即获取20个令牌,不需要等待直接执行,也就是最大并发数
    limiter := rate.NewLimiter(rate.Every(time.Millisecond*100), 20)

    //2.获取1个令牌,获取到返回true,否则false
    bo := limiter.Allow()
    if bo {
        fmt.Println("获取令牌成功")
    }

    //2.获取指定时间内指定个数令牌,获取到返回true,
    //实际上方的Allow()内部调用的就是AllowN()
    limiter.AllowN(time.Now(), 2)

    //3.阻塞直到获取足够的令牌或者上下文取消
    ctx, _ := context.WithTimeout(context.Background(), time.Second*10)
    limiter.Wait(ctx)
    err := limiter.WaitN(ctx, 20)
    if err != nil {
        fmt.Println("error", err)
    }

    //4.可以理解为预定一个令牌,当调用Reserve后不管是否存在有效令牌都会返回一个Reservation指针对象
    //接下来可以通过返回的Reservation进行指定操作
    reservation := limiter.Reserve()
    if 0 == reservation.Delay() {
        fmt.Println("获取令牌成功")
    }

    //5.指定实际内预定指定个数令牌
    //上面Reserve()内部实际就是调用的ReserveN()
    limiter.ReserveN(time.Now(), 1)

    //6.修改令牌生成速率
    limiter.SetLimit(rate.Every(time.Millisecond * 100))
    limiter.SetLimitAt(time.Now(), rate.Every(time.Millisecond*100))

    //7.修改令牌桶大小,也就是生成令牌的最大数量限制
    limiter.SetBurst(50)
    limiter.SetBurstAt(time.Now(), 50)

    //8.获取限流的速率即结构体中limit的值,每秒允许处理的事件数量,即每秒处理事件的频率
    l := limiter.Limit()
    fmt.Printf("每秒允许处理的事件数量,即每秒处理事件的频率为: %v", l)
    //9.返回桶的最大容量
    limiter.Burst()
}

WaitN实现超时取消示例
time/rate基于WaitN方法实现超时控制:限制每秒只允许10个请求,最大允许请求数为20,当超过20个后,超过部分等待30秒,如果30秒还获取不到则拒绝,示例中写明中文注释,写明哪里是拒绝执行的,哪里是放行执行的
package main

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

func main() {
    // 创建一个每秒允许10个请求，最大允许请求数为20的限速器
    limiter := rate.NewLimiter(10, 20)
    // 模拟100个请求
    for i := 0; i < 100; i++ {
        // 创建一个带有30秒超时时间的context
        ctx, cancel := context.WithTimeout(context.Background(), 30*time.Second)
        defer cancel()
        // 等待获取一个令牌,(如果当前获取的令牌数超过了最大限制,或者通过context超时取消了,返回错误)
        err := limiter.WaitN(ctx, 1)
        if err != nil {
            // 处理错误，表示拒绝执行
            fmt.Println(i, "rejected:", err) 
            continue
        }
        // 没有错误，表示放行执行
        fmt.Println(i, "accepted")
    }
}

time/rate基于WaitN方法实现超时控制:
限制每秒只允许10个请求,最大允许请求数为20,
当请求超过20个后,判断当前是否有正在阻塞等待的请求,如果有判断阻塞等待的请求数是否超过5个,如果阻塞等待请求超过5个直接拒绝请求
如果没有阻塞等待请求,或者阻塞等待请求没有超过5个,阻塞等待30秒,如果30秒未执行,响应超时
package main

import (
    "context"
    "fmt"
    "golang.org/x/time/rate"
    "sync/atomic"
    "time"
)

func main() {
    // 创建一个每秒允许10个请求，最大允许请求数为20的限速器
    limiter := rate.NewLimiter(10, 20)
    // 创建一个原子计数器，用于记录阻塞等待的请求数
    var waiting int64 = 0
    // 模拟100个请求
    for i := 0; i < 100; i++ {

        if atomic.LoadInt64(&waiting) > 5 {
            // 如果阻塞等待的请求数超过5个，直接拒绝执行
            fmt.Println(i, "rejected: too many waiting requests") 
            continue
        }
        // 增加计数器
        atomic.AddInt64(&waiting, 1)
        
        // 创建一个带有30秒超时时间的context
        ctx, cancel := context.WithTimeout(context.Background(), 30*time.Second)
        defer cancel()
        
        // 尝试获取一个令牌，(如果当前获取的令牌数超过了最大限制,或者通过context超时取消了,返回错误)
        err := limiter.WaitN(ctx, 1)
        if err != nil {
            // 处理错误，表示拒绝执行
            fmt.Println(i, "rejected:", err)
            continue
        }
        //当获取到令牌,减少计数器(获取到令牌就累减计数器,总觉得有点问题)
        atomic.AddInt64(&waiting, -1)
        // 没有错误，表示放行执行
        fmt.Println(i, "accepted") 
    }
}

ReserveN预定令牌示例
在执行Limiter下的Reserve()或ReserveN()方法时会返回一个Reservation,Reservation下的方法使用示例,注意ReserveN只能预订最大限制以内的,如果ReserveN预定数量超过了最大限制
func test() {
    //1.初始化 limiter 每秒10个令牌，令牌桶容量为20
    limiter := rate.NewLimiter(rate.Every(time.Millisecond*100), 20)

    //2.可以理解为预定一个令牌,当调用Reserve后不管是否存在有效令牌都会返回一个Reservation指针对象
    //接下来可以通过返回的Reservation进行指定操作
    reservation := limiter.Reserve()
    if !reservation .OK() {
        // 预定失败，表示超过了最大突发数
    }

    //获取到Reservation后

    //3.Delay():如果ReserveN预订超过最大限制,Delay()方法会返回一个非零的值
    //返回需要阻塞等待多长时间才能拿到令牌,如果为0说明不用阻塞等待
    if 0 == reservation.Delay() {
        fmt.Println("获取令牌成功")
    }

    //4.上面Delay()内部就是调用的该方法,如果返回0，表示有足够的令牌,
    //如果返回InfDuration，表示到截至时间时仍然没有足够的令牌
    reservation.DelayFrom(time.Now())

    //5.返回限流器limiter是否可以在最大等待时间内提供请求数量的令牌。
    //如果Ok为false，则Delay返回InfDuration，Cancel不执行任何操作
    if reservation.OK() {
        fmt.Println("获取令牌成功")
    }

    //6.用于取消预约令牌操作,如果有需要还原的令牌,
    //则将需要还原的令牌重新放入到令牌桶中,注意并不是无脑还原
    reservation.Cancel()
    //上方的Cancel()内部就是调用的CancelAt()这个方法
    reservation.CancelAt(time.Now())
}

使用示例
需求: 根据调用服务或者接口限流
指定服务或接口有限流要求,获取到限流规则
编写限流逻辑,创建限流结构,限流容器,获取限流limit方法
提供限流中间件,获取到请求后获取限流limit,如果超出阈值熔断
限流逻辑
import (
    "golang.org/x/time/rate"
    "sync"
)

// 1.针对服务(或者针对接口)限流,封装限流结构
type FlowLimiterItem struct {
    ServiceName string        //需要限流的服务或接口标识
    Limter      *rate.Limiter //限流limit
}

// 1.封装限流容器(不同服务或者不同接口的限流上下文存储到该容器中)
type FlowLimiter struct {
    FlowLmiterMap   map[string]*FlowLimiterItem
    FlowLmiterSlice []*FlowLimiterItem
    Locker          sync.RWMutex
}

// 3.提供初始化限流容器函数
func NewFlowLimiter() *FlowLimiter {
    return &FlowLimiter{
        FlowLmiterMap:   map[string]*FlowLimiterItem{},
        FlowLmiterSlice: []*FlowLimiterItem{},
        Locker:          sync.RWMutex{},
    }
}

//4.服务启动时初始化限流容器
var FlowLimiterHandler *FlowLimiter

func init() {
    FlowLimiterHandler = NewFlowLimiter()
}

//5.获取指定服务或接口限流limit方法
//serverName:服务或接口标识
//qps:该服务或接口限流qps
func (counter *FlowLimiter) GetLimiter(serverName string, qps float64) (*rate.Limiter, error) {

    //1.通过服务或接口标识在限流容器中获取
    for _, item := range counter.FlowLmiterSlice {
        if item.ServiceName == serverName {
            return item.Limter, nil
        }
    }

    //2.如果容器中不存在说明第一次执行,需要创建限流limit
    newLimiter := rate.NewLimiter(rate.Limit(qps), int(qps*3))
    //封装限流结构添加到限流容器中
    item := &FlowLimiterItem{
        ServiceName: serverName,
        Limter:      newLimiter,
    }
    counter.FlowLmiterSlice = append(counter.FlowLmiterSlice, item)
    counter.Locker.Lock()
    defer counter.Locker.Unlock()
    counter.FlowLmiterMap[serverName] = item
    return newLimiter, nil
}

编写限流中间件
import (
    "fmt"
    "github.com/e421083458/go_gateway/dao"
    "github.com/e421083458/go_gateway/middleware"
    "github.com/e421083458/go_gateway/public"
    "github.com/gin-gonic/gin"
    "github.com/pkg/errors"
)

func HTTPFlowLimitMiddleware() gin.HandlerFunc {
    return func(c *gin.Context) {
        //1.获取请求参数
        serverInterface, ok := c.Get("service")
        if !ok {
            middleware.ResponseError(c, 2001, errors.New("service not found"))
            c.Abort()
            return
        }
        //2.根据请求数据拿查询限流配置
        serviceDetail := serverInterface.(*dao.ServiceDetail)

        //3.根据配置判断限流规则
        if serviceDetail.AccessControl.ServiceFlowLimit != 0 {

            //4.获取限流limit
            serviceLimiter, err := public.FlowLimiterHandler.GetLimiter(
                public.FlowServicePrefix+serviceDetail.Info.ServiceName,
                float64(serviceDetail.AccessControl.ServiceFlowLimit))
            if err != nil {
                middleware.ResponseError(c, 5001, err)
                c.Abort()
                return
            }

            //5.判断限流是否超过阈值,超过返回false,进入if进行异常响应
            if !serviceLimiter.Allow() {
                middleware.ResponseError(c, 5002, errors.New(fmt.Sprintf("service flow limit %v", serviceDetail.AccessControl.ServiceFlowLimit)))
                c.Abort()
                return
            }
        }

        if serviceDetail.AccessControl.ClientIPFlowLimit > 0 {
            clientLimiter, err := public.FlowLimiterHandler.GetLimiter(
                public.FlowServicePrefix+serviceDetail.Info.ServiceName+"_"+c.ClientIP(),
                float64(serviceDetail.AccessControl.ClientIPFlowLimit))
            if err != nil {
                middleware.ResponseError(c, 5003, err)
                c.Abort()
                return
            }
            if !clientLimiter.Allow() {
                middleware.ResponseError(c, 5002, errors.New(fmt.Sprintf("%v flow limit %v", c.ClientIP(), serviceDetail.AccessControl.ClientIPFlowLimit)))
                c.Abort()
                return
            }
        }

        //6.中间件放行
        c.Next()
    }
}

该方式也可以再提取出一个针对租户限流的中间件
import (
    "fmt"
    "github.com/e421083458/go_gateway/dao"
    "github.com/e421083458/go_gateway/middleware"
    "github.com/e421083458/go_gateway/public"
    "github.com/gin-gonic/gin"
    "github.com/pkg/errors"
)

func HTTPJwtFlowLimitMiddleware() gin.HandlerFunc {
    return func(c *gin.Context) {
        //1.获取请求
        appInterface, ok := c.Get("app")
        if !ok {
            c.Next()
            return
        }
        //2.通过请求查询该app用户下的限流配置
        appInfo := appInterface.(*dao.App)
        //3.判断是否开启限流
        if appInfo.Qps > 0 {
            clientLimiter, err := public.FlowLimiterHandler.GetLimiter(
                public.FlowAppPrefix+appInfo.AppID+"_"+c.ClientIP(),
                float64(appInfo.Qps))
            if err != nil {
                middleware.ResponseError(c, 5001, err)
                c.Abort()
                return
            }
            //4.判断是否到达限流阈值
            if !clientLimiter.Allow() {
                middleware.ResponseError(c, 5002, errors.New(fmt.Sprintf("%v flow limit %v", c.ClientIP(), appInfo.Qps)))
                c.Abort()
                return
            }
        }
        c.Next()
    }
}

二. time/rate 底层原理相关
Limiter 与 Reservation 结构
在调用NewLimiter()创建限流器时会返回一个Limiter结构体变量,查看内部组成:
type Limiter struct {
    //每秒允许处理的事件数量,即每秒处理事件的频率
    limit Limit  
    //令牌桶的最大数量,如果burst为0,则除非limit == Inf,否则不允许处理任何事件
    burst int   

    mu     sync.Mutex
    //令牌桶中可用的令牌数量
    tokens float64  
    //记录上次limiter的tokens被更新的时间
    last time.Time
    //lastEvent记录速率受限制(桶中没有令牌)的时间点,该时间点可能是过去的
    //也可能是将来的(Reservation预定的结束时间点)
    //如果没有预约令牌的话,该时间等于last，是过去的
    //如果有预约令牌的话,该时间等于最新的预约的截至时间
    lastEvent time.Time  
}

当调用Reserve()预定令牌时,会返回一个Reservation结构体变量
type Reservation struct {
    //到截止时间是否可以获取足够的令牌
    ok        bool 
    lim       *Limiter
    //需要获取的令牌数量
    tokens    int   
    //需要等待的时间点(本次预约需要等待到的指定时间点才有足够预约的令牌)
    timeToAct time.Time  
    limit Limit
}

消费令牌底层原理
在rate中默认提供了Allow()消费一个令牌,Wait()阻塞等待消费一个令牌, Reserve()预定一个令牌,实际底层对应调用的是WaitN(), AllowN(), ReserveN()消费指定个数令牌的方法
所有消费令牌的方法内部都会调用reserveN和advance方法,reserveN可以理解为预约令牌的逻辑,由于可以预约,当桶中令牌不够时,预定过后桶中令牌有可能为负数
以Allow()消费一个令牌为例,内部会调用AllowN(), AllowN内部会调用reserveN(),reserveN内部会调用advance()
func (lim *Limiter) Allow() bool {
    return lim.AllowN(time.Now(), 1)
}

func (lim *Limiter) AllowN(t time.Time, n int) bool {
    return lim.reserveN(t, n, 0).ok
}

1. reserveN()方法逻辑
reserveN是 AllowN, ReserveN及 WaitN的辅助方法,主要用于判断在maxFutureReserve指定时间内是否有足够的令牌
// @param n 要消费的token数量
// @param maxFutureReserve 愿意等待的最长时间
func (lim *Limiter) reserveN(t time.Time, n int, maxFutureReserve time.Duration) Reservation {
    lim.mu.Lock() //加锁，保证数据的一致性
    defer lim.mu.Unlock() //解锁，释放资源

    if lim.limit == Inf { //如果速率限制是无限的，表示不需要限流
        return Reservation{ //返回一个预约结果，包括是否允许、令牌数、执行时间等信息
            ok:        true, //允许通过
            lim:       lim, //关联的限流器
            tokens:    n, //请求的令牌数
            timeToAct: t, //执行时间为当前时间
        }
    } else if lim.limit == 0 { //如果速率限制是零，表示不允许任何事件
        var ok bool 
        if lim.burst >= n { //如果桶中有足够的令牌，表示可以通过
            ok = true 
            lim.burst -= n //更新桶中的令牌数，减去请求的令牌数
        }
        return Reservation{ //返回一个预约结果，包括是否允许、令牌数、执行时间等信息
            ok:        ok, //是否允许通过
            lim:       lim, //关联的限流器
            tokens:    lim.burst, //桶中剩余的令牌数
            timeToAct: t, //执行时间为当前时间
        }
    }

    t, tokens := lim.advance(t) //根据当前时间和上次更新时间计算桶中剩余的令牌数

    tokens -= float64(n) //计算请求后桶中剩余的令牌数，可能为负数

    var waitDuration time.Duration 
    if tokens < 0 { //如果剩余的令牌数小于零，表示需要等待一段时间才能通过
        waitDuration = lim.limit.durationFromTokens(-tokens) //根据速率限制计算需要等待的时间间隔
    }

    //判断是否允许通过，需要满足两个条件：请求的令牌数不超过桶的容量，等待的时间间隔不超过最大允许的未来预约时间
    ok := n <= lim.burst && waitDuration <= maxFutureReserve 

    r := Reservation{ //准备一个预约结果，包括是否允许、关联的限流器、速率限制等信息
        ok:    ok, 
        lim:   lim, 
        limit: lim.limit, 
    }
    if ok { //如果允许通过，还需要设置以下信息：
        r.tokens = n //请求的令牌数
        r.timeToAct = t.Add(waitDuration) //执行时间为当前时间加上等待时间间隔

        // Update state
        lim.last = t //更新限流器中的上次更新时间为当前时间
        lim.tokens = tokens //更新限流器中的剩余令牌数为请求后的值
        lim.lastEvent = r.timeToAct //更新限流器中的最近事件时间为执行时间
    }
    return r //返回预约结果
}

对reserveN的流程总结
调用NewLimiter()创建限流器时会返回一个Limiter结构体变量,内部存在一个limit每秒允许处理的事件数量,与burst最大通过数量属性
在调用reserveN()消费令牌时,首先会加锁,判断limit是否等于MaxFloat64,如果是说明无限的速率限制桶中一直拥有足够的令牌,直接返回true
如果limit等于0,判断当前获取的令牌数量是否超过了burst最大并发限制,如果超过了返回false,没超过返回true
如果limit不等于MaxFloat64并且不等于0,调用advance()计算当前可以使用的令牌数量,也就是(上次剩余令牌数+上次消费令牌时间到当前时间所生成的令牌,如果大于最大并发限制,的更新为最大并发限制)
如果advance()拿到当前可消费的令牌数量小于0,说明超过并发限制,调用durationFromTokens()计算等待生成令牌时间
封装Reservation,如果当前要消费的令牌数量小于允许可消费的令牌数量则Reservation中的ok为true表示允许消费,否则为false
最后解锁,返回预约结果
2. advance()根据当前时间和上次更新时间计算桶中剩余的令牌数逻辑
该方法的作用是更新令牌桶的状态,计算出令牌桶未更新的时间(elapsed),根据elapsed算出需要向桶中加入的令牌数delta，然后算出桶中可用的令牌数newTokens
func (lim *Limiter) advance(t time.Time) (newT time.Time, newTokens float64) {
    last := lim.last //获取限流器中的上次更新时间
    if t.Before(last) { //如果当前时间早于上次更新时间，表示时间回退了
        last = t //使用当前时间作为上次更新时间
    }

    elapsed := t.Sub(last) //计算当前时间和上次更新时间的差值，单位纳秒
    delta := lim.limit.tokensFromDuration(elapsed) //根据速率限制计算在这段时间内应该增加的令牌数
    tokens := lim.tokens + delta //计算桶中新的令牌数，等于原来的令牌数加上增加的令牌数
    if burst := float64(lim.burst); tokens > burst { //如果新的令牌数超过了桶的容量
        tokens = burst //将新的令牌数设置为桶的容量，即不能超过最大值
    }
    return t, tokens //返回当前时间和新的令牌数
}

3. durationFromTokens()根据令牌数量tokens计算出产生该数量的令牌需要的时长
durationFromTokens()计算出生成N 个新的 Token 一共需要多久
func (limit Limit) durationFromTokens(tokens float64) time.Duration {
    if limit <= 0 { //如果速率限制小于等于零，表示不需要任何时间
        return InfDuration //返回一个无限大的时间间隔
    }
    seconds := tokens / float64(limit) //计算生成令牌数所需的秒数，等于令牌数除以速率限制
    return time.Duration(float64(time.Second) * seconds) //返回对应的时间间隔，单位纳秒
}

4. tokensFromDuration()获取指定期间内产生的令牌数量
tokensFromDuration()给定一段时长,计算这段时间一共可以生成多少个 Token
func (limit Limit) tokensFromDuration(d time.Duration) float64 {
    if limit <= 0 { //如果速率限制小于等于零，表示不生成任何令牌
        return 0
    }
     //返回时间间隔的秒数乘以速率限制，即在这段时间内生成的令牌数
    return d.Seconds() * float64(limit)
}

Wait 阻塞获取令牌
在Wait阻塞消费令牌函数中,首先会封装一个返回定时器通道的函数,然后调用Limiter的wait()方法, 查看该方法:
首先获取到当前限速器配置的最大并发数burst 与limit限流速率,如果当前一次性申请的令牌数超过最大并发数,并且限流速率不是MaxFloat64报错
通过select-case监听context的Done取消,如果取消了返回异常
将Context取消时间,设置为等待时间
通过当前时间, 当前消费令牌数量,通过Context取消时间设置的等待时间,调用reserveN()进行预订
在reserveN()预订令牌方法中,会根据传入的等待时间计算这个时间段内是否存在或可以生产出指定数量的令牌,并且会返回生产这些令牌所需要的时间
如果存在或者可以生产出需要的令牌reserveN()返回的Reservation中ok为true,调用DelayFrom()方法计算获取令牌需要的延迟时间,DelayFrom()返回0说明不需要等待直接返回
DelayFrom()如果返回大于0,执行Wait()函数中封装的返回定时器通道的函数,拿到定时器通道,通过select-case监听Context的Done取消消息和这个定时器通道,当定时器通道返回说明令牌生成完毕函数返回,Wait阻塞开始向下执行
// WaitN 会阻塞当前 goroutine 直到可以获取 n 个令牌，或者 ctx 被取消
// 如果 n 超过了 limiter 的 burst 值，并且 limit 不是 Inf，WaitN 会返回一个错误
// 如果 ctx 已经被取消，WaitN 也会返回一个错误
func (lim *Limiter) WaitN(ctx context.Context, n int) (err error) {
    // 这是真正的定时器生成器
    // newTimer 是一个函数，它接受一个时间间隔 d 作为参数，
    //返回一个定时器的通道，一个停止定时器的函数，和一个空函数(只在测试时有作用)
    newTimer := func(d time.Duration) (<-chan time.Time, func() bool, func()) {
        // 创建一个定时器，它会在 d 时间后发送当前时间到 timer.C 通道
        timer := time.NewTimer(d) 
        // 返回定时器的通道，停止定时器的函数，和空函数
        return timer.C, timer.Stop, func() {} 
    }
    // 调用 lim.wait 方法，传入 ctx, n, 当前时间，和 newTimer 函数
    return lim.wait(ctx, n, time.Now(), newTimer) 
}

// wait 是 WaitN 的内部实现
func (lim *Limiter) wait(ctx context.Context, n int, t time.Time, newTimer func(d time.Duration) (<-chan time.Time, func() bool, func())) error {
    lim.mu.Lock()
    burst := lim.burst // 获取最大并发限制
    limit := lim.limit // 获取限流速率
    lim.mu.Unlock()

    if n > burst && limit != Inf {
        // 如果 n 超过了 burst 值，并且 limit 不是 Inf，返回一个错误
        return fmt.Errorf("rate: Wait(n=%d) exceeds limiter's burst %d", n, burst) 
    }
    // 检查 ctx 是否已经被取消
    select {
    case <-ctx.Done():
        return ctx.Err() // 如果 ctx 已经被取消，返回一个错误
    default:
    }
    // 确定等待限制
    waitLimit := InfDuration // 初始化等待限制为无穷大
    if deadline, ok := ctx.Deadline(); ok {
        // 如果 ctx 有截止时间，等待限制为截止时间减去当前时间
        waitLimit = deadline.Sub(t) 
    }
    // 预约
    // 调用 lim.reserveN 方法，传入当前时间t，n，和等待限制，返回一个预约对象 r
    r := lim.reserveN(t, n, waitLimit) 
    if !r.ok {
        // 如果 r 不 ok，说明预约失败，返回一个错误
        return fmt.Errorf("rate: Wait(n=%d) would exceed context deadline", n) 
    }
    //判断是否需要等待
    delay := r.DelayFrom(t) // 获取 r 的延迟时间
    if delay == 0 {
        return nil // 如果延迟时间为 0直接返回 nil
    }
    // 调用 newTimer 函数，传入延迟时间，返回一个定时器的通道，
    //一个停止定时器的函数，和一个空函数（只在测试时有作用）
    ch, stop, advance := newTimer(delay) 
    defer stop() // 延迟执行停止定时器的函数
    advance() // 只在测试时有作用
    select {
    case <-ch:
        // 如果定时器的通道收到消息，说明延迟时间到了，我们可以继续，返回 nil
        return nil 
    case <-ctx.Done():
        // ctx 被取消了,取消预约
        r.Cancel() 
        return ctx.Err() // 返回 ctx 的错误
    }
}

// DelayFrom 返回 r 的延迟时间，即从 t 到 r.timeToAct 的时间间隔。
// 如果 r 不 ok，说明预约失败，返回无穷大的延迟时间。
// 如果 r.timeToAct 在 t 之前，说明预约已经可以执行，返回 0 的延迟时间。
func (r *Reservation) DelayFrom(t time.Time) time.Duration {
    if !r.ok {
        return InfDuration // 如果 r 不 ok，返回无穷大的延迟时间
    }
    delay := r.timeToAct.Sub(t) // 计算 r.timeToAct 和 t 的时间差，赋值给 delay
    if delay < 0 {
        return 0 // 如果 delay 小于 0，说明 r.timeToAct 在 t 之前，返回 0 的延迟时间
    }
    return delay // 否则，返回 delay
}

CancelAt()取消令牌消费操作
func (r *Reservation) Cancel() {
    r.CancelAt(time.Now())
    return
}
 
func (r *Reservation) CancelAt(t time.Time) {
    //如果预约结果不允许通过，表示没有消耗令牌，无需取消
    if !r.ok { 
        return
    }

    r.lim.mu.Lock() //加锁，保证数据的一致性
    defer r.lim.mu.Unlock() //解锁，释放资源

    //如果速率限制是无限的，或者请求的令牌数是零，或者执行时间早于取消时间，表示无需取消
    if r.lim.limit == Inf || r.tokens == 0 || r.timeToAct.Before(t) { 
        return
    }

    //计算需要恢复的令牌数，等于请求的令牌数减去在预约结果之后被预约的令牌数
    //这里的r.lim.lastEvent可能是本次Reservation的结束时间
    //也可能是后来的Reservation的结束时间
    //所以要把本次结束时间点(r.timeToAct)之后产生的令牌数减去
    restoreTokens := float64(r.tokens) - r.limit.tokensFromDuration(r.lim.lastEvent.Sub(r.timeToAct)) 
    if restoreTokens <= 0 { //如果需要恢复的令牌数小于等于零，表示无需取消
        return
    }
    t, tokens := r.lim.advance(t) //根据当前时间和上次更新时间计算桶中剩余的令牌数

    tokens += restoreTokens //计算桶中新的令牌数，等于原来的令牌数加上恢复的令牌数
    if burst := float64(r.lim.burst); tokens > burst { //如果新的令牌数超过了桶的容量
        tokens = burst //将新的令牌数设置为桶的容量，即不能超过最大值
    }
    // update state
    r.lim.last = t //更新限流器中的上次更新时间为当前时间
    r.lim.tokens = tokens //更新限流器中的剩余令牌数为新的令牌数
    //如果预约结果的执行时间等于限流器中的最近事件时间，表示需要调整最近事件时间
    if r.timeToAct == r.lim.lastEvent { 
        //计算预约结果之前的最近事件时间，等于执行时间减去生成请求令牌数所需的时间间隔
        prevEvent := r.timeToAct.Add(r.limit.durationFromTokens(float64(-r.tokens))) 
        if !prevEvent.Before(t) { //如果预约结果之前的最近事件时间不早于当前时间，表示有效
            r.lim.lastEvent = prevEvent //更新限流器中的最近事件时间为预约结果之前的最近事件时间
        }
    }
}

可以调用Cancel()取消令牌消费操作,该函数中会调用CancelAt(),首先要了解Reservation中的几个字段
r.tokens指的是本次消费的token数，
r.timeToAcr指的是Token桶可以满足本次消费数目的时刻，也就是消费的时刻+等待的时长
r.lim.lastEvent指的是最近一次消费的timeToAct的值
在CancelAt()中最重要的逻辑:通过r.limit.tokensFromDuration方法得出从该次消费到当前时间一共又消费了多少Token数目,然后"r.tokens本次消费的令牌数" 减去 "从该次消费到当前时间一共又消费的令牌数"得出要归还的令牌
restoreTokens := float64(r.tokens) - r.limit.tokensFromDuration(r.lim.lastEvent.Sub(r.timeToAct))，
1
然后更新Reservation中的上次token更新时间,剩余令牌数等信息
三. 总结
复习限流算法
先说一下几个限流相关算法的优缺点
计数器: 只需要维护一个计数器变量,实现简单,性能消耗较小,缺点无法控制速率,无法解决瞬时高并发问题
令牌桶:
固定速率,向桶中添加令牌,桶容量是有限的,接收到请求后首先获取桶中的令牌进行消费
缺点: 需要维护令牌生成速率与桶容量实现稍微有点复杂,通过桶容量一定程度上解决了瞬时并发问题,但是没有彻底解决
漏桶
可以以任意速率流入水滴到漏桶中,但是按照固定速率流出水滴, 如果桶是空的，则不需流出水滴,；如果流入水滴超出了桶的容量，则流入的水滴溢出了执行服务降级
令牌桶是按照固定速率往桶中添加令牌,请求是否被处理需要看桶中令牌是否足够,当令牌数减为零时则拒绝新的请求；漏桶则是按照常量固定速率流出请求,请求到达后端,流入请求速率任意请求有客户端发送到桶中,当流入的请求数累积到漏桶容量时,则新流入的请求被拒绝
缺点: 与令牌桶相同
滑动窗口
滑动窗口出现的原因: 假设通过计数器实现限流,限制每秒钟最高允许10个请求通过,每请求一次计数器+1,当请求超过10,并且与第一次请求的时间间隔不超过一秒钟,说明请求过多,服务熔断降级,如果与第一次请求间隔超过一秒钟,说明还在范围内重置计数器(思考问题临界问题:假设在第1秒时接收到9个请求,都在执行中,到2秒计数器重置进入新的计算阶段又进来9个请求,当前实际就承载了18个请求,超过阈值)
滑动窗口算法计数器: 解决传统计数器临界问题: 假设每分钟允许向后台请求60次,可以将这60次请求分为6份,每秒钟允许请求10次,每个时间段都有自己的计数器,记录这个时间段内发生的请求数量,通过滑动进行判断,每过一个时间段,就把最早的时间段和它的计数器删掉,然后加入一个新的时间段和计数器,进而解决临界问题
time/rate 总结
time/rate 基于令牌桶算法实现的限流组件,允许一定程度的突发,同时保证了请求的平均速率,内部基于锁,channel,保证了并发安全,牺牲了一点性能但是保证了令牌的精确性
了解time/rate限流首先要了解Limiter与Reservation两个结构体,在调用NewLimiter()函数创建限流器时会返回一个Limiter 结构体变量,内部有一个limit 属性表示每秒处理的频率也就是限流速率, burst 最大并发数,mu 锁, tokens 当前令牌桶中可用的令牌数…
在实现限流时底层都会调用到一个reserveN()函数,会根据传入的等待时间,计算这段时间内能否生成需要的令牌数,封装Reservation,在Reservation 中存在,tokens本次消费的令牌数,ok 到截止时间是否能够生成指定的令牌数属性,timeToAct 获取指定令牌需要等待的时间属性
消费令牌原理:
rate中提供了Allow()消费一个令牌,Wait()阻塞等待消费一个令牌, Reserve()预定一个令牌,内部实际都会调用到调用reserveN和advance方法,reserveN()用于判断在指定时间内是否有足够的令牌
首先判断当前消费的令牌数是否超过了最大限制,如果超过了,直接报错,判断limit限流速率如果不等于MaxFloat64并且不等于0,调用advance()计算当前可以使用的令牌数量,也就是(上次剩余令牌数+上次消费令牌时间到当前时间所生成的令牌,如果大于最大并发限制,的更新为最大并发限制)
如果advance()拿到当前可消费的令牌数量小于0,说明超过并发限制,调用durationFromTokens()计算等待生成令牌时间
封装Reservation,如果当前要消费的令牌数量小于允许可消费的令牌数量则Reservation中的ok为true表示允许消费,否则为false,最后解锁,返回预约结果
Wait 阻塞获取令牌原理,在Wait阻塞消费令牌函数中,首先会封装一个返回定时器通道的函数,然后调用Limiter的wait()方法,
在wait()方法中,会通过select-case监听context的Done取消,如果取消了返回异常,并获取context的取消时间,作为等待时间调用reserveN()进行预订
在reserveN()预订令牌方法中,会根据传入的等待时间计算这个时间段内是否存在或可以生产出指定数量的令牌,并且会返回生产这些令牌所需要的时间
如果存在或指定等待时间内可以生产出需要的令牌reserveN()返回的Reservation中ok为true,调用DelayFrom()方法计算获取令牌需要的等待时间,DelayFrom()返回0说明不需要等待直接返回,大于0,执行Wait()函数中封装的返回定时器通道的函数,拿到定时器通道,通过select-case监听Context的Done取消消息和这个定时器通道,当定时器通道返回说明令牌生成完毕函数返回,Wait阻塞开始向下执行
Cancel()取消令牌消费操作: Cancel()函数内部会调用CancelAt(),该函数中最重要的逻辑:通过r.limit.tokensFromDuration方法得出从该次消费到当前时间一共又消费了多少Token数目,然后"r.tokens本次消费的令牌数" 减去 "从该次消费到当前时间一共又消费的令牌数"得出要归还的令牌,然后更新Reservation中的上次token更新时间,剩余令牌数等信息