关于golang:Go实现各类限流

在开发高并发零碎时，咱们可能会遇到接口拜访频次过高，为了保证系统的高可用和稳定性，这时候就须要做流量限度，你可能是用的 Nginx 这种 Web Server 来管制申请，也可能是用了一些风行的类库实现。限流是高并发零碎的一大杀器，在设计限流算法之前咱们先来理解一下它们是什么。

限流 的目标是通过对并发拜访申请进行限速，或者对一个工夫窗口内的申请进行限速来爱护零碎，一旦达到限度速率则能够拒绝服务、排队或期待、降级等解决。通过对并发（或者肯定工夫窗口内）申请进行限速来爱护零碎，一旦达到限度速率则拒绝服务（定向到谬误页或告知资源没有了）、排队期待（比方秒杀、评论、下单）、降级（返回兜底数据或默认数据）。

如图:

如图上的漫画，在某个时间段流量上来了，服务的接口拜访频率可能会十分快，如果咱们没有对接口拜访频次做限度可能会导致服务器无奈接受过高的压力挂掉，这时候也可能会产生数据失落，所以就要对其进行限流解决。

限流算法就能够帮忙咱们去管制每个接口或程序的函数被调用频率，它有点儿像保险丝，避免零碎因为超过拜访频率或并发量而引起瘫痪。咱们可能在调用某些第三方的接口的时候会看到相似这样的响应头：

X-RateLimit-Limit: 60         // 每秒 60 次申请
X-RateLimit-Remaining: 22     // 以后还剩下多少次
X-RateLimit-Reset: 1612184024 // 限度重置工夫

下面的 HTTP Response 是通过响应头通知调用方服务端的限流频次是怎么的，保障后端的接口拜访下限。为了解决限流问题呈现了很多的算法，它们都有不同的用处，通常的策略就是回绝超出的申请，或者让超出的申请排队期待。

一般来说，限流的罕用解决伎俩有：

计数器
滑动窗口
漏桶
令牌桶

计数器是一种最简略限流算法，其原理就是：在一段时间距离内，对申请进行计数，与阀值进行比拟判断是否须要限流，一旦到了工夫临界点，将计数器清零。
这个就像你去坐车一样，车厢规定了多少个地位，满了就不让上车了，不然就是超载了，被交警叔叔抓到了就要罚款的，如果咱们的零碎那就不是罚款的事件了，可能间接崩掉了。

能够在程序中设置一个变量 count，当过去一个申请我就将这个数 +1，同时记录申请工夫。
当下一个申请来的时候判断 count 的计数值是否超过设定的频次，以及以后申请的工夫和第一次申请工夫是否在 1 分钟内。
如果在 1 分钟内并且超过设定的频次则证实申请过多，前面的申请就回绝掉。
如果该申请与第一个申请的间隔时间大于计数周期，且 count 值还在限流范畴内，就重置 count。

代码实现:

package main

import (
    "log"
    "sync"
    "time"
)

type Counter struct {
    rate  int           // 计数周期内最多容许的申请数
    begin time.Time     // 计数开始工夫
    cycle time.Duration // 计数周期
    count int           // 计数周期内累计收到的申请数
    lock  sync.Mutex
}

func (l *Counter) Allow() bool {l.lock.Lock()
    defer l.lock.Unlock()

    if l.count == l.rate-1 {now := time.Now()
        if now.Sub(l.begin) >= l.cycle {
            // 速度容许范畴内，重置计数器
            l.Reset(now)
            return true
        } else {return false}
    } else {
        // 没有达到速率限度，计数加 1
        l.count++
        return true
    }
}

func (l *Counter) Set(r int, cycle time.Duration) {
    l.rate = r
    l.begin = time.Now()
    l.cycle = cycle
    l.count = 0
}

func (l *Counter) Reset(t time.Time) {
    l.begin = t
    l.count = 0
}

