bloomf

README

Bloomf Bloomfilter written in Go, backed by redis

Bloomf is a Bloomfilter written in Go and backed by redis.

• It makes use of several redis bitmap, so It won't be limited to 512MB which is the max of redis bitmap.
• Every add and check only take one roundtrip for pipeline is used.
• It stores metadata in redis, you can fetch the metadata and restore bloomfilter instance, so Apps that use bloomf can be stateless.
• It use murmur3 hash function which will be uniformly distributed and high performance.

Getting started

Getting bloomf

$ go get github.com/euclidr/bloomf

dependencies

go packages bellow is also needed

• go-redis
• murmur3

Example

package main

import (
    "github.com/euclidr/bloomf"
    "github.com/go-redis/redis"
)


func main() {
    client := redis.NewClient(&redis.Options{
        Addr: "localhost:6379",
    })
    bl, err := bloomf.New(client, "bf" 1000000, 0.001)
    if err == bloomf.ErrDuplicated {
        bl, _ := bloomf.GetByName(client, "bf")
    }

    bl.Add([]bytes("awesome key"))

    exists, _ := bl.Exists([]bytes("awesome key"))
    if exists {
        ...
    }

    ...

    // bl.Clear() // you can clean up all datas in redis
}

Documentation

Index

• Constants
• Variables
• type Bloom
  • func GetByName(client *redis.Client, name string) (bloom *Bloom, err error)
  • func New(client *redis.Client, name string, n uint64, p float64) (bloom *Bloom, err error)
  • func (b *Bloom) Add(value []byte) error
  • func (b *Bloom) Clear()
  • func (b *Bloom) Exists(value []byte) (bool, error)

Constants

const (
	InfoKeyName  = "name"
	InfoKeyN     = "n"
	InfoKeyP     = "p"
	InfoKeyM     = "m"
	InfoKeyK     = "k"
	InfoKeyParts = "parts"
)

InfoKeys

const (
	PartBitCount uint64 = 1 << 32
)

PartBitCount the offset of bitmap in redis must smaller than 2^32 https://redis.io/commands/SETBIT

Variables

var (
	ErrDuplicated = errors.New("duplicated")
	ErrNotExists  = errors.New("not exists")
)

Errors

Types

type Bloom

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

Bloom bloomfilter class

func GetByName

func GetByName(client *redis.Client, name string) (bloom *Bloom, err error)

GetByName get bloomfilter by name client is instance of redis.Client name should be a unique key in redis instance

and it should exist before New function is called

It returns Bloom instance if no error It returns error if not exists or because of other errors such as bad network

func New

func New(client *redis.Client, name string, n uint64, p float64) (bloom *Bloom, err error)

New create and initialize bloomfilter client is instance of redis.Client name should be a unique key in redis instance

and it shouldn't exist before New function is called

n is estimated amount of total element that will be marked in bloomfilter p is the expected false positive rate

It returns Bloom instance if no error It returns error if duplicated or because of other errors such as bad network

func (*Bloom) Add

func (b *Bloom) Add(value []byte) error

Add add element in bloomfilter

func (*Bloom) Clear

func (b *Bloom) Clear()

Clear clear bloomfilter data in redis

func (*Bloom) Exists

func (b *Bloom) Exists(value []byte) (bool, error)

Exists check if element in bloomfilter