Loading...
Let us assume that the traffic shall be about 1 million requests per second, since all requests shall pass through the rate limiter.
Storage estimation depends upon the rules of the rate limiter i.e. scope (per api/ per user/ per ip/ per region/ per org/ all together), the type of algorithm used for rate limiting(token bucket, sliding window, leaky bucket, fixed window, etc.) , etc. So in the worst case lets say 1000 rules per user, for a million users. Thus, the storage estimations will be
As we can see storage isn't the issue, the crux of the problem is throughput to handle heavy traffic.
Moreover, the latency should be at minimum. Let us assume an API sitting behind the rate limiter takes a total of 100ms per call. Now, if the rate limiter takes 30ms, then total time becomes 130ms. The rate limiter itself caused an increase of 30% time for the total round trip. So, let us estimate that an acceptable latency would be sub 10ms , so we need the rate limiter to make decisions under 10ms.
On rules modification side:
We shall let users i.e. people using the rate limiter to modify and add rules, apis to the limiter. These shall be much less frequent, let's estimate at around 10 modifications per day. This is easy to maintain and handle since it is just storing rules and at a very low frequency.
There shall be a single API for modifying rules.
The rate limiter system has 2 main sections, RL-sidecar and RL-modify.
We have the clients, API gateways whose sidecars will be the decision side of our rate limiter system (RL-sidecar).
We then have a centralised microservice for the modifications side of the rate limiter called RL-modify.
We shall have centralised Redis server to which all the instances of the RL-sidecar shall communicate with.
We then have our backend services/ APIs that need to be rate limited.
The RL-modify i.e. modifications side shall be a separate microservice. That way, users of the RL can communicate globally making it highly globally available, shall be easy to scale and manage independently.
We will be using PostgreSQL with the RL-modify to store user info and rules created by users.
PostgreSQL shall have 2 tables. users and rules. We are mainly concerned with the rules table.
The rules table shall have the columns columns: rule_id (UUID primary key), scope (enum of user, ip, org, api_key), scope_value (the specific user ID or IP), api (the path being limited), algorithm (token_bucket, sliding_window, etc), max_requests (the limit), window_seconds (the time window), and burst_size (for token bucket). A unique constraint on (scope_type, scope_value, api_endpoint) prevents conflicting rules for the same scope and endpoint.
Redis shall store the keys in the format rl:{scope}:{scope_value}:{api}. Each of these keys stores whatever info we need for a selected algorithm to work. For example if we choose token bucket algorithm, we shall be storing in this key curr_tokens (the counter that keeps track of present tokens) and refill_rate (the rate per second at which the tokens are supposed to refill).
We choose to use PostgreSQL for modifying rules, because we need ACID properties on rules so that rules aren't mid way incompletely modified. Moreover, we use Redis as an in memory DB for decision making, because we need sub millisecond access to data (depending upon the algorithm) to provider for the low latency. Thus using an amalgamation of both SQL and in memory key value store, gives us best of both worlds.
Moreover, the rules that users modify in the RL-modify service gets stored in PostgrSQL. These rules are stored in a local cache that each RL-sidecar shall have.
For simplicity's sake we shall be implementing rate limiting on APIs (not API key/user/org/region based) and we shall using the token bucket algorithm for rate limiting. We choose tokens bucket because it will be enough for most APIs use case since it allows for burst traffic. It should be noted that the way system is designed, we can implement any algorithm we see fit for any API or particular use case.
For example, for the starter APIs of an app, token bucket should be implemented since we would need to allow traffic bursts. But in case of payment APIs we might need a stable flow of traffic (to protect the payment system), so we implement leaky bucket to facilitate that.
Admin users can access the RL-modify service to create rules for APIs rate limiting. These are stored in the RL-modify's PostgreSQL DB in the rules table. We only allow a user to modify rules 10 times a day and no more than that.
In order to keep the admin users from abusing the system and frequently changing the rules, thus in turn not letting our system work properly as intended. Admin users shall be authenticated, thus only admin users can access the dashboard since this is a sensitive part of the rate limiting system. Once the admin user creates/updates the rules and is stored the the DB, we invoke a NOTIFY operation and update the rules stored in all instances of local cache of RL-sidecar. We NEED to keep the latest rules in those local caches, because the rules are the core of how the APIs are to be rate limited. RL-sidecar uses these rules from their local caches to make decisions and determine if a request should go through.
All of the requests first hit our API gateway, which has the RL-sidecar responsible for making decision, whether to pass the request forward or not.
When a request is received, the RL-sidecar fetches the rules (in our case token bucket algorithm's values) i.e. token refresh rate, etc.
Now, our centralised Redis server keeps the counter i.e. the number of tokens currently available. The external Redis server stores this info in keys of format rl:{scope}:{scope_value}:{api} which has curr_tokens and refresh_rate of the tokens.
These tokens are continually updated as requests come to the RL-sidecar. Each request consumes 1 token. Lets assume initially the bucket has 10000 tokens, curr_tokens = 10000, with refresh_rate of 1000 tokens/second.
The whole decision process takes sub 10ms, since we are not querying anything from a persistent DB, instead we are making use of Redis as a key value store. Since Redis lives in memory, the whole round trip of deciding and forwarding/returning the request takes sub 10ms. This is well within our requirements of latency.
We discussed how 1 single instance of the RL-sidecar is handling the requests. But in case of horizontal scaling (to meet traffic needs and handle 1 million+ requests/second), lets suppose multiple pods of the API gateway are deployed. Thus, in turn the number of RL-sidecar pods increase as well. This is the benefit of making the rate limiter a sidecar, it scales according to traffic needs, thus no need to separately scale up horizontally. Now, in case of multiple pods of RL-sidecar (i.e. multiple pods of API gateway), all those pods still use the same Redis server because we need all the pods to use the same curr_tokens counter in order to maintain accuracy. Thus, a single Redis server is used by multiple instances/pods of RL-sidecar.
Here, another issue arises. Since there are multiple pods of RL-sidecar, there will most definitely be race conditions where multiple pods try to access and change the same curr_token leading to inaccuracies. To tackle this problem, we make use of Redis Lua scripts to read and update (decrement) the curr_token value in Redis. We use Redis Lua scripts because these scripts carry out operations on the resources in Redis with atomicity. Thus, at a moment, only 1 pod can read and decrement the curr_token, in turn maintaining accuracies and only letting appropriate amount of requests to pass through. So, the whole flow decision flow we discussed, all the operations carried out by RL-sidecar on Redis are done in a single Redis Lua script.
This approach makes our system resilient to inaccuracies. In this way, we make our rate limiter system scalable and able to handle high traffic at lightning speed, all without the danger of inaccuracies.
We have used sidecar design instead of a separate microservice is to reduce the latency of the system. Using sidecar makes the latency from API gateway to RL-sidecar 0ms, extremely reducing the latency. The tradeoff we are making here is that lets say there are N instance of API gateway, meaning N instances of RL-sidecar that we need to manage. Thus, in scenarios where the admin user creates/modifies new rules they need to be propagated to N RL-sidecars, incraseing overhead. But since we have restricted the number of modifications to rules that an admin can make AND we need low latency, this tradeoff is acceptable.
In our system, we have decided to use external central cache instead of local cache for RL-sidecars. Using local cache for decisions will again make latency to Redis as 0ms, but using local cache will have its own challenges. Each instance of RL-sidecar will need to communicate with other instances async to keep curr_tokens counter accurate and consistent thus in turn increasing latency. Moreover, in case of hotspot issues, a single instance of Redis(local) gets overwhelmed while others are free.
As we can see from the design, our rate limiter highly depends upon the centralised external Redis server for decision making. This makes the Redis server a Single Point Of Failure for the system. If Redis goes down, decision making is completely blocked. At this point we must decide to either go fail-open (let through all the requests) or fail-close(block all the requests from going forward). Ideally we should do a fail-close to protect the health of our backend APIs, thus trading off availability.
To prevent thundering herd problem, along with fail-close system, we additionally implement a circuit breaker pattern, so when Redis is not reachable, we open the circuit (i.e. fail-close) and completely block all requests . Periodically, we process a certain number of requests using the same Lua scripts and if certain threshold of requests pass (If 80% of those pass), we incrementally increase the number of requests and eventually reach full capacity. This helps us protect the backend APIs and gracefully bring the system back up.
Using circuit breaker and fail-close system, we completely block the system for a short period of time. BUT, there's another solution Redis Sentinel. We will use Redis Sentinel to tackle failure of external Redis server. Redis Sentinel provides multiple Redis instances packed into it. There's 1 primary instance and a few other replicas. All the changes from primary are asynchronously and periodically copied to the replicas, thus maintaining eventual consistency among multiple Redis instances. In normal conditions, Redis Sentinel routes all requests to the primary instance but in case the primary fails, Sentinel immediately promotes a replica to a primary while the previous primary recovers. Using Redis Sentinel makes our system HIGHLY fault tolerant without compromising availability.
The tradeoff is that using Redis Sentinel can serve stale data since the data is copied periodically and asynchronously, meaning some data might fail to be copied before the previous primary goes down. This is still acceptable since we need our rate limiter to be highly available.
In case of a hotkey problem, i.e. a single key is being accessed extremely frequently. Now imagine that in this case where millions and millions of requests come up for the same api. This will overwhelm the system, so to resolve this issue, we batch decrements in the Lua scripts in case of hotkey issue. Let’s say we batch 10 operations at a time. Just batching 10 at a time reduces the number of calls to Redis by 90%
This resolves the hotkey issue.