Rate limiting

A load-shading solution assesses the state of the entire cluster or a specific node to protect the system and ensure critical requests are processed.

This approach, however, can be unfair. It does not distinguish between clients making requests.

Imagine two clients: A and B. Client A sends one request per second on average. Client B sends 20 requests per second—either intentionally or by error.

The load-shader only tracks total request volume, not client identity. As a result, when the total request limit is reached, requests from both clients are dropped.

Client A may have a single request rejected—even though it is not overloading the system.

This is the noisy neighbor problem: one client’s high volume degrades service for others, even if they are not responsible.

In multi-tenant systems, shared resources must be fairly allocated among clients.

We must limit total request volume to protect the system.

At the same time, each client must be guaranteed a fair share of available resources.

One solution: split the total request limit across all clients.

Each client gets an individual request quota.

No client exceeds their assigned limit within a time interval.

Requests beyond that limit are dropped.

This is the core idea behind request rate limiting.

Also known as request throttling.

Rate limiting controls the rate of requests sent or received over a network.

It operates on a per-client basis.

Our goal is to design a rate-limiting solution.

What time interval should we use?

How should we handle requests of different processing costs?

Typically, some requests are cheap to process, others are expensive.

We must account for this difference.

Possibly by assigning a cost to each request.

But this is not yet clear.

Set time interval to one second.

Later, make this configurable.

Assume all requests have equal cost.

A common starting point: begin with simplicity.

A random internet user advised starting small and simple.

I will follow this advice.

Start with a single server processing requests for multiple clients.

For each client, track the number of requests received every second.

When the count reaches a defined limit, no further requests from that client are accepted during that second.

Where to store request counters?

Two options:

• Memory

• Persistent storage

Memory allows fast access and real-time updates.

Persistent storage ensures state survives restarts.

But memory is sufficient for a single-server, short-duration scenario.

We will evaluate both options in later parts.

The design must ensure fairness, prevent overloading, and maintain system stability.

Each client’s request rate must be bounded individually.

The system must not allow one client to dominate resource usage.

This ensures equitable service delivery across all clients.

The solution must be scalable and adaptable to future changes.

We will refine the time interval and cost model in subsequent sections.

For now, the design is grounded in simplicity and fairness.

The core mechanism remains: per-client, per-second request counting with a hard limit.

Store request counters in a local in-memory cache or disk. Prefer an embedded database for simplicity and speed.

Since counters are short-lived and don’t need persistence, store them in memory for fast access.

Use a unique client identifier—such as username, email, or IP address—as the key.

The value is the total number of requests made by that client.

Store the timestamp of the request in the key or alongside the counter.

Both approaches have trade-offs in cost and performance. This document focuses on the key-based timestamp method.

When a request arrives:

• Identify the client using their unique identifier.
• Retrieve the client’s request counter from the local cache.
• Check if the request limit has been reached.
• If the limit is exceeded, reject the request.
• If not, increment the counter and update the cache.

This flow works well under ideal conditions.

Two critical issues emerge:

• Concurrency: Multiple threads accessing the same cache entry simultaneously can cause race conditions.
• Cache size: Each client generates a new key every second, leading to exponential key growth.

Use atomic operations or logs to ensure thread-safe updates.

Atomic variables prevent race conditions during counter increments.

Implement eviction policies to prevent memory overflow.

Options include:

• LRU (Least Recently Used) eviction
• Time-based expiration

LRU works well because keys for past seconds are no longer accessed.

Time-based expiration removes keys that are no longer in use.

Active expiration is more effective than passive expiration.

Active expiration uses a background thread that runs at regular intervals to delete expired entries.

Passive expiration removes entries only during read or write operations, which is less reliable.

With multiple servers, requests from the same client are distributed across servers.

The load balancer distributes requests evenly.

This implies dividing each client’s quota by the number of servers in the cluster.

This approach is simple to implement and maintain.

It allows reuse of the single-server rate limiting solution.

When servers join or leave, the cluster size must be updated across all nodes.

This requires timely communication of a static value—such as cluster size—to all servers.

Options for sharing this information include:

• Configuration management tools deploying the value directly to each server
• Pulling data from a database or object storage at regular intervals
• Using a gossip protocol

The even distribution by load balancers suggests that the current design is scalable in theory.

However, the need for real-time cluster size updates introduces operational complexity.

This remains a known challenge in distributed systems.

Not all requests from the same client are guaranteed to be distributed uniformly across servers.

A simple example shows this issue: if a client’s quota is low, some servers may receive many more requests than others.

This imbalance occurs even when the client quota is sufficient. However, when quotas are low, the problem becomes significant.

If the load balancer routes connections rather than requests, persistent connections may transfer far more requests than others.

These issues indicate that the initial simple design is a reasonable starting point.

But it should be evaluated for improvements.

Let’s examine the last example closely. It may reveal useful design insights.

Using small, concrete examples to generate ideas is a proven strategy.

Since servers handle different numbers of requests from the same client, what if all servers periodically share the total number of requests they’ve received?

Each server would then know the full cluster-wide request count per client.

With each new request, every server compares the total count against a client quota and makes a throttling decision.

How can this dynamic data be shared across the cluster?

Several existing solutions exist.

One is gossiping.

Servers can discover peers via service registry or DNS-advertised seed nodes.

They exchange request counts one or several times per second using TCP or UDP.

However, this approach does not scale well in large clusters with many clients.

As cluster size grows, communication cost increases with each new server.

An alternative is a shared cache.

All servers report their partial request counts to the cache.

Hash partitioning and consistent hashing enable a scalable, performant, and reliable distributed cache.

This approach scales better with cluster size.

Another key point: what should clients do when requests are throttled?

This has been discussed before.

Retries with exponential backoff, fallbacks, and request batching are established patterns.

I will end this thought experiment here.

I hope this demonstrates progress in solving an ambiguous problem.

It may seem unrealistic to design a real production system in 10 minutes using only conventional knowledge.

Yet, it is possible.

Many details are omitted in this third part.

But the high-level ideas are used in real-world systems.

For example, Yahoo and AWS use gossiping and distributed caches for rate limiting.

The main difference between these ideas and real systems lies in how request counts are stored in the cache.

Some algorithms allow a single keeper client to manage the count.

One such algorithm is called the talking bucket.

For more details on how it works, see the video on my YouTube channel.

This slide summarizes all concepts explicitly mentioned or implied in the rate limiting design.

Most were discussed previously and will be covered in future lessons.

There is much to discuss with a teammate or colleague when analyzing rate limiting.

Revisit the corresponding course videos to brush up on these concepts.