Loading...
The volume of requests would be depends on the volume of requests for the entire distributed system. and for Rate limiter system itself, all requests would be read requests.
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
I 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.
Shown as diagram
The client made a request and send out to our backend system. The API gateway would receive the requests and handover to Ratelimiter service with limit rules prefetched, and fetch the requests count for current userId and Ip if present.
Increment the count and check whether it exceed the limit, if so, reject the request with 429 http code and "too many requests" to let the client better understanding the situation and react on it. If passed, redirect to the Load balancer and routes to one of the server instance and process the real requests.
There are many algorithms such as Token Bucket, Leaking Bucket, Sliding Window, Fixed Window, etcs. What kind of algorithm should we select?
We'd like to make the limiting to be more accurate and also can handle spikes, so we can use the Token bucketalgorithms
Token bucket:
Shared bucket: For example if the our application allowed 10000 requests per second, we can have a shared bucket that prefilled with 10000 buckets
IP specific bucket: For a single IP address we may have indivual bucket
Pros: Can handle burst of traffic in a short time period.
Cons: May difficult to configure the buckets base on various businesses.
Sliding window log:
It would calculate the request count based on the timestamp of the request in the time window, and would remove the expired data if time window sliced。
Pros: Would be accurately limit the requests compare to Sliding window count
Cons: Might consume more memory
Sliding window count:
For example, we have limit rule 10 request per minute
Request count in current minute + overlap percentage * request count in previous minute.
Pros: It can smooth out the spikes and it's memory efficient
Cons: It's an approximate number as it assume the requests are evenly distributed in the previous window
1.Deploy Rate limiter in client, server or independent service (like API Gateway)?
Deploy in client side would be not recommended as it's hard to control and easily got modified.
Deploy with the backend application is a valid choice, before hitting the real logic we added the protection and check with the single logic. However, our application may overwhelmed by the high volume of requests, and also it's tightly coupled so it would diffcult to scale indivually.
I prefer deploy it in API Gateway as we can manage all api request from one location, and helps protect backend service from being overwhelmed by too many requests. Also API Gateway would receive requests before backend services.
2.Token bucket or other algorithms?
For handling requests accurately and be able to handle spikes as well, we choose to use Token bucket. The comparison is below:
Token bucket:
Shared bucket: For example if the our application allowed 10000 requests per second, we can have a shared bucket that prefilled with 10000 buckets
IP specific bucket: For a single IP address we may have indivual bucket
Pros: Can handle burst of traffic in a short time period.
Cons: May difficult to configure the buckets base on various businesses.
Sliding window log:
It would calculate the request count based on the timestamp of the request in the time window, and would remove the expired data if time window sliced。
Pros: Would be accurately limit the requests compare to Sliding window count
Cons: Might consume more memory
Sliding window count:
For example, we have limit rule 10 request per minute
Request count in current minute + overlap percentage * request count in previous minute.
Pros: It can smooth out the spikes and it's memory efficient
Cons: It's an approximate number as it assume the requests are evenly distributed in the previous window
1.Concurrency issues for read-and-write operations for multiple applications
If multiple applications read the current count of requests for the same key (same user), and they did the modification and make the write requests to Redis simutanously, we would suffer from the concurrency issues as Redis process the requests sequentially by a single thread.
If we have only one Redis instance, we can use Lua script to resolve this issue as it created for atomic usage natually. However, if we used Redis cluster in a large distributed system, Lua script can not guarantee the atomicity accross multiple Redis nodes.
We can only use distributed locks but it's a distributed locks and would slow down the response time. We actually can use key hash tagging while creating key such as rate_limiter:{userId:ip} to make sure the data would be hashed to the same slot (nodes), and combine with the lua scripts to ensure the thread-safe.
1.Performance optimization. We can make the Rate limit closer to the clients by deploying it in nearest Data center geographically.
2.Monitoring. It's import to analysis and monitor the metrics for Rate limiter to see whether it's efficient or not