Sum-based sliding rate limiting with Redis and Lua

Question

As I'm new to Redis, I would like to get a review / improvement suggestions from Redis / Lua experts on the following problem and the solution I have found so far.

Problem

The context is: an e-commerce system used by multiple users purchasing various items at different prices. Because of regulation, user purchases must be capped to a certain amount during a certain sliding period.

For example, no more than 10€ can be spent by a purchasing user during a sliding window of 1 week.

The problem to solve is: using StackExchange.Redis (Redis client .NET library) and Redis v3, implement a sliding window rate limiting mechanism, based not on max count of requests (many solutions for this particular problem can be found on web), but on a total sum of purchases done during a sliding period.

Solution design

A single purchase is represented by a purchase ID. It is stored as a string data type with the associated purchase amount (2.5 in the example below). Because we don't need to keep it forever, we'll expire it after 1 week (604800 seconds).

SETEX purchaseid:98db31bf9b 604800 2.5

Users and their corresponding purchases are represented by a sorted list where the key is the user ID, scores are numbers of seconds since 1970 (Epoch time), and values are purchase IDs. Likewise, the expiration is one week (renewed with each new purchase):

ZADD userid:[email protected] 1443719939 purchaseid:98db31bf9b
EXPIRE userid:[email protected] 604800

Fig1.: Data model (example)

Because several Redis calls might be required to implement this, I used a pre-loaded Lua script (using EVALSHA) in order to execute several Redis commands in one shot, so to avoid race conditions and to reduce network exchanges (please correct me if I'm wrong here).

Every time a user tries to purchase something, this script is called by the client application, and returns 1 if the purchase is accepted and registered, 0 otherwise.

However, I'm not sure how this approach will work in the context of a Redis Cluster. Will the data created through the Lua script be auto-partitioned over multiple masters? If yes, will the Lua script be able to read it back?

Solution code (Lua)

--[[
Initialization: StackExchange.Redis library allows passing
named parameters tagged with @
--]]
local userKey = 'userid:' .. @curUserId 
local curPurchaseKey = 'purchaseid:' .. @curPurchaseId
local sum = 0
--[[
Cleaning up old entries up to @minSecond (in our example,
minSecond = Now (Epoch time in secs) - 604800 (nb of secs in a week)):
--]]
redis.call('ZREMRANGEBYSCORE', userKey, '-inf', @minSecond) 

--[[
Getting the list of purchases done by user since @minSecond,
summing them up, returning 0 (failed) if @maxAmount is reached (e.g., 10€):
--]]
local pastEntries = redis.call('ZRANGEBYSCORE', userKey, @minSecond, '+inf') 
for i = 1, #pastEntries, 1 do
    local purchaseKey = pastEntries[i]
    local amount = tonumber(redis.call('GET', purchaseKey) or 0) 
    sum = sum + amount
end

if sum >= tonumber(@maxAmount) then
    return 0
end

--[[
Saving the current purchase ID + amount (e.g., 2.5€),
updating the sorted list of the user's purchases,
returning 1 (success):
--]]
redis.call('SETEX', curPurchaseKey, @expInSec, @curAmount)
redis.call('ZADD', userKey, @curSecond, curPurchaseKey)
redis.call('EXPIRE', userKey, @expInSec)
return 1

Answer 1

There might be one correctness issue here:

If a customer makes just one purchase all week with the transaction amount exceeding the cap, do you still want to throttle the transaction? Just wanted to bring that up in case you missed this corner case.

Since you talk about performance, you will want to consider which of the two are important to you:

• request latency - each request completing within a fixed time
• throughput - number of requests served from the cache in a time period.

You can have higher latency, but still maintain a high throughput as long as the transactions are not serialized.

One suggestion I had that might help with both is that you can pull the following:

--[[
Cleaning up old entries up to @minSecond (in our example,
minSecond = Now (Epoch time in secs) - 604800 (nb of secs in a week)):
--]]
redis.call('ZREMRANGEBYSCORE', userKey, '-inf', @minSecond) 

outside into a separate call or issue it lazily.

Lazy techniques can be:

• GC once every 'N' calls,
• run GC as a cron / batch job once a day for all customers
• Do GC only if the size of the sorted set is greater than a fixed threshold

This will make individual transactions potentially faster at the expense of a larger memory footprint.

This might have some performance implication, so I would do some benchmarking just for that one call.

If you're okay with being slightly inaccurate about the cap on spending per customer, there are two things you can potentially play with:

1. Use Exponential Moving Averages. This will allow you to not do a range query on the sorted set, and instead do a constant time query. There's plenty of resources on this topic on the inter-webs.

2. Use daily aggregates. Whenever you get a query, you will need to look-up exactly 7 key-value pairs. Ofcourse this will not work if you want precision.

Otherwise, your existing approach will get the job done.

Answer 2

Disclaimer: I don't know sqat about Lua or Redis.

I have just one small thing to point out. You return 0 for failure and 1 for success. Lua seems to have boolean type, so why not return false and true, respectively?

I hope somebody else will give you a more insightful review!