software

如何在系统设计面试中设计 Rate Limiter？

发布: (2025年12月19日 GMT+8 16:02)
8 min read
原文: Dev.to

Source: Dev.to

请提供您希望翻译的正文内容，我将按照要求保留源链接、格式和技术术语进行简体中文翻译。

什么是速率限制器？

Rate Limiter（速率限制器） 是系统组件，用于限制用户（或客户端）在给定时间范围内可以执行的操作次数。

示例

  • API 网关 – 每位用户每分钟仅允许 100 次请求。
  • 登录系统 – 在 10 分钟内仅允许 5 次失败尝试。
  • 消息应用 – 防止用户每秒发送超过 20 条消息。

如果用户超出这些限制，系统应阻止其请求（通常返回 HTTP 状态码 429 Too Many Requests）。

Rate limiting system design

面试中的关键限流系统需求

  • Correctness – 超出限制的请求会被拒绝。
  • Efficiency – 能以低延迟处理每秒数百万请求。
  • Scalability – 在跨多台服务器的分布式系统中工作。
  • Fairness – 避免出现允许突发流量的漏洞。
  • Configurability – 能轻松为每个用户、每个 API 等更改限制。

你也可以提出澄清性问题，例如：“我们是否需要对每个 URL 和每个 HTTP 方法设置限制？”

常用限流算法

固定窗口计数器

  • 将时间划分为固定窗口（例如，每分钟）。
  • 计数请求。
  • 简单，但在窗口边界可能出现突发。

滑动窗口日志

  • 在日志（数组/队列）中存储请求的时间戳。
  • 移除旧的时间戳。
  • 更加准确，但需要的内存与请求量成比例。

滑动窗口计数器

  • 使用当前窗口和前一个窗口的计数器，并按时间加权。
  • 内存高效，比固定窗口更平滑。

令牌桶 / 漏桶

  • 令牌以固定速率加入，请求消耗令牌。
  • 平滑流量，广泛用于生产系统。

如何在面试中设计限流器？

下面展示了两种流行的 Java 实现，易于在白板上解释和编码。

1. 滑动窗口日志（时间戳数组）

该方法为每个请求维护一个时间戳队列。在处理新请求之前：

  1. 移除早于配置时间窗口的时间戳。
  2. 如果队列大小低于限制，则允许请求并插入新的时间戳。
  3. 否则，拒绝请求。

Sliding Window Log 动画

Java 实现

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 简单的滑动窗口日志限流器。
 */
public class SlidingWindowLogRateLimiter {
    private final int maxRequests;
    private final long windowSizeInMillis;
    private final Deque<Long> timestamps = new ArrayDeque<>();

    public SlidingWindowLogRateLimiter(int maxRequests, int windowSizeInSeconds) {
        this.maxRequests = maxRequests;
        this.windowSizeInMillis = windowSizeInSeconds * 1000L;
    }

    /**
     * 返回 true 表示请求被允许，false 表示被拒绝。
     */
    public synchronized boolean allowRequest() {
        long now = System.currentTimeMillis();

        // 丢弃已超出当前窗口的时间戳
        while (!timestamps.isEmpty() && now - timestamps.peekFirst() > windowSizeInMillis) {
            timestamps.pollFirst();
        }

        if (timestamps.size() < maxRequests) {
            timestamps.addLast(now);
            return true;   // 请求被允许
        }
        return false;      // 请求被拒绝
    }

    // 演示
    public static void main(String[] args) throws InterruptedException {
        SlidingWindowLogRateLimiter limiter = new SlidingWindowLogRateLimiter(5, 10); // 每 10 秒 5 次请求
        for (int i = 1; i <= 7; i++) {
            System.out.println("Request " + i + ": " + (limiter.allowRequest() ? "allowed" : "rejected"));
            Thread.sleep(1500);
        }
    }
}

这种解法 非常适合面试，因为它简单直观，能够展示你对滑动窗口限流的理解。

2. 令牌桶

令牌桶算法 在生产环境中被广泛使用（例如 API 网关、微服务）。

  • 令牌以固定速率加入。
  • 每个请求消耗一个令牌。
  • 如果没有可用令牌，请求被拒绝。

如何在系统设计面试中设计限流器

Java 实现

public class TokenBucket {
    private final int capacity;
    private final double refillRate; // 每秒令牌数
    private double tokens;
    private long lastRefillTimestamp; // 纳秒

    public TokenBucket(int capacity, double refillRate) {
        this.capacity = capacity;
        this.refillRate = refillRate;
        this.tokens = capacity;
        this.lastRefillTimestamp = System.nanoTime();
    }

    public synchronized boolean allowRequest() {
        long now = System.nanoTime();
        double tokensToAdd = ((now - lastRefillTimestamp) / 1e9) * refillRate;
        tokens = Math.min(capacity, tokens + tokensToAdd);
        lastRefillTimestamp = now;

        if (tokens >= 1) {
            tokens -= 1;
            return true;    // 请求被允许
        }
        return false;       // 请求被拒绝
    }

    // 演示
    public static void main(String[] args) throws InterruptedException {
        TokenBucket bucket = new TokenBucket(10, 5); // 最大突发 10，5 令牌/秒补充
        for (int i = 1; i <= 15; i++) {
            System.out.println("Request " + i + ": " + (bucket.allowRe
quest() ? "allowed" : "rejected"));
            Thread.sleep(200);
        }
    }
}

此实现是线程安全的，并且在并发负载下表现良好。

面试策略（针对 Java 开发者）

当被问到 “你会如何设计一个限流器？” 时，你可以按以下要点展开：

  1. Fixed‑Window Counter – 易于解释，但存在边缘情况问题。
  2. Sliding‑Window Log – 使用 Deque<Long> 来保存时间戳。
  3. Token Bucket – 适用于突发流量的生产级解决方案。
  4. Distributed Rate Limiting – 提及基于 Redis 的计数器或 API 网关功能（例如 Nginx、Envoy）。

覆盖广度（算法知识）和深度（可运行的 Java 代码）展示了强大的系统设计能力。

系统设计面试准备资料

ByteByteGo

系统设计面试最佳资源

Codemia.io

破解系统设计面试的最佳资源

Exponent

  • 网站： https://bit.ly/3cNF0vw
  • 为顶级科技公司提供专业课程、模拟面试和系统设计材料。

典型的备考组合

  1. ByteByteGo – 理论与基础。
  2. Codemia – 实战练习。
  3. Exponent – 模拟面试和面试专项辅导。

最后思考

速率限制是那类面试题之一，能够考察你的 算法知识 和 系统设计直觉。

  • 对于一个简洁、面试准备好的答案，使用 Sliding Window Log 方法（例如 Java 中的 Deque）。
  • 为了展示生产级别的专业能力，还可以讨论 Token Bucket 算法。
Back to Blog

相关文章

阅读更多 »