新来的外包，限流算法用的这么6
1.流行的限速器
① 固定窗口限速 Fixed Window Counter
跟踪固定时间间隔（如 1 分钟）内的请求数量，一旦达到上限，就会拒绝该窗口中的后续所有请求。
1_VsdNn5KGd1A0rIfbczGy8Q.gif
UserCase： 可预测流量、低精度需求的简单API，比如云平台会对开发者提供 “免费调用API”的限速额度。
eg： 公共天气 API 允许每个用户每分钟 100 次请求，任何额外请求都会返回 “429 请求过多 ”响应。
Drawback： 客户端可通过在两个时间窗口的边界堆砌请求（例如，在1min时间窗口的第59秒和下一个1min窗口的第1s都堆砌100 个请求）， 轻松突破qps=100/min 语义。
固定窗口算法对应最直观意义的qps语义，但是qps漏洞也很明显。
② 滑动窗口限速 Sliding Window Log
维护每个请求的时间戳日志，并根据滚动时间窗口计算限制。
1_tmaCfNHgzaAJNop4Aa2afA.gif
UserCase：要求高精度的核心系统，如金融交易 API 或欺诈检测机制。
eg： 银行 API 限制每小时取款次数为 10 次，每次新请求都要根据最近1小时的取款次数来评估。
Drawback： 当扩展到数百万用户或频繁请求时，内存使用量大（可以想象对每一个请求都会产生一个kv窗口计数器），计算成本高。
滑动窗口限速器对应严格意义的qps语义，从任意一个请求点切入的统计都试图保持恒定的qps， 计算成本高。
那为什么会有漏桶和令牌桶算法？
上面的固定窗口和滑动窗口算法，他们都聚焦在“维持qps”， 对于超出qps的流量他们会直接拒绝。
漏桶算法和令牌桶不仅聚焦“维持qps”， 同时不完全无脑拒绝：
在突发流量时，能给出等待处理/有暂存令牌迅速处理的行为， 也就是能应对突发的流量波动。
③ 漏桶限速 Leaky Bucket
想象一个底部有小孔的水桶，请求（水）被添加到桶中，并以稳定的 “漏水 ”速度进行处理，从而防止突然的洪水泛滥。
1_UioRG8-qID51i0rEOPVh-w.gif
UserCase： 是平滑流量的理想选择，例如在流媒体服务或支付处理中，可预测的输出是至关重要的。
eg： 视频流平台对其内容交付网络的 API 调用进行管理，确保一致的播放质量。
Drawback： 不适合处理突发事件，如闪电销售或促销活动。
漏洞算法基于“稳定的漏水机制”，也维持了严格意义的qps语义，但是他有桶，短时的波动流量可凭借桶容量排队依次漏出， 超过桶容量的请求还是会被拒绝。
物理学意义（压强/高度因素、动态平衡）不能维持”稳定的漏水机制“， 这里的稳定漏水机制是需要技术强制实现。
④ 令牌桶限速
令牌以固定速率生成并存储在一个桶中。每次请求都会消耗一个令牌；支持短时间瞬发（只要有令牌）。令牌产生快过实际请求，桶满会被丢弃。
1_7cDKq5yh5RD0ygvb3mVwfQ.gif
UserCase： 非常适合需要处理偶尔出现的流量高峰，同时执行总体限制（如登录尝试或搜索查询）的应用程序接口。
eg： 某电子商务网站在结账时允许每秒最多 20 个请求的突发流量，但将总体流量限制在每分钟 100 个请求（r= 1.6, b=20）。
Drawback： 需要固定速率补充令牌，技术上有点复杂。
令牌桶通过稳定的投放令牌，也尝试维持了恒定的qps语义，严格上讲他维持恒定的qps不是依靠稳定的投放令牌， 而是消耗令牌。
消耗令牌的速率某些时刻可能就不是恒定的：在突发大流量时，桶中暂存的令牌可以迅速给到请求用(这一瞬间突破qps语义)，而不用像漏桶一样排队等待被处理（因流量漏水塑形）。
漏桶算法和令牌桶的区别
漏桶算法聚焦于”流量塑形“，有一定量的突发流量对应能力，但不多；
令牌桶算法 大部分情况下会产生”流量塑形“的效果，能应对突发大流量。
举个例子：
容量均为20的漏桶和令牌桶， 分别以10/s的速率漏水、投放令牌。
日常流量恰好稳定是10/s，某瞬间突发流量： 来了100个请求。
请求迅速堆满漏桶：后80个请求被拒绝，前20个请求被处理（第一个请求迅速被处理，第20个在第2s末被处理完，beacuse漏水塑形）。
而令牌桶在这一瞬间，因为桶中有暂存令牌， 可迅速给到请求使用，在这一瞬间能突破10/s
的qps（第1s放行30个请求，第2s依靠令牌放行10个请求，只要请求不自己取消，这突发的流量最后都会被消化掉）， 因此令牌桶才成为互联网突发流量的优质限速算法。
2. 今日快闪：基于gin框架的原生api限速器
golang内置了一款限速器golang/x/time/rate, 基于令牌桶限速算法。
维基百科令牌桶限速器
Think in this way, someone put 1 candy per second(r) in your bucket, then you can eat only 1 candy per sec. If your bucket can hold 10(b) candies and if you haven't eaten any of them for a while, your bucket will be full then you can eat 10 candies as fast as you can eat at a time.
将该限速器应用到gin框架上：
package main
import (
"github.com/gin-gonic/gin"
"golang.org/x/time/rate"
)
func RateLimiter() gin.HandlerFunc {
limiter := rate.NewLimiter(10, 30)
return func(c *gin.Context) {
if limiter.Allow() {
c.Next()
} else {
c.JSON(http.StatusTooManyRequests, gin.H{
"message": "Limite exceed",
})
}
}
func NewLimiter(r Limit, b int) *Limiter 限速器控制事件发生的频率。
它实现了一个大小为 b 的 “令牌桶”，最初是满的，并以每秒 r 个令牌的速度重新装满。Limiter对多个goroutine同时使用是安全的。
Limiter主要有三个方法，Allow、Reserve、Wait,大多数时候开发者应该使用Wait。
这三种方法都消耗一个令牌,当没有可用令牌时，它们的行为有所不同。
如果没有可用的令牌，Allow 将返回 false。
如果没有可用的令牌，Reserve 将返回未来令牌的预留以及调用者在使用它之前必须等待的时间。
如果没有可用的令牌，则 Wait 会阻塞，直到可以获得令牌或其关联的 context.Context 被取消。
方法AllowN、ReserveN 和WaitN 消耗n 个令牌。
2.1 使用http基准测试工具wrk压测
wrk -t12 -c400 -d30s http://localhost:8080/themes/2
运行基准测试 30 秒，使用 12 个线程，并保持 400 个 HTTP 连接打开。
① 不加限速中间件：
在此压力下，宏观的qps：250
② 将RateLimiter应用到可能被刷单的API
r.GET("/themes/:id", RateLimiter(), func(c *gin.Context) {
......
})
在r=10， b=30的令牌桶设定下，大部分请求都被迅速拒绝了，显得qps很大。