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...
For a large-scale global service, num requests per seconds can be 1M per second.
Number of cache updates will also be the same.
A load-balancer in front of the service is required.
Define what APIs are expected from the system...
The rate limiter will get application's APIs
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...
Rate Limiters are mostly stateless except storing the number of requests per unit of time in a cache and storing requests for history and analytics.
Store number of requests per unit of time in cache (Redis or similar)
Store historical data in a persistent NoSQL database like Cassandra (write-heavy). NoSQL DB is suitable because of the amount of data and heavy write load.
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 can be implemented in the API Gateway or inside the application/service directly.
Most modern cloud service providers like AWS, Google Cloud, Microsoft Azure etc. provide an API Gateway. Applications hosted on such cloud platforms can leverage the inbuilt rate limiter. This also simplifies the service architecture, implementation and complexity.
However, using an in-build rate-limiter takes away the flexibility and control provided by developing an in-house rate-limiter.
The choice must be made based on requirements, resources and engineering expertise.
At a high level, the rate limiter maintains a counter/track of requests received per unit of time and/or per user and allows it if it is within the threshold or rejects it if beyond the threshold.
When the request is rejected, it responds with HTTP status code 429 which denotes too many requests. The header or body can contain more information such as 'Retry After' or something similar.
Several algorithms can be used to implement rate limiting. Some of them are as below:
Token Bucket
===========
A fixed number of tokens are kept per unit of time and number of requests equal to this number are allowed. If more requests arrive, they are rejected until the time unit has passed and the token bucket is replenished.
The number of buckets and tokens will be based on application requirement and criteria.
Pros:
Cons:
Leaky Bucket
============
Same as token bucket with the additional feature of flow control to the services. It uses a queue where requests are added if tokens available. Requests are sent to the application at a fixed rate and hence processed at an interval.
Pros:
Cons:
Fixed Window Counter
===================
Same as Token Bucket
Sliding Window Log
=================
Addresses the request exceeded limitation of the previous approach by maintaining a timestamp of each request in a log. When a request arrives, it timestamp is added to the log. It then calculates the number of requests received in the unit of time based on the request's timestamp. If the number is within the threshold, the request is allowed otherwise rejected.
Pros:
Cons:
Sliding Window Counter
===================
Improvement over the previous approach by keeping a counter of num requests received in each pre-determined time window.
When a new request arrives at x% time inside the current window, it decides whether to allow or not based on following criteria:
num requests in current window + (100-x)% * num requests in previous window.
If above number is within the threshold, the request is allowed.
Pros:
Cons:
Out of all above algorithms, the one suited to application needs must be selected.
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...
Rate Config is information about rate limiting rules. They are stored in config files(yml, json etc) in the persistent store.
This information is pulled by workers in the cache.
Rate Limiter reads the info from cache and performs rate limiting accordingly.
If a request is allowed, it is passed to the services otherwise rejected with a 429 response.
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...
Algorithms For Rate Limiting
======================
Several algorithms can be used to implement rate limiting. Some of them are as below:
Token Bucket
===========
A fixed number of tokens are kept per unit of time and number of requests equal to this number are allowed. If more requests arrive, they are rejected until the time unit has passed and the token bucket is replenished.
The number of buckets and tokens will be based on application requirement and criteria.
Pros:
Cons:
Leaky Bucket
============
Same as token bucket with the additional feature of flow control to the services. It uses a queue where requests are added if tokens available. Requests are sent to the application at a fixed rate and hence processed at an interval.
Pros:
Cons:
Fixed Window Counter
===================
Same as Token Bucket
Sliding Window Log
=================
Addresses the request exceeded limitation of the previous approach by maintaining a timestamp of each request in a log. When a request arrives, it timestamp is added to the log. It then calculates the number of requests received in the unit of time based on the request's timestamp. If the number is within the threshold, the request is allowed otherwise rejected.
Pros:
Cons:
Sliding Window Counter
===================
Improvement over the previous approach by keeping a counter of num requests received in each pre-determined time window.
When a new request arrives at x% time inside the current window, it decides whether to allow or not based on following criteria:
num requests in current window + (100-x)% * num requests in previous window.
If above number is within the threshold, the request is allowed.
Pros:
Cons:
Out of all above algorithms, the one suited to application needs must be selected.
Maintaining Shared Num Requests Counter
===============================
A distributed/centralized cache must be used to ensure that the requests tracker is shared between different instances of Rate Limiter. A user's request can arrive on any rate limiter.
Concurrent Update of Shared Counter
==============================
Use Lua scripts or Redis Sets.
Explain any trade offs you have made and why you made certain tech choices...
Try to discuss as many failure scenarios/bottlenecks as possible.
Maintaining Shared Num Requests Counter
===============================
A distributed/centralized cache must be used to ensure that the requests tracker is shared between different instances of Rate Limiter. A user's request can arrive on any rate limiter.
Concurrent Update of Shared Counter
==============================
Use Lua scripts or Redis Sets.
Overwhelming the Rate Limiter
=========================
A rate limiter instance should be deployed in multiple geographies to be close to the user's location.
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?