如何设计一个API速率限制器？
在互联网增长速度趋于稳定的今天，许多大厂已将面试重心从八股文转向场景题，也就是系统设计，强调应聘者在实际工作环境中的解决问题能力。这就是我推出的系统设计系列的初衷，专注于系统设计的深度学习和面试技巧。在这个系列中，提供大量真实的系统设计场景题，以及高效的解决方案。无论您是初学者还是资深从业者，都能在这里得到宝贵的知识和经验。点击关注
我们来设计一个API速率限制器，它将根据用户发送的请求数量对用户进行限流。
难度级别：中等
1. 什么是速率限制器？
假设我们有一个服务，它收到了大量的请求，但是它每秒只能处理有限数量的请求。要处理这个问题，我们需要某种节流或速率限制机制，只允许一定数量的请求，这样我们的服务才能响应所有的请求。在高级别上，速率限制器限制了一个实体（用户、设备、IP等）在特定时间窗口内可以执行的事件数量。例如：
• 用户每秒只能发送一条消息。
• 用户每天只能进行三次信用卡交易失败。
• 单个IP每天只能创建二十个账户。
一般来说，速率限制器限制了发送者在特定时间窗口内可以发出的请求数量。一旦达到上限，就会阻止请求。
2. 我们为什么需要API速率限制？
速率限制有助于保护服务不受针对应用层的恶意行为的侵害，如拒绝服务（DOS）攻击，暴力破解密码尝试，暴力破解信用卡交易等。这些攻击通常是HTTP/S请求的弹幕，看起来像是来自真实用户，但通常是由机器（或机器人）生成的。因此，这些攻击往往更难检测，更容易导致服务、应用程序或API宕机。
速率限制也被用来防止收入损失，降低基础设施成本，阻止垃圾邮件，阻止在线骚扰。以下是一些可以通过速率限制使服务（或API）更可靠的场景列表：
• 行为不端的客户端/脚本：有些实体可能会有意或无意地通过发送大量请求来压垮服务。另一个情况可能是，当用户发送大量低优先级的请求，我们希望确保这不会影响高优先级的流量。例如，不应该允许发送大量请求获取分析数据的用户影响其他用户的关键交易。
• 安全：通过限制用户允许进行的第二因素尝试次数（在2因素认证中），例如，他们尝试错误密码的次数。
• 防止恶意行为和糟糕的设计实践：没有API限制，客户端应用程序的开发者会使用马虎的开发策略，例如，反复请求同样的信息。
• 控制成本和资源使用：服务通常针对正常的输入行为设计，例如，用户在一分钟内写一篇帖子。计算机可以轻松地通过API每秒推送数千个请求。速率限制器可以对服务API进行控制。
• 收入：某些服务可能希望根据客户服务的等级限制操作，从而根据速率限制创建收入模型。所有的API服务可能都有默认的限制。要超越这个限制，用户必须购买更高的限制。
• 消除流量峰值：确保服务对其他所有人保持在线。
3. 系统的需求和目标
我们的速率限制器应满足以下要求：
功能需求：
1. 限制一个实体在一定时间窗口内可以向API发送的请求数量，例如，每秒15个请求。
2. API可以通过一个集群进行访问，所以应考虑在不同服务器间的速率限制。无论是在单个服务器还是在多个服务器的组合中超过定义的阈值，用户都应该收到一个错误信息。
非功能需求：
1. 系统应该高可用。速率限制器应始终工作，因为它保护我们的服务不受外部攻击。
2. 我们的速率限制器不应引入大量的延迟，影响用户体验。
4. 如何进行速率限制？
速率限制是一个过程，用于定义消费者访问API的速率和速度。节流是控制客户在给定期间使用API的过程。节流可以在应用程序级别和/或API级别定义。当节流限制被突破时，服务器返回HTTP状态“429 - 请求过多”。
5. 有哪些不同类型的节流？
以下是三种不同的节流类型，被不同的服务使用：
硬节流：API请求的数量不能超过节流限制。
软节流：在这种类型中，我们可以设置API请求限制超过一定的百分比。例如，如果我们有每分钟100条信息的速率限制和10%的超出限制，我们的速率限制器将允许每分钟最多110条信息。
弹性或动态节流：在弹性节流下，如果系统有一些可用资源，请求的数量可以超过阈值。例如，如果一个用户每分钟只允许发送100条信息，当系统中有可用资源时，我们可以让用户每分钟发送超过100条信息。
6. 用于速率限制的不同类型的算法是什么？
以下是用于速率限制的两种类型的算法：
固定窗口算法：在这个算法中，时间窗口是从时间单位的开始到时间单位的结束。例如，对于一分钟来说，无论API请求是在哪个时间段做出的，都会被认为是0-60秒。在下面的图中，0-1秒之间有两条信息，1-2秒之间有三条信息。如果我们有每秒两条信息的速率限制，那么这个算法只会节流‘m5’。
滚动窗口算法：在这个算法中，时间窗口是从请求发出的时间的一部分开始，加上时间窗口的长度。例如，如果在一秒钟的第300毫秒和第400毫秒发送了两条信息，我们会把它们算作从那一秒的第300毫秒到下一秒的第300毫秒的两条信息。在上面的图中，保持每秒两条信息，我们会节流‘m3’和‘m4’。
7. 速率限制器的高级设计
速率限制器将负责决定哪个请求将由API服务器处理，哪个请求将被拒绝。一旦新的请求到达，Web服务器首先会询问速率限制器是否会被处理或被节流。如果请求没有被节流，那么它将被传递给API服务器。
8. 基本的系统设计和算法
让我们以我们希望限制每个用户的请求数量为例进行讨论。在这种情况下，对于每个独特的用户，我们会记录该用户已经发送了多少个请求，以及我们开始计数请求的时间戳。我们可以把这些信息存储在一个哈希表中，其中“键”是“用户ID”，“值”是一个结构，包含一个代表“计数”的整数和一个代表时间戳的整数。
假设我们的限速器每分钟允许每个用户发送三个请求，那么每当有新的请求进入，我们的限速器会执行以下步骤：
1. 如果哈希表中不存在“用户ID”，则插入它，将“计数”设置为1，将“开始时间”设置为当前时间（规范化为一分钟），并允许该请求。
2. 否则，找到“用户ID”的记录，如果当前时间 - 开始时间 >= 1分钟，将“开始时间”设置为当前时间，“计数”设置为1，并允许该请求。
3. 如果当前时间 - 开始时间 <= 1分钟并且
image-20230718210656680 o 如果“计数 < 3”，增加计数并允许请求。o 如果“计数 >= 3”，拒绝请求。
我们的算法有什么问题呢？
1. 这是一个固定窗口算法，因为我们在每分钟结束时都会重置“开始时间”，这意味着它可能每分钟允许两倍数量的请求。假设Kristie在一分钟的最后一秒发送了三个请求，那么她可以在下一分钟的第一秒立即发送三个更多的请求，这样在两秒的时间内就有6个请求。这个问题的解决方案将是一个滑动窗口算法，我们稍后将讨论。
image-20230718210706648 2. 原子性：在分布式环境中，“读然后写”的行为可以创建一个竞态条件。假设Kristie当前的“计数”为“2”，并且她发出了两个更多的请求。如果两个独立的进程服务了每个这些请求并在任何一个更新它之前同时读取了计数，每个进程都会认为Kristie可以有一个更多的请求，并且她还没有达到速率限制。
image-20230718210733156
如果我们正在使用Redis来存储我们的键值，解决原子性问题的一个解决方案是在读-更新操作期间使用Redis锁。然而，这会以减慢同一用户的并发请求并引入另一层复杂性为代价。我们可以使用Memcached，但它会有相似的复杂性。
如果我们正在使用一个简单的哈希表，我们可以有一个自定义的实现对每个记录进行“锁定”，以解决我们的原子性问题。
我们需要多少内存来存储所有的用户数据呢？假设我们保持所有的数据在一个哈希表中的简单解决方案。
假设“用户ID”占用8字节。我们还假设一个2字节的“计数”可以计数到65k，这对我们的使用案例来说是足够的。尽管时间戳需要4字节，但我们可以选择只存储分钟和秒部分，这可以放入2字节。因此，我们需要总共12字节来存储一个用户的数据： 8 + 2 + 2 = 12字节
假设我们的哈希表对每个记录有20字节的开销。如果我们需要在任何时候跟踪一百万个用户，我们需要的总内存将是32MB： (12 + 20)字节 * 1百万 => 32MB
如果我们假设我们需要一个4字节的数字来锁定每个用户的记录以解决我们的原子性问题，我们将需要总共36MB的内存。
这可以轻松地放入一台服务器；然而，我们不希望将所有的流量通过一台机器路由。另外，如果我们假设每秒10个请求的速率限制，这将转化为我们的速率限制器的1000万QPS！这将是
对于一台服务器来说过于庞大。在实际操作中，我们可以假设我们会在分布式设置中使用类似Redis或Memcached的解决方案。我们将所有数据存储在远程的Redis服务器中，所有的速率限制器服务器在服务或限制任何请求之前，都会读取（并更新）这些服务器。
9. 滑动窗口算法
如果我们可以跟踪每个用户的每个请求，那么我们可以维护一个滑动窗口。我们可以在哈希表的'值'字段中的Redis排序集合中存储每个请求的时间戳。
假设我们的限速器每分钟每用户允许三次请求，所以，每当有新请求进来时，限速器将执行以下步骤：
1. 从排序集合中删除所有“当前时间 - 1分钟”之前的时间戳。
2. 计算排序集合中元素的总数。如果此计数大于我们的限速限制“3”，则拒绝请求。
3. 将当前时间插入排序集合并接受请求。
我们需要多少内存来存储滑动窗口的所有用户数据呢？假设'用户ID(UserID)'需要8个字节。每个时刻需要4个字节。假设我们需要每小时限制500个请求。假设哈希表的开销为20字节，排序集合的开销为20字节。最多，我们需要总共12KB来存储一个用户的数据：
8 + (4 + 20（排序集开销）) * 500 + 20（哈希表开销） = 12KB
这里我们为每个元素预留了20字节的开销。在一个排序集合中，我们可以假设我们至少需要两个指针来维护元素之间的顺序 - 一个指向前一个元素，一个指向下一个元素。在一个64位的机器上，每个指针将消耗8个字节。所以我们需要16个字节来存储指针。我们额外添加了一个字（4字节）用来存储其他开销。
如果我们需要随时跟踪一百万个用户，我们需要的总内存将是12GB：
12KB * 100万 ~= 12GB
相比于固定窗口，滑动窗口算法需要更多的内存；这将是一个可扩展性问题。如果我们能结合上述两种算法来优化我们的内存使用呢？
10. 带计数器的滑动窗口
如果我们使用多个固定时间窗口来跟踪每个用户的请求计数，例如，我们的限速时间窗口大小的1/60。例如，如果我们有一个每小时的速率限制，我们可以每分钟计数一次，并在收到新请求计算限流限制时，计算过去一小时内所有计数器的总和。这将减少我们的内存占用。让我们以每小时500次请求的速率限制，以及每分钟10次请求的附加限制为例。这意味着当过去一小时内带时间戳的计数器之和超过请求阈值（500）时，Kristie就超过了速率限制。除此之外，她每分钟不能发送超过10次请求。这是一个合理和实际的考虑，因为没有真正的用户会频繁发送请求。即使他们这么做，他们也会因为他们的限制每分钟都会重置而看到重试成功。
我们可以在Redis哈希中存储我们的计数器，因为它为少于100个键提供了非常高效的存储。当每个请求在哈希中递增一个计数器时，它也会设置哈希在一小时后过期。我们将每个‘时间’标准化到一分钟。
我们需要多少内存来存储带计数器的滑动窗口的所有用户数据？假设'用户ID(UserID)'需要8个字节。每个时刻需要4个字节，计数器需要2个字节。假设我们需要每小时限制500个请求。假设哈希表的开销为20字节，Redis哈希为20字节。由于我们将每分钟保留一个计数，因此每个用户最多需要60个条目。我们需要总共1.6KB来存储一个用户的数据：
8 + (4 + 2 + 20 (Redis哈希开销)) * 60 + 20 (哈希表开销) = 1.6KB
如果我们需要随时跟踪一百万个用户，我们需要的总内存将是1.6GB：
1.6KB * 100万 ~= 1.6GB
因此，我们的'带计数器的滑动窗口'算法比简单的滑动窗口算法减少了86%的内存使用。
11. 数据分片和缓存
我们可以基于‘用户ID(UserID)’进行分片，以分配用户的数据。为了容错和复制，我们应该使用一致性哈希。如果我们想为不同的API设置不同的限流限制，我们可以选择按用户和API进行分片。以URL缩短器(URL Shortener)为例；我们可以为每个用户或IP的createURL()和deleteURL() API设定不同的速率限制器。
如果我们的API是分区的，一个实际的考虑可能是为每个API分片也有一个单独的（相对较小的）速率限制器。以我们的URL缩短器为例，我们希望限制每个用户每小时不超过100个短URL。假设我们正在为我们的createURL() API使用基于哈希的分区，我们可以限制每个分区，使用户除了每小时不超过100个短URL外，每分钟也不超过3个短URL。
我们的系统可以从缓存近期活跃用户中获得巨大的好处。应用服务器可以在击中后端服务器之前快速检查缓存是否有所需的记录。我们的速率限制器可以通过仅在缓存中更新所有计数器和时间戳，从写回缓存中获得显著的好处。对永久存储的写入可以在固定间隔进行。这样我们可以确保速率限制器对用户请求增加的延迟最小。读取总是可以先击中缓存；这在用户达到他们的最大限制，而速率限制器只是读取数据而不进行任何更新时，将是极其有用的。
最近最少使用（LRU）可以是我们系统的合理缓存淘汰策略。
12. 我们应该按IP还是按用户限制速率？
让我们讨论一下使用这些方案的优点和缺点：
IP：在这种方案中，我们限制每个IP的请求；虽然在区分“好”和“坏”行为者方面不是最优的，但它仍然比不设限制要好。基于IP限制的最大问题是当多个用户共享一个公共IP，比如在网吧或使用相同网关的智能手机用户。一个不良用户可能会导致其他用户被限流。当缓存基于IP的限制时，可能会出现另一个问题，因为即使一台计算机可以为黑客提供大量的IPv6地址，让服务器因跟踪IPv6地址而耗尽内存是轻而易举的！
用户：限速可以在用户认证后的API上完成。一旦认证，用户将被提供一个令牌，用户将在每个请求中传递这个令牌。这将确保我们将对具有有效认证令牌的特定API进行限速。但如果我们必须在登录API本身进行限速呢？这种限速的弱点在于，黑客可以通过输入错误的凭证达到限制次数，从而对用户进行拒绝服务攻击；之后，真正的用户将无法登录。
如果我们将上述两种方案结合起来怎么样呢？
混合：正确的方法可能是同时进行每个IP和每个用户的限速，因为它们在单独实施时都有弱点，不过，这将导致更多的缓存条目，每个条目有更多的详细信息，因此需要更多的内存和存储空间。
推荐阅读
你好，我是拾叁，7年开发老司机、互联网两年外企5年。怼得过阿三老美，也被PR comments搞崩溃过。这些年我打过工，创过业，接过私活，也混过upwork。赚过钱也亏过钱。一路过来，给我最深的感受就是不管学什么，一定要不断学习。只要你能坚持下来，就很容易实现弯道超车！所以，不要问我现在干什么是否来得及。如果你还没什么方向，可以先关注我，这里会经常分享一些前沿资讯和编程知识，帮你积累弯道超车的资本。