Documentation
¶
Overview ¶
Package bloom is a Bloom filter implementation of monoid.Monoid[[]byte], suitable for approximate set-membership aggregations.
Backed by github.com/bits-and-blooms/bloom/v3. Combine is bitwise-OR of the two underlying bit arrays. All sketches in a pipeline must share the same (m, k) parameters — a bitwise-OR of two differently-sized bit arrays is not defined, so Combine refuses to merge mismatched shapes: it returns the left operand and reports the mismatch through WithDecodeErrorHandler.
Identity is the empty byte slice, deliberately not a marshaled empty filter. The marshaled form carries (m, k), so an Identity that had a shape was only an identity for filters of its own shape: a pipeline whose monoid was built with NewWithCapacity but whose value extractor called the default-sized Single merged every event into a shape mismatch, and the row stayed the empty filter forever.
Because every filter carries its own (m, k), the shape a monoid was CONSTRUCTED with never reaches the merge. NewWithCapacity's parameters are therefore a declaration rather than a constraint, and Combine reports operands that do not match it — see WithDecodeErrorHandler. Without that report the parameters would be decorative, which is exactly what they had become.
Default parameters: 1M bits, k=7 hash functions, ~1% false-positive rate at ~100K inserts. Use NewWithCapacity for custom sizing.
Index ¶
- Constants
- func Bloom(opts ...Option) monoid.Monoid[[]byte]
- func Contains(sketch, element []byte) bool
- func Equal(a, b []byte) bool
- func Inspect(sketch []byte) (capacity uint64, hashes uint32, approxSize uint64, err error)
- func NewSingle(n uint, p float64, element []byte) []byte
- func NewWithCapacity(n uint, p float64, opts ...Option) monoid.Monoid[[]byte]
- func Single(element []byte) []byte
- type Option
Constants ¶
const ( DefaultCapacity = 100_000 DefaultFPR = 0.01 )
Default capacity and FPR. Yields ~10K-bit filter at p=0.01, k=7.
Variables ¶
This section is empty.
Functions ¶
func Bloom ¶
Bloom returns a Bloom-filter monoid with default parameters. To track a different expected cardinality / FPR, use NewWithCapacity.
func Contains ¶
Contains reports whether element is (probably) in the marshaled filter. Returns false on decode error.
func Equal ¶
Equal reports whether two marshaled filters have identical bits and shape. Used in tests for determinism checks.
func Inspect ¶
Inspect returns the (capacity m, hash count k, approximate number of inserted elements) triple from a marshaled filter. Used by the admin server to render a human-readable view of an opaque sketch in the Query Console.
"Approximate size" comes from the bits-and-blooms library's estimator — derived from the bit-fill ratio against (m, k); accurate within a few percent at typical fill levels, less reliable as the filter approaches saturation.
func NewSingle ¶
NewSingle returns a marshaled Bloom filter sized for (n, p) and pre-populated with the given element. The pipeline's value extractor uses this to lift a per-event element into a one-element sketch suitable for monoidal merge.
func NewWithCapacity ¶
NewWithCapacity returns a Bloom-filter monoid that DECLARES the shape (n, p) implies: every sketch it merges must have been built with the same parameters, which in practice means the pipeline's value extractor calls NewSingle with the same (n, p) this call got.
The monoid never builds a filter itself — Identity is the empty slice and Combine reads (m, k) off the wire — so these parameters cannot force a shape on anything. What they do is make disagreement detectable: Combine reports, through WithDecodeErrorHandler, any pair of operands whose shape is not the declared one. That is the only signal a caller gets that NewWithCapacity(1_000, 0.01) is quietly aggregating DefaultCapacity filters produced by a Single() the extractor forgot to size.
Types ¶
type Option ¶ added in v0.2.0
type Option func(*bloomMonoid)
Option configures the Bloom monoid.
func WithDecodeErrorHandler ¶ added in v0.2.0
WithDecodeErrorHandler installs a callback invoked when Combine cannot decode one of its operands, or when the two operands have incompatible (m, k) shapes.
Combine returns no error — the contract is Combine(a, b) V — so the only recovery on a decode failure is to return the operand that DID decode, silently discarding the other. That recovery is deliberate; doing it silently is not. For Bloom the silent case is especially easy to hit: every sketch merged must share the (m, k) shape, so a single caller constructing the monoid with different capacity parameters produces filters that cannot be OR'd together — and without this hook, membership answers just quietly go wrong.
The shape mismatch is the case this hook's doc always claimed to cover and never did: (m, k) is written into the marshaled form and read back out of it, so mismatched filters both decode fine and the merge was abandoned with no error at all.
Three distinct conditions reach this hook:
- an operand that will not decode — the other operand is kept;
- two operands whose (m, k) differ, which cannot be OR'd — the left operand is kept;
- two operands that agree with each other but not with the (n, p) this monoid was constructed for. That merge is sound and is performed; the report is what keeps NewWithCapacity's parameters from being decorative.
The handler must be cheap and non-blocking; it runs on the merge path, and the third condition fires on every merge for as long as the pipeline is misconfigured — count it, do not log it unsampled.
Source Files