Loading...
List functional requirements for the system (Ask the chat bot for hints if stuck.)...
List non-functional requirements for the system...
Estimate the scale of the system you are going to design...
Define what APIs are expected from the system...
if a request is throttled, return 429 too many requests.
rate limiting information in the response header
X-Ratelimit-Remaining: The remaining number of allowed requests within the window.
X-Ratelimit-Limit: It indicates how many calls the client can make per time window.
X-Ratelimit-Retry-After: The number of seconds to wait until you can make a request again without being throttled.
Defining the system data model early on will clarify how data will flow among different components of the system. Also you could draw an ER diagram using the diagramming tool to enhance your design...
Why choose Redis?
Redis operates primarily in-memory, which leads to extremely fast read and write operations (sub-millisecond latency). This is crucial for applications that require high performance, such as real-time data processing like rate limiting.
With in-memory data access, Redis dramatically reduces the latency compared to disk-bound databases, making it suitable for high-frequency operations.
Redis supports various data types, which can be useful in our rate limiting, where you can implement counters using sorted sets efficiently.
To implement the specified rules for rate control over users using Redis, we can design a data model that supports different user pools, protects various API endpoints at different rates, and accommodates both user classes and API classes. Below is a proposed Redis data model structured to fulfill those requirements.
Simple Redis just for controlling rate limit over a user:
Implementing rate control over users using Redis can be an efficient way to manage your rate limiter due to its fast in-memory data storage capabilities. Here’s a structured approach to do this effectively.
Data Structure:
Use a Redis key for each user to track API requests, with the key format being something like rate_limit:{user_id}.
Request Handling Logic:
Each time a user makes a request, check how many requests they have made in the given time window.
Use Redis commands to increment the count and set an expiration time for the key.
Example Logic
Increment Request Count: Use INCR to increment the request count for a user.
Set Expiration Time: Use EXPIRE to set a TTL (Time to Live) on that key for the time window.
Rate Limit Rules:
Store rate limiting rules for different user classes and API endpoints.
Key Pattern: ratelimit:
Value: Hash (storing the limit and time window).
Example:
HSET ratelimit:pinner:search_api_endpoint limit 10 window 60
HSET ratelimit:partner:search_api_endpoint
Request Counters:
Store request counters for each user per API endpoint, using a sorted set to keep track of timestamps.
Key Pattern: requests:
Value: Sorted Set (to track the count of requests and their timestamps).
Example:
ZADD requests:user123:endpoint_api
ZADD requests:user123:endpoint_api
User Class and Pool Mapping:
Map users to their respective pools (e.g., 'pinner' or 'partner') for quick access to their rate limits.
Key Pattern: user_class:
Value: String (storing the user pool).
Example:
SET user_class:user123 pinner
SET user_class:user456 partner
Blacklist (Optional):
Maintain a temporary block for users who exceed rate limits.
Key Pattern: blacklist:
Value: String (to store the reason for blacklisting).
Example:
SET blacklist:user123 "Exceeded rate limits"
You should identify enough components that are needed to solve the actual problem from end to end. Also remember to draw a block diagram using the diagramming tool to augment your design. If you are unfamiliar with the tool, you can simply describe your design to the chat bot and ask it to generate a starter diagram for you to modify...
Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...
Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...
If you prefer to minimize storage requirements in Redis and only maintain counts instead of timestamps for rate limiting, you can adopt a fixed window counter strategy. This method simplifies the implementation and reduces the overhead on data storage.
In a fixed window rate limiter, you count the number of requests a user makes within a defined time period (the "window"). Each window is fixed, meaning it starts at a specific time and lasts for a predefined duration (e.g., one minute). Here’s a general outline of how it operates:
Define Limits and Windows:
Specify a maximum number of requests allowed (e.g., 100 requests per minute).
Set the duration of the time window (e.g., 1 minute).
Counting Requests:
Each time a request is made, check the current count for that user in the current time window.
If the count is less than the limit, increment the count and allow the request.
If the count exceeds the limit, the request is denied.
Resetting Counts:
At the end of each fixed window (e.g., every minute), reset the count back to zero.
Key: rate_limit:
Value: count (integer that tracks the number of requests)
Expiration: Set a time-to-live (TTL) on the key to match the duration of your window (e.g., 60 seconds).
The fixed window can lead to the "bursting" problem, where a user can hit the limit at the end of one window and then immediately start again at the beginning of the next, leading to potential abuse.
In the Sliding Window algorithm, instead of having a fixed time frame at the start of which you count requests, you maintain a list or a queue of timestamps of each request made by the user.
How It Works:
Each time a request is made, you check the current time and discard any timestamps that are outside your defined time window (e.g., older than one minute).
The current count of timestamps left in that time window determines whether to allow or deny the request.
You then add the new timestamp to the list.
This allows for a more granular and fair way of counting requests throughout the allowed time period, as it makes use of continuous rolling windows for rate limiting and accommodates bursts more effectively than fixed windows.
Race condition
Request A checks the token count in Redis.
Request B checks the same token count before Request A decrements the count.
If there are tokens available, both might proceed to decrease the token count, allowing more requests than intended.
Redis sorted set helps us manage race condition efficiently given its atomic nature. Another approach is to use Lua scripts in Redis, which allow you to perform multiple operations atomically as a single transaction.
With Lua scripts, you can check the current tokens and decrement them in one atomic operation.
Explain any trade offs you have made and why you made certain tech choices...
where do we want to implement the API rate limiter?
Pros:
Centralized Control: Rate limiting rules are applied uniformly before any request reaches the backend services, providing consistent policies across all APIs.
Reduced Load on Backends: By filtering out excessive requests at the gateway, it reduces the load on backend servers, allowing them to focus on processing legitimate requests.
Easier Configuration: Many API gateways offer built-in rate limiting features that are easier to manage, often with a degree of customization for different users and endpoints.
Scalability: As the application scales, traffic management is handled at the gateway, improving ease of scaling backend components without changing rate limiting logic.
Cons:
Single Point of Failure: If the gateway goes down or encounters issues, it can block all traffic until it's resolved.
Limited Granularity: Some gateway implementations may have limited capabilities for complex rate limiting rules (like distinguishing between user classes or tiered limits).
Increased Latency: Adding an extra layer can introduce some latency, especially if the rate limiting logic is complex.
Pros:
Granularity and Control: More granular control over rate limiting policies can be implemented. This makes it easier to tailor rules specific to certain user classes or API endpoints.
Custom Logic: Specific business rules can easily be integrated into rate limiting logic, enabling more complex scenarios.
More Proximity to Data: Since the limit is applied at the server level, it can leverage in-memory stores or databases that are already in place, potentially providing faster access to rate info.
Cons:
Increased Load on Servers: Excess request traffic will reach your backend servers before being limited, which can affect server performance.
Complexity in Management: Maintaining consistent rate limiting logic across multiple backend services can become cumbersome and error-prone.
More Overhead on Server Resources: Processing requests that are ultimately rejected adds unnecessary resource consumption on the servers.
Try to discuss as many failure scenarios/bottlenecks as possible.
If the master node goes down, we promote a follower to be the new master.
how to handle malicious users?
Error handling if Redis is down:
If Redis is unavailable, you can decide to operate the rate limiter in a "fallback" mode. This means you will still allow requests without enforcing strict limits, possibly logging the incidents for future audit or review.
implement a local cache to record counts after Redis is down, and follow the predefined limits based on these locally cache data, while this will not replace the distributed nature of Redis, it can help mitigate the impact temporarily.
Implement a circuit breaker pattern when communicating with Redis, if the service experiences frequent failures, circuit breaker can open for a certain time to avoid overwhelming the Redis server and allow it time to recover.
implement retry logic, if we encounter a connection failure, retry the request after a short delay while also managing a maximum number of retries to avoid indefinite blocking
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?
We need to set up multi data centres across the world because our service have users from different places in the world. We will go to the server closest to the users.