undefined

一、基于滑动窗口的限流算法

滑动算法弥补了计数器算法的不足。滑动窗口算法把间隔时间划分成更小的粒度，当更小粒度的时间间隔过去后，把过去的间隔请求数减掉，再补充一个空的时间间隔。如图

• 把 1 分钟划分成 10 个更小的时间时间，每 6 秒为一个间隔，如图中的 10 个格子，每个格子代表 6 秒
• 每过 6 秒，滑动窗口向右移动 1 个格子。每个格子都有独立的计数
• 如果时间窗口内所有格子的计数之和超过了限流阈值，则触发限流操作

滑动窗口设置的越精细，限流效果越好，但滑动窗口的时间间隔（格子）多了，存储空间也会增加。需要根据业务场景来定义

1. 实现

实现目标：1分钟请求少于 1000。如下代码实现

// 滑动窗口
type SlideWindowLimit struct {
    // 滑动窗口大小
    size int
    // 滑动窗口数组，每移动一个格子，更新对应数据项的值
    window []int
    // 移动窗口中正在计数的格子
    curId int
    // 上次统计时间
    lastDate time.Time
    // 当前窗口计数总和
    counter int
}

// 初始化
func (s *SlideWindowLimit) Init() {
    s.size = 10
    s.window = []int{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
    s.curId = 0
    s.lastDate = time.Now()
    s.counter = 0
}

// 模拟一次请求是否限流
func (s *SlideWindowLimit)IsLimit() bool {
    // 当前时间同上次记录时间的间隔
    elapsedTime := time.Since(s.lastDate)
    // 按照新的移动窗口进行计数
    if elapsedTime.Seconds() >= 6 {
        // 当前计数格子的下一个格子将被清掉重写
        s.curId++
        s.curId = s.curId % s.size
        newCurId := s.curId
        // 下一个格子将被清掉，总数据减掉
        s.counter = s.counter - s.window[newCurId]
        s.window[newCurId] = 1
        s.lastDate = time.Now()
    } else {
        s.window[s.curId]++
    }
    s.counter++
    return s.counter > 1000
}

func main() {
    // 先发送 600 次，等待 30 秒后，发送 600 次，就会触动限频
    s := new(SlideWindowLimit)
    s.Init()
    for i := 0; i < 600; i++ {
        if s.IsLimit() == true {
            panic("error")
        }
    }
    time.Sleep(30*time.Second)
    for i := 0; i < 600; i++ {
        if s.IsLimit() == true {
            fmt.Printf("触发限频, i: %d \n", i + 600)
            return
        }
    }
}