新来的外包，限流算法用的这么6

有态度的马甲

发布于 2025-11-24 14:23:48

750

文章被收录于专栏：精益码农精益码农

CloudFlare介绍限速[1]的文章，讲述了限速的使用场景和运作方式。

最难的是构建一个既高效又匹配需求的算法。

1.流行的限速器[2]

① 固定窗口限速 Fixed Window Counter

跟踪固定时间间隔（如 1 分钟）内的请求数量。一旦达到上限，就会拒绝该窗口中的后续所有请求。

UserCase：可预测流量、低精度需求的简单API，比如云平台会对开发者提供 “免费调用API”的限速额度。

eg：公共天气 API 允许每个用户每分钟 100 次请求，任何额外请求都会返回 “429 请求过多 ”响应。

Drawback：客户端可通过在两个时间窗口的边界堆砌请求（例如，在1min时间窗口的第59秒和下一个1min窗口的第1s都堆砌100 个请求），轻松突破qps=100/min 语义。

固定窗口算法对应最字面意义的qps语义，但是qps漏洞也很明显（很容器在瞬间被突破）。

② 滑动窗口限速 Sliding Window Log

维护每个请求的时间戳日志，并根据滚动时间窗口计算限制。

UserCase：要求高精度的核心系统，如金融交易 API 或欺诈检测机制。

eg：银行 API 限制每小时取款次数为 10 次，每次新请求都要根据最近1小时的取款次数来评估。

Drawback：当扩展到数百万用户或频繁请求时，内存使用量大（可以想象对每一个请求都会产生一个kv窗口计数器，会有一个很大的map），计算成本高。

滑动窗口算法对应严格意义的qps语义，从任意一个请求点切入的统计都试图保持恒定的qps。

那为什么会有漏桶和令牌桶算法？

上面的固定窗口和滑动窗口算法，他们都聚焦在“维持qps”，对于超出qps的流量他们会直接拒绝。

漏桶算法和令牌桶不仅聚焦“维持qps”，同时不完全无脑拒绝：

在突发流量时，能给出等待处理/有暂存令牌迅速处理的行为，也就是能应对突发的流量波动。

③ 漏桶限速 Leaky Bucket

想象一个底部有小孔的水桶，请求（水）被添加到桶中，并以稳定的 “漏水 ”速度进行处理，从而防止突然的洪水泛滥。

UserCase：是平滑流量的理想选择，例如在流媒体服务或支付处理中，可预测的输出是至关重要的。

eg：视频流平台对其内容交付网络的 API 调用进行管理，确保一致的播放质量。

Drawback：不适合处理突发事件，如闪电销售或促销活动。

漏洞算法基于“稳定的漏水机制”，也维持了严格意义的qps语义，但是他有桶，短时的波动流量可凭借桶容量排队依次漏出，超过桶容量的请求还是会被拒绝。

物理学意义（压强/高度因素、动态平衡）不能维持”稳定的漏水机制“，这里的稳定漏水机制是需要技术强制实现。

④ 令牌桶限速[3]

令牌以固定速率生成并存储在一个桶中。每次请求都会消耗一个令牌（令牌产生快于实际请求，桶满多余令牌会被丢弃）；

支持短时间瞬发（只要有令牌）。

UserCase：适合需要处理偶尔出现的流量高峰，同时执行总体限制（如登录尝试或搜索查询）的应用程序接口。

eg：某电子商务网站在结账时允许每秒最多 20 个请求的突发流量，但将总体流量限制在每分钟 100 个请求（r= 1.6, b=20）。

Drawback：需要固定速率补充令牌，技术上稍复杂。

令牌桶通过稳定的投放令牌，也尝试维持了恒定的qps语义，严格上讲令牌桶维持恒定的qps不是依靠稳定的投放令牌，而是消耗令牌。

消耗令牌的速率某些时刻可能就不是恒定的：在突发大流量时，桶中暂存的令牌可以迅速给到请求用(这一瞬间突破qps语义)，而不用像漏桶一样排队等待被处理（因漏水塑形）。

漏桶算法和令牌桶的区别

漏桶算法聚焦于”流量塑形“，有一定量的突发流量对应能力，但不多；

令牌桶算法大部分情况下会产生”流量塑形“的效果，优势是：应对突发流量。

举个例子🌰：容量均为20的漏桶和令牌桶，分别以10/s的速率漏水、投放令牌。

日常流量恰好稳定是10/s，某瞬间突发流量：来了100个请求。

请求迅速堆满漏桶：后80个请求被拒绝，前20个请求被处理（第一个请求迅速被处理，第20个在第2s末被处理完，because恒定的漏水塑形）。

而令牌桶在这一瞬间，因为桶中有暂存令牌，可迅速给到请求使用，在这一瞬间能突破10/s 的qps（第1s放行30个请求，第2s依靠投递令牌放行10个请求，只要请求不自己取消，这突发的流量最后都会被消化掉），因此令牌桶才成为互联网应对突发流量的优质限速算法。

2. 今日快闪：基于gin框架的原生api限速器。

golang内置了一款限速器golang/x/time/rate[4], 基于令牌桶限速算法。

维基百科令牌桶限速器[5]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。

这三种方法都消耗一个令牌,当没有可用令牌时，它们的行为有所不同。