【系统设计】系统设计基础：速率限制器
什么是速率限制器？
速率限制是指防止操作的频率超过定义的限制。 在大型系统中，速率限制通常用于保护底层服务和资源。 速率限制一般在分布式系统中作为一种防御机制，使共享资源能够保持可用性。
速率限制通过限制在给定时间段内可以到达您的 API 的请求数量来保护您的 API 免受意外或恶意过度使用。 在没有速率限制的情况下，任何用户都可以用请求轰炸您的服务器，从而导致其他用户饿死的峰值。
Rate limiting at work
为什么要限速？
- 防止资源匮乏：速率限制的最常见原因是通过避免资源匮乏来提高基于 API 的服务的可用性。如果应用速率限制，则可以防止基于负载的拒绝服务 (doS) 攻击。即使一个用户用大量请求轰炸 API，其他用户也不会挨饿。
- 安全性：速率限制可防止暴力破解登录、促销代码等安全密集型功能。对这些功能的请求数量在用户级别受到限制，因此暴力破解算法在这些场景中不起作用。
- 防止运营成本：在按使用付费模式自动扩展资源的情况下，速率限制通过对资源扩展设置虚拟上限来帮助控制运营成本。如果不采用速率限制，资源可能会不成比例地扩展，从而导致指数级的账单。
速率限制策略
速率限制可应用于以下参数：
- 用户：限制在给定时间段内允许用户的请求数。基于用户的速率限制是最常见和最直观的速率限制形式之一。
- 2. 并发性：这里限制了在给定时间范围内用户可以允许的并行会话数。并行连接数量的限制也有助于缓解 DDOS 攻击。
- 3. 位置/ID：这有助于运行基于位置或以人口统计为中心的活动。可以限制不是来自目标人口统计的请求，以提高目标区域的可用性
- 4. 服务器：基于服务器的速率限制是一种利基策略。这通常在特定服务器需要大部分请求时使用，即服务器与特定功能强耦合
速率限制算法
漏桶：
漏桶是一种简单直观的算法。它创建一个容量有限的队列。在给定时间范围内超出队列容量的所有请求都会溢出。
这种算法的优点是它可以平滑请求的突发并以恒定的速率处理它们。它也很容易在负载均衡器上实现，并且对每个用户来说都是高效的内存。无论请求的数量如何，都保持到服务器的恒定接近均匀的流量。
Leaky Bucket
该算法的缺点是请求的爆发可能会填满存储桶，导致新请求的匮乏。它也不能保证请求在给定的时间内完成。
2、令牌桶：
令牌桶类似于漏桶。在这里，我们在用户级别分配令牌。对于给定的持续时间 d，定义了用户可以接收的请求 r 个数据包的数量。每次新请求到达服务器时，都会发生两个操作：
- 获取令牌：获取该用户的当前令牌数。如果它大于定义的限制，则丢弃请求。
- 更新令牌：如果获取的令牌小于持续时间 d 的限制，则接受请求并附加令牌。
该算法具有内存效率，因为我们为我们的应用程序为每个用户节省了更少的数据量。这里的问题是它可能导致分布式环境中的竞争条件。当来自两个不同应用程序服务器的两个请求同时尝试获取令牌时，就会发生这种情况。
Token Bucket Algorithm
3、固定窗口计数器：
固定窗口是最基本的限速机制之一。 我们在给定的时间内保留一个计数器，并为我们收到的每个请求不断增加它。 一旦达到限制，我们将丢弃所有进一步的请求，直到重置持续时间。
这里的优点是它确保最近的请求得到服务，而不会被旧的请求饿死。 但是，在限制边缘的单个流量突发可能会囤积当前和下一个时隙的所有可用时隙。 消费者可能会轰炸边缘的服务器，以尝试最大化所服务的请求数量。
Fixed Window Counter
4. 滑动日志：
滑动日志算法涉及在用户级别维护带有时间戳的请求日志。系统将这些请求时间排序在一个集合或一个表中。它丢弃所有时间戳超过阈值的请求。我们每一分钟都在寻找旧的请求并将它们过滤掉。然后我们计算日志的总和来确定请求率。如果请求将超过阈值速率，则保留它，否则提供服务。
该算法的优点是不受固定窗口边界条件的影响。速率限制的执行将保持精确。由于系统会跟踪每个消费者的滑动日志，因此不会出现挑战固定窗口的踩踏效应。
但是，为每个请求存储无限数量的日志可能会很昂贵。计算也很昂贵，因为每个请求都需要计算消费者先前请求的总和，可能跨服务器集群。因此，它不能很好地扩展以处理大量流量或拒绝服务攻击。
5、Sliding Window：
这类似于Sliding Log算法，但内存效率高。它结合了固定窗口算法的低处理成本和滑动对数改进的边界条件。
我们保留一个按时间排序的条目列表/表格，每个条目都是混合的，包含时间戳和当时的请求数。我们保留一个持续时间的滑动窗口，并且仅在我们的窗口中以给定的速率提供服务请求。如果计数器的总和大于限制器的给定速率，那么我们只取等于速率限制的第一个条目总和。
滑动窗口方法是最好的方法，因为它提供了扩展速率限制的灵活性和良好的性能。速率窗口是一种向 API 使用者呈现速率限制数据的直观方式。它还避免了漏桶的饥饿问题和固定窗口实现的爆裂问题
分布式系统中的速率限制
上述算法非常适用于单服务器应用程序。但是当分布式系统涉及到多个节点或应用服务器时，问题就变得非常复杂。如果有多个限速服务分布在不同的服务器区域，问题就会变得更加复杂。在这些情况下遇到的两个广泛问题是不一致和竞争条件。
不一致
对于具有分布在不同区域的多个应用服务器并具有自己的速率限制器的复杂系统，我们需要定义一个全局速率限制器。
如果消费者在短时间内收到大量请求，它可能会单独超过全局速率限制器。节点数越多，用户越有可能超过全局限制。
有两种方法可以解决这些问题：
- 粘性会话：在您的负载均衡器中设置一个粘性会话，以便每个消费者都准确地发送到一个节点。缺点包括节点过载时缺乏容错和扩展问题。您可以在此处阅读有关粘性会话的更多信息
- 集中式数据存储：使用 Redis 或 Cassandra 等集中式数据存储来处理每个窗口和消费者的计数。增加的延迟是一个问题，但提供的灵活性使其成为一个优雅的解决方案。
比赛条件
竞争条件以高并发的获取然后设置的方法发生。每个请求都获取 counter 的值，然后尝试增加它。但是当写操作完成时，其他几个请求已经读取了计数器的值（这是不正确的）。因此，发送的请求数量超出了预期。这可以通过在读写操作上使用锁来缓解，从而使其成为原子操作。但这是以性能为代价的，因为它成为导致更多延迟的瓶颈。
节流
限制是在给定时间段内控制客户对 API 的使用的过程。可以在应用程序级别和/或 API 级别定义限制。当超过油门限制时，服务器返回 HTTP 状态“429 — 请求太多”。
节流类型：
- Hard Throttling：API 请求数不能超过限制。
- Soft Throttling：在这种类型中，我们可以将 API 请求限制设置为超过一定百分比。例如，如果我们的速率限制为每分钟 100 条消息并且 10% 超出限制，那么我们的速率限制器将允许每分钟最多 110 条消息。
- 弹性或动态限制：在弹性限制下，如果系统有一些可用资源，请求的数量可能会超过阈值。例如，如果一个用户每分钟只允许发送 100 条消息，我们可以让该用户每分钟发送超过 100 条消息，当系统中有可用资源时。
谢谢阅读！
References
- Sticky sessions:
- Kong API Gateway:
- Token Bucket:
原文：https://medium.com/geekculture/system-design-basics-rate-limiter-351c09…
- 114 次浏览