Loading...
List functional requirements for the system (Ask the chat bot for hints if stuck.)...
I'm assuming we are not throttling by an API key, rather by user.
Authenticated vs unauthenticated requests:
Rate limiting will be segmented by service. The other option is rate limiting for any request, regardless of service. To do this, we would likely need a high threshold which could lead to one service being overloaded, like login. Additionally, service teams would not be able to customize their thresholds.
co-located vs distributed system:
We will choose the distributed option and explore options to reduce the latency.
List non-functional requirements for the system...
We want to avoid disk access because it is slow and this would add additional latency to our solution. Therefore, we are likely looking at an in-memory solution.
Estimate the scale of the system you are going to design...
1B (10 ^ 9) users
Our rate limiter needs to store userId, timestamp, ip address, and the service being accessed. Assuming 8 bytes for each and additional metadata, 50 bytes.
Therefore, roughly 50GB of ram
Define what APIs are expected from the system...
boolean allowAccess(userID: String?, ipAddress: String, timestamp: DateTime, serviceName: String, thresholdLimit: Int, thresholdWindowInSeconds: Int)
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...
Our data model will look follow the API parameters:
userId: String? - nullable in case user is not authenticated
ipAddress: String
timeStamp: DateTime
serviceName: String
Only requests that have been allowed through would be persisted.
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...
The rate limiter will exist as a separate service. This allows us to call it from the load balancer, which will reduce the load on our network infrastructure as well as our services.
Our load balancer will contain a cache to reduce the number of repeated network requests.
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...
When a request arrives to the load balancer, the load balancer will check its local cache. For a cache miss, it will send the request to the rate limiter. If the request should be allowed, the load balancer sends the request to the service. Otherwise, the load balancer blocks the request.
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...
Rate limiting logic
The rate limiter can be implemented using fixed window or sliding window. A fixed window resets counts every specified time period. A sliding window will count the number of requests from the current time period to the specified window size. The fixed window solution is simpler to implement but allows for more instances of bad actors, as they can flood a service after the reset point. The sliding window has a more complex implementation but more secure. we will choose this approach.
Concurrency
To implement a sliding window, we will likely a queue backed by a linked list. Requests which are outside of the window will be removed from the head of the list, and new requests will be added to the end. If our solution runs in a multi threaded environment, then we may run into concurrent modification exceptions. Solutions to this are using the blocking versions of linkedList in popular languages or running single threaded.
Cache
The load balancer cache will be used to reduce the number of requests to our rate limiter service. The types of cache are write around, write back, and write through. Write through is not ideal here because the cost is too great to synchronously write to our service.
What is stored in the cache?
We'd need to run our solution in our load balancer.
We could explore a fixed window solution in the load balancer with a TTL. In this case, we would want a write around cache.
Explain any trade offs you have made and why you made certain tech choices...
Try to discuss as many failure scenarios/bottlenecks as possible.
Our rate limiter becomes a single point of failure. The business should decide whether to allow requests through or deny all requests if the rate limiter is down. A DDOS could potentially bring down additional services if requests are allowed through.
Our load balancer cache may be filled during a DDOS attack. Our rate limiting service could experience high load.
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?
We will likely need a better heuristic than IP address to determine a DDOS attack. Our rate limiter could have stronger rules for unauthenticated requests than authenticated ones.