System requirements

Functional:

• User can set an allowed rate of access (requests / second) for a particular API.
• There can be many configurations for the rates: for example, per user per API, per IP address per API, per organization per API. For the sake of simplicity, we will assume the configuration is per user per API.
• We use token bucket rate limiting algorithm.

[Mid-level deep dive topic.]

Two of the commonly used rate limiting algorithms are (1) token bucket, and (2) leaky bucket. Token buckets allow a burst of traffic. As long as the rate is below the set limit, even bursty traffic get through. Leaky bucket, on the other hand, restricts the rate of requests to a certain limit. Here we will use the token bucket algorithm. It is suitable for API rate limiting because it allows bursty traffic.

Leaky bucket is more suitable for protecting resources by smoothing out traffic.

[Mid-level deep dive topic.]

Rate limiting can be done at several levels. For example:

• At API Gateway. The benefit of this approach is its wholeness. We can protect data centers as a whole with this rate limiter because all requests come through API GW. The disadvantage is that this would be coarse-grained. Since API GW is not aware of contextual information (e.g. who the requesting user is, user profile, organization the user belongs to, etc.), it can only implement simple configurations, e.g., rate limit access to a REST endpoint by IP addresses.
• Inside a data center, at an application service level. The benefit of this approach is, because app servers can access the contextual information, we can implement more fine-grained configuration, e.g., a rate per API endpoint per user, for particular users, accessing particular resources. The disadvantage is that it would need a more complex architecture. We would have to modify more nodes.

In this solution, we will work on the latter (in-date center RL) for its flexibility.

[As you can see, we have a couple of tradeoff discussions in the requirements section. These are important tradeoff decisions you would like to make early in the interview. However, you do not want to spend too much time. In an interview, we would probably defer the algorithm decision later. The architecture tradeoff (at API GW vs in-data center RL) is more important to decide at a requirement stage.]

Non-Functional:

• Reliability.
• Response time. Let's shoot for < 10ms per request.
• Scalability.

Capacity estimation

• Overall, let's assume 1 million requests / second.
• 1 million users.
• 1000 configuration settings.
• Each configuration needs, let's say, 256 bytes. This would result in 256KB data for configuration. It can be stored in RDB.
• Buckets should be stored in a in-memory cache for fast response time. For example, Redis Cache, or in Cache Service's memory.

API design

• is_allowed(user_id, request_context, API_endpoint, target)

These parameters define the type of request:

Using user_id, Cache Service can obtain who the requesting user is, and the profile information of the user.

request_context provides rich information about the request, e.g., IP address, browser information, request header information, etc.

API_endpoint tells us what action the user is trying to take.

target determines which resource the user is trying to access.

This API returns the request is allowed or denied. If denied, it would return the number of seconds the client can retry. This is an advice the server gives the client, if the server wants the client to implement a back off strategy (e.g. exponential backoff).

Database design

Each token bucket should be represented by an object in memory:

• bucket_id
• user_id
• number of tokens

Let's say the size is 32 bytes.

At maximum level, 1 M users * 1000 RLs * 32 bytes = 32GB. The size is small enough to fit into one server's main memory. (Although we should partition it for scalability and performance.)

High-level design

[Mid-level deep dive topic.]

Should Rate Limiting Service (RLS) itself store the buckets in memory, or should it store it in an external cache service like Redis?

In-memory approach: The benefit of this approach is the latency of reading and writing the bucket. The disadvantage is, all the requests that for a particular bucket comes to one RLS server. This can create a bottleneck (hot spot). If millions of requests suddenly come to one RLS server, it can overwhelm the server, causing slowness or even a crash. By its definition, rate limiting service has to handle a burst of requests.

External cache approach, e.g., Redis Cache: The benefit of this approach is that is_allowed() requests can be distributed across RLS servers. This reduces the risk of one RLS server becoming a bottleneck. It also provides separation of concerns. Redis Cache is now solely responsible for storing the buckets. It is a specialized component for optimizing performance, scalability, and fault tolerance, of caching. RLS can focus on other tasks, such as reading configurations, gather user profile, and so on. The disadvantage is that Redis Cache can now be the bottleneck. As it is a cache system designed for high performance and scalability, we can expect it to withstand load better than newly implemented RLS.

