看完这篇,轻松get限流!

2023-05-26 0 193

看完这篇,轻松get限流!

结语:责任编辑推举自【技思庆丰 · 百度控制技术人创作者集】时评。该时评是百度云开发人员街道社区为百度控制技术人与广为开发人员打造出的撷取沟通交流询问处。版块旧友百度控制技术人撷取创作者的控制技术底蕴,与广为开发人员互感悟共高速成长。译者是百度云开发人员街道社区的译者——一头螃蟹。

开闭在保证当代网络通讯的稳定运转中,充分发挥了非常重要的作用。责任编辑企图对此项控制技术做一个剖析,以期更快地了解并应用领域它。

看完这篇,轻松get限流!
看完这篇,轻松get限流!

什么是开闭?

开闭,也叫速度管制(Rate Limiting),是一种管制允诺速度的控制技术。通常用于为保护服务项目另一方面,或在上游服务项目未知无法为保护另一方面的情况下,为保护上游服务项目。

看完这篇,轻松get限流!

为何要开闭?

服务项目需要为保护自己,以防被太多的允诺冲走(不论是蓄意或有意的),进而保持易用性。

举个生活中的范例,某一风景区,平常可能将显然无所谓人赶赴,但是除非到了国庆节假期就门庭若市,这时风景区职员就会实施一连串的开闭措施,来管制进入的客网络流量。为何要这么做呢?假定风景区能容纳1Bazas,现在进来了3Bazas,势必会人声鼎沸,Ossun还会有冲撞交通事故出现。这种的结果就是其他人的新体验都不太好,如果出现了交通事故,风景区可能将还要停用,导致对内不可用。

看完这篇,轻松get限流!

网络情景中,这种的范例也经常出现。比如说直降热卖,通过开闭来管制mammalian和允诺量,进而为保护另一方面或上游系统不被超大型网络流量冲毁。

(一)防止资源枯竭

开闭最常见的一个原因是,通过避免资源枯竭,来提高服务项目的易用性。常见的导致资源枯竭的原因有:

遭受蓄意的攻击(如DDoS攻击、暴力密码猜测攻击等),这些攻击看起来像是来自真实用户,但通常是由僵尸程序或某种脚本机器人生成,往往会在短时间内发起大量的服务项目允诺,导致合法用户无法使用该系统。

非蓄意的(friendly-fire)资源消耗,这可能将由于一些错误的配置,或者人为的误用导致。比如说:上游调用方在应该发起批量允诺的地方,发起了多次简单允诺。

(二)管理配额

许多公共资源(如开放API,服务项目容量等),可能将由多个租户共享。如果没有开闭,每个用户都随心所欲的发出允诺,消耗资源,将导致嘈杂邻居效应(noisy neighbor),使其他用户的服务项目质量变差,甚至得不到服务项目。对每个用户使用开闭,进而为每个用户提供公平的服务项目,而不影响其他用户。

(三)费用控制

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

看完这篇,轻松get限流!

管制键(Limiting Key)

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

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

个特征组合起来形成一个管制键。

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

看完这篇,轻松get限流!

开闭算法

Allow a key to make x requests per y time period

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

(一)漏桶(Leaky Bucket)

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

看完这篇,轻松get限流!

算法过程:

漏桶由一个有限长度的FIFO队列组成。当一个允诺到达时,如果队列中有空间,它就被附加到队列中;否则它将被拒绝。队列的另一端,则以一个恒定的速度漏出/放行允诺。
看完这篇,轻松get限流!

优点:

能够平滑突发网络流量,这使得漏桶特别适合需要削峰填谷的瞬时高mammalian情景(如:整点签到、直降等)

缺点:

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

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

(二)令牌桶(Token Bucket)

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

看完这篇,轻松get限流!

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

算法过程:

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

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

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

(三)简单计数

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

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

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

算法过程:

允诺开始处理时,计数器加一允诺处理完毕时,计数器减一若计数器超过阈值,则直接拒绝该允诺

优点:简单粗暴。

缺点:缺乏灵活性,应用领域情景有限。

(四)固定询问处计数(Fixed Window Counter)

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

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

看完这篇,轻松get限流!

优点:可以保证新的允诺得到处理,而不会被旧的允诺饿死。

缺点:对资源的使用,不能均匀的按时间分布。这导致了边界双倍暴击问题:蓄意用户可以在询问处重置点前后,制造双倍速度的突发允诺,进而瞬间压垮应用领域。

举个范例:假定规划的吞吐量是1分钟3个允诺,即每秒0.05个允诺。蓄意用户在0:59,瞬间发送3个允诺,在1:00,又瞬间发送3个允诺。则在这个1秒瞬间,共发送了6个允诺,远超规划速度,瞬间压垮应用领域。

看完这篇,轻松get限流!

(五)滑动日志(Sliding Logs)

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

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

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

看完这篇,轻松get限流!

优点:能够精确地执行开闭,不受固定询问处边界条件的影响。

缺点:为允诺存储日志,可能将会消耗大量的存储空间,这使得该算法不能很好地扩展以处理大网络流量或防御DoS攻击。

(六)滑动询问处计数(Sliding Window Counter)

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

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

看完这篇,轻松get限流!

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

(七)背压(Back Pressure)

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

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

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

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

丢弃这个允诺缓存这个允诺,并在将来的某一时刻再次发送

案例:TCP滑动询问处

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

看完这篇,轻松get限流!

阻塞调用链(Callstack Blocking)

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

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

TCP阻塞send:内核有一个固定长度的发送缓冲区,缓冲区满时,会阻塞send方法。线程池:提交任务到线程池,线程池满后,会阻塞在提交动作上,这将隐式地阻塞上游的生产者。
看完这篇,轻松get限流!

客户端策略

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

(一)超时重试

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

(二)退避(Backoff)

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

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

指数退避(exponential backoff)

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

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

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

其他的退避模式

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

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

(三)增加抖动(Jitter)

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

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

(四)谨慎重试

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

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

分布式开闭

网络通讯中,可能将需要对服务项目的所有实例进行整体管制,这时就要使用高效的全局存储(如Redis)来跟踪各种管制计数。

看完这篇,轻松get限流!

(一)竞争条件

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

解决方案1:放宽管制

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

解决方案2:会话保持

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

解决方案3:加锁

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

解决方案4:Redis+Lua

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

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

参考资料:

1.开闭:计数器、漏桶、令牌桶三大算法的原理与实战

2.Google Cloud速度管制策略和方式

3.NGINX Rate Limiting

4.Understanding Rate Limiting Algorithms

5.Token bucket-Wikipedia

6.Leaky bucket-Wikipedia

7.Backpressure explained

8.超时、重试和抖动回退

相关文章

发表评论
暂无评论
官方客服团队

为您解决烦忧 - 24小时在线 专业服务