This document specifies a concept for a multi-level rate limiting procedure that can be used to implement rate limiting of many kinds. It should be considered a work in progress!
This document describes the schema that should be utilized.
Each user shall be assigned a multi-level set of limiting that must pass for any request to continue.
We utilize a generic cell algorithm (GCRA) to implement intelligent backoff and burst handling using the Redis Module redis-cell
This is configured using limits.yaml. We use a recursive data format for building the rate limits and when a request is made against a given key, we call each step in the tree.
Internally this is handled efficiently using a built-in
luascript.
schema:
# user:
user:
children:
# if no others match
"*":
# limits against user:${username}
limits:
- 15
- 30
- 60
children:
# limits against user:${username}:trade
trade:
limits:
- 5
- 10
- 15Based on the above configuration, we can walk through an example situation. Lets say we have a user, alex. Whenever alex makes requests, we will run a check based on his action(s) to determine if he/she should be allowed to make the given request:
import { authorizeActionForUser } from "abstracted-redis-library-here";
// convenience function against the above request. "alex" will be
// substituted for the "*" value
authorizeActionForUser("alex", "trade").then(limited => {
if (limited) {
// user is rate limited!
}
});In this case, limited would be undefined since it is our first request. However, with each request that is made, the system will parse the tree and add a "token" against each limits key it encounters along the way.
In practice this looks like this:
# limits found at path schema.user.children["*"]
LIMITER user:alex 15 30 60 1
# limits found at path schema.user.children["*"].children.trade
LIMITER user:alex:trade 5 10 15 1We aggregate the results of all the requests (after they have been made) and return a summary of the results. This summary becomes the final descriptor of the limit against the given parameters. Limits may be nested as deeply as needed, remebering that every limits key encountered along the way will always be checked against and will cause a rejection if crosses the threshold.
It is important to realize that this means that
user:alex:tradeanduser:alex:withdrawalmeans that both requests go against theuser:alexquota whereas they each also maintain their own quotas on top. This is critical to consider when buildinglimitsas each root level must have enough of a quota to
In each step of the check, the replies we receive will each be an array:
/* @flow */
/**
* 0 = User is not being limited
* 1 = User is being limited
*/
type Limiter$IsLimited = 0 | 1;
/**
* Burst allowed requests in any interval
*/
type Limiter$Burst = number;
/**
* Remaining requests allowed before
* limited unless timer expires
*/
type Limiter$Remaining = number;
/**
* If the user is limited, how many seconds must they
* wait until they will be allowed to make the requested
* value again? This is -1 if the user is not being limited.
*/
type Limiter$RetryAfter = number;
/**
* How many seconds remain until the limiter resets to
* its maximum value?
*/
type Limiter$ResetsAfter = number;
type Limiter$Response = [
Limiter$IsLimited,
Limiter$Burst,
Limiter$Remaining,
Limiter$RetryAfter,
Limiter$ResetAfter
];This means that in our existing example, we will end up with a aggregated result looking something like:
type ExampleResponse = [Limiter$Response, Limiter$Response];In order to provide a valid final result, we then need to parse the response to provide a summary which matches Limiter$Response but takes into account every set of limits along the way.
type FinalSummary = Limiter$Response;If mapped to the standard rate limiting headers, this would mean the following for each item in the array response:
The meaning of each array item is:
- Whether the action was limited:
- 0 indicates the action is allowed.
- 1 indicates that the action was limited/blocked.
- The total limit of the key (max_burst + 1). This is equivalent to the common X-RateLimit-Limit HTTP header.
- The remaining limit of the key. Equivalent to X-RateLimit-Remaining.
- The number of seconds until the user should retry, and always -1 if the action was allowed. Equivalent to Retry-After.
- The number of seconds until the limit will reset to its maximum capacity. Equivalent to X-RateLimit-Reset.
Benchmark
Quick benchmarks against RateLimit.js in redback. Note that results got as high as a 5,000% increase in performance - however, this is likely due to Javascript Engine / Heap & Memory (a valid concern). RateLimit.js could not run when making more than 60,000 requests simultaneously whereas I was able to make nearly 1,000,000 requests simultaneously with the cell implementation before running out of heap memory (default node settings)
All tests run against
v10.8.0on Redis version4.0.11With Hardware Specs: