CHAPTER 4: DESIGN A RATE LIMITER

Requirement questions

Step 1

1. Is it a client side rate limiter or client side?

2. Does the rate limiter throttle request based on IP? User ID?

3. How many request are we talking?

4. Should it be a separate service or in application code?

5. Do we tell users they are throttled?

Common requirements

1. Low latency

2. High throughput

3. Low memory usage

4. High fault tolerance. If there are any problems with the rate limiter (for example, a cache server goes offline), it does not affect the entire system.

Status code for too many requests

429

Benefits of build your own rate limiter

You can choose algorithm

Algorithms for rate limiting

1. Token bucket

2. Leaky bucket

3. Fixed window counter

4. Sliding window counter

5. Sliding window log

Considerations for token bucket algo

1. Bucket size (burst request allowance)

2. Refill rate

3. Bucket grouping (per endpoint per IP per server)

Issue with fixed window counter

If the burst falls between 1 windows, up to 2x the limit would be allowed

How does sliding window log work

1. Keep track of each request timestamp

2. Get count of request in last 1s on every request

How does sliding window counter work

1. Uses fixed window counter, but use a percentage of each window

2. Not 100% accurate

Issues with refilling token bucket

1. A lot of load to constantly incrementing token counter

Alternative to refilling token bucket

1. Get token count

2. If positive, decrement token, update token timestamp, allow request

3. If negative, calculate new token count based on last updated token timestamp

How to make rules configurable

1. Use YAML config file, each rule has request filter, rate limit unit and requests per unit

2. Cache the rules

3. Add worker to update cache if rule changes

HTTP Headers for rate limiting

1. X-Ratelimit-Limit: total number of requests allowed

2. X-Ratelimit-Remaining: the remaining number of allowed requests

3. X-Ratelimit-Retry-After

Options when request hit rate limit

1. Drop

2. Put it in message queue and retry later

What’s the race condition challenge

• Client needs to calculate how many token in the bucket as well incrementing the bucket in 1 atomic action

• Otherwise 2 concurrent request may not count each other

Solution to race condition challenge

1. Use lua script for 1 atomic action

2. Use sliding window algo with Sorted String Set in Redis

Components needed for rate limiter

1. Rate limiter service

2. Redis

3. Rule store (cache)

How to improve performance

1. Close to user (multiple data centers or edge servers)

2. Synchronize data eventual consistency

How to reduce hitting rate limit

1. Cache on client side

2. Gracefully handle rate limit

3. Add sufficient back off time for retry

High level diagram