Functionality:

• Rate limit for a user on a single HTTP method. The rate limiter has to understand if the user exceeded the limit and if it happens rejects the request

Rate limiter must be as fast as possible. Because we don't want the rate limiter the add a bit amount of latency to our server responses.

And it must utilize the resource very efficiently. Because we want the rate limiter to handle a huge request load.

The system will consist of these components:

1. The client, that sends HTTP request to a web-service
2. The rate limiter, that checks if the user has exceeded the limit of requests. If it happens, the rate limiter responses with 429 error
3. The database, that stores data about a requests. I consider we will need an in-memory database here, because of the latency requirements. It may be Redis, becuse it supports time series natively, it is popular in community for the in-memory storage, it works well with the concurrent requests (single-thread)

How can we identify the user that makes a request. I consider we may use this data:

• IP address of the request. The user usually makes requests from one network
• User-Agent header. The header tell about user device
• Authentication token (if we have it)
• Cookie (if we have it)

We will use these points to identify the user. We can join these strings and make a md5 hash function of it. The resulting string will define the specific user. It will be the key in the Redis storage. And the value will be the time series of the user's requests (native time series in Redis). Not updated time series in Redis will be deleted from Redis

So database schema in the Redis key-value:

• key – HTTP method + hash of users data from the request
• value – time series of requests for the user. It is a list of timestamps of passed requests for this user. The list is ordered in historical order

Rate limiting rules

The rules may be configured using configuration file for the rate limiter service. It may be yaml file. The rate limiter will load the file on the start-up and use it's data as rules. In this scenario the file will contain the amount of requests allowed by the single user (10, 50k, etc.) in a defined period of time (1s, 10s, 5 minutes, etc.). So there are only two parameters in the configuration

Rate limiting algorithm

For example, the rules are 10 requests in 1 second and 50 requests in 1 minute.

1. When a new request comes to the rate limiter it goes to the in-memory key-value storage and retrieve data using key – HTTP method + hash of users data from the request.
2. The rate limiter takes the time series for the user. The rate limiter gets data of the longest period in rules (1 minute in the example) from Redis and counts the number of requests made by the user.
3. If the number is smaller then the number from the rule, the rate limiter passes the request through to the web-service
4. If the number exceeds the number from any rules, the rate limiter responds with 429 error
5. In the background all the timestamps older then "Current time minus longest time period" are deleted from the time series list

Edge cases (failures and scaling)

What happens if the rate limiter restarts?

Here are no any problems with it, because it is stateless and must handle all the requests correctly after restart. The load between rate limiters will be balanced using round-robing algorithm

What happens if there is a failure in the Redis database?

We have to use Redis asynchronous replication that will increase our availability. In case of failure one replica will take place of the master and the rate limiter will start to work again

How can we handle a huge amount of requests?

The rate limiter itself may be easily scaled horizontally, because it is stateless. So the best way of scaling the Redis is sharding using Redis Cluster. The sharding key is the hash again and the algorithm of sharding is consistent hashing. If the load grows, more shards may be added to handle the requests.

Concurrent requests

The concurrent requests in this system will be handled by the Redis. Redis works in a single-threaded mode on a key. So all the concurrent requests will be processed in a row, because the rate limiter will wait for Redis to process the previous request

Multiple users

Our system works well for different users, because we have different keys in the database for different users. So the rate limiting rules will work separately for different users

Concurrent requests from different users is not a problem at all, because they will have different keys in the database. So they will not be concurrent.