bloom

Documentation

Index

• Variables
• func Add(f *Filter, key, salt []byte)
• func Contains(c Checker, key, salt []byte) bool
• func EstimateCount(numHashes, numEntries int, falsePositiveProbability float64) int
• func Hash(key, salt []byte) uint64
• func OptimalEntries(count int, falsePositiveProbability float64) int
• func OptimalHashes(numEntries, count int) int
• func OptimalParameters(count int, falsePositiveProbability float64) (int, int)
• type Checker
• type Filter
  • func New(numHashes, numEntries int) (*Filter, error)
  • func (f *Filter) Add(hash uint64)
  • func (f *Filter) Contains(hash uint64) bool
  • func (f *Filter) Count() int
  • func (f *Filter) Marshal() []byte
• type Metrics
  • func NewMetrics(namespace string, registerer prometheus.Registerer) (*Metrics, error)
  • func (m *Metrics) Reset(newFilter *Filter, maxCount int)
• type ReadFilter
  • func Parse(bytes []byte) (*ReadFilter, error)
  • func (f *ReadFilter) Contains(hash uint64) bool
  • func (f *ReadFilter) Marshal() []byte

Variables

var (
	EmptyFilter = &ReadFilter{
		hashSeeds: make([]uint64, minHashes),
		entries:   make([]byte, minEntries),
	}
	FullFilter = &ReadFilter{
		hashSeeds: make([]uint64, minHashes),
		entries:   make([]byte, minEntries),
	}
)

Functions

func Add

func Add(f *Filter, key, salt []byte)

func Contains

func Contains(c Checker, key, salt []byte) bool

func EstimateCount

func EstimateCount(numHashes, numEntries int, falsePositiveProbability float64) int

EstimateCount estimates the number of additions a bloom filter with [numHashes] and [numEntries] must have to reach [falsePositiveProbability]. This is derived by inversing a lower-bound on the probability of false positives. For values where numBits >> numHashes, the predicted probability is fairly accurate.

It is guaranteed to return a value in the range [0, MaxInt].

ref: https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=903775

func Hash

func Hash(key, salt []byte) uint64

func OptimalEntries

func OptimalEntries(count int, falsePositiveProbability float64) int

OptimalEntries calculates the optimal number of entries to use when creating a new Bloom filter when targenting a size of [count] with [falsePositiveProbability] assuming that the optimal number of hashes is used.

It is guaranteed to return a value in the range [minEntries, MaxInt].

ref: https://en.wikipedia.org/wiki/Bloom_filter

func OptimalHashes

func OptimalHashes(numEntries, count int) int

OptimalHashes calculates the number of hashes which will minimize the false positive probability of a bloom filter with [numEntries] after [count] additions.

It is guaranteed to return a value in the range [minHashes, maxHashes].

ref: https://en.wikipedia.org/wiki/Bloom_filter

func OptimalParameters

func OptimalParameters(count int, falsePositiveProbability float64) (int, int)

OptimalParameters calculates the optimal [numHashes] and [numEntries] that should be allocated for a bloom filter which will contain [count] and target [falsePositiveProbability].

Types

type Checker

type Checker interface {
	Contains(hash uint64) bool
}

type Filter

type Filter struct {
	// contains filtered or unexported fields
}

func New

func New(numHashes, numEntries int) (*Filter, error)

New creates a new Filter with the specified number of hashes and bytes for entries. The returned bloom filter is safe for concurrent usage.

func (*Filter) Add

func (f *Filter) Add(hash uint64)

func (*Filter) Contains

func (f *Filter) Contains(hash uint64) bool

func (*Filter) Count

func (f *Filter) Count() int

Count returns the number of elements that have been added to the bloom filter.

func (*Filter) Marshal

func (f *Filter) Marshal() []byte

type Metrics

type Metrics struct {
	Count      prometheus.Gauge
	NumHashes  prometheus.Gauge
	NumEntries prometheus.Gauge
	MaxCount   prometheus.Gauge
	ResetCount prometheus.Counter
}

Metrics is a collection of commonly useful metrics when using a long-lived bloom filter.

func NewMetrics

func NewMetrics(
	namespace string,
	registerer prometheus.Registerer,
) (*Metrics, error)

func (*Metrics) Reset

func (m *Metrics) Reset(newFilter *Filter, maxCount int)

Reset the metrics to align with the provided bloom filter and max count.

type ReadFilter

type ReadFilter struct {
	// contains filtered or unexported fields
}

func Parse

func Parse(bytes []byte) (*ReadFilter, error)

Parse bytes into a read-only bloom filter.

func (*ReadFilter) Contains

func (f *ReadFilter) Contains(hash uint64) bool

func (*ReadFilter) Marshal

func (f *ReadFilter) Marshal() []byte