gobloomgo
A bloom filter is a probabilistic data structure that is used to determine if an element is present in a set.
Bloomdb implements a bloom filter in Go, while using boltdb and badgerdb as optional in-memory persistent storage.
Bloomdb also implement a scalable bloom filter described in a paper written by P. Almeida, C.Baquero, N. Preguiça, D. Hutchison.
A scalable bloom filter allows you to grow the filter as needed, and removes the need for an apriori filter size as expected by the basic bloom filter, while preserving the desired false positive rate by scaling the filter as needed.
Installation
go get github.com/dsa0x/gobloomgo
Usage
gobloomgo contains implementation of both the normal and scalable bloom filter via the methods below:
bf := gobloomgo.NewBloom(0.01, 100, nil)
sbf := gobloomgo.NewScalableBloom(0.9, 100, nil)
With a persistent store
gobloomgo supports boltdb and badgerdb as persistent store. Using them is very simple. gobloomgo exposes methods that initializes the database and then they can be attached to the bloom filter
Using Boltdb
// initialize boltdb
db := gobloomgo.NewBolt("/tmp/test.db", 0600)
// you can also setup options supported by bolt to configure your store
opts := bbolt.Options{
Timeout: 10 * time.Second,
}
db = gobloomgo.NewBolt("/tmp/test.db", 0600, opts)
defer db.Close()
bf := gobloomgo.NewBloom(0.01, 100, db)
Badgerdb (v3)
// initialize badgerdb
db := gobloomgo.NewBadger()
// initialize badgerdb with options
opts := badger.DefaultOptions("/tmp/bloom.db")
db = gobloomgo.NewBadger(opts)
bf := gobloomgo.NewBloom(0.01, 100, db)
Using Scalable bloom filter
// initialize badgerdb
db := gobloomgo.NewBadger()
sbf := gobloomgo.NewScalableBloom(0.9, 100, db)
Example
package main
import (
"fmt"
"github.com/dgraph-io/badger/v3"
"github.com/dsa0x/gobloomgo"
)
func main() {
bf := gobloomgo.NewScalableBloom(0.01, 100, nil)
bf.Find([]byte("foo"))
// with a persistent store
opts := badger.DefaultOptions("/tmp/bloom.db")
db := gobloomgo.NewBadger(opts)
bf := gobloomgo.NewScalableBloom(0.9, 100, db)
bf.Add([]byte("key"), []byte("bar"))
fmt.Printf("%s\n", bf.Get([]byte("key")))
}