Request flows

Clients (e.g. browsers, mobile apps) request some services via API Gateway.

Services, who need rate limiting, send is_allowed() calls to Rate Limiting Service (RLS).

RLS, using configuration stored in the database, and buckets stored in Cache, decide if the request is allowed or not.

Detailed component design

How Rate Limiting Service Uses Cache For Buckets

[Mid-level deep dive topic.]

Earlier, we decided to store the buckets in a cache service (e.g. Redis Cache). A concurrency challenges arises.

Let's say RLS naively implements the bucket naively:

1. RLS reads the number of tokens in a bucket (N) from cache.
2. That number is below the bucket threshold. RLS increments it by one (N+1).
3. RLS writes the number (N+1) in cache.

If two RLS servers take step (1) concurrently, they may end up writing N+1 (instead of the correct value, N+2) to cache in step (3). This is a race condition.

To avoid this, we can use atomic increment / decrement functionality of Redis. Instead of reading value and writing value, RLS can call INCR command to atomically increase the value by 1.

Every second (or every minute, depending on the RL configuration), the number of tokens must be decreased. This can be done by atomic decrement command, which can decrement the counter by a number larger than 1.

This approach may create a throughput problem because they would now be more requests to Redis. One way to approach this is for RLS to increment the counter locally, and update the bucket counter in one out of K (e.g. 10) times.

Trade offs/Tech choices

See tradeoff discussions in Requirements and Failure Scenarios sections.

Failure scenarios/bottlenecks

Hot Spots on Cache

[Mid-level deep dive topic.]

One of the important challenges of this problem is the rapid number of requests. Earlier, we took the decision to store the bucket counters in an external cache service (e.g. Redis) instead of Rate Limiting Service. This allows us to replicate RLS servers and load-balance among them. Consistent hashing may be used to distribute the load evenly among them.

We need to make sure Cache service is scalable. Although the counters (at 32GB) would fit in one Cache server, we should still partition them so that one server does not receive overwhelming number of requests. A bucket is identified by a combination of user_id and API. We can use the hash of (user_id, API) combination as a portioning key.

Even with partitioning, a hot key issue is possible. If one user suddenly starts hitting one API rapidly, it may overwhelm the cache.

One mitigation would be for RLS to increment the counter locally, and update the bucket counter in one out of K (e.g. 10) times. We need to decide which buckets need this special logic, by configuration, or by auto-configuration based on monitoring.

Server Unavailability

[Mid-level deep dive topic.]

RLS servers are stateless. Therefore, if one of the RLS servers becomes unavailable (crashes, network partition, extreme slowness, etc.), another can take over without a major downtime. A coordination service, e.g., ZooKeeper can be used to keep track of membership of the servers.

When a cache service becomes unavailable, that would be more challenging. Bucket counters get lost. RLS may have to resort to blocking all requests (fail open), or starting all the bucket counters from 0, allowing many requests which should be blocked.

We can add read backup replicas to cache service. By keeping the same information between the leader and the replicas, the replicas can take over for the leader in case the leader becomes unavailable.

We need to do careful performance measurement and analysis to decide if this is an effective approach. For example, if most of the rate limiters are configured for each second (e.g. 100 requests per second), the recovery from a replica may not be effective. If it takes more than 1 second for the replica to take over, it might not be worth the effort to synchronize data between the leader and the replicas.

On the other hand, if most of the rate limiters are of per-minute granularity (e.g., 10,000 requests per minute), the replication method would make sense.

Future improvements

In this solution, we restricted the RL configuration to user and rate. In the real world, there would be many more configurations:

• RL for organizations instead of individual users.
• RL for particular actions (e.g. you can read this resource 100 times / s, but write only 3 times / s).
• RL for particular resources
• Dynamic RL (e.g. you can send 100 emails out, but keep it to 3 during peak hours).

It would require enrichment of the components we designed.