This repository has been archived by the owner on Jul 30, 2019. It is now read-only.
/
bloom_filter.go
92 lines (79 loc) · 2.52 KB
/
bloom_filter.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
// Copyright (C) 2018 MediBloc
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program. If not, see <https://www.gnu.org/licenses/>
package net
import (
"fmt"
"sync"
"github.com/medibloc/go-medibloc/util/logging"
"github.com/sirupsen/logrus"
"github.com/willf/bloom"
)
const (
// according to https://krisives.github.io/bloom-calculator/
// Count (n) = 100000, Error (p) = 0.001
maxCountOfRecvMessageInBloomFiler = 1000000
bloomFilterOfRecvMessageArgM = 14377588
bloomFilterOfRecvMessageArgK = 10
)
// BloomFilter manages bloom filter
type BloomFilter struct {
argM uint
argK uint
bloomFilter *bloom.BloomFilter
bloomFilterMutex sync.Mutex
counts int
maxCounts int
}
// NewBloomFilter returns BloomFilter
func NewBloomFilter(m uint, k uint, maxCount int) *BloomFilter {
return &BloomFilter{
argM: m,
argK: k,
bloomFilter: bloom.New(m, k),
counts: 0,
maxCounts: maxCount,
}
}
// RecordKey add key to bloom filter.
func (bf *BloomFilter) RecordKey(key string) {
bf.bloomFilterMutex.Lock()
defer bf.bloomFilterMutex.Unlock()
bf.counts++
if bf.counts > bf.maxCounts {
// reset.
logging.WithFields(logrus.Fields{
"countOfBloomFilter": bf.counts,
}).Debug("reset bloom filter.")
bf.counts = 0
bf.bloomFilter = bloom.New(bf.argM, bf.argK)
}
bf.bloomFilter.AddString(key)
}
// HasKey use bloom filter to check if the key exists quickly
func (bf *BloomFilter) HasKey(key string) bool {
bf.bloomFilterMutex.Lock()
defer bf.bloomFilterMutex.Unlock()
return bf.bloomFilter.TestString(key)
}
// HasRecvMessage use bloom filter sender check if the key exists quickly
func (bf *BloomFilter) HasRecvMessage(msg *SendMessage) bool {
key := fmt.Sprintf("%s-%v", msg.receiver.Pretty(), msg.Hash())
return bf.HasKey(key)
}
// RecordRecvMessage records received message
func (bf *BloomFilter) RecordRecvMessage(msg *RecvMessage) {
key := fmt.Sprintf("%s-%v", msg.sender.Pretty(), msg.Hash())
bf.RecordKey(key)
}