Rolling Rate Limiter
Description
This is an implementation of a rate limiter in node.js that allows for rate limiting with a rolling window.
This means that if a user is allowed 5 actions per 60 seconds, any action will be blocked if 5 actions have already occured in the preceeding 60 seconds, without any set points at which this interval resets. This contrasts with many existing implementations, in which a user could make 5 requests at 0:59 and another 5 requests at 1:01.
It can use either in-memory storage or Redis as a backend. If Redis is used, multiple rate limiters can share one instance with different namespaces, and multiple processes can share rate limiter state safely without race conditions. The implementation uses what I believe to be a novel algorithm, with sorted sets.
Examples
In-memory
/* Setup: */ var RateLimiter = ; var limiter = ; /* Action: */ { // Argument should be a unique identifier for a user if one exists. // If none is provided, the limiter will not differentiate between users. var timeLeft = if timeLeft > 0 // limit was exceeded, action should not be allowed // timeLeft is the number of ms until the next action will be allowed // note that this can be treated as a boolean, since 0 is falsy else // limit was not exceeded, action should be allowed } /* Note that the in-memory version can also operate asynchronously. The syntax is identical to the redis implementation below. */
With a redis backend
This allows multiple processes (e.g. multiple instances of a server application) to use a single redis to share rate limiter state. Make sure that the limiters have identical configurations in each instance.
/* Setup: */ var RateLimiter = ; var Redis = ; var client = Redis; var limiter = ; /* Action: */ { ; }
As a middleware
You can easily use this module to set up a request rate limiter middleware in Express.
var limiter = ; app;
Method of operation
- Each identifier/user corresponds to a sorted set data structure. The keys and values are both equal to the (microsecond) times at which actions were attempted, allowing easy manipulation of this list.
- When a new action comes in for a user, all elements in the set that occurred earlier than (current time - interval) are dropped from the set.
- If the number of elements in the set is still greater than the maximum, the current action is blocked.
- If a minimum difference has been set and the most recent previous element is too close to the current time, the current action is blocked.
- The current action is then added to the set.
- Note: if an action is blocked, it is still added to the set. This means that if a user is continually attempting actions more quickly than the allowed rate, all of their actions will be blocked until they pause or slow their requests.
- If the limiter uses a redis instance, the keys are prefixed with namespace, allowing a single redis instance to support separate rate limiters.
- All redis operations for a single rate-limit check/update are performed as an atomic transaction, allowing rate limiters running on separate processes or machines to share state safely.