Loading...
Estimate the scale of the system. Consider daily active users, read/write ratio, storage requirements, bandwidth, and any relevant QPS calculations...
Assuming 1 billion DAU, and each user sends on average 100 request per day, the peak QPS we are looking at is around 3 million.
Assuming 1 billion users and 100 APIs, we have per-user/per-API rate limit set up. Depending on different rate limiting algorithms, we need to either store a counter per user, or event logs. Assuming we store up to past year of API events, and each API event storage per user is 1KB.
We will need 1KB * 1 billion users * 100 requests per day * 365 days = 36.5PB of storage.
For rule metadata, since it is implemented per API, assuming we have 100 APIs, and each rule takes 10MB. We only need 1GB of storage for storing all the rules, which is trivial compared to event logs.
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...
We will need to give admin access to add/update/delete/view API rate limiting rules:
GET view_rate_limit_rule {
api_id: UUID
}
POST update_rate_limit_rule {
api_id: UUID,
rule_update: String
}
POST add_rate_limit_rule {
api_id: UUID,
api_rule: String
}
DELETE delete_rate_limit_rule {
api_id: UUID
}
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.
In our API rate limiter, we first hit the load balancer that routes request to the appropriate server based on consistent hashing of user_id, this ensures that we can easily horizontally scale the servers.
Then in the actual rate-limiting servers, we store 2 things:
For both, we implement a caching layer to handle the repeated reads. We could use a redis cluster as caching layer, or even just caches on the servers.
The cache will be a write-through cache. When we write to the cache, we synchronously write to the database. This will lead to higher write latency and lower read latency. However, we need to have strong consistency for our use case so this is a necessary tradeoff.
In cases of cache misses or partial outage of the cache layer, requests will hit the underlying database to query data. If the request volume is too large, the database will implement load shedding and the server will implement circuit breakers. We will also implement TTL jittering and stale-while-revalidate to avoid thundering herd.
We do shard the database using consistent hashing of user_ids, so requests from different users will be distributed evenly. If certain shards are overloaded with very active keys, we can break down the hot keys to different shards. On the database layer, we also create read replicas for each write replica. For implementing rate limit, consistency is important, so any write needs to be synchronously updated to all replicas. This is a tradeoff between consistency and write latency.
To ensure even sharding, we use consistent hashing of user_ids. In a single hash ring, we assign different key ranges to different servers, with the use of virtual nodes as well to ensure more even distribution. For very hot keys, we can break down the key to smaller sub keys, and have them distributed in different ranges.
For any rule updates, they are written directly to the cache and underlying database, so any rule change will be immediately visible in the next read.
For our servers, we also need to determine the right algorithm to use. Here are a few and with tradeoffs:
Token bucket: For each API/user, we create a virtual bucket. The bucket refills tokens at a constant rate. If the tokens are depleted, we no longer allow any more requests. For this approach, the pro is that we can allow burst traffic up to capacity, and we implement accurate rate limiting that is memory efficient.
Sliding window log: Sliding window logs looks at the API events for each user for a given API, for the past period (like 1 minute), remove old/stale logs, and calculates the number of logs in this period, and whether it exceed the capacity. This approach is highly accurate, allows burst traffic. However, it is very memory intensive.
Sliding window counter: Sliding window counter breaks down time to different intervals. Then it looks at request count in current interval + a weighted percentage of previous window's total count. This is an estimated count, but it also allows burst without boundary problems, and it has low memory foot print.
In our use case, we will use token bucket. For this approach, we only need to store the tokens for each user/API, and still have accurate rate limiting.
We also need to address race conditions in our design. If 2 requests both try to read and update the tokens at the same time, we would have inconsistencies. In this case, we use atomic operations on the redis cluster, where read-calculation-write is considered as a single transaction. This will increase write latency, but gives us consistency.
If the whole RL system is down, we will use a fail-open policy, still allowing requests to flow through until it recovers. This is a tradeoff between availability and reliability.
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...
In the database, there are 2 kinds of data we need to store.
The first is rate limit rules, this is simple data allowing the servers to know what rate limit rule to implement for each API. This data is structured, and doesn't handle high read/write QPS. We choose a relational database for storing them.
The second is the actual rate limit metadata per user. Assuming we need to store all the API events for each user for the past year, this will be a very high throughput database.
We choose relational database, and will use sharding and replication to handle the high throughput.
Relational database isn't inherently scalable. But it's an acceptable tradeoff and we will navigate the complexity of scaling.
To design the rate limit metadata schema effectively, consider a relational database structure that captures essential elements for rate limiting per user and per API. A potential schema could include the following tables:
id (Primary Key, UUID): Unique identifier for the rate limit rule.user_id (Foreign Key): Identifier for the user this rule applies to.api_endpoint (VARCHAR): The specific API endpoint being limited.limit (INT): The maximum number of requests allowed.time_window (INT): The duration (in seconds) for which the limit applies.created_at (TIMESTAMP): Timestamp for when the rule was created.updated_at (TIMESTAMP): Timestamp for the last update to the rule.user_id (VARCHAR): Identifier for the user.api_endpoint (VARCHAR): The specific API endpoint.request_count (INT): The current count of requests made.last_request_time (TIMESTAMP): The time of the last request made.Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.
In the database, there are 2 kinds of data we need to store.
The first is rate limit rules, this is simple data allowing the servers to know what rate limit rule to implement for each API. This data is structured, and doesn't handle high read/write QPS. We choose a relational database for storing them.
The second is the actual rate limit metadata per user. Assuming we need to store all the API events for each user for the past year, this will be a very high throughput database.
We choose relational database, and will use sharding and replication to handle the high throughput.
Relational database isn't inherently scalable. But it's an acceptable tradeoff and we will navigate the complexity of scaling.
To design the rate limit metadata schema effectively, consider a relational database structure that captures essential elements for rate limiting per user and per API. A potential schema could include the following tables:
id (Primary Key, UUID): Unique identifier for the rate limit rule.user_id (Foreign Key): Identifier for the user this rule applies to.api_endpoint (VARCHAR): The specific API endpoint being limited.limit (INT): The maximum number of requests allowed.time_window (INT): The duration (in seconds) for which the limit applies.created_at (TIMESTAMP): Timestamp for when the rule was created.updated_at (TIMESTAMP): Timestamp for the last update to the rule.user_id (VARCHAR): Identifier for the user.api_endpoint (VARCHAR): The specific API endpoint.request_count (INT): The current count of requests made.last_request_time (TIMESTAMP): The time of the last request made.In our API rate limiter, we first hit the load balancer that routes request to the appropriate server based on consistent hashing of user_id, this ensures that we can easily horizontally scale the servers.
Then in the actual rate-limiting servers, we store 2 things:
For both, we implement a caching layer to handle the repeated reads. We could use a redis cluster as caching layer, or even just caches on the servers.
The cache will be a write-through cache. When we write to the cache, we synchronously write to the database. This will lead to higher write latency and lower read latency. However, we need to have strong consistency for our use case so this is a necessary tradeoff.
In cases of cache misses or partial outage of the cache layer, requests will hit the underlying database to query data. If the request volume is too large, the database will implement load shedding and the server will implement circuit breakers. We will also implement TTL jittering and stale-while-revalidate to avoid thundering herd.
We do shard the database using consistent hashing of user_ids, so requests from different users will be distributed evenly. If certain shards are overloaded with very active keys, we can break down the hot keys to different shards. On the database layer, we also create read replicas for each write replica. For implementing rate limit, consistency is important, so any write needs to be synchronously updated to all replicas. This is a tradeoff between consistency and write latency.
To ensure even sharding, we use consistent hashing of user_ids. In a single hash ring, we assign different key ranges to different servers, with the use of virtual nodes as well to ensure more even distribution. For very hot keys, we can break down the key to smaller sub keys, and have them distributed in different ranges.
For any rule updates, they are written directly to the cache and underlying database, so any rule change will be immediately visible in the next read.
For our servers, we also need to determine the right algorithm to use. Here are a few and with tradeoffs:
Token bucket: For each API/user, we create a virtual bucket. The bucket refills tokens at a constant rate. If the tokens are depleted, we no longer allow any more requests. For this approach, the pro is that we can allow burst traffic up to capacity, and we implement accurate rate limiting that is memory efficient.
Sliding window log: Sliding window logs looks at the API events for each user for a given API, for the past period (like 1 minute), remove old/stale logs, and calculates the number of logs in this period, and whether it exceed the capacity. This approach is highly accurate, allows burst traffic. However, it is very memory intensive.
Sliding window counter: Sliding window counter breaks down time to different intervals. Then it looks at request count in current interval + a weighted percentage of previous window's total count. This is an estimated count, but it also allows burst without boundary problems, and it has low memory foot print.
In our use case, we will use token bucket. For this approach, we only need to store the tokens for each user/API, and still have accurate rate limiting.
We also need to address race conditions in our design. If 2 requests both try to read and update the tokens at the same time, we would have inconsistencies. In this case, we use atomic operations on the redis cluster, where read-calculation-write is considered as a single transaction. This will increase write latency, but gives us consistency.
If the whole RL system is down, we will use a fail-open policy, still allowing requests to flow through until it recovers. This is a tradeoff between availability and reliability.
To address the scenario where the cache is slow or unavailable, a robust fallback mechanism is essential. In such cases, the system can implement a local rate limiting strategy using a default policy, such as allowing a conservative number of requests per user or API endpoint. This local strategy can utilize an in-memory data structure that tracks request counts and timestamps, ensuring that the rate limiting logic remains functional even when the external cache is not accessible. Once the cache is back online, the system can reconcile the local state with the cache, updating it with any missed requests or adjustments needed to maintain consistency.
For handling clock skew and ensuring that window semantics remain correct, it is important to establish a time synchronization mechanism. The system can utilize a centralized time server or a consensus algorithm to ensure that all nodes in the distributed system have a consistent view of time. This approach helps mitigate discrepancies between client and server clocks. Additionally, implementing a sliding window algorithm that accounts for potential clock drift can help maintain accurate rate limiting behavior, ensuring that requests are counted correctly within the defined time windows, regardless of any minor clock differences.
Regarding the implementation of batching for hot keys, it is crucial to ensure that batching does not violate the guarantees of the chosen rate limiting algorithm. One approach is to implement a controlled batching mechanism where requests are aggregated over a short time interval, such as one second, before being processed. This allows the system to maintain accurate counts while reducing the load on the underlying data store. Additionally, the batching process should ensure that the total count of requests does not exceed the defined limits, and any excess requests can be handled gracefully by either queuing them or applying a temporary throttle. By carefully managing the batching process, the system can effectively handle hot keys while adhering to the rate limiting constraints.