System requirements

Functional:

• Multiple API endpoints with different API rate limits (configurable)
• When rate limit is hit, return error with status code 429
• The API endpoint should be again accessible when retried after some time when rate limit is not met.
• Rate limit is for a user
• > 10,000 users
• 10,000 requests per minute for each API endpoint
• 20 API endpoints
• response time 500 ms
• Rate limit should be configured using requests per minute
• Way for the user to know how many requests are remaining

Non-Functional:

• Validation of the request for the API endpoint

Capacity estimation

Estimate the scale of the system you are going to design...

20 API endpoints * 10,000 requests per minute = 200,000 requests per minute

API design

No additional APIs, the API rate limiter which is being designed will sit in the API gateway

Database design

Defining the system data model early on will clarify how data will flow among different components of the system. Also you could draw an ER diagram using the diagramming tool to enhance your design...

Configuration for the API rate limiter can be stored in a relational database

schema name : APIRateLimits

Columns: APIPath (string), Requests per minute (Integer)

High-level design

You should identify enough components that are needed to solve the actual problem from end to end. Also remember to draw a block diagram using the diagramming tool to augment your design. If you are unfamiliar with the tool, you can simply describe your design to the chat bot and ask it to generate a starter diagram for you to modify...

The APIRateLimiterService sits behind the load balancer. The requests for the service are obtained from a message queue.

APIRateLimiterConfigService will make sure to return the latest API rate limit configurations. The rate limits for the service could be updated in place without restarting the rate limiter.

Request flows

Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...

Detailed component design

Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...

API Rate limiter service:

This service could be run on multiple instances or on a single instance depending upon the the requests being handled. It should be possible to auto scale the service horizontally.

Assume that each user is assigned a bucket of tokens for each endpoint which suggests the number of requests they are allowed to make.

1. At each interval (or minute), the Service fills up the bucket completely.
2. Whenever a request comes in for a particular user, a token from the bucket is used
3. If the bucket is empty, then return 429 to the load balancer
4. If the bucket is not empty, forward the request to the Web server. The forwarded request could also specify the number of tokens remaining in the bucket to specify how many more requests the user is allowed to make in the window (i.e minute)

A distributed cache service can be used to store the user information and their corresponding token buckets

APIRateLimitService calls the APIRateLimitterConfigService to fetch the size of the token bucket for each endpoint at each interval.

API Rate limiter config service returns the most updated rate limits from the data base for an endpoint.

Trade offs/Tech choices

Explain any trade offs you have made and why you made certain tech choices...

Message queue helps to establish a pull model for each machines in the API rate limiter service.

Alternative is to distribute the requests in a round robin fashion. But message queue can ensure that the requests are picked up even when one of the instances in API rate limiter service is faulty

Failure scenarios/bottlenecks

Distributed cache used by the instances of API rate limiter service can be come a bottle neck. This bottleneck can be reduced by using consistent hash to determine what server will address request from a user.

Future improvements

Assumption made: the requests are already authenticated when the requests land on the APIRatelimiterService.

Rate limiting the authentication APIs as they are embedded within the Load Balancer / API gateway