cuckoo

package module
v0.2.0 Latest Latest
Warning

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

 Go to latest Published: Mar 1, 2021 License: MIT Imports: 5 Imported by: 16

README

cuckoo-filter

cuckoo-filter go implement. Config by you

transplant from efficient/cuckoofilter

中文文档

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

Implementation details

The paper cited above leaves several parameters to choose.

  1. Bucket size(b): Number of fingerprints per bucket
  2. Fingerprints size(f): Fingerprints bits size of hashtag

In other implementation:

In this implementation, you can adjust b and f to any value you want, and the Semi-sorting Buckets mentioned in paper is also avaliable, which can save 1 bit per item.

Why custom is important?

According to paper

  • Different bucket size result in different filter loadfactor, which means occupancy rate of filter
  • Different bucket size is suitable for different target false positive rate
  • To keep a false positive rate, bigger bucket size, bigger fingerprint size

Given a target false positive rate of r

when r > 0.002, having two entries per bucket yields slightly better results than using four entries per bucket; when decreases to 0.00001 < r ≤ 0.002, four entries per bucket minimizes space.

with a bucket size b, they suggest choosing the fingerprint size f using

f >= log2(2b/r) bits

as the same time, notice that we got loadfactor 84%, 95% or 98% when using bucket size b = 2, 4 or 8

To know more about parameter choosing, refer to paper's section 5

Note: generally b = 8 is enough, without more data support, we suggest you choosing b from 2, 4 or 8. And f is max 32 bits

Example usage:

package main

import (
	"fmt"
	"github.com/linvon/cuckoo-filter"
)

func main() {
	cf := cuckoo.NewFilter(4, 9, 3900, cuckoo.TableTypePacked)
	fmt.Println(cf.Info())
	fmt.Println(cf.FalsePositiveRate())

	a := []byte("A")
	cf.Add(a)
	fmt.Println(cf.Contain(a))
	fmt.Println(cf.Size())

	b := cf.Encode()
	ncf, _ := cuckoo.Decode(b)
	fmt.Println(ncf.Contain(a))

	cf.Delete(a)
	fmt.Println(cf.Size())
}

Documentation

Index

Constants

View Source 
const (
	TableTypeSingle = 0
	TableTypePacked = 1
)

Variables

This section is empty.

Functions

This section is empty.

Types

type Filter 

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

func Decode 

func Decode(bytes []byte) (*Filter, error)

Decode returns a Cuckoo Filter from a byte slice

func NewFilter 

func NewFilter(tagsPerBucket, bitsPerItem, maxNumKeys, tableType uint) *Filter

tagsPerBucket: num of tags for each bucket, which is b in paper. tag is fingerprint, which is f in paper. bitPerItem: num of bits for each item, which is length of tag(fingerprint) maxNumKeys: num of keys that filter will store. this value should close to and lower 

nextPow2(maxNumKeys/tagsPerBucket) * maxLoadFactor. cause table.NumBuckets is always a power of two

func (*Filter) Add 

func (f *Filter) Add(item []byte) bool

func (*Filter) AddUnique 

func (f *Filter) AddUnique(item []byte) bool

func (*Filter) BitsPerItem 

func (f *Filter) BitsPerItem() float64

func (*Filter) Contain 

func (f *Filter) Contain(key []byte) bool

func (*Filter) Delete 

func (f *Filter) Delete(key []byte) bool

func (*Filter) Encode 

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

Encode returns a byte slice representing a Cuckoo filter

func (*Filter) FalsePositiveRate 

func (f *Filter) FalsePositiveRate() float64

FalsePositiveRate return the False Positive Rate of filter Notice that this will reset filter

func (*Filter) Info 

func (f *Filter) Info() string

func (*Filter) LoadFactor 

func (f *Filter) LoadFactor() float64

func (*Filter) Reset 

func (f *Filter) Reset()

Reset reset the filter

func (*Filter) Size 

func (f *Filter) Size() uint

func (*Filter) SizeInBytes 

func (f *Filter) SizeInBytes() uint

type PackedTable 

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

Using Permutation encoding to save 1 bit per tag

func NewPackedTable 

func NewPackedTable() *PackedTable

func (*PackedTable) BitsPerItem 

func (p *PackedTable) BitsPerItem() uint

func (*PackedTable) Decode 

func (p *PackedTable) Decode(bytes []byte) error

Decode parse a byte slice into a TableBucket

func (*PackedTable) DeleteTagFromBucket 

