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)

input:

{

"apiKey": myAPIKey,

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

}

output:

{

"apiKey": myAPIKey,

"status": success/failure

}

adminsvc

getPlanForEndpoint/thisendpoint

{

"apiKey": myAPIKey,

}

output:

{

"apiKey": myAPIKey,

"maxRequests": 3,

"minutes": 1

}

upgradePlanForEndpoint/thisendpoint - upgrading tier

{

"apiKey": myAPIKey,

"payment": cardDetails

}

output:

{

"apiKey": myAPIKey,

"maxRequests": 10,

"minutes": 1

}

cancelPlanForEndpoint/thisendpoint - upgrading tier

{

"apiKey": myAPIKey,

}

output:

{

"apiKey": myAPIKey,

"success": true

}

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: distributed cache to keep track of how many requests an api key has done within a time range (token bucket)
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 token bucket algorithm to keep track of how many requests an api key has made within a time range. Token bucket algorithm allows a burst in traffic. Also, this algorithm allows high QPS based on our rate limiting rules. So, if we allow 6000 requests per second, our algorithm will allow around 100 requests per second. Ex: assume a user can make 3 requests per minute for endpoint X (stored in admin database). And the bucket refills itself. 1 request = 20 seconds. Meaning that bucket will add 1 token every 20 seconds (if bucket is less than 3).
   1. Example:
      1. User has 3 tokens left and makes request at 10:25:35. limitersvc queries the admin database if cache miss know the configurations of the api key (3 requests/minute). In cache: Tokens left 2, last refill at 10:25:35 with plan as 3 requests/minute)
      2. User has 2 tokens left and makes request at 10:25:52. Tokens left 1
      3. time arrives at 10:25:55, 20 seconds have passed. Add one token to the bucket. So now we have 2 tokens in bucket and last refill is 10:25:55.

b. Cache key is api key + endpoint. Values are number of tokens + last refill time.

Cons: what if we receive two requests from the same API key at same millisecond, different machines? Use a locking mechanism, where one acquires a lock to write. That way we guarantee one write per key.

1. cache: it's a 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).
2. 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. As soon as this change is made, adminsvc should call limitersvc to update the cache, specially the settings only. So cache will now say 1000 requests/hour. Service should continue working as is.