README

A strict rate limiter with reasonable performance and memory usage.

Just like the sliding log algorithm, it guarantees "no more than X events per T time", but it doesn't store every single event. Instead, it splits the time window into N+1 counters (frames). This gives it predictable memory usage and performance. The trade-off is an extra delay of up to one frame when an event leaves the window.

Example:

We want to allow no more than 30 messages per 10 minutes.
We can create a window with 10 frames, 60 seconds each.
Internally, 11 frames will be created, and a message received right now will expire in [10..11] minutes.

The added delay shrinks as the frame count increases, but calculation complexity grows.

The library is written entirely in Lua as a set of Redis functions but wrapped in a Laravel package to simplify its usage. For languages other than PHP, you only need the throttling.lua file.

Features

ETA (retry after). Calculates it for every operation and any event count.
Parallelism. Primary operations are implemented as single functions, so they can be called safely from different jobs or machines.
Precision. The minimum possible window duration is frame count microseconds.
Small memory usage. Each gateway stores a binary string of 64 + 64 + frame_width * (frame_count + 1) bits.

Performance / complexity

Worst-case complexity is frame_count + 1 operations. Total event count in the time window is cached in the header, so when event_count >= limit - total_count, the check costs only a single operation plus E expired frames clearing (E equals the distance between the current time and the last check time in frames). Write operations and checks are usually fast, but when eta > now, using some client-side waiting mechanism is recommended.

Usage

Raw

async function trySend(message) {
	const frame_count = 10, frame_length = 60 * 10**6, frame_width = 5, limit = 30, event_count = 1;
	const { ticket_id, user_id } = message;
	const [taken, eta] = await redis.fCall('dwthrottler_try',
			[`throttling:${ticket_id}:${user_id}`],
			[frame_count, frame_length, frame_width, limit, event_count]);
	if(parseInt(taken) > 0)
		message.send();
	else
		setTimeout(() => trySend(message), Math.ceil(parseInt(eta) / 1000 - Date.now()));
}

PHP

$throttling = app()->make(\Ontec\Throttling\DiscreteWindow::class, [
	'connection' => \Illuminate\Support\Facades\Redis::connection('cache')
	'frame_count' => 10,
	'frame_length' => \Carbon\CarbonInterval::minute(),
	'frame_width' => 5,
]);
$this->throttler->relative_eta = true;

// ...

$r = $throttling->tryLog("throttling:{$ticket_id}:{$user_id}", 1, 30);
if($r->taken > 0)
	$message->send();
else
	$job->delay($r->eta);

Installation

Raw

cat throttling.lua | redis-cli -x FUNCTION LOAD REPLACE

Laravel

composer require ontec/discrete-window-throttling
php artisan vendor:publish --tag=redis-functions

$code = file_get_contents(resource_path('redis/functions/discrete_window_throttling.lua'));
\Illuminate\Support\Facades\Redis::function('LOAD', 'REPLACE', $code);

Docker

services:
  redis:
    image: redis:8.8-alpine
    command: redis-server --save '600 1'
    post_start:
      - command: sh -c 'until redis-cli info persistence | grep -q "^loading:0"; do sleep 5; done'
      - command: sh -c 'redis-cli -x FUNCTION LOAD REPLACE < /opt/redis_dwt.lua'
    #environment:
    #  REDISCLI_AUTH: ${REDIS_PASSWORD}
    volumes:
      - ./throttling.lua:/opt/redis_dwt.lua

Reference

Parameters

key. Redis key where all data related to the gateway is stored as a binary string.
frame_length^[1]. Duration of each frame in microseconds.
frame_count^[1]. Number of frames in the time window.
frame_width^[1]. Number of bits reserved for each frame counter.
limit. Maximum number of events allowed in the time window. It can vary freely between queries.
event_count. Number of events to store/request/get ETA for, depending on the function.

1. This parameter is related to binary data geometry. If you want to change it, you must wipe the key first. Otherwise, any kind of unpredictable errors are unavoidable.

Functions

FCALL dwthrottler_try 1 key frame_count frame_length frame_width limit event_count => { taken_count, eta }^[2]
Logs event_count events, or returns ETA as a timestamp in microseconds if they don't fit.
FCALL dwthrottler_fill 1 key frame_count frame_length frame_width limit event_count => { taken_count, eta }^[2]
Logs the largest fitting part of event_count and returns ETA for the rest.
FCALL dwthrottler_events 1 key frame_count frame_length frame_width event_count => { total_count, expired_count }
Only logs events; performs no limit checks and calculates no ETA. Returns the total event count in the window and the number of expired events (when possible, because the key itself has a TTL). It can be called with event_count = 0 to actualize gateway data or query the total.
FCALL_RO dwthrottler_eta 1 key frame_count frame_length frame_width limit event_count => eta^[1]
Only calculates ETA. It may work slower than dwthrottler_try because it doesn't refresh data and therefore can't use the cached total.
FCALL_RO dwthrottler_now 0 => timestamp^[1]
Returns the current timestamp from the Redis server in microseconds. Useful for synchronization and debugging.

1. Non-modifying functions. They don't increase the AOF file size and can be used safely on replicas.
2. Atomic functions. If event_count modification takes place, only these functions should be used to sustain parallelism safety.

Benchmarks (AMD Ryzen 7 H 255)

100K requests across 1K keys, 1K frames: 6K RPS 100K requests across 1K keys, 10 frames: 19K RPS

License

Apache 2.0. See LICENSE.

ontec / discrete-window-throttling

Package info

Security

Statistics