Repository navigation
Expand file tree
/
Copy pathbloom.go
More file actions
210 lines (180 loc) · 5.87 KB
/
Copy pathbloom.go
File metadata and controls
210 lines (180 loc) · 5.87 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
/*
Package bloom provides data structures and methods for creating 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 is a
member of a set.
A Bloom filter has two parameters: _m_, a maximum size (typically a reasonably large
multiple of the cardinality of the set to represent) and _k_, the number of hashing
functions on elements of the set. (The actual hashing functions are important, too,
but this is not a parameter for this implementation). A Bloom filter is backed by
a BitSet; a key is represented in the filter by setting the bits at each value of the
hashing functions (modulo _m_). Set membership is done by _testing_ whether the
bits at each value of the hashing functions (again, modulo _m_) are set. If so,
the item is in the set. If the item is actually in the set, a Bloom filter will
never fail (the true positive rate is 1.0); but it is susceptible to false
positives. The art is to choose _k_ and _m_ correctly.
In this implementation, the hashing functions used is murmurhash,
a non-cryptographic hashing function.
This implementation accepts keys for setting as testing as []byte. Thus, to
add a string item, "Love":
uint n = 1000
filter := bloom.New(20*n, 5) // load of 20, 5 keys
filter.Add([]byte("Love"))
Similarly, to test if "Love" is in bloom:
if filter.Test([]byte("Love"))
*/
package bloom
import (
"math"
"github.com/m3db/bitset"
)
func bloomFilterLocation(h [4]uint64, i, m uint64) uint {
v := h[i%2] + i*h[2+(((i+(i%2))%4)/2)]
return uint(v % m)
}
// BloomFilter is a bloom filter set membership.
// It cannot be concurrently read or written to. Multiple concurrent readers
// is also unsafe so a sync.Mutex must be used to guard read/write access if
// desired. This is due to a cached hash digest being used to avoid
// allocation each read/write.
type BloomFilter struct {
m uint64
k uint64
set *bitset.BitSet
}
// NewBloomFilter creates a new bloom filter that can represent
// m elements with k hashes. It is not concurrent read or write safe.
func NewBloomFilter(m uint, k uint) *BloomFilter {
if m < 1 {
m = 1
}
if k < 1 {
k = 1
}
return &BloomFilter{
m: uint64(m),
k: uint64(k),
set: bitset.NewBitSet(m),
}
}
// EstimateFalsePositiveRate estimates m and k, based on:
// https://stackoverflow.com/a/22467497
func EstimateFalsePositiveRate(n uint, p float64) (m uint, k uint) {
floatM := (float64(-1) * float64(n) * math.Log(p)) / (math.Pow(math.Log(2), 2))
floatK := (floatM / float64(n)) * math.Log(2)
m, k = uint(math.Ceil(floatM)), uint(math.Ceil(floatK))
return
}
// Add value to the set.
func (b *BloomFilter) Add(value []byte) {
h := sum128WithEntropy(value)
for i := uint64(0); i < b.k; i++ {
b.set.Set(bloomFilterLocation(h, i, b.m))
}
}
// Test if value is in the set.
func (b *BloomFilter) Test(value []byte) bool {
h := sum128WithEntropy(value)
for i := uint64(0); i < b.k; i++ {
if !b.set.Test(bloomFilterLocation(h, i, b.m)) {
return false
}
}
return true
}
// M returns the m elements represented.
func (b *BloomFilter) M() uint {
return uint(b.m)
}
// K returns the k hashes used.
func (b *BloomFilter) K() uint {
return uint(b.k)
}
// BitSet returns the bitset used.
func (b *BloomFilter) BitSet() *bitset.BitSet {
return b.set
}
// ReadOnlyBloomFilter is a read only bloom filter set membership.
// It cannot be concurrently read or written to. Multiple concurrent readers
// is also unsafe so a sync.Mutex must be used to guard read/write access if
// desired. This is due to a cached hash digest being used to avoid
// allocation each read/write.
type ReadOnlyBloomFilter struct {
m uint64
k uint64
set *bitset.ReadOnlyBitSet
}
// NewReadOnlyBloomFilter returns a new read only bloom filter backed
// by a byte slice, this means it can be used with a mmap'd bytes ref.
// It is not concurrent read or write safe.
func NewReadOnlyBloomFilter(m, k uint, data []byte) *ReadOnlyBloomFilter {
return &ReadOnlyBloomFilter{
m: uint64(m),
k: uint64(k),
set: bitset.NewReadOnlyBitSet(data),
}
}
// Test if value is in the set.
func (b *ReadOnlyBloomFilter) Test(value []byte) bool {
h := sum128WithEntropy(value)
for i := uint64(0); i < b.k; i++ {
if !b.set.Test(bloomFilterLocation(h, i, b.m)) {
return false
}
}
return true
}
// M returns the m elements represented.
func (b *ReadOnlyBloomFilter) M() uint {
return uint(b.m)
}
// K returns the k hashes used.
func (b *ReadOnlyBloomFilter) K() uint {
return uint(b.k)
}
// BitSet returns the bitset used.
func (b *ReadOnlyBloomFilter) BitSet() *bitset.ReadOnlyBitSet {
return b.set
}
// ConcurrentReadOnlyBloomFilter is a concurrent read only bloom filter set
// membership. It can be concurrently read from by any number of readers.
type ConcurrentReadOnlyBloomFilter struct {
m uint64
k uint64
set *bitset.ReadOnlyBitSet
}
// NewConcurrentReadOnlyBloomFilter returns a new concurrent read only bloom
// filter backed by a byte slice, this means it can be used with a mmap'd
// bytes ref. It can be concurrently read from by any number of readers.
func NewConcurrentReadOnlyBloomFilter(
m, k uint,
data []byte,
) *ConcurrentReadOnlyBloomFilter {
return &ConcurrentReadOnlyBloomFilter{
m: uint64(m),
k: uint64(k),
set: bitset.NewReadOnlyBitSet(data),
}
// Test if value is in the set.
func (b *ConcurrentReadOnlyBloomFilter) Test(value []byte) bool {
h := sum128WithEntropy(value)
for i := uint64(0); i < b.k; i++ {
if !b.set.Test(bloomFilterLocation(h, i, b.m)) {
return false
}
}
return true
}
// M returns the m elements represented.
func (b *ConcurrentReadOnlyBloomFilter) M() uint {
return uint(b.m)
}
// K returns the k hashes used.
func (b *ConcurrentReadOnlyBloomFilter) K() uint {
return uint(b.k)
}
// BitSet returns the bitset used.
func (b *ConcurrentReadOnlyBloomFilter) BitSet() *bitset.ReadOnlyBitSet {
return b.set
}