Come implementare rate limiting utilizzando Redis

Question

Io uso INCR e EXPIRE per implementare limitazione della velocità (per l'esempio di seguito, consentire solo 5 richieste al mintui):

if EXISTS counter 
    count = INCR counter 
else 
    EXPIRE counter 60 
    count = INCR counter 

if count > 5 
    print "Exceeded the limit"  

Ma c'è un problema che un popolo può inviare 5 richieste all'ultimo secondo al minuto e altre 5 richieste al primo secondo al minuto successivo, in altre parole 10 richieste in due secondi.

C'è un modo migliore per evitare il problema?

---

Aggiornamento: Mi è venuta un'idea proprio ora: utilizzare un elenco per implementarlo.

times = LLEN counter 
if times < 5 
    LPUSH counter now() 
else 
    time = LINDEX counter -1 
    if now() - time < 60 
     print "Exceeded the limit" 
    else 
     LPUSH counter now() 
LTRIM counter 5 

È un buon modo?

Answer 1

È possibile passare da "5 richieste nell'ultimo minuto" a "5 richieste nel minuto x". Da questo sarebbe possibile fare:

counter = current_time # for example 15:03 
count = INCR counter 
EXPIRE counter 60 # just to make sure redis doesn't store it forever 

if count > 5 
    print "Exceeded the limit" 

Se si desidera continuare a utilizzare "5 richieste negli ultimi minuti", allora si potrebbe fare

counter = Time.now.to_i # this is Ruby and it returns the number of milliseconds since 1/1/1970 
key = "counter:" + counter 
INCR key 
EXPIRE key 60 

number_of_requests = KEYS "counter"*" 
if number_of_requests > 5 
    print "Exceeded the limit" 

Se hai vincoli di produzione (in termini di prestazioni), è not advised utilizzare la parola chiave KEYS. Potremmo usare set invece:

counter = Time.now.to_i # this is Ruby and it returns the number of milliseconds since 1/1/1970 
set = "my_set" 
SADD set counter 1 

members = SMEMBERS set 

# remove all set members which are older than 1 minute 
members {|member| SREM member if member[key] < (Time.now.to_i - 60000) } 

if (SMEMBERS set).size > 5 
    print "Exceeded the limit" 

questo è tutto pseudo codice Ruby, ma dovrebbe dare l'idea.

Answer 2

vostro aggiornamento è un algoritmo molto bello, anche se un paio fatta di cambiamenti:

times = LLEN counter 
if times < 5 
    LPUSH counter now() 
else 
    time = LINDEX counter -1 
    if now() - time <= 60 
     print "Exceeded the limit" 
    else 
     LPUSH counter now() 
     RPOP counter 

Answer 3

Ecco un approccio alternativo. Se l'obiettivo è di limitare il numero di richieste a X richieste per Y secondi con il timer che inizia quando viene ricevuta la prima richiesta, è possibile creare 2 chiavi per ciascun utente che si desidera tracciare: una per il tempo che la prima richiesta è stato ricevuto e un altro per il numero di richieste fatte.

key = "123" 
key_count = "ct:#{key}" 
key_timestamp = "ts:#{key}" 

if (not redis[key_timestamp].nil?) && (not redis[key_count].nil?) && (redis[key_count].to_i > 3) 
    puts "limit reached" 
else 
    if redis[key_timestamp].nil? 
     redis.multi do 
      redis.set(key_count, 1) 
      redis.set(key_timestamp, 1) 
      redis.expire(key_timestamp,30) 
     end 
    else 
     redis.incr(key_count) 
    end 
    puts redis[key_count].to_s + " : " + redis[key_timestamp].to_s + " : " + redis.ttl(key_timestamp).to_s 
end 

Answer 4

Questa è una vecchia domanda a cui è già stata data una risposta, ma ecco un'implementazione che ho preso prendendo ispirazione da qui. Sto usando ioredis per Node.js

Ecco il limitatore di tempo rolling-finestra in tutta la sua asincrono ancora gara-condizione-free (spero) la gloria:

var Ioredis = require('ioredis'); 
var redis = new Ioredis(); 

// Rolling window rate limiter 
// 
// key is a unique identifier for the process or function call being limited 
// exp is the expiry in milliseconds 
// maxnum is the number of function calls allowed before expiry 
var redis_limiter_rolling = function(key, maxnum, exp, next) { 
    redis.multi([ 
    ['incr', 'limiter:num:' + key], 
    ['time'] 
    ]).exec(function(err, results) { 
    if (err) { 
     next(err); 
    } else { 
     // unique incremented list number for this key 
     var listnum = results[0][1]; 
     // current time 
     var tcur = (parseInt(results[1][1][0], 10) * 1000) + Math.floor(parseInt(results[1][1][1], 10)/1000); 
     // absolute time of expiry 
     var texpiry = tcur - exp; 
     // get number of transacation in the last expiry time 
     var listkey = 'limiter:list:' + key; 
     redis.multi([ 
     ['zadd', listkey, tcur.toString(), listnum], 
     ['zremrangebyscore', listkey, '-inf', texpiry.toString()], 
     ['zcard', listkey] 
     ]).exec(function(err, results) { 
     if (err) { 
      next(err); 
     } else { 
      // num is the number of calls in the last expiry time window 
      var num = parseInt(results[2][1], 10); 
      if (num <= maxnum) { 
      // does not reach limit 
      next(null, false, num, exp); 
      } else { 
      // limit surpassed 
      next(null, true, num, exp); 
      } 
     } 
     }); 
    } 
    }); 
}; 

e qui è una sorta di limitatore di velocità lockout-style:

// Lockout window rate limiter 
// 
// key is a unique identifier for the process or function call being limited 
// exp is the expiry in milliseconds 
// maxnum is the number of function calls allowed within expiry time 
var util_limiter_lockout = function(key, maxnum, exp, next) { 
    // lockout rate limiter 
    var idkey = 'limiter:lock:' + key; 
    redis.incr(idkey, function(err, result) { 
    if (err) { 
     next(err); 
    } else { 
     if (result <= maxnum) { 
     // still within number of allowable calls 
     // - reset expiry and allow next function call 
     redis.expire(idkey, exp, function(err) { 
      if (err) { 
      next(err); 
      } else { 
      next(null, false, result); 
      } 
     }); 
     } else { 
     // too many calls, user must wait for expiry of idkey 
     next(null, true, result); 
     } 
    } 
    }); 
}; 

Here's a gist of the functions. Fammi sapere se vedi eventuali problemi.

Answer 5

Il modo canonico per limitare la velocità è tramite il numero Leaky bucket algorithm. Lo svantaggio di utilizzare un contatore è che un utente può eseguire una serie di richieste subito dopo il reset del contatore, ovvero 5 azioni nel primo secondo del minuto successivo per il tuo caso. L'algoritmo Leaky bucket risolve questo problema.In breve, puoi utilizzare set ordinati per memorizzare il tuo "contenitore che perde", utilizzando i timestamp di azione come chiavi per riempirlo.

Leggi questo articolo per l'esatta applicazione: Better Rate Limiting With Redis Sorted Sets

Answer 6

ho provato con la lista, scadono e PTTL

Se TPS 5 al secondo, quindi
il throughput = 5
RampUp = 1000 (1000ms = 1sec)
intervallo = 200 ms

local counter = KEYS[1] 
local throughput = tonumber(ARGV[1]) 
local rampUp = tonumber(ARGV[2]) 
local interval = rampUp/throughput 
local times = redis.call('LLEN', counter) 

if times == 0 then 
    redis.call('LPUSH', counter, rampUp) 
    redis.call('PEXPIRE', counter, rampUp) 
    return true 
elseif times < throughput then 
    local lastElemTTL = tonumber(redis.call('LINDEX', counter, 0)) 
    local currentTTL = redis.call('PTTL', counter) 
    if (lastElemTTL-currentTTL) < interval then 
     return false 
    else 
     redis.call('LPUSH', counter, currentTTL) 
     return true 
    end 
else 
    return false 
end 

Più Più semplice versione:

local tpsKey = KEYS[1] 
local throughput = tonumber(ARGV[1]) 
local rampUp = tonumber(ARGV[2]) 
-- Minimum interval to accept the next request. 
local interval = rampUp/throughput 
local currentTime = redis.call('PTTL', tpsKey) 

-- -2 if the key does not exist, so set an year expiry 
if currentTime == -2 then 
    currentTime = 31536000000 - interval 
    redis.call('SET', tpsKey, 31536000000, "PX", currentTime) 
end 

local previousTime = redis.call('GET', tpsKey) 

if (previousTime - currentTime) >= interval then 
     redis.call('SET', tpsKey, currentTime, "PX", currentTime) 
     return true 
else 
     redis.call('ECHO',"0. ERR - MAX PERMIT REACHED IN THIS INTERVAL") 
     return false 
end