滑动窗口

滑动窗口算法指有一个固定大小的时间窗口T ，设置在这个T窗口下只能通过M个请求，并且这个窗口是不断向前移动

计算公式 remaining = M - (resetInSec / T * prevHit + currHit)

resetInSec = exp - ts - time until end of current window.

exp: 当前窗口的 end time
ts: 当前时间

        prev                       curr
|----------------------|------------------------|
                                 ^              ^
                                 ts------------exp
                                    resetInSec

代码逻辑

对于设置 exp

// 设置下一个窗口，这里有两种可能
// 1. elapsed 超过窗口，那么直接创建一个新的窗口
// 2. 没有超过一个新窗口，s.exp + s.expiration
elapsed := ts - s.exp
if elapsed >= s.expiration {
    s.exp = ts + s.expiration
} else {
    s.exp = s.expiration + s.exp
}

漏桶限流

漏桶限流算法指有一个固定大小的漏桶以固定速率流出水，如果漏桶中没有水就不流出（相当于没有请求），如果流通的水过多就把多余的水丢弃（相当于请求过多）。

实现方法

当请求 1 处理结束后, 我们记录下请求 1 的处理完成的时刻, 记为 limiter.last。
当请求2到来，如果此刻的时间与 limiter.last 相比并没有达到 perRequest 的间隔大小，那么 sleep
一段时间即可。sleepFor = per - now.Sub(old.last) > 0

sleepFor = t.perRequest - now.Sub(t.last)
if sleepFor > 0 {
    t.clock.Sleep(sleepFor)
    t.last = now.Add(sleepFor)
} else {
    t.last = now
}

最大松弛量（maxStack）

请求 1 完成后，15ms 后，请求 2 才到来，可以对请求 2 立即处理。请求 2 完成后，5ms 后，请求 3 到来，这个时候距离上次请求还不足
10ms，因此还需要等待 5ms。

// 请求1执行后，15ms，请求2到达，此时sleepFor=-5ms，即有5ms的松弛时间
t.sleepFor += t.perRequest - now.Sub(t.last)
if t.sleepFor > 0 {
    t.clock.Sleep(t.sleepFor)
    t.last = now.Add(t.sleepFor)
    t.sleepFor = 0
} else {
    t.last = now
}