System requirements

Functional:

1. The system is able to throttle an API request if it violates the rate limiting rule.

Non-Functional:

1. The system is able to support multiple APIs.
2. Low latency < 200ms.
3. High availability > 99.99%
4. Support 1M DAU and 10M QPS traffic for API requests

Capacity estimation

1. We would have user_id(8 bytes), limit count(4 bytes), consider we have 10 APIs to support.
2. 12 * 10 * 1M = 120Mb for storage

API design

GET /rateLimit/user_id?/api_name?/

return 200 if the request is able to go through.

return 429 if we need to throttle the request.

Database design

RequestCount Table:

{

user_id: string (ip_address for non-login user)

api_name: string

count: int

}

High-level design

Client -> LB -> RL Cache -> RL service -> API service -> Client

|

DB

When a request comes in, it hits the LoadBalancer first.

LB will check the RateLimit Cache first for the user/ip.

If it is already throttled, reject the request.

If not, go to the RateLimit service to increment the request counts (and write back to cache).

If it is not throttled, go to API server. If hit the limit, reject the request.

Request flows

When a request comes in, it hits the LoadBalancer first.

LB will check the RateLimit Cache first for the user/ip.

If it is already throttled, reject the request.

If not, go to the RateLimit service to increment the request counts (and write back to cache).

RL service will fetch the Rate limit rule from DB.

If it is not throttled, go to API server. If hit the limit, reject the request.

Detailed component design

For the LB, shard by user_id/ip help us to scale horizontally.

The RL cache and RL service also shard by user_id/ip.

In RL service, we can have two choices for the RL algorithm.

• Fixed window

Based on Map>

At a fixed time window, we will calculate the number reuqets received for one user and for one API. We will clear the count once the fixed time window passed.

• Sliding window

Based on Map>

When the request comes in, we will verify if the oldest request in the linkedlist has above the time window we have for rate limiting. If so, we need to evict these requests from the linkedlist. The size of the linkedlist is the number request we have.

Other algo: token bucket algorithm

Trade offs/Tech choices

We have two choices where we put the rate limit service.

• Put together with API service

pros: no api calls to RL service, faster

cons: couple with API service, no optimized for fault tolerance, not langugae agnostic (need to be same with API service)

• Make RL service a separate service

pros: better fault tolerance. Language agnostic

cons: network overhead

There are also tradeoffs for fixed window and sliding window RL algo.

• fixed window
• pros: easy to manage
• cons: not accurate for request close the the boundary

• Sliding window
• pros: calculation of # of request is precise
• cons: more storage since we store the requests as a linkedlist, more time complexity since we need to evict the requests

Failure scenarios/bottlenecks

when the cache failed, we can go to RL service to get the request count.

When RL service is down, we will have a distributed server pool which can be fault tolerant.

When DB is down, we will go the a backup DB.

Bottlenecks:

1. If we find an API is frequently accessed by a user, we can leverage cache to avoid frequent request to RL server.

Future improvements

since we store the counts in memory in RL service, if RL service is down, we will lost the count. One way is to reload the data from some persist storage and this requires us to persist the data to a data storage from time to time.