面试题库

30 天从前端工程师到 Agent 工程师

D29 弱项补强 + 编码热身：rate limiter、LRU、并发控制、流式 JSON 解析

• 限流器有哪几种常见算法？各自的优缺点是什么？如果只能落地一种，你选哪个？What are the common rate limiting algorithms, what are their trade-offs, and which one would you actually ship?

  国内高频海外高频基础#rate-limiting#concurrency

  分析过程 · 先想清楚再作答

  1. 这题在考「你知不知道限流有多种语义」，而不是「你会不会写计数器」。只答出一种算法的人，会被默认没做过真正的流量治理。
  2. 先把四种按复杂度排开再逐个给弱点：固定窗口最省内存但有边界双倍；滑动窗口日志最精确但内存和请求数同阶；滑动窗口计数是近似解、内存回到常数；令牌桶允许突发、内存常数。这个排列顺序本身就是答案的骨架。
  3. 边界双倍要用具体数字讲，它是本题最常见的追问：限每分钟 100 次，用户在 12:00:59 打满 100 次，12:01:00 计数器清零又能打 100 次，跨边界的这 2 秒实际放行了 200 次。说不出这个例子，等于没答第一问。
  4. 结论选令牌桶，理由要落在业务形状上：真实流量本来就是突发的，令牌桶同时约束了长期速率（补充速度）和瞬时突发（桶容量），两个旋钮分别对应两个业务问题。实现上必须是惰性补充——取的时候按时间差现算，不要给每个用户起一个定时器，十万用户就是十万个定时器。
  5. 生产视角：单机内存版只在单实例下成立。多个网关实例共享配额时，「读余额 → 算补充 → 写回」三步之间一定有竞态，两个实例都读到「还剩 1 个」就会双双放行。修法是把三步塞进一段 Redis Lua 脚本，靠单线程执行整段脚本拿到原子性——用 Lua 不是为了快，是为了把三条命令粘成一条。
  6. 可以预期的追问：脚本里为什么不直接取当前时间？因为那会让脚本变得不确定，时间戳应该由调用方传进来；代价是各实例的时钟要大致对齐，这个取舍要主动说出口。

  How to reason about it · think before answering

  1. This question tests whether you know rate limiting has several distinct semantics, not whether you can write a counter. Naming only one algorithm reads as never having run real traffic.
  2. Lay the four out by complexity and attach a weakness to each: fixed window is cheapest but has the boundary burst; sliding window log is exact but its memory grows with request count; sliding window counter is an approximation with constant memory; token bucket allows bursts with constant memory. That ordering is the skeleton of a good answer.
  3. Make the boundary burst concrete, because it is the standard follow-up: with a 100-per-minute limit, a client can spend 100 at 12:00:59 and another 100 the instant the counter resets at 12:01:00 — 200 requests inside two seconds, double the quota.
  4. Pick the token bucket and justify it by traffic shape: real traffic is bursty, and the bucket gives you two independent knobs — refill rate caps the long-run rate, capacity caps the burst. Implement it with lazy refill: compute the top-up from the elapsed time when a token is requested, never run a timer per user.
  5. Production angle: the in-memory version only holds for a single instance. Across gateway replicas, read-compute-write has a race and two replicas can both see 'one token left' and both allow. Fix it with a Redis Lua script so refill and deduction happen in one atomic step — Lua is not for speed here, it is for gluing three commands into one.
  6. Expect the follow-up: why not read the clock inside the script? Because that makes the script non-deterministic. Pass the timestamp in from the caller, and say the cost out loud — replica clocks now have to be roughly aligned.

  答题要点

  • 四种算法：固定窗口（省内存但边界双倍）、滑动窗口日志（精确但内存与请求数同阶）、滑动窗口计数（近似、常数内存）、令牌桶（允许突发、常数内存）
  • 固定窗口的边界双倍：跨窗口交界的 2 秒内可以放行两倍配额，下游是数据库或模型 API 时足以打穿
  • 落地选令牌桶：补充速度管长期速率、桶容量管瞬时突发，两个旋钮对应两个真实业务约束
  • 必须用惰性补充：取令牌时按时间差现算，不要为每个 key 起定时器
  • 分布式版把补充与扣减写进一段 Redis Lua 脚本，先 GET 再 SET 一定有竞态；时间戳由调用方传入以保持脚本确定性

  Key points

  • Four algorithms: fixed window (cheap, boundary burst), sliding window log (exact, memory grows with requests), sliding window counter (approximate, constant memory), token bucket (bursty, constant memory)
  • The fixed-window boundary burst lets twice the quota through in the two seconds around a window edge, which is enough to overload a database or model API
  • Ship the token bucket: refill rate bounds the long-run rate and capacity bounds the burst, two knobs for two real constraints
  • Use lazy refill — top up from elapsed time on access instead of running one timer per key
  • For the distributed version, put refill and deduction in one Redis Lua script; a GET followed by a SET always races. Pass the timestamp in to keep the script deterministic