Requirements

Functional Requirements:

• per-user / per-API rate limits (meaning that an endpoint within an API can have stricter rate limits).
• Admins can add/update/delete/view rate-limit rules via an API or console.

Non-Functional Requirements:

• Calling our API rate limiter should not affect external APIs. We expect low latency.
• System should be scalable (add more machines to handle more traffic)
• System should be reliable and fault tolerant

API Design

Define the APIs expected from the system. This is your chance to analyze and define the read and write paths so that you can come up with the high-level design...

limitersvc - invoked by a client (potentially another API - API is checking with limitersvc that client can make requests)

{

"apiKey": myAPIKey,

"request": requestType // different endpoints can have different max rate limits

}

{

"apiKey": myAPIKey,

"status": success/failure

}

High-Level Design

Describe the overall system architecture. Identify the main components needed to solve the problem end-to-end. Use the diagramming tool to create a block diagram.

1. Load balancer: redistribute traffic
2. API gateway: abstract microservices that we have for the client. The gateway should know to where route traffic. We can have multiple instances to provide horizontal scaling
3. limitersvc: service that will keep track of number of requests of each api key. It will tell whether maximum limit has been reached or good to make requests
4. cache: redis distributed cache to keep track of how many requests an api key has done within a time range (sliding windo)
5. adminsvc: service to add/update/delete/view rate-limit rules via an API
6. admin database: keep state of api key rules (which plans api key or user has...). Ex: api key has this many number of requests for endpoint X in api X, api key has this many number of requests for endpoint Y in api X. Different endpoints can different rate limits

Detailed Component Design

Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.

1. limitersvc: we can leverage sliding window technique to keep track of how many requests an api key has made within a time range. Ex: assume a user can make 3 requests per minute for endpoint X (stored in admin database)
   1. Example:
      1. 1st request at 10:05:17. Since this api key is not in our cache, we will store it in our cache and the record will be something like: {'apiKey': {'count': 1, 'exp': 10:06:17}
      2. 2nd request at 10:05:42. and now record in cache will look like {'apiKey': {'count': 2, 'exp': 10:06:17}. So user is allowed to make a request.
      3. 3rd request at 10:06:11 and now record in cache will look like {'apiKey': {'count': 3, 'exp': 10:06:17}.
      4. 4th request at 10:06:13 and since in our cache we had already made 3 requests under a minute, the request won't proceed.
      5. if our 4th request is at 10:06:24, we would see that exp already expired. Hence, we would need to update cache to look like {'apiKey': {'count': 1, 'exp': 10:07:24}.
2. cache: it's a redis distributed cache, that way all instances of limitersvc uses the same cache and its not tied to a local cache. We can also have read replicas in case our cache fails. Why use a cache, we're storing simple key value pairs. And reason of using cache is because it is a faster retrieval and our service should be low latent.
   1. cons of having a cache: limited memory. What happens if cache is completely full? We can either scale vertically or partition the data by apikey (consistent hashing).
3. adminsvc: for simplicity, let's assume that a user has only one api key. User onboards and signs in, selects their plan and pays for it. Here users can upgrade their plans to increase rate limiting. Let's say a user was rate limited because he was paying for 100 requests every 1 hour. Let's say that in 30 min, user already made the 100 requests and wants to update his/her membership to make 1000 requests in 1 hour. Our limitersvc would check admin database to check the maximum the api key can query. so user would have 90 requests remaining.