bloomfilter

package module

v0.0.0-...-6819c0d Latest Latest Go to latest Published: Sep 22, 2018 License: MIT Imports: 18 Imported by: 246

Details

Valid go.mod file

The Go module system was introduced in Go 1.11 and is the official dependency management solution for Go.
Redistributable license

Redistributable licenses place minimal restrictions on how software can be used, modified, and redistributed.
Tagged version

Modules with tagged versions give importers more predictable builds.
Stable version

When a project reaches major version v1 it is considered stable.
Learn more about best practices

Repository

github.com/steakknife/bloomfilter

Links

Open Source Insights

README ¶

Important: Zeroth, consider if a Cuckoo filter could be right for your use-case.

Face-meltingly fast, thread-safe, marshalable, unionable, probability- and optimal-size-calculating Bloom filter in go

MIT license

WTF is a bloom filter

**TL;DR: **Probabilistic, extra lookup table to track a set of elements kept elsewhere to reduce expensive, unnecessary set element retrieval and/or iterator operations when an element is not present in the set. It's a classic time-storage tradeoff algoritm.

Properties

See wikipedia for algorithm details

Impact	What	Description
Good	No false negatives	know for certain if a given element is definitely NOT in the set
Bad	False positives	uncertain if a given element is in the set
Bad	Theoretical potential for hash collisions	in very large systems and/or badly hash.Hash64-conforming implementations
Bad	Add only	Cannot remove an element, it would destroy information about other elements
Good	Constant storage	uses only a fixed amount of memory

Naming conventions

(Similar to algorithm)

Variable/function	Description	Range
m/M()	number of bits in the bloom filter (memory representation is about m/8 bytes in size)	>=2
n/N()	number of elements present	>=0
k/K()	number of keys to use (keys are kept private to user code but are de/serialized to Marshal and file I/O)	>=0
maxN	maximum capacity of intended structure	>0
p	maximum allowed probability of collision (for computing m and k for optimal sizing)	>0..<1

Memory representation should be exactly 24 + 8*(k + (m+63)/64) + unsafe.Sizeof(RWMutex) bytes.
Serialized (BinaryMarshaler) representation should be exactly 72 + 8*(k + (m+63)/64) bytes. (Disk format is less due to compression.)

Binary serialization format

All values in Little-endian format

Offset	Offset (Hex)	Length (bytes)	Name	Type
0	00	8	k	`uint64`
8	08	8	n	`uint64`
16	10	8	m	`uint64`
24	18	k	(keys)	`[k]uint64`
24+8*k	...	(m+63)/64	(bloom filter)	`[(m+63)/64]uint64`
24+8k+8((m+63)/64)	...	48	(SHA384 of all previous fields, hashed in order)	`[48]byte`

bloomfilter.Filter conforms to encoding.BinaryMarshaler and `encoding.BinaryUnmarshaler'

Usage


import "github.com/steakknife/bloomfilter"

const (
  maxElements = 100000
  probCollide = 0.0000001
)

bf, err := bloomfilter.NewOptimal(maxElements, probCollide)
if err != nil {
  panic(err)
}

someValue := ... // must conform to hash.Hash64

bf.Add(someValue)
if bf.Contains(someValue) { // probably true, could be false
  // whatever
}

anotherValue := ... // must also conform to hash.Hash64

if bf.Contains(anotherValue) {
  panic("This should never happen")
}

err := bf.WriteFile("1.bf.gz")  // saves this BF to a file
if err != nil {
  panic(err)
}

bf2, err := bloomfilter.ReadFile("1.bf.gz") // read the BF to another var
if err != nil {
  panic(err)
}

Design

Where possible, branch-free operations are used to avoid deep pipeline / execution unit stalls on branch-misses.

Get

go get -u github.com/steakknife/bloomfilter  # master is always stable

Source

On the web: https://github.com/steakknife/bloomfilter
Git: git clone https://github.com/steakknife/bloomfilter

Contact

License

MIT license