Design a Distributed Rate Limiter

Question

Design a rate limiting service for an API gateway. Compare token bucket, leaky bucket, and sliding window algorithms. Cover distributed coordination across data centers and handling edge cases like clock skew.

Codemia · Accepted Answer

- **Functional Requirements**:
  - Implement a distributed rate limiter using a token bucket algorithm.
  - Support multi-tenancy to handle different rate limits for various users.
  - Provide APIs to check current usage and remaining tokens for clients.
  - Support burst and sustained rate limits, allowing clients to exceed limits temporarily.

- **Non-functional Requirements**:
  - Ensure low latency (under 50ms) for rate limit checks and enforcement.
  - Achieve high availability with a 99.9% uptime SLA.
  - Support horizontal scaling to accommodate growing API usage without significant reconfiguration.
  - Ensure fault tolerance, allowing the system to degrade gracefully under high load.

Assuming Perplexity has 10,000 active users querying the LLM API:
- Each user makes an average of 10 requests per minute, leading to a total of:
  - Total requests per minute = 10,000 users * 10 requests/user = 100,000 requests/minute.
- In a burst scenario, let's assume that 20% of users might make requests simultaneously:
  - Burst requests = 2,000 users * 20 requests/user = 40,000 burst requests/minute.
- Thus, the system should be designed to handle at least 140,000 requests per minute with a provision for scaling to 200,000 requests/minute.
- This translates to approximately 3,000 requests per second on average.

The architecture consists of the following components:
- **API Gateway** (e.g., NGINX or AWS API Gateway):
  - Routes requests to the appropriate microservices and performs initial rate limit checks.

- **Rate Limiter Service** (Node.js or Go-based microservice):
  - Implements the token bucket algorithm and handles requests from the API Gateway.
  - Communicates with Redis for distributed state management.

- **Redis Cluster**:
  - Stores token buckets for each user and provides fast access for rate limiting checks.
  - Utilizes Redis Pub/Sub for notifications of token refill events.

- **Monitoring & Logging** (Prometheus and Grafana):
  - Monitors rate limiting actions and logs for audit and performance metrics.

- **Database** (PostgreSQL):
  - Stores user profiles and their configured rate limits.

The schema design would consist of the following tables:
- **Users Table**:
  - `user_id` (PK, UUID): Unique identifier for each user.
  - `rate_limit` (INTEGER): Maximum tokens a user can have.
  - `token_bucket` (INTEGER): Current tokens available in the user's bucket.
  - `last_refill_time` (TIMESTAMP): Last time tokens were refilled.

- **Rate Limiting Events Table** (optional for logging):
  - `event_id` (PK, UUID): Unique identifier for each event.
  - `user_id` (FK, UUID): Reference to the Users table.
  - `timestamp` (TIMESTAMP): Time of the event.
  - `action` (ENUM): Action taken (e.g., `allowed`, `denied`).

- This schema supports efficient access patterns for checking and updating token counts and tracking usage.

- **Redis vs. Database for State Management**:
  - Redis provides faster access for real-time rate limiting, but it is an in-memory store, leading to potential data loss on failure. A hybrid approach could be used where Redis is the primary for fast access, and periodic snapshots are stored in a PostgreSQL database for recovery.

- **Token Bucket vs. Sliding Window Algorithms**:
  - The token bucket algorithm is simpler to implement and supports burst traffic well, making it a good fit for this use case. However, it can lead to unfair usage if not monitored correctly. A sliding window approach could provide better fairness but requires more complex calculations and state management.

- **Graceful Degradation**:
  - Implementing a fallback mechanism to deny requests or serve cached responses when limits are hit adds complexity but is essential to maintain user experience. The trade-off involves balancing user satisfaction with resource conservation during peak loads.

Design a Distributed Rate Limiter

Google

How to Approach This

Sharpen Your Skills on Codemia

Sample Answer

Requirements

Capacity Estimation

Submit Your Answer

Google Software Engineer Interview Guide

Related Questions

Design a high-throughput Inventory Management System

Design a low-latency Rate Limiting System

Design a fault-tolerant Payment System

Design a fault-tolerant Messaging System

Design Walmart Product Search