func (p *PackedTable) DeleteTagFromBucket(i uint, tag uint32) bool

func (*PackedTable) Encode 

func (p *PackedTable) Encode() []byte

Encode returns a byte slice representing a TableBucket

func (*PackedTable) FindTagInBuckets 

func (p *PackedTable) FindTagInBuckets(i1, i2 uint, tag uint32) bool

func (*PackedTable) Info 

func (p *PackedTable) Info() string

func (*PackedTable) Init 

func (p *PackedTable) Init(_, bitsPerTag, num uint)

func (*PackedTable) InsertTagToBucket 

func (p *PackedTable) InsertTagToBucket(i uint, tag uint32, kickOut bool, oldTag *uint32) bool

func (*PackedTable) NumBuckets 

func (p *PackedTable) NumBuckets() uint

func (*PackedTable) PrintBucket 

func (p *PackedTable) PrintBucket(i uint)

func (*PackedTable) PrintTags 

func (p *PackedTable) PrintTags(tags [tagsPerPTable]uint32)

func (*PackedTable) ReadBucket 

func (p *PackedTable) ReadBucket(i uint, tags *[tagsPerPTable]uint32)

read and decode the bucket i, pass the 4 decoded tags to the 2nd arg * bucket bits = 12 codeword bits + dir bits of tag1 + dir bits of tag2 ...

func (*PackedTable) Reset 

func (p *PackedTable) Reset()

func (*PackedTable) SizeInBytes 

func (p *PackedTable) SizeInBytes() uint

func (*PackedTable) SizeInTags 

func (p *PackedTable) SizeInTags() uint

func (*PackedTable) WriteBucket 

func (p *PackedTable) WriteBucket(i uint, tags [tagsPerPTable]uint32)

Tag = 4 low bits + x high bits * L L L L H H H H ...

type PermEncoding 

type PermEncoding struct {
	DecTable []uint16
	EncTable []uint16
	// contains filtered or unexported fields
}

func (*PermEncoding) Decode 

func (p *PermEncoding) Decode(codeword uint16, lowBits *[tagsPerPTable]uint8)

func (*PermEncoding) Encode 

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

func (*PermEncoding) Init 

func (p *PermEncoding) Init()

type SingleTable 

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

the most naive table implementation: one huge bit array

func NewSingleTable 

func NewSingleTable() *SingleTable

func (*SingleTable) BitsPerItem 

func (t *SingleTable) BitsPerItem() uint

func (*SingleTable) Decode 

func (t *SingleTable) Decode(bytes []byte) error

Decode parse a byte slice into a TableBucket

func (*SingleTable) DeleteTagFromBucket 

func (t *SingleTable) DeleteTagFromBucket(i uint, tag uint32) bool

func (*SingleTable) Encode 

func (t *SingleTable) Encode() []byte

Encode returns a byte slice representing a TableBucket

func (*SingleTable) FindTagInBuckets 

func (t *SingleTable) FindTagInBuckets(i1, i2 uint, tag uint32) bool

func (*SingleTable) Info 

func (t *SingleTable) Info() string

func (*SingleTable) Init 

func (t *SingleTable) Init(tagsPerBucket, bitsPerTag, num uint)

func (*SingleTable) InsertTagToBucket 

func (t *SingleTable) InsertTagToBucket(i uint, tag uint32, kickOut bool, oldTag *uint32) bool

func (*SingleTable) NumBuckets 

func (t *SingleTable) NumBuckets() uint

func (*SingleTable) ReadTag 

func (t *SingleTable) ReadTag(i, j uint) uint32

read tag from pos(i,j)

func (*SingleTable) Reset 

func (t *SingleTable) Reset()

func (*SingleTable) SizeInBytes 

func (t *SingleTable) SizeInBytes() uint

func (*SingleTable) SizeInTags 

func (t *SingleTable) SizeInTags() uint

func (*SingleTable) WriteTag 

func (t *SingleTable) WriteTag(i, j uint, n uint32)

write tag to pos(i,j)

type Table 

type Table interface {
	Init(tagsPerBucket, bitsPerTag, num uint)
	NumBuckets() uint
	FindTagInBuckets(i1, i2 uint, tag uint32) bool
	DeleteTagFromBucket(i uint, tag uint32) bool
	InsertTagToBucket(i uint, tag uint32, kickOut bool, oldTag *uint32) bool
	SizeInTags() uint
	SizeInBytes() uint
	Info() string
	BitsPerItem() uint
	Encode() []byte
	Decode([]byte) error
	Reset()
}

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.