Approach: use a Redis-backed token-bucket per user with an atomic Lua script that refills tokens based on elapsed time and decrements on request. Store for each user: last_ts and tokens. Use TTLs to let inactive users expire. For very hot users, use binning or sharding to avoid single-key contention.Lua script (atomic, runs server-side):lua
-- KEYS[1] = user_key
-- ARGV[1] = now_ms
-- ARGV[2] = refill_rate_per_ms
-- ARGV[3] = capacity
-- ARGV[4] = tokens_requested
-- returns {allowed(1/0), tokens_left}
local key = KEYS[1]
local now = tonumber(ARGV[1])
local rate = tonumber(ARGV[2])
local cap = tonumber(ARGV[3])
local req = tonumber(ARGV[4])
local data = redis.call("HMGET", key, "tokens", "last_ts")
local tokens = tonumber(data[1]) or cap
local last = tonumber(data[2]) or now
local delta = math.max(0, now - last)
local add = delta * rate
tokens = math.min(cap, tokens + add)
if tokens >= req then
tokens = tokens - req
redis.call("HMSET", key, "tokens", tokens, "last_ts", now)
redis.call("PEXPIRE", key, 3600000) -- 1 hour TTL
return {1, tokens}
else
redis.call("HMSET", key, "tokens", tokens, "last_ts", now)
redis.call("PEXPIRE", key, 3600000)
return {0, tokens}
end
