常见的几种限流算法

如上图所示：每个时间片段为1s。在第一个时间单位内的前800ms只有一次请求，后200ms（800ms-1s范围内）内承载999次请求，而第二个时间单位内前200ms承载1001-2000次共1000个请求。这样系统在400ms（第800ms到1200ms时间范围内）内共承载了1999次用户请求，此访问量已经达到系统所能承载的最大QPS 1000次请求的两倍。

滑动窗口算法

滑动窗口算法的时间单位不再是彼此独立，而是步步递进，彼此重叠。

滑动窗口算法将固定窗口算法的时间单位进一步细化，如将1秒再分为10个时间网格，每个网格占用100ms的时间。第一个时间单位为0ms-1000ms、第二个时间单位为100ms-1100ms、第三个时间单位为200ms-1200ms，以此类推。每个时间单位的请求总量都需小于设定的最大请求量。

弊端：

由于滑动窗口算法每次都需要统计单位时间的请求量，开销远大于固定窗口算法，所以在真实的业务环境中需要慎重使用滑动窗口算法。

漏桶算法

漏桶算法以绝对平均的速度处理用户请求，无论用户请求有多少，最终消费/处理用户请求的速率是固定不变的。

package main

import (
	"fmt"
	"github.com/gin-gonic/gin"
	"go.uber.org/ratelimit"
	"time"
)

// 定义全局限流器对象
var rateLimit ratelimit.Limiter

// 在 gin.HandlerFunc 加入限流逻辑
func leakyBucket() gin.HandlerFunc {
	prev := time.Now()
	return func(c *gin.Context) {
		now := rateLimit.Take()
		fmt.Println("时间间隔：", now.Sub(prev)) // 为了打印时间间隔
		prev = now                          // 记录上一次的时间，没有这个打印的会有问题
	}
}

func main() {
	rateLimit = ratelimit.New(10)
	r := gin.Default()
	r.GET("/ping", leakyBucket(), func(c *gin.Context) {
		c.JSON(200, true)
	})
	r.Run() // listen and serve on 0.0.0.0:8080 (for windows "localhost:8080")
}

运行，然后使用ab来进行压测：

ab -n 10 -c 2 http://127.0.0.1:8080/ping

其中－n表示请求数，－c表示并发数

上一个请求处理的时间是at

每秒请求量(RPS)

弊端

在真实的业务场景中，漏桶算法面对合法的突发流量，有点捉襟见肘。

令牌桶算法

这两种方法(漏桶和令牌桶)看起来很像，不过还是有区别的。漏桶流出的速率固定，而令牌桶只要在桶中有令牌，那就可以拿。也就是说令牌桶是允许一定程度的并发的，比如同一个时刻，有100个用户请求，只要令牌桶中有100个令牌，那么这100个请求全都会放过去。令牌桶在桶中没有令牌的情况下也会退化为漏桶模型，实际应用中令牌桶应用较为广泛。

对比

来自常用限流算法

来自限流算法实践(360云计算平台)

来自图解+代码|常见限流算法以及限流在单机分布式场景下的思考

来自一文搞懂高频面试题之限流算法，从算法原理到实现，再到对比分析

Go 中基于 IP 地址的 HTTP 请求限流

nginx的限流策略以及google的guava限流策略。

市面上一些比较成熟的限流工具和框架：

Google的Guava中基于令牌桶实现的限流组件，拿来即用；Guava 是一个 Google 开源项目，包含了若干被 Google 的 Java 项目广泛依赖的核心库，其中的 RateLimiter 提供了令牌桶算法实现：平滑突发限流 (SmoothBursty) 和平滑预热限流 (SmoothWarmingUp) 实现。
Alibaba开源的面向分布式服务架构的流量控制框架Sentinel，基于滑动窗口实现
Nginx：对于 Nginx 接入层限流可以使用 Nginx 自带了两个模块：1. 连接数限流模块 ngx_http_limit_conn_module； 2. 漏桶算法实现的请求限流模块 ngx_http_limit_req_module

高并发场景下限流，常见的限流算法、方案解析！