bloom

README

Bloom Filters for Golang

Bloom filter for go, backed by redis or in process bitset

If you are not familiar with how Bloom filters work and their usefulness, please read.

Example Usage (in process):

install with

go get gopkg.in/bculberson/bloom.v2

go import ( "gopkg.in/bculberson/bloom.v2" )

This bloom filter is initialized to hold 1000 keys and will have a false positive rate of 1% (.01).

m, k := bloom.EstimateParameters(1000, .01)
b := bloom.New(m, k, bloom.NewBitSet(m))
b.Add([]byte("some key"))
exists, _ := b.Exists([]byte("some key"))
doesNotExist, _ := b.Exists([]byte("some other key"))

Example Usage (redis backed):

This bloom filter is initialized to hold 1000 keys and will have a false positive rate of 1% (.01).

This library uses http://github.com/garyburd/redigo/redis

pool := &redis.Pool{
    MaxIdle:     3,
    IdleTimeout: 240 * time.Second,
    Dial:        func() (redis.Conn, error) { return redis.Dial("tcp", addr) },
}


conn := pool.Get()
m, k := bloom.EstimateParameters(1000, .01)
bitSet := bloom.NewRedisBitSet("test_key", m, conn)
b := bloom.New(m, k, bitSet)
b.Add([]byte("some key"))
exists, _ := b.Exists([]byte("some key"))
doesNotExist, _ := b.Exists([]byte("some other key"))

Documentation

Index

• func EstimateParameters(n uint, p float64) (uint, uint)
• type BitSet
  • func NewBitSet(m uint) *BitSet
  • func (b *BitSet) Set(offsets []uint) error
  • func (b *BitSet) Test(offsets []uint) (bool, error)
• type BitSetProvider
• type BloomFilter
  • func New(m uint, k uint, bitSet BitSetProvider) *BloomFilter
  • func (f *BloomFilter) Add(data []byte) error
  • func (f *BloomFilter) Exists(data []byte) (bool, error)
• type Connection
• type RedisBitSet
  • func NewRedisBitSet(keyPrefix string, m uint, conn Connection) *RedisBitSet
  • func (r *RedisBitSet) Delete() error
  • func (r *RedisBitSet) Expire(seconds uint) error
  • func (r *RedisBitSet) Set(offsets []uint) error
  • func (r *RedisBitSet) Test(offsets []uint) (bool, error)

Functions

func EstimateParameters

func EstimateParameters(n uint, p float64) (uint, uint)

Types

type BitSet

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

func NewBitSet

func NewBitSet(m uint) *BitSet

func (*BitSet) Set

func (b *BitSet) Set(offsets []uint) error

func (*BitSet) Test

func (b *BitSet) Test(offsets []uint) (bool, error)

type BitSetProvider

type BitSetProvider interface {
	Set([]uint) error
	Test([]uint) (bool, error)
}

type BloomFilter

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

func New

func New(m uint, k uint, bitSet BitSetProvider) *BloomFilter

func (*BloomFilter) Add

func (f *BloomFilter) Add(data []byte) error

func (*BloomFilter) Exists

func (f *BloomFilter) Exists(data []byte) (bool, error)

type Connection

type Connection interface {
	Do(cmd string, args ...interface{}) (reply interface{}, err error)
	Send(cmd string, args ...interface{}) error
	Flush() error
}

type RedisBitSet

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

func NewRedisBitSet

func NewRedisBitSet(keyPrefix string, m uint, conn Connection) *RedisBitSet

func (*RedisBitSet) Delete

func (r *RedisBitSet) Delete() error

func (*RedisBitSet) Expire

func (r *RedisBitSet) Expire(seconds uint) error

func (*RedisBitSet) Set

func (r *RedisBitSet) Set(offsets []uint) error

func (*RedisBitSet) Test

func (r *RedisBitSet) Test(offsets []uint) (bool, error)