go/golang: fast bit set Bloom filter

Overview

bbloom: a bitset Bloom filter for go/golang

===

Build Status

package implements a fast bloom filter with real 'bitset' and JSONMarshal/JSONUnmarshal to store/reload the Bloom filter.

NOTE: the package uses unsafe.Pointer to set and read the bits from the bitset. If you're uncomfortable with using the unsafe package, please consider using my bloom filter package at github.com/AndreasBriese/bloom

===

changelog 11/2015: new thread safe methods AddTS(), HasTS(), AddIfNotHasTS() following a suggestion from Srdjan Marinovic (github @a-little-srdjan), who used this to code a bloomfilter cache.

This bloom filter was developed to strengthen a website-log database and was tested and optimized for this log-entry mask: "2014/%02i/%02i %02i:%02i:%02i /info.html". Nonetheless bbloom should work with any other form of entries.

Hash function is a modified Berkeley DB sdbm hash (to optimize for smaller strings). sdbm http://www.cse.yorku.ca/~oz/hash.html

Found sipHash (SipHash-2-4, a fast short-input PRF created by Jean-Philippe Aumasson and Daniel J. Bernstein.) to be about as fast. sipHash had been ported by Dimtry Chestnyk to Go (github.com/dchest/siphash )

Minimum hashset size is: 512 ([4]uint64; will be set automatically).

###install

go get github.com/AndreasBriese/bbloom

###test

  • change to folder ../bbloom
  • create wordlist in file "words.txt" (you might use python permut.py)
  • run 'go test -bench=.' within the folder
go test -bench=.

If you've installed the GOCONVEY TDD-framework http://goconvey.co/ you can run the tests automatically.

using go's testing framework now (have in mind that the op timing is related to 65536 operations of Add, Has, AddIfNotHas respectively)

usage

after installation add

import (
	...
	"github.com/AndreasBriese/bbloom"
	...
	)

at your header. In the program use

// create a bloom filter for 65536 items and 1 % wrong-positive ratio 
bf := bbloom.New(float64(1<<16), float64(0.01))

// or 
// create a bloom filter with 650000 for 65536 items and 7 locs per hash explicitly
// bf = bbloom.New(float64(650000), float64(7))
// or
bf = bbloom.New(650000.0, 7.0)

// add one item
bf.Add([]byte("butter"))

// Number of elements added is exposed now 
// Note: ElemNum will not be included in JSON export (for compatability to older version)
nOfElementsInFilter := bf.ElemNum

// check if item is in the filter
isIn := bf.Has([]byte("butter"))    // should be true
isNotIn := bf.Has([]byte("Butter")) // should be false

// 'add only if item is new' to the bloomfilter
added := bf.AddIfNotHas([]byte("butter"))    // should be false because 'butter' is already in the set
added = bf.AddIfNotHas([]byte("buTTer"))    // should be true because 'buTTer' is new

// thread safe versions for concurrent use: AddTS, HasTS, AddIfNotHasTS
// add one item
bf.AddTS([]byte("peanutbutter"))
// check if item is in the filter
isIn = bf.HasTS([]byte("peanutbutter"))    // should be true
isNotIn = bf.HasTS([]byte("peanutButter")) // should be false
// 'add only if item is new' to the bloomfilter
added = bf.AddIfNotHasTS([]byte("butter"))    // should be false because 'peanutbutter' is already in the set
added = bf.AddIfNotHasTS([]byte("peanutbuTTer"))    // should be true because 'penutbuTTer' is new

// convert to JSON ([]byte) 
Json := bf.JSONMarshal()

// bloomfilters Mutex is exposed for external un-/locking
// i.e. mutex lock while doing JSON conversion
bf.Mtx.Lock()
Json = bf.JSONMarshal()
bf.Mtx.Unlock()

// restore a bloom filter from storage 
bfNew := bbloom.JSONUnmarshal(Json)

isInNew := bfNew.Has([]byte("butter"))    // should be true
isNotInNew := bfNew.Has([]byte("Butter")) // should be false

to work with the bloom filter.

why 'fast'?

It's about 3 times faster than William Fitzgeralds bitset bloom filter https://github.com/willf/bloom . And it is about so fast as my []bool set variant for Boom filters (see https://github.com/AndreasBriese/bloom ) but having a 8times smaller memory footprint:

Bloom filter (filter size 524288, 7 hashlocs)
github.com/AndreasBriese/bbloom 'Add' 65536 items (10 repetitions): 6595800 ns (100 ns/op)
github.com/AndreasBriese/bbloom 'Has' 65536 items (10 repetitions): 5986600 ns (91 ns/op)
github.com/AndreasBriese/bloom 'Add' 65536 items (10 repetitions): 6304684 ns (96 ns/op)
github.com/AndreasBriese/bloom 'Has' 65536 items (10 repetitions): 6568663 ns (100 ns/op)

