cuckoo

package module
v0.4.0 Latest Latest
Warning

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

 Go to latest Published: Oct 9, 2021 License: MIT Imports: 7 Imported by: 16

README

cuckoo-filter

Mentioned in Awesome Go

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 in TableTypeSingle type implementation.

In addition, the Semi-sorting Buckets mentioned in paper which can save 1 bit per item is also available in TableTypePacked type, note that b=4, only f is adjustable.

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 normal single table
	TableTypeSingle = 0
	// TableTypePacked packed table, use semi-sort to save 1 bit per item
	TableTypePacked = 1
)

Variables

This section is empty.

Functions

This section is empty.

Types

type Filter 

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

Filter cuckoo filter type struct

func Decode 

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

Decode returns a Cuckoo Filter using a copy of the provided byte slice.

func DecodeFrom added in v0.4.0 

func DecodeFrom(b []byte) (*Filter, error)

DecodeFrom returns a Cuckoo Filter using the exact provided byte slice (no copy).

func NewFilter 

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

NewFilter return a new initialized 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

Add add an item into filter, return false when filter is full

func (*Filter) AddUnique 

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

AddUnique add an item into filter, return false when filter already contains it or filter is full

func (*Filter) BitsPerItem 

func (f *Filter) BitsPerItem() float64

BitsPerItem return bits occupancy per item of filter's table

func (*Filter) Contain 

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

Contain return if filter contains an item

func (*Filter) Delete 

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

Delete delete item from filter, return false when item not exist

func (*Filter) Encode 

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

Encode returns a byte slice representing a Cuckoo filter

func (*Filter) EncodeReader added in v0.4.0 

func (f *Filter) EncodeReader() (io.Reader, uint)

EncodeReader returns a reader 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

Info return filter's detail info

func (*Filter) LoadFactor 

func (f *Filter) LoadFactor() float64

LoadFactor return current filter's loadFactor

func (*Filter) Reset 

func (f *Filter) Reset()

Reset reset the filter

func (*Filter) Size 

func (f *Filter) Size() uint

Size return num of items that filter store

func (*Filter) SizeInBytes 

func (f *Filter) SizeInBytes() uint

SizeInBytes return bytes occupancy of filter's table

type PackedTable 

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

PackedTable using Permutation encoding to save 1 bit per tag

func NewPackedTable 

func NewPackedTable() *PackedTable

NewPackedTable return a packedTable

func (*PackedTable) BitsPerItem 

func (p *PackedTable) BitsPerItem() uint

BitsPerItem return bits occupancy per item of table

func (*PackedTable) Decode 

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

Decode parse a byte slice into a TableBucket

func (*PackedTable) DeleteTagFromBucket 

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

DeleteTagFromBucket delete tag from bucket i

func (*PackedTable) FindTagInBuckets 

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

FindTagInBuckets find if tag in bucket i1 i2

func (*PackedTable) Info 

func (p *PackedTable) Info() string

Info return table's info

func (*PackedTable) Init 

func (p *PackedTable) Init(_, bitsPerTag, num uint, initialBucketsHint []byte) error

Init init table

func (*PackedTable) InsertTagToBucket 

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

InsertTagToBucket insert tag into bucket i

func (*PackedTable) NumBuckets 

func (p *PackedTable) NumBuckets() uint

NumBuckets return num of table buckets

func (*PackedTable) PrintBucket 

func (p *PackedTable) PrintBucket(i uint)

PrintBucket print a bucket

func (*PackedTable) PrintTags 

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

PrintTags print tags

func (*PackedTable) ReadBucket 

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

ReadBucket 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) Reader added in v0.4.0 

func (p *PackedTable) Reader() (io.Reader, uint)

Encode returns a byte slice representing a TableBucket

func (*PackedTable) Reset 

func (p *PackedTable) Reset()

Reset reset table

func (*PackedTable) SizeInBytes 

func (p *PackedTable) SizeInBytes() uint

SizeInBytes return bytes occupancy of table

func (*PackedTable) SizeInTags 

func (p *PackedTable) SizeInTags() uint

SizeInTags return num of tags that table can store

func (*PackedTable) WriteBucket 

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

WriteBucket write tags into bucket i

type PermEncoding 

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

PermEncoding permutation table

func (*PermEncoding) Decode 

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

Decode decode codeword to lowBits

func (*PermEncoding) Encode 

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

Encode encode lowBits to codeword

func (*PermEncoding) Init 

func (p *PermEncoding) Init()

Init init permutation table

type SingleTable 

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

SingleTable the most naive table implementation: one huge bit array

func NewSingleTable 

func NewSingleTable() *SingleTable

NewSingleTable return a singleTable

func (*SingleTable) BitsPerItem 

func (t *SingleTable) BitsPerItem() uint

BitsPerItem return bits occupancy per item of table

func (*SingleTable) Decode 

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

Decode parse a byte slice into a TableBucket

func (*SingleTable) DeleteTagFromBucket 

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

DeleteTagFromBucket delete tag from bucket i

func (*SingleTable) FindTagInBuckets 

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

FindTagInBuckets find if tag in bucket i1 i2

func (*SingleTable) Info 

func (t *SingleTable) Info() string

Info return table's info

func (*SingleTable) Init 

func (t *SingleTable) Init(tagsPerBucket, bitsPerTag, num uint, initialBucketsHint []byte) error

Init init table

func (*SingleTable) InsertTagToBucket 

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

InsertTagToBucket insert tag into bucket i

func (*SingleTable) NumBuckets 

func (t *SingleTable) NumBuckets() uint

NumBuckets return num of table buckets

func (*SingleTable) ReadTag 

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

ReadTag read tag from bucket(i,j)

func (*SingleTable) Reader added in v0.4.0 

func (t *SingleTable) Reader() (io.Reader, uint)

Encode returns a byte slice representing a TableBucket

func (*SingleTable) Reset 

func (t *SingleTable) Reset()

Reset reset table

func (*SingleTable) SizeInBytes 

func (t *SingleTable) SizeInBytes() uint

SizeInBytes return bytes occupancy of table

func (*SingleTable) SizeInTags 

func (t *SingleTable) SizeInTags() uint

SizeInTags return num of tags that table can store

func (*SingleTable) WriteTag 

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

WriteTag write tag into bucket(i,j)

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.