High-Level Design

Describe the overall system architecture. Identify the main components needed to solve the problem end-to-end. Use the diagramming tool to create a block diagram.

The request path: Client sends a request to the API Gateway. The gateway extracts the user identity and forwards the request to the Rate Limiting Service (RLS). RLS constructs a Redis key from the user identity and endpoint, runs a Lua script on Redis to atomically check and decrement tokens, and returns allow or deny. If allowed, the gateway forwards the request to the Backend Service. If denied, the gateway returns 429 with Retry-After.

API Gateway: authenticates, extracts user identity, routes to RLS. Does NOT make rate limiting decisions itself.
Rate Limiting Service (RLS): stateless workers. Each instance loads rules from a local cache (populated from PostgreSQL via NOTIFY). For each request, it constructs a key, calls Redis, interprets the result, and returns a decision.
Redis Cluster: stores all bucket state. Executes Lua scripts atomically. The single source of truth for token counts. Sharded by key hash for throughput.
PostgreSQL: stores rule configurations. Provides ACID transactions for admin operations. Publishes change events via NOTIFY.

The Lua script executes these steps atomically on Redis:

Read the hash fields tokens and last_refill from the bucket key.
Calculate elapsed time since last refill: elapsed = now - last_refill.
Refill tokens proportionally: tokens = min(max_tokens, tokens + elapsed * refill_rate).
Check: if tokens >= 1, decrement by 1 and return allowed with remaining count. Otherwise return denied with seconds until next token arrives.
Write updated tokens and last_refill back to the hash. Set TTL to 2x the window.

This lazy refill approach means idle buckets consume zero Redis resources. No background timer needed. Tokens accumulate mathematically when the next request arrives.

Submissions

Displaying Solutions with Scores Ranging from 1 to 10