github.com/willf/bloom 'Add' 65536 items (10 repetitions): 24367224 ns (371 ns/op)
github.com/willf/bloom 'Test' 65536 items (10 repetitions): 21881142 ns (333 ns/op)
github.com/dataence/bloom/standard 'Add' 65536 items (10 repetitions): 23041644 ns (351 ns/op)
github.com/dataence/bloom/standard 'Check' 65536 items (10 repetitions): 19153133 ns (292 ns/op)
github.com/cabello/bloom 'Add' 65536 items (10 repetitions): 131921507 ns (2012 ns/op)
github.com/cabello/bloom 'Contains' 65536 items (10 repetitions): 131108962 ns (2000 ns/op)

(on MBPro15 OSX10.8.5 i7 4Core 2.4Ghz)

With 32bit bloom filters (bloom32) using modified sdbm, bloom32 does hashing with only 2 bit shifts, one xor and one substraction per byte. smdb is about as fast as fnv64a but gives less collisions with the dataset (see mask above). bloom.New(float64(10 * 1<<16),float64(7)) populated with 1<<16 random items from the dataset (see above) and tested against the rest results in less than 0.05% collisions.

Issues
  • Use of unsafe is unsound

    Use of unsafe is unsound

    Casting to a uintptr, saving the uintptr, and then casting it back is unsound.

    https://github.com/AndreasBriese/bbloom/blob/e2d15f34fcf99d5dbb871c820ec73f710fca9815/bbloom.go#L80-L88

    https://github.com/AndreasBriese/bbloom/blob/e2d15f34fcf99d5dbb871c820ec73f710fca9815/bbloom.go#L232-L246

    opened by Stebalien 8
  • Union and Intersection features

    Union and Intersection features

    Hi Andreas,

    congrats for your work on bbloom, I am integrating it at the core of my new project. I was wondering if you were planning to add methods to calculate union and intersection of 2 bloom filters or if you could put me in the right direction to learn how to do it.

    Let me know, best, Romain.

    opened by romainPellerin 3
  • fix travis build failures and fix

    fix travis build failures and fix "allready" is a misspelling of "already"

    Hey @AndreasBriese , for travis:

    Your's travis builds were failing because of uncompatible old version of go defined in .travis.yml file and because words.txt is not uploaded to the repository, so travis can't actually find when it runs the TestMain test method (the last is fixed by stopping the test without error if os.Open("words.txt") failed).

    go: 1.1 will make use the go.1 version not the go.11, the correct way for what you wanted to do with your commit: 343706a is to represent the version as 1.11.x instead.

    opened by kataras 1
  • Right way to integrate it into my project

    Right way to integrate it into my project

    This may be a stupid question, but I'd very much appreciate your help. I want to implement a page view counter that will be pushed to a database every X hours. Before it gets pushed, then I intend to store it in memory and make sure that the same device (checked using IP + UA) doesn't count for multiple views (unless 1000 other people have visited the page, or it has been X hours since last visit)

    I have the following code:

    package main
    
    import (
    	"fmt"
    	"sync"
    )
    
    type page struct {
    	mu     *sync.Mutex
    	values map[string]int64
    }
    
    var pageCounters = page{
    	values: make(map[string]int64),
    }
    
    func (p *page) Delete(key string) {
    	p.mu.Lock()
    	defer p.mu.Unlock()
    	delete(pageCounters.values, key)
    }
    
    func (p *page) Get(key string) int64 {
    	p.mu.Lock()
    	defer p.mu.Unlock()
    	return p.values[key]
    }
    
    func (p *page) Incr(key string) int64 {
    	p.mu.Lock()
    	defer p.mu.Unlock()
    	p.values[key]++
    	return p.values[key]
    }
    
    func main() {
    	_ = pageCounters.Incr("/some/url/here")
    	_ = pageCounters.Incr("/another/url")
    	_ = pageCounters.Incr("/some/url/here")
    	
    	fmt.Println(pageCounters.Get("/some/url/here"))
    	fmt.Println(pageCounters.Get("/another/url"))
    	fmt.Println(pageCounters)
    	pageCounters.Delete("/another/url")
    	fmt.Println(pageCounters)
    
    }
    

    The plan now is to update the page struct to include a bloomfilter field, I'm thinking it would be done like this:

    type page struct {
    	mu     *sync.Mutex
    	values map[string]int64
    	bloom  bbloom.Bloom
    }
    

    I'm now wondering how I should update the Incr func so that:

    • if a bloom filter doesn't exist, then it will create one containing 1000 items
    • each item will be a combination of user IP address + User Agent (curious how you would recommend storing it?)
    • when the bloom filters items have been filled up, then the bloom filter should either be deleted and replaced by a new bloom filter, or have the previous items be overridden (I assume this is impossible)

    I'm thinking it would look something like this:

    func (p *page) Incr(key, ipUA string) int64 {
    	p.mu.Lock()
    	defer p.mu.Unlock()
    	if (p.values[key] == 0) {
    		p.bloom = bbloom.New(1000.0, 7.0) // probably use wrong values here
    	}
    	added := p.bloom.AddIfNotHasTS([]byte(ipUA))
    	if added == true {
    		p.values[key]++
    	}
    	return p.values[key]
    }
    

    Right now then I don't really know what will happen if the bloomfilter is full, and I'm not sure how to check for this and how to replace it. I guess if (p.values[key] == 0) could become if (p.values[key] == 0 || p.bloom.Size == 999)?

    I also wonder, would there be any benefit to store the bloom as JSON? Keep in mind that each website page will have its own filter and they'll only be deleted after X hours (meaning there could potentially be many thousands of page structs initialized at any given moment)

    I hope you don't mind me abusing your repo & time with this question

    opened by dadatawajue 0
