System requirements

Functional:

1. Limit the access for users
2. What kind of Rate limiter are we going to design? Client-side or server side? - server side
3. Limit the access based on IP address, userId or other properties? - should be flexible enough to support different rules
4. Would the system going to be worked in a distributed system? - yes
5. What is the scale of this system? - The system should be able to handle large numbers of requests

Non-Functional:

1. High performance. The Rate limiter system should not impact the latency for the entire process of the request.
2. Highly scalable. The Rate limiter would be worked in a distributed system so it should be highly scalable to handle high volume of requests.
3. High fault toleratance. If any problems happened for the Rate limiter, it should not impact the entire system

Algorithms for Rate Limiting

We have the following rate limiting algorithms.

1. Token Bucket
   1. We feed tokens to a bucket in a predefined rate. One request consumes one token. When token runs out, the request will be throttled.
   2. For different scenario, we can set the bucket size and feeding rate.
   3. + easy implementation
   4. + handle burst requests scenario
   5. - hard to tune the bucket size and feeding rate
2. Leaking Bucket
   1. the requests are added into a queue. The consumer processes the requests from the queue in a fixed rate.
   2. + memory efficient as the queue size is fixed.
   3. - not able to handle burst requests.
   4. - hard to turn the queue size and processing rate.
3. Fixed Window Counter
   1. In a fixed time window, each user has a unique counter. The rate limiter increases the counter when it receive a request. If the counter reached to the limit, the request is throttled.
   2. + easy implementation.
   3. + memory efficient
   4. - the spike in the traffic at the end of an interval may cause more requests than allowed quota.
4. Sliding Window Log
   1. log the request and its timestamp. When a request received, count the total number of requests received in the passed time window and decide if throttle the request.
   2. + accurate throttling.
   3. - memory not efficient, Higher CPU to prune old entries
5. Sliding Window Counter
   1. When a request arrives in the current time window (e.g. at 30% timestamp in the current window), use the total number of requests in the previous time window to estimate the number of request in the last 70% interval of time window. Then plus the number of requests in the first 30% time of the current time window to decide if the current request exceeds the allowed quota.
   2. + memory efficient
   3. + Acceptable in accuracy (between sliding window log and fixed window counter)
   4. - complicated in implementation.

By comparing the above algorithm and their cons / pros, we decide to use the token bucket algorithm for our rate limiter as it is easy implementation and able to handle burst traffic. In actual practice, the algorithm can be dynamic to fit different use cases.

Capacity estimation

API design

For Rate limiter, API is not necessary needed for it

and generally if the requests received by the application, we would take the userId and ip address to validate whether it reached the limit or not

Database design

prefer using key-value store such as Redis for current design as it stores data in memory and easily to populate and use, also it would provide fast reads as everything stored in memory/

For data stored in Redis, we can use

tableName: RequestCounts

key: rate_limiter:userId:ipAddress

value: {

"count" : "3",

"requestTime" : currentMillis

}

In terms of deploying in the distributed system, we can have Redis Cluster which have at lease 3 masters and 3 followers to ensure high available, fault tolerance and best performance.

High-level design

The clients (web browser / mobile app) sends a request to rate limiter middleware.

the rate limiter middleware decides if the request should be limited

if limited, discard the request.

if not limited, pass the request to the API servers.

Request flows

why use API Gateway instead of Load Balancer

need an application-level component that can run that logic per request. A simple load balancer can’t interpret your rate-limit rules, hit Redis, or return a custom 429 payload—it can only proxy TCP/HTTP.

Flow Steps:

1. When a client sends a request to a server, the request is sent to API Gateway first.
2. Rate limiting rules are stored in disk (API-Gateway host’s local filesystem )as config files. Workers frequently pulls the rate limiting rules from disk and load it to rule cache (In-Memory Map/Hash on API Gateway).
   1. This “pull-and-cache” pattern lets you manage and update your rate-limit rules dynamically without touching or restarting the API Gateway itself
3. API gateway get the counter from the memory (redis) and the rule from the rule cache. it decides if the request is passed or throttled.
   1. If the request is passed, it is redirected to the API servers.
   2. If the request is throttled, it returns a response to the client with the response code 429 (too many requests). In some cases, the request can be pushed to a queue for later processing.

Rate Limiting Rule:

The rate limiting rules can be stored in disk as config files. For example:

{

"rules": [

"rate_limit": {

"unit": "minute",

"requests_per_unit": 5,

"burst_capacity": 10 # for token-bucket bursts

},

"algorithm": "token_bucket", # or fixed_window, sliding_window_log, etc.

}

]

}

Detailed component design

Rate Limiting in Distributed System:

Two problems:

1. Race Condition:
   1. In high concurrent environment, two API gateways read the same counter from memory, they increase the counter by 1 and write it back to memory cache.
   2. Solution:
      1. add a lock on the counter
         1. - decrease the performance
      2. Lua script in Redis.
         1. Lua script bundles multiple Redis commands (e.g. GET, INCR, EXPIRE) into one atomic operation
         2. Because Redis executes the entire script without interleaving other clients’ commands, you avoid the race-condition of “read + modify + write” across separate calls.
         3. read–modify–write happens entirely inside Redis, eliminating external race conditions without adding locks in your application.
2. Synchronization:
   1. a client can send requests to different servers (through multiple API Gateway). If the user sessions do not synchronized between the servers, the client could send more requests than the rate limiting rule allowed.
   2. Solution is to use the centralized data store (Redis) to store the user session data.
      1. client1 -> server1 -> centralized data store
      2. client2 -> server2 -> centralized data store
3. Performance Optimization:
   1. In distributed environment, user should access the closest data center (full deployment of your service stack (API gateways, application servers, caches like Redis, databases, etc.) co-located in one geographic region or facility) to send the requests.

Monitoring, Alert and Logging

1. Monitoring:
   1. the rate limiting algorithm is effective
   2. the rate limiting rules are effective
2. Load the data to metrics and use dashboard to visualize and alert to take actions when it is not healthy.
3. Logging can help to quickly find out the issue.

Trade offs/Tech choices

1. co-located with servers vs distributed system
   1. co-located with servers:
      1. + simple
      2. - not scalable of coupling. We need to spin up the whole service just to scale the rate limiting.
   2. distributed system:
      1. + decouple. independently scaling for servers and rate limiter
      2. - additional latency probably introduced.
2. Where to store the counter? Disk vs Memory
   1. Disk:
      1. + persistent (not necessary)
      2. - high latency
   2. In memory:
      1. + fast and support time-based expiration strategy
      2. Redis is a good choice: INCR and EXPIRE
         1. INCR: increase by 1 for the stored counter
         2. EXPIRE: it sets a timeout for the counter. If the timeout expired, the counter will be cleared.

Failure scenarios/bottlenecks

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

Future improvements

Hard rate limiting vs soft rate limiting:

• If the server load is not heavy and a client requests has reached the limit, we can allow extra quota for this client to improve the overall performance.