Prompt and context
One tenant buys a global allowance of 30,000 requests per minute with a burst capacity of 6,000. Traffic enters three active regions, and a cross-region decision on every request would miss the latency objective. Design only the global coordination layer; assume each region already has a correct local token bucket.
The answer must quantify what happens when demand moves between regions, a region is partitioned, or the coordinator fails. HTTP 429 and Retry-After communicate rejection to clients, but they do not choose the internal limiting algorithm.
What the interviewer evaluates
- Whether you state that low latency, partition availability, and an exact global ceiling cannot all be assumed at once.
- Whether quota is conserved across leases instead of copied to every region.
- Whether unused capacity can be reclaimed without double spending.
- Whether failure policy and maximum overshoot are measurable.
Clarifying questions to ask
- Is the global number a hard abuse boundary or a commercial target with tolerated error?
- During a partition, should a region stop when its lease is empty or continue within an emergency allowance?
- How quickly can traffic move, and how uneven can regional demand become?
- Does one request have unit cost, or do endpoints consume weighted cost?
- Is temporary under-utilization preferable to overshoot?
For a hard ceiling, a partitioned region may use only its unexpired lease. A best-effort commercial limit may permit an explicitly bounded emergency allowance.
A 30-second answer
“I would have a strongly ordered coordinator manage two leasable resources: a global refill rate of 500 requests per second and a global burst capacity of 6,000. It leases short-lived refill-rate and burst shares to regions, which consume through their existing local atomic token buckets. At all times, overlapping active leases sum to at most 500 requests per second and 6,000 burst tokens; renewal updates parameters without refilling the local balance. During a traffic shift, an old share must be returned or expire before reallocation. A hard-limit region stops after lease expiry during a partition; a best-effort region may use a separate emergency allowance whose sum is the documented overshoot bound.”
Step-by-step deep dive
1. Preserve quota as a conservation invariant
Convert 30,000 requests per minute to continuous refill rate R = 500 req/s, with burst capacity B = 6000. At all times, sum(active_lease.refill_rate) <= R and sum(active_lease.burst_capacity) <= B. A lease has tenant, region, epoch, rate share, burst share, activation time, expiry, and unique ID. Initial regional balances sum to at most B, and renewal, expansion, or reconfiguration cannot create balance from nothing; total admissions over any interval are therefore at most R × duration + B. Failover uses a durable lease ledger and a higher epoch; existing leases count against both limits until acknowledged return or expiry.
2. Consume locally and renew before exhaustion
The regional bucket refills at its leased rate and caps its balance at the leased burst share; each request still decrements atomically. An uninterrupted renewal extends or changes rate and capacity while preserving the existing balance, truncating it when capacity falls rather than filling the bucket again. After a lease gap, the next lease starts at zero balance unless the coordinator transfers confirmed reclaimed tokens. Shorter leases tighten rebalancing and failure bounds but increase renewal load. Choose duration from measured peaks, coordinator capacity, and tolerated disconnection time.
3. Rebalance without double spending
Healthy regions report balance and demand. The coordinator reduces the cold region's rate and burst share in its next lease, then gives released shares to the hot region. Until the old lease is acknowledged as returned or expires, overlapping old and new leases both count against the two limits. Return acknowledgement first invalidates the old bucket; increasing capacity in the hot region creates no balance, which starts at zero or receives only confirmed transferred tokens. Returns are idempotent; when status is uncertain, temporarily under-utilize rather than allocate the same share twice.
4. Make failure semantics explicit
With a hard ceiling, a region refills only while its lease is valid. If it cannot renew, expiry invalidates the local bucket and discards any balance that was not transferred through a confirmed return; the cost is temporary under-utilization. If each region has emergency allowance E outside the normal burst bound, maximum additional allowance is the sum of budgets that can activate while disconnected, and that mode cannot claim strict zero overshoot. Coordinator failure does not invalidate issued leases. A replacement restores the durable ledger, fences the old issuer with a higher epoch, and continues counting unexpired old leases.
A strong sample answer
“The existing regional token buckets stay on the synchronous path. I add a global coordinator that represents 30,000 requests per minute as a 500-request-per-second refill rate and separately manages 6,000 requests of burst capacity. It issues epoch-fenced, expiring rate and burst shares while ensuring that active leases sum to at most 500 requests per second and 6,000 burst tokens.
Each region refills its local bucket at the leased rate and caps it at the leased burst share. Uninterrupted renewals preserve balance, and extra capacity does not create balance. A hot region receives only confirmed returned tokens, or starts refilling from zero after the cold lease expires. Under a hard limit, a partitioned region invalidates its bucket after lease expiry. If the business authorizes 100 extra emergency tokens per region, the documented partition overshoot is at most the sum of emergency budgets whose activation rules can overlap. Failover restores the lease ledger and uses a new epoch. I would test traffic shifts, duplicate returns, overlapping renewals, clock skew, and network partitions against both invariants.”
Common mistakes
- Giving every region the full rate and burst capacity → the global limit multiplies by region count → lease rate and burst shares separately.
- Reusing a returned lease before the return is certain → the same tokens can be spent twice → make returns idempotent or wait for expiry.
- Saying “eventual consistency” without an error bound → nobody knows the possible overshoot → state lease and emergency-budget bounds.
- Refilling the local bucket on every renewal → each renewal creates another burst → preserve balance and update only rate, capacity, and validity.
- Failing over without fencing → two coordinators may issue valid quota → attach a monotonic epoch to every lease.
Follow-up questions and responses
How do you choose lease size?
Choose duration, refill-rate share, and burst share separately. Set duration from tolerated disconnection time, assign rate from recent demand, and assign burst from peaks within the global 6,000 capacity. Shorter duration speeds rebalancing and tightens failure bounds but raises renewal load.
What happens when traffic suddenly moves regions?
The coordinator reduces the cold region's rate and burst share in its next lease, then transfers the released shares after acknowledged return or old-lease expiry. The system may temporarily reject despite unused capacity while waiting; that is the cost of preventing overlapping overallocation.
How do you return Retry-After?
Use the earliest of the next local refill under the current lease, a confirmed new-lease activation, or expected coordinator recovery, rounded to the response's supported precision. Do not promise a time if recovery is unknown; return a bounded retry policy instead.
Can the design guarantee zero overshoot and full partition availability?
Only if each partition already holds enough preallocated quota, which can strand capacity, or if requests synchronously coordinate across regions, which sacrifices latency and partition availability. The answer must choose the product boundary explicitly.