fastcheck

package
v1.0.25 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Oct 9, 2023 License: Apache-2.0 Imports: 11 Imported by: 3

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

View Source
var ErrSizeTooLarge = errors.New("oppobloom: size given too large to round to a power of 2")
View Source
var ErrSizeTooSmall = errors.New("oppobloom: filter cannot have a zero or negative size")
View Source
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

func (LRUCacheFilter) Add

func (l LRUCacheFilter) Add(_ context.Context, id []byte) bool

func (LRUCacheFilter) Contains

func (l LRUCacheFilter) Contains(_ context.Context, id []byte) bool

Simply uses Contains from the LRUCacheFilter

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/

func (*OppoBloomFilter) Add

func (f *OppoBloomFilter) Add(_ context.Context, id []byte) bool

func (*OppoBloomFilter) Contains

func (f *OppoBloomFilter) Contains(_ context.Context, id []byte) bool

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL