Time bucketed

Un primo approccio per limitare il numero delle richieste in un periodo (period) è quello di utilizzare un algoritmo a tempo (chiamato time-bucketed), in cui un contatore (inizialmente settato a limit) e un tempo di scadenza (period) sono salvati per ogni chiave (detta rate-key, contenente qualcosa di univoco come lo username o l’indirizzo IP) e vengono decrementati nelle richieste successive. 

Come vedremo nel codice più avanti, con Python e Redis possiamo implementare la logica del time-bucketed in questo modo:

• controllare se la rate-key (key esiste
• se key non esiste, inizializzarla al valore di limit (Redis SETNX) e un tempo di scadenza period (Redis EXPIRE)
• decrementare questo valore per ogni richiesta successiva (Redis DECRBY)
• la richiesta sarà limitata solo quando il valore del campo identificato da key scende sotto zero
• dopo il periodo (period) dato la chiave sarà automaticamente cancellata 

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

Puoi vedere questo snippet di codice in azione che simula delle richieste con un limite di 20 richieste / 30 secondi.

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')

Solo le prime 20 richieste non saranno limitate, poi sarà necessario aspettare 30 secondi prima di essere in grado di effettuare una nuova richiesta.

Lo svantaggio di questo approccio è che in realtà impone un limite al numero di richieste che un utente può fare entro un periodo piuttosto che un rate. Ciò significa che l'intera quota può essere esaurita immediatamente, azzerandosi solo allo scadere del periodo.

L’algoritmo Leaky bucket

C'è un algoritmo che può prendersi cura del rate limiting e produce un effetto di limitazione del rate molto regolare: l'approccio leaky-bucket. L'algoritmo funziona in modo simile a un vero e proprio secchio bucato che ha un buco dove perde il contenuto: si può versare acqua (paragonabile alle richieste che arrivano) nel secchio fino a una capacità massima mentre una certa quantità di acqua fuoriesce a un tasso costante (di solito implementato utilizzando un processo separato in background). Se la quantità di acqua che entra nel secchio è maggiore di quella che esce, il secchio inizia a riempirsi e quando il secchio sarà pieno le nuove richieste verranno limitate. Possiamo saltare questo algoritmo per un approccio più elegante che non richiede un processo separato per simulare una perdita: il Generic Cell Rate Algorithm.

L’algoritmo Generic Cell Rate

Il Generic Cell Rate Algorithm (GCRA) proviene da una tecnologia di comunicazione chiamata Asynchronous Transfer Mode (ATM) ed era usato negli scheduler della rete ATM per ritardare o eliminare piccoli pacchetti di dati di dimensioni fisse che arrivavano oltre il loro rate limit.

GCRA funziona tracciando il limite rimanente attraverso un tempo chiamato TAT (Theoretical Arrival Time) su ogni richiesta.

tat = current_time + period

e limitare la prossima richiesta se il tempo di arrivo è inferiore al TAT memorizzato. Questo funziona se rate = 1 request / period in cui ogni richiesta è separata da period, comunque nel mondo reale di solito abbiamo rate = limit / period. Per esempio con rate = 10 requests / 60 seconds un utente sarebbe autorizzato a fare 10 richieste nei primi 6 secondi, con rate = 1 request / 6 seconds l'utente dovrebbe aspettare 6 secondi tra le richieste.

Per poter raggruppare le richieste in un breve periodo di tempo e supportare le richieste limitate (limit) all'interno del periodo (period) con limit > 1, ogni richiesta dovrebbe essere separata per period / limit e il prossimo Theoretical Arrival Time (ATM)  (new_tat) calcolato in un modo diverso da prima. Indicando con t il tempo di arrivo della richiesta.

• new_tat = tat + period / limit  se le richieste si raggruppano (t <= tat)
• new_tat = t + period / limit se le richieste non si raggruppano (t > tat)

quindi

new_tat = max(tat, t) + period / limit

La richiesta è limitata se new_tat supera il tempo corrente più il periodo, new_tat > t + period. Con new_tat = tat + period / limit abbiamo

tat + period / limit > t + period

Quindi, dovremmo limitare le richieste solo quando

tat — t > period — period / limit

      period — period / limit

      <----------------------->

--|----------------------------|--->

  t                           TAT

In questo caso TAT non dovrebbe essere aggiornato, perché le richieste limitate non hanno un tempo di arrivo teorico.

Ora è il momento di svelare il codice finale!

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

In questa implementazione utilizziamo Redis TIME perché l’algoritmo GCRA dipende dal tempo ed è fondamentale assicurarsi che il tempo corrente sia coerente tra più implementazioni (la divergenza di ora tra le macchine potrebbe infatti portare a falsi positivi). Nel seguente script potete vedere GCRA in azione con rate = 10 requests / 60 seconds

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')

Le prime 10 richieste sono permesse dall’algoritmo GCRA, ma bisogna aspettare almeno 6 secondi per fare un'altra richiesta. Prova ad eseguire lo script dopo un po' di tempo per vedere come funziona e prova a cambiare limit e period ( per esempio limit=1 e period=timedelta(seconds=6) ).

Per mantenere chiara l'implementazione dell’algoritmo GCRA, abbiamo evitato di aggiungere un lock tra le chiamate get e set, ma risulta necessario in caso di richieste multiple con la stessa chiave allo stesso tempo. Usando Lua-based lock possiamo semplicemente aggiungere un lock context manager.

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