System requirements

Functional:

1. The API rate limiter is time-based and restrict volume of requests over time.
2. The API rate limiter can limit per key (such as ip, customer id, etc)
3. In the MVP, the rate limiter does not support request-based / semaphore-based limiting.

Non-Functional:

1. The limiter must be able to handle large number of requests per second, including burst.
2. The rate limit are second level.
3. The rate limiter is server-side, not just at client-level.
4. Availability is critical because this sits on critical path of most service.

Capacity estimation

The API rate limiter should be able to handle 100K requests per second. It should also be horizontally scalable.

The API rate limit can support at most 2 billion keys.

API design

// Return None if the client can acquire the n requests now

// Else, return the time to wait

fn acquire(id: &[u8], n: i32) -> Option

Database design

RateLimiter

• Primary key = id: Vec<u8>
• request_per_sec: i64
• current_volume: i64
• last_update: i64

Assuming 64byte key, data per entry is 64+16 < 100 byte

High-level design

Because the system handle large volume and potentially in a burst. The data should be kept in memory rather than on disk.

A medium server (like c4.xl) can handle around 100K concurrent connections, using non-blocking event loops.

Given we have about 100 byte per entry, a server with 8GB ram can handle about 80 million keys. If we want to track 2 billion keys, we need about 30 servers.

In other words, we need to divide the 64-byte key space into ranges, each range owned by at least a single server. We can consider having a standby in future design.

The client would have a rate limiter library, which talks to the assignment service to understand which server owns the key. This assignment service is a cache view over the assignment database. Then, the client will connect to the server for the key. To reduce number of requests, this information can have a time-to-live.

The rate limiter server is a simple key-value that tracks volume per key and use last update to deduce the current volume and whether the request can be approved. It also maintains heartbeat to the assignment database.

Request flows

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...

Trade offs/Tech choices

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

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?