Neste artigo, veremos alguns algoritmos de limite de taxa baseados em Python e Redis, da implementação mais simples ao avançado algoritmo Generic Cell Rate Algorithm (GCRA ). Usaremos redis-py
para interagir com Redis (
pip install redis) . Sugiro clonar meu repositório para experimentar as restrições de consulta.
Limite de tempo
A primeira abordagem para limitar o número de solicitações por período é usar um algoritmo de tempo limitado: para cada chave de limitação (chave de taxa, algo único, como um apelido ou endereço IP), um contador (inicialmente definindo o valor limite) e uma data de expiração são armazenados separadamente (período), que diminuem conforme as solicitações são recebidas.
Com Python e Redis, você pode implementar esse algoritmo da seguinte maneira:
- Verificando a existência da chave de restrição.
- Se existir, inicialize-o com um valor limite ( Redis SETNX ) e uma data de validade ( Redis EXPIRE ).
- Diminuímos esse valor com cada solicitação subsequente ( Redis DECRBY ).
- As consultas são interrompidas apenas quando o valor cai abaixo de zero.
- Após um período de tempo especificado, a chave é excluída automaticamente.
from datetime import timedelta
from redis import Redis
def request_is_limited(r: Redis, key: str, limit: int, period: timedelta):
if r.setnx(key, limit):
r.expire(key, int(period.total_seconds()))
bucket_val = r.get(key)
if bucket_val and int(bucket_val) > 0:
r.decrby(key, 1)
return False
return True
Você pode ver o trabalho desse código ao emular o limite de 20 requisições em 30 segundos (para deixar mais claro, coloquei a função em um módulo).
import redis
from datetime import timedelta
from ratelimit import time_bucketed
r = redis.Redis(host='localhost', port=6379, db=0)
requests = 25
for i in range(requests):
if time_bucketed.request_is_limited(r, 'admin', 20, timedelta(seconds=30)):
print ('Request is limited')
else:
print ('Request is allowed')
Apenas as primeiras 20 solicitações não serão limitadas, depois delas você terá que esperar 30 segundos para que novas solicitações possam ser enviadas novamente.
A desvantagem dessa abordagem é que ela não limita a frequência, mas o número de solicitações feitas pelo usuário em um determinado período. Se todo o limite se esgotar imediatamente, você terá que aguardar o fim do período.
Algoritmo de balde com vazamento
Existe uma abordagem em que podemos limitar a frequência com muito cuidado: este é o algoritmo de intervalo atual . O princípio de operação é o mesmo de um balde com vazamento real: despejamos água (solicitações) no balde até as bordas, enquanto parte da água flui constantemente pelo orifício no fundo (geralmente implementado usando um processo em segundo plano). Se a quantidade de água despejada no balde for maior do que a quantidade de água despejando, o balde está cheio e, quando estiver cheio, novos pedidos não são mais aceitos.
Como o algoritmo funciona
Você pode pular esta abordagem para obter uma solução mais elegante que não requer um processo separado para emular o vazamento: o algoritmo Generic Cell Rate.
Algoritmo de controle de taxa de célula generalizada
O GCRA foi criado no setor de telecomunicações, onde é denominado Modo de Transferência Assíncrona (ATM). Foi usado por gerentes de rede ATM para atrasar ou descartar células - pequenos pacotes de dados de tamanho fixo - que chegavam a uma taxa maior do que um limite especificado.
O GCRA rastreia o limite restante usando o chamado Tempo Teórico de Chegada (TAT) de cada solicitação:
tat = current_time + period
e limita a próxima solicitação se o tempo de chegada for menor que o TAT atual. Isso funciona bem se a frequência for 1 solicitação / período, quando as solicitações são divididas em períodos. Mas, na realidade, a frequência geralmente é calculada como um limite / período. Por exemplo, se a frequência é de 10 solicitações / 60 segundos, o usuário pode fazer 10 solicitações nos primeiros 6 segundos. E com uma frequência de 1 solicitação / 6 segundos, ele terá que aguardar 6 segundos entre as solicitações.
Para poder enviar um grupo de solicitações em um curto período e manter a limitação de seu número por um período com um limite> 1, cada solicitação deve ser dividida pela relação período / limite, e então o próximo tempo teórico de chegada (
new_tat) será calculado de forma diferente. Vamos denotar a hora de chegada da solicitação como t:
new_tat = tat + period / limitse as solicitações são agrupadas (t <= tat)new_tat = t + period / limitse as solicitações não forem agrupadas (t > tat)
Conseqüentemente:
new_tat = max(tat, t) + period / limit
O pedido será limitado, se
new_tatmaior do que a soma do tempo atual e o período: new_tat > t + period. Quando new_tat = tat + period / limitchegarmos tat + period / limit > t + period. Portanto, você precisa restringir as consultas apenas quando tat - t > period - period / limit.
period — period / limit
<----------------------->
--|----------------------------|--->
t TAT
Nesse caso, não precisamos atualizar o TAT, pois as solicitações limitadas não têm tempo de chegada teórico.
Agora vamos construir a versão final do código!
from datetime import timedelta
from redis import Redis
def request_is_limited(r: Redis, key: str, limit: int, period: timedelta):
period_in_seconds = int(period.total_seconds())
t = r.time()[0]
separation = round(period_in_seconds / limit)
r.setnx(key, 0)
tat = max(int(r.get(key)), t)
if tat - t <= period_in_seconds - separation:
new_tat = max(tat, t) + separation
r.set(key, new_tat)
return False
return True
Usamos o Redis TIME porque o GCRA depende do tempo e precisamos nos certificar de que o horário atual seja consistente em várias implantações (discrepâncias de relógio entre máquinas diferentes podem levar a falsos positivos).
Este código demonstra o desempenho GCRA em 10 solicitações / 60 seg.
import redis
from datetime import timedelta
from ratelimit import gcra
r = redis.Redis(host='localhost', port=6379, db=0)
requests = 10
for i in range(requests):
if gcra.request_is_limited(r, 'admin', 10, timedelta(minutes=1)):
print ('Request is limited')
else:
print ('Request is allowed')
O algoritmo não limita as 10 primeiras solicitações, mas você terá que esperar pelo menos 6 segundos para fazer a próxima solicitação. Tente executar o script após algum tempo e altere o valor do limite e do período (por exemplo,
limit = 1e period=timedelta(seconds=6)).
Para manter a implementação limpa, não adicionei um bloqueio entre o recebimento e o envio de chamadas. Mas é necessário para várias solicitações com a mesma chave e ao mesmo tempo. Com Lua, você pode adicionar bloqueio como um gerenciador de contexto.
def request_is_limited(r: Redis, key: str, limit: int, period: timedelta):
period_in_seconds = int(period.total_seconds())
t = r.time()[0]
separation = round(period_in_seconds / limit)
r.setnx(key, 0)
try:
with r.lock('lock:' + key, blocking_timeout=5) as lock:
tat = max(int(r.get(key)), t)
if tat - t <= period_in_seconds - separation:
new_tat = max(tat, t) + separation
r.set(key, new_tat)
return False
return True
except LockError:
return True
O código completo está no GitHub .