一、为什么会有限流
限流，看字面意思，限制流动。
为什么要限制流动？
发生了一些意外情况，才可能要限制流动。等恢复正常情况后，就解除限制。不可能无缘无故的限制流动，毕竟限制会影响正常系统运行。
足球馆看足球比赛，足球馆的场地大小是固定的，座位数是固定的，能容纳看球人数总量是有限的。如果超过足球馆容量最大承载，会导致场内拥挤，这样会发生2个问题：一个是导致大家行动不便，一个可能会发生意想不到的事故。
那怎么办？球票。
一个足球场出售的球票是有限制的，一共卖多少张票是有一定数量额度。
那在计算机系统中，为什么要限流？
计算机系统容量是有限的，内存大小，CPU 处理数据的速度，都是有限的，不可能无限大。如果超过了一定的阙值，系统就会出现异常，甚至宕机。
如果访问一个 API 服务时，超过了这个服务能提供的最大访问能力，服务会崩溃，那就要对这个服务进行保护，避免服务因访问过大导致服务不可用，不仅影响自己服务，也可能影响其它相关服务。
在 IT 高并发系统中，处于对系统的保护，需要对系统进行限流。
二、IT 系统中的限流
下面来看看对使用限流的一些具体情况描述。
流动起来就形成了网络流。TCP 里就有限制流量的算法-滑动窗口算法。
对接口访问请求，怎么描述接口请求情况？
一般用每秒请求数（request per second），并发请求数等，来描述对接口的请求情况。所以限制也是对每秒请求数进行限制。
三、常用限流算法
常用的限流算法，一般有 4 种：
计数器
滑动窗口
漏桶
令牌桶
计数器算法
在固定窗口内对请求进行计数，然后与设置的最大请求数进行比较，如果超过了最大值，就进行限流。到达了一个固定时间窗口终点，将计数器清零，重新开始计数。
计数器算法又叫 固定窗口算法-Fixed Window。
根据描述，这个算法为：
还有一个计时开始时间 BeginTime , 请求计数 Counter。
package main
import (
"fmt"
"sync"
"time"
)
const (
MAXREQUEST = 10 // 限制最大请求数
WINDOWTIME = 3 * time.Second // 最大窗口时间
)
type limit struct {
beginTime time.Time
counter int
mu sync.Mutex
}
func (limit *limit) apiLimit() bool {
limit.mu.Lock()
defer limit.mu.Unlock()
nowTime := time.Now()
if nowTime.Sub(limit.beginTime) >= WINDOWTIME {
limit.beginTime = nowTime
limit.counter = 0
}
if limit.counter > MAXREQUEST {
return false
}
limit.counter++
fmt.Println("counter: ", limit.counter)
return true
}
func main() {
var wg sync.WaitGroup
var limit limit
for i := 0; i < 15; i++ {
wg.Add(1)
fmt.Println("req start:", i, time.Now())
go func(i int) {
if limit.apiLimit() {
fmt.Println("req counter: ", i, time.Now())
}
wg.Done()
}(i)
time.Sleep(150 * time.Millisecond)
}
wg.Wait()
}算法优点：实现简单
1.计数器算法有一个”临界时间点“问题。
它无法应对两个时间窗口临界时间内的突发流量。
滑动窗口算法
滑动窗口算法（Sliding Window）部分解决了计数器算法（固定时间窗口算法）“时间临界点” 的问题。
滑动窗口日志(sliding window log) 和 滑动窗口计数（sliding window counter）。
滑动窗口计数
在计数器算法中，把大时间窗口在进一步划分为更细小的时间窗口格子，随着时间向前移动，大时间窗每次向前移动一个小格子，而不是大时间窗向前移动。每个小格子都有自己独立计数器，小格子会记录每个请求到达的时间点。
比较小格子内请求数：(大时间窗口内规定最大请求数 / N个小格子) > 小格子时间窗内总请求数
举个例子：
都有自己独立的计数器 counter。下面图1到图2：
这个例子把最大请求数设置为300，最大时间窗时间设置为 30秒，小格子时间窗设置为 1秒，便于程序演示。
package main
import (
"fmt"
"sync"
"time"
)
const (
MAXREQUEST = 300 // 限制最大请求数
WINDOWTIME = 30 * time.Second // 最大窗口时间
)
type SlidingWindow struct {
smallWindowTime int64 // 小窗口时间大小
smallWindowNum int64 // 小窗口总数
smallWindowCap int // 小窗口请求容量
counters map[int64]int // 小窗口计数器
mu sync.Mutex // 锁
}
func NewSlidingWindow(smallWindowTime time.Duration) (*SlidingWindow, error) {
num := int64(WINDOWTIME / smallWindowTime) // 小窗口总数
return &SlidingWindow{
smallWindowTime: int64(smallWindowTime),
smallWindowNum: num,
smallWindowCap: MAXREQUEST / int(num),
counters: make(map[int64]int),
}, nil
}
func (sw *SlidingWindow) ReqLimit() bool {
sw.mu.Lock()
sw.mu.Unlock()
// 获取当前小格子窗口所在的时间值
curSmallWindowTime := time.Now().Unix()
// 计算当前小格子窗口起始时间
beginTime := curSmallWindowTime - sw.smallWindowTime*(sw.smallWindowNum-1)
// 计算当前小格子窗口请求总数
var count int
for sWindowTime, counter := range sw.counters { // 遍历计数器
if sWindowTime < beginTime { // 判断不是当前小格子
delete(sw.counters, sWindowTime)
} else {
count += counter // 当前小格子窗口计数器累加
}
}
// 当前小格子请求到达请求限制，请求失败，返回 false
if count >= sw.smallWindowCap {
return false
}
// 没有到达请求上限，当前小格子窗口计数器+1，请求成功
sw.counters[curSmallWindowTime]++
return true
}
func main() {
var wg sync.WaitGroup
sw, _ := NewSlidingWindow(1 * time.Second)
fmt.Println("num:", sw.smallWindowNum, "cap:", sw.smallWindowCap)
for i := 0; i < 15; i++ {
wg.Add(1)
fmt.Println("req start:", i, time.Now())
go func(i int) {
if sw.ReqLimit() {
fmt.Println("req counter: ", time.Now())
}
wg.Done()
}(i)
time.Sleep(200 * time.Millisecond)
}
wg.Wait()
}滑动窗口算法是怎么解决“临界时间点”问题？
在 21:30:59 秒到达 30 个请求，它落在上图2中灰色小格子中，然后 21:31:01 秒又瞬间到达 30 个，它会落在图2橘色小格子中。而当时间到达 21:31:01 时，时间窗要向右移动一小格（如上图2箭头所示），此时大时间窗内的总请求数为 60，超过了规定的最大请求数 30 个，这时就能检测出超过了请求阙值从而触发限流。
这个看划分小格子的时间大小了。比如说上面例子小格子时间是 10 秒，如果瞬间流量是微秒呢？可能又会超过限制。那划分更细时间单位。理论上流量到达时间也可以更细。
多层次限流，同一个接口设置多条限流规则。比如 1 分钟 30 个，100ms 2 个。
计数器其实是一个固定时间窗口，它只有一格，比较大的一格时间，计数器算法是按照一大格时间窗向前移动。滑动窗口算法是按照一小格时间向前移动。固定窗口可以说是滑动窗口的一种特殊情况。
漏桶算法
先看下面一张图：
(a)图：有一个控制开关的水龙头，下面有一个桶用来装水，桶下面有一个放水的洞。把请求比作水，水来了就先放到桶里，然后按照一定
(b)图：把 (a) 图在进一步算法化，把漏桶算法形象表示出来。
有的人形象把它叫作流量“整形”，因为不管你流入有多快，流出都是固定速率。
package main
import (
"fmt"
"sync"
"time"
)
const (
MAXREQUEST = 5
)
type LeakyBucket struct {
capacity int // 桶的容量 - 最高水位
currentReqNum int // 桶中当前请求数量 - 当前水位
lastTime time.Time // 桶中上次请求时间 - 上次放水时间
rate int // 桶中流出请求的速率，每秒流出多少请求,水流速度/秒
mu sync.Mutex // 锁
}
func NewLeakyBucket(rate int) *LeakyBucket {
return &LeakyBucket{
capacity: MAXREQUEST, //容量
lastTime: time.Now(),
rate: rate,
}
}
func (lb *LeakyBucket) ReqLimit() bool {
lb.mu.Lock()
lb.mu.Unlock()
now := time.Now()
// 计算距离上次放水时间间隔
gap := now.Sub(lb.lastTime)
fmt.Println("gap：", gap)
if gap >= time.Second {
// gap 这段时间流出的请求数=gap时间 * 每秒流出速率
out := int(gap/time.Second) * lb.rate
// 计算当前桶中请求数
lb.currentReqNum = maxInt(0, lb.currentReqNum-out)
lb.lastTime = now
}
// 桶中的当前请求数大于桶容量，请求失败
if lb.currentReqNum >= lb.capacity {
return false
}
// 若没超过桶容量，桶中请求量+1，返回true
lb.currentReqNum++
fmt.Println("curReqNum:", lb.currentReqNum)
return true
}
func maxInt(a, b int) int {
if a > b {
return a
}
return b
}
// 测试
func main() {
var wg sync.WaitGroup
lb := NewLeakyBucket(1)
fmt.Println("cap:", lb.capacity)
for i := 0; i < 15; i++ {
wg.Add(1)
fmt.Println("req start:", i, time.Now())
go func(i int) {
if lb.ReqLimit() {
fmt.Println("req counter: ", time.Now())
}
wg.Done()
}(i)
time.Sleep(10 * time.Millisecond)
}
wg.Wait()
}缺点：
令牌桶算法
上面漏桶算法流入速度不稳定，流出速度是稳定的。
令牌总数超过桶容量，就丢弃。令牌我们可以匀速生产，所以流入桶中令牌是稳定的。
令牌桶算法如下图所示：
1.令牌桶的容量
2.最大限流量，最大请求的容量，这个关系到令牌桶里的令牌总数
