/ 
Shared-Arena-0.01
/ Shared::Arena::Bloom

NAME

Shared::Arena::Bloom - a shared set that answers "no" exactly and "yes" probably

VERSION

Version 0.01

SYNOPSIS

my $arena = Shared::Arena->create(size => 8 * 1024 * 1024);
my $seen  = $arena->bloom('seen', capacity => 1_000_000, fp_rate => 0.001);

# skip work already done, in any process
next if $seen->add($id);

# or ask without adding
do_expensive($id) unless $seen->check($id);

DESCRIPTION

A bit array and a handful of hash functions. Adding a key sets some bits; asking about a key tests them. If any bit is clear the key was definitely never added. If all are set it probably was, and the probability is a number you chose when you sized the filter.

It holds no keys, so it costs the same for a million short ones as for a million long ones, and a filter for a million items at one in a thousand is under two megabytes. That is what makes it worth sharing: every process asks the same question of the same bits without copying anything or taking a lock.

Get one from $arena->bloom($name). Every process can ask for the same name with the same arguments; the first creates it and the rest attach.

What it will not do

It cannot forget one key. Clearing a bit would clear it for every other key that happens to share it, turning a definite "no" into a wrong one. There is no delete, and there never will be. A filter only fills; when it is too full it is replaced.

It cannot count. estimated in the stats is arithmetic on how many bits are set, and it degrades as the filter saturates.

It cannot make a decision exactly once. add reports whether every bit was already set, which is nearly always the answer you want, but the bits are set one at a time: two processes adding the same key at the same instant can both be told it was new. For deduplicating work that is harmless, because the loser merely repeats something. For anything that must happen once, use a lock.

Sizing, and what happens past it

Ask for what you expect to hold and the rate you will accept:

my $b = $arena->bloom('seen', capacity => 1_000_000, fp_rate => 0.001);

The bits and the number of hashes follow from those two numbers, and asking for them directly is almost always a way of getting them wrong.

The rate you asked for is what you get at that capacity. Past it the rate climbs, and it climbs fast: a filter at twice its rating is not slightly worse, it is several times worse. Watch fill in the stats. At the rated capacity it sits near one half, and a filter approaching saturation is answering "probably" to almost everything, which is the same as answering nothing at all.

Rotating one

Because there is no delete, a long-running filter needs replacing rather than tidying. The usual arrangement is two filters and a switch:

my $current  = $arena->bloom('seen-a', capacity => 1_000_000);
my $previous = $arena->bloom('seen-b', capacity => 1_000_000);

# ask both, add to the current one only
my $known = $current->check($id) || $previous->check($id);
$current->add($id) unless $known;

# when the current one fills, reset the older and swap the two
if (($current->stats){fill} > 0.5) {
    $previous->reset;
    ($current, $previous) = ($previous, $current);
}

which keeps a full window of history at all times and never asks a saturated filter anything. Two filters are provided rather than one that rotates itself, because how much history to keep is a decision only the caller can make.

METHODS

add

my $already = $b->add($key);

Adds a key. Returns true when every bit was already set, meaning the key had probably been added before, and false when this call set at least one.

check

if ($b->check($key)) { ... }

False is exact: this key was never added. True is probable.

reset

$b->reset;

Forgets everything. Readers are not locked out, so a check running at the same moment may see the filter half cleared and answer either way for a key being forgotten, which is what it would have answered a moment either side.

stats

my %s = $b->stats;
# bits, hashes, set, added, seen, estimated, capacity, fill

added counts calls that set something, seen counts calls that found everything already set. fill is the fraction of bits set and is the number that says whether the filter is still delivering the rate it was sized for.

Counting the set bits walks the whole array, so this belongs on a status page rather than in a loop.

bits, hashes

my $m = $b->bits;
my $k = $b->hashes;

SEE ALSO

Shared::Arena, Shared::Arena::Map.

AUTHOR

LNATION, <email at lnation.org>

LICENSE AND COPYRIGHT

This software is Copyright (c) 2026 by LNATION.

This is free software, licensed under the Artistic License 2.0.