fastbloom

README

FastBloom

fastbloom implements a Bloom Filter that supports any number of concurrent readers and writers.

Docs: http://godoc.org/github.com/JamesHageman/fastbloom

Example:

package main

import "github.com/JamesHageman/fastbloom"

func ExampleNewFilter() {
	filter := fastbloom.NewFilter(100, 0.01)
	fmt.Println(filter.Test([]byte(`a`)))
	fmt.Println(filter.Test([]byte(`b`)))

	filter.Add([]byte(`a`))
	filter.Add([]byte(`b`))

	fmt.Println(filter.Test([]byte(`a`)))
	fmt.Println(filter.Test([]byte(`b`)))
	fmt.Println(filter.Test([]byte(`c`)))

	// Output:
	// false
	// false
	// true
	// true
	// false
}

Concurrency

fastbloom allows any number of concurrent readers and writers. It maintains the following invariants:

• Before Add(key) or TestAndAdd(key) are called, Test(key) may return false.
• After Add(key) or TestAndAdd(key) are called, Test(key) will always return true.
• If Test(key) and either of the mutating methods (Add or TestAndAdd) are called concurrently, Test may return false.

Instead of relying on locks, fastbloom takes advantage of the sync/atomic package from the standard library.

The bit vector is implemented as a []uint32. Each unint32 can be thought of as a 32 bit block. When reading the bit vector, the reader queries bits by calling atomic.LoadUint32(addr) on each block. When writing a bit, the writer uses a combination of atomic.LoadUint32(addr) and atomic.CompareAndSwapUint32(addr, orig, updated) to safely read a block, mutate it, and write it back to memory. If two concurrent writers try to mutate the same block, both will only finish once atomic.CompareAndSwapUint32 returns true, meaning that the write-after read was guaranteed to be atomic. This ensures that two writers that try to update different bits withing a block do not unexpectedly erase the other's changes.

Documentation

Index

• type Filter
  • func NewFilter(n uint, fpRate float64) *Filter
  • func (f *Filter) Add(key []byte) *Filter
  • func (f *Filter) Capacity() uint
  • func (f *Filter) GobDecode(data []byte) error
  • func (f *Filter) GobEncode() ([]byte, error)
  • func (f *Filter) K() uint
  • func (f *Filter) Test(key []byte) bool
  • func (f *Filter) TestAndAdd(key []byte) bool

Examples

• NewFilter

Types

type Filter

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

Filter is an implementation of a Bloom Filter that permits n concurrent readers and m concurrent writers.

func NewFilter

func NewFilter(n uint, fpRate float64) *Filter

NewFilter creates a bloom filter optimized for n elements with a falsePositive rate fpRate.

Example

package main

import (
	"fmt"

	"github.com/JamesHageman/fastbloom"
)

func main() {
	filter := fastbloom.NewFilter(100, 0.01)
	fmt.Println(filter.Test([]byte(`a`)))
	fmt.Println(filter.Test([]byte(`b`)))

	filter.Add([]byte(`a`))
	filter.Add([]byte(`b`))

	fmt.Println(filter.Test([]byte(`a`)))
	fmt.Println(filter.Test([]byte(`b`)))
	fmt.Println(filter.Test([]byte(`c`)))

}

Output:

false
false
true
true
false

func (*Filter) Add

func (f *Filter) Add(key []byte) *Filter

Add writes a key to the bloom filter. It can be called concurrently with other calls to Add, TestAndAdd, and Test.

func (*Filter) Capacity

func (f *Filter) Capacity() uint

Capacity returns the Bloom filter capacity, m.

func (*Filter) GobDecode

func (f *Filter) GobDecode(data []byte) error

GobDecode implements gob.GobDecoder interface.

func (*Filter) GobEncode

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

GobEncode implements gob.GobEncoder interface.

func (*Filter) K

func (f *Filter) K() uint

K returns the number of hash functions.

func (*Filter) Test

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

Test tests the filter for the presence of a key. It is (only) guaranteed to return true after a call to Add(key) or TestAndAdd(key) have completed. Because of the possibility of false positives, Test(key) could also return true if the key hasn't been added.

func (*Filter) TestAndAdd

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

TestAndAdd adds a key to the bloom filter and returns true if it appears that the key was already present.