Requirements

Functional Requirements:

List the key functional requirements for the system (Ask the AI for hints if stuck)...

• Rate limiter has to pass requests before limit, and reject requests over limit
• Rate limiter has to filter requests exactly
• Rate limiter has to return 429 error code for rejected requests
• Rate limiter has to support any rule type (e.g. limit by userId, messages per second, etc.)

Non-Functional Requirements:

List the key non-functional requirements (performance, scalability, reliability, etc.)...

• Low latency - rate limiter shouldn't delay requests
• Rate limiter hasn't be a single point of failure
• Horizontal scalability - Rate limiter has to work in distributed environment
• Low memory usage
• Rate limiter has to be fault tolerance

Capacity Estimation

Estimate the scale of the system. Consider daily active users, read/write ratio, storage requirements, bandwidth, and any relevant QPS calculations...

• 1M DAU
• Suppose every user does 5000 requests per day - 1M * 5000 = 5 billion requests per day = 57K requests/sec
• QPS = 57 * 20 = 1M requests/sec
• All requests are writes
• If we support request count per user we have 1M requests counters
• 1M users * rule number * 100 byte = 100 MB
• A few KB in memory for rule config and metadata

API Design

Define the APIs expected from the system. This is your chance to analyze and define the read and write paths so that you can come up with the high-level design...

POST /check - check if request is allowed

body: userId, IP, API method, API url, request body if need

200 - if request is allowed,

headers:

X-Ratelimit-Limit - requests count for time interval

X-Ratelimit-Remaining - remaining requests count for time interval

429 - if requests isn't allowed

headers:

X-Ratelimit-Limit - requests count for time interval

X-Ratelimit-Remaining - remaining requests count for time interval

X-Ratelimit-Retry-After - time after which requests will be allowed

POST /rule - add rule

body: rule name, time interval, requests count, applied for (user, IP, global), etc.

201 - rule is created

{"id": 1234},

400 - invalid data

401 - No authorization

403 - Access forbidden

PUT /rule/{id} - update rule

body: rule name, time interval, requests count, applied for (user, IP, global), etc.

200 - rule is updated

400 - invalid data

401 - No authorization

403 - Access forbidden

404 - Rule doesn't exist

DELETE /rule/{id} - delete rule

200 - rule is deleted

400 - invalid data

401 - No authorization

403 - Access forbidden

404 - Rule doesn't exist

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.

Client sends a request to rate limiter middleware. Rate limiter reads rule from config files. We can keep rules in local memory. Then rate limiter gets a counter from Redis. Counter increments by 1. If counter > limit, request is rejected and we return 429 status code and header X-Ratelimit-Retry-After header to client. If counter <= limit, we pass the request further.

Admin sends POST, PUT, DELETE requests for adding, updating, deleting rate limiter rules to rate limiter middleware. Rules are written to config files. After file changes we should notify rate limiter instances about them.

For distributed enviroment we should to have some instances of rate limiter middleware. We should place instances in different data centers. We should use the nearest data center to process request. So requests will be processed fast. We should have one Redis instance to support counters consistency. If Redis is unavailable, we should to pass requests further.

Database Design

Define the data model. Identify the main entities, their attributes, and relationships. Consider the choice of database type (SQL vs NoSQL) and justify your decision based on access patterns...

Redis data structure {prev_window_count, curr_window_count, window_start_time}. Every counter has a key {subject_type, subject_id, api}. We can shard by these keys. For celebrity problem we can add salt to key.

We can keep rules in relational DB. We have small amount of data and they changes rarely. Table for rules: id, rule_type, time_unit, requests_per_unit, subject_type (userId, IP, api, or global)

Detailed Component Design

Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.

We chose sliding window counter algorithm. We get counter value by formula: counter in previous interval * percent of previous interval in sliding interval + counter in current interval. This algorithm is memory sufficient because we only have to save counter in previous interval and counter in current interval. This algorithm also helps to align traffic surge. Fixed window algorithms doesn't support this. For token bucket it is difficult to set speed of adding tokens.

It is better to use Lua scripting to atomicy and avoid race conditioning. Redis data structure {prev_window_count, curr_window_count, window_start_time}.

When Redis itself is slow or down, we allow requests through