System requirements

Functional:

• Service receives requests to users
• Service rejects requests if above rate limits
• Service allows request if below the rate limits

Non-Functional:

• Highly available
• Low latency
• Scale up to large QPS

Capacity estimation

Estimate the scale of the system you are going to design...

• Total number of requests per day: 1,000,000
• Average number of requests per user per day: 100
• DAU: 10,000
• Requests per second: 1000000/24/3600 ~= 100
• Maximum number of requests per user per minute: 20
• burst requests per second: 0.3 * 1,000,000 = 300,000
• Number of servers needed: 300,000 / 200 = 1,500

API design

POST (put a request)

GET (read current count)

Database design

id: uint

count: uint

timestamps: LinkedList

High-level design

• Load Balancer: takes user requests
• Application Server: takes requests and allows or rejects requests
• Cache: stores and tracks the key-value map.
• Database: persist the cache asynchronously and failover if cache fails

Request flows

User sends a request -> load balancer routes it to an applicable server -> server checks cache to determine whether to reject -> deny if rejected -> pass to the backend service if allowed

Detailed component design

• Applicable Server: It queries the cache every time it receives a new request to get the info of the user. It will first expire the request's timestamps that has expired (i.e., earlier than current time minus the time window). It will then include the current timestamp to the end of the list. count will be updated accordingly. Based on the count, it will decide whether to reject the request. It will then update the cache with the new data.
• Cache: It will receive queries from Application Server and receive updates from the server. It meanwhile will sync with database asynchronously. If a failure occurs, it will fail over from the database.
• Load balancer: it will route requests based on users. Each user will be dedicated to one application server so cache on the server has the data.

Trade offs/Tech choices

• Cache over message queue: we want low latency so queue is not applicable. Using a cache to quickly query and fail fast would decrease latency.
• Memcache over Redis: we want to have low latency. Persists the data at the cache level is not a priority. Missing a few request data is OK and we have fail over from the persisted database.

Failure scenarios/bottlenecks

• Failure scenarios
• Application Server fails: certain users won't get access to the service
• Cache fails: Application server cannot access cache so hanging. Certain users won't get access to the service
• Bottlenecks
• There could be hot spots in application servers that certain application servers will be busier than the others.

Future improvements

• Failure handling
• Application Server fails: Load balancer will route to another Applicable Server. The server will get data from Database on the users handled by the failed Application Server
• Cache fails: Application server will have another failover cache to read data from Database and connect with the server.
• There could be hot spots in application servers that certain application servers will be busier than the others. Need to rebalance the load so hot users are distributed to different servers.
• Improvements
• Tell users to try after how much time after getting rejected
• Make rate limiting configurable for different users. Only be set by the system based on importance and frequency of requests.