Redis rate limiting in Lua

Question

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!)

Answer 1

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