likes
comments
collection
share

设计一个限流器：四种限流算法详解

作者站长头像
站长
· 阅读数 4

前言

Hi 你好，我是东东拿铁，95后奶爸程序员。

前一阵子，朋友在面试大厂时，笔试的设计题便是写一个限流器，工作多年来，这种比较基础的内容，实际上已经有些忘却。

所以这次也特地做一下梳理，包含了限流器的简介、算法以及具体实现。知识，常看常新，希望能够帮助到你。

限流器简介

在互联网日益发达的今天，想要系统做到高可用，限流是一种非常有效的的方式。

限流器是部署在网关中的一个过滤器（filter）组件，过滤器常见的还有验签、权限、登陆状态等，我们一般会把限流放到第一位。

什么是限流器？

限流器是一种用于控制流量的设备或机制，通常用于计算机网络、软件系统或其他数据传输过程中。限流器的主要目的是防止系统超负荷，确保资源分配合理，提高系统的稳定性和性能。

在计算机网络中，限流器可以应用于各种场景，包括：

  1. 网络流量控制： 限制网络流量，防止过度拥塞，确保网络的正常运行。这可以通过设置带宽限制、流量速率限制或连接数限制来实现。
  2. API访问控制： 对于Web服务或API，限流器可以用于控制每个用户或每个应用程序的请求频率，以防止滥用或恶意攻击。
  3. 数据库访问控制： 在数据库系统中，限流器可以用于限制对数据库的并发查询或事务数量，以防止数据库过载。
  4. 消息队列控制： 在分布式系统中，限流器可以应用于消息队列，以平衡生产者和消费者之间的速率，避免消息积压。
  5. 防护措施： 限流器还可以用于防止某些类型的攻击，如DDoS（分布式拒绝服务）攻击，通过限制恶意流量的速率。
  6. 限流器的实现可以基于不同的算法和策略，例如令牌桶算法、漏桶算法等。这些算法可以帮助平滑流量并确保在限制的范围内分配资源。

设计

综合设计

限流器配置

  • 远程配置，配置内容放入Redis缓存

  • 本地配置，本地缓存配置内容

限流方式

  • 全局限流，保护整个系统
  • 账号限流，根据登录信息获取用户，防止黑产，防刷
  • 设备限流，获取IP、IMEI、MAC等信息，限流
  • 接口限流，根据URL，保护接口

限流器算法

固定窗口算法

固定窗口限流算法就是将时间单位 unit 作为一个时间窗口，每个窗口仅允许限制流量内的请求通过，如图。

设计一个限流器：四种限流算法详解 大家可以看到上图，共有两个时间窗口，窗口单位为1s。当10:00:01时刻开始时，进入的请求，我们计数器+1，当时间进入10:00:02时，计数器清零。如果我们配置限流数是100，则窗口内请求当超过100时，我们直接返回503。循环往复即可。

优点：实现简单，易于理解。

但是，简单必然有他的缺点。

当在10:00:01快要结束时，进来100个请求，这时到了10:00:02，又进来一个请求，在1s内，系统实际进入了200个请求，我们的限流器，就似乎不是这么精准了。

滑动窗口算法

滑动窗口顾名思义，就是持续的滑动，但是窗口被分割成了更小的时间片。如下图所示

设计一个限流器：四种限流算法详解 每次滑动，都会滑过一小个时间片，形成新的限流窗口，就是滑动窗口了。我们的限流只需要在滑动窗口内执行固定窗口的算法就可以了。

滑动窗口可以避免固定窗口出现的放过两倍请求的问题，因为一个短时间内出现的所有请求必然在一个滑动窗口内，所以一定会被滑动窗口限流。

滑动窗口限流的核心思想如下：

  1. 初始化： 设定一个固定大小的时间窗口，例如一分钟，以及一个存储请求次数的滑动窗口数组。

  2. 处理请求： 每当有请求到达时，将当前时间戳对应的窗口位置的计数加1。

  3. 滑动窗口： 定期滑动时间窗口，去掉过期的时间段，并将相应位置的计数清零。

  4. 检查限流： 在处理新请求之前，检查当前时间窗口内的请求次数是否超过了限制。

总结一下 优点：简单易懂，精度高（通过调整时间窗口的大小来实现不同的限流效果），也解决了固定窗口，在临界时间处理的漏洞。

缺点：

  1. 时间粒度问题： 滑动窗口的时间窗口是固定的，可能难以适应不同请求的处理需求。例如，在一个 1 秒的窗口内，如果有 100 次请求，它们可能在这一秒钟内集中发生，也可能分布在这一秒钟的不同时间点。滑动窗口不能很好地应对这种不均匀的请求分布，可能导致对请求的处理过于粗略。
  2. 对突发流量的敏感性： 如果在一个较短的时间窗口内出现了大量请求，滑动窗口限流可能会突然限制请求，影响正常流量。这是因为在窗口内的请求次数超过限制时，就会拒绝后续的请求，无法很好地适应突发流量。
  3. 动态调整困难：如果系统在某个时间点需要更严格的流量控制，可能需要使用其他更灵活的限流策略。

漏桶限流算法

设计一个限流器：四种限流算法详解 漏桶算法（Leaky Bucket Algorithm）是一种简单且经典的限流算法，可以应用在限流场景。基本思想是，请求被看作是水滴，它们以固定的速率被添加到一个漏桶中，当漏桶满了时，多余的请求将被溢出或丢弃。

基本原理如下：

  1. 漏桶结构：漏桶是一个固定容量的容器，以恒定的速率漏水（发放请求）。
  2. 请求处理：每当有请求到达时，将其看作是一滴水，尝试放入漏桶。
  3. 容量限制：如果漏桶未满，请求将被接受并放入漏桶中。如果漏桶已满，则请求可能会被丢弃或等待下一个时间段。
  4. 漏水速率：漏桶以固定的速率漏水，即使突发请求到来，漏桶也能以一定的速率处理这些请求。

代码实现

public class LeakyBucket {
    private int capacity; // 漏桶容量
    private int rateLimit; // 漏水速率，每秒处理的请求数量
    private int waterLevel; // 漏桶中的水量
    private long lastLeakTime; // 上一次漏水的时间戳
    public LeakyBucket(int capacity, int rateLimit) {
    this.capacity = capacity;
    this.rateLimit = rateLimit;
    this.waterLevel = 0; 
    this.lastLeakTime = System.currentTimeMillis();
}

private long currentTimeInSeconds() {
    return System.currentTimeMillis() / 1000;
}

public synchronized void processRequest() {
    // 获取当前时间戳
    long currentTime = currentTimeInSeconds();
    // 计算时间间隔
    long timeInterval = currentTime - lastLeakTime;
    // 漏水：水量减少，但不能小于0
    waterLevel = Math.max(0, waterLevel - (int) (timeInterval * rateLimit));
    // 更新上一次漏水的时间戳
    lastLeakTime = currentTime;
    // 处理新的请求
    if (waterLevel < capacity) {
        waterLevel++;
        // 处理请求的逻辑，可以是放入队列、执行任务等
        System.out.println("Request processed successfully.");
    } else {
        // 请求被拒绝，漏桶已满
        System.out.println("Request rejected. Bucket is full.");
    }

}

public static void main(String[] args) {
    // 示例用法
    LeakyBucket bucket = new LeakyBucket(10, 2);
    // 模拟处理请求
    for (int i = 0; i < 15; i++) {
        bucket.processRequest();
    }
}

}

优点：

  1. 既能够限流，还能够平滑控制处理速度。

缺点：

  1. 当大量请求同时到达时，漏桶的处理速度恒定，会浪费一部分资源

令牌桶（Token Bucket）限流算法

设计一个限流器：四种限流算法详解

令牌桶（Token Bucket）算法，模拟一个特定大小的桶，然后向桶中以特定的速度放入令牌（token），当系统有请求时，必须从桶中取出一个令牌才能继续处理。如果桶中已经没有令牌了，那么当前请求就被限流，直接返回503。

Google的Guava包中的RateLimiter类就是令牌桶算法的解决方案。

实现代码就不放了，大家可以直接参考Guava的实现。这里总结一下实现关键点

  1. 记录上次生成令牌的时间
  2. 如果令牌桶为空，只需要计算上次生成的时间和当前时间的时间差，根据速率生成对应数量即可
总令牌数 = Math.min(令牌数上限值，总令牌数 +  (now - 最近生成令牌时间戳) / 令牌生成时间间隔)；

优点：

  1. 可以处理突发流量：令牌桶算法可以处理突发流量。当桶满时，能够以最大速度处理请求。这对于需要处理突发流量的应用场景非常有用；
  2. 限制平均速率：在长期运行中，数据的传输率会被限制在预定义的平均速率（即生成令牌的速率）；
  3. 灵活性：与漏桶算法相比，令牌桶算法提供了更大的灵活性。例如，可以动态地调整生成令牌的速率；

说在最后

限流器是一种非常典型的中间件，也许在日常工作中，我们不会接触到，但是它却无时无刻保护着我们的系统稳定，了解具体的实现原理，也是每一个后端程序员的必备要求，不知道你熟悉的是哪种限流算法呢？

最后，如果本文对你有帮助，欢迎点赞评论，每一个评论我都会认真回答。也欢迎加我的wx:Ldhrlhy10，加我进群，一起进步，成为更好的自己。