面试题库

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
• 怎么实现一个限制并发数的调度器？为什么不能直接用 Promise.all 或者 asyncio.gather？How would you build a scheduler that caps in-flight async tasks, and why is Promise.all or asyncio.gather not enough?

  国内高频海外高频进阶#concurrency#async

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

  1. 题眼在后半句。面试官在确认你分不分得清「等待一批任务」和「限制同时运行的任务数」——这两件事在 API 名字上很像，在语义上毫无关系。
  2. 先说破错误答案为什么错：把 500 个任务全部映射成 Promise 再一起 await，这段代码的并发度是 500。Promise 一被创建，它内部的请求就已经发出去了，await 只是在等结果；gather 和 CompletableFuture.allOf 是同一个坑的另外两种口音。
  3. 再给正确形状的两条路：固定数量的工人从同一个游标取任务（JS 的惯用法，槽位就是工人本身），或者用信号量挡在任务启动之前（Python 的 asyncio.Semaphore、Java 的 Semaphore）。Swift 要用 TaskGroup 自己开滑动窗口，先塞满 limit 个、每收一个结果补一个。
  4. 本题真正的失分点是槽位泄漏：acquire 之后必须在 finally 里 release，或者把错误在任务内部收敛成结果值。忘了这一步的代码在 happy path 上完全正常，只有下游开始报错时才会一点点变慢直到彻底卡死——这是最难查的那类 bug，因为症状出现在故障之后而不是之中。
  5. 落到 Agent 场景说收益：批量 embedding、并行工具调用、多路子任务都靠它。收益不只是「不打爆下游」，还有同时驻留的内存与并发度同阶而不是与任务数同阶。
  6. 可以预期的追问：如果任务本身还要重试呢？答案是重试要在槽位内部完成（占着槽位退避重试），否则重试风暴会绕过限流；再追一层就是给重试加抖动，避免所有失败任务在同一时刻一起回来。

  How to reason about it · think before answering

  1. The hinge is the second half. They are checking whether you separate 'await a batch' from 'cap how many run at once' — similar API names, unrelated semantics.
  2. Name the wrong answer first: mapping 500 items to promises and awaiting them together runs at concurrency 500. Creating the promise already fired the request; awaiting only collects results. gather and CompletableFuture.allOf are the same trap in other accents.
  3. Then give the two correct shapes: a fixed set of workers pulling from a shared cursor (the JS idiom, where a worker is the slot), or a semaphore gating task start (asyncio.Semaphore, java.util.concurrent.Semaphore). Swift needs a manual window over a TaskGroup — fill limit slots, then add one task per result received.
  4. The real failure mode is slot leakage: release must happen in a finally, or the error must be collapsed into a result value inside the task. Code that misses this looks perfect on the happy path and only degrades once the downstream starts failing, which makes it one of the hardest bugs to trace.
  5. Tie it to agents: batch embedding, parallel tool calls, fan-out subtasks. The benefit is not only sparing the downstream — peak memory now scales with the concurrency limit instead of the task count.
  6. Expect the follow-up: what if tasks retry? Retries must happen inside the slot, otherwise a retry storm bypasses the limiter entirely. One level deeper: add jitter so failed tasks do not all come back at the same instant.

  答题要点

  • Promise.all 与 asyncio.gather 只负责等待，任务在被创建的那一刻就已经启动了，并发度等于任务总数
  • 两种正确形状：固定数量的工人从共享游标取任务，或者用信号量挡在任务启动之前
  • 槽位必须在任何退出路径上归还：Java 写在 finally 里，Python 用 async with，Swift 把错误收敛成结果值，JS 在循环里 try 与 catch
  • 槽位泄漏的症状是「下游一开始报错就越来越慢直到卡死」，happy path 完全看不出来
  • 收益是同时驻留的内存与并发度同阶，而不是与任务总数同阶；重试要占着槽位做，并加抖动

  Key points

  • Promise.all and asyncio.gather only wait; the work started when each promise was created, so concurrency equals the task count
  • Two correct shapes: a fixed worker set pulling from a shared cursor, or a semaphore gating task start
  • The slot must be returned on every exit path — finally in Java, async with in Python, error-to-value inside a Swift task, try/catch inside the JS loop
  • A leaked slot shows up as gradual slowdown to a full stall once the downstream starts erroring, and is invisible on the happy path
  • The payoff is peak memory scaling with the concurrency limit rather than the task count; retries must stay inside the slot and carry jitter