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)

Endpoint for limitersvc:

checkRateLimit(apiKey, endpoint) --> Response(status - success/failure, waitTime[optional] - time it needs to wait if user is throttled)

configsvc - invoked by a client to view/add/update/remove configurations such as: selecting the plan a user wants for a particular api key and endpoint. Ex: as a user I want tier 1 for api key and access to endpoint XYZ. Tier 1 includes 100 requests per minute. The user can upgrade its plan, view its plan or remove it.

Endpoints of configsvc:

getLimit(apiKey, endpoint) --> Response(maxRequests, minutes)

upgradePlan(apiKey, endpoint, payment, tier[maxRequests, minutes]) -> Response(status=success/fail)

cancelPlan(apiKey, endpoint) -> Response(status=success/fail)

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 and a have local cache of api key.
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 + having high availability. If limitersvc is down (0 instances are working), we can fallback to the load balancer in the cache. The expectation is that limitersvc will get a bit of less request because of the local cache in load balancer.
  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 per limitersvc instance. 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. If cache is down (0 instances are working), we can fallback to the load balancer's local cache to provide high availability. But since we have leader replication (high availability), low probability of cache being unavailable. When master gets down, we can rely on one of our followers.
• 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 remove overload Redis. Let's say that user has 100 requests/min. We let the load balancer handle 50 requests instead. As soon as the load balancer handle the 50 requests, we let know the redis cache (we're leasing a portion of the max tokens in a local cache). That way we make sure that max tokens never gets in overflow state. In conclusion, small local buckets absorbs bursts, backed by Redis for global enforcement.

Another way to handle high QPS is to partition distributed cache by pair (apikey and endpoint) to distribute load. We can use consistent hashing for whenever a machine gets added/removed. Even if we partition the cache, we may get huge number of requests for a particular pair (apikey and endpoint). We can make an exception for those type of keys and partition even further.