NAME
    Data::TopK::Shared - shared-memory top-k heavy hitters (Space-Saving,
    optional time decay)

SYNOPSIS
        use Data::TopK::Shared;

        # track the 100 most frequent keys of a stream
        my $tk = Data::TopK::Shared->new(undef, 100);

        $tk->add($_) for @stream;           # feed keys one at a time

        for my $h (@{ [ $tk->top(10) ] }) { # the 10 heaviest, count-descending
            printf "%s: ~%d (+/- %d)\n", $h->{key}, $h->{count}, $h->{error};
        }

        my $est = $tk->estimate("popular"); # estimated count of one key (0 if untracked)

        # share the summary across processes via a backing file
        my $shared = Data::TopK::Shared->new("/tmp/hitters.tk", 100);

        # time-decayed: recent hits outweigh old ones (half-life 3600 time units)
        my $decayed = Data::TopK::Shared->new_decayed(undef, 100, 256, 3600);
        $decayed->add($key, $epoch_seconds);   # optional timestamp; else a per-add tick
        $decayed->top(10);                      # the heaviest *recent* hitters

DESCRIPTION
    A top-k heavy hitters summary in shared memory: with a fixed set of
    "capacity" counters it tracks the most frequent keys of a stream and
    estimates each one's frequency, using the Space-Saving algorithm, in
    memory that does not grow with the stream. This is the standard way to
    find the top talkers, hot URLs, busiest source IPs, or most-frequent
    search terms without storing a per-key counter for every distinct key
    seen.

    Feed keys with "add". While a counter is free a new key claims it; once
    all "capacity" counters are in use, a new key evicts the smallest
    counter and takes over its count as an over-estimate bound. Consequently
    each monitored key carries a "count" (an upper bound) and an "error"
    (the maximum over-estimate), so its true frequency lies in "[count -
    error, count]". Any key whose true frequency exceeds "total_observations
    / capacity" is guaranteed to be retained -- the genuine heavy hitters
    never fall out.

    Because the summary lives in a shared mapping, several processes feed
    one top-k: any process that opens the same backing file, inherits the
    anonymous mapping across "fork", or reopens a passed memfd contributes
    to and reads the same counters. A write-preferring futex rwlock with
    dead-process recovery guards mutation.

    Keys are handled by their byte content, truncated to "key_size" bytes
    (default 256): two keys sharing a "key_size"-byte prefix are counted as
    one. Wide-character strings (any codepoint above 255) cause a "Wide
    character" croak -- encode to bytes first. Linux-only. Requires 64-bit
    Perl.

  Time decay (recent hitters)
    A summary created with "new_decayed($path, $capacity, $key_size,
    $half_life)" keeps a time-decayed top-k: an observation's contribution
    halves every $half_life time units, so recent activity dominates and
    stale heavy hitters fade out. It uses forward decay (Efraimidis /
    Cormode): counts are stored as decayed weights so the Space-Saving
    min-heap stays consistent, with an occasional internal landmark rescale
    to keep the weights bounded (no unbounded growth). Feed it with
    "$tk->add($key, $timestamp)" -- $timestamp is any non-decreasing number
    in your own units (epoch seconds, milliseconds, an event index); if you
    omit it, time advances one tick per "add". A past (smaller) timestamp
    does not rewind the clock. "estimate", "error", and "top" then report
    decayed counts (floating point) as of the latest time seen; everything
    else -- eviction bounds, cross-process sharing, "clear" -- works the
    same. A plain (non-decayed) summary is unchanged and on-disk compatible.

