如何使用Redis实现速率限制

Question

我使用INCR和EXPIRE来实施速率限制，例如每分钟5个请求：

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

if count > 5
    print "Exceeded the limit"    

然而，可以在最后一分钟发送5个请求，在第二分钟的第一秒发送5个请求，即在两秒钟内发送10个请求。

如何避免这个问题？

更新：我提出了这个清单。这是一个好方法吗？

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

Answer 1

这是一个已经回答过的老问题，但是这里有一个实现，我从这里获得了一些灵感。我用ioredisode.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);
      }
    }
  });
};

这是功能的要点。如果你看到任何问题，请告诉我。

Answer 2

进行速率限制的标准方法是通过漏桶算法。使用计数器的缺点是，用户可以在计数器重置后立即执行一系列请求，即在下一分钟的第一秒钟内为您的案例执行5个操作。漏桶算法解决了这个问题。简单地说，您可以使用有序集合来存储“漏桶”，使用动作时间戳作为键来填充它。

查看这篇文章，了解确切的实现：使用Redis排序集实现更好的速率限制

更新：

还有另一种算法，与漏桶相比有一些优势。它被称为通用细胞率算法。以下是它在更高级别上的工作方式，如速率限制、单元格和GCRA中所述：

GCRA的工作原理是通过一个称为“理论到达时间”（TAT）的时间跟踪剩余限制，该时间通过在当前时间中添加一个代表其成本的持续时间来播种在第一个请求上。成本计算为“排放间隔”（T）的乘数，该乘数来自我们希望桶重新填充的速率。当任何后续请求进来时，我们取现有的TAT，从中减去代表极限总突发容量的固定缓冲区（τT），并将结果与当前时间进行比较。此结果表示下一次允许请求的时间。如果是在过去，我们允许传入请求，如果是在将来，我们不允许。成功请求后，通过添加T计算新的TAT。

GitHub上有一个实现此算法的redis模块：https://github.com/brandur/redis-cell

Answer 3

您可以从"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"

如果您有生产限制（特别是性能限制），建议不要使用键关键字。我们可以使用集合来代替：

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代码，但应该给你一个想法。