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 int64) *BitSet
  • func (b *BitSet) Set(offsets []int64) error
  • func (b *BitSet) Test(offsets []int64) (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 int64) error
  • func (r *RedisBitSet) Set(offsets []int64) error
  • func (r *RedisBitSet) Test(offsets []int64) (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 int64) *BitSet

func (*BitSet) Set

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

func (*BitSet) Test

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

type BitSetProvider

type BitSetProvider interface {
	Set([]int64) error
	Test([]int64) (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 {
	SetBit(key string, offset int64, value int) error
	GetBit(key string, offset int64) (int, error)
	Expire(key string, expiration time.Duration) error
	Del(keys ...string) error
	Pipeline() Connection
	Exec() 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 int64) error

func (*RedisBitSet) Set

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

func (*RedisBitSet) Test

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