System requirements

A Rate limiter restricts the number of data that is being sent by a particular user within a given time frame

Functional:

• Limits the user to 15 requests per second
• The user should be able to receive an error message if they cross the given threshold

Non-Functional:

• System should be highly available as it protects our servers from external attacks
• System should not have high latencies

Capacity estimation

Traffic Estimation

• 10 milion total users
• 5 million daily users
• 15 requests per second from each user

Data entities

• User
• userID (4 bytes)
• Requests
• userID (4 bytes)
• Time (4 bytes)

Storage estimation

• We will only store user information, request information will be temporary.
• 10 million * 4 bytes = 30 MB

Cache estimation

• We want to cache the top 50% of users in memory, for faster data retrieval. Hence our cache size will be 30MB * 50% = 15MB

API design

send_request(userID) - sends a request to the server, the server will check whether the request is valid and is within the threshold. If it is within the threshold then return status code 200, else return status code 429

Database design

To be honest, we only need to store userID in the database, we need data retrieval to be fast. We can store the userID in a SQL database like MySQL and Postgres, however, to truly have fast data retrieval, we will also use a cache, which can either be a Memcache or a Redis instance on each server

High-level design

The Rate Limiter is responsible for determining which requests are allowed, hence when a web server recieves a request, the webserver will send the userID to the Rate Limiter server, which will then determine whether to serve the request or deny it. The Rate Limiter server will be connected to a backend storage and a cache server

Request flows

The Rate Limiter is responsible for determining which requests are allowed, hence when a web server recieves a request, the webserver will send the userID to the Rate Limiter server, which will then determine whether to serve the request or deny it. The algorithm to determine this will be discussed in the next section. The Rate Limiter server will be connected to a backend storage and a cache server

Detailed component design

The most important question here would be how can we design a reliable and low latency algorithm to determine whether to serve or deny a request

Basic Fixed-window algorithm

We could keep a hash map of userID and the value would be the number of request sent per fixed window of time, this means that every second (our fixed window), all hash map values will be turned to 0

Steps

1. If userID not in hashmap, go to cache or DB to check whether the userID is valid. insert userID into the hash map and set the startTime to the current time (by second), set the count to 1
2. If a request is sent outside the current time, set the count to 1
3. if count < 15, serve request, else dont serve

The problem with this algorithm is that a user can send, for instance 15 requests in quick succession at the end of a fixed-window, then when the counter is reset in the next fixed window, the user then sends 15 requests in quick succession at the start of the current fixed-window. What this could do is that our service might have served 30 requests within a second for a particular user. Not good

Sliding window algorithm

We could keep a hashmap of linked lists for a userID. Each node in a linked list contains the time a request was sent

1. If userID not in hashmap go to cache or DB to check whether the userID is valid. insert userID into the hash map, create a new node of the current time
2. For each request sent by the user, we will start at the beginning of the linked list and traverse from there, if the time +1 < currentTime, delete it
3. If the size of linked list is < 15 serve request, if >= 15 deny request. We create a node if < 15, then insert it at the end of the linked list

This algorithm works, but it takes up memory

Sliding window with counters

What if we keep track of request counts for each user using multiple fixed time windows, e.g., 1/60th the size of our rate limit’s time window. For example, if we have an hourly rate limit we can keep a count for each minute and calculate the sum of all counters in the past hour when we receive a new request to calculate the throttling limit. This would reduce our memory footprint. Let’s take an example where we rate-limit at 500 requests per hour with an additional limit of 10 requests per minute. This means that when the sum of the counters with timestamps in the past hour exceeds the request threshold (500), Kristie has exceeded the rate limit. In addition to that, she can’t send more than ten requests per minute. This would be a reasonable and practical consideration, as none of the real users would send frequent requests. Even if they do, they will see success with retries since their limits get reset every minute.

Now the thing here is that in order to distribute load and not overwork a single server, we might have a few servers. We need the userID to reach the same server every time a user sends a request. Hence between the webserver and the rate limiter server, we will have a reverse proxy, which analyses the userID that is sent from the webserver and redirects it to the correct server.

Trade offs/Tech choices

Explain any trade offs you have made and why you made certain tech choices...

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

Future improvements

At the moment, our system only keeps track of the requests sent per user, however what we could do is that we can track the request sent per user per API! meaning that we will keep track of the rate limit of API specific requests sent by the user