题目: 设计一个 API 速率限流器, 它将根据用户发送的请求数限制用户.
难度等级: 中等
一, 限流器介绍
假设我们有一个接收大量请求的服务, 但它每秒只能处理有限的请求. 要处理这个问题, 我们需要某种节流或速率限制机制, 只允许一定数量的请求, 这样我们的服务就可以响应所有请求. 速率限制器在高级别上限制实体 (用户, 设备, IP 等) 在特定时间窗口中可以执行的事件数. 例如:
• 用户每秒只能发送一条消息.
• 一个用户每天只能进行三次失败的信用卡交易.
• 一个 IP 每天只能创建 20 个帐户.
通常, 速率限制器限制发送者在特定时间窗口内可以发出的请求数. 一旦达到上限, 它就会阻止请求.
比如我们的淘宝, 京东秒杀页面, 如果已经超过系统的负载能力, 这个时候请求就会被抛弃.
二, 为什么需要限流
速率限制有助于保护服务免受针对应用层的滥用行为, 如拒绝服务 (DOS) 攻击, 暴力口令尝试, 暴力信用卡交易等. 这些攻击通常是一系列 HTTP/S 请求, 看起来可能来自真实用户, 但通常是由机器 (或机器人) 生成的. 因此, 这些攻击通常更难检测, 并且更容易使服务, 应用程序或 API 瘫痪.
<font color=blue > 速率限制还用于防止收入损失, 降低基础设施成本, 阻止垃圾邮件和阻止在线骚扰.</blue > 以下是通过使服务 (或 API) 更可靠而受益于速率限制的场景列表:
• 行为不端的客户机 / 脚本:
无论是有意还是无意, 一些实体都可以通过发送大量请求来压倒服务. 另一种情况可能是, 当用户发送大量低优先级请求时, 我们希望确保它不会影响高优先级通信量. 例如, 不应允许发送大量分析数据请求的用户妨碍其他用户的关键事务.
• 安全性:
通过限制允许用户执行的第二因素尝试次数(在 2 因素身份验证中), 例如, 允许用户尝试使用错误密码的次数.
• 防止滥用行为和糟糕的设计实践:
没有 API 限制, 客户端应用程序的开发人员会使用草率的开发策略, 例如, 反复请求相同的信息.
• 控制成本和资源使用:
服务通常是为正常的输入行为而设计的, 例如, 用户在一分钟内写一篇文章. 计算机可以轻松地以每秒数千次的速度通过 API. 速率限制器启用对服务 API 的控制.
• 收入:
某些服务可能希望根据其客户的服务级别限制运营, 从而创建基于费率限制的收入模型. 服务提供的所有 API 都可能有默认限制. 为了超越这个限制, 用户必须购买更高的限制
• 为了消除交通中的刺耳现象:
确保为其他人提供服务.
三, 系统的要求和目标
我们的限速器应满足以下要求:
功能要求:
1. 限制一个实体在一个时间窗口内可以向 API 发送的请求数, 例如每秒 15 个请求.
2.API 可以通过集群访问, 所以应该考虑不同服务器之间的速率限制. 当单个服务器或多个服务器的组合中超过定义的阈值时, 用户应该会收到一条错误消息.
非功能要求:
1. 系统应具有高可用性. 速率限制器应该一直工作, 因为它保护我们的服务免受外部攻击.
2. 我们的速率限制器不应该引入影响用户体验的大量延迟.
四, 如何做速率限流
速率限制是一个用于定义用户可以访问 API 的速率和速度的过程. 节流是在给定的时间段内控制客户对 API 的使用的过程. 节流可以在应用程序级别和 / 或 API 级别定义. 当超过限制时, 服务器返回 HTTP 状态 "429 - 请求过多".
五, 限流的不同类型
以下是不同服务使用的三种著名的节流类型:
硬节流:
API 请求的数量不能超过节流限制.
软节流:
在这种类型中, 我们可以将 API 请求限制设置为超过某个百分比. 例如, 如果我们的速率限制为每分钟 100 条消息, 并且有 10% 超出限制, 那么我们的速率限制器将允许每分钟最多 110 条消息.
弹性节流或动态节流:
在弹性节流下, 如果系统有一些可用资源, 则请求数可能超过阈值. 例如, 如果一个用户每分钟只允许发送 100 条消息, 那么当系统中有可用的免费资源时, 我们可以让用户每分钟发送 100 条以上的消息.
六, 限流的算法
以下是用于速率限制的两种算法:
固定窗口算法: 在该算法中, 时间窗口是从时间单位的开始到时间单位的结束. 例如, 一段时间将被视为 0-60 秒一分钟, 而不考虑发出 API 请求的时间范围. 在下图中, 0-1 秒之间有两条消息, 1-2 秒之间有三条消息. 如果我们有每秒两条消息的速率限制, 这个算法将只限制 "m5".
滚动窗口算法: 在该算法中, 时间窗口是从请求发出的时间加上时间窗口长度的分数来考虑的. 例如, 如果有两条消息以 300 毫秒和 400 毫秒的速度发送, 我们将把它们计算为从该秒的 300 毫秒到下一秒的 300 毫秒之间的两条消息. 在上图中, 每秒钟保留两条消息, 我们将限制 "m3" 和 "m4".
七, 限流的高级设计
速率限制器将负责决定哪些请求将由 API 服务器提供服务, 哪些请求将被拒绝. 一旦一个新的请求到达, web 服务器首先要求速率限制器决定是服务还是限制. 如果请求没有被限制, 那么它将被传递到 API 服务器
八, 基本系统设计与算法
让我们举一个例子, 我们想限制每个用户的请求数. 在这种情况下, 对于每个唯一的用户, 我们将保留一个计数, 表示用户已发出的请求数和开始计数请求时的时间戳. 我们可以将其保存在哈希表中, 其中 "key" 将是 "UserID","value" 将是包含 "Count" 的整数和划时代的整数的结构:
假设我们的速率限制器允许每个用户每分钟有三个请求, 因此每当有新请求传入时, 我们的速率限制器将执行以下步骤:
1. 如果哈希表中不存在 "UserID", 请插入它, 将 "Count" 设置为 1, 将 "StartTime" 设置为当前时间(标准化为一分钟), 然后允许请求.
2. 否则, 找到 "UserID" 的记录, 如果 CurrentTime-StartTime>=1 分钟, 则将 "StartTime" 设置为当前时间,"Count" 设置为 1, 并允许请求.
3. 如果 CurrentTime-StartTime<=1 分钟
• 如果 "计数 < 3", 则增加计数并允许请求.
• 如果 "计数>=3", 则拒绝请求.
速率限制器允许用户 "Kristie" 每分钟三个请求
这里描述的算法会有什么问题呢?
1. 这是一个固定窗口算法, 因为我们在每分钟结束时重置 "StartTime", 这意味着它可能允许每分钟两倍的请求数. 想象一下, 如果克里斯蒂在一分钟的最后一秒发送了三个请求, 那么她可以立即发送
在下一分钟的第一秒又有三个请求, 结果在两秒钟内有 6 个请求. 这个问题的解决方案是滑动窗口算法, 我们将在后面讨论.
2. 原子性: 在分布式环境中,"先读后写" 行为可以创建竞争条件. 想象一下, 如果 Kristie 当前的 "计数" 是 "2", 并且她又发出了两个请求. 如果两个独立的进程为每个请求提供服务, 并且在其中一个更新计数之前同时读取计数, 那么每个进程都会认为 Kristie 可能还有一个请求, 并且她没有达到速率限制.
如果我们使用 Redis 来存储键值, 那么解决原子性问题的一个解决方案就是在读更新操作期间使用 Redis 锁. 然而, 这样做的代价是减缓来自同一用户的并发请求, 并引入另一层复杂性. 我们可以使用 Memcached, 但它会有类似的复杂性.
如果我们使用的是一个简单的哈希表, 那么我们可以有一个自定义的实现来 "锁定" 每个记录, 以解决原子性问题.
我们需要多少内存来存储所有的用户数据? 让我们假设一个简单的解决方案, 我们将所有数据保存在一个哈希表中.
假设 "UserID" 需要 8 个字节. 我们还假设一个 2 字节的 "Count", 最多可以计算 65k, 对于我们的用例来说已经足够了. 虽然 epoch 时间需要 4 个字节, 但我们可以选择只存储分和秒部分, 这可以放入 2 个字节. 因此, 我们总共需要 12 个字节来存储用户的数据:
假设我们的哈希表每个记录有 20 字节的开销. 如果我们需要随时跟踪一百万用户, 我们需要的总内存将是 32MB:
如果我们假设我们需要一个 4 字节的数字来锁定每个用户的记录来解决原子性问题, 那么我们需要一个 36MB 的内存.
这可以很容易地安装在一台服务器上; 但是, 我们不希望所有的流量都通过一台机器. 另外, 如果我们假设速率限制为每秒 10 个请求, 那么对于我们的速率限制器, 这将转化为 1000 万 QPS! 这对于单个服务器来说太多了. 实际上, 我们可以假设在分布式设置中使用 Redis 或 Memcached 之类的解决方案. 我们将把所有的数据存储在远程 Redis 服务器中, 所有的速率限制器服务器将在服务或限制任何请求之前读取 (和更新) 这些服务器.
九. 滑动窗口算法
我们可以保持一个滑动窗口, 如果我们可以跟踪每个用户的请求. 我们可以将每个请求的时间戳存储在哈希表的'value'字段中的 Redis 排序集中.
假设我们的速率限制器允许每个用户每分钟有三个请求, 因此, 每当有新请求传入时, 速率限制器将执行以下步骤:
1. 从排序集移除所有早于 "CurrentTime-1 分钟" 的时间戳.
2. 计算排序集中元素的总数. 如果此计数大于我们的限制 "3", 则拒绝请求.
3. 在排序集中插入当前时间并接受请求.
我们需要多少内存来存储滑动窗口的所有用户数据? 假设 "UserID" 需要 8 个字节. 每个历元时间需要 4 个字节. 假设我们需要每小时 500 个请求的速率限制. 假设哈希表有 20 字节的开销, 排序集有 20 字节的开销. 最多需要 12KB 来存储一个用户的数据:
这里我们为每个元素预留 20 字节的开销. 在排序集中, 我们可以假设至少需要两个指针来维持元素之间的顺序 - 一个指针指向前一个元素, 另一个指针指向下一个元素. 在 64 位机器上, 每个指针需要 8 个字节. 所以我们需要 16 个字节作为指针. 我们添加了一个额外的字 (4 字节) 来存储其他开销.
如果我们需要随时跟踪一百万用户, 我们需要的总内存将是 12GB:
滑动窗口算法比固定窗口算法占用大量内存; 这将是一个可伸缩性问题. 如果我们可以结合以上两种算法来优化我们的内存使用呢?
十, 带计数器的滑动窗口
如果我们使用多个固定时间窗口跟踪每个用户的请求计数, 例如, 速率限制时间窗口大小的 1/60, 会怎么样. 例如, 如果我们有一个小时费率限制, 我们可以为每分钟保留一个计数, 并在收到计算限制的新请求时计算过去一小时内所有计数器的总和. 这将减少我们的内存占用. 让我们举一个例子, 我们的速率限制为每小时 500 个请求, 额外的限制为每分钟 10 个请求. 这意味着, 当过去一小时内带有时间戳的计数器的总和超过请求阈值 (500) 时, Kristie 已经超过了速率限制. 除此之外, 她每分钟不能发送超过 10 个请求. 这将是一个合理和实际的考虑, 因为没有一个真正的用户会发送频繁的请求. 即使他们这样做了, 他们将看到成功的重试, 因为他们的限制得到重置每分钟.
我们可以将计数器存储在 Redis 散列中, 因为它为不到 100 个密钥提供了难以置信的高效存储. 当每个请求在散列中增加一个计数器时, 它还将散列设置为一小时后过期. 我们将把每个 "时间" 标准化为一分钟.
我们需要多少内存来存储带计数器的滑动窗口的所有用户数据?
假设 "UserID" 需要 8 个字节. 每个历元时间需要 4 个字节, 计数器需要 2 个字节. 假设我们需要每小时 500 个请求的速率限制. 假设哈希表的开销为 20 字节, Redis 哈希表的开销为 20 字节. 因为我们会为每分钟保留一个计数, 最多时, 每个用户需要 60 个条目. 我们总共需要 1.6KB 来存储一个用户的数据:
如果我们需要随时跟踪一百万用户, 我们需要的总内存将是 1.6GB:
因此, 我们的 "带计数器的滑动窗口" 算法使用的内存比简单的滑动窗口算法少 86%.
十一, 数据分片和缓存
我们可以基于 "UserID" 进行切分来分发用户的数据. 对于容错和复制, 我们应该使用一致的哈希. 如果我们想对不同的 API 有不同的限制, 我们可以选择对每个 API 的每个用户进行分片. 以 URL-Shortener 为例; 我们可以为每个用户或 IP 的 createURL()和 deleteURL()API 设置不同的速率限制器.
如果我们的 API 是分区的, 那么一个实际的考虑因素可能是为每个 API 切分也有一个单独的 (稍微小一些的) 速率限制器. 让我们以我们的 URL Shortener 为例, 我们希望限制每个用户每小时创建的短 URL 不超过 100 个. 假设我们对 createURL()API 使用基于哈希的分区, 我们可以对每个分区进行速率限制, 以允许用户每分钟创建不超过 3 个短 URL, 以及每小时创建 100 个短 URL.
我们的系统可以从缓存最近的活跃用户中获得巨大的好处. 应用程序服务器可以在命中后端服务器之前快速检查缓存是否具有所需的记录. 通过只更新缓存中的所有计数器和时间戳, 我们的速率限制器可以显著受益于写回缓存. 对永久存储器的写入可以按固定的间隔进行. 通过这种方式, 我们可以确保速率限制器向用户请求添加的最小延迟. 读取总是可以先命中缓存; 这将是非常有用的, 一旦用户已经达到了他们的最大限度和速率限制器将只读取数据没有任何更新.
对于我们的系统来说, 最近最少使用 (LRU) 是一个合理的缓存逐出策略.
十二, 应该用 IP 还是用户 ID 进行限流
让我们讨论一下使用这些方案的利弊:
IP: 在这个方案中, 我们限制每个 IP 的请求; 尽管在区分 "好" 和 "坏" 演员方面, 它不是最佳的, 但总比完全没有利率限制要好. 基于 IP 的节流最大的问题是, 当多个用户共享一个公共 IP 时, 就像在网吧或使用同一网关的智能手机用户一样. 一个坏用户可能会导致其他用户的限制. 缓存基于 IP 的限制时可能会出现另一个问题, 因为黑客甚至可以从一台计算机上获得大量 IPv6 地址, 所以让服务器耗尽跟踪 IPv6 地址的内存是很简单的!
用户: 在用户身份验证之后, 可以对 API 进行速率限制. 一旦通过身份验证, 将向用户提供一个令牌, 用户将在每次请求时传递该令牌. 这将确保我们对具有有效身份验证令牌的特定 API 进行速率限制. 但如果我们必须限制登录 API 本身? 这种速率限制的缺点是, 黑客可以通过输入错误的凭据来对用户执行拒绝服务攻击; 之后, 实际用户将无法登录.
如果我们把这两个方案结合起来怎么样?
混合: 一个正确的方法可以是同时进行每 IP 和每用户速率限制, 因为它们单独实现时都有缺点, 但是这将导致更多的缓存条目, 每个条目都有更多的细节, 因此需要更多的内存和存储.
参考资料:
grok_system_design_interview.PDF
来源: https://www.qcloud.com/developer/article/1829042