README
¶
Cuckoo Filter: Practically Better Than Bloom
Package cuckoo provides a Cuckoo Filter (Practically Better Than Bloom). 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.
Implementation is based heavily on whitepaper: "Cuckoo Filter: Better Than Bloom" by Bin Fan, Dave Andersen and Michael Kaminsky (https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf).
Example
var item []byte
// Create a new filter with 32MB capacity
f := cuckoo.NewFilter(32 * 1024 * 1024)
if f.Lookup(item) {
if !f.Delete(item) {
// Cannot delete the item
// ...
}
} else {
if err := f.Insert(item); err != nil {
// Hashtable is considered full
// ...
}
}
Fuzzing - randomized testing
- get go-fuzz
$ go get github.com/dvyukov/go-fuzz/go-fuzz
$ go get github.com/dvyukov/go-fuzz/go-fuzz-build
- build the test program with necessary instrumentation
$ go-fuzz-build github.com/kuba--/cuckoo/fuzz/cuckoo
- ready to go
$ go-fuzz -bin=./cuckoo-fuzz.zip -workdir=/tmp/cuckoo
Documentation
¶
Overview ¶
Package cuckoo provides a Cuckoo Filter (Practically Better Than Bloom). 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.
Implementation is based heavily on whitepaper: "Cuckoo Filter: Better Than Bloom" by Bin Fan, Dave Andersen and Michael Kaminsky (https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf).
Index ¶
Constants ¶
This section is empty.
Variables ¶
var DefaultHash32 = fnv.New32a()
DefaultHash32 is a default hash function.
var MaxNumKicks uint32 = 512
MaxNumKicks stands for maximum number of cuckoo kicks before insert failure.
Functions ¶
This section is empty.
Types ¶
type Filter ¶
type Filter struct {
// contains filtered or unexported fields
}
Filter keeps hashtable with fingerprints.
func NewFilter ¶
NewFilter creates a new Cuckoo Filter with given capacity (rounding up to the nearest power of 2).
func (*Filter) Delete ¶
Delete deletes an item from the filter. Pseudo code:
f = fingerprint(x); i1 = hash(x); i2 = i1 ⊕ hash(f); if bucket[i1] or bucket[i2] has f then remove a copy of f from this bucket; return True; return False;
func (*Filter) Insert ¶
Insert inserts an item to the filter. Pseudo code:
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;
Source Files
Directories