API 速率约束器是一个用于操控运用程序或服务对API恳求的频率的服务。速率约束一般用于操控资源的运用、防止乱用和保护服务的安稳性。
类似的产品有：Express Rate Limit、Spring Boot Rate Limiter、Ratelimiter
难度级别：中等
1、什么是API速率约束服务？
想象一下，咱们有一个服务正在接纳很多恳求，但它每秒只能处理有限数量的恳求。为了处理这个问题，咱们需求某种节省或速率约束机制，只答应一定数量的恳求，这样咱们的服务就能对一切恳求进行呼应。从高层次来看，速率约束器约束了一个实体（用户、设备、IP等）在特定时刻窗口内能够履行的事情数量。例如：
- 一个用户每秒只能发送一条音讯。
- 用户每天只能有三次信用卡买卖失败。
- 单个IP每天只能创立二十个账号。
总的来说，速率约束器约束了发送者在特定时刻窗口内能够宣布的恳求数量，当到达上限时，它会阻止恳求。
2、为什么需求API速率约束？
速率约束的效果就好比是给你的服务穿上一件“防弹背心”，能够抵挡一些歹意进犯，比方拒绝服务进犯，暴力破解暗码或许信用卡信息等。这些进犯往往像海量的HTTP/S恳求砸过来，表面上看似乎是实在用户在操作，实则或许是机器人在背面操控，因此这种进犯更加难以发现，也更有或许导致你的服务、运用或API被拖垮。
别的，速率约束还能帮助咱们节省开支，下降保护网络设施的费用，防止垃圾邮件和网络打扰。以下是一些能从速率约束中获益，使服务或API更安稳牢靠的状况：
- 操控不守规则的客户端或脚本：有些用户或许脚本或许会一股脑儿地发送很多恳求，这无论是故意仍是无意，都或许让你的服务受不了。别的，有些用户或许会频频地发送一些不那么重要的恳求，咱们得保证这种行为不会影响到重要的流量。比方，有的用户或许频频地恳求数据剖析，咱们不能让这种行为妨碍到其他用户的重要操作。
- 提升安全性：例如咱们能够约束用户在两层认证中测验暗码的次数，防止暗码被测验破解。
- 防止乱用和不合理的规划实践：假如咱们对API的运用没有约束，开发者或许会懒散下来，比方重复恳求同样的信息，这样不只浪费资源，也不符合好的开发习惯。
- 操控本钱和资源运用：咱们的服务一般是为正常运用状况规划的，比方一个用户每分钟发一篇帖子。假如没有约束，一些核算机或许会一秒钟就经过API推送不计其数条信息。所以咱们需求用速率约束来操控API的运用状况。
- 提高收入：某些服务或许会根据用户的付费级别来约束他们的操作，这样就能根据约束来发生收入。例如，咱们能够对一切的API设定一个默许的运用上限，假如用户想要更多运用权，就需求付费升级。
- 防止流量突增：保证服务即便面对很多恳求，也能继续正常为其他用户供给服务。
3、体系需求和方针
咱们的流量操控器需求到达以下要求：
功用要求：
- 约束一个实体在一段时刻内能够向API发送的恳求次数，例如每秒钟15次恳求。
- API是经过集群来供给的，所以限流应该在整个集群中进行，跨服务器的恳求都应归入考虑。无论是在单台服务器仍是在多台服务器上，只要超越了预设的阈值，用户都应该看到一个过错信息。
非功用要求：
- 体系应该高度可用。流量操控器需求随时待命，由于它是咱们的服务对抗外部进犯的重要工具。
- 咱们的流量操控器不该引入过多的推迟，以防止影响用户体验。
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、根本的体系规划和算法
咱们以每个用户的恳求次数约束为例。在这种场景下，咱们为每个用户设置计数器，记载用户现已宣布了多少个恳求，以及咱们开端计数恳求的时刻戳。咱们能够将这些信息存放在一个哈希表中，其中’key’是’UserID’，’value’是一个包含一个用于’Count’的整数和一个用于Epoch时刻的整数的结构：
假定咱们的流量操控器答应每个用户每分钟宣布三个恳求，那么每逢有新恳求进来，咱们的流量操控器将履行以下过程：
-
假如’UserID’在哈希表中不存在，将其刺进，将’Count’设为1，将’StartTime’设为当时时刻（规范化为分钟），然后答应该恳求。
-
否则，找到’UserID’的记载，假如 CurrentTime – StartTime >= 1分钟，将’StartTime’设为当时时刻，’Count’设为1，并答应恳求。
-
假如 CurrentTime – StartTime <= 1分钟，且
- 假如 ‘Count< 3’，添加计数并答应恳求。
- 假如 ‘Count>= 3’，拒绝恳求。
咱们的算法存在什么问题？
- 固定窗口算法：由于咱们在每分钟结束时重置’StartTime’，这意味着或许每分钟答应两倍数量的恳求。假定一个用户在一分钟的最终一秒发送了三个恳求，然后她鄙人一分钟的榜首秒当即发送了三个更多的恳求，这就导致在两秒内有6个恳求。这个问题的解决计划是滑动窗口算法，咱们稍后将讨论。
- 原子性：在分布式环境中，“读-然后-写”的行为或许会发生竞态条件。假定用户当时’Count’是”2″，而且她宣布了两个或许更多的恳求。假如这两个恳求由两个独立的进程处理，而且在任何一个进程更新它之前同时读取了Count，那么每个进程都会以为用户还能有一个恳求，而且她还没有到达速率约束。
假如咱们运用Redis来存储咱们的键值，解决原子性问题的一个解决计划是在读取-更新操作期间运用Redis锁。然而，这将以下降同一用户的并发恳求速度和添加另一层复杂性为价值。咱们能够运用Memcached，可是它会有类似的问题。
假如咱们运用简略的哈希表，咱们能够对每条记载进行确定以解决咱们的原子性问题。
咱们需求多少内存来存储一切的用户数据呢？让咱们假定一个简略的解决计划，即咱们将一切的数据保存在一个哈希表中。
假定’UserID’需求8 bytes。咱们也假定一个2 bytes的’Count’，能够计数到65k，对咱们的运用场景来说现已足够了。虽然epoch时刻需求4 bytes，咱们能够选择只存储分钟和秒部分，这能够用2 bytes来存储。因此，咱们需求一共12 bytes来存储用户的数据：
8+2+2=12bytes8 + 2 + 2 = 12 bytes 8+2+2=12bytes
假定咱们的哈希表每条记载需求额定20 bytes的开支。假如咱们需求在任何时候盯梢一百万用户，咱们需求的总内存是32MB：
(12+20)bytes∗1million=>32MB(12 + 20) bytes * 1 million => 32MB (12+20)bytes∗1million=>32MB
假如咱们假定需求一个4-byte的数来确定每个用户的记载以解决咱们的原子性问题，咱们将需求一共36MB的内存。
这能够轻松地放在一台服务器上；然而咱们不期望将一切的流量都路由到一台机器上。此外，假如咱们假定一个速率约束为每秒10个恳求，那么这将对咱们的流量操控器发生1000万QPS！这对一台服务器来说太多了。实践上，咱们能够假定咱们将在一个分布式环境中运用类似Redis或Memcached这样的解决计划。咱们将一切的数据存储在远程的Redis服务器中，一切的流量操控器服务器将在处理或节省任何恳求之前读取（和更新）这些服务器。
9、Sliding Window（滑动窗口）算法
假如咱们能够追寻每个用户的每个恳求，咱们就能够保护一个滑动窗口。咱们能够在哈希表的’value’字段中的Redis Sorted Set（有序集合）中存储每个恳求的时刻戳。
假定咱们的速率约束器每分钟每用户答应3个恳求，那么，每逢有新恳求进来，速率约束器将履行以下过程：
- 从Sorted Set中移除一切早于”CurrentTime（当时时刻） – 1分钟”的时刻戳。
- 核算Sorted Set中元素的总数。假如这个计数大于咱们的阈值”3″，则拒绝恳求。
- 在Sorted Set中刺进当时时刻并承受恳求。
咱们运用滑动窗口，要存储一切用户的数据需求多少内存呢？假定’UserID’需求8 byte。每个epoch时刻将需求4byte。假定咱们需求每小时500个恳求的速率约束。假定哈希表有20 byte的开支，Sorted Set有20 byte的开支。最多，咱们需求一共12KB来存储一个用户的数据：
8 + (4 + 20 (Sorted Set开支)) * 500 + 20 (哈希表开支) = 12KB
这里咱们为每个元素预留了20 byte的开支。在一个Sorted Set中，咱们能够假定咱们至少需求两个指针来保护元素之间的顺序 —— 一个指向前一个元素，一个指向后一个元素。在64位机器上，每个指针将占用8byte。所以咱们将需求16byte用于指针。咱们额定添加了一个word（4 byte）用于存储其他开支。
假如咱们需求在任何时候盯梢一百万用户，咱们需求的总内存将是12GB：
12KB∗1million=12GB12KB * 1million ~= 12GB 12KB∗1million=12GB
与Fixed Window（固定窗口）比较，Sliding Window算法占用了很多的内存；这会是一个可扩展性问题。假如咱们能够结合运用上述两种算法来优化咱们的内存运用会怎样呢？
10、带计数器的滑动窗口
假如咱们用多个固定的时刻窗口来追寻每个用户的恳求计数，例如，1/60的咱们速率约束的时刻窗口大小会怎样呢？例如，假如咱们有一个小时的速率约束，咱们能够每分钟计数一次，并在收到新恳求时核算过去一个小时内一切计数器的总和，以核算阈值。这样能够减少咱们的内存占用。比方，咱们约束每小时500次恳求，每分钟最多10次恳求。这意味着，当过去一小时内带时刻戳的计数器之和超越恳求阈值（500）时，用户就超越了速率约束。此外，她每分钟不能发送超越十个恳求。这是一个合理而实用的考虑，由于没有实在的用户会频频发送恳求。即便他们这么做，他们也会由于每分钟约束都会重置而看到重试的成功。
咱们能够在Redis哈希中存储咱们的计数器，由于它为少于100个键供给了极其高效的存储。当每个恳求在哈希中添加一个计数器时，它也会设置哈希在一小时后过期。咱们将每个’time’（时刻）规范化到一分钟。
咱们运用带计数器的滑动窗口，存储一切用户的数据需求多少内存呢？假定’UserID’需求8byte。每个epoch时刻将需求4byte，Counter（计数器）将需求2byte。假定咱们需求每小时500个恳求的速率约束。假定哈希表有20byte的开支，Redis哈希有20byte的开支。由于咱们每分钟都会进行计数，所以最多，每个用户需求60个条目。咱们需求一共1.6KB来存储一个用户的数据：
8 + (4 + 2 + 20 (Redis哈希开支)) * 60 + 20 (哈希表开支) = 1.6KB
假如咱们需求在任何时候盯梢一百万用户，咱们需求的总内存将是1.6GB：
1.6KB * 1百万 ~= 1.6GB
所以，咱们的’带计数器的滑动窗口’算法比简略的滑动窗口算法少用86%的内存。
11、数据分片和缓存
关于用户ID的数据，咱们能够进行分片处理以涣散用户数据。为了容错和仿制，咱们应该运用“一致性哈希”。假如咱们期望对不同的API实施不同的限流规范，咱们能够选择每个用户每个API进行分片。以“URL短链接生成器”为例，咱们能够对每个用户或IP的createURL()和deleteURL() API设置不同的限流规则。
假如咱们的API是分区的，一个实践的考虑是为每个API分片也设置一个相对较小的限流器。以咱们的URL短链接生成器为例，咱们期望约束每个用户每小时不超越100个短URL的创立。假定咱们运用根据哈希的分区方式对createURL() API进行分区，咱们能够设置每个分区的限流器，答应每个用户每分钟创立不超越3个短URL，别的每小时创立不超越100个短URL。
咱们的体系能够从缓存近期活跃用户中取得巨大的优点。运用服务器能够在击中后端服务器之前快速查看缓存是否有所需记载。咱们的限流器能够从Write-back缓存中取得显著的优点，只在缓存中更新一切计数器和时刻戳。对永久存储的写入能够在固定的时刻距离进行。这样咱们能够保证限流器对用户恳求添加的推迟最小。读取操作一直先击中缓存，这在用户到达最大约束时非常有用，由于限流器将只读取数据而不进行任何更新。
关于API速率约束服务来说，最近最少运用（Least Recently Used，LRU）或许是一个合理的缓存驱赶策略。
12、咱们应该依照IP仍是用户进行限流？
让咱们来讨论一下运用这两种计划的优缺点：
IP：在此计划中，咱们对每个IP的恳求进行限流；虽然在区分“好”与“坏”行为者方面并非最佳，但它依然比彻底没有限流要好。根据IP的限流最大的问题在于，当多个用户同享一个公网IP时，如在网吧或运用相同网关的智能手机用户。一个行为不当的用户或许导致对其他用户的限流。另一个问题或许出现在缓存IP约束时，由于即便一个核算机也有很多的IPv6地址可供黑客运用，让服务器因盯梢IPv6地址而耗尽内存是轻而易举的事！
用户：限流能够在用户认证后对API进行。一旦认证成功，用户将取得一个令牌，用户将在每次恳求时传递该令牌。这将保证咱们对具有有效认证令牌的特定API进行限流。可是，假如咱们必须对登录API本身进行限流怎么办？这种限流的弱点是，黑客能够经过输入过错的凭证到达限流阈值来对用户进行拒绝服务进犯；之后，实践的用户将无法登录。
假如咱们结合以上两种计划会怎么样呢？
混合：一个正确的方法或许是同时进行每IP和每用户的限流，由于它们在单独实施时都有弱点，然而，这将导致更多的缓存条目，每个条目需求更多的细节，因此需求更多的内存和存储空间。
