Loading...
This is a read heavy system.
If we assume 1M unique active users in a day, and 10% concurrency between our users -> we have 10^5 unique users.
10^5 * 100 bytes = 10MB storage for counter, which makes it suitable for in memory storage
Peak load = 10^6 req / sec (2 operations -> read the current count and increment the count)
Storage = 10^6 * 1000 (limit rules) * 32 bytes = 32 GB, which means we need to use Redis cluster and a sharding strategy
Rules changes rarely (<10 writes/sec) vs ~1M/sec reads. Rules cached in memory, counters in Redis. Both needs to be stored separately.
POST /ratelimit/status/{client_id}
Request:
{
client_id: string,
resource: string (API),
tokens: int (optional, no of tokens each request consume)
}
Response:
{
status: ENUM (allowed, blocked),
retry_at: timestamp,
retry_after: int (seconds after retry can be possible, if current status is blocked)
}
Admin POST /ratelimit/rules
Request:
{
resource: string (api endpoints, support wildcard),
limit: int,
time_window: int
tier: ENUM (free, paid, premium),
algorithm: ENUM (leaky bucket, sliding window etc)
}
GET /ratelimit/rules/{resource}
Response:
{
rules: list (all rules applicable to the API)
}
Clients call our API Gateway, which calls our Ratelimit Services.
Ratelimit services could be many nodes including RL1 to RL4 (N).
Based on the result from Ratelimit nodes response, the request will either be rejected, or forwarded to backend services.
On the other Side, Admin can call the Rules Service to add/modify/delete the rules, which will be saved in Postgres database and cached to the Rate limit nodes.
Since we need atomicity and the rules changes rate is relatively slow, Postgres is a good choice for our use case.
The Ratelimit nodes (RL1 to RL4), will call the Redis Cluster to get the current count (we will use Lua scripts, to handle the race conditions, which will read the current state and update the result in 1 atomic operation), compare it with the existing rules cached in memory, compare the values and return the result.
Result will either be success (forwarded to Backend service), or, 429 Too Many Request (with retry after, so that clients know the current status).
We can use headers to pass this info (XRateLimit-limit, XRateLimit-RetryAfter)
In case, there is any failure in the Ratelimit service (nodes going down, Redis cluster issue), we would either let the user access the backend (for non-critical paths) or block them (for critical paths) based on our config.
We would use consistent hashing, along with virtual nodes to handle the hot key paths
There are 2 types of storage required.
Each Rate Limit service nodes reads and updates the Redis Cluster atomically using Lua script, while the Rules are stored in memory cache of the nodes.
Redis
Key: ratelimit:{resource}:{client_id}:{window}
Value: 10
When Rules are modified, they are written to Postgress for persistence and then they are updated in the ratelimit nodes through cache invalidation (could use a rabbitMQ queue to push those invalidation)
Postgres Table:
id, Resource, Limit, Time Window, Tier, Algorithm, Created At, Updated at
We will discuss the following things in depth for our system:
We have different algorithms, including:
E.g. Tokens used in last 1 min window = 100
Time lapsed in current window = 20s
Tokens used in current window = 80
Limit = 120
Calculation - (20/60) * 100 + 80 = 113 -> under limit -> accepted
This method assumes that the rate of token utilisation will be similar to the rate in the previous window.
Sync Challenges: The nodes could be geographically apart and the info could take some time to travel and sync between the nodes. One solution could be to give each nodes its own quota -> E.g. limit = 1000, Nodes 4 -> Each node has limit of 250 tokens. While we continuously sync the data between the nodes in the background
Failure cases: If the nodes in one region is down, the users will be directed towards nodes in other region.
If the whole Ratelimiting system is down, we can close the system for critical cases (like payments etc), while we can let the requests through for non critical APIs.
We will manage concurrent hits using Redis Lua scripts, where one single atomic operation will read the tokens in the cluster and increment the count. This way, the concurrency issue is resolved.