考察点:令牌桶的编码实现与并发安全细节,检验是否真正理解限流算法的工程落地,编程题。
要点(讲解):
令牌桶核心是「惰性补充」——不在定时任务里续令牌,而在每次请求时按当前时间补够令牌,再用 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),自写需处理时钟回拨与精度问题。
题目与答案就在本页;收藏、批注和错题重练在应用内