北京网站建设公司大全,苏州商城网站建设,easy ssl wordpress,一级造价工程师报考条件及科目限速器 (Rate Limiter) 相信大家都不会陌生#xff0c;在网络系统中#xff0c;限速器可以控制客户端发送流量的速度#xff0c;比如 TCP, QUIC 等协议。而在 HTTP 的世界中#xff0c; 限速器可以限制客户端在一段时间内发送请求的次数#xff0c;如果超过设定的阈值在网络系统中限速器可以控制客户端发送流量的速度比如 TCP, QUIC 等协议。而在 HTTP 的世界中 限速器可以限制客户端在一段时间内发送请求的次数如果超过设定的阈值多余的请求就会被丢弃。生活中也有很多这样的例子比如• 用户一分钟最多能发 5 条微博• 用户一天最多能投 3 次票• 用户一小时登录超过5次后需要等待一段时间才能重试。限速器Rate Limiter有很多好处可以防止一定程度的 Dos 攻击也可以屏蔽掉一些网络爬虫的请求避免系统资源被耗尽导致服务不可用。 设计要求 让我们从一个面试开始吧面试官你好我想考察一下你的设计能力如果让你设计一个限速器 (Rate Limiter)你会怎么做面试者我们需要什么样的限速器它是在客户端限速还是在服务端限速面试官这个问题很好没有固定要求取决于你的设计。面试者我想了解一下限速的规则我们是根据 IP、UserId或者手机号码进行限速吗面试官这个不固定限速器应该是灵活的要能很方便的支持不同的规则。面试者如果请求被限制了需要提示给用户吗面试官需要提示要给用户提供良好的体验。面试者好吧那系统的规模是多大的是单机还是分布式场景面试官我们是 TOC 的产品 系统流量很大并且是分布式的环境 所以限速器要支持海量请求。面试者小声嘀咕你这是造火箭呢我们总结一下限速器的设计要求• 低延迟性能要好• 需要适用于分布式场景。• 用户的请求受到限制时需要提示具体的原因。• 高容错如果限速器故障不应该影响整个系统。 限速器应该放在哪里 从系统整体的角度上来看我们的限速器应该放在哪里通常有三种选择如下客户端是的我们可以在客户端设置限速器。但是有个问题是我们都知道在 Web 前端做一些限制实际上是不安全的同样客户端也是一样的 限速客户端可以做但是远远不够。服务端在服务端设置限速器是很常见且安全的如下中间件还有一种做法是我们可以提供一个单独的限速中间件如下假如限速器设置了每秒最大允许2个请求那么客户端发出的多余的请求就会被拒绝并返回 HTTP 状态码 429, 表示用户发送了太多的请求。实际上很多网关都有限速的实现包括认证、IP 白名单功能。限速器应该放在哪里没有固定的答案它取决于公司的技术栈系统规模。 限速算法 实际上我们可以用算法实现限速器下面是几种经典的限速算法每种算法都有自己的优点和缺点了解这些可以帮助我们选择更适合的算法。• 令牌桶 Token bucket• 漏桶Leaking bucket• 固定窗口计数器Fixed window counter• 滑动窗口日志Sliding window log• 滑动窗口计数器Sliding window counter 令牌桶算法 令牌桶算法是实现限速使用很广泛的算法它很简单也很好理解。令牌桶是固定容量的容器。一方面按照一定的速率向桶中添加令牌桶装满后多余的令牌就会被丢弃。如下图桶的容量为4每次填充2个令牌。另一方面一个请求消耗一个令牌如果桶中没有令牌了则拒绝请求。直到下个时间段继续向桶中填充新的令牌。令牌桶算法有两个重要的参数分别是桶大小和填充率另外有时候可能需要多个桶比如多个 api 限速的规则是不一样的。令牌桶算法的优点是简单易实现并且允许短时间的流量并发。缺点是在应对流量变化时正确地调整桶大小和填充率会比较有挑战性。 漏桶算法 漏桶算法和令牌桶算法是类似的同样有一个固定容量的桶。一方面当一个请求进来时会被填充到桶里如果桶满了就拒绝这个请求。另一方面想象桶下面有一个漏洞桶里的元素以固定的速率流出。通常可以用先入先出的队列实现如下图漏桶算法有两个参数分别是桶大小和流出率优点是使用队列易实现缺点是面对突发流量时虽然有的请求已经推到队列中了但是由于消费的速率是固定的存在效率问题。 固定窗口计数器算法 固定窗口计数器算法的工作原理是把时间划分成固定大小的时间窗口每个窗口分配一个计数器接收到一个请求计数器就加一一旦计数器达到设定的阈值新的请求就会被丢弃直到新的时间窗口新的计数器。让我们通过下面的例子来看看它是如何工作的。一个时间窗口是1秒每秒最多允许3个请求超出的请求就会被丢弃。不过这个算法有一个问题是如果在时间窗口的边缘出现突发流量时可能会导致通过的请求数超过阈值什么意思呢我们看看下面的情况一个时间窗口是1分钟每分钟最多允许5个请求。如果前一个时间窗口的后半段有5个请求后一个时间窗口的前半段有5个请求也就是 2:00:30 到 2:01:30 的一分钟内是可以通过10个请求的这明显超过了我们设置的阈值。固定窗口计数器的优点是简单易于理解缺点是时间窗口的边缘应对流量高峰时可能会让通过的请求数超过阈值。 滑动窗口日志算法 我们上面看到了固定窗口计数器算法有一个问题在窗口边缘可能会突破限制而滑动窗口日志算法可以解决这个问题。它的工作原理是假如设定1分钟内最多允许2个请求每个请求都需要记录请求时间比如保存在 Redis 的 sorted sets 中保存之后还需要删除掉过时的日志过时日志是如何定义的比如某次请求的时间是 1:01:36那么往前推1分钟1:00:36 之前的日志都算过时的需要从集合中删掉。同时判断集合中的数量是否大于阈值如果大于2则丢弃请求如果小于或等于2则处理这个请求。让我们看看下面的例子1.在 1:00:01 来了一个请求第一步记录请求时间到日志中第二步判断是否有过时的日志, 也就是 0:59:01 之前的日志明显没有第三步判断日志中的数量没有大于2处理这次请求。2.在 1:00:30 来了一个请求执行上面的三个步骤最后处理这次请求。3.在 1:00:50 的新请求没有过时的日志然后发现日志的数量为3拒绝这次请求。4.在 1:01:40 的新请求清除2条过时的日志也就是 1:00:40 之前的日志此时日志中的数量为2处理这次请求。这个算法实现的限速非常准确但是它可能会消耗较多的内存。 滑动窗口计数器算法 滑动窗口计数器可以说是固定窗口计数器的升级版上面提到了固定窗口计数器存在窗口边缘可能会有超出限制的情况如下而滑动窗口把固定的窗口又分成了很多小的窗口单位比如下图每个固定窗口的大小为1分钟又拆分成了6份每次移动一个小的单位保证总和不超过阈值。这样就可以避免上面的窗口边缘超出限制的问题。 使用 Redis 实现高效计数器 限速器算法的思想其实很简单我们需要使用计数器记录用户的请求如果超过阈值服务这个请求否则拒绝这个请求。一个很重要的问题是我们应该把计数器放在哪里我们知道磁盘速度比较慢使用数据库明显是不太现实的方案想要更快的话可以使用内存缓存最常见的就是 Redis是的我们可以使用 Redis 实现高效计数器如下 规则引擎 Lyft 是一个开源的限速组件可以供我们参考它通过 Yaml 配置文件实现灵活的限速规则看下面的示例这个配置表示系统每天只能发送 5 条营销信息。这个配置表示 1分钟的登录次数不能超过 5 次。可以看到基于配置文件声明式的限速规则是非常灵活的我们可以把配置文件保存到磁盘中。 限速提示 当请求超过限制时限速器会拒绝掉其他的请求这样其实不够为了更好的用户体验我们需要返回友好的错误信息给用户并提示。首先限速器拒绝请求后可以返回 HTTP 状态码 429表示请求过多。其次我们可以返回更详细的信息比如剩余请求次数、等待时间等。一种很常见的做法时把这些信息放到 Http 响应的 Header 中返回如下• X-Ratelimit-Remaining表示剩余次数 • X-Ratelimit-Limit表示客户端每个时间窗口可以进行多少次调用 • X-Ratelimit-Retry-After表示等待多长时间可以进行重试看起来不错让我们看看现在的架构设计首先限速规则存储在磁盘上因为要经常访问可以添加到缓存中。当客户端向服务器发送请求时会先发送到限速中间件。限速中间件从缓存中拉取限速规则同时把请求数据写入到 Redis 的计数器然后判断是否超出限制。如果没有超出限制把请求转发给我们的后端服务器。如果超出了限制第一种方案丢弃多余的请求返回 429第二种方案把多余的请求推送到消息队列中后续再进行处理。使用哪种方案取决于您的实际场景。 分布式环境 构建一个在单服务器运行的限速器是很简单的但是在分布式环境中支持多台服务器那就完全是另外一回事了。我们主要要考虑两个问题• 并发问题• 数据同步问题并发问题我们的限速器的工作原理是当接收到新的请求时从 Redis 中读取计数器 counter然后做加一的操作在高并发场景中可能存在多个线程读到了旧的值比如两个线程同时读取到 counter 的值为3然后都把 counter 改成了4这样是有问题的其实最终应该是 5。有朋友说我们可以用锁但实际上锁的效率是不高的。解决这个问题通常有两个方案第一个是使用 Lua 脚本第二个是使用 Redis 的 sorted sets 数据结构具体的细节本文不做过多介绍。数据同步问题在流量比较大的情况下一个限速器是难以支撑的我们需要多个限速器。由于 Web 层通常是无状态的客户端的请求会随机发送给不同的限速器如下这种情况下如果没有数据同步我们的限速器肯定是没办法正常工作的。我们可以使用像 Redis 这样的集中式数据存储如下 性能优化 当我们的系统是面向全球用户时为了让各个地区的用户都能有一个不错的体验通常会在不同的地区设置多个数据中心。另外现在很多云服务商在全球各地都有边缘服务器流量会自动路由到最近的边缘服务器来减少网络的延迟。当然存在多个数据中心时可能还要考虑到数据的最终一致性。 总结 在本文中我们讨论了不同的限速算法以及它们有优缺点算法包括• 令牌桶• 漏桶• 固定窗口计数器• 滑动窗口日志• 滑动窗口计数器然后我们讨论了分布式环境中的系统架构并发问题和数据同步问题和灵活配置的限速规则最后你会发现实现一个限速器其实没有那么难希望对您有用 译等天黑 作者Alex Xu 来源System Design Interview
