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

}

configsvc

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. configsvc: service to add/update/delete/view rate-limit rules via an API
6. 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.

• 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. Ex: assume a user can make 3 requests per minute for endpoint X (stored in 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). limitersvc have multiple instances to scale horizontally
  1. Example: For each api key and endpoint pair, the limitersvc will query the configuration database to know max limit api key can query for that endpoint only in the FIRST request
     1. User has 3 tokens left and makes request at 10:25:35. 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.

• 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.
• configsvc: 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, configsvc should call limitersvc or send a notification to it, to update the cache for a particular api key + endpoint cache key (if it exists) So cache will now say 1000 requests/hour for that api key + endpoint. configsvc should continue working as is.

Tradeoffs

Cons: what if we receive two requests from the same API key+ endpoint as cache key at same millisecond, different machines? Use a locking mechanism, where one acquires a lock to write, but this is very slow. Redis has support for atomic operations. We move all logic into one atomic step inside Redis and it guarantees no race conditions and that no other request can interrupt this logic.

what if machines have different clocks? Servers can differ in time. Let's use Redis time as the single source of truth of time.

Let's say we have a billion of DAU, how do we handle high QPS? We can have a local cache in the load balancer to know overload Redis. We can periodically sync Redis and local cache in load balancer. If tokens run low for a cache key api key + endpoint, fetch/refresh from redis. Another approach is to partition redis by api key and endpoint to spread load evenly (use consistent hashing)