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

Overview

ring - high performance bloom filter

Build Status codecov Go Report Card PkgGoDev GitHub license Mentioned in Awesome Go

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.

Comments
  • Module path should be

    Module path should be "github.com/TheTannerRyan/ring", not "github.com/thetannerryan/ring"

    Background

    Module path is inconsistent with go import path. GO111MODULE=on, as doc said, import "github.com/TheTannerRyan/ring", then get this error:

    go: finding module for package github.com/TheTannerRyan/ring
    go: downloading github.com/TheTannerRyan/ring v1.1.1
    go: found github.com/TheTannerRyan/ring in github.com/TheTannerRyan/ring v1.1.1
    go: test1 imports
            github.com/TheTannerRyan/ring: github.com/TheTannerRyan/[email protected]: parsing go.mod:
            module declares its path as: github.com/thetannerryan/ring
                    but was required as: github.com/TheTannerRyan/ring 
    

    Solution

    Fix the module path:

    1. Rename the module path to "github.com/TheTannerRyan/ring": https://github.com/TheTannerRyan/ring/blob/master/go.mod#L1
    module github.com/TheTannerRyan/ring
    go 1.12 
    
    1. Consider reverting the thetannerryan -> TheTannerRyan rename.
    2. Change the doc document to use import "github.com/thetannerryan/ring".
    opened by KateGo520 5
  • The bitset doesn't return the 0s and 1s

    The bitset doesn't return the 0s and 1s

    Hello! Sorry for concerning, but can't understand why Marshal.Binary returns [1 0 0 0 0 0 0 3 191 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 32 0 0 0 0 0 0 0 0 32 0 0 128 16 0 0 0 0 0 0 0 36 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 16 0 0 0 0 0 0 0 4 0 0 0 64 0 0 0 0 0 0 16 0 64 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0] this, fro where this numbers "191, 3,36, ...", Bloom Filter isn't bitset which should give "101010101" this type of bitset? Thank you in advance.

    opened by Agipa 4
  • Added Merge, MarshalBinary, UnmarshalBinary

    Added Merge, MarshalBinary, UnmarshalBinary

    We need to be able to merge multiple different Ring's from different hours of data since we process our data in hourly chunks concurrently. The Marshal/Unmarshal methods will be necessary so we can store already-processed hours in a database so we don't need to re-compute them all of the time.

    I added tests to test the Merge and Marshal methods but I made them separate tests. They're still ran by TestMain but they don't affect the stats output.

    /cc @TheTannerRyan

    opened by jameshartig 2
  • generateMultiHash changes source byte array

    generateMultiHash changes source byte array

    unit test below fails

    func TestRing(t *testing.T) {
            assert := assert.New(t)
    
            filter, err := ring.Init(1000, 0.03)
            assert.NoError(err)
    
            b := []byte{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}
            d := []byte{0x77, 0x50, 0x52, 0x48, 0x57, 0x32, 0x32, 0x77}
    
            copy(b, d)
            assert.False(filter.Test(b[:3]))
            assert.Equal(b, d)
    
            copy(b, d)
            filter.Add(b[:3])
            assert.Equal(b, d)
    
            copy(b, d)
            filter.Add(b[:3])
            assert.Equal(b, d)
    
    }
    

    part of output:

                    Error:          Not equal:
                                    expected: []byte{0x77, 0x50, 0x52, 0x1, 0x57, 0x32, 0x32, 0x77}
                                    actual  : []byte{0x77, 0x50, 0x52, 0x48, 0x57, 0x32, 0x32, 0x77}
    
                                    Diff:
                                    --- Expected
                                    +++ Actual
                                    @@ -1,3 +1,3 @@
                                     ([]uint8) (len=8) {
                                    - 00000000  77 50 52 01 57 32 32 77                           |wPR.W22w|
                                    + 00000000  77 50 52 48 57 32 32 77                           |wPRHW22w|
                                     }
                    Test:           TestRing
    
    

    It caused by this line:

    h3, h4 := murmur128(append(data, single))
    
    opened by xnum 0
  • Add parameterizable Init funciton

    Add parameterizable Init funciton

    I am an engineer at Elixxir, and we are considering using your bloom filter as part of our system. However, we want to use a more customizable bloom filter, in which we can input our own values for the size of the bit array and the number of hash rounds.Thus, we are presenting this pull request to you for your consideration.

    opened by joshem 0
Releases(v1.1.2)
Owner
Tanner Ryan
DevOps Engineer @fyelabs. Cyborg. Network and security stuff. Flowing with @golang.
Tanner Ryan
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 26 Jul 4, 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
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 952 Jan 4, 2023
go/golang: fast bit set Bloom filter

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

Andreas Briese 125 Nov 3, 2022
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 42 Aug 24, 2022
A bloom filter is a probabilistic data structure that is used to determine if an element is present in a set

A Go implementation of a bloom filter, with support for boltdb and badgerdb as optional in-memory persistent storage.

Samsondeen 26 Jul 4, 2022
go.fifo provides a simple fifo thread-safe queue for the Go programming language

go.fifo Description go.fifo provides a simple FIFO thread-safe queue. *fifo.Queue supports pushing an item at the end with Add(), and popping an item

Foize 42 Aug 29, 2022
A simple and efficient thread-safe sharded hashmap for Go

shardmap A simple and efficient thread-safe sharded hashmap for Go. This is an alternative to the standard Go map and sync.Map, and is optimized for w

Josh Baker 192 Dec 17, 2022
A thread safe map which has expiring key-value pairs

~ timedmap ~ A map which has expiring key-value pairs. go get github.com/zekroTJA/timedmap Intro This package allows to set values to a map which will

zekro 51 Dec 29, 2022
A Golang lock-free thread-safe HashMap optimized for fastest read access.

hashmap Overview A Golang lock-free thread-safe HashMap optimized for fastest read access. Usage Set a value for a key in the map: m := &HashMap{} m.S

Cornel 1.4k Dec 30, 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.8k Dec 30, 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.8k Dec 28, 2022
Fast ring-buffer deque (double-ended queue)

deque Fast ring-buffer deque (double-ended queue) implementation. For a pictorial description, see the Deque diagram Installation $ go get github.com/

Andrew Gillis 412 Dec 26, 2022
Fast golang queue using ring-buffer

Queue A fast Golang queue using a ring-buffer, based on the version suggested by Dariusz Górecki. Using this instead of other, simpler, queue implemen

Evan Huus 478 Jan 3, 2023
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 feature complete and high performance multi-group Raft library in Go.

Dragonboat - A Multi-Group Raft library in Go / 中文版 News 2021-01-20 Dragonboat v3.3 has been released, please check CHANGELOG for all changes. 2020-03

lni 4.5k Jan 5, 2023
High-performance minimalist queue implemented using a stripped-down lock-free ringbuffer, written in Go (golang.org)

This project is no longer maintained - feel free to fork the project! gringo A high-performance minimalist queue implemented using a stripped-down loc

Darren Elwood 129 Oct 24, 2022
skipmap is a high-performance concurrent sorted map based on skip list. Up to 3x ~ 10x faster than sync.Map in the typical pattern.

Introduction skipmap is a high-performance concurrent map based on skip list. In typical pattern(one million operations, 90%LOAD 9%STORE 1%DELETE), th

ZhangYunHao 106 Jan 8, 2023
go-fasttld is a high performance top level domains (TLD) extraction module.

go-fasttld go-fasttld is a high performance top level domains (TLD) extraction module implemented with compressed tries. This module is a port of the

Wu Tingfeng 13 Dec 21, 2022