bloom

package module
v0.0.0-...-ffcbfcf Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Jul 16, 2021 License: Apache-2.0 Imports: 6 Imported by: 0

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.

Build Status

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

Constants

This section is empty.

Variables

This section is empty.

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)

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL