实现限流的几种方案

实现限流的几种方案

4月 4, 2021
Go, Algorithms, 系统设计

限流是服务在高并发的情况下,通过限制处理请求的速率,以达到保证服务不过载的目的,实现高可用和稳定性的目标。限流的方案一般有计数法、滑动窗口、漏桶、令牌桶几种,其中各有各的特点,通常需要根据场景采用不同的方案。

计数法 #

相对于滑动窗口,计数法也叫固定窗口。就是说接口在固定时间内的访问次数不能超过多少个,在实现的时候,假设限流为每分钟 100 个请求,设置一个开始时间 start 和计数器 counter,每有一个请求 counter++,如果 counter 大于 100 并且此时与开始时间相比小于 1 分钟,则触发限流;如果 counter 大于 100 并且与开始时间相比大于 1 分钟,则重置开始时间 start 和 counter 的值。

img

计数法存在的一个比较严重的问题就是临界点问题,如果有恶意用户在第一个时间段的最后一秒钟触发 100 个请求,在第二个时间段的第一秒钟触发了 100 个请求,那么在短短一秒内其实服务器收到了 200 个请求,并没有触发限流,这种就可能会对服务造成影响。

滑动窗口 #

针对固定窗口的问题进行优化,就产生了滑动窗口的方案。滑动窗口最核心的思想在于,任何时间段的 1 分钟,最多都是 100 个请求。滑动窗口把 100 个请求分摊到了每一个格子,成个格子就是 10 秒钟,就是 6 个格子。counter 值就是可滑动的 6 个格子的总和。

当遇到恶意用户再次在 00:59 请求时,服务可以成功处理 100 个请求,可是到 1:00 时触发 100 个请求时,由于窗口的滑动,counter 总数已经到了第 2- 第7 个格子的和,counter 得到 200 个请求从而触发了限流。可见滑动窗口的时间段永远是最新的 “1 分钟”。只要格子分的粒度足够细,限流实现的精度就越高。

通常考虑使用 Redis 的 zset 结构来实现滑动窗口限流功能。

漏桶(Leaky Bucket) #

漏桶算法很形象,就是一个漏桶,它的桶里是请求的流量,然后按照固定速率漏掉的水滴(看到固定速率我们就知道肯定像固定窗口一样,有更优解了,我们下面会继续说)。漏掉的水滴,就是服务的处理速度,我们发现漏桶的特点很明显:

  1. 可以任意速率接收大量请求,瞬间也可以。
  2. 容量是固定的,超出了就会触发限流;
  3. 流量的处理速度是匀速的。

这种特性,特别适合有生产者-消费者的场景,Uber 针对漏桶开源了一个 go语言的包 uber-go/ratelimit,源码实现可以参考这篇博客

令牌桶(Token Bucket) #

令牌桶限流可能是实际工作中最可能遇到的方式了,与漏桶最大不同的是,令牌桶不是以匀速来处理流量的,而装的是令牌,如下图,生成令牌的速度是恒定的,每有一个请求过来时,会从桶里取走一个令牌,当桶里没有令牌时,则触发限流。

令牌桶算法

可见,令牌桶即可以处理一定程度的突发流量(漏桶),也可以解决滑动时间段计数问题(滑动窗口),它拥有其他几个限流算法的优点,复杂度就是多了一个“令牌”的概念。

Go 扩展库也提供了一个基于令牌桶算法的限流器实现 time/rate,在 Go 的官方实现里面,有针对令牌桶做了优化,比如生成令牌的速率不一定是匀速的,具体实现可以参考这篇博客。下面简单介绍下使用:

安装方法

go get golang.org/x/time/rate

初始化

// 每秒放入 10 个 token,桶的容量为 1
limiter := NewLimiter(10, 1);

// Every 表示放入 token 速率时间粒度;
limit := Every(100 * time.Millisecond);
limiter := NewLimiter(limit, 1);

触发限流时有三种处理方式:

  • wait
  • allow
  • reserve

Wait/WaitN 示例 #

Wait 获取 token 时如果数组不足(小于N),将会阻塞一段时间,直至 token 满足条件, 如果充足则直接返回,阻塞时间可以通过 context 设置。

func main() {
    limiter := rate.NewLimiter(10, 1)
    ctx, _ := context.WithCancel(context.TODO())
    for {
        l.Wait(ctx)
        time.Sleep(200 * time.Millisecond)
        fmt.Println(time.Now().Format("2016-01-02 15:04:05.000"))
    }
}

Allow/AllowN 示例 #

Allow获取 token 充足返回 true,同时 token 减少,否则返回 false,不会阻塞。

Reserve/ReserveN 示例 #

ReserveN 的用法就相对来说复杂一些,当调用完成后,无论 Token 是否充足,都会返回一个 Reservation 对象。

func (r *Reservation) OK() bool // 判断是否获取到token

// Delay is shorthand for DelayFrom(time.Now()).
func (r *Reservation) Delay() time.Duration // 获取延迟等待时间,此时Cancel不起作用
func (r *Reservation) DelayFrom(now time.Time) time.Duration

// Cancel is shorthand for CancelAt(time.Now()).
func (r *Reservation) Cancel() // 取消,将获取的Token重新放入桶中
func (r *Reservation) CancelAt(now time.Time)
本文共 1531 字,上次修改于 Jul 9, 2024,以 CC 署名-非商业性使用-禁止演绎 4.0 国际 协议进行许可。

相关文章

» Go 语言的 MPG 并发调度模型

» 了解下 Protobuf 相关概念

» Go 程序是怎样跑起来的?

» Go 语言的垃圾回收机制概览

» Go 语言的内存管理机制概览