]>
Commit | Line | Data |
---|---|---|
7c673cae | 1 | // Copyright (c) 2011-present, Facebook, Inc. All rights reserved. |
11fdf7f2 TL |
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). | |
7c673cae FG |
5 | |
6 | #include <map> | |
7 | ||
8 | #include "rocksdb/filter_policy.h" | |
9 | ||
11fdf7f2 | 10 | #include "table/full_filter_bits_builder.h" |
7c673cae FG |
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" | |
18 | ||
19 | namespace rocksdb { | |
20 | ||
21 | std::map<uint64_t, Slice> slices; | |
22 | ||
23 | class MockedBlockBasedTable : public BlockBasedTable { | |
24 | public: | |
11fdf7f2 TL |
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; | |
28 | } | |
7c673cae | 29 | |
494da23a | 30 | CachableEntry<FilterBlockReader> GetFilter( |
11fdf7f2 TL |
31 | FilePrefetchBuffer*, const BlockHandle& filter_blk_handle, |
32 | const bool /* unused */, bool /* unused */, GetContext* /* unused */, | |
33 | const SliceTransform* prefix_extractor) const override { | |
7c673cae FG |
34 | Slice slice = slices[filter_blk_handle.offset()]; |
35 | auto obj = new FullFilterBlockReader( | |
494da23a | 36 | prefix_extractor, true, BlockContents(slice), |
7c673cae FG |
37 | rep_->table_options.filter_policy->GetFilterBitsReader(slice), nullptr); |
38 | return {obj, nullptr}; | |
39 | } | |
11fdf7f2 | 40 | |
494da23a | 41 | FilterBlockReader* ReadFilter( |
11fdf7f2 TL |
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( | |
494da23a | 47 | prefix_extractor, true, BlockContents(slice), |
11fdf7f2 TL |
48 | rep_->table_options.filter_policy->GetFilterBitsReader(slice), nullptr); |
49 | return obj; | |
50 | } | |
7c673cae FG |
51 | }; |
52 | ||
11fdf7f2 TL |
53 | class PartitionedFilterBlockTest |
54 | : public testing::Test, | |
55 | virtual public ::testing::WithParamInterface<uint32_t> { | |
7c673cae FG |
56 | public: |
57 | BlockBasedTableOptions table_options_; | |
58 | InternalKeyComparator icomp = InternalKeyComparator(BytewiseComparator()); | |
59 | ||
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 | |
11fdf7f2 TL |
65 | table_options_.format_version = GetParam(); |
66 | table_options_.index_block_restart_interval = 3; | |
7c673cae FG |
67 | } |
68 | ||
69 | std::shared_ptr<Cache> cache_; | |
494da23a | 70 | ~PartitionedFilterBlockTest() override {} |
7c673cae FG |
71 | |
72 | const std::string keys[4] = {"afoo", "bar", "box", "hello"}; | |
73 | const std::string missing_keys[2] = {"missing", "other"}; | |
74 | ||
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())); | |
80 | } | |
81 | uint64_t max_index_size = num_keys * (max_key_size + 8 /*handle*/); | |
82 | return max_index_size; | |
83 | } | |
84 | ||
11fdf7f2 TL |
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); | |
91 | auto partition_size = | |
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; | |
96 | } | |
97 | ||
7c673cae FG |
98 | int last_offset = 10; |
99 | BlockHandle Write(const Slice& slice) { | |
100 | BlockHandle bh(last_offset + 1, slice.size()); | |
101 | slices[bh.offset()] = slice; | |
102 | last_offset += bh.size(); | |
103 | return bh; | |
104 | } | |
105 | ||
106 | PartitionedIndexBuilder* NewIndexBuilder() { | |
11fdf7f2 TL |
107 | const bool kValueDeltaEncoded = true; |
108 | return PartitionedIndexBuilder::CreateIndexBuilder( | |
109 | &icomp, !kValueDeltaEncoded, table_options_); | |
7c673cae FG |
110 | } |
111 | ||
112 | PartitionedFilterBlockBuilder* NewBuilder( | |
11fdf7f2 TL |
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)) + | |
119 | 99) / | |
120 | 100); | |
121 | partition_size = std::max(partition_size, static_cast<uint32_t>(1)); | |
122 | const bool kValueDeltaEncoded = true; | |
7c673cae | 123 | return new PartitionedFilterBlockBuilder( |
11fdf7f2 | 124 | prefix_extractor, table_options_.whole_key_filtering, |
7c673cae | 125 | table_options_.filter_policy->GetFilterBitsBuilder(), |
11fdf7f2 TL |
126 | table_options_.index_block_restart_interval, !kValueDeltaEncoded, |
127 | p_index_builder, partition_size); | |
7c673cae FG |
128 | } |
129 | ||
130 | std::unique_ptr<MockedBlockBasedTable> table; | |
131 | ||
132 | PartitionedFilterBlockReader* NewReader( | |
11fdf7f2 TL |
133 | PartitionedFilterBlockBuilder* builder, PartitionedIndexBuilder* pib, |
134 | const SliceTransform* prefix_extractor) { | |
7c673cae FG |
135 | BlockHandle bh; |
136 | Status status; | |
137 | Slice slice; | |
138 | do { | |
139 | slice = builder->Finish(bh, &status); | |
140 | bh = Write(slice); | |
141 | } while (status.IsIncomplete()); | |
142 | const Options options; | |
143 | const ImmutableCFOptions ioptions(options); | |
11fdf7f2 | 144 | const MutableCFOptions moptions(options); |
7c673cae | 145 | const EnvOptions env_options; |
11fdf7f2 TL |
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, | |
494da23a | 150 | !kSkipFilters, 0, !kImmortal))); |
7c673cae | 151 | auto reader = new PartitionedFilterBlockReader( |
494da23a TL |
152 | prefix_extractor, true, BlockContents(slice), nullptr, nullptr, icomp, |
153 | table.get(), pib->seperator_is_key_plus_seq(), | |
11fdf7f2 | 154 | !pib->get_use_value_delta_encoding()); |
7c673cae FG |
155 | return reader; |
156 | } | |
157 | ||
158 | void VerifyReader(PartitionedFilterBlockBuilder* builder, | |
11fdf7f2 TL |
159 | PartitionedIndexBuilder* pib, bool empty = false, |
160 | const SliceTransform* prefix_extractor = nullptr) { | |
161 | std::unique_ptr<PartitionedFilterBlockReader> reader( | |
162 | NewReader(builder, pib, prefix_extractor)); | |
7c673cae FG |
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()); | |
11fdf7f2 TL |
168 | ASSERT_TRUE(reader->KeyMayMatch(key, prefix_extractor, kNotValid, !no_io, |
169 | &ikey_slice)); | |
7c673cae FG |
170 | } |
171 | { | |
172 | // querying a key twice | |
173 | auto ikey = InternalKey(keys[0], 0, ValueType::kTypeValue); | |
174 | const Slice ikey_slice = Slice(*ikey.rep()); | |
11fdf7f2 TL |
175 | ASSERT_TRUE(reader->KeyMayMatch(keys[0], prefix_extractor, kNotValid, |
176 | !no_io, &ikey_slice)); | |
7c673cae FG |
177 | } |
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()); | |
182 | if (empty) { | |
11fdf7f2 TL |
183 | ASSERT_TRUE(reader->KeyMayMatch(key, prefix_extractor, kNotValid, |
184 | !no_io, &ikey_slice)); | |
7c673cae FG |
185 | } else { |
186 | // assuming a good hash function | |
11fdf7f2 TL |
187 | ASSERT_FALSE(reader->KeyMayMatch(key, prefix_extractor, kNotValid, |
188 | !no_io, &ikey_slice)); | |
7c673cae FG |
189 | } |
190 | } | |
191 | } | |
192 | ||
193 | int TestBlockPerKey() { | |
194 | std::unique_ptr<PartitionedIndexBuilder> pib(NewIndexBuilder()); | |
195 | std::unique_ptr<PartitionedFilterBlockBuilder> builder( | |
196 | NewBuilder(pib.get())); | |
197 | int i = 0; | |
198 | builder->Add(keys[i]); | |
199 | CutABlock(pib.get(), keys[i], keys[i + 1]); | |
200 | i++; | |
201 | builder->Add(keys[i]); | |
202 | CutABlock(pib.get(), keys[i], keys[i + 1]); | |
203 | i++; | |
204 | builder->Add(keys[i]); | |
205 | builder->Add(keys[i]); | |
206 | CutABlock(pib.get(), keys[i], keys[i + 1]); | |
207 | i++; | |
208 | builder->Add(keys[i]); | |
209 | CutABlock(pib.get(), keys[i]); | |
210 | ||
11fdf7f2 | 211 | VerifyReader(builder.get(), pib.get()); |
7c673cae FG |
212 | return CountNumOfIndexPartitions(pib.get()); |
213 | } | |
214 | ||
11fdf7f2 | 215 | void TestBlockPerTwoKeys(const SliceTransform* prefix_extractor = nullptr) { |
7c673cae FG |
216 | std::unique_ptr<PartitionedIndexBuilder> pib(NewIndexBuilder()); |
217 | std::unique_ptr<PartitionedFilterBlockBuilder> builder( | |
11fdf7f2 | 218 | NewBuilder(pib.get(), prefix_extractor)); |
7c673cae FG |
219 | int i = 0; |
220 | builder->Add(keys[i]); | |
221 | i++; | |
222 | builder->Add(keys[i]); | |
223 | CutABlock(pib.get(), keys[i], keys[i + 1]); | |
224 | i++; | |
225 | builder->Add(keys[i]); | |
226 | builder->Add(keys[i]); | |
227 | i++; | |
228 | builder->Add(keys[i]); | |
229 | CutABlock(pib.get(), keys[i]); | |
230 | ||
11fdf7f2 | 231 | VerifyReader(builder.get(), pib.get(), prefix_extractor); |
7c673cae FG |
232 | } |
233 | ||
234 | void TestBlockPerAllKeys() { | |
235 | std::unique_ptr<PartitionedIndexBuilder> pib(NewIndexBuilder()); | |
236 | std::unique_ptr<PartitionedFilterBlockBuilder> builder( | |
237 | NewBuilder(pib.get())); | |
238 | int i = 0; | |
239 | builder->Add(keys[i]); | |
240 | i++; | |
241 | builder->Add(keys[i]); | |
242 | i++; | |
243 | builder->Add(keys[i]); | |
244 | builder->Add(keys[i]); | |
245 | i++; | |
246 | builder->Add(keys[i]); | |
247 | CutABlock(pib.get(), keys[i]); | |
248 | ||
11fdf7f2 | 249 | VerifyReader(builder.get(), pib.get()); |
7c673cae FG |
250 | } |
251 | ||
252 | void CutABlock(PartitionedIndexBuilder* builder, | |
253 | const std::string& user_key) { | |
254 | // Assuming a block is cut, add an entry to the index | |
255 | std::string key = | |
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); | |
259 | } | |
260 | ||
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 | |
264 | std::string key = | |
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); | |
271 | } | |
272 | ||
273 | int CountNumOfIndexPartitions(PartitionedIndexBuilder* builder) { | |
274 | IndexBuilder::IndexBlocks dont_care_ib; | |
275 | BlockHandle dont_care_bh(10, 10); | |
276 | Status s; | |
277 | int cnt = 0; | |
278 | do { | |
279 | s = builder->Finish(&dont_care_ib, dont_care_bh); | |
280 | cnt++; | |
281 | } while (s.IsIncomplete()); | |
282 | return cnt - 1; // 1 is 2nd level index | |
283 | } | |
284 | }; | |
285 | ||
11fdf7f2 TL |
286 | INSTANTIATE_TEST_CASE_P(FormatDef, PartitionedFilterBlockTest, |
287 | testing::Values(test::kDefaultFormatVersion)); | |
288 | INSTANTIATE_TEST_CASE_P(FormatLatest, PartitionedFilterBlockTest, | |
289 | testing::Values(test::kLatestFormatVersion)); | |
290 | ||
291 | TEST_P(PartitionedFilterBlockTest, EmptyBuilder) { | |
7c673cae FG |
292 | std::unique_ptr<PartitionedIndexBuilder> pib(NewIndexBuilder()); |
293 | std::unique_ptr<PartitionedFilterBlockBuilder> builder(NewBuilder(pib.get())); | |
294 | const bool empty = true; | |
11fdf7f2 | 295 | VerifyReader(builder.get(), pib.get(), empty); |
7c673cae FG |
296 | } |
297 | ||
11fdf7f2 | 298 | TEST_P(PartitionedFilterBlockTest, OneBlock) { |
7c673cae FG |
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(); | |
303 | } | |
304 | } | |
305 | ||
11fdf7f2 | 306 | TEST_P(PartitionedFilterBlockTest, TwoBlocksPerKey) { |
7c673cae FG |
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(); | |
311 | } | |
312 | } | |
313 | ||
11fdf7f2 TL |
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)); | |
339 | } | |
340 | } | |
341 | ||
342 | TEST_P(PartitionedFilterBlockTest, OneBlockPerKey) { | |
7c673cae FG |
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; | |
346 | TestBlockPerKey(); | |
347 | } | |
348 | } | |
349 | ||
11fdf7f2 | 350 | TEST_P(PartitionedFilterBlockTest, PartitionCount) { |
7c673cae | 351 | int num_keys = sizeof(keys) / sizeof(*keys); |
11fdf7f2 TL |
352 | table_options_.metadata_block_size = |
353 | std::max(MaxIndexSize(), MaxFilterSize()); | |
7c673cae FG |
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 */); | |
360 | } | |
361 | ||
362 | } // namespace rocksdb | |
363 | ||
364 | int main(int argc, char** argv) { | |
365 | ::testing::InitGoogleTest(&argc, argv); | |
366 | return RUN_ALL_TESTS(); | |
367 | } |