Owner
Andreas Briese
Andreas Briese
Cuckoo Filter: Practically Better Than Bloom

Cuckoo Filter Cuckoo filter is a Bloom filter replacement for approximated set-membership queries. While Bloom filters are well-known space-efficient

Seif Lotfy 913 Jun 25, 2022
Package ring provides a high performance and thread safe Go implementation of a bloom filter.

ring - high performance bloom filter Package ring provides a high performance and thread safe Go implementation of a bloom filter. Usage Please see th

Tanner Ryan 126 May 10, 2022
A simple Bloom Filter implementation in Go

This is a simple Bloom filter implementation written in Go. For the theory behind Bloom filters, read http://en.wikipedia.org/wiki/Bloom_filter This

Damian Gryski 16 Apr 26, 2018
Leaked password check library with bloom filter

Leaked password check With this library you can check the password is probably leaked or not. Pre generated bitset DB includes 6 Million leaked passwo

Kaan Karakaya 41 Dec 2, 2021
A Go implementation of an in-memory bloom filter, with support for boltdb and badgerdb as optional data persistent storage.

Sprout A bloom filter is a probabilistic data structure that is used to determine if an element is present in a set. Bloom filters are fast and space

Samsondeen 25 Jun 7, 2022
IntSet - Integer based Set based on a bit-vector

IntSet - Integer based Set based on a bit-vector Every integer that is stored will be converted to a bit in a word in which its located. The words are

Jakob Möller 0 Feb 2, 2022
Go package implementing Bloom filters

Bloom filters A Bloom filter is a representation of a set of n items, where the main requirement is to make membership queries; i.e., whether an item

Will Fitzgerald 1.6k Jun 26, 2022
Go package implementing Bloom filters

Bloom filters A Bloom filter is a concise/compressed representation of a set, where the main requirement is to make membership queries; i.e., whether

Go language BitSet and Bloom filter 1.6k Jun 26, 2022
Sync distributed sets using bloom filters

goSetReconciliation An implementation to sync distributed sets using bloom filters. Based on the paper "Low complexity set reconciliation using Bloom

Elton SV 25 Jan 4, 2022
A Go implementation of the 64-bit xxHash algorithm (XXH64)

xxhash xxhash is a Go implementation of the 64-bit xxHash algorithm, XXH64. This is a high-quality hashing algorithm that is much faster than anything

Caleb Spare 1.2k Jun 30, 2022
Sroar - 64-bit Roaring Bitmaps in Go

sroar: Serialized Roaring Bitmaps This is a fork of dgraph-io/sroar, being maint

Outcaste, Inc. 26 Jun 6, 2022
A fast (5x) string keyed read-only map for Go - particularly good for keys using a small set of nearby runes.

faststringmap faststringmap is a fast read-only string keyed map for Go (golang). For our use case it is approximately 5 times faster than using Go's

The Sensible Code Company 27 Jun 23, 2022
A simple Set data structure implementation in Go (Golang) using LinkedHashMap.

Set Set is a simple Set data structure implementation in Go (Golang) using LinkedHashMap. This library allow you to get a set of int64 or string witho

Studio Sol Comunicação Digital Ltda 21 Apr 6, 2022
Collections for Golang using generics. Currently containing Hash Set.

Implementation of missing colections for Golang using Generics. Free of dependencies. Curently in early development phase. Requirements Go 1.18+ Insta

Vinícius Ferreira 0 Dec 30, 2021
Probabilistic set data structure

Your basic Bloom filter Golang probabilistic set data structure A Bloom filter is a fast and space-efficient probabilistic data structure used to test

Algorithms to Go 72 May 23, 2022
A simple set type for the Go language. Trusted by Docker, 1Password, Ethereum and Hashicorp.

golang-set The missing set collection for the Go language. Until Go has sets built-in...use this. Coming from Python one of the things I miss is the s

Ralph Caraveo III 2.5k Jul 1, 2022
Set is a useful collection but there is no built-in implementation in Go lang.

goset Set is a useful collection but there is no built-in implementation in Go lang. Why? The only one pkg which provides set operations now is golang

zoumo 46 Apr 4, 2022
Set data structure for Go

Archived project. No maintenance. This project is not maintained anymore and is archived.. Please create your own map[string]Type or use one of the ot

Fatih Arslan 647 Jun 22, 2022
Set data structure for Go

Archived project. No maintenance. This project is not maintained anymore and is archived.. Please create your own map[string]Type or use one of the ot

Fatih Arslan 647 Jun 22, 2022