看完这篇，轻松get限流！

限流在确保现代散布式系统的稳定运转中，发挥了相当重要的感化。本文试图对这项技术做一个梳理，以便更好地领会并利用它。

什么是限流？

限流，也叫速度限制（Rate Limiting），是一种限制请求速度的技术。凡是用于庇护办事本身，或鄙人流办事已知没法庇护本身的情况下，庇护下流办事。

为什么要限流？

办事需要庇护自己，免得被太多的请求沉没（不管是恶意或无意的），从而连结可用性。

举个生活中的例子，某个景区，平常能够底子没什么人前往，可是一旦到了国庆沐日就人满为患，这时景区治理职员就会实施一系列的限风行动，来限制进入的人流量。为什么要这么做呢？假定景区能包容1万人，现在进去了3万人，势必摩肩相继，搞欠好还会有踩踏变乱发生。这样的成果就是一切人的体验都欠好，假如发生了变乱，景区能够还要封闭，致使对外不成用。

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

（一）避免资本干涸

限流最多见的一个缘由是，经过避免资本干涸，来进步办事的可用性。常见的致使资本干涸的缘由有：

蒙受恶意的进犯（如DDoS进犯、暴力密码猜测进犯等），这些进犯看起来像是来自实在用户，凡是是是由僵尸法式或某种剧本机械人天生，常常会在短时候内倡议大量的办事请求，致使正当用户没法利用该系统。

非恶意的（friendly-fire）资本消耗，这能够由于一些毛病的设置，大概报酬的误用致使。比如：上游挪用方在应当倡议批量请求的地方，倡议了屡次简单请求。

（二）治理配额

很多公共资本（如开放API，办事容量等），能够由多个租户同享。假如没有限流，每个用户都为所欲为的发出请求，消耗资本，将致使喧闹邻人效应（noisy neighbor），使其他用户的办事质量变差，甚至得不到办事。对每个用户利用限流，从而为每个用户供给公允的办事，而不影响其他用户。

（三）用度控制

在按利用付费形式中，底层资本可以自动伸缩以满足需求，限畅经过对资本扩大设备虚拟上限来帮助控制运营本钱。假如没有限流，资本能够会不成比例地扩大（比如设置毛病，大概尝试失控），从而致使指数级的账单。

限制键（Limiting Key）

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

本质上限制键是一个用于计数的标识，也是限流算法所感化的工具。比如当基于IP大概用户停止限流，这里IP地址大概用户ID就是一个限制键。

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

当肯定好限制键后，便可以按照利用的流量特征，挑选合适的限流算法。当到达限制时，你需要挑选若何处置这些请求，比如：抛弃请求，大概向挪用方返回一个限制信号（比如HTTP 429响应）

限流算法

Allow a key to make x requests per y time period

一般来说，速度是一段时候内发生次数的简单计数。有几种分歧的技术用于丈量和限制速度，每种技术都有自己的用处和寄义。

（一）漏桶（Leaky Bucket）

漏桶算法是收集天下中流量整形（Traffic Shaping）或速度限制（Rate Limiting）时经常利用的一种算法，它的首要目标是控制数据注入到收集的速度，平滑收集上的突发流量（Bursty Flow）。漏桶算法供给了一种机制，经过它，突发流量可以被整形为一个稳定的流量。

算法进程：

• 漏桶由一个有限长度的FIFO行列组成。
• 当一个请求到达时，假如行列中有空间，它就被附加到行列中；否则它将被拒绝。
• 行列的另一端，则以一个恒定的速度漏出/放行请求。

优点：

可以平滑突发流量，这使得漏桶出格合适需要削峰填谷的瞬时高并发场景（如：整点签到、秒杀等）

弱点：

1. 资本操纵率低：漏桶并不能高效地操纵可用的资本。由于它只在牢固的时候间隔放行请求，所以在很多情况下，流量很是低，即使不存在资本争用，也没法有用地消耗资本。
2. 饥饿题目：当短时候内有大量突发请求，即使办事器没有任何负载，每个请求也需要在行列中期待一段时候才能响应。

举个例子：平常拜候某个网站，倘使有多个用户同时拜候，这时虽然办事器没有什么负载，但排在前面的客户请求没法被立即响应，这样网站看起来就很慢，用户体验就很差。

（二）令牌桶（Token Bucket）

