System requirements

Functional:

1. The requests from clients should be limited to servers
2. The limit rules should be flexible for different use cases, like IP address, user id, etc.
3. The rate limiter should be able to work in distributed environment
4. The user should receive notification when the request is throttled.
5. the limited request should be either discarded or forwarded to a queue for later processing which depends on use cases.

Non-Functional:

1. High availability: the rate limiter should be high available to limit requests from clients
2. low latency: the rate limiter should be in low latency when deciding if limiting a request
3. High error tolerance: if the rate limiter failed, it should not affect the entire system
4. monitoring, alerts and logging

Rate Limiting Algorithms:

We have the following rate limiting algorithms.

1. Token Bucket
2. We feed tokens to a bucket in a predefined rate. One request consumes one token. When token runs out, the request will be throttled.
3. For different scenario, we can set the bucket size and feeding rate.
4. + easy implementation
5. + handle burst requests scenario
6. - hard to tune the bucket size and feeding rate
7. Leaking Bucket
8. the requests are added into a queue. The consumer processes the requests from the queue in a fixed rate.
9. + memory efficient as the queue size is fixed.
10. - not able to handle burst requests.
11. - hard to turn the queue size and processing rate.
12. Fixed Window Counter
13. 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.
14. + easy implementation.
15. + memory efficient
16. - the spike in the traffic at the end of an interval may cause more requests than allowed quota.
17. Sliding Window Log
18. 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.
19. + accurate throttling.
20. - memory not efficient
21. Sliding Window Counter
22. 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.
23. + memory efficient
24. + Acceptable in accuracy (between sliding window log and fixed window counter)
25. - 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.

Database design

userID: String

IpAddress: String

timestamp: DateTime

serviceName: String

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.

Design Deep Dive

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 as config files. Workers frequently pulls the rate limiting rules from disk and load it to rule cache.
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.
4. If the request is passed, it is redirected to the API servers.
5. 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:

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

domain: auth

descriptor:

key: auth_type

value: login

rate_limit:

unit: minute

request_per_unit: 5

Rate Limiting in Distributed System:

Two problems:

1. Race Condition:
2. 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.
3. Solution:
4. add a lock on the counter
5. - decrease the performance
6. lua script or sorted set data structure in Redis.
7. Synchronization:
8. a client can send requests to different servers. If the user sessions do not synchronized between the servers, the client could send more requests than the rate limiting rule allowed.
9. Solution is to use the centralized data store to store the user session data.
10. client1 -> server1 -> centralized data store
11. client2 -> server2 -> centralized data store
12. Performance Optimization:
13. In distributed environment, user should access the closest data center to send the requests.

Monitoring, Alert and Logging

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

Trade offs/Tech choices

Explain any trade offs you have made and why you made certain tech choices...

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

Failure scenarios/bottlenecks

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?

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.