题目：设计一个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和每用户速率限制，因为它们单独实现时都有缺点，但是这将导致更多的缓存条目，每个条目都有更多的细节，因此需要更多的内存和存储。
参考资料：
