Как реализовать ограничение скорости использования Redis

Ответ 1

Вы можете переключиться с "5 запросов в последнюю минуту" на "5 запросов в минуту x". Благодаря этому можно было бы сделать:

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"

Если вы хотите продолжать использовать "5 запросов в последнюю минуту", вы можете сделать

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"

Если у вас есть производственные ограничения (особенно производительность), не рекомендуется использовать ключевое слово KEYS. Вместо этого мы могли бы использовать наборы:

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"

Это все псевдо-Ruby-код, но должен дать вам эту идею.

Ответ 2

Это старый вопрос, на который уже был дан ответ, но вот реализация, которую я действительно вдохновляла здесь. Я использую ioredis для Node.js

Вот ограничитель времени прокатки во всей его асинхронной, но без расовой (надеюсь) славе:

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

и вот вид ограничителя скорости в локаторе:

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

Вот суть функций. Дайте мне знать, если вы видите какие-либо проблемы.

Ответ 3

Канонический способ ограничения скорости - использование алгоритма Leaky Bucket. Недостатком использования счетчика является то, что пользователь может выполнить несколько запросов сразу после сброса счетчика, то есть 5 действий в первую секунду следующей минуты для вашего случая. Алгоритм Leaky Bucket решает эту проблему. Вкратце, вы можете использовать упорядоченные наборы для хранения вашего "утечки", используя метки времени действия в качестве ключей для его заполнения.

Прочитайте эту статью для точной реализации: лучшее ограничение скорости с помощью Redis Sorted Sets

ОБНОВИТЬ:

Существует также другой алгоритм, который имеет некоторые преимущества по сравнению с утечкой. Он называется общим алгоритмом сотовой скорости. Вот как это работает на более высоком уровне, как описано в Ограничение скорости, Ячейки и GCRA:

GCRA работает, отслеживая оставшийся лимит в течение времени, называемого "теоретическим временем прибытия" (TAT), которое определяется по первому запросу путем добавления продолжительности, представляющей его стоимость, к текущему времени. Стоимость рассчитывается как множитель нашего "интервала выбросов" (T), который получается из скорости, с которой мы хотим, чтобы корзина пополнялась. Когда поступает любой последующий запрос, мы берем существующий TAT, вычитаем из него фиксированный буфер, представляющий предельную общую мощность пакета (τ + T), и сравниваем результат с текущим временем. Этот результат представляет следующий раз, чтобы разрешить запрос. Если это в прошлом, мы разрешаем входящий запрос, а если это в будущем, мы не делаем. После успешного запроса новый TAT рассчитывается путем добавления T.

Существует модуль Redis, который реализует этот алгоритм, доступный на GitHub: https://github.com/brandur/redis-cell

Ответ 4

Примечание. Следующий код является примером реализации на Java.

private final String 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;
}

Ответ 5

Ваше обновление - очень хороший алгоритм, хотя я сделал пару изменений:

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

Ответ 6

Вот моя leaky bucket реализация ограничения скорости, используя Redis Lists.

Примечание. Следующий код является примером реализации в php, вы можете реализовать его на своем родном языке.

$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.

Ответ 7

Подобно другому ответу Java, но будет меньше туда и обратно в Redis:

    @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) {
        Long value = hashOperations.increment(key, COUNT, 1l);
        if (value == 1) {
            stringRedisTemplate.expire(key, timeout, timeUnit);
        }
        return value > limit;
    }

Ответ 8

Вот альтернативный подход. Если целью является ограничение количества запросов на X-запросы на Y секунд с таймером, начинающимся с первого приема, тогда вы можете создать 2 ключа для каждого пользователя, который вы хотите отслеживать: один на время, когда первый запрос был получен, а другой - за количество выполненных запросов.

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

Ответ 9

Я попытался использовать LIST, EXPIRE и PTTL

Если tps равно 5 в секунду, то
    пропускная способность = 5
    rampup = 1000 (1000 мс = 1сек)
    интервал = 200 мс

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

Более простая версия:

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