cuckoo

README

Cuckoo

Package cuckoo implements a cuckoo filter using the techniques described in https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf.

Cuckoo filters are space-efficient, probabalistic structures for set membership tests. Essentially, a Cuckoo filter behaves like a set, but the only query it supports is "is x a member of the set?", to which it can only respond "no" or "maybe".

This is useful for many purposes, but one use case is avoiding expensive lookups. A Cuckoo filter of the items contained in the store is capable of definitively saying that an item is not in the store, and a lookup can be skipped entirely.

The rate at which the filter responds "maybe" when an item wasn't actually added to the filter is configurable, and changes the space used by the filter. If too many items are added to a filter, it overflows and returns "maybe" for every query, becoming useless.

Cuckoo filters are similar to Bloom filters, a more well-known variety of set-membership filter. However, Cuckoo filters have two main advantages:

• For false positive rates below about 3%, Cuckoo filters use less space than a corresponding Bloom filter.

• Cuckoo filters support Delete(), and Bloom filters do not.

Documentation

Overview

Package cuckoo implements a cuckoo filter using the techniques described in https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf.

Cuckoo filters are space-efficient, probabalistic structures for set membership tests. Essentially, a Cuckoo filter behaves like a set, but the only query it supports is "is x a member of the set?", to which it can only respond "no" or "maybe".

This is useful for many purposes, but one use case is avoiding expensive lookups. A Cuckoo filter of the items contained in the store is capable of definitively saying that an item is not in the store, and a lookup can be skipped entirely.

The rate at which the filter responds "maybe" when an item wasn't actually added to the filter is configurable, and changes the space used by the filter. If too many items are added to a filter, it overflows and returns "maybe" for every query, becoming useless.

Cuckoo filters are similar to Bloom filters, a more well-known variety of set-membership filter. However, Cuckoo filters have two main advantages:

- For false positive rates below about 3%, Cuckoo filters use less space than a corresponding Bloom filter.

- Cuckoo filters support Delete(), and Bloom filters do not.

Index

• type Filter
  • func New(n int, fp float64) *Filter
  • func NewRaw(f, b, n int) *Filter
  • func (fl *Filter) Add(x []byte)
  • func (fl *Filter) Contains(x []byte) Result
  • func (fl *Filter) Count() int
  • func (fl *Filter) Delete(x []byte)
  • func (fl *Filter) Overflowed() bool
  • func (fl *Filter) SizeBytes() uint64
• type Result
  • func (r Result) String() string

Types

type Filter

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

func New

func New(n int, fp float64) *Filter

Returns a new filter capable of holding n items with an estimated false-positive rate of fp. If more than n items are added, the false-positive rate approaches 1.

func NewRaw

func NewRaw(f, b, n int) *Filter

Returns a new filter constructed using raw parameters.

- f: fingerprint length in bits. [2, 16]

- b: bucket size in number of entries. [1, 8]

- n: number of buckets in the table.

f * b must be less than 64.

The most efficient representation can be used when f=4 and b=4, using the fewest bits per item.

See https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf for more information on how to select these parameters.

func (*Filter) Add

func (fl *Filter) Add(x []byte)

Adds an item to the filter. After Add(x) returns, Contains(x) returns Maybe.

func (*Filter) Contains

func (fl *Filter) Contains(x []byte) Result

Returns No if x is definitely not in the filter, and Maybe if x might be in the filter.

func (*Filter) Count

func (fl *Filter) Count() int

Returns the number of items in the filter.

func (*Filter) Delete

func (fl *Filter) Delete(x []byte)

Deletes x from the filter. x must have been previously added.

func (*Filter) Overflowed

func (fl *Filter) Overflowed() bool

True if the filter has overflowed, and now blindly returns Maybe for every query. This happens when an Add() fails because there is no more room left in the filter.

func (*Filter) SizeBytes

func (fl *Filter) SizeBytes() uint64

Returns the number of bytes used by the filter.

type Result

type Result byte

const (
	// The item is definitely not a member of the set.
	No Result = iota
	// The item might be a member of the set.
	Maybe
)

func (Result) String

func (r Result) String() string