view release on metacpan or  search on metacpan

README  view on Meta::CPAN

    where consumers open it read-only and query it with no locking at all.

        # producer: build, freeze, ship the file
        my $z = Data::SortedSet::Shared->new("/tmp/leaderboard.sset", 1_000_000);
        $z->add_many(\@rows);
        $z->freeze;                  # seal: now immutable, and $z itself is read-only
        # ... copy /tmp/leaderboard.sset to another host ...

        # consumer (any process, same architecture): read-only, lock-free
        my $ro  = Data::SortedSet::Shared->new_readonly("/tmp/leaderboard.sset");
        my @top = $ro->rev_range_by_rank(0, 9);
        my $r   = $ro->rank($member);

    "freeze" takes the write lock, marks the set permanently immutable (there
    is no unfreeze -- rebuild the file to change it), and flushes the seal to
    disk. A frozen set rejects every mutator ("add", "incr", "remove",
    "add_many", "pop_min", "pop_max", "clear") with a croak, and a read-write
    reopen ("new($path, ...)" or new_from_fd($fd)) of a sealed file is refused
    -- so a shipped artifact can never be silently mutated out from under its
    readers. The order-statistics B+tree (subtree counts, leaf links, and
    separators) is maintained on every write, so nothing has to be built or
    completed at freeze time.

    new_readonly($path) maps the file "O_RDONLY" / "PROT_READ" and requires it
    to be frozen (it croaks on a file that was never "freeze"d). Because a
    sealed set's tree, leaf links, subtree counts and member index are all
    immutable, every read -- "score", "exists", "rank", "rev_rank", "at_rank",
    "count", "count_in_score", "range_by_rank", "range_by_score", "peek_*",
    "each", "stats" -- reads them directly, taking no reader lock. The mapping
    is never written (a range or iteration walks with a process-local cursor
    and returns its results in a private buffer), so a read-only view works
    from a read-only file descriptor or a read-only filesystem, and any number
    of processes can share one "PROT_READ" mapping. "frozen" reports whether
    the file is sealed and "readonly" whether this handle is a read-only view;
    "stats" gains matching "frozen" and "readonly" flags. "sync" is a no-op on
    a read-only view.

    Portability. The on-disk format is native binary (native-endian 64-bit
    words), so a frozen file may be copied only between machines of the same
    architecture; a wrong-endian file is rejected at open by the magic check.
    Copy the file to each consumer -- do not share one file over a network
    filesystem: the lock is a Linux futex (process-local to one kernel), and
    the "no live writer" contract that makes the lock-free reads safe assumes
    a static copy. Linux-only; 64-bit Perl.

SHARING ACROSS PROCESSES
    The set lives in a shared mapping, so several processes operate on the
    same data with no serialization layer in between. There are three ways to
    share it:

    *   A backing file -- every process calls "new($path, $max)" on the same
        path. The first to arrive creates and sizes the file (serialized by an
        exclusive lock); the rest map it.

    *   An anonymous mapping inherited across "fork" -- create with
        "new(undef, $max)" before forking; the parent and its children then
        share the one mapping.

    *   A memfd -- create with "new_memfd($name, $max)" and hand its "memfd"
        descriptor to an unrelated process (over a UNIX socket with
        "SCM_RIGHTS", or while the creator is alive via "/proc/$pid/fd/$n"),
        which reopens it with new_from_fd($fd).

        # children populate a fork-shared set; the parent reads the result
        my $z = Data::SortedSet::Shared->new(undef, 1_000_000);
        for my $k (1 .. 4) {
            unless (fork) {                                  # child
                $z->add($k * 1_000_000 + $_, rand) for 1 .. 1000;
                exit;
            }
        }
        1 while wait != -1;                                  # reap children
        print $z->count, "\n";                               # 4000

    Every operation is serialized by the rwlock, so concurrent writers do not
    corrupt the tree. A writer can wake readers blocked in other processes
    through the eventfd interface: it calls "notify" after a batch, and a
    reader selects on "fileno" then drains the count with "eventfd_consume".

COMPLEXITY
    "score"/"exists"/"peek_*" are O(1); "add"/"remove"/"incr"/"rank"/
    "at_rank"/"pop_*" and locating a range bound are O(log n); a range or
    iteration of "k" members is O(log n + k), scanning sequentially through
    the linked leaves.

STATS
    stats() returns a hashref with keys: "count", "max_entries", "height"
    (B+tree height), "node_capacity", "nodes_used", "index_slots",
    "index_load" (occupied fraction of the member index), "ops" (running count
    of write-path calls, whether or not they changed the set), "mmap_size"
    (bytes), "frozen" (1 if the set has been sealed by "freeze"), and
    "readonly" (1 if this handle is a read-only view -- see "FROZEN
    (READ-ONLY) MODE").

SECURITY
    Backing files are created with mode 0600 (owner-only) by default, so only
    the creating user can open and attach them. To share a backing file across
    users, pass an explicit octal file mode such as 0660 as the last argument
    to "new"; the mode is applied when the file is created, and when a file
    left behind by an interrupted create is re-initialized (see "CRASH
    SAFETY"); a file already in use keeps its own permissions. The file is
    opened with "O_NOFOLLOW", so a symlink planted at the path is refused, and
    created with "O_EXCL"; the on-disk header is validated when the file is
    attached. Any process you grant write access to a shared mapping is
    trusted not to corrupt its contents while other processes are using it.

CRASH SAFETY
    The write lock is a futex-based rwlock with PID-encoded ownership; if a
    writer dies while holding it, the next writer detects the dead owner and
    recovers. Reader slots are reclaimed similarly. Recovery restores locking
    only, never tree consistency: a writer killed mid-mutation (a node split,
    underflow, or insert) can leave the B+tree structurally corrupt.
    Limitation: PID reuse is not detected, which is very unlikely in practice
    but cannot be ruled out.

    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