Rate Limiter with Redis
Rate Limiter, controls and limits the rate of requests to access an object or resource. This limitation is mostly represented by units like Requests Per Seconds (RPS) or Requests Per Minutes (RPM). The reason to use Rate Limiter is to maintain the resources available and prevent denial of service (DoS). One of the common algorithms to implement Rate Limiter is Leaky Bucket. In this blog post, the Leaky Bucket is implemented based on Redis cache engine.
The leaky bucket is an algorithm based on an analogy of how a bucket with a constant leak will overflow if either the average rate at which water is poured in exceeds the rate at which the bucket leaks or if more water than the capacity of the bucket is poured in all at once.
Why Redis?
As in the title Redis is used to implement a Rate Limiter. Here are the main reasons to use Redis to implement a Rate Limiter:
- High speed I/O makes Redis suitable for high loads of requests [1].
- Redis provides an atomic transaction to set a key to hold a value and set key to timeout after a given number of seconds [2]. Expiration of the keys works like leaks on the bucket. This transaction is provided via SETEX command.
- Redis provides a mechanism to lock resources [3]. Lock is necessary to guarantee the accuracy in checking the limit while many concurrent clients are requesting the same resource. Without lock the limit may exceed.
The Implementation:
The complete implementation in Python is publicly available on Github. In the following all parts are described. In this implementation, Rate Limiter records access logs on Redis (it’s like pouring water into the bucket) and sets expiry for each log (it’s like leaking water from the bucket). Per request the limit is checked to accept or reject the request.
In the above code snippet, the required modules are imported and the constructor of the Rate Limiter is defined. A connection pool is passed in con_pool . The limit is defined by number of requests (number_of_requests attribute) in a time bound (time_bound attribute). The limitation can be applied on each client separately (limit_per_client=True) or without distinguishing the clients (limit_per_client=False). lock_timeout is the default timeout to release the lock and log_value is the default value in setting access log.
In the above, private methods of the Rate Limiter are listed. The return value in all of them depends on the _limit_per_client flag. _get_lock_name() returns a unique lock name. If the flag is true it generate the lock name just by resource id otherwise the client id is also used. Per request the proper lock name should be returned to make sure the correct lock is acquired.
Access logs are (key, value) pairs on Redis. Keys should be unique to prevent overriding previous logs. On the other hand, there should be a pattern between logs to find and count related logs to a resource. Keys are generated by _generate_log_name() . All the related logs are started with the same string padded with a randomly generated string to make them unique. The same starting substring is the unique pattern between related logs.
To check the limit, number of available logs on Redis should be counted. _get_log_pattern() returns the pattern of the related logs to be counted. The patten depend on the _limit_per_client flag.Per request to a resource, number of related logs to the resource are counted by calling count_logs() . If the limit is exceeded is_allowed() returns false otherwise true is returned. If the request is accepted, an access log with expiration (time_bound) is recorded on Redis. All these operations are executed when the proper lock is acquired in the context manager. The log() method returns false if the limit is exceeded otherwise sets a key with expiration when the lock is acquired and returns true. To reset the limit flush_logs() is provided. It removes all the related logs on Redis.
Further Notes:
- Redis provides other features like scalability and persistency which are important in an enterprise system.
- If the limit is per client, it is necessary to define client id in a way that is not forgeable or at least make the forging hard. This is for security purposes because by forging the client id rate limiter is bypassed.
- There are other algorithms for rate limiting. For instance take a look at this link.
Feel free to comment or send me emails at pouya.esmaeili.g@gmail.com.
