Ho fatto questo, quindi so come è fatto in modo ottimale. L'idea è di utilizzare una funzione di hash come SipHash per calcolare un valore hash per l'indirizzo IP. Quindi utilizzi un algoritmo token bucket per ciascun bucket hash: ad es. 100 gettoni iniziali in ciascun secchio hash, aggiungi 10 token al secondo fino a un massimo di 100 token e rimuovi un token ogni volta che ricevi una richiesta, altrimenti, se non ci sono token, rifiuta la richiesta. Ciò consentirebbe 10 richieste al secondo con una dimensione massima di burst di 100.
In teoria, è possibile che due hash degli indirizzi IP siano sullo stesso bucket, ma in questo caso d'uso non è un problema, se hai abbastanza bucket hash.
Per quanto riguarda l'aggiornamento dei bucket, puoi eseguirli utilizzando i timer batch. Per esempio. per i bucket 131072, è possibile aggiornare ad es. 4096 secchi per ogni timer e quindi hanno 32 timer che scadono in modo uniforme in un secondo. Quindi, a 1/32 secondi, aggiorni i primi 4096 bucket, a 2/32 secondi, aggiorni i successivi 4096 bucket, ecc. La struttura dati per il mantenimento dei timer è in modo ottimale a coda priorità come un heap binario .
Se implementato in questo modo, se qualcuno inonda il tuo sistema da numerosi indirizzi IP di origine contraffatti, la tua memoria non viene riempita.
La memoria utilizzata da questo approccio utilizza 8, 16 o 32 bit per ciascun hash bucket se si utilizza un array intero. La dimensione intera deriva dalle tue esigenze: ad es. 8 bit non supportano più delle dimensioni burst di 255. Analogamente, 16 bit consentono dimensioni di burst di massimo 65535. Pertanto, ad es. 8 bit o 1 byte per bucket e 131072 bucket impiegano 128 kilobyte di memoria. In nessun posto vicino a essere un problema. Una buona macchina ha almeno 2 GB di memoria, il che significa oltre 15.000 volte la quantità richiesta per questo sistema.
È necessario considerare anche la larghezza di banda della memoria: se ogni bucket viene aggiornato una volta al secondo, la larghezza di banda richiesta è 128 KB / s. I computer di qualità supportano oltre 5 GB / s di larghezza di banda in lettura e scrittura o oltre 40.000 volte ciò che questa mia proposta utilizza.
Salva la cache nella RAM. Non utilizzare un database o un file su disco per questo. Se il sistema si arresta in modo anomalo, allora basta inizializzare tutti i bucket sul valore iniziale.