看完这篇,轻松get限流!

限流在确保现代分布式系统的稳定运行中,发挥了至关重要的作用。本文试图对这项技术做一个梳理,以便更好的了解并应用它。

1. 什么是限流?

限流,也叫速率限制(Rate Limiting),是一种限制请求速率的技术。通常用于保护服务自身,或在下游服务已知无法保护自身的情况下,保护下游服务

2. 为什么要限流?

服务需要保护自己,以免被太多的请求淹没(无论是恶意或无意的),从而保持可用性。

举个生活中的例子,某个景区,平时可能根本没什么人前往,但是一旦到了国庆假日就人满为患,这时景区管理人员就会实施一系列的限流举措,来限制进入的人流量。为什么要这么做呢?假设景区能容纳 1 万人,现在进去了 3 万人,势必摩肩接踵,搞不好还会有踩踏事故发生。这样的结果就是所有人的体验都不好,如果发生了事故,景区可能还要关闭,导致对外不可用

互联网场景中,这样的例子也随处可见。比如秒杀抢购,通过限流来限制并发和请求量,从而保护自身或下游系统不被巨型流量冲垮。

2.1 防止资源枯竭

限流最常见的一个原因是,通过避免资源枯竭,来提高服务的可用性。常见的导致资源枯竭的原因有:

  1. 遭受恶意的攻击(如DDoS攻击、暴力密码猜测攻击等),这些攻击看起来像是来自真实用户,但通常是由僵尸程序或某种脚本机器人生成,往往会在短时间内发起大量的服务请求,导致合法用户无法使用该系统。
  2. 非恶意的(friendly-fire)资源消耗,这可能由于一些错误的配置,或者人为的误用导致。比如:上游调用方在应该发起批量请求的地方,发起了多次简单请求。

2.2 管理配额

许多公共资源(如开放API,服务容量等),可能由多个租户共享。如果没有限流,每个用户都随心所欲的发出请求,消耗资源,将导致嘈杂邻居效应(noisy neighbor),使其他用户的服务质量变差,甚至得不到服务。

对每个用户使用限流,从而为每个用户提供公平的服务,而不影响其他用户。

2.3 费用控制

在按使用付费模式中,底层资源能够自动伸缩以满足需求,限流通过对资源扩展设置虚拟上限来帮助控制运营成本。如果没有限流,资源可能会不成比例地扩展(比如配置错误,或者实验失控),从而导致指数级的账单

3. 限制键(Limiting Key)

使用限流时,第一步要做的是选择一个合适的限制键。某些场合中,限制键有其他叫法,比如:条件、过滤器等。

本质上限制键是一个用于计数的标识,也是限流算法所作用的对象。比如当基于IP或者用户进行限流,这里IP地址或者用户ID就是一个限制键。

理论上,任何可从请求中提取的特征都可以用作限制键,比如来源IP地址、用户、地区、API Key,甚至是一个query参数。也可以将多个特征组合起来形成一个限制键。

