Improve rolling-window implementation for Redis adapter

[chowchow316]

Currently, the rolling-window is done via Sorted Set structure in Redis, and the timestamps of all coming requests during last window (expiration time) are kept in Redis, this maybe OK for short expiration (e.g., 1 second), but will lead to large memory consumption if the expiration is long (e.g., 1 hour). To reduce the memory usage, we may want to group the requests from last window into small buckets, and only keep the number of requests for each buckets. In this case, the memory usage will be reduced, as discussed in: https://medium.com/figma-design/an-alternative-approach-to-rate-limiting-f8a06cf7c94c

[mangchiandjjoe]

I started working on this. Instead of storing every single event, aggregate events for the shorter duration, named bucket.

bucket-rolling-window algorithm manages namespace + ".map" and namespace + ".set". Consumed token for the window, Consumed token for the bucket, Bucket creation time will be stored into the map record, namespace + ".map". Bucket history will be stored into the set record, namespace + ".set"

This is the pseudo code.

namespace		// quota namespace
credit	 		// credit allowed to the namespace
token			// requested token
timestamp		// in milliseconds or nanoseconds
window size		// quota window size
bucket window size	// bucket window size

// initialization
consumed token := hget(namespace + ".map", "token");
bucket token := hget(namespace + ".map", "bucket.token");
bucket timestamp := hget(namespace + ".map", "bucket.timestamp");

if not consumed token or not bucket token  or not bucket timestamp request then
  consumed token : = 0
  bucket token := 0
  bucket timestamp := timestamp

  hmset(namespace + ".map",
    "token", consumed token, 
    "bucket.token", bucket token,
    "bucket.timestamp", bucket timestamp);
end

// append bucket to the sorted-set
if timestamp - bucket timestamp > bucket window size then
  zadd(namespace + '.set', bucket timestamp, timestamp + "." + bucket token)

  bucket token := 0
  bucket timestamp := timestamp
  hmset(namespace + ".map", "bucket.token", 0, "bucket.timestamp", timestamp);
end

// reclaim expired tokens
reclaimed := 0
for expired_token : zrangebyscore(namespace + ".set", 0, timestamp - window size) then
  reclaimed += expired_token
end

zremrangebyscore(namespace + ".set", 0, timestamp - window size)

// update consumed token for positive reclaimed token
if reclaimed > 0 then
  consumed token -= reclaimed
  if consumed token < 0 then
    // error situation
    consumed token := 0
  end
  hset(namespace + ".map". "token", consumed token)
end

available token := credit - consumed token

if available token < 0 then
  return false;
else if  available token >= token
  hincby(namespace + ".map", "token", token);
  hincby(namespace + ".map", "bucket.token", token);
  return true
else
  if best effort == false then
    return false
  end

  hincby(namespace + ".map", "token", available token);
  hincby(namespace + ".map", "bucket.token", available token);
  return true
end

Since this logic touches multiple records based on the stored data, it requires transaction. LUA script and EVAL command guarantees atomic execution.