Distributed Token-Bucket Rate Limiter

Coding round (distinct from the inbound/outbound rate-limiter system-design prompt): implement a per-user token-bucket limiter with lazy on-read refill, backed by a shared cache so the whole fleet enforces one limit. The follow-up is making the read-modify-write safe across concurrent servers. Problem Implement a distributed token-bucket rate limiter with lazy (on-read) refill. Each user has an independent bucket; tokens accrue over time up to a capacity and are spent one per request. State lives in a shared cache (Redis-style) so any server in the fleet enforces the same limit. You are given two primitives: class DistributedCache: def get(self, key: str) -> object | None: ... # None if the key is missing def put(self, key: str, value: object) -> None: ... @dataclass class TokenBucket: tokens: float # tokens currently available last_refill_time: float # unix ts of last refill capacity: int # max tokens the bucket can hold refill_rate: float # tokens added per second Implement two functions: def refill_token_bucket(bucket: TokenBucket, current_time: float) -> TokenBucket: ... # Add `elapsed * refill_rate` tokens, capped at `capacity`, and advance last_refill_time. # If current_time <= last_refill_time (clock skew), return the bucket unchanged. def allow_request(cache: DistributedCache, user_id: str, tokens_requested: int = 1, capacity: int = 100, refill_rate: float = 10.0) -> bool: ... # Key = f"rate_limit:{user_id}". A brand-new user starts with a FULL bucket. # Refill on read, then: if tokens >= tokens_requested -> deduct, save, return True; # else -> save the refilled bucket anyway (so credit keeps accruing), return False. Examples allow_request(cache, "user_123") # True (new bucket starts full: 100 tokens) # spend the remaining 99 quickly ... allow_request(cache, "user_123") # False (0 tokens left) # wait 1s at refill_rate=10 -> +10 tokens allow_request(cache, "user_123") # True refill: tokens=50, rate=10, +1s -> 60 refill: tokens=95, rate=10, +1s -> 100 (capped, not 105) refill: tokens=0, rate=10, +100s -> 100 (capped) refill: same timestamp -> unchanged Notes Lazy refill is the core idea: never run a background timer over millions of buckets — compute accrued tokens (elapsed * refill_rate) only when a request reads the bucket. The read-modify-write on a shared bucket races across servers (two servers both read 10, both write 9 → one token leaked). Fixes, in order of preference: Atomic server-side script (Redis Lua): do refill + check + deduct + EXPIRE in one uninterruptible eval. Fastest correct option at high QPS. Distributed lock on lock:rate_limit:{user_id}: correct but adds latency; on a lock-acquire timeout, decide fail-open vs fail-closed up front. Optimistic / CAS with a version field: retry on conflict; only worth it under low contention. Set a TTL (EXPIRE, e.g. 1h) on idle buckets so inactive users are garbage-collected from the cache. Variable per-user quota is the standard extension: store (capacity, refill_rate) per user (e.g. free 10/s, standard 100/s, enterprise 10_000/s) in a separate config lookup rather than hard-coding the defaults — large customers and internal tools buy higher limits. Token bucket allows bursts up to capacity; if the requirement is a smooth rate, name sliding-window-log / leaky-bucket as alternatives and explain the burst-vs-smoothness tradeoff. Preparation Write refill_token_bucket + allow_request from scratch in under 10 minutes; get the clock-skew guard and the "save the refilled bucket even on reject" detail right. Be able to write the Redis Lua atomic version and explain why folding refill + check + deduct into one eval removes the race. Publicly mirrored on the hack2hire xAI listing as "Token Limiter".