hkeys - redis instructions

Cómo implementar la limitación de velocidad usando Redis

Question

Utilizo INCR y EXPIRE para implementar la limitación de velocidad (para el ejemplo a continuación, solo permito 5 solicitudes por minuto):

if EXISTS counter
count = INCR counter
else
EXPIRE counter 60
count = INCR counter
if count > 5
print "Exceeded the limit"

Pero existe el problema de que las personas pueden enviar 5 solicitudes en el último segundo en un minuto y otras 5 solicitudes en el primer segundo en el siguiente minuto, es decir, 10 solicitudes en dos segundos.

¿Hay alguna forma mejor de evitar el problema?

Actualización: se me ocurrió una idea en este momento: usar una lista para implementarla.

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

¿Es una buena manera?

Answer 1

Aquí está mi implementación de la limitación de velocidad, utilizando las Lists Redis.

Nota: el siguiente código es una implementación de ejemplo en php , puede implementarlo en su propio idioma.

$list = $redis->lRange($key, 0, -1); // get whole list
$noOfRequests = count($list);
if ($noOfRequests > 5) {
$expired = 0;
foreach ($list as $timestamp) {
if ((time() - $timestamp) > 60) { // Time difference more than 1 min == expired
$expired++;
}
}
if ($expired > 0) {
$redis->lTrim($key, $expired, -1); // Remove expired requests
if (($noOfRequests - $expired) > 5) { // If still no of requests greater than 5, means fresh limit exceeded.
die("Request limit exceeded");
}
} else { // No expired == all fresh.
die("Request limit exceeded");
}
}
$redis->rPush($key, time()); // Add this request as a genuine one to the list, and proceed.

Answer 2

Aquí hay un enfoque alternativo. Si el objetivo es limitar el número de solicitudes a X solicitudes por Y segundos con el temporizador comenzando cuando se recibe la primera solicitud, entonces puede crear 2 claves para cada usuario que desea rastrear: una para el momento en que la primera solicitud Se recibió y otro por el número de solicitudes realizadas.

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 3

Esta es una vieja pregunta que ya fue respondida, pero aquí hay una implementación que tomé un poco de inspiración de aquí. Estoy usando ioredis para Node.js

Aquí está el limitador de tiempo de la ventana móvil en toda su gloria asíncrona pero sin condiciones de carrera (espero):

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);
}
}
});
}
});
};

Y aquí hay un tipo de limitador de tasa de bloqueo:

// 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);
}
}
});
};

Aquí hay un resumen de las funciones . Déjame saber si ves algún problema.

Answer 4

He probado con LIST, EXPIRE y PTTL

Si tps es 5 por segundo, entonces
rendimiento = 5
rampup = 1000 (1000ms = 1sec)
intervalo = 200ms

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

Más versión más simple:

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

Answer 5

La forma canónica de realizar la limitación de velocidad es a través del algoritmo Leaky bucket . La desventaja de usar un contador, es que un usuario puede realizar una gran cantidad de solicitudes justo después de que se reinicie el contador, es decir, 5 acciones en el primer segundo del siguiente minuto para su caso. El algoritmo del cubo Leaky resuelve este problema. Brevemente, puede usar conjuntos ordenados para almacenar su "cubeta con fugas", usando sellos de tiempo de acción como claves para llenarlo.

Echa un vistazo a este artículo para conocer la implementación exacta: Mejor límite de velocidad con Redis conjuntos ordenados

ACTUALIZAR:

También hay otro algoritmo, que tiene algunas ventajas en comparación con el cubo con fugas. Se llama algoritmo genérico de velocidad celular . Así es como funciona en el nivel superior, como se describe en Limitación de velocidad, Celdas y GCRA :

GCRA funciona al rastrear el límite restante a través de un tiempo llamado "tiempo de llegada teórico" (TAT), que se agrega a la primera solicitud al agregar una duración que representa su costo a la hora actual. El costo se calcula como un multiplicador de nuestro "intervalo de emisión" (T), que se deriva de la tasa a la que queremos que se llene el cubo. Cuando llega una solicitud posterior, tomamos el TAT existente, le restamos un búfer fijo que representa la capacidad de ráfaga total del límite (τ + T) y comparamos el resultado con la hora actual. Este resultado representa la próxima vez para permitir una solicitud. Si está en el pasado, permitimos la solicitud entrante, y si está en el futuro, no lo hacemos. Después de una solicitud exitosa, se calcula un TAT nuevo agregando T.

Hay un módulo redis que implementa este algoritmo disponible en GitHub: https://github.com/brandur/redis-cell

Answer 6

Nota: El siguiente código es una implementación de ejemplo en Java. Cadena final privada COUNT = "count";

@Autowired
private StringRedisTemplate stringRedisTemplate;
private HashOperations hashOperations;
@PostConstruct
private void init() {
hashOperations = stringRedisTemplate.opsForHash();
}
@Override
public boolean isRequestAllowed(String key, long limit, long timeout, TimeUnit timeUnit) {
Boolean hasKey = stringRedisTemplate.hasKey(key);
if (hasKey) {
Long value = hashOperations.increment(key, COUNT, -1l);
return value > 0;
} else {
hashOperations.put(key, COUNT, String.valueOf(limit));
stringRedisTemplate.expire(key, timeout, timeUnit);
}
return true;
}

Answer 7

Puede cambiar de "5 solicitudes en el último minuto" a "5 solicitudes en el minuto x". Por esto sería posible hacer:

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"

Si desea seguir usando "5 solicitudes en el último minuto", entonces podría hacer

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"

Si tiene restricciones de producción (especialmente el rendimiento), no se recomienda utilizar la palabra clave KEYS . Podríamos usar conjuntos en su lugar:

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"

Todo esto es un código pseudo Ruby, pero debería darle una idea.

Answer 8

Su actualización es un algoritmo muy bueno, aunque hice algunos cambios:

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