-
Notifications
You must be signed in to change notification settings - Fork 3
/
Copy pathgroupktbloomfilter_GEN_.go
134 lines (117 loc) · 4.16 KB
/
groupktbloomfilter_GEN_.go
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
package store
import (
"encoding/binary"
"fmt"
"math"
"github.com/spaolacci/murmur3"
)
const _GROUP_KT_BLOOM_FILTER_HEADER_BYTES int = 20
// groupKTBloomFilter is a key+timestamp bloom filter implementation.
type groupKTBloomFilter struct {
n uint64
p float64
salt uint32
m uint32
kDiv4 uint32
bits []byte
scratch []byte
}
func newGroupKTBloomFilter(n uint64, p float64, salt uint16) *groupKTBloomFilter {
m := -((float64(n) * math.Log(p)) / math.Pow(math.Log(2), 2))
return &groupKTBloomFilter{
n: n,
p: p,
salt: uint32(salt) << 16,
m: uint32(math.Ceil(m/8)) * 8,
kDiv4: uint32(math.Ceil(m / float64(n) * math.Log(2) / 4)),
bits: make([]byte, uint32(math.Ceil(m/8))),
// salt:4, keyA:8, keyB:8, childKeyA:8, childKeyB:8, timestamp:8
scratch: make([]byte, 44),
}
}
func newGroupKTBloomFilterFromMsg(prm *groupPullReplicationMsg, headerOffset int) *groupKTBloomFilter {
n := binary.BigEndian.Uint64(prm.header[headerOffset:])
p := math.Float64frombits(binary.BigEndian.Uint64(prm.header[headerOffset+8:]))
salt := binary.BigEndian.Uint16(prm.header[headerOffset+16:])
m := -((float64(n) * math.Log(p)) / math.Pow(math.Log(2), 2))
return &groupKTBloomFilter{
n: n,
p: p,
salt: uint32(salt) << 16,
m: uint32(math.Ceil(m/8)) * 8,
kDiv4: uint32(math.Ceil(m / float64(n) * math.Log(2) / 4)),
bits: prm.body,
// salt:4, keyA:8, keyB:8, childKeyA:8, childKeyB:8, timestamp:8
scratch: make([]byte, 44),
}
}
func (ktbf *groupKTBloomFilter) toMsg(prm *groupPullReplicationMsg, headerOffset int) {
binary.BigEndian.PutUint64(prm.header[headerOffset:], ktbf.n)
binary.BigEndian.PutUint64(prm.header[headerOffset+8:], math.Float64bits(ktbf.p))
binary.BigEndian.PutUint16(prm.header[headerOffset+16:], uint16(ktbf.salt>>16))
copy(prm.body, ktbf.bits)
}
func (ktbf *groupKTBloomFilter) String() string {
return fmt.Sprintf("groupKTBloomFilter %p n=%d p=%f salt=%d m=%d k=%d bytes=%d", ktbf, ktbf.n, ktbf.p, ktbf.salt>>16, ktbf.m, ktbf.kDiv4*4, len(ktbf.bits))
}
func (ktbf *groupKTBloomFilter) add(keyA uint64, keyB uint64, childKeyA uint64, childKeyB uint64, timestamp uint64) {
// CONSIDER: There are optimization opportunities here as the keys can be
// considered to already have good bit distribution and using a hashing
// function to mix-in timestamp, salt, and i instead of redoing the whole
// hash each time would be good to test and benchmark.
scratch := ktbf.scratch
binary.BigEndian.PutUint64(scratch[4:], keyA)
binary.BigEndian.PutUint64(scratch[12:], keyB)
binary.BigEndian.PutUint64(scratch[20:], childKeyA)
binary.BigEndian.PutUint64(scratch[28:], childKeyB)
binary.BigEndian.PutUint64(scratch[36:], timestamp)
for i := ktbf.kDiv4; i > 0; i-- {
binary.BigEndian.PutUint32(scratch, ktbf.salt|i)
h1, h2 := murmur3.Sum128(scratch)
bit := uint32(h1>>32) % ktbf.m
ktbf.bits[bit/8] |= 1 << (bit % 8)
bit = uint32(h1&0xffffffff) % ktbf.m
ktbf.bits[bit/8] |= 1 << (bit % 8)
bit = uint32(h2>>32) % ktbf.m
ktbf.bits[bit/8] |= 1 << (bit % 8)
bit = uint32(h2&0xffffffff) % ktbf.m
ktbf.bits[bit/8] |= 1 << (bit % 8)
}
}
func (ktbf *groupKTBloomFilter) mayHave(keyA uint64, keyB uint64, childKeyA uint64, childKeyB uint64, timestamp uint64) bool {
scratch := ktbf.scratch
binary.BigEndian.PutUint64(scratch[4:], keyA)
binary.BigEndian.PutUint64(scratch[12:], keyB)
binary.BigEndian.PutUint64(scratch[20:], childKeyA)
binary.BigEndian.PutUint64(scratch[28:], childKeyB)
binary.BigEndian.PutUint64(scratch[36:], timestamp)
for i := ktbf.kDiv4; i > 0; i-- {
binary.BigEndian.PutUint32(scratch, ktbf.salt|i)
h1, h2 := murmur3.Sum128(scratch)
bit := uint32(h1>>32) % ktbf.m
if ktbf.bits[bit/8]&(1<<(bit%8)) == 0 {
return false
}
bit = uint32(h1&0xffffffff) % ktbf.m
if ktbf.bits[bit/8]&(1<<(bit%8)) == 0 {
return false
}
bit = uint32(h2>>32) % ktbf.m
if ktbf.bits[bit/8]&(1<<(bit%8)) == 0 {
return false
}
bit = uint32(h2&0xffffffff) % ktbf.m
if ktbf.bits[bit/8]&(1<<(bit%8)) == 0 {
return false
}
}
return true
}
func (ktbf *groupKTBloomFilter) reset(salt uint16) {
b := ktbf.bits
l := len(b)
for i := 0; i < l; i++ {
b[i] = 0
}
ktbf.salt = uint32(salt) << 16
}