A lock-free Bloom filter on :atomics.
Answers "have I seen this key?" with no false negatives and a configurable
false positive rate, in fixed memory. Bits are set with compare-and-swap,
so put/2 can tell whether it was the first to add a key, which makes the
filter usable as a replay guard.
Summary
Functions
Hashes key for put_hash/2 and member_hash?/2, so that a key looked up
in several filters is hashed once.
Like hash/1, hashing key only once: the second hash is derived from the
first, which halves the cost for large keys.
Whether key may have been added. false is certain.
Memory used by the bits, in bytes.
Creates a filter for capacity keys at the given false positive rate.
Adds key. Returns true if the key was not already present.
Clears the filter. Not atomic with respect to concurrent updates.
Types
@opaque hash()
@type t() :: %Limen.Sketch.Bloom{ bits: pos_integer(), hashes: pos_integer(), ref: :atomics.atomics_ref() }
Functions
Hashes key for put_hash/2 and member_hash?/2, so that a key looked up
in several filters is hashed once.
Like hash/1, hashing key only once: the second hash is derived from the
first, which halves the cost for large keys.
Keys whose first hashes collide then share every bit, which adds a false
positive rate of about n / 2^32 for n keys: negligible for a filter at
1% or more, too much for a replay guard at one in a million.
Whether key may have been added. false is certain.
@spec memory(t()) :: non_neg_integer()
Memory used by the bits, in bytes.
@spec new(pos_integer(), float()) :: t()
Creates a filter for capacity keys at the given false positive rate.
Adds key. Returns true if the key was not already present.
When several processes add the same key concurrently, at least one of them
gets true; in the common uncontended case exactly one does.
@spec reset(t()) :: :ok
Clears the filter. Not atomic with respect to concurrent updates.