Documentation
¶
Overview ¶
This package contains implementation for checking if an item has been seen previously. This is different from a bloom-filter as it prioritizes false-negatives (return absence even if the object was seen previously), instead of false-positives. A Bloom filter prioritizes false-positives (return presence even if the object was not seen previously) and thus is able to provide a high compression. This is similar to a cache, with the difference being that it does not store a value and can use other optimized representations to compress the keys and optimize for storage. The simplest implementation for the fastcheck.Filter is an LRU cache the package provides alternative implementations and is inspired by the code in https://github.com/jmhodges/opposite_of_a_bloom_filter/ and the related blog https://www.somethingsimilar.com/2012/05/21/the-opposite-of-a-bloom-filter/
the fastcheck.OppoBloomFilter provides two methods instead of one, a contains and an add. This makes it possible to check and then optionally add the value. It is possible that two threads may race and add it multiple times
Index ¶
Constants ¶
This section is empty.
Variables ¶
var ErrSizeTooLarge = errors.New("oppobloom: size given too large to round to a power of 2")
var ErrSizeTooSmall = errors.New("oppobloom: filter cannot have a zero or negative size")
var MaxFilterSize = 1 << 30
Functions ¶
This section is empty.
Types ¶
type Filter ¶
type Filter interface {
// Contains returns a True if the id was previously seen or false otherwise
// It may return a false, even if a item may have previously occurred.
Contains(ctx context.Context, id []byte) bool
// Adds the element id to the Filter and returns if a previous object was evicted in the process
Add(ctx context.Context, id []byte) (evicted bool)
}
type LRUCacheFilter ¶
type LRUCacheFilter struct {
// contains filtered or unexported fields
}
Implements the fastcheck.Filter interface using an underlying LRUCache from cache.Cache the underlying lru cache implementation is thread-safe
func NewLRUCacheFilter ¶
func NewLRUCacheFilter(size int, scope promutils.Scope) (*LRUCacheFilter, error)
Create a new fastcheck.Filter using an LRU cache of type cache.Cache with a fixed size
type Metrics ¶
type Metrics struct {
// Indicates if the item was found in the cache
Hit prometheus.Counter
// Indicates if the item was not found in the cache
Miss prometheus.Counter
}
Every implementation of the Filter Interface provides these metrics
type OppoBloomFilter ¶
type OppoBloomFilter struct {
// contains filtered or unexported fields
}
Implementation of the oppoFilter proposed in https://github.com/jmhodges/opposite_of_a_bloom_filter/ and the related blog https://www.somethingsimilar.com/2012/05/21/the-opposite-of-a-bloom-filter/
func NewOppoBloomFilter ¶
func NewOppoBloomFilter(size int, scope promutils.Scope) (*OppoBloomFilter, error)
NewOppoBloomFilter creates a new Opposite of Bloom filter proposed in https://github.com/jmhodges/opposite_of_a_bloom_filter/ and the related blog https://www.somethingsimilar.com/2012/05/21/the-opposite-of-a-bloom-filter/
Source Files
Directories