README
¶
Cuckoo Filter
Cuckoo Filter in Go
Install
Install via go get
go get -u -v github.com/mtchavez/cuckoo
Usage
New Filter
Create a new filter with default configuration
package main
import "github.com/mtchavez/cuckoo"
func main() {
cuckoo.New()
}
Configuration
You can configure a filter via a ConfigOption type and the composed config option
functions provided.
package main
import "github.com/mtchavez/cuckoo"
func main() {
options := []cuckoo.ConfigOption{
cuckoo.BucketEntries(uint(24)),
cuckoo.BucketTotal(uint(1 << 16)),
cuckoo.FingerprintLength(uint(1)),
cuckoo.Kicks(uint(250)),
}
cuckoo.New(options...)
}
Insert
Inserting items into a filter
package main
import "github.com/mtchavez/cuckoo"
func main() {
filter := cuckoo.New()
filter.Insert([]byte("special-items"))
}
Insert Unique
Inserting items into a filter only if they do not already exist
package main
import (
"fmt"
"github.com/mtchavez/cuckoo"
)
func main() {
filter := cuckoo.New()
filter.InsertUnique([]byte("special-items"))
filter.InsertUnique([]byte("special-items"))
if filter.ItemCount() != 1 {
fmt.Println("Expected only 1 item")
}
}
Lookup
Check if items exist in the filter using Lookup
package main
import (
"fmt"
"github.com/mtchavez/cuckoo"
)
func main() {
filter := cuckoo.New()
filter.Insert([]byte("special-items"))
found := filter.Lookup([]byte("special-items"))
if !found {
fmt.Println("Expected to find item in filter")
}
}
Delete
Deleting an item if it exists in the filter
package main
import (
"fmt"
"github.com/mtchavez/cuckoo"
)
func main() {
filter := cuckoo.New()
filter.Insert([]byte("special-items"))
deleted := filter.Delete([]byte("special-items"))
if !deleted {
fmt.Println("Expected to delete item from filter")
}
}
Item Count
Getting the item count of filter. Using Insert with duplicates will cause the item count to be more like a total items inserted count. Using InsertUnique and checking the ItemCount will be more of a real item count.
package main
import (
"fmt"
"github.com/mtchavez/cuckoo"
)
func main() {
filter := cuckoo.New()
filter.InsertUnique([]byte("special-items"))
filter.InsertUnique([]byte("special-items"))
if filter.ItemCount() != 1 {
fmt.Println("Expected only 1 item")
}
}
Save
Encode and save a filter to be able to re-build or re-load back into memory.
package main
import (
"fmt"
"github.com/mtchavez/cuckoo"
)
func main() {
filter := New()
item := []byte("Largo")
filter.InsertUnique(item)
filter.Save("./tmp/example_save.gob")
}
Load
Load a filter back into memory from an encoded filter saved to a file.
package main
import (
"fmt"
"github.com/mtchavez/cuckoo"
)
func main() {
filter := New()
item := []byte("Largo")
filter.InsertUnique(item)
filter.Save("./tmp/example_save.gob")
loadedFilter, _ := Load("./tmp/example_save.gob")
fmt.Printf("Loaded filter has same item? %v\n\n", loadedFilter.Lookup(item))
}
Benchmarks
There are benchmark tests to check performance of the filter. The following results were ran on a 2.3 GHz Intel Core i7
# Updated: 2017-08-15
BenchmarkCuckooNew-8 20 69606308 ns/op
BenchmarkInsert-8 2000000 1000 ns/op
BenchmarkInsertUnique-8 5000000 405 ns/op
BenchmarkLookup-8 5000000 399 ns/op
Tests
Run tests via go test or with provided Makefile
go test -v -cover or make test
Documentation
¶
Overview ¶
Package cuckoo ...
Implements a CuckooFilter that uses cuckoo hashing to provide fast set membership testing.
Index ¶
- type ConfigOption
- type Filter
- func (f *Filter) Delete(item []byte) bool
- func (f *Filter) Insert(item []byte) bool
- func (f *Filter) InsertUnique(item []byte) bool
- func (f *Filter) ItemCount() uint
- func (f *Filter) Lookup(item []byte) bool
- func (f *Filter) MarshalBinary() ([]byte, error)
- func (f *Filter) Save(path string) error
- func (f *Filter) UnmarshalBinary(data []byte) error
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type ConfigOption ¶
type ConfigOption func(*Filter)
ConfigOption ...
Composed Filter function type used for configuring a Filter
func BucketEntries ¶
func BucketEntries(entries uint) ConfigOption
BucketEntries ...
Number of entries per bucket denoted as b ¶
Example:
New(BucketEntries(uint(42)))
func BucketTotal ¶
func BucketTotal(total uint) ConfigOption
BucketTotal ...
Number of buckets in the Filter denoted as m ¶
Example:
New(BucketTotal(uint(42)))
func FingerprintLength ¶
func FingerprintLength(length uint) ConfigOption
FingerprintLength ...
Length of the item fingerprint denoted as f ¶
Example:
New(FingerprintLength(uint(4)))
func Kicks ¶
func Kicks(kicks uint) ConfigOption
Kicks ...
Maximum number of kicks to attempt when bucket collisions occur ¶
Example:
New(Kicks(uint(200)))
type Filter ¶
Filter ...
Cuckoo filter type
func New ¶
func New(opts ...ConfigOption) (filter *Filter)
New ...
Create a new Filter with an optional set of ConfigOption to configure settings.
Example: New Filter with custom config option
New(FingerprintLength(4))
Example: New Filter with default config
New()
returns a Filter type
func (*Filter) Delete ¶
Delete ...
Delete an item of []byte if it exists in the Filter
Example:
filter.Delete([]byte("new-item"))
returns a boolean of whether the item was deleted or not
func (*Filter) Insert ¶
Insert ...
Add a new item of []byte to a Filter
Example:
filter.Insert([]byte("new-item"))
returns a boolean of whether the item was inserted or not
func (*Filter) InsertUnique ¶
InsertUnique ...
Add a new item of []byte to a Filter only if it doesn't already exist. Will do a Lookup of item first.
Example:
filter.InsertUnique([]byte("new-item"))
returns a boolean of whether the item was inserted or not
func (*Filter) ItemCount ¶
ItemCount ...
Get an estimate of the total items in the Filter. Could be drastically off if using Insert with many duplicate items. To get a more accurate total using InsertUnique can be used
Example:
filter.ItemCount()
returns an uint of the total items in the Filter
func (*Filter) Lookup ¶
Lookup ...
Check if an item of []byte exists in the Filter
Example:
filter.Lookup([]byte("new-item"))
returns a boolean of whether the item exists or not
func (*Filter) MarshalBinary ¶
MarshalBinary used to interact with gob encoding interface
func (*Filter) UnmarshalBinary ¶
UnmarshalBinary modifies the receiver so it must take a pointer receiver. Used to interact with gob encoding interface
Source Files