Loading...
Token Bucket algorithm - allows clients to access API only when they have enough "tokens" in their bucket. Each request will consume a token, and the bucket is refilled at a constant rate
Rate limiting rules can be extendable to include IP address, user ID and other properties.
Inform users that they are being throttled.
Highly fault tolerance
Accommodates both large companies and startups.
Scales based on expected traffic and usage requirements of application.
Server side
Estimate the scale of the system you are going to design...
Define what APIs are expected from the system...
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...
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...
Rate Limiter middleware will sit between client and web servers.
We will use Redis to store the counters which has two commands: INCR and EXPIRE.
INCR increments the counter by 1
EXPIRE resets the counter to 0
flowchart TD
B[Client] --> C(Rate Limiter)
C --> D[Web Servers]
C --> Cache[Cache]
C --> Rules[Cached Rules]
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...
Client forwards request to rate limiter. If token bucket has enough tokens, it will forward the request to the web servers. Otherwise, request will be dropped
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...
flowchart TD
B[Refiller] --Refills bucket with n tokens every second--> Bucket[Bucket]
Bucket[Bucket with c capacity] --> decision{Is there enough
tokens?}
decision -- No --> Request(Request is dropped)
decision -- Yes --> Server(Request is forwarded to the server)
Client[Client] -- Sends requests
to rate limiter--> Bucket
Rate limiter will throttle requests based on the Token Bucket algorithm. A bucket is instantiated for each user with a a refill rate of n tokens and capacity c. If there are more than 0 tokens in the bucket, a request can be forwarded and that token is then removed. Otherwise, the token will be dropped.
To scale and add rate limiters to ensure fault tolerance, we need synchronisation between them to determine how many tokens are available to a client. To do this, we centralise our buckets in a cache like Redis, which is also already scalable out of the box. When a user sends a request to the rate limiter, the rate limiter will check Redis to see if they have gone over their capacity. If they haven't, the we INCR their value and forward the request, otherwise it gets dropped. Their counter gets reset with EXPIRE.
To make transparent how many requests are available to the users, we send them back with the request headers:
If the rate request is limited, they will be send back with a 429 response, which is TOO MANY REQUESTS.
Explain any trade offs you have made and why you made certain tech choices...
Try to discuss as many failure scenarios/bottlenecks as possible.
We centralise our
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?