令牌桶算法很轻易和漏桶算法毛病地混淆在一路。和漏桶一样，令牌桶也被用于流量整形和速度限制。但现实上，这两种算法具有截然分歧的特征，它们之间最首要的不同在于：漏桶经过平滑流量强行限流（不答应突发经过），而令牌桶在限流的同时还答应某种水平的突发传输（答应突发经过）。

令牌桶的战略，简单来说就是“广积粮”：平常存粮，以备灾年之用（应对突发）

算法进程：

• 算法利用一个牢固容量的桶。
• 只要桶不满，系统就以一个恒定的速度（比如每秒）向桶中增加令牌。
• 当请求到来时，就从桶中拿走1个或多个令牌，若没有可用令牌，就拒绝该请求。

优点：答应突发流量。利用法式在本质上常常是突发性的，当有突发流量时，只要桶里的令牌充足，就能处置，是以可以更高效的操纵底层资本。

举个例子：假定令牌桶的容量为20，令牌规复速度为5个/秒。一般情况下，系统可以处置延续的每秒5个请求，也可以处置每隔4秒一次性20个请求的突发情况。

（三）简单计数

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

举个生活中常见的例子：国庆时代，某景区限流，最多只答应1W人进入，当到达1W人后，每出来一小我，才答应再进入一小我。

算法只需为计数器设备一个阈值（凡是就是底层资本的可用量），并为请求做简单计数。

算法进程：

• 请求起头处置时，计数器加一
• 请求处置终了时，计数器减一
• 若计数器跨越阈值，则间接拒绝该请求

优点：简单粗鲁。

弱点：缺少灵活性，利用处景有限。

（四）牢固窗口计数（Fixed Window Counter）

算法利用一个牢固巨细的时候窗口（如1分钟），并跟踪窗口内的请求数。每个传入的请求都将增加窗口的计数器，假如计数器跨越阈值，则该请求被拒绝。

窗口凡是由当前时候戳的下限界说，是以10:01:06和60秒的窗口长度将在10:01:00窗口中。每那时候到达一个新的窗口时，计数器被重置。

优点：可以确保新的请求得处处置，而不会被旧的请求饿死。

弱点：对资本的利用，不能均匀的按时候散布。这致使了鸿沟双倍暴击题目：恶意用户可以在窗口重置点前后，制造双倍速度的突发请求，从而瞬间压垮利用。

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

（五）滑动日志（Sliding Logs）

滑动日志算法经过实时转动窗口，即切确地计较当前时辰的窗口（而不是由时候戳下限界说的牢固窗口），从而消除了静态窗口鸿沟，处理了牢固窗口的鸿沟双倍暴击题目。

算法跟踪每个请求的时候戳日志。这些日志凡是存储在FIFO行列中，大概按时候排序的散列集或表中。当一个请求到来时，先淘汰掉1分钟（假定限速器基于1分钟）前的日志，残剩的日志总数就代表了当前的实时窗口计数，若跨越阈值，则请求被拒绝，否则将请求的时候戳增加到日志中。

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

优点：可以切确地履行限流，不受牢固窗口鸿沟条件的影响。

弱点：为请求存储日志，能够会消耗大量的存储空间，这使得该算法不能很好地扩大以处置大流量或防御DoS进犯。

（六）滑动窗口计数（Sliding Window Counter）

类似于滑动日志，但内存效力更高。该算法连系了牢固窗口的低处置本钱优点，以及滑动日志的改良鸿沟条件优点。

算法不再为每个请求零丁保存一个时候戳日志，而是将不异时候戳的日志合并（这是大流量下节省内存的关键），每个日志记录时候戳和该时候戳上发生的请求数。经过对窗口中的一切日志的请求数求和，即可获得当前的实时窗口计数。

优点：供给了灵活性和杰出的性能。避免了漏桶的饥饿题目和牢固窗口的鸿沟双倍暴击题目。

（七）背压（Back Pressure）

背压是一种障碍请求经过的反向压力，凡是出现在请求速度快于处置速度的高低文中。

它不是一种纯真的限流战略，由于这类战略不是办事器零丁完成的，而是需要办事器和客户端合作来应对：

• 办事器照旧负责限流的部分。分歧的是，当办事器压力很大，没法处置更多请求的时辰，需要向客户端传递这类压力信号（称之为背压信号），经过响应（如HTTP 429）反向传导给客户端。
• 然后压力就来到了客户端，客户端需要了解这类反应，并做出适当的办法，以下降其请求速度，从而适配办事器的处置才能。

