view release on metacpan or  search on metacpan

lib/Data/SortedSet/Shared.pm  view on Meta::CPAN

per member in score order after the lock is released, so the callback may safely
call back into the set.

=head2 Introspection and lifecycle

    $z->count; $z->max_entries; $z->stats;     # see STATS
    $z->path; $z->memfd; $z->sync; $z->unlink;     # or Class->unlink($path)
    $z->eventfd; $z->fileno; $z->notify; $z->eventfd_consume;

C<sync> flushes the mapping to its backing store and C<unlink> removes the
backing file (also callable as C<< Class->unlink($path) >>).  C<path> returns the
backing file path (C<undef> for an anonymous or memfd-backed set) and C<memfd>
returns the descriptor of a C<new_memfd> set (-1 otherwise).  The eventfd methods
let another process wait for updates: C<eventfd> lazily creates an eventfd and
returns its descriptor (croaks on failure; calling it again returns the same fd),
C<fileno> returns the current eventfd descriptor or -1, C<notify> writes a wakeup
(returning false if no eventfd is attached), and C<eventfd_consume> reads and
resets the counter, returning it as an integer or C<undef> when nothing is
pending.

=head1 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:

=over 4

=item *

B<A backing file> -- every process calls C<< 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.

=item *

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

=item *

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

=back

    # 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 C<notify> after a batch, and a reader selects on
C<fileno> then drains the count with C<eventfd_consume>.

=head1 COMPLEXITY

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

=head1 STATS

C<stats()> returns a hashref with keys: C<count>, C<max_entries>, C<height>
(B+tree height), C<node_capacity>, C<nodes_used>, C<index_slots>, C<index_load>
(occupied fraction of the member index), C<ops> (running count of write-path
calls, whether or not they changed the set), and C<mmap_size> (bytes).

=head1 SECURITY

The mmap region is writable by all processes that open it.  Do not share backing
files with untrusted processes.

=head1 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.  B<Limitation>: PID reuse is not detected,
which is very unlikely in practice but cannot be ruled out.

=head1 SEE ALSO

L<Data::SortedSet::Shared::Strings> (string-keyed variant, bundled with this
distribution), L<Data::Intern::Shared>, L<Data::SpatialHash::Shared>,
L<Data::HashMap::Shared>, L<Data::Heap::Shared>, L<Data::Graph::Shared>, and the
rest of the C<Data::*::Shared> family.

=head1 AUTHOR

vividsnow

=head1 LICENSE

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

=cut