METHODS
  Constructors
        my $tk = Data::TopK::Shared->new($path, $capacity, $key_size, $mode);
        my $tk = Data::TopK::Shared->new(undef, $capacity);            # anonymous, key_size 256
        my $tk = Data::TopK::Shared->new_memfd($name, $capacity, $key_size);
        my $tk = Data::TopK::Shared->new_from_fd($fd);

        # time-decayed (forward decay) -- extra half_life argument
        my $tk = Data::TopK::Shared->new_decayed($path, $capacity, $key_size, $half_life);
        my $tk = Data::TopK::Shared->new_decayed_memfd($name, $capacity, $key_size, $half_life);

    "new_decayed" / "new_decayed_memfd" take a final $half_life (a finite
    number greater than 0, in whatever time units you feed to "add"): a
    contribution's weight halves every $half_life units. They croak on a
    non-positive or non-finite half-life. $capacity is the number of
    counters (the maximum number of keys tracked at once, at least 1, up to
    2^24) -- pick it a few times larger than the number of heavy hitters you
    want to reliably capture. $key_size is the maximum bytes stored per key
    (default 256; longer keys are truncated). Memory is roughly "capacity *
    (40 + key_size)" bytes plus a fixed header. "new" and "new_memfd" croak
    on a capacity below 1 or above 2^24, or a $key_size outside 1..4096.
    When reopening an existing file or memfd the stored geometry wins and
    the caller's arguments are ignored. An optional file mode may be passed
    as the last argument to "new" (e.g. 0660) for cross-user sharing; it
    defaults to 0600 (owner-only).

  Feeding and querying
        my $count = $tk->add($key);           # observe one key; returns its new estimated count
        my $count = $tk->add($key, $t);       # decayed mode: observe at time $t (optional)
        $tk->observe($key);                   # alias for add
        my $n     = $tk->add_many(\@keys);    # observe a batch under one lock; returns the batch size
        my @top   = $tk->top($k);             # the $k heaviest as hashrefs, count-descending
        my @all   = $tk->top;                 # all tracked keys (k defaults to every counter)
        my $est   = $tk->estimate($key);      # estimated count of one key, 0 if untracked
        my $err   = $tk->error($key);         # the over-estimate bound for that key (0 if exact/untracked)
        $tk->clear;                           # forget everything (counters and totals reset)

    "add" observes one key and returns its estimated count after the
    observation. "add_many" feeds an array reference under a single write
    lock. "top" returns a list of hash references "{ key => $bytes, count =>
    $n, error => $e }" sorted by "count" descending (ties broken by tighter
    "error" first); with no argument, or an argument larger than the number
    tracked, it returns every tracked key. "estimate" returns the
    upper-bound count for a single key (0 if it is not currently tracked);
    "error" returns that key's over-estimate bound, so its true count lies
    in "[estimate - error, estimate]". To read a key's count and error as a
    consistent pair under one lock, use the hashref "top" returns for it.

  Introspection
        $tk->capacity;      # number of counters
        $tk->key_size;      # max bytes stored per key
        $tk->tracked;       # keys currently tracked: min(distinct seen, capacity)
        $tk->seen;          # total observations fed
        $tk->is_decayed;    # true for a time-decayed summary
        $tk->half_life;     # the decay half-life (0 for a plain summary)
        $tk->stats;         # { capacity, key_size, tracked, seen, ops, mmap_size, decayed[, half_life] }

    "is_decayed" reports whether the summary is time-decayed; "half_life"
    returns its half-life (0 for a plain summary). In decayed mode
    "estimate", "error", and the "count"/"error" fields of "top" are decayed
    counts (floating point) as of the latest observed time; "stats" gains
    "decayed" (and "half_life" when decayed).

  Lifecycle
        $tk->path; $tk->memfd; $tk->sync; $tk->unlink;

    "sync" flushes the mapping to its backing store (a no-op for anonymous
    and memfd summaries); "unlink" removes the backing file (also callable
    as "Class->unlink($path)"); "path" returns the backing path ("undef" for
    anonymous, memfd, or fd-reopened summaries) and "memfd" the backing
    descriptor.

ACCURACY
    Space-Saving gives one-sided guarantees. Every key's "count" is an upper
    bound on its true frequency, and its true frequency is at least "count -
    error". Any key whose true frequency exceeds "seen / capacity" is
    guaranteed to be among the tracked keys, so with "capacity" comfortably
    larger than the number of genuine heavy hitters, the top of the list is
    exact and only the long tail is approximate. Increasing "capacity"
    tightens the error on the marginal keys.

SHARING ACROSS PROCESSES
    The summary lives in a shared mapping, shared the same three ways as the
    rest of the family: a backing file, an anonymous mapping inherited
    across "fork", or a memfd passed to an unrelated process and reopened
    with new_from_fd($fd). Every process's "add" feeds the one shared
    summary, so a fleet of workers can each process part of a stream into a
    single top-k.

SECURITY
    Backing files are created with mode 0600 (owner-only) by default; pass
    an explicit octal mode (e.g. 0660) as the last argument to "new" for
    cross-user sharing. The file is opened with "O_NOFOLLOW" and "O_EXCL",
    and the header is validated on attach. Any process granted write access
    is trusted not to corrupt the mapping.

CRASH SAFETY
    Mutation is guarded by a futex-based write-preferring rwlock with
    PID-encoded ownership and dead-owner recovery. Each "add" is a short
    bounded update, so a crash leaves the summary consistent up to the last
    completed operation. Limitation: PID reuse is not detected (very
    unlikely in practice).

    Reader-slot exhaustion (slotless readers): dead-process recovery
    attributes a crashed lock holder's contribution through its reader-slot.
    The slot table holds 1024 entries (one per concurrent reader process).
    If more than that many reader processes share one mapping at once, a
    reader that cannot claim a slot proceeds "slotless" -- it still takes
    the read lock but leaves no per-process record. If such a slotless
    reader is then killed while holding the read lock, its share of the lock
    cannot be attributed to a dead process, so writer recovery cannot
    reclaim it and writers may block until the mapping is recreated.
    Reaching this needs more than 1024 concurrent reader processes on one
    mapping plus a crash in the brief read-lock window; the dead-process
    slot reclaim keeps the table from filling with stale entries, so in
    practice it is very unlikely.

SEE ALSO
    Data::CountMinSketch::Shared (per-key frequency estimation),
    Data::Reservoir::Shared (uniform sampling), and the rest of the
    "Data::*::Shared" family.

AUTHOR
    vividsnow

LICENSE
    This is free software; you can redistribute it and/or modify it under
    the same terms as Perl itself.