My favorites | Sign in
Project Home Downloads Wiki Issues Source
Repository:
Checkout   Browse   Changes   Clones  
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
// Copyright (c) 2012 The LevelDB Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file. See the AUTHORS file for names of contributors.

#include "leveldb/filter_policy.h"

#include "util/coding.h"
#include "util/logging.h"
#include "util/testharness.h"
#include "util/testutil.h"

namespace leveldb {

static const int kVerbose = 1;

static Slice Key(int i, char* buffer) {
EncodeFixed32(buffer, i);
return Slice(buffer, sizeof(uint32_t));
}

class BloomTest {
private:
const FilterPolicy* policy_;
std::string filter_;
std::vector<std::string> keys_;

public:
BloomTest() : policy_(NewBloomFilterPolicy(10)) { }

~BloomTest() {
delete policy_;
}

void Reset() {
keys_.clear();
filter_.clear();
}

void Add(const Slice& s) {
keys_.push_back(s.ToString());
}

void Build() {
std::vector<Slice> key_slices;
for (size_t i = 0; i < keys_.size(); i++) {
key_slices.push_back(Slice(keys_[i]));
}
filter_.clear();
policy_->CreateFilter(&key_slices[0], key_slices.size(), &filter_);
keys_.clear();
if (kVerbose >= 2) DumpFilter();
}

size_t FilterSize() const {
return filter_.size();
}

void DumpFilter() {
fprintf(stderr, "F(");
for (size_t i = 0; i+1 < filter_.size(); i++) {
const unsigned int c = static_cast<unsigned int>(filter_[i]);
for (int j = 0; j < 8; j++) {
fprintf(stderr, "%c", (c & (1 <<j)) ? '1' : '.');
}
}
fprintf(stderr, ")\n");
}

bool Matches(const Slice& s) {
if (!keys_.empty()) {
Build();
}
return policy_->KeyMayMatch(s, filter_);
}

double FalsePositiveRate() {
char buffer[sizeof(int)];
int result = 0;
for (int i = 0; i < 10000; i++) {
if (Matches(Key(i + 1000000000, buffer))) {
result++;
}
}
return result / 10000.0;
}
};

TEST(BloomTest, EmptyFilter) {
ASSERT_TRUE(! Matches("hello"));
ASSERT_TRUE(! Matches("world"));
}

TEST(BloomTest, Small) {
Add("hello");
Add("world");
ASSERT_TRUE(Matches("hello"));
ASSERT_TRUE(Matches("world"));
ASSERT_TRUE(! Matches("x"));
ASSERT_TRUE(! Matches("foo"));
}

static int NextLength(int length) {
if (length < 10) {
length += 1;
} else if (length < 100) {
length += 10;
} else if (length < 1000) {
length += 100;
} else {
length += 1000;
}
return length;
}

TEST(BloomTest, VaryingLengths) {
char buffer[sizeof(int)];

// Count number of filters that significantly exceed the false positive rate
int mediocre_filters = 0;
int good_filters = 0;

for (int length = 1; length <= 10000; length = NextLength(length)) {
Reset();
for (int i = 0; i < length; i++) {
Add(Key(i, buffer));
}
Build();

ASSERT_LE(FilterSize(), static_cast<size_t>((length * 10 / 8) + 40))
<< length;

// All added keys must match
for (int i = 0; i < length; i++) {
ASSERT_TRUE(Matches(Key(i, buffer)))
<< "Length " << length << "; key " << i;
}

// Check false positive rate
double rate = FalsePositiveRate();
if (kVerbose >= 1) {
fprintf(stderr, "False positives: %5.2f%% @ length = %6d ; bytes = %6d\n",
rate*100.0, length, static_cast<int>(FilterSize()));
}
ASSERT_LE(rate, 0.02); // Must not be over 2%
if (rate > 0.0125) mediocre_filters++; // Allowed, but not too often
else good_filters++;
}
if (kVerbose >= 1) {
fprintf(stderr, "Filters: %d good, %d mediocre\n",
good_filters, mediocre_filters);
}
ASSERT_LE(mediocre_filters, good_filters/5);
}

// Different bits-per-byte

} // namespace leveldb

int main(int argc, char** argv) {
return leveldb::test::RunAllTests();
}

Change log

0cfb990d58ff by David Grogan <dgro...@chromium.org> on Dec 10, 2013   Diff
Release LevelDB 1.15

- switched from mmap based writing to
simpler stdio based writing. Has a
  minor impact (0.5 microseconds) on
microbenchmarks for asynchronous
  writes. Synchronous writes speed up from
30ms to 10ms on linux/ext4.
  Should be much more reliable on diverse
platforms.
- compaction errors now immediately put
the database into a read-only
...
Go to: 
Project members, sign in to write a code review

Older revisions

946e5b5a4ce7 by David Grogan <dgro...@chromium.org> on Oct 12, 2012   Diff
Update to leveldb 1.6

Highlights
----------
Mmap at most 1000 files on Posix to
...
85584d497e7b by Sanjay Ghemawat <san...@google.com> on Apr 17, 2012   Diff
Added bloom filter support.

In particular, we add a new
FilterPolicy class.  An instance
of this class can be supplied in
...
All revisions of this file

File info

Size: 3788 bytes, 161 lines
Powered by Google Project Hosting