NAME

LinkedList::Single::Example::SlidingWindow - events in a time window held in a linked list

SYNOPSIS

use LinkedList::Single::Example::SlidingWindow;

my $window = LinkedList::Single::Example::SlidingWindow->new( span => 60 );

$window->record( $now, $request );

# returns the number of events dropped; the handler sees each
# one as it goes.

my $dropped = $window->expire( $now, sub( $time, @payload ) { ... } );

DESCRIPTION

A window holds the events of the last span time units, oldest first. record adds an event (a time and any payload) at the end. expire drops every event older than $now - span, passes each one to the handler, oldest first, and returns how many went. size and contents (an arrayref of [ $time, @payload ], oldest first) look at the window without changing it. Times must be recorded in order.

The events are kept in a LinkedList::Single. A cursor parked at the end of the list makes record a constant-time step that never walks the list. expire cuts the expired events off the front as one Fragment (a piece of list that nothing else can reach), puts the live events back, and consumes the Fragment, so each expired node and its payload are freed as the handler finishes with it.

LinkedList::Single::Example::SlidingWindow::Array keeps the same window in a perl array with splice, behind the same interface. It is the test oracle: the tests drive both with the same random events and compare the contents, the counts and the handler calls after every step. app/30-SlidingWindow/sliding-window uses the window as a login throttle.

How it is benchmarked

benchmarks/30-SlidingWindow/compare records 100,000 events into a window of 1,000, expiring after every event and after every 100 events, and reports the best of three runs in seconds. It then records a burst of 200,000 events, expires all but 10, and reports the bytes each container still holds, along with statements, branches and index operations counted in each expire.

Why it matters

A rate limiter or a login throttle runs on every request, and its window grows and shrinks with the traffic. Here the array is more than ten times faster in steady state, and the list gives the memory of a burst back as it expires (1,056 bytes left against 1,754,784) and destroys each expired payload at once. So the list is a choice for bursty windows, or when expired events hold something that must be released promptly, and not for speed. The measurements, the background and the references are in LinkedList::Single::Example::SlidingWindow::POD.

This is an example, not a rate limiter for production use: it has no locking, no persistence and no per-key windows.

SEE ALSO

LinkedList::Single::Example::SlidingWindow::POD, LinkedList::Single::Example::SlidingWindow::Array, LinkedList::Single