Requirements of a Rate Limiter

Our focus in this lesson is to design a rate limiter with the following functional and non-functional requirements.

Functional requirements

• Limit the number of requests a client can send to an API within a time window.

• The limit of requests per window must be configurable.

• The client should get a message (error or notification) whenever the defined threshold is crossed within a single server or combination of servers.

Non-functional requirements

• Availability: Essentially, the rate limiter protects our system; therefore, it should be highly available.

• Low Latency: As all API requests pass through the rate limiter, it should work with a minimum latency without affecting the user experience.

• Scalability: Our design should be highly scalable. It should be able to rate-limit an increasing number of clients’ requests over time.

Types of throttling

There are three types of throttling a rate limiter can perform.

1. Hard throttling: This type of throttling puts a hard limit on the number of APIs requests. So, whenever a request exceeds the limit, it is discarded.

2. Soft throttling: Under soft throttling, the number of requests can exceed the predefined limit by a certain percentage. For example, if our system has a predefined limit of 500 messages per minute with a 5% exceed in the limit, we can let the client send 525 requests per minute.

3. Elastic or Dynamic throttling: In this throttling, the number of requests can cross the predefined limit if the system has excess resources available. However, there is no specific percentage defined for the upper limit. For example, if our system allows 500 requests per minute, it can let the user send more than 500 requests when free resources are available.

Where to put the rate limiter?

There are three different ways to place the rate limiter.

1. At the client-side: It is easy to place the rate-limiter at the client-side; however, this strategy is not safe as it can easily be tempered by malicious activity. Moreover, the configuration on the client-side is also difficult to apply in this approach.

2. At the server-side: As shown in the following figure, the rate limiter is placed on the server-side. In this approach, a server receives a request which is passed through the rate-limiter that resides on the server.

3. As a middleware: In this strategy, the rate-limiter acts as middleware, throttling requests to API servers, as shown in the following figure.

A question might arise that where the rate limiter should be placed, on the server-side or as a middleware? The answer to this question is subjective. It depends on the organization’s technology stack, engineering resources, priorities, plan, and goals.

Many modern services use APIs to provide their functionality to the clients. API end-points can be a good vantage point to rate-limit the incoming client traffic because all the traffic pass-through them.

Two models for implementing rate-limiter

One rate limiter might not be enough to handle enormous traffic to support millions of users. Therefore, a better option is to use multiple rate-limiters as a cluster of independent nodes. Since there will be numerous rate limiters with their corresponding counters (rate limit); therefore, there are two ways to use databases to store, retrieve and update the counters along with the user information.

1. Rate-limiter with centralized database: In this approach, rate-limiters interact with a centralized database, preferably Redis or Cassandra. The advantage of this model is that since the counters are stored in centralized databases; therefore, a client can’t exceed the pre-defined limit. However, there are a few drawbacks to this approach. It causes an increase in latency if an enormous number of requests hit the centralized database. Another extensive problem is the potential for race conditions in highly concurrent requests (or associated lock contention).

2. Rate-limiter with distributed database: Using an independent cluster of nodes is another approach where the rate-limiting state is in a distributed database. In this approach, each node has to track the rate limit. The problem with this approach is that a client could exceed a rate limit (at least momentarily while the state is being collected from everyone) when sending requests to different nodes (rate-limiters). To enforce the limit, we must set up sticky sessions in the load balancer to send each consumer to exactly one node. However, this approach lack fault tolerance and scaling problems when nodes get overloaded.

Apart from the above two concepts, another question is whether to use a global counter shared by all the incoming requests or individual counters per user. For example, the token bucket algorithm can be implemented in two ways. In the first method, all requests can share the total number of tokens in a single bucket, while in the second method, individual buckets are assigned to users. The choice of using shared or separate counters (buckets) depends on the use case and the rate-limiting rules.

Building blocks we will use

The design of the rate limiter utilizes the following building blocks that we discussed in the initial chapters.

• Database(s) will be used to store rules defined by a service provider and metadata of users using the service.
• Cache(s) are used to cache the rules and users’ data for frequent access.
• Queue(s) are essential for keeping the incoming requests that are allowed by the rate limiter.

In the next lesson, we will focus on the high-level and detailed design of a rate limiter based on the requirements discussed in this lesson.