Requirements

Functional Requirements:

• Supports both per-user AND per-API rate limits.
  • example: Two endpoints, foo and bar. foo allows 1000 requests per minute, but only up to 10 per user per minute. Bar allows 2000 per minute, but only up to 30 per minute per user.
• Admins can add/update/delete/view rate-limit rules via an API or console.
  • clarification: What rules are supported? Let's assume a simple schema with two properties per endoint: endpoint_quota, user_quota.
• clarification: What time ranges? daily limit? Weekly limit? minute limit? We will assume only per-minute limit for simplicity.
• clarification: How is quota measured? Number of requests? Total request time? We'll assume it's request count.

Non-Functional Requirements:

• Checking the rate limit must be very low latency, because it will be done on every single API request and we don't want it to impact performance across the system.

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...

Every request calls get_api_quota to check if the request can be processed. If not enough quota, return an appropriate error to the client.

Every request calls record_request(endpoint, user_id), which is processed by backends to increment per-endpoint and per-user counters.

// Checking the rate limit for an endpoint and user

get_api_quota(endpoint: str, user_id: str)

Response

{

endpoint_max_quota: int

endpoint_remaining_quota: int

user_max_quota: int

user_remaining_quota: int

}

// Incrementing request counters

record_request(endpoint: str, user_id: str)

Response

{

// Nothing returned.

}

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 general idea is to implement a request counter using key-value stores. For per-user quota, we'll use "endpoint:user_id" as the key, and for endpoints we'll just use "endpoint" as the key. The values will be of the form:

{

"remaining_quota": int

"last_token_refill_time": Timestamp

}

Then we can implement a token-bucket filter as follows:

1. Token refill rate is set by Admin. Let's say it's 1 per second.
2. Whenever Rate Limit Service reads a record, it compute the number of tokens that would have been generated since last_token_refill_time, then updates remaining_quota and sets last_token_refill_time accordingly. Never increments remaining_quota abot the max configured quota.
3. Calling record_request() decrements remaining_quota by 1, but does not go below 0.

Early in the request processing, e.g. in an API Gateway, we call get_api_quota() which hits a Rate Limit Service and reads from the key-value store to check if the request should be allowed. If the request is allows to process, we call record_request()

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.

The per-user rate limits have good horizontal scaling, because the storage keys containing user ID naturally distribute across database shards. We may add a caching layer, either in Rate Limit Service or even locally on the Web Server.

Per-endpoint rate limit is more challenging. Even with in-memory databases like Redis, if the entire system is reading/writing a single key (for the endpoint) this could overload the service. There are a few options to deal with this:

1. Split endpoint into multiple keys, e.g. endpoint-1, endpoint-2, etc. record_request is routed deterministically to one of them when writing. Reads must read every key and sum them to get the total request count. This is not an ideal solution, because our non-functional requirement of low-latency. Fan-out when reading the keys will definitely increase request latency.
2. If we can tolerate some delay in consistency and potential data loss, let the web server or Rate Limit Service buffer request counts for a time (say 100 ms) before updating the store. This could reduce the number of writes by an order of magnitude if QPS is high.
3. Like 1, split the endpoint key. But instead of deterministically writing to one, pick one at random to update. Then to compute total quota remaining, we read one of the keys and multiply it by the number of shards to approximate the total quota. This won't yield 100% accurate results, but may be good enough to protect our system from DDOS attacks.