当确定好限制键后,就可以根据应用的流量特征,选择合适的限流算法。当达到限制时,你需要选择如何处理这些请求,比如:丢弃请求,或者向调用方返回一个限制信号(比如 HTTP 429 响应

4. 限流算法

Allow a key to make x requests per y time period

一般来说,速率是一段时间内发生次数的简单计数。有几种不同的技术用于测量和限制速率,每种技术都有自己的用途和含义

4.1 漏桶(Leaky Bucket)

漏桶算法是网络世界中流量整形(Traffic Shaping)或速率限制(Rate Limiting)时经常使用的一种算法,它的主要目的是控制数据注入到网络的速率,平滑网络上的突发流量(Bursty Flow)。漏桶算法提供了一种机制,通过它,突发流量可以被整形为一个稳定的流量。

算法过程

  1. 漏桶由一个有限长度的FIFO队列组成
  2. 当一个请求到达时,如果队列中有空间,它就被附加到队列中;否则它将被拒绝
  3. 队列的另一端,则以一个恒定的速率漏出/放行请求

优点

能够平滑突发流量,这使得漏桶特别适合需要削峰填谷的瞬时高并发场景(如:整点签到、秒杀等)

缺点

  1. 资源利用率低:漏桶并不能高效地利用可用的资源。因为它只在固定的时间间隔放行请求,所以在很多情况下,流量非常低,即使不存在资源争用,也无法有效地消耗资源。
  2. 饥饿问题:当短时间内有大量突发请求,即使服务器没有任何负载,每个请求也需要在队列中等待一段时间才能响应。

举个例子:平时访问某个网站,如果有多个用户同时访问,这时虽然服务器没有什么负载,但排在后面的客户请求无法被立即响应,这样网站看起来就很慢,用户体验就很差。

4.2 令牌桶(Token Bucket)

令牌桶算法很容易和漏桶算法错误地混淆在一起。和漏桶一样,令牌桶也被用于流量整形和速率限制。但实际上,这两种算法具有截然不同的特性,它们之间最主要的差别在于:漏桶通过平滑流量强行限流(不允许突发通过),而令牌桶在限流的同时还允许某种程度的突发传输(允许突发通过)。

令牌桶的策略,简单来说就是"广积粮":平时存粮,以备灾年之用(应对突发)

算法过程

  1. 算法使用一个固定容量的桶
  2. 只要桶不满,系统就以一个恒定的速率(比如每秒)向桶中添加令牌
  3. 当请求到来时,就从桶中拿走1个或多个令牌,若没有可用令牌,就拒绝该请求

优点

允许突发流量。应用程序在本质上往往是突发性的,当有突发流量时,只要桶里的令牌足够,就能处理,因此能够更高效的利用底层资源。

举个例子:假设令牌桶的容量为20,令牌恢复速度为5个/秒。正常情况下,系统可以处理持续的每秒5个请求,也可以处理每隔4秒一次性20个请求的突发情况。

4.3 简单计数

最简单的限流算法就是简单计数了,常被用于池类资源场景,如:线程池,连接池等。这类场景的典型特征是资源用完放回。

举个生活中常见的例子:国庆期间,某景区限流,最多只允许1W人进入,当到达1W人后,每出来一个人,才允许再进入一个人

算法只需为计数器设置一个阈值(通常就是底层资源的可用量),并为请求做简单计数

算法过程

  1. 请求开始处理时,计数器加一
  2. 请求处理完毕时,计数器减一
  3. 若计数器超过阈值,则直接拒绝该请求

优点
简单粗暴

缺点
缺乏灵活性,应用场景有限

4.4 固定窗口计数(Fixed Window Counter)

算法使用一个固定大小的时间窗口(如1分钟),并跟踪窗口内的请求数。每个传入的请求都将增加窗口的计数器,如果计数器超过阈值,则该请求被拒绝。

窗口通常由当前时间戳的下限定义,因此10:01:06和60秒的窗口长度将在10:01:00窗口中。每当时间到达一个新的窗口时,计数器被重置。

优点

可以确保新的请求得到处理,而不会被旧的请求饿死

缺点

对资源的使用,不能均匀的按时间分布。这导致了边界双倍暴击问题:恶意用户可以在窗口重置点前后,制造双倍速率的突发请求,从而瞬间压垮应用。

举个例子:假设规划的吞吐量是1分钟3个请求,即每秒0.05个请求。恶意用户在0:59,瞬间发送3个请求,在1:00,又瞬间发送3个请求。则在这个1秒瞬间,共发送了6个请求,远超规划速率,瞬间压垮应用

4.5 滑动日志(Sliding Logs)

滑动日志算法通过实时滚动窗口,即精确地计算当前时刻的窗口(而不是由时间戳下限定义的固定窗口),从而消除了静态窗口边界,解决了固定窗口的边界双倍暴击问题。

算法跟踪每个请求的时间戳日志。这些日志通常存储在FIFO队列中,或者按时间排序的散列集或表中。当一个请求到来时,先裁减掉1分钟(假设限速器基于1分钟)前的日志,剩余的日志总数就代表了当前的实时窗口计数,若超过阈值,则请求被拒绝,否则将请求的时间戳添加到日志中。

举个例子:假设在1:20来了一个请求,但在0:20~1:20的时间窗口内,已经有3个请求,因此当前请求被拒绝。时间来到1:26,此时1分钟前的日志0:25被裁剪掉,因此当前窗口中只有0:45和1:10两条日志,于是请求被接受。

优点

能够精确地执行限流,不受固定窗口边界条件的影响。

缺点

为请求存储日志,可能会消耗大量的存储空间,这使得该算法不能很好地扩展以处理大流量或防御DoS攻击

4.6 滑动窗口计数(Sliding Window Counter)

类似于滑动日志,但内存效率更高。该算法结合了固定窗口的低处理成本优点,以及滑动日志的改进边界条件优点。

算法不再为每个请求单独保存一个时间戳日志,而是将相同时间戳的日志合并(这是大流量下节省内存的关键),每个日志记录时间戳和该时间戳上发生的请求数。通过对窗口中的所有日志的请求数求和,即可得到当前的实时窗口计数。

优点

提供了灵活性和良好的性能。避免了漏桶的饥饿问题和固定窗口的边界双倍暴击问题

4.7 背压(Back Pressure)

背压是一种阻碍请求通过的反向压力,通常出现在请求速度快于处理速度的上下文中。

它不是一种单纯的限流策略,因为这种策略不是服务器单独完成的,而是需要服务器和客户端合作来应对:

  1. 服务器仍然负责限流的部分。不同的是,当服务器压力很大,无法处理更多请求的时候,需要向客户端传递这种压力信号(称之为背压信号),通过响应(如HTTP 429)反向传导给客户端。
  2. 然后压力就来到了客户端,客户端需要理解这种反馈,并做出适当的措施,以降低其请求速率,从而适配服务器的处理能力。

客户端可以进行的措施包括:

  1. 丢弃这个请求
  2. 缓存这个请求,并在将来的某个时刻再次发送

案例:TCP滑动窗口

一个著名的案例是TCP滑动窗口:接收端在每次收到一个数据包后,都会在ACK中带上自己的接口窗口大小,发送方收到ACK后,根据接收方通告的窗口大小,调整自己的发送窗口大小,以动态适配接收方的处理能力。

阻塞调用链(Callstack Blocking)

上面描述的机制实现了一种显示的生产者和消费者的协调机制。

除此之外,还存在一种隐式的协调机制,即阻塞调用链(Callstack Blocking),当下游无法处理时直接阻塞上游。下面是一些例子:

  1. TCP阻塞send:内核有一个固定长度的发送缓冲区,缓冲区满时,会阻塞 send 方法
  2. 线程池:提交任务到线程池,线程池满后,会阻塞在提交动作上,这将隐式地阻塞上游的生产者

5. 客户端策略

除了上面描述的背压策略,客户端还需要在网络超时的情况下,参与到限流过程。

5.1 超时重试

分布式系统存在特有的三态概念,即成功 ,失败,和超时无响应(结果未知)。当超时发生时,客户端通常需要重试,就和收到背压信号时的处理类似。

5.2 退避(Backoff)

重试是“自私的”。 换句话说,在客户端重试时,它将花费更多的服务器时间来获得更大的成功几率。在故障很少发生或瞬时发生的情况下,这并不是问题,因为重试请求的总数很小。但如果故障是由过载引起的,重试会增加负载,导致情况进一步恶化。

重试的首选解决方案是退避:客户端不会立即积极地重试,而是在两次尝试之间等待一段时间。

指数退避(exponential backoff)

最佳的退避模式是指数退避,即每次尝试后的等待时间都呈指数级增加。这可能导致很长的退避时间,因为指数函数增长很快。为了避免重试太长时间,实现通常会设置一个上限值。

timeout = min(base * pow(2, attempt), threshold)

使用这种方法的一个经典案例是:TCP超时重传时采用的Karn算法

其他的退避模式

  1. 恒定时间:在每次尝试之间等待恒定的时间。例如,使用1秒的恒定延迟,那么重试将在1秒、2秒、3秒、4秒等发生
  2. 斐波纳契:使用斐波纳契数,来获得对应于当前重试的等待时长,比如1,1,2,3,5,8,13,等等

这个Python退避包提供了一些常用的解决方案

5.3 增加抖动(Jitter)

如果许多客户端同时发出基于时间表的请求(比如每小时查询一次),那么可能会造成周期性的惊群效应 (thundering herd)。该效应指的是由于突发事件而导致的突发的流量激增的情况。

解决方法是:通过在超时时间上增加额外的随机值(抖动),以使重试在时间上有所分散,从而避免这种情况的发生。

5.4 谨慎重试

重试会加重从属系统上的负载:如果对系统的调用超时,且该系统过载,则重试会导致过载问题恶化,而非好转。
下面是一些建议:

  1. 仅在观察到依赖项运行状况良好时才进行重试,从而避免了这种负载加剧的问题。
  2. 当重试无助于提高可用性时,应停止重试。

6. 分布式限流

分布式系统中,可能需要对服务的所有实例进行整体限制,这时就要使用高效的全局存储(如Redis)来跟踪各种限制计数

6.1 竞争条件

集中式数据存储最常见的一个问题是高并发场景下的竞争条件问题。当使用一种简单的“get-then-set”方法,就会发生这种问题。在这种方法中,先获得当前的限流计数器,将其递增,然后写回存储。问题在于,这一系列操作并非原子的,中间可能会插入额外的请求,每个请求都试图写入过期的计数器。这使得消费者可以通过高频的请求来绕过限流控制。

解决方案1:放宽限制

允许计数器超过阈值, 可以设置一个容忍区间(如1%)。举个例子:设定上限为200,但是允许203个请求。
这也许算不上解决方案,但某些场景确实能用。

解决方案2:会话保持

通过在负载均衡器中设置会话保持,以便确保来自同一个用户的请求总是由同一个节点串行处理。
缺点:缺乏容错能力、节点过载时的扩展性问题

解决方案3:加锁

解决竞争条件,最常用的方法是加锁,以防止计数器的并发访问。
缺点:消费者发出的其他请求的响应延迟,此外锁会很快成为一个严重的性能瓶颈,并且不能很好地伸缩。

解决方案4:Redis+Lua

当使用Redis作为数据存储时,可以搭配Lua脚本实现“get-then-set”原子化。Redis将整个Lua脚本作为一个命令原子执行,无需担心并发

local curr_count = tonumber(redis.call('GET', key) or "0")

if curr_count + 1 > limit then
    -- 限流
    return 0
else
    -- 放行
    redis.call("INCRBY", key, 1)
    redis.call("EXPIRE", key, 2)
    return 1
end

参考

限流:计数器、漏桶、令牌桶 三大算法的原理与实战
Google Cloud 速率限制策略和方式
NGINX Rate Limiting
Understanding Rate Limiting Algorithms
Token bucket - Wikipedia
Leaky bucket - Wikipedia
Backpressure explained
超时、重试和抖动回退

版权声明:
作者:一只小黄鱼
链接:https://jkboy.com/archives/13642.html
来源:随风的博客
文章版权归作者所有,未经允许请勿转载。

THE END
分享
二维码
打赏
海报
看完这篇,轻松get限流!
限流,也叫速率限制(Rate Limiting),是一种限制请求速率的技术。通常用于保护服务自身,或在下游服务已知无法保护自身的情况下,保护下游服务
<<上一篇
下一篇>>