网站上线倒计时 模板,建设部网站 43号文件,安徽水安建设集团网站,珠海企业营销型网站建设公司首先看看使用API限流器的好处。
•预防由拒绝服务攻击(Denial of Service#xff0c;DoS)引起的资源耗尽问题。大型科技公司发布的所有API几乎都强制执行某种形式的限流操作。例如#xff0c;推特限制每个用户每3小时最多发300条推文。谷歌文档API的默认限制是每个用户每60秒…首先看看使用API限流器的好处。
•预防由拒绝服务攻击(Denial of ServiceDoS)引起的资源耗尽问题。大型科技公司发布的所有API几乎都强制执行某种形式的限流操作。例如推特限制每个用户每3小时最多发300条推文。谷歌文档API的默认限制是每个用户每60秒最多发出300个读请求。限流器通过有意或者无意地拦截超额的请求来预防DoS攻击。
•降低成本。限制过量的请求意味着需要的服务器更少并且可以把更多的资源分配给优先级更高的API。限流器对于使用付费的第三方API的公司来说极为重要。比如对于外部API如检查信用值、请求付款、获取健康记录等你需要按照请求次数付费。限制这些请求的数量对于降低成本很重要。
•预防服务器过载。为了降低服务器负载可以使用限流器来过滤机器人或者用户不当操作所造成的过量请求。
1.限流器场景需求设定
•能准确限制过量的请求。
•低延时限流器不能拖慢HTTP响应时间。
•尽量占用较少的内存。
•这是一个分布式限流器可以在多个服务器或者进程之间共享。
•需要处理异常。当用户的请求被拦截时给用户展示明确的异常信息。
•高容错性。如果限流器出现任何问题比如某个缓存服务器宕机不能影响整个系统。
2.顶层设计 我们从简单的情形入手采用基本的客户—服务器通信模式。
2.1在哪里实现限流器 直观地说既可以在客户端也可以在服务器端实现限流器。
•在客户端实现。一般而言客户端不是一个强制实行限流的可靠位置因为客户端请求很容易被恶意伪造。此外我们也可能无法控制客户端的实现。
•在服务器端实现。图-1展示了一个服务器端的限流器。 图-1
除了在客户端和服务器端实现还有一种方案。我们可以创建一个中间件作为限流器用它来限制对API的请求而不是把限流器放在API服务器上如图-2所示。 图-2
我们用图-3作为例子来讲解限流器在我们的设计中是怎样工作的。假设我们的API服务器允许客户端每秒发送两次请求而客户端在1秒之内向服务器发送了3个请求那么头两个请求被转发到API服务器上限流器中间件会拦截第3个请求并返回HTTP状态码429表示用户发送的请求太多。 图-3
云微服务已经非常流行限流器通常在一个叫作API网关的组件中实现。API网关是一个完全托管的服务支持流量限制、SSL终止、身份验证、IP地址白名单、静态内容服务等功能。现在我们只需要知道API网关是一个支持流量限制的中间件即可。
在设计限流器的时候我们要问自己一个很重要的问题这个限流器应该在哪里实现是在服务器端还是在网关中实现这个问题没有唯一的答案而是取决于你公司现在的技术栈、工程资源、优先级、目标等因素。以下是一些一般性的指导原则。
•评估公司现在的技术栈比如编程语言、缓存服务等。确保你现在用的编程语言能高效地在服务器端实现流量限制。
•找到适合业务需求的流量限制算法。如果把所有功能或模块都放在服务器端实现你就可以自由地选择算法。如果使用第三方网关你的算法选择就有可能受到限制。
•如果你已经使用了微服务架构并且在设计中包含了API网关以实现身份验证、IP地址白名单等功能那么你可以把限流器加在API网关上。
•创建自己的限流器是很花时间的。如果你没有足够的工程资源去实现限流器使用商业版的API网关是更好的选择。
2.2 流量限制算法 流量限制可以通过不同的算法来实现每种算法都有不同的优点和缺点。本文虽然并不重点讨论算法但是大概了解一下它们有助于为我们的场景选择最适合的算法或者算法组合。下面是流行算法的列表。
•代币桶算法(Token Bucket)。
•漏桶算法(Leaking Bucket)。
•固定窗口计数器算法(Fixed Window Counter)。
•滑动窗口日志算法(Sliding Window Log)。
•滑动窗口计数器算法(Sliding Window Counter)。
代币桶算法 代币桶算法被广泛用于限制流量。它很简单、容易理解并被互联网公司广泛使用。亚马逊[插图]和Stripe都使用此算法来对它们的API请求限流。代币桶算法的工作原理如下
•代币桶是一个有预定义容量的容器。代币按照预定的速率被放入桶中。一旦桶被装满就不再往里面添加代币。如图-4所示代币桶的容量是4个代币。重新注入装置每秒将两个代币放入桶中。如果桶满了多出来的代币就会溢出。 图-4
•每个请求消耗一个代币。当一个请求到达时我们检查桶里有没有足够的代币。图-5解释了它是如何工作的。
◆ 如果有足够的代币每次请求到达时我们就取出一个代币然后这个请求就可以通过。
◆ 如果没有足够的代币这个请求将被丢弃。 图-5
图-6描述了代币消耗、重新注入和流量限制的工作原理。在这个例子中代币桶的容量是4个代币重新注入代币的速度是每分钟4个。 图-6
代币桶算法有两个参数。
•桶大小桶内最多允许有多少个代币。
•重新注入代币的速度每秒放进桶里的代币数量。
我们需要多少个桶呢说不准这取决于流量限制规则。下面是一些例子。
•通常不同的API端点需要使用不同的桶。比如如果允许用户每秒发1篇帖子每天添加150个好友每秒点赞5篇帖子那么每个用户就需要3个桶。
•如果我们需要基于IP地址来对请求限流则每个IP地址需要一个桶。
•如果系统最多允许每秒发送10000个请求那么所有请求理应共享一个全局桶。
代币桶算法有不少优点。
•算法容易实现。
•内存的使用效率高。
•允许在很短时间内出现突发流量。只要还有代币请求就可以通过。
代币桶算法也有缺点。尽管该算法只需要两个参数但是要把这两个参数调校好可能很具有挑战性。
漏桶算法 漏桶算法跟代币桶算法很相似只不过它对请求是按照固定速率处理的。漏桶算法通常采用先进先出(First-In-First-OutFIFO)队列来实现。该算法的工作原理如下所述。
•当一个请求到达时系统先检查桶是否已满。如果没有就将请求添加到队列中。
•否则丢弃请求。•定期从队列中取出请求并进行处理。
图-7解释了该算法是如何工作的。 图-7
漏桶算法有如下两个参数。
•桶大小它等于队列大小。队列中保存了要按固定速率处理的请求。
•出栈速度它定义了每秒可以处理多少个请求通常以秒为时间单位。Shopify是一个电商公司它使用漏桶算法来进行流量限制。
漏桶算法的优点
•因为队列大小是有限的所以内存的使用更高效。
•因为对请求是按固定速率来处理的所以漏桶算法很适合要求出栈速度稳定的场景。
漏桶算法的缺点
•突发流量会使队列中积压大量旧的请求如果这些请求不能被及时处理最新的请求会被限流。
•该算法有两个参数要调校好它们可能不那么容易。
固定窗口计数器算法 固定窗口计数器算法的工作原理如下所述。
•将时间轴分成固定大小的时间窗口并给每个时间窗口分配一个计数器。
•每到达一个请求计数器的值都会加1。
•一旦计数器到达预先设定的阈值新请求就会被丢弃直到开始一个新的时间窗口。
我们用一个具体的例子来看看它到底是怎么工作的。在图-8中时间单位是秒系统允许每秒最多通过3个请求。在每个1秒的时间窗口中如果收到超过3个请求超出的请求会如图4-8所示的那样被丢弃。 图-8 这个算法的一个主要问题是如果在时间窗口的边界上出现流量的爆发则有可能会导致通过的请求数超出阈值。我们来看下面这个例子。如图-9所示系统每分钟最多只允许通过5个请求并且可用配额阈值在整分钟时会重置。在2:00:00和2:01:00之间有5个请求在2:01:00和2:02:00之间又有5个请求。对于2:00:30至2:01:30这1分钟的时间窗口有10个请求通过而这是允许通过的请求数量的两倍。 图-9
固定窗口计数器算法的优点
•内存的使用效率高。
•容易理解。
•在每个单位时间窗口结束时重置请求数阈值这种设计适用于某些特定场景。
固定窗口计数器算法的缺点是如果在时间窗口的边界上流量激增会导致通过的请求数超过设定的阈值。
滑动窗口日志算法 前面讨论过固定窗口计数器算法有一个重大问题在时间窗口的边界上它允许更多的请求通过。滑动窗口日志算法解决了这个问题。它的工作原理如下所述。
•算法记录每个请求的时间戳。时间戳数据通常保存在缓存中比如Redis中的有序集合。
•当新请求到达时移除所有过时的时间戳。过时时间戳是指那些早于当前时间窗口起始时间的时间戳。
•将新请求的时间戳添加到日志中。
•如果日志的条数等于或者少于允许的请求数则请求通过否则请求被拒绝。我们用一个例子来解释这个算法如图-10所示。 图-10
在这个例子中限流器每分钟允许2个请求通过。通常Linux时间戳会被存储在日志中。但是为了使可读性更高我们在这里使用了人类可读的时间表示。•当一个新请求在1:00:01到达时日志是空的。因此该请求被允许通过。
•当一个新请求在1:00:30到达时1:00:30这个时间戳被添加到日志中。添加后日志条数变为2没有超过允许通过的请求数量。因此这个请求也被允许通过。
•当一个新请求在1:00:50到达时时间戳被插入日志。在插入后日志条数变为3大于允许通过的最大请求数。因此该请求被拒绝但是它的时间戳留在了日志中。
•当一个新请求在1:01:40到达时所有在[1:00:401:01:40范围内的请求都在最近的时间窗口中所有早于1:00:40发送的请求都已过时。两个过时的时间戳1:00:01和1:00:30从日志中被删除。删除后日志的条数变成2因此这个请求被允许通过。
滑动窗口日志算法的优点是其实现的流量限制非常准确在任何滑动的时间窗口中请求的数量都不会超过阈值。但是其消耗的内存过多因为即使一个请求已被拒绝它的时间戳依然被保存在内存中。
滑动窗口计数器算法 滑动窗口计数器算法是组合了固定窗口计数器算法和滑动窗口日志算法的方法。这个算法有两种不同的实现方法这里会解释其中的一种。图-11展示了这个算法是怎么工作的。
假设限流器每分钟最多允许通过7个请求然后前一分钟有5个请求当前分钟有3个请求。当一个新请求出现在当前分钟的30%的位置时滑动窗口所允许的请求数量通过下面的公式来计算
当前窗口的请求数之前窗口的请求数×滑动窗口和之前窗口的重合率
用这个公式我们可以算出滑动窗口所允许的请求数量为6.5个(35×0.76.5)。基于不同的用户场景对这个数字可以向上或者向下取整。在我们的例子中将它向下取整为6。 图-11
因为限流器每分钟最多允许通过7个请求所以现在的请求可以通过。但是再多接收一个请求就会超过阈值。受篇幅所限我们不讨论另一种实现方式感兴趣的读者可以阅读Medium网站上的文章“System Design—Rate limiter and Data Modelling”。滑动窗口计数器算法也不是完美的。它也有优点和缺点。
滑动窗口计数器算法优点
•它平滑了流量中的波动因为当前时间窗口内请求的速率是基于前一个时间窗口内请求的平均速率计算出来的。
•对内存的使用很高效。滑动窗口计数器算法的缺点是它只对不那么严格的回溯窗口起作用。该算法只是对真实流量速率进行了近似估计因为它假设前一个窗口中的请求是均匀分布的。尽管如此这个问题可能并没有看起来那么严重。根据Cloudflare的实验在4亿个请求中只有0.003%的请求被错误地允许通过或被限流。
2.3 高层级架构 流量限制算法的基本理念是简单的。从高层级来看我们需要一个计数器来记录有多少请求是由同一个用户、同一个IP地址等发来的。如果计数器的值超出设定的阈值请求就不允许通过。
那么我们应该在哪里存储计数器呢使用数据库并不是一个好主意因为硬盘的访问速度很慢。内存上的缓存速度快且支持基于时间的过期策略因此可以选它。比如Redis就是一个很受欢迎的选项。Redis是一个内存存储系统它提供了两个命令INCR和EXPIRE。
•INCR把存储的计数器值加1。
•EXPIRE为计数器设置一个超时时间。如果超时时间到期计数器会被自动删除。
图-12展示了限流器的高层级架构它按如下方式工作。
•客户端将请求发送给限流器中间件。
•限流器中间件在Redis对应的桶中获取计数器并检查其值是否达到了阈值。
◆ 如果达到阈值请求将被拒绝。
◆ 如果没有请求将被发送给API服务器。同时系统增加计数器的值并把它保存到Redis中。 图-12
3.深入设计 图-12所示的高层级设计并没有回答下面的问题
•流量限制规则是如何创建的这些规则存储在哪里
•如何处理被限流的请求
在本节中我们先回答关于流量限制规则的问题然后讨论处理被限流请求的策略最后讨论如何在分布式系统中进行流量限制。我们会给出一个详细的设计并探讨性能优化和监控方面的问题。
3.1 流量限制规则 Lyft开源了它的流量限制组件。我们来看两个使用这个组件编写的流量限制规则的例子。在下面的例子中系统设置了每天最多允许有5条营销消息。 下面是另一个例子。这个规则是在1分钟之内客户端登录不允许超过5次。这些规则一般都写在配置文件中并保存在硬盘上。 3.2 超过流量的限制 如果一个请求被限流API会给客户端返回HTTP响应码429请求过多。根据应用场景我们有可能会把超过阈值的请求放入队列之后再处理。比如一些订单请求因为系统过载被限流了我们可以保存这些订单以便稍后处理。
限流器返回的HTTP头
客户端如何知道请求有没有被限流呢客户端如何在请求被拦截之前知道允许通过的请求数还剩多少答案藏在HTTP头里。限流器会返回下面的HTTP头给客户端。
•X-Ratelimit-Remaining在当前时间窗口内剩余的允许通过的请求数量。
•X-Ratelimit-Limit客户端在每个时间窗口内可以发送多少个请求。
•X-Ratelimit-Retry-After在被限流之后需要等待多少秒才能继续发送请求而不被拦截。当用户发送的请求过多时限流器将向客户端返回HTTP响应码429表示请求太多和X-Ratelimit-Retry-After响应头。
3.3 详细设计 图-13
•流量限制规则存储在硬盘上。工作进程(Worker)经常从硬盘中获取规则并将其存储到缓存中。
•当客户端向服务器发送请求时请求会首先被发给限流器中间件。
•限流器中间件从缓存中加载规则。它从Redis缓存中获取计数器和上一次请求的时间戳。基于响应限流器中间件做出以下决定
◆ 如果请求没有被限流就将其转发给API服务器。
◆ 如果请求被限流限流器会向客户端返回429响应码请求太多来报错。同时请求要么被丢弃要么被转发到队列中。
3.4 分布式系统中的限流器 在单服务器环境中创建一个限流器并不难。但是要将限流器系统扩展以支持多个服务器和并发线程那就是另一回事了。其中存在两个挑战
•竞争条件(Race Condition)。
•同步问题。
竞争条件
如前所述限流器大体上是按如下方式工作的
•从Redis中读取计数器的值。
•检查计数器值加1后是否超过了阈值。
•如果没有就把计数器的值在Redis中加1。
竞争条件可能会发生在一个高并发的环境中如图-14所示。 图-14
假设在Redis中计数器的值是3。如果两个请求同时读计数器的值它们中的任何一个在将值写回Redis之前都会把计数器的值加1而不检查其他线程的情况。这样两个请求线程都认为它们拥有正确的计数器值——4但是正确的计数器值应该是5。
锁是竞争条件最直观的解决方案但是它会显著地拖慢系统。通常我们使用以下两种策略用来解决这个问题Lua脚本和Redis的有序集合数据结构。
同步问题
同步是分布式系统中需要考虑的另一个重要因素。为了支持百万量级的用户一个限流器有可能不足以处理所有的流量。当使用多个限流器时限流器之间就必须同步。举个例子如图-15所示在左图中客户端1向限流器1发送请求客户端2向限流器2发送请求。但因为网络层是无状态的所以客户端也可以把请求发给别的限流器如图-15的右图所示。如果没有同步则限流器1将不包含任何关于客户端2的数据因此限流器1就无法正常工作。 图-15
一个可行的解决方案是使用黏性会话(Sticky Session)允许客户端将请求发往同一个限流器。但是这个解决方案既不可扩展也不灵活因此不建议使用。更好的方法是使用中心化的数据存储比如Redis。该设计如图-16所示。 图-16
3.5 性能优化 性能优化是系统设计面试中常见的主题。我们会针对两个方面来做优化。
第一对限流器而言设置多数据中心是至关重要的因为离数据中心越远响应延时越高。大多数云服务提供商在全球设置了很多边缘服务器。比如截至2020年5月20日Cloudflare有194个在地理上广泛分布的边缘服务器。流量会被自动转发到最近的边缘服务器以降低延时如图-17所示。 图-17
3.6 监控 在设置好限流器之后收集数据来检查限流器是否有效是很重要的。我们主要想确保
•流量限制算法有效。
•流量限制规则有效。
举个例子如果流量限制规则太严格就会导致很多有效请求被丢弃。在这种情况下我们希望稍微放宽限制。另一个例子是我们发现在限时促销这种流量激增的场景下限流器变得无效了。因此可能需要换一种流量限制算法来应对突发的流量。这时候代币桶就是一个合适的替代算法。
4.总结 在本文中我们讨论了不同的流量限制算法及其优缺点。这些算法包括
•代币桶算法。
•漏桶算法。
•固定窗口计数器算法。
•滑动窗口日志算法。
•滑动窗口计数器算法。
然后我们讨论了系统架构、分布式系统中的限流器、性能优化和监控。同任何其他系统设计面试题类似如果有时间你还可以谈一谈下面的话题。
•硬流量限制与软流量限制。硬流量限制是指请求数量不能超过阈值。软流量限制是指请求数量可以在短时间内超过阈值。
•在不同层级做流量限制。在本文中我们只讨论了在应用层HTTP层第7层做流量限制。流量限制也可以用在其他层。例如你可以使用Iptables[插图]IP层第3层并根据IP地址来限流。注意开放系统互联模型Open Systems InterconnectionOSI模型有7层[插图]其中第1层为物理层第2层为数据链路层第3层为网络层第4层为传输层第5层为会话层第6层为表示层第7层为应用层。
•避免被限流。用以下最佳实践来设计你的客户端
◆ 使用客户端缓存避免频繁地调用API。
◆ 理解流量限制不要在短时间内发送太多请求。
◆ 添加代码以捕获异常或错误使客户端可以优雅地从异常中恢复。
◆ 在重试逻辑中添加足够的退避时间。
