ring

README

ring - high performance bloom filter

Package ring provides a high performance and thread safe Go implementation of a bloom filter.

Usage

Please see the godoc for usage.

Accuracy

Running make will perform unit tests, comparing the target false positive rate with the actual rate. Here is a test against 1 million elements with a targeted false positive rate of 0.1%. Tests fail if the number of false positives exceeds the target.

=== RUN   TestBadParameters
--- PASS: TestBadParameters (0.00s)
=== RUN   TestReset
--- PASS: TestReset (0.26s)
=== RUN   TestData
--- PASS: TestData (14.07s)
=== RUN   TestMerge
--- PASS: TestMerge (13.78s)
=== RUN   TestMarshal
--- PASS: TestMarshal (14.48s)
PASS
>> Number of elements:  1000000
>> Target false positive rate:  0.001000
>> Number of false positives:  99
>> Actual false positive rate:  0.000099
>> Number of false negatives:  0
>> Actual false negative rate:  0.000000
>> Benchmark Add():  10000000          158 ns/op
>> Benchmark Test():  10000000         173 ns/op
ok      command-line-arguments  47.914s

License

Copyright (c) 2019 Tanner Ryan. All rights reserved. Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.

Documentation

Overview

Package ring provides a high performance and thread safe bloom filter.

License

Copyright (c) 2019 Tanner Ryan. All rights reserved. Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.

Index

• type Bloom
  • func Init(elements int, falsePositive float64) (*Bloom, error)
  • func InitByParameters(size, hashFunctions uint64) (*Bloom, error)
  • func (r *Bloom) Add(data []byte)
  • func (r *Bloom) BufferSize() int
  • func (r *Bloom) GetHashOpCount() uint64
  • func (r *Bloom) GetSize() uint64
  • func (r *Bloom) MarshalBinary() ([]byte, error)
  • func (r *Bloom) MarshalStorage() ([]byte, error)
  • func (r *Bloom) Merge(m *Bloom) error
  • func (r *Bloom) Reset()
  • func (r *Bloom) Test(data []byte) bool
  • func (r *Bloom) UnmarshalBinary(data []byte) error
  • func (r *Bloom) UnmarshalStorage(data []byte) error

Types

type Bloom

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

Bloom contains the information for a ring data store.

func Init

func Init(elements int, falsePositive float64) (*Bloom, error)

Init initializes and returns a new ring, or an error. Given a number of elements, it accurately states if data is not added. Within a falsePositive rate, it will indicate if the data has been added.

func InitByParameters

func InitByParameters(size, hashFunctions uint64) (*Bloom, error)

InitByParameters initializes a bloom filter allowing the user to explicitly set the size of the bit array and the amount of hash functions

func (*Bloom) Add

func (r *Bloom) Add(data []byte)

Add adds the data to the ring.

func (*Bloom) BufferSize

func (r *Bloom) BufferSize() int

BufferSize returns the size of the buffer the filter is using, in bytes this is the same size as the outputted buffer from Bloom.MarshalStorage

func (*Bloom) GetHashOpCount

func (r *Bloom) GetHashOpCount() uint64

Returns the number the hash operations

func (*Bloom) GetSize

func (r *Bloom) GetSize() uint64

Returns the size of the bloom filter.

func (*Bloom) MarshalBinary

func (r *Bloom) MarshalBinary() ([]byte, error)

MarshalBinary implements the encoding.BinaryMarshaler interface.

func (*Bloom) MarshalStorage

func (r *Bloom) MarshalStorage() ([]byte, error)

MarshalStorage is a marshal function which returns the bit array only, excluding extraneous information of the bloom filter. Included for efficient DB storage purposes

func (*Bloom) Merge

func (r *Bloom) Merge(m *Bloom) error

Merges the sent Bloom into itself.

func (*Bloom) Reset

func (r *Bloom) Reset()

Reset clears the ring.

func (*Bloom) Test

func (r *Bloom) Test(data []byte) bool

Test returns a bool if the data is in the ring. True indicates that the data may be in the ring, while false indicates that the data is not in the ring.

func (*Bloom) UnmarshalBinary

func (r *Bloom) UnmarshalBinary(data []byte) error

UnmarshalBinary implements the encoding.BinaryUnmarshaler interface.

func (*Bloom) UnmarshalStorage

func (r *Bloom) UnmarshalStorage(data []byte) error

UnmarshalStorage is an unmarshal function which populates passed in data into the bloom filters bit array. The stored data must be sized for this filter and be created with the same filter parameters, misconfigurations will not be caught Included for efficient DB storage purpose.