1 // Copyright (c) 2011-present, Facebook, Inc. All rights reserved.
2 // This source code is licensed under both the GPLv2 (found in the
3 // COPYING file in the root directory) and Apache 2.0 License
4 // (found in the LICENSE.Apache file in the root directory).
8 #include "rocksdb/filter_policy.h"
10 #include "table/full_filter_bits_builder.h"
11 #include "table/index_builder.h"
12 #include "table/partitioned_filter_block.h"
13 #include "util/coding.h"
14 #include "util/hash.h"
15 #include "util/logging.h"
16 #include "util/testharness.h"
17 #include "util/testutil.h"
21 std::map
<uint64_t, Slice
> slices
;
23 class MockedBlockBasedTable
: public BlockBasedTable
{
25 explicit MockedBlockBasedTable(Rep
* rep
) : BlockBasedTable(rep
) {
26 // Initialize what Open normally does as much as necessary for the test
27 rep
->cache_key_prefix_size
= 10;
30 CachableEntry
<FilterBlockReader
> GetFilter(
31 FilePrefetchBuffer
*, const BlockHandle
& filter_blk_handle
,
32 const bool /* unused */, bool /* unused */, GetContext
* /* unused */,
33 const SliceTransform
* prefix_extractor
) const override
{
34 Slice slice
= slices
[filter_blk_handle
.offset()];
35 auto obj
= new FullFilterBlockReader(
36 prefix_extractor
, true, BlockContents(slice
),
37 rep_
->table_options
.filter_policy
->GetFilterBitsReader(slice
), nullptr);
38 return {obj
, nullptr};
41 FilterBlockReader
* ReadFilter(
42 FilePrefetchBuffer
*, const BlockHandle
& filter_blk_handle
,
43 const bool /* unused */,
44 const SliceTransform
* prefix_extractor
) const override
{
45 Slice slice
= slices
[filter_blk_handle
.offset()];
46 auto obj
= new FullFilterBlockReader(
47 prefix_extractor
, true, BlockContents(slice
),
48 rep_
->table_options
.filter_policy
->GetFilterBitsReader(slice
), nullptr);
53 class PartitionedFilterBlockTest
54 : public testing::Test
,
55 virtual public ::testing::WithParamInterface
<uint32_t> {
57 BlockBasedTableOptions table_options_
;
58 InternalKeyComparator icomp
= InternalKeyComparator(BytewiseComparator());
60 PartitionedFilterBlockTest() {
61 table_options_
.filter_policy
.reset(NewBloomFilterPolicy(10, false));
62 table_options_
.no_block_cache
= true; // Otherwise BlockBasedTable::Close
63 // will access variable that are not
64 // initialized in our mocked version
65 table_options_
.format_version
= GetParam();
66 table_options_
.index_block_restart_interval
= 3;
69 std::shared_ptr
<Cache
> cache_
;
70 ~PartitionedFilterBlockTest() override
{}
72 const std::string keys
[4] = {"afoo", "bar", "box", "hello"};
73 const std::string missing_keys
[2] = {"missing", "other"};
75 uint64_t MaxIndexSize() {
76 int num_keys
= sizeof(keys
) / sizeof(*keys
);
77 uint64_t max_key_size
= 0;
78 for (int i
= 1; i
< num_keys
; i
++) {
79 max_key_size
= std::max(max_key_size
, static_cast<uint64_t>(keys
[i
].size()));
81 uint64_t max_index_size
= num_keys
* (max_key_size
+ 8 /*handle*/);
82 return max_index_size
;
85 uint64_t MaxFilterSize() {
86 uint32_t dont_care1
, dont_care2
;
87 int num_keys
= sizeof(keys
) / sizeof(*keys
);
88 auto filter_bits_reader
= dynamic_cast<rocksdb::FullFilterBitsBuilder
*>(
89 table_options_
.filter_policy
->GetFilterBitsBuilder());
90 assert(filter_bits_reader
);
92 filter_bits_reader
->CalculateSpace(num_keys
, &dont_care1
, &dont_care2
);
93 delete filter_bits_reader
;
94 return partition_size
+
95 partition_size
* table_options_
.block_size_deviation
/ 100;
99 BlockHandle
Write(const Slice
& slice
) {
100 BlockHandle
bh(last_offset
+ 1, slice
.size());
101 slices
[bh
.offset()] = slice
;
102 last_offset
+= bh
.size();
106 PartitionedIndexBuilder
* NewIndexBuilder() {
107 const bool kValueDeltaEncoded
= true;
108 return PartitionedIndexBuilder::CreateIndexBuilder(
109 &icomp
, !kValueDeltaEncoded
, table_options_
);
112 PartitionedFilterBlockBuilder
* NewBuilder(
113 PartitionedIndexBuilder
* const p_index_builder
,
114 const SliceTransform
* prefix_extractor
= nullptr) {
115 assert(table_options_
.block_size_deviation
<= 100);
116 auto partition_size
= static_cast<uint32_t>(
117 ((table_options_
.metadata_block_size
*
118 (100 - table_options_
.block_size_deviation
)) +
121 partition_size
= std::max(partition_size
, static_cast<uint32_t>(1));
122 const bool kValueDeltaEncoded
= true;
123 return new PartitionedFilterBlockBuilder(
124 prefix_extractor
, table_options_
.whole_key_filtering
,
125 table_options_
.filter_policy
->GetFilterBitsBuilder(),
126 table_options_
.index_block_restart_interval
, !kValueDeltaEncoded
,
127 p_index_builder
, partition_size
);
130 std::unique_ptr
<MockedBlockBasedTable
> table
;
132 PartitionedFilterBlockReader
* NewReader(
133 PartitionedFilterBlockBuilder
* builder
, PartitionedIndexBuilder
* pib
,
134 const SliceTransform
* prefix_extractor
) {
139 slice
= builder
->Finish(bh
, &status
);
141 } while (status
.IsIncomplete());
142 const Options options
;
143 const ImmutableCFOptions
ioptions(options
);
144 const MutableCFOptions
moptions(options
);
145 const EnvOptions env_options
;
146 const bool kSkipFilters
= true;
147 const bool kImmortal
= true;
148 table
.reset(new MockedBlockBasedTable(
149 new BlockBasedTable::Rep(ioptions
, env_options
, table_options_
, icomp
,
150 !kSkipFilters
, 0, !kImmortal
)));
151 auto reader
= new PartitionedFilterBlockReader(
152 prefix_extractor
, true, BlockContents(slice
), nullptr, nullptr, icomp
,
153 table
.get(), pib
->seperator_is_key_plus_seq(),
154 !pib
->get_use_value_delta_encoding());
158 void VerifyReader(PartitionedFilterBlockBuilder
* builder
,
159 PartitionedIndexBuilder
* pib
, bool empty
= false,
160 const SliceTransform
* prefix_extractor
= nullptr) {
161 std::unique_ptr
<PartitionedFilterBlockReader
> reader(
162 NewReader(builder
, pib
, prefix_extractor
));
163 // Querying added keys
164 const bool no_io
= true;
165 for (auto key
: keys
) {
166 auto ikey
= InternalKey(key
, 0, ValueType::kTypeValue
);
167 const Slice ikey_slice
= Slice(*ikey
.rep());
168 ASSERT_TRUE(reader
->KeyMayMatch(key
, prefix_extractor
, kNotValid
, !no_io
,
172 // querying a key twice
173 auto ikey
= InternalKey(keys
[0], 0, ValueType::kTypeValue
);
174 const Slice ikey_slice
= Slice(*ikey
.rep());
175 ASSERT_TRUE(reader
->KeyMayMatch(keys
[0], prefix_extractor
, kNotValid
,
176 !no_io
, &ikey_slice
));
178 // querying missing keys
179 for (auto key
: missing_keys
) {
180 auto ikey
= InternalKey(key
, 0, ValueType::kTypeValue
);
181 const Slice ikey_slice
= Slice(*ikey
.rep());
183 ASSERT_TRUE(reader
->KeyMayMatch(key
, prefix_extractor
, kNotValid
,
184 !no_io
, &ikey_slice
));
186 // assuming a good hash function
187 ASSERT_FALSE(reader
->KeyMayMatch(key
, prefix_extractor
, kNotValid
,
188 !no_io
, &ikey_slice
));
193 int TestBlockPerKey() {
194 std::unique_ptr
<PartitionedIndexBuilder
> pib(NewIndexBuilder());
195 std::unique_ptr
<PartitionedFilterBlockBuilder
> builder(
196 NewBuilder(pib
.get()));
198 builder
->Add(keys
[i
]);
199 CutABlock(pib
.get(), keys
[i
], keys
[i
+ 1]);
201 builder
->Add(keys
[i
]);
202 CutABlock(pib
.get(), keys
[i
], keys
[i
+ 1]);
204 builder
->Add(keys
[i
]);
205 builder
->Add(keys
[i
]);
206 CutABlock(pib
.get(), keys
[i
], keys
[i
+ 1]);
208 builder
->Add(keys
[i
]);
209 CutABlock(pib
.get(), keys
[i
]);
211 VerifyReader(builder
.get(), pib
.get());
212 return CountNumOfIndexPartitions(pib
.get());
215 void TestBlockPerTwoKeys(const SliceTransform
* prefix_extractor
= nullptr) {
216 std::unique_ptr
<PartitionedIndexBuilder
> pib(NewIndexBuilder());
217 std::unique_ptr
<PartitionedFilterBlockBuilder
> builder(
218 NewBuilder(pib
.get(), prefix_extractor
));
220 builder
->Add(keys
[i
]);
222 builder
->Add(keys
[i
]);
223 CutABlock(pib
.get(), keys
[i
], keys
[i
+ 1]);
225 builder
->Add(keys
[i
]);
226 builder
->Add(keys
[i
]);
228 builder
->Add(keys
[i
]);
229 CutABlock(pib
.get(), keys
[i
]);
231 VerifyReader(builder
.get(), pib
.get(), prefix_extractor
);
234 void TestBlockPerAllKeys() {
235 std::unique_ptr
<PartitionedIndexBuilder
> pib(NewIndexBuilder());
236 std::unique_ptr
<PartitionedFilterBlockBuilder
> builder(
237 NewBuilder(pib
.get()));
239 builder
->Add(keys
[i
]);
241 builder
->Add(keys
[i
]);
243 builder
->Add(keys
[i
]);
244 builder
->Add(keys
[i
]);
246 builder
->Add(keys
[i
]);
247 CutABlock(pib
.get(), keys
[i
]);
249 VerifyReader(builder
.get(), pib
.get());
252 void CutABlock(PartitionedIndexBuilder
* builder
,
253 const std::string
& user_key
) {
254 // Assuming a block is cut, add an entry to the index
256 std::string(*InternalKey(user_key
, 0, ValueType::kTypeValue
).rep());
257 BlockHandle
dont_care_block_handle(1, 1);
258 builder
->AddIndexEntry(&key
, nullptr, dont_care_block_handle
);
261 void CutABlock(PartitionedIndexBuilder
* builder
, const std::string
& user_key
,
262 const std::string
& next_user_key
) {
263 // Assuming a block is cut, add an entry to the index
265 std::string(*InternalKey(user_key
, 0, ValueType::kTypeValue
).rep());
266 std::string next_key
= std::string(
267 *InternalKey(next_user_key
, 0, ValueType::kTypeValue
).rep());
268 BlockHandle
dont_care_block_handle(1, 1);
269 Slice slice
= Slice(next_key
.data(), next_key
.size());
270 builder
->AddIndexEntry(&key
, &slice
, dont_care_block_handle
);
273 int CountNumOfIndexPartitions(PartitionedIndexBuilder
* builder
) {
274 IndexBuilder::IndexBlocks dont_care_ib
;
275 BlockHandle
dont_care_bh(10, 10);
279 s
= builder
->Finish(&dont_care_ib
, dont_care_bh
);
281 } while (s
.IsIncomplete());
282 return cnt
- 1; // 1 is 2nd level index
286 INSTANTIATE_TEST_CASE_P(FormatDef
, PartitionedFilterBlockTest
,
287 testing::Values(test::kDefaultFormatVersion
));
288 INSTANTIATE_TEST_CASE_P(FormatLatest
, PartitionedFilterBlockTest
,
289 testing::Values(test::kLatestFormatVersion
));
291 TEST_P(PartitionedFilterBlockTest
, EmptyBuilder
) {
292 std::unique_ptr
<PartitionedIndexBuilder
> pib(NewIndexBuilder());
293 std::unique_ptr
<PartitionedFilterBlockBuilder
> builder(NewBuilder(pib
.get()));
294 const bool empty
= true;
295 VerifyReader(builder
.get(), pib
.get(), empty
);
298 TEST_P(PartitionedFilterBlockTest
, OneBlock
) {
299 uint64_t max_index_size
= MaxIndexSize();
300 for (uint64_t i
= 1; i
< max_index_size
+ 1; i
++) {
301 table_options_
.metadata_block_size
= i
;
302 TestBlockPerAllKeys();
306 TEST_P(PartitionedFilterBlockTest
, TwoBlocksPerKey
) {
307 uint64_t max_index_size
= MaxIndexSize();
308 for (uint64_t i
= 1; i
< max_index_size
+ 1; i
++) {
309 table_options_
.metadata_block_size
= i
;
310 TestBlockPerTwoKeys();
314 // This reproduces the bug that a prefix is the same among multiple consecutive
315 // blocks but the bug would add it only to the first block.
316 TEST_P(PartitionedFilterBlockTest
, SamePrefixInMultipleBlocks
) {
317 // some small number to cause partition cuts
318 table_options_
.metadata_block_size
= 1;
319 std::unique_ptr
<const SliceTransform
> prefix_extractor
320 (rocksdb::NewFixedPrefixTransform(1));
321 std::unique_ptr
<PartitionedIndexBuilder
> pib(NewIndexBuilder());
322 std::unique_ptr
<PartitionedFilterBlockBuilder
> builder(
323 NewBuilder(pib
.get(), prefix_extractor
.get()));
324 const std::string pkeys
[3] = {"p-key1", "p-key2", "p-key3"};
325 builder
->Add(pkeys
[0]);
326 CutABlock(pib
.get(), pkeys
[0], pkeys
[1]);
327 builder
->Add(pkeys
[1]);
328 CutABlock(pib
.get(), pkeys
[1], pkeys
[2]);
329 builder
->Add(pkeys
[2]);
330 CutABlock(pib
.get(), pkeys
[2]);
331 std::unique_ptr
<PartitionedFilterBlockReader
> reader(
332 NewReader(builder
.get(), pib
.get(), prefix_extractor
.get()));
333 for (auto key
: pkeys
) {
334 auto ikey
= InternalKey(key
, 0, ValueType::kTypeValue
);
335 const Slice ikey_slice
= Slice(*ikey
.rep());
336 ASSERT_TRUE(reader
->PrefixMayMatch(prefix_extractor
->Transform(key
),
337 prefix_extractor
.get(), kNotValid
,
338 false /*no_io*/, &ikey_slice
));
342 TEST_P(PartitionedFilterBlockTest
, OneBlockPerKey
) {
343 uint64_t max_index_size
= MaxIndexSize();
344 for (uint64_t i
= 1; i
< max_index_size
+ 1; i
++) {
345 table_options_
.metadata_block_size
= i
;
350 TEST_P(PartitionedFilterBlockTest
, PartitionCount
) {
351 int num_keys
= sizeof(keys
) / sizeof(*keys
);
352 table_options_
.metadata_block_size
=
353 std::max(MaxIndexSize(), MaxFilterSize());
354 int partitions
= TestBlockPerKey();
355 ASSERT_EQ(partitions
, 1);
356 // A low number ensures cutting a block after each key
357 table_options_
.metadata_block_size
= 1;
358 partitions
= TestBlockPerKey();
359 ASSERT_EQ(partitions
, num_keys
- 1 /* last two keys make one flush */);
362 } // namespace rocksdb
364 int main(int argc
, char** argv
) {
365 ::testing::InitGoogleTest(&argc
, argv
);
366 return RUN_ALL_TESTS();