客户端可以停止的办法包括：

• 抛弃这个请求
• 缓存这个请求，并在未来的某个时辰再次发送

案例：TCP滑动窗口

一个著名的案例是TCP滑动窗口：接收端在每次收到一个数据包后，城市在ACK中带上自己的接口窗口巨细，发送方收到ACK后，按照接收方通告的窗口巨细，调剂自己的发送窗口巨细，以静态适配接收方的处置才能。

阻塞挪用链（Callstack Blocking）

上面描写的机制实现了一种显现的生产者和消耗者的调和机制。

除此之外，还存在一种隐式的调和机制，即阻塞挪用链（Callstack Blocking），当下流没法处置时间接阻塞上游。下面是一些例子：

• TCP阻塞send：内核有一个牢固长度的发送缓冲区，缓冲区满时，会阻塞send方式。
• 线程池：提交使命到线程池，线程池满后，会阻塞在提交行动上，这将隐式地阻塞上游的生产者。

客户端战略

除了上面描写的背压战略，客户端还需要在收集超时的情况下，介入到限流进程。

（一）超时重试

散布式系统存在独有的三态概念，即成功 ，失利，和超时无响应（成果未知）。当超时发生时，客户端凡是需要重试，就和收到背压信号时的处置类似。

（二）退避（Backoff）

重试是“无私的”。换句话说，在客户端重试时，它将花费更多的办事器时候来获得更大的成功几率。在故障很少发生或瞬时发生的情况下，这并不是题目，由于重试请求的总数很小。但假仍旧障是由过载引发的，重试会增加负载，致使情况进一步恶化。

重试的首选处理计划是退避：客户端不会立即积极地重试，而是在两次尝试之间期待一段时候。

指数退避（exponential backoff）

最好的退避形式是指数退避，即每次尝试后的期待时候都呈指数级增加。这能够致使很长的退避时候，由于指数函数增加很快。为了避免重试太长时候，实现凡是会设备一个上限值。

利用这类方式的一个典范案例是：TCP超时重传时采用的Karn算法。

其他的退避形式

• 恒按时候：在每次尝试之间期待恒定的时候。例如，利用1秒的恒定提早，那末重试将在1秒、2秒、3秒、4秒等发生。
• 斐波纳契：利用斐波纳契数，来获得对应于当前重试的期待时长，比如1，1，2，3，5，8，13，等等。

这个Python退避包供给了一些常用的处理计划。

（三）增加发抖（Jitter）

假如很多客户端同时发出基于时候表的请求（比如每小时查询一次），那末能够会形成周期性的惊群效应 (thundering herd)。该效应指的是由于突发事务而致使的突发的流量激增的情况。

处理方式是：经过在超不时候上增加额外的随机值（发抖），以使重试在时候上有所分离，从而避免这类情况的发生。

（四）谨稳重试

重试会加重隶属系统上的负载：假如对系统的挪用超时，且该系统过载，则重试会致使过载题目恶化，而非好转。下面是一些倡议：

• 仅在观察到依靠项运转状态杰出时才停止重试，从而避免了这类负载加重的题目。
• 当重试无助于进步可用性时，应停止重试。

散布式限流

散布式系统中，能够需要对办事的一切实例停止整体限制，这时就要利用高效的全局存储（如Redis）来跟踪各类限制计数。

（一）合作条件

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

处理计划1：放脱期制

答应计数器跨越阈值， 可以设备一个容忍区间（如1%）。举个例子：设定上限为200，可是答应203个请求。这也许算不上处理计划，但某些场景确切能用。

处理计划2：会话连结

经过在负载平衡器中设备会话连结，以便确保来自同一个用户的请求总是由同一个节点串行处置。弱点：缺少容错才能、节点过载时的扩大性题目。

处理计划3：加锁

处理合作条件，最常用的方式是加锁，以避免计数器的并发拜候。弱点：消耗者发出的其他请求的响应提早，此外锁会很快成为一个严重的性能瓶颈，而且不能很好地伸缩。

处理计划4：Redis+Lua

当利用Redis作为数据存储时，可以搭配Lua剧本实现“get-then-set”原子化。Redis将全部Lua剧本作为一个号令原子履行，无需担忧并发。