DBF

README

The Distributed Bloom Filter

The Distributed Bloom Filter is a space-efficient, probabilistic data structure designed to perform more efficient set reconciliations in distributed systems. It guarantees eventual consistency of states between nodes in a system, while still keeping bloom filter sizes as compact as possible. The eventuality can be tweaked as desired, by tweaking the distributed bloom filter’s parameters. The scalability, as well as accuracy of the data structure is made possible by combining two novel ideas: The first idea introduces a new, computationally inexpensive way for populating bloom filters, making it possible to quickly compute new bloom filters when interacting with peers. The second idea introduces the concept of unique bloom filter mappings between peers. By applying these two simple ideas, one can achieve incredibly bandwidth-efficient set reconciliation in networks. Instead of trying to minimize the false positive rate of a single bloom filter, we use the unique bloom filter mappings to increase the probability for an element to propagate through a network. For more information on the distributed bloom filter, please refer to the original paper

Example

To initiate a distributed bloom filter, we need to specify three parameters: n, fpr, and s. n is the number of elements that we want to insert into the distributed bloom filter, fpr is the false positive rate for our bloom filter, and s is an initial seed value that determines the bloom filter mapping. By specifying n and fpr, the DBF automatically determines the bloom filter size m and number of hash functions used k.

dbf := DBF.NewDbf(10, 0.5, []byte("seed"))
element := []byte("something")
dbf.Add(element)

Installation

go get github.com/labbloom/DBF

License

Apache-2.0

Documentation

Index

• func EstimateParameters(n uint, fpr float64) (m uint, k uint)
• func VerifyBitArray(dbf *DistBF, elem []byte, b *bitset.BitSet) bool
• type DEncode
• type DistBF
  • func NewDBFBitSet(b *bitset.BitSet) *DistBF
  • func NewDbf(n uint, fpr float64, s []byte) *DistBF
  • func UnmarshalBinary(b []byte) (*DistBF, error)
  • func (dbf *DistBF) Add(element []byte)
  • func (dbf *DistBF) BitArray() *bitset.BitSet
  • func (dbf *DistBF) Bytes() ([]byte, error)
  • func (dbf *DistBF) GetBitIndices() (indices []uint)
  • func (dbf *DistBF) GetElementIndices(elem []byte) (indices []uint)
  • func (dbf *DistBF) MapElementToBF(elem, seedValue []byte) (indices []uint)
  • func (dbf *DistBF) NumOfHashes() uint
  • func (dbf *DistBF) Proof(elem []byte) ([]uint64, bool)
  • func (dbf *DistBF) SetBitSet(b *bitset.BitSet)
  • func (dbf *DistBF) SetIndices(indices []int)
  • func (dbf *DistBF) VerifyElement(elem []byte) bool

Functions

func EstimateParameters

func EstimateParameters(n uint, fpr float64) (m uint, k uint)

EstimateParameters estimates requirements for m and k. Based on https://bitbucket.org/ww/bloom/src/829aa19d01d9/bloom.go

func VerifyBitArray

func VerifyBitArray(dbf *DistBF, elem []byte, b *bitset.BitSet) bool

VerifyBitArray returns true if element is in the other DBF, false otherwise

Types

type DEncode

type DEncode struct {
	B []byte
	M uint
	K uint
	H [][sha512.Size256]byte
}

helper struct to encode DBF to byte

type DistBF

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

DistBF is the dbf struct

func NewDBFBitSet

func NewDBFBitSet(b *bitset.BitSet) *DistBF

func NewDbf

func NewDbf(n uint, fpr float64, s []byte) *DistBF

NewDbf function return the DBF generated from the sizes of to peers

func UnmarshalBinary

func UnmarshalBinary(b []byte) (*DistBF, error)

func (*DistBF) Add

func (dbf *DistBF) Add(element []byte)

Add element to DBF

func (*DistBF) BitArray

func (dbf *DistBF) BitArray() *bitset.BitSet

func (*DistBF) Bytes

func (dbf *DistBF) Bytes() ([]byte, error)

func (*DistBF) GetBitIndices

func (dbf *DistBF) GetBitIndices() (indices []uint)

GetBitIndices returns the indices of every 1 in the dbf

func (*DistBF) GetElementIndices

func (dbf *DistBF) GetElementIndices(elem []byte) (indices []uint)

GetElementIndices returns the dbf indices an element would have if mapped to the dbf

func (*DistBF) MapElementToBF

func (dbf *DistBF) MapElementToBF(elem, seedValue []byte) (indices []uint)

MapElementToBF returns the indices an element would have if mapped to a dbf, but with a different seedValue

func (*DistBF) NumOfHashes

func (dbf *DistBF) NumOfHashes() uint

func (*DistBF) Proof

func (dbf *DistBF) Proof(elem []byte) ([]uint64, bool)

Proof returns true if element is in DBF, false otherwise

func (*DistBF) SetBitSet

func (dbf *DistBF) SetBitSet(b *bitset.BitSet)

func (*DistBF) SetIndices

func (dbf *DistBF) SetIndices(indices []int)

SetIndices increments bit array values without inserting an element.

func (*DistBF) VerifyElement

func (dbf *DistBF) VerifyElement(elem []byte) bool

VerifyElement returns true if element is in DBF, false otherwise