11
\$\begingroup\$

I've implemented a rate limiter for redis in Lua, and I'm wondering if anyone has any suggestions that might improve the performance.

An example use:

eval '[sha] mykey 1234567 60000 1000 1 10' 0

Which translates to:

  • Create a hash under key mykey
  • The current ms since the last epoch is 1234567
  • Limit over a period of 60s
  • Each bucket should be 1s
  • Increment by 1
  • The maximum number of increments for this limiter is 10

Refer to this and this for alternative implementations.

local key = KEYS[1]
local time_in_ms = tonumber(ARGV[1])
local span_ms = tonumber(ARGV[2])
local bucket_ms = tonumber(ARGV[3])
local incrby = tonumber(ARGV[4])
local throttle = tonumber(ARGV[5])

local current_bucket = math.floor((time_in_ms % span_ms) / bucket_ms)
local current_count = incrby

local last_bucket = tonumber(redis.call('HGET', key, 'L'))

local getting = {}
if nil == last_bucket then
    -- this is a new rate limit hash (perhaps the old one expired?)
    redis.call('HINCRBY', key, current_bucket, incrby)
    redis.call('PEXPIRE', key, span_ms)
    redis.call('HSET', key, 'L', current_bucket)
else
    local bucket_count = span_ms / bucket_ms

    -- clear unused buckets
    if last_bucket ~= current_bucket then
        local j = current_bucket
        while j ~= last_bucket do
            redis.call('HDEL', key, j)
            j = ((j - 1) % bucket_count)
        end
    end

    -- generate an array containing all of the possible fields
    local i = 0
    while i < bucket_count do
        local j = i + 1
        getting[j] = i
        i = j
    end

    -- get all of the available values at once
    local all = redis.call('HMGET', key, unpack(getting))
    for k, v in pairs(all) do
        current_count = current_count + (tonumber(v) or 0)
    end

    -- stop here if the throttle value will be surpassed on this request
    if throttle < current_count then
        return throttle
    end

    -- only set the 'current bucket' if we're actually incrementing it's value
    if last_bucket ~= current_bucket then
        redis.call('HSET', key, 'L', current_bucket)
    end

    redis.call('HINCRBY', key, current_bucket, incrby)
    redis.call('PEXPIRE', key, span_ms)
end

return current_count

Setup:

  • Calling this using booksleeve.
  • Running redis in a virtual box Ubuntu 12.04 server vm on the same machine.
  • The vm has 8gb mem, access to all cores of my computer.
  • My computer uses an i7 950 @ 3.07GHz.

I'm seeing approximately 4.4 async ops per ms, or 4,400 ops per second.

Revision 1

Darn, I actually lied. In my original code I was returning something like { current_count, ... }, but for the purposes of this post I just trimmed it down to return the value itself. (if you noticed, the variable getting is never used, and it was one of the items I was returning). I've actually adjusted my code to return only current_count, and the performance went way up! (I still think it could be faster). Here's the latest version of my code, which also makes a few other adjustments:

local key = KEYS[1]
local time_in_ms = tonumber(ARGV[1])
local span_ms = tonumber(ARGV[2])
local bucket_ms = tonumber(ARGV[3])
local incrby = tonumber(ARGV[4])
local throttle = tonumber(ARGV[5])

local current_bucket = math.floor((time_in_ms % span_ms) / bucket_ms)
local current_count = incrby

local last_bucket = tonumber(redis.call('HGET', key, 'L'))
local not_same = last_bucket ~= current_bucket

if nil ~= last_bucket then
    local bucket_count = span_ms / bucket_ms

    -- clear unused buckets
    if not_same then
        local j = current_bucket
        while j ~= last_bucket do
            redis.call('HDEL', key, j)
            j = ((j - 1) % bucket_count)
        end
    end

    -- generate an array containing all of the possible fields
    local getting = {}
    local bc = bucket_count + 1
    for i = 1, bc, 1 do
        getting[i] = i - 1
    end

    -- get all of the available values at once
    local all = redis.call('HMGET', key, unpack(getting))
    for k, v in pairs(all) do
        current_count = current_count + (tonumber(v) or 0)
    end

    -- stop here if the throttle value will be surpassed on this request
    if throttle < current_count then
        return (current_count - incrby)
    end
end

-- only set the 'current bucket' if we're actually incrementing it's value
if not_same then
    redis.call('HSET', key, 'L', current_bucket)
end

redis.call('HINCRBY', key, current_bucket, incrby)
redis.call('PEXPIRE', key, span_ms)

return current_count

With this revision, I'm now seeing approximately 10.2 async ops per ms, or 10,200 ops per second. (Even if I just return { current_count } - an array with a single element - I see only approximately 6.0 async ops per ms!)

\$\endgroup\$
3
\$\begingroup\$

I run the code in my laptop. I got 16594.76 requests per second.

Environment:

  • Ubuntu 15.10
  • Run Redis natively (no VM)
  • CPU: Intel(R) Core(TM) i7-2620M CPU @ 2.70GHz
  • Mem: 16GB

After some changes I got 17825.31 requests per second.

> local all = redis.call('HMGET', key, unpack(getting))
> for k, v in pairs(all) do
>    current_count = current_count + (tonumber(v) or 0)
> end

HMGET returns a non-sparse array. It's possible to iterate the array using ipairs, which is faster than pairs. I removed the explicit conversion to number, as Lua will automatically coerce the types if necessary. After the changes the loop looks like:

-- get all of the available values at once
local all = redis.call('HMGET', key, unpack(getting))
for _, v in ipairs(all) do
   current_count = current_count + (v or 0)
end

This is the biggest improvement. Then other minor things (which probably don't improve performance):

> local bc = bucket_count + 1
> for i = 1, bc, 1 do
>    getting[i] = i - 1
> end

1 increment is not necessary as it's the default; bc is only used once, can be replaced in the loop.

for i = 1, bucket_count + 1 do
   getting[i] = i - 1
end
> if nil ~= last_bucket then

Same as:

if last_bucket then
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.