System requirements

Functional:

Limit maximum number of requests from a user in certain time frame

Non-Functional:

Latency: Rate limiter should provide low latency, to avoid blocking of the actual request

Available : Rate limiter should be available always

Reliable: it should not restrict users accurately according to maximum limits

Scalability - Rate limiter should be able to support growing number of users without issues

Capacity estimation

I am assuming 1million users for the underlying application,

and 10% as DAU - 100,000 users per day

10% of DAU as concurrent users - 10000

Storage:

We need to store number of requests per user

Assuming count is an integer type and some metadata like userId

1million * 8Bytes - 8MB storage

Throughput

10,000 concurrent users making 10 requests per minute

1lakh requests per minute - 1666 TPS

API design

Check rate limit

GET rate/userId - returns a response with boolean field processRequest - true/false

Database design

Since the Latency should be low we can consider a key-value store like redis or memcached to retrieve the counts faster.

Since redis or memcached is in-memory, we can store the data in a SQL server for maintaining and reloading whenever the application is restarted.

High-level design

1. Load balancer - load balancer to balance requests between multiple rate limiter services
2. Rate limiter - to limit rate based on userId
3. Cache - maintaining cache for easy access of counts for minimum latency, whenever there is a change in the request count by user the cache is synched asynchronously

Request flows

whenever there is a request to check rate limit, the rate limiter service queries cache to get the data and if exceeds maximum limit the request is rejected. if the data is not present in cache , the count is checked from the DB and loaded to cache.

Detailed component design

The rate limiter is a distributed system which runs on a distributed application.

1. count is increased and pushed to DB with each request on the application
2. Cache is synched asynchronously whenever the count changes in DB.
3. Count is reset after a certain time and synched to cache

Trade offs/Tech choices

Cache is maintained asynchronously , and availability and high latency is picked over consistency. so the count may not be upto date sometimes

Failure scenarios/bottlenecks

Cache is maintained asynchronously , and availability and high latency is picked over consistency. so the count may not be upto date sometimes.

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?