func main() {
    var wg sync.WaitGroup
    var lr Counter
    lr.Set(3, time.Second) // 1s 内最多申请 3 次
    for i := 0; i < 10; i++ {wg.Add(1)
        log.Println("创立申请:", i)
        go func(i int) {if lr.Allow() {log.Println("响应申请:", i)
          }
          wg.Done()}(i)

        time.Sleep(200 * time.Millisecond)
    }
    wg.Wait()}

OutPut:

2021/02/01 21:16:12 创立申请: 0
2021/02/01 21:16:12 响应申请: 0
2021/02/01 21:16:12 创立申请: 1
2021/02/01 21:16:12 响应申请: 1
2021/02/01 21:16:12 创立申请: 2
2021/02/01 21:16:13 创立申请: 3
2021/02/01 21:16:13 创立申请: 4
2021/02/01 21:16:13 创立申请: 5
2021/02/01 21:16:13 响应申请: 5
2021/02/01 21:16:13 创立申请: 6
2021/02/01 21:16:13 响应申请: 6
2021/02/01 21:16:13 创立申请: 7
2021/02/01 21:16:13 响应申请: 7
2021/02/01 21:16:14 创立申请: 8
2021/02/01 21:16:14 创立申请: 9

能够看到咱们设置的是每 200ms 创立一个申请，显著高于 1 秒最多 3 个申请的限度，运行起来之后发现编号为 2、3、4、8、9 的申请被抛弃，阐明限流胜利。

那么问题来了，如果有个需要对于某个接口 /query 每分钟最多容许拜访 200 次，假如有个用户在第 59 秒的最初几毫秒霎时发送 200 个申请，当 59 秒完结后 Counter 清零了，他在下一秒的时候又发送 200 个申请。那么在 1 秒钟内这个用户发送了 2 倍的申请，这个是合乎咱们的设计逻辑的，这也是计数器办法的设计缺点，零碎可能会接受歹意用户的大量申请，甚至击穿零碎。

如下图:

这种办法尽管简略，但也有个大问题就是没有很好的解决单位工夫的边界。

滑动窗口 是针对计数器存在的临界点缺点，所谓 滑动窗口（Sliding window） 是一种流量控制技术，这个词呈现在 TCP 协定中。滑动窗口 把固定工夫片进行划分，并且随着工夫的流逝，进行挪动，固定数量的能够挪动的格子，进行计数并判断阀值。

如图：

上图中咱们用红色的虚线代表一个工夫窗口（一分钟），每个工夫窗口有 6 个格子，每个格子是 10 秒钟。每过 10 秒钟工夫窗口向右挪动一格，能够看红色箭头的方向。咱们为每个格子都设置一个独立的计数器 Counter，如果一个申请在 0:45 拜访了那么咱们将第五个格子的计数器 +1（也是就是 0:40~0:50），在判断限流的时候须要把所有格子的计数加起来和设定的频次进行比拟即可。

那么滑动窗口如何解决咱们下面遇到的问题呢？来看上面的图：

当用户在 0:59 秒钟发送了 200 个申请就会被第六个格子的计数器记录 +200，当下一秒的时候工夫窗口向右挪动了一个，此时计数器曾经记录了该用户发送的 200 个申请，所以再发送的话就会触发限流，则回绝新的申请。

其实计数器就是滑动窗口啊，只不过只有一个格子而已，所以想让限流做的更准确只须要划分更多的格子就能够了，为了更准确咱们也不晓得到底该设置多少个格子，格子的数量影响着滑动窗口算法的精度，仍然有工夫片的概念，无奈基本解决临界点问题。

相干算法实现 github.com/RussellLuo/slidingwindow

漏桶算法（Leaky Bucket），原理就是一个固定容量的漏桶，依照固定速率流出水滴。用过水龙头都晓得，关上龙头开关水就会流下滴到水桶里，而漏桶指的是水桶上面有个破绽能够出水。如果水龙头开的特地大那么水流速就会过大，这样就可能导致水桶的水满了而后溢出。

如图：

一个固定容量的桶，有水流进来，也有水流进来。对于流进来的水来说，咱们无奈预计一共有多少水会流进来，也无奈预计水流的速度。然而对于流出去的水来说，这个桶能够固定水流出的速率（处理速度 ），从而达到 流量整形 和 流量管制 的成果。

代码实现:

type LeakyBucket struct {
    rate       float64 // 固定每秒出水速率
    capacity   float64 // 桶的容量
    water      float64 // 桶中以后水量
    lastLeakMs int64   // 桶上次漏水工夫戳 ms

    lock sync.Mutex
}

func (l *LeakyBucket) Allow() bool {l.lock.Lock()
    defer l.lock.Unlock()

    now := time.Now().UnixNano() / 1e6
    eclipse := float64((now - l.lastLeakMs)) * l.rate / 1000 // 先执行漏水
    l.water = l.water - eclipse                              // 计算残余水量
    l.water = math.Max(0, l.water)                           // 桶干了
    l.lastLeakMs = now
    if (l.water + 1) < l.capacity {
        // 尝试加水, 并且水还未满
        l.water++
        return true
    } else {
        // 水满，回绝加水
        return false
    }
}

func (l *LeakyBucket) Set(r, c float64) {
    l.rate = r
    l.capacity = c
    l.water = 0
    l.lastLeakMs = time.Now().UnixNano() / 1e6
}

漏桶算法有以下特点：

漏桶具备固定容量，出水速率是固定常量（流出申请）
如果桶是空的，则不需流出水滴
能够以任意速率流入水滴到漏桶（流入申请）
如果流入水滴超出了桶的容量，则流入的水滴溢出（新申请被回绝）

漏桶限度的是常量流出速率（即流出速率是一个固定常量值），所以最大的速率就是出水的速率，不能呈现突发流量。

令牌桶算法 （Token Bucket） 是网络流量整形 （Traffic Shaping） 和速率限度 （Rate Limiting） 中最常应用的一种算法。典型状况下，令牌桶算法用来管制发送到网络上的数据的数目，并容许突发数据的发送。

咱们有一个固定的桶，桶里寄存着令牌 （token）。一开始桶是空的，零碎按固定的工夫（rate） 往桶里增加令牌，直到桶里的令牌数满，多余的申请会被抛弃。当申请来的时候，从桶里移除一个令牌，如果桶是空的则拒绝请求或者阻塞。

实现代码：

type TokenBucket struct {
    rate         int64 // 固定的 token 放入速率, r/s
    capacity     int64 // 桶的容量
    tokens       int64 // 桶中以后 token 数量
    lastTokenSec int64 // 桶上次放 token 的工夫戳 s

    lock sync.Mutex
}

func (l *TokenBucket) Allow() bool {l.lock.Lock()
    defer l.lock.Unlock()

    now := time.Now().Unix()
    l.tokens = l.tokens + (now-l.lastTokenSec)*l.rate // 先增加令牌
    if l.tokens > l.capacity {l.tokens = l.capacity}
    l.lastTokenSec = now
    if l.tokens > 0 {
        // 还有令牌，支付令牌
        l.tokens--
        return true
    } else {
        // 没有令牌, 则回绝
        return false
    }
}

func (l *TokenBucket) Set(r, c int64) {
    l.rate = r
    l.capacity = c
    l.tokens = 0
    l.lastTokenSec = time.Now().Unix()
}

令牌桶有以下特点：

令牌按固定的速率被放入令牌桶中
桶中最多寄存 B 个令牌，当桶满时，新增加的令牌被抛弃或回绝
如果桶中的令牌有余 N 个，则不会删除令牌，且申请将被限流（抛弃或阻塞期待）

令牌桶限度的是均匀流入速率（容许突发申请，只有有令牌就能够解决，反对一次拿 3 个令牌，4 个令牌 …），并容许肯定水平突发流量。

目前罕用的是 令牌桶 这种，本文介绍了几种常见的限流算法实现，文章撰写不易，点个关注不迷路。

关于golang:Go实现各类限流

前言

限流

计数器

滑动窗口

漏桶

令牌桶算法

小结

前 言

限 流

计数器

滑动窗口

漏 桶

令牌桶算法

小 结

前言

限流

漏桶

小结