System requirements

Functional:

List functional requirements for the system (Ask the chat bot for hints if stuck.)...

• the rate limiter should be flexible enough to support different throttle rules
• should support a large number of requests, support a distributed system environment
• should be shared across multiple servers or processes
• show users their request are throttled when the rate limit is exceeded

Non-Functional:

List non-functional requirements for the system...

• low latency, the rate limiting service shouldn't slow down the HTTP response time
• reliable
• highly scalable

Capacity estimation

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

API design

Define what APIs are expected from the system...

if a request is throttled, return 429 too many requests.

rate limiting information in the response header

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

redis:

user_id, ip_address, count

depends on the rate limit rules:

• limit different pools of users separately? we will add pool_type to the schema
• Protect different API endpoints at different rates? add service_name

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

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

1. we have different rate limiting rules, rules are stored on disk, workers periodically pulls rules and put it into cache
2. when a client sends a request, the request goes into the middleware first
3. middleware checks rule corresponding to the API service/user_id/IP address/user_type, fetch count from redis
4. If rate limit is not limited, request is forwarded to API server
5. If it is limited, request is either dropped or put into a queue for retry.

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

For Redis, we can use the following two commands.

INCR: It increases the stored counter by 1.

EXPIRE: It sets a timeout for the counter. If the timeout expires, the counter is automatically deleted.

Since we are using rate limiter in a distributed environment, it can cause race condition in highly concurrent environment. We can use lock but that can be very slow. To resolve this, we can use LUA script or Redis sorted set efficiently, both of these strategies provide a way to perform atomic operation.

• LUA script: Use a Lua script to check if incrementing the request count will exceed the limit and update it at the same time. Because Lua scripts are run in a transaction (single thread), no other commands can interleave.
• sorted set: Redis sorted sets provide a way to group user requests with timestamps, allowing you to manage rate limiting efficiently. Using sorted sets allows you to count active requests on-the-fly without requiring complex locking mechanisms. You can use commands like ZADD to add the request with the timestamp, combined with automatic expiration (EXPIRE) to clean up old timestamps, keeping your counts accurate

Synchronization between multiple server:

To synchronize across different servers. We can go with single leader replication, we will read and write from the master node. Since we have a lot of writes, we can partition the database and hopefully that will be enough.

Trade offs/Tech choices

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

where do we want to implement the API rate limiter?

option 1: on the local service, easy to manage if we have different business logic for different service. But it is tightly coupled with the service.

option 2: on the load balancer, but we can have a lot of counts and the data is too large to store in memory on the load balancer.

option 3: use a distributed in-memory store like Redis which is good for our usecase

option 4: build rate limiting service as a separate microservice but this means for every API call we are adding an additional call which can increase lantency.

Failure scenarios/bottlenecks

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

If the master node goes down, we promote a follower to be the new master.

how to handle malicious users?

1. Rate Limiting with Penalties:
   • Implement stricter rate limits for users who consistently hit their limits or exceed them. This could involve temporarily reducing their allowed request rate for a certain period to discourage abusive behavior.
2. Blacklisting:
   • Introduce a mechanism to blacklist users (identified by IP address, API key, etc.) who demonstrate malicious behavior. Blacklisted users can be completely denied access for a certain duration or permanently based on severity.
   • Maintain a separate blacklist in Redis or a similar quick-access storage.

Future improvements

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

We need to set up multi data centres across the world because our service have users from different places in the world. We will go to the server closest to the users.