IT 面试题库

请用 Java 手写一个简单令牌桶限流器(支持 tryAcquire),并解释关键参数与线程安全做法。

中级编程题Java后端工程师令牌桶限流Java并发安全CAS

题目

考察点:令牌桶的编码实现与并发安全细节,检验是否真正理解限流算法的工程落地,编程题。

参考答案

内容深度:详细 · 含示例/代码 · 来源:外部链接 · 未复核 · 54 天前更新 · 技术内容可能随版本变化,建议结合官方文档理解

要点(讲解):

令牌桶核心是「惰性补充」——不在定时任务里续令牌,而在每次请求时按当前时间补够令牌,再用 CAS/原子变量扣减,避免锁竞争。关键参数:capacity(桶容量,决定可突发量)、rate(每秒补充速率=限流 QPS)、tokens(当前可用令牌)、lastTs(上次补充时间)。线程安全用 AtomicLong 存 tokens 与 lastTs,按「先算补充→再 CAS 扣减」的顺序重试即可,无需 synchronized。

public class TokenBucket {
    private final long capacity;      // 桶容量(可突发上限)
    private final double rate;        // 每秒补充速率 = 限流 QPS
    private final AtomicLong tokens;  // 当前令牌数(放大 1000 倍避免小数)
    private final AtomicLong lastTs;  // 上次补充时间(ms)

    public TokenBucket(long capacity, double rate) {
        this.capacity = capacity * 1000;
        this.rate = rate * 1000;
        this.tokens = new AtomicLong(this.capacity);
        this.lastTs = new AtomicLong(System.currentTimeMillis());
    }

    public boolean tryAcquire() {      // 取 1 个令牌
        long now = System.currentTimeMillis();
        while (true) {
            long last = lastTs.get();
            long elapsed = now - last;
            long cur = tokens.get();
            long added = (long) (elapsed * rate / 1000); // 按时间补令牌
            long next = Math.min(capacity, cur + added);
            if (next < 1000) return false;               // 令牌不足
            if (tokens.compareAndSet(cur, next - 1000)
                && lastTs.compareAndSet(last, now)) {
                return true;
            }
        }
    }
}

注意:实际生产建议用成熟库(Guava RateLimiter / Sentinel),自写需处理时钟回拨与精度问题。

练这道题

同分类 · 高频题

题目与答案就在本页;收藏、批注和错题重练在应用内

这道题看完了?连刷同类题,趁热打铁效果最好 进入刷题