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

Вы можете переключиться с «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, но он должен дать вам представление.

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

Ознакомьтесь с этой статьей, чтобы узнать о точной реализации: Лучшее ограничение скорости с Сортированные наборы Redis

ОБНОВЛЕНИЕ:

Есть еще один алгоритм, имеющий ряд преимуществ по сравнению с дырявым ведром. Это называется Generic Cell Rate Algorithm. Вот как это работает на более высоком уровне, как описано в Ограничение скорости, ячейки и GCRA:

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

На GitHub есть модуль redis, реализующий этот алгоритм: https://github.com/brandur/redis-cell

Это старый вопрос, на который уже был дан ответ, но вот реализация, на которую я вдохновился. Я использую 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);
      }
    }
  });
};

Вот суть функций. Сообщите мне, если возникнут проблемы.

Примечание. Следующий код является примером реализации на 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;
}

Вот моя leaky bucket реализация ограничения скорости с использованием Redis _ 2_.

Примечание. Следующий код является примером реализации в 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.

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

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

Подобно другому ответу 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;
    }

Вот альтернативный подход. Если цель состоит в том, чтобы ограничить количество запросов до 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

Это достаточно мало, чтобы вы могли избежать его хеширования.

local f,k,a,b f=redis.call k=KEYS[1] a=f('incrby',k,ARGV[1]) b=f('pttl',k) if b<0 then f('pexpire',k,ARGV[2]) end return a

Параметры:

KEYS[1] = имя ключа, может быть действие для ограничения скорости, например,
ARGV[1] = количество, которое нужно увеличить, обычно 1, но вы можете выполнять группировку через 10 или 100 миллисекундных интервалов на клиенте
ARGV[2] = window, в миллисекундах, для ограничения скорости в
Returns: новое увеличенное значение, которое затем можно сравнить со значением в вашем коде, чтобы узнать, не превышает ли оно ограничение скорости.

Для ttl не будет возвращено базовое значение с помощью этого метода, он будет продолжать скользить вниз, пока не истечет срок действия ключа, после чего он начнется с ARGV[2] ttl при следующем вызове.

Запросы в последнем интервале / скользящем окне

interval == Количество времени, в течение которого количество принятых запросов (пропускная способность)
throughput == количество запросов за интервал
RequestTimeList == Время каждого запроса, добавляемого в этот список

// Remove older request entries
while (!RequestTimeList.isEmpty() && (now() - RequestTimeList.get(0)) > interval) {

    RequestTimeList.remove(0)
}

if (RequestTimeList.length < throughput) {

    RequestTimeList.add(now())

} else {

    throw err;
}

Запросы в интервале / фиксированном окне

Я пробовал использовать LIST, EXPIRE и PTTL

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

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

другой способ со списком

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