[BENCHMARK] Up to 1,100% faster than ratelimit.js

[bradennapier]

👍

Rough Specification

As someone with obviously a ton of experience with rate limiting, would be happy to hear your thoughts on the abstraction (if you have the time, of course).

I've been doing really extensive testing for load-testing etc on it and hope to put this into production where it would def be tested against some serious load!

More tests and examples of implementation (including the aggregated result) are in the specification above.

tl;dr

Just want to say thank you! as this provides a huge performance improvement over what is pretty much the only other established method I have found ON TOP OF actually implementing GCRA rather than a simple "how many requests were made in the last n seconds.

Stress Test Results

Calls Setup, Starting Requests
Running Tests for:  cell
[ 'user', '1', 'trade' ]
[ 'user', '2', 'trade' ]
[ 'user', '3', 'trade' ]
[ 'user', '4', 'trade' ]
[ 'user', '5', 'trade' ]
[ 'user', '6', 'trade' ]
[ 'user', '7', 'trade' ]
Running Tests for:  rl
[ '1', 60, 'user:1:trade' ]
[ '2', 60, 'user:2:trade' ]
[ '3', 60, 'user:3:trade' ]
[ '4', 60, 'user:4:trade' ]
[ '5', 60, 'user:5:trade' ]
[ '6', 60, 'user:6:trade' ]
[ '7', 60, 'user:7:trade' ]

    --- Test Results ---

    Total Iterations: 5000 * 7 Tests (35,000 iterations each)

    rl:
      Total Duration: 343693971.74181193
      Average: 9819.82776405177
      Max: 14198.909738004208
      Min: 5541.352702006698

    cell:
      Total Duration: 26785993.573875546
      Average: 765.3141021107299
      Max: 1454.7679300010204
      Min: 322.44201999902725

    Diff: cell is 1183% faster

Quick Test Results (consistent against around 500 runs of the test)

// RUN FOR CELL ONLY (Dont Require rl or include in scope at all)
Calls Setup, Starting Requests
Running Tests for:  cell
[ 'user', '1', 'trade' ]
[ 'user', '2', 'trade' ]
[ 'user', '3', 'trade' ]
[ 'user', '4', 'trade' ]
[ 'user', '5', 'trade' ]
[ 'user', '6', 'trade' ]
[ 'user', '7', 'trade' ]

    --- Test Results ---

    Total Iterations: 10 * 7 Tests (70 iterations each)

    cell:
      Total Duration: 231.97511593997478
      Average: 3.3139302277139255
      Max: 4.6971050053834915
      Min: 2.4761980026960373

// RUN FOR RL ONLY (Dont Require cell or include in scope at all)
Calls Setup, Starting Requests
Running Tests for:  rl
[ '1', 60, 'user:1:trade' ]
[ '2', 60, 'user:2:trade' ]
[ '3', 60, 'user:3:trade' ]
[ '4', 60, 'user:4:trade' ]
[ '5', 60, 'user:5:trade' ]
[ '6', 60, 'user:6:trade' ]
[ '7', 60, 'user:7:trade' ]

    --- Test Results ---

    Total Iterations: 10 * 7 Tests (70 iterations each)

    rl:
      Total Duration: 2249.6415529847145
      Average: 32.13773647121021
      Max: 36.03293499350548
      Min: 28.242240011692047

Implementation / Benchmark

So this is definitely not even a fair benchmark considering the module runs as a native module and I implemented lua logic to handle the situation - but my goal was to implement a multi-bucket rate limiter using this as a base.

Team is super spooked by the "note on stability" part though and wants to go with RateLimit.js anyway which is completely client side :-\

Essentially I take a limits.yaml and use it to build a rate limiting bucket:

schema:
  # user:
  user:
    children:
      # if no others match
      "*":
        # limits against user:${username}
        limits:
          - 15
          - 30
          - 60
        children:
          # limits against user:${username}:trade
          trade:
            limits:
              - 5
              - 10
              - 15

Then I receive a "bucket key" which is an array of arguments ("user", "myuserid", "trade") and run against each step when limits is found, returning the results so that we can easily and efficiently implement multi-tiered rate limits against user actions with as few requests as possible.

So essentially when I call ("user", "myuserid", "trade") it is running

CL.THROTTLE user:myuserid 15 30 60
CL.THROTTLE user:myuserid:trade 5 10 15

--[[
  Summary:
    Takes the generated lua limits table (from limits.yaml which must be compiled 
    whenever we need to change it) and iterates the request, returning the results
    of all matching rate limits in the requested path.
]]
local LimitsSchema = {
  ["user"] = {
    ["children"] = {["*"] = {["limits"] = {15, 30, 60}, ["children"] = {["trade"] = {["limits"] = {5, 10, 15}}}}}
  }
}

local Response, LimitsTable, CurrentPath = {}, {}, {}
local Complete = 1
local child

local CheckLimit = function(bucket, args)
  return redis.call("CL.THROTTLE", bucket, unpack(args))
end

for k, v in ipairs(KEYS) do
  if LimitsSchema[v] then
    child = LimitsSchema[v]
  elseif LimitsSchema["*"] then
    child = LimitsSchema["*"]
  else
    Complete = 0
    break
  end

  table.insert(CurrentPath, v)

  if child["limits"] then
    LimitsTable[table.concat(CurrentPath, ":")] = child["limits"]
  end
  LimitsSchema = child["children"]
end

for k, v in pairs(LimitsTable) do
  table.insert(Response, CheckLimit(k, v))
end

if Complete == 0 then
  return redis.error_reply("Invalid Path at: " .. table.concat(CurrentPath, ":"))
end

return Response

Lua Performance: In an initial check with the lua performance when running the benchmark, looks like the latency of the request being made averaged at around 0.50 milliseconds per call... pretty awesome!

Then utilizing ioredis to handle the script

// static setup that shouldnt count towards perf since it is
// done one time per server instance
const Redis = require("ioredis");
const fs = require("fs");
const path = require("path");
const redis = new Redis();

const cmd = {
  lua: fs.readFileSync(
    path.resolve(__dirname, "..", "lua", "traverse.lua")
  )
};

redis.defineCommand("limiter", cmd);

module.exports = redis;

const { performance } = require("perf_hooks");
const redis = require("./cell-setup");

function checkPath(...path) {
  return redis.limiter(path.length, ...path);
}

async function request(...args) {
  const startTime = performance.now();
  await checkPath(...args);
  return performance.now() - startTime;
}

module.exports = {
  request
};

[brandur]

Very cool @bradennapier! Thanks for the detailed writeup.

Team is super spooked by the "note on stability" part though and wants to go with RateLimit.js anyway which is completely client side :-\

I put this note there mostly because I'm not actively using it myself. If I can get a few confirmed users that are using it regularly with good success, I'll remove it (I think some already are, but it's difficult to tell unless they're advertising themselves).

[bradennapier]

@brandur i can report that we have been successfully using this now in production and it has handled billions of requests without a hitch thus far! Thanks again!

We have provided a docker container that has redis-cell as well:

idexexchange/redis-cell

( assumes you have docker and redis-cli installed )

docker pull idexexchange/redis-cell
# maps to port 3802 from the default port - not necessary but good example
docker run -d -p 3802:6379 --name throttler idexexchange/redis-cell

redis-cli -p 3802

then...

CL.THROTTLE ... 

[brandur]

@bradennapier That's great!!

Thanks for remembering to report back in. As suggested above, I removed the note on unknown stability in the README. See 456f0b5.