Introduction to limiting the number of requests with Redis [Part 1]
Recently, I have written several different ways to limit the number of requests using Redis . Both in commercial and in personal projects. In two parts of this publication, I want to cover two different, but related ways to limit the number of requests - using standard Redis commands and using Lua scripts. Each subsequent of the described methods will add new use cases and solve the flaws of the previous ones.
This publication assumes that you have some experience with Python and Redis and, to a lesser extent, with Lua, but it will also be interesting for those who have no such experience.
For example, Twitter limits the number of requests to its API, and Reddit and StackOverflow use restrictions on the number of messages and comments.
Someone limits the number of requests to optimize the utilization of resources, someone struggles with spammers. In other words, in the modern Internet, limiting the number of requests to the platform aims to limit the impact that the user can have. Regardless of the reason, let's assume that we must count some user actions and prevent them if the user has reached or exceeded a certain limit. Let's start by limiting the number of requests to some API, to a maximum of 240 requests per hour per user.
')
We know that we need to count actions and restrict the user, so we need a bit of auxiliary code. First, we must have a function that gives us one or more identifiers for the user performing the action. Sometimes it's just the user's IP, sometimes his ID. I prefer to use both if possible. At least IP if the user is not authorized. Below is the function that receives the IP and user ID using the Flask Flask-Login plugin.
Now we have a function that returns user identifiers and we can start to count our actions. One of the easiest ways available in Redis is to calculate the key for a time range and increment the counter in it whenever an action of interest occurs. If the number in the counter exceeds the value we need, we will not allow the action to be performed. Here is a function that uses automatically dimmed keys with a range (and lifetime) of 1 hour:
This is a fairly simple function. For each identifier, we increase the corresponding key in Redis and expose it to a lifetime of 1 hour. If the counter value exceeds the limit, you will return True. Otherwise, we return False.
That's all. Well, or almost. This allows us to solve our problem - to limit the number of requests to 240 per hour for each user. The reality, however, is that users quickly notice that the limit is reset at the beginning of each hour. And nothing will prevent them from making their 240 requests within a couple of seconds immediately at the beginning of the hour. Our work will go in that case to smarka.
Our primary goal with the restriction of requests with an hourly basis was successful, but users begin to send all their requests to the API as soon as it becomes possible (at the beginning of each hour). It looks like that in addition to the hourly limit, we should introduce a per second and minute limit to smooth out situations with a peak number of requests.
Suppose we decide that 10 requests per second, 120 requests per minute and 240 requests per hour are sufficient for our users, and allow us to better distribute requests over time.
To do this, we can simply use our over_limit () function:
This will work as we expected. However, each of the 3 over_limit () calls can execute two Redis commands — one to update the counter and another to set the lifetime for the key. We will execute them for IP and user ID. As a result, it may require up to 12 requests in Redis to simply say that one person exceeded the limit for one operation. The easiest method to minimize the number of requests to Redis is to use `pipelining` (pipelined requests). Such requests are also called transactional in Redis. In the context of Redis, this means that you will send many commands in one request.
We are lucky that our over_limit () function is written so that it is easy to replace the INCR and EXPIRE call with one request with MULTI . This change will allow us to reduce the number of requests to Redis from 12 to 6 when we use it with over_limit_multi () .
Reducing the number of calls to Redis twice is great, but we still make 6 requests just to see if the user can make a call to the API. You can write another variant over_limit_multi () , which does all the operations at once and checks the constraints after, but it is obvious that the implementation will have several errors. We will be able to restrict users and allow them to make no more than 240 requests per hour, although in the worst case, this will be only 10 requests per hour. Yes, the error can be corrected by making another request to Redis, or you can simply transfer all the logic to Redis!
Instead of fixing our previous implementation, let's move it to the LUA script that we will execute inside Redis. In this script, we will do the same thing as we did above - go through the list of restrictions, increase the counter for each identifier, update the lifetime and check if the counter has exceeded the limit.
Look at the piece of code right after the 'local bucket' . See that our Lua script looks like our previous solution and performs the same operations as the original over_limit () ?
We started from the same time interval, but in the end, we have a method for limiting the number of requests that can work with several levels of restrictions, work with different identifiers for a single user, and executes only one request to Redis.
Actually, any of the options for our limiters can be useful in different applications.
I could not find the correct way for an article from the sandbox to indicate that it is translated:
This publication assumes that you have some experience with Python and Redis and, to a lesser extent, with Lua, but it will also be interesting for those who have no such experience.
Why limit the number of requests?
For example, Twitter limits the number of requests to its API, and Reddit and StackOverflow use restrictions on the number of messages and comments.
Someone limits the number of requests to optimize the utilization of resources, someone struggles with spammers. In other words, in the modern Internet, limiting the number of requests to the platform aims to limit the impact that the user can have. Regardless of the reason, let's assume that we must count some user actions and prevent them if the user has reached or exceeded a certain limit. Let's start by limiting the number of requests to some API, to a maximum of 240 requests per hour per user.
')
We know that we need to count actions and restrict the user, so we need a bit of auxiliary code. First, we must have a function that gives us one or more identifiers for the user performing the action. Sometimes it's just the user's IP, sometimes his ID. I prefer to use both if possible. At least IP if the user is not authorized. Below is the function that receives the IP and user ID using the Flask Flask-Login plugin.
from flask import g, request def get_identifiers(): ret = ['ip:' + request.remote_addr] if g.user.is_authenticated(): ret.append('user:%s'%g.user.get_id()) return ret Just use the counters.
Now we have a function that returns user identifiers and we can start to count our actions. One of the easiest ways available in Redis is to calculate the key for a time range and increment the counter in it whenever an action of interest occurs. If the number in the counter exceeds the value we need, we will not allow the action to be performed. Here is a function that uses automatically dimmed keys with a range (and lifetime) of 1 hour:
import time def over_limit(conn, duration=3600, limit=240): bucket = ':%i:%i'%(duration, time.time() // duration) for id in get_identifiers(): key = id + bucket count = conn.incr(key) conn.expire(key, duration) if count > limit: return True return False This is a fairly simple function. For each identifier, we increase the corresponding key in Redis and expose it to a lifetime of 1 hour. If the counter value exceeds the limit, you will return True. Otherwise, we return False.
That's all. Well, or almost. This allows us to solve our problem - to limit the number of requests to 240 per hour for each user. The reality, however, is that users quickly notice that the limit is reset at the beginning of each hour. And nothing will prevent them from making their 240 requests within a couple of seconds immediately at the beginning of the hour. Our work will go in that case to smarka.
We use different ranges.
Our primary goal with the restriction of requests with an hourly basis was successful, but users begin to send all their requests to the API as soon as it becomes possible (at the beginning of each hour). It looks like that in addition to the hourly limit, we should introduce a per second and minute limit to smooth out situations with a peak number of requests.
Suppose we decide that 10 requests per second, 120 requests per minute and 240 requests per hour are sufficient for our users, and allow us to better distribute requests over time.
To do this, we can simply use our over_limit () function:
def over_limit_multi(conn, limits=[(1, 10), (60, 120), (3600, 240)]): for duration, limit in limits: if over_limit(conn, duration, limit): return True return False This will work as we expected. However, each of the 3 over_limit () calls can execute two Redis commands — one to update the counter and another to set the lifetime for the key. We will execute them for IP and user ID. As a result, it may require up to 12 requests in Redis to simply say that one person exceeded the limit for one operation. The easiest method to minimize the number of requests to Redis is to use `pipelining` (pipelined requests). Such requests are also called transactional in Redis. In the context of Redis, this means that you will send many commands in one request.
We are lucky that our over_limit () function is written so that it is easy to replace the INCR and EXPIRE call with one request with MULTI . This change will allow us to reduce the number of requests to Redis from 12 to 6 when we use it with over_limit_multi () .
def over_limit(conn, duration=3600, limit=240): pipe = conn.pipeline(transaction=True) bucket = ':%i:%i'%(duration, time.time() // duration) for id in get_identifiers(): key = id + bucket pipe.incr(key) pipe.expire(key, duration) if pipe.execute()[0] > limit: return True return False Reducing the number of calls to Redis twice is great, but we still make 6 requests just to see if the user can make a call to the API. You can write another variant over_limit_multi () , which does all the operations at once and checks the constraints after, but it is obvious that the implementation will have several errors. We will be able to restrict users and allow them to make no more than 240 requests per hour, although in the worst case, this will be only 10 requests per hour. Yes, the error can be corrected by making another request to Redis, or you can simply transfer all the logic to Redis!
Believe correctly
Instead of fixing our previous implementation, let's move it to the LUA script that we will execute inside Redis. In this script, we will do the same thing as we did above - go through the list of restrictions, increase the counter for each identifier, update the lifetime and check if the counter has exceeded the limit.
import json def over_limit_multi_lua(conn, limits=[(1, 10), (60, 125), (3600, 250)]): if not hasattr(conn, 'over_limit_multi_lua'): conn.over_limit_multi_lua = conn.register_script(over_limit_multi_lua_) return conn.over_limit_multi_lua( keys=get_identifiers(), args=[json.dumps(limits), time.time()]) over_limit_multi_lua_ = ''' local limits = cjson.decode(ARGV[1]) local now = tonumber(ARGV[2]) for i, limit in ipairs(limits) do local duration = limit[1] local bucket = ':' .. duration .. ':' .. math.floor(now / duration) for j, id in ipairs(KEYS) do local key = id .. bucket local count = redis.call('INCR', key) redis.call('EXPIRE', key, duration) if tonumber(count) > limit[2] then return 1 end end end return 0 ''' Look at the piece of code right after the 'local bucket' . See that our Lua script looks like our previous solution and performs the same operations as the original over_limit () ?
Conclusion
We started from the same time interval, but in the end, we have a method for limiting the number of requests that can work with several levels of restrictions, work with different identifiers for a single user, and executes only one request to Redis.
Actually, any of the options for our limiters can be useful in different applications.
I could not find the correct way for an article from the sandbox to indicate that it is translated:
- Written by Josiah Carlson
- Original article
Source: https://habr.com/ru/post/241321/
All Articles