限流

常见的限流算法

固定窗口计数器算法

固定窗口计数器算法将工夫分为固定大小的窗口，例如1秒。在每个窗口中，服务会记录它接管到的申请数。如果在一个窗口中的申请数超过了事后设定的阈值，那么新的申请将被回绝，直到进入下一个窗口。

这种算法简略易实现，但可能会导致窗口边界左近的申请突发。例如，如果窗口大小为1秒，阈值为100，那么在1秒的边界处，服务可能会在短时间内解决200个申请。

滑动窗口计数器算法

滑动窗口计数器算法试图解决固定窗口计数器算法中的申请突发问题。它将窗口分成更小的子窗口，例如将1秒分为10个100毫秒的子窗口。每次接管到申请时，服务会更新以后子窗口的计数器。服务会查看过来的N个子窗口的计数器之和，如果这个和超过阈值，那么新的申请将被回绝。

这种算法能够更好地平滑申请流量，但实现起来绝对简单，因为须要跟踪多个子窗口的计数器。

令牌桶算法

令牌桶算法保护一个令牌桶，其中蕴含肯定数量的令牌。令牌以恒定速率增加到桶中，直到达到桶的容量。每次接管到申请时，服务会尝试从桶中获取一个令牌。如果桶中有足够的令牌，申请被容许解决；如果没有足够的令牌，申请将被回绝。

令牌桶算法容许短暂的申请突发，因为在低流量期间，令牌能够累积到桶的容量。这种算法在实践中体现良好，但实现起来绝对简单。

漏桶算法

漏桶算法应用一个队列模仿一个漏水的桶。申请作为水滴进入队列，以恒定速率从队列中移除并解决。如果队列已满，新的申请将被回绝。

漏桶算法能够平滑申请流量，但它不能解决突发流量，因为申请解决速率是固定的。实现漏桶算法也绝对简单，因为须要在后盾应用定时器或其余机制来以恒定速率解决队列中的申请。

time/rate

次要办法

  • NewLimiter(limit Limit, burst int) *Limiter: 创立一个新的限流器，参数包含每秒容许的事件数量（limit）和令牌桶容量（burst）。
  • (lim *Limiter) Allow() bool: 查看令牌桶中是否有可用的令牌。如果有可用令牌，则从桶中取走一个令牌并返回 true；否则返回 false。
  • (lim *Limiter) AllowN(now time.Time, n int) bool: 与 Allow() 相似，但查看 n 个令牌是否可用。如果有足够的令牌，从桶中取走 n 个令牌并返回 true；否则返回 false。
  • (lim *Limiter) Wait(ctx context.Context) error: 阻塞期待，直到有一个可用的令牌。如果在期待过程中 context 被勾销或超时，将返回一个谬误。
  • (lim *Limiter) WaitN(ctx context.Context, n int) error: 阻塞期待，直到有 n 个可用的令牌。如果在期待过程中 context 被勾销或超时，将返回一个谬误。
  • (lim *Limiter) Reserve() *Reservation: 返回一个预留令牌的 Reservation 对象。你能够依据须要期待预留令牌或勾销预留。
  • (lim *Limiter) ReserveN(now time.Time, n int) *Reservation: 相似于 Reserve()，但预留 n 个令牌。

各个办法的作用

  • NewLimiter 用于创立一个新的限流器实例。
  • Allow 和 AllowN 用于疾速查看是否有足够的令牌可用，这些办法非阻塞。
  • Wait 和 WaitN 用于阻塞期待直到有足够的令牌可用，这些办法会阻塞。
  • Reserve 和 ReserveN 用于预留令牌，容许您依据须要期待预留令牌或勾销预留。

time/rate 是如何实现限流的

time/rate 包基于令牌桶算法实现限流。限流器通过一个恒定速率（limit）向令牌桶增加令牌，直到桶的容量（burst）达到下限。每当解决一个申请时，限流器会尝试从令牌桶中取出一个或多个令牌。

Allow 和 AllowN 办法查看令牌桶中是否有足够的令牌。如果没有足够的令牌，这些办法会立刻返回 false，示意应拒绝请求。Wait 和 WaitN 办法会阻塞期待，直到有足够的令牌可用。如果在期待过程中上下文（context）被勾销或超时，这些办法会返回一个谬误，示意申请被回绝。Reserve 和 ReserveN 办法提供了更灵便的形式来预留令牌，您能够依据须要期待预留的令牌或勾销预留。

通过这些办法，time/rate 限流器能够管制解决申请的速率，确保它不会超过设定的限度。通过调整令牌生成速率和令牌桶容量，您能够依据理论需要和零碎负载来调整限流策略。

源码解析

令牌桶限流器的定义：

在 rate.go 文件中，定义了 Limiter 构造体：

type Limiter struct {    mu     sync.Mutex    limit  Limit    tokens float64    // last 是上次令牌桶更新的工夫    last time.Time    // 用于调整令牌桶更新工夫的时钟    clock Clock    // 用于在 Wait 系列办法中进行休眠的定时器    sleepFn func(time.Duration)}

Limiter 构造体蕴含了一些要害属性，例如令牌生成速率（limit）、以后令牌数（tokens）和上次更新工夫（last）。

令牌桶更新：

time/rate 包中的外围函数之一是 reserveN，它负责预留 N 个令牌。在此过程中，令牌桶会依据工夫更新。

func (lim *Limiter) reserveN(now time.Time, n int) *Reservation {    lim.mu.Lock()    defer lim.mu.Unlock()    // 更新令牌桶    now, tokens := lim.advance(now)    // 计算须要的令牌数与以后可用令牌数之间的差值    delta := float64(n) - tokens    // 计算等待时间    waitDuration := lim.limit.durationFromTokens(delta)    // 更新令牌桶状态    tokens -= float64(n)    lim.last = now.Add(waitDuration)    lim.tokens = tokens    return &Reservation{        ok:        true,        lim:       lim,        tokens:    n,        timeToAct: now.Add(waitDuration),    }}

在 reserveN 函数中，首先调用 advance 函数来更新令牌桶：

func (lim *Limiter) advance(now time.Time) (time.Time, float64) {    last := lim.last    // 计算上次更新以来通过的工夫    elapsed := now.Sub(last)    // 依据通过的工夫计算生成的令牌数    delta := elapsed.Seconds() * float64(lim.limit)    // 更新令牌桶中的令牌数，但不超过令牌桶容量    tokens := math.Min(lim.tokens+delta, float64(lim.limit.Burst()))    return now, tokens}

advance 函数依据工夫更新令牌桶，计算从上次更新以来生成的令牌数量，并将新令牌增加到桶中，但不超过桶的容量。

令牌预留和期待：

在 reserveN 函数中，首先计算须要的令牌数与以后可用令牌数之间的差值。而后依据差值计算等待时间。如果等待时间为正值，则示意须要期待一段时间

能力取得足够的令牌。最初，更新令牌桶状态，将所需令牌数从以后令牌数中减去。

reserveN 函数返回一个 Reservation 对象，其中蕴含预留的令牌数、等待时间等信息。Reservation 构造体定义如下：

type Reservation struct {    ok        bool    lim       *Limiter    tokens    int    timeToAct time.Time}

Reservation 对象提供了一些办法，例如 Delay（返回须要期待的工夫）和 Cancel（勾销预留）。这些办法容许用户在须要时期待预留的令牌，或在不再须要令牌时勾销预留。

公开 API：

time/rate 包提供了一系列公开 API，例如 Allow, AllowN, Wait, WaitN, Reserve 和 ReserveN。这些办法都是基于 reserveN 函数的封装。例如，Allow 办法只需查看预留的等待时间是否为零：

func (lim *Limiter) Allow() bool {    return lim.AllowN(time.Now(), 1)}func (lim *Limiter) AllowN(now time.Time, n int) bool {    return lim.reserveN(now, n).Delay() == 0}

相似地，Wait 和 WaitN 办法将阻塞期待，直到预留的等待时间过来：

func (lim *Limiter) Wait(ctx context.Context) error {    return lim.WaitN(ctx, 1)}func (lim *Limiter) WaitN(ctx context.Context, n int) error {    if n > lim.limit.Burst() {        return fmt.Errorf("rate: Wait(n=%d) exceeds limiter's burst %d", n, lim.limit.Burst())    }    r := lim.ReserveN(time.Now(), n)    delay := r.DelayFrom(time.Now())    if delay == 0 {        return nil    }    t := lim.clock.AfterFunc(delay, r.Cancel)    defer t.Stop()    select {    case <-ctx.Done():        r.Cancel()        return ctx.Err()    case <-t.C:        return nil    }}

总之，time/rate 包通过令牌桶算法实现了限流。它提供了一系列 API，容许用户在不同场景下灵便地管制申请速率。外部实现次要依赖于 reserveN 函数来更新令牌桶状态，并依据须要期待或预留令牌。