cuckoo

README

cuckoo filter

Overview

Cuckoo filter is a Bloom filter replacement for approximated set-membership queries. While Bloom filters are well-known space-efficient data structures to serve queries like "if item x is in a set?", they do not support deletion. Their variances to enable deletion (like counting Bloom filters) usually require much more space.

Cuckoo filters provide the flexibility to add and remove items dynamically. A cuckoo filter is based on cuckoo hashing (and therefore named as cuckoo filter). It is essentially a cuckoo hash table storing each key's fingerprint. Cuckoo hash tables can be highly compact, thus a cuckoo filter could use less space than conventional Bloom filters, for applications that require low false positive rates (< 3%).

For details about the algorithm and citations please use:

"Cuckoo Filter: Practically Better Than Bloom" in proceedings of ACM CoNEXT 2014 by Bin Fan, Dave Andersen and Michael Kaminsky

API

A cuckoo filter supports following operations:

• Insert([]byte) insert an item to the filter
• Contain([]byte) return if item is already in the filter. Note that this method may return false positive results like Bloom filters
• Delete([]byte) delete the given item from the filter. Note that to use this method, it must be ensured that this item is in the filter (e.g., based on records on external storage); otherwise, a false item may be deleted.

Example usage:

// default option
filter := NewCuckooFilter()
// insert item "12" into filter
filter.Insert([]byte("12"))

assert(filter.Contain("12") == true)

Documentation

Index

• Constants
• type Cuckoo
  • func NewCuckooFilter(opts ...Option) *Cuckoo
  • func (c *Cuckoo) BitsPerItem() float64
  • func (c *Cuckoo) Contain(item []byte) bool
  • func (c *Cuckoo) Delete(item []byte) bool
  • func (c *Cuckoo) Insert(x []byte) bool
  • func (c *Cuckoo) LoadFactor() float64
• type Option
  • func WithBitsPerItem(n uint32) Option
  • func WithHash(hf hash.Hash64) Option
  • func WithKickCount(kicks int) Option
  • func WithNumKeys(n uint32) Option
  • func WithTable(t Table) Option
  • func WithTagsPerBucket(n uint32) Option
• type Options
• type PackedTable
  • func NewPackedTable() *PackedTable
  • func (p *PackedTable) Delete(i uint32, tag uint32) bool
  • func (p *PackedTable) Find(i uint32, tag uint32) bool
  • func (p *PackedTable) Info() string
  • func (p *PackedTable) Init(numBucket, tagsPerBucket, bitsPerItem uint32)
  • func (p *PackedTable) Insert(i uint32, tag uint32, kickout bool) (oldTag uint32, ok bool)
  • func (p *PackedTable) SizeInTags() uint32
  • func (p *PackedTable) String() string
• type PermEncoding
  • func NewPermEncoding() *PermEncoding
  • func (p *PermEncoding) DecItem(codeword uint16) uint16
  • func (p *PermEncoding) Decode(codeword uint16) [4]uint8
  • func (p *PermEncoding) Encode(lowBits [4]uint8) uint16
• type Table

Constants

const (
	N_ENTS = 3876
)

const (
	SingleTable = "single-table"
)

Types

type Cuckoo

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

func NewCuckooFilter

func NewCuckooFilter(opts ...Option) *Cuckoo

NewCuckooFilter

func (*Cuckoo) BitsPerItem

func (c *Cuckoo) BitsPerItem() float64

func (*Cuckoo) Contain

func (c *Cuckoo) Contain(item []byte) bool

f = fingerprint(x); i1 = hash(x); i2 = i1 ⊕ hash(f); if bucket[i1] or bucket[i2] has f then

return True;

return False;

func (*Cuckoo) Delete

func (c *Cuckoo) Delete(item []byte) bool

func (*Cuckoo) Insert

func (c *Cuckoo) Insert(x []byte) bool

f = fingerprint(x); i1 = hash(x); i2 = i1 ⊕ hash(f); if bucket[i1] or bucket[i2] has an empty entry then

add f to that bucket;
return Done;

// must relocate existing items; i = randomly pick i1 or i2; for n = 0; n < MaxNumKicks; n++ do

randomly select an entry e from bucket[i];
swap f and the fingerprint stored in entry e;
i = i ⊕ hash(f);
if bucket[i] has an empty entry then
	add f to bucket[i];
	return Done;

// Hashtable is considered full; return Failure;

func (*Cuckoo) LoadFactor

func (c *Cuckoo) LoadFactor() float64

type Option

type Option func(options *Options)

func WithBitsPerItem

func WithBitsPerItem(n uint32) Option

WithBitsPerItem per item has bits count

func WithHash

func WithHash(hf hash.Hash64) Option

WithHash

func WithKickCount

func WithKickCount(kicks int) Option

WithKickCount

func WithNumKeys

func WithNumKeys(n uint32) Option

func WithTable

func WithTable(t Table) Option

func WithTagsPerBucket

func WithTagsPerBucket(n uint32) Option

type Options

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

Options cuckoo options

type PackedTable

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

semi sort table Using Permutation encoding to save 1 bit per tag

func NewPackedTable

func NewPackedTable() *PackedTable

NewPackedTable new a PackedTable

func (*PackedTable) Delete

func (p *PackedTable) Delete(i uint32, tag uint32) bool

func (*PackedTable) Find

func (p *PackedTable) Find(i uint32, tag uint32) bool

func (*PackedTable) Info

func (p *PackedTable) Info() string

func (*PackedTable) Init

func (p *PackedTable) Init(numBucket, tagsPerBucket, bitsPerItem uint32)

Init init packed table

func (*PackedTable) Insert

func (p *PackedTable) Insert(i uint32, tag uint32, kickout bool) (oldTag uint32, ok bool)

func (*PackedTable) SizeInTags

func (p *PackedTable) SizeInTags() uint32

func (*PackedTable) String

func (p *PackedTable) String() string

type PermEncoding

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

func NewPermEncoding

func NewPermEncoding() *PermEncoding

func (*PermEncoding) DecItem

func (p *PermEncoding) DecItem(codeword uint16) uint16

func (*PermEncoding) Decode

func (p *PermEncoding) Decode(codeword uint16) [4]uint8

func (*PermEncoding) Encode

func (p *PermEncoding) Encode(lowBits [4]uint8) uint16

type Table

type Table interface {
	Init(numBucket, tagsPerBucket, bitsPerItem uint32)
	Insert(i uint32, tag uint32, kickout bool) (oldTag uint32, ok bool)
	Delete(i uint32, tag uint32) bool
	Find(i1 uint32, tag uint32) bool
	SizeInTags() uint32
	Info() string
	String() string
}