限流算法与实现

[TFdream]

漏桶算法

想象有一个水桶，水桶以一定的速度出水（以一定速率消费请求），当水流速度过大水会溢出（访问速率超过响应速率，就直接拒绝）。

漏桶算法的两个变量：

• 水桶漏洞的大小：rate
• 最多可以存多少的水：burst

令牌桶算法

系统按照恒定间隔向水桶里加入令牌（Token），如果桶满了的话，就不加了。每个请求来的时候，会拿走1个令牌，如果没有令牌可拿，那么就拒绝服务。

参考资料

• Stripe - Scaling your API with rate limiters
• Stripe - Redis Rate Limiter 实现
• 令牌桶算法文章： Token Bucket Algorithm