NAME Data::DDSketch::Shared - shared-memory DDSketch relative-error quantile sketch SYNOPSIS use Data::DDSketch::Shared; # 1% relative-error quantiles my $dd = Data::DDSketch::Shared->new(undef, 0.01); $dd->add($_) for @latencies; # feed values (e.g. request latencies) my $p50 = $dd->quantile(0.50); # median, within 1% of the true value my $p99 = $dd->quantile(0.99); # tail latency my $max = $dd->max; # exact min/max are tracked too # share the sketch across processes via a backing file my $shared = Data::DDSketch::Shared->new("/tmp/latency.dd", 0.01); DESCRIPTION A DDSketch in shared memory: it estimates any quantile of a stream of numbers to within a configured relative accuracy "alpha" (default 1%), in a fixed amount of memory, no matter how many values are added. Unlike a fixed histogram, the guarantee is relative: the returned value for any quantile is within a factor "alpha" of the true value, whether that quantile is a microsecond or an hour -- which is what you want for latencies and other long-tailed, wide-dynamic-range data. Each value "v" falls into a logarithmic bucket keyed by "ceil(log_gamma(|v|))", with "gamma = (1 + alpha) / (1 - alpha)"; every value in a bucket is within "alpha" of the bucket's representative value. Positive and negative magnitudes use separate bucket stores and exact zeros a dedicated counter, so the full real line is covered. The sketch also tracks the exact count, minimum, and maximum, plus a running sum, giving mean and true extremes for free. Because the buckets live in a shared mapping, several processes feed one sketch: 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 distribution. A write-preferring futex rwlock with dead-process recovery guards mutation. Linux-only. Requires 64-bit Perl. Memory is bounded at "num_buckets" counters per sign (default 2048): the buckets form a fixed window centred on value 1, and values whose magnitude falls outside the window collapse into the nearest extreme bucket. With the defaults the window spans roughly 1.5e-9 to 6.6e8, so ordinary data never reaches the edges; raise "num_buckets" for a wider exact range. Two sketches created with the same "alpha" and "num_buckets" can be merged. METHODS Constructors my $dd = Data::DDSketch::Shared->new($path, $alpha, $num_buckets, $mode); my $dd = Data::DDSketch::Shared->new(undef, 0.01); # anonymous, 2048 buckets my $dd = Data::DDSketch::Shared->new_memfd($name, $alpha, $num_buckets); my $dd = Data::DDSketch::Shared->new_from_fd($fd); $alpha is the relative accuracy (default 0.01 = 1%; between 1e-6 and 0.5). $num_buckets is the number of counters per sign (default 2048; between 8 and 2^24) and sets both the memory use ("2 * num_buckets * 8" bytes plus a fixed header) and the exact value range. "new" and "new_memfd" croak on an out-of-range $alpha or $num_buckets. 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 values my $n = $dd->add($value); # add one value; returns the new total count $dd->insert($value); # alias for add $dd->add_many(\@values); # add a batch under a single write lock $dd->clear; # empty the sketch "add" adds one finite number (croaks on "NaN" or infinity) and returns the running total count. "add_many" adds an array reference of numbers under one write lock, validating them all first. Negative values and zero are supported. Querying my $v = $dd->quantile($q); # value at quantile $q in 0 .. 1 (undef if empty) my $med = $dd->median; # quantile(0.5) $dd->min; $dd->max; # exact smallest / largest value (undef if empty) $dd->mean; # running mean (undef if empty) $dd->sum; $dd->count; # running sum and exact number of values $dd->zero_count; # how many exact-zero values were added "quantile" returns the estimated value at quantile $q (e.g. 0.99 for the 99th percentile), guaranteed within relative error "alpha" of the true value; it returns "undef" for an empty sketch and croaks if $q is outside "[0, 1]". "min", "max", and "count" are exact (tracked separately from the buckets); "sum" and "mean" are double-precision running values subject to floating-point rounding. Merging and introspection $dd->merge($other); # fold another sketch's values in (same alpha + num_buckets) $dd->alpha; $dd->gamma; $dd->num_buckets; $dd->stats; # { alpha, gamma, num_buckets, count, zero_count, sum, min, max, mean, ops, mmap_size } "merge" requires $other to have the same "alpha" and "num_buckets" and croaks otherwise; afterwards this sketch represents the combined distribution. Lifecycle $dd->path; $dd->memfd; $dd->sync; $dd->unlink; "sync" flushes the mapping to its backing store (a no-op for anonymous and memfd sketches); "unlink" removes the backing file (also callable as "Class->unlink($path)"); "path" returns the backing path ("undef" for anonymous, memfd, or fd-reopened sketches) and "memfd" the backing descriptor. ACCURACY For any quantile, the returned value "e" and the true value "v" satisfy "|e - v| <= alpha * |v|" -- a relative guarantee that holds across the whole range, so the 99.9th percentile of a heavy tail is as accurate (in relative terms) as the median. This is the property a fixed-bucket histogram lacks. The count, minimum, and maximum are exact; the sum and mean are double-precision running values subject to floating-point rounding. The only approximation is the per-quantile value, and only for magnitudes inside the representable window; magnitudes outside it collapse into the extreme bucket and lose accuracy. SHARING ACROSS PROCESSES The sketch 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 sketch, so a fleet of workers can each measure part of a workload into a single distribution. 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, but recovery restores locking only -- it performs no state repair. "add" commits the scalar aggregates (count, sum, min, max) before the bucket counter, so a crash in that window leaves "count" ahead of the buckets and quantile(1.0) can return "undef" on a non-empty sketch until the next "add" completes. 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::Histogram::Shared (fixed-bucket histogram), the DDSketch paper (Masson, Rim, Lee, 2019), 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.