/Users/deen/code/yugabyte-db/src/yb/rocksdb/table/table_test.cc
Line | Count | Source (jump to first uncovered line) |
1 | | // Copyright (c) 2011-present, Facebook, Inc. All rights reserved. |
2 | | // This source code is licensed under the BSD-style license found in the |
3 | | // LICENSE file in the root directory of this source tree. An additional grant |
4 | | // of patent rights can be found in the PATENTS file in the same directory. |
5 | | // |
6 | | // The following only applies to changes made to this file as part of YugaByte development. |
7 | | // |
8 | | // Portions Copyright (c) YugaByte, Inc. |
9 | | // |
10 | | // Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except |
11 | | // in compliance with the License. You may obtain a copy of the License at |
12 | | // |
13 | | // http://www.apache.org/licenses/LICENSE-2.0 |
14 | | // |
15 | | // Unless required by applicable law or agreed to in writing, software distributed under the License |
16 | | // is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express |
17 | | // or implied. See the License for the specific language governing permissions and limitations |
18 | | // under the License. |
19 | | // |
20 | | // Copyright (c) 2011 The LevelDB Authors. All rights reserved. |
21 | | // Use of this source code is governed by a BSD-style license that can be |
22 | | // found in the LICENSE file. See the AUTHORS file for names of contributors. |
23 | | |
24 | | #include <inttypes.h> |
25 | | #include <stdio.h> |
26 | | |
27 | | #include <algorithm> |
28 | | #include <map> |
29 | | #include <memory> |
30 | | #include <string> |
31 | | #include <vector> |
32 | | |
33 | | #include <boost/optional.hpp> |
34 | | #include <gtest/gtest.h> |
35 | | |
36 | | #include "yb/rocksdb/db/dbformat.h" |
37 | | #include "yb/rocksdb/db/memtable.h" |
38 | | #include "yb/rocksdb/db/write_batch_internal.h" |
39 | | #include "yb/rocksdb/db/writebuffer.h" |
40 | | #include "yb/rocksdb/env.h" |
41 | | #include "yb/rocksdb/filter_policy.h" |
42 | | #include "yb/rocksdb/flush_block_policy.h" |
43 | | #include "yb/rocksdb/iterator.h" |
44 | | #include "yb/rocksdb/memtablerep.h" |
45 | | #include "yb/rocksdb/perf_context.h" |
46 | | #include "yb/rocksdb/slice_transform.h" |
47 | | #include "yb/rocksdb/statistics.h" |
48 | | #include "yb/rocksdb/table.h" |
49 | | #include "yb/rocksdb/table/block.h" |
50 | | #include "yb/rocksdb/table/block_based_table_builder.h" |
51 | | #include "yb/rocksdb/table/block_based_table_factory.h" |
52 | | #include "yb/rocksdb/table/block_based_table_reader.h" |
53 | | #include "yb/rocksdb/table/block_builder.h" |
54 | | #include "yb/rocksdb/table/format.h" |
55 | | #include "yb/rocksdb/table/get_context.h" |
56 | | #include "yb/rocksdb/table/internal_iterator.h" |
57 | | #include "yb/rocksdb/table/meta_blocks.h" |
58 | | #include "yb/rocksdb/table/plain_table_factory.h" |
59 | | #include "yb/rocksdb/table/scoped_arena_iterator.h" |
60 | | #include "yb/rocksdb/util/compression.h" |
61 | | #include "yb/rocksdb/util/file_reader_writer.h" |
62 | | #include "yb/rocksdb/util/logging.h" |
63 | | #include "yb/rocksdb/util/random.h" |
64 | | #include "yb/rocksdb/util/statistics.h" |
65 | | #include "yb/rocksdb/util/testharness.h" |
66 | | #include "yb/rocksdb/util/testutil.h" |
67 | | |
68 | | #include "yb/util/enums.h" |
69 | | #include "yb/util/string_util.h" |
70 | | #include "yb/util/test_macros.h" |
71 | | |
72 | | DECLARE_double(cache_single_touch_ratio); |
73 | | |
74 | | namespace rocksdb { |
75 | | |
76 | | extern const uint64_t kLegacyBlockBasedTableMagicNumber; |
77 | | extern const uint64_t kLegacyPlainTableMagicNumber; |
78 | | extern const uint64_t kBlockBasedTableMagicNumber; |
79 | | extern const uint64_t kPlainTableMagicNumber; |
80 | | |
81 | | namespace { |
82 | | |
83 | | // Return reverse of "key". |
84 | | // Used to test non-lexicographic comparators. |
85 | 70.4M | std::string Reverse(const Slice& key) { |
86 | 70.4M | auto rev = key.ToString(); |
87 | 70.4M | std::reverse(rev.begin(), rev.end()); |
88 | 70.4M | return rev; |
89 | 70.4M | } |
90 | | |
91 | | class ReverseKeyComparator : public Comparator { |
92 | | public: |
93 | 7.28k | const char* Name() const override { |
94 | 7.28k | return "rocksdb.ReverseBytewiseComparator"; |
95 | 7.28k | } |
96 | | |
97 | 35.1M | int Compare(const Slice& a, const Slice& b) const override { |
98 | 35.1M | return BytewiseComparator()->Compare(Reverse(a), Reverse(b)); |
99 | 35.1M | } |
100 | | |
101 | | virtual void FindShortestSeparator(std::string* start, |
102 | 5.92k | const Slice& limit) const override { |
103 | 5.92k | std::string s = Reverse(*start); |
104 | 5.92k | std::string l = Reverse(limit); |
105 | 5.92k | BytewiseComparator()->FindShortestSeparator(&s, l); |
106 | 5.92k | *start = Reverse(s); |
107 | 5.92k | } |
108 | | |
109 | 1.51k | void FindShortSuccessor(std::string* key) const override { |
110 | 1.51k | std::string s = Reverse(*key); |
111 | 1.51k | BytewiseComparator()->FindShortSuccessor(&s); |
112 | 1.51k | *key = Reverse(s); |
113 | 1.51k | } |
114 | | }; |
115 | | |
116 | | ReverseKeyComparator reverse_key_comparator; |
117 | | |
118 | 157k | void Increment(const Comparator* cmp, std::string* key) { |
119 | 157k | if (cmp == BytewiseComparator()) { |
120 | 78.9k | key->push_back('\0'); |
121 | 78.9k | } else { |
122 | 78.9k | assert(cmp == &reverse_key_comparator); |
123 | 78.9k | std::string rev = Reverse(*key); |
124 | 78.9k | rev.push_back('\0'); |
125 | 78.9k | *key = Reverse(rev); |
126 | 78.9k | } |
127 | 157k | } |
128 | | |
129 | 5 | void SetFixedSizeFilterPolicy(BlockBasedTableOptions* table_options) { |
130 | 5 | table_options->filter_policy.reset(NewFixedSizeFilterPolicy( |
131 | 5 | rocksdb::FilterPolicy::kDefaultFixedSizeFilterBits, |
132 | 5 | rocksdb::FilterPolicy::kDefaultFixedSizeFilterErrorRate, nullptr)); |
133 | 5 | } |
134 | | |
135 | | } // namespace |
136 | | |
137 | | // Helper class for tests to unify the interface between |
138 | | // BlockBuilder/TableBuilder and Block/Table. |
139 | | class Constructor { |
140 | | public: |
141 | | explicit Constructor(const Comparator* cmp) |
142 | 1.16k | : data_(stl_wrappers::LessOfComparator(cmp)) {} |
143 | 1.16k | virtual ~Constructor() { } |
144 | | |
145 | 2.47M | void Add(const std::string& key, const Slice& value) { |
146 | 2.47M | data_[key] = value.ToString(); |
147 | 2.47M | } |
148 | | |
149 | | // Finish constructing the data structure with all the keys that have |
150 | | // been added so far. Returns the keys in sorted order in "*keys" |
151 | | // and stores the key/value pairs in "*kvmap" |
152 | | void Finish(const Options& options, const ImmutableCFOptions& ioptions, |
153 | | const BlockBasedTableOptions& table_options, |
154 | | const InternalKeyComparatorPtr& internal_comparator, |
155 | 13.2k | std::vector<std::string>* keys, stl_wrappers::KVMap* kvmap) { |
156 | 13.2k | last_internal_key_ = internal_comparator; |
157 | 13.2k | *kvmap = data_; |
158 | 13.2k | keys->clear(); |
159 | 1.13M | for (const auto& kv : data_) { |
160 | 1.13M | keys->push_back(kv.first); |
161 | 1.13M | } |
162 | 13.2k | data_.clear(); |
163 | 13.2k | Status s = FinishImpl(options, ioptions, table_options, |
164 | 13.2k | internal_comparator, *kvmap); |
165 | 26.4k | ASSERT_TRUE(s.ok()) << s.ToString(); |
166 | 13.2k | } |
167 | | |
168 | | // Construct the data structure from the data in "data" |
169 | | virtual Status FinishImpl(const Options& options, |
170 | | const ImmutableCFOptions& ioptions, |
171 | | const BlockBasedTableOptions& table_options, |
172 | | const InternalKeyComparatorPtr& internal_comparator, |
173 | | const stl_wrappers::KVMap& data) = 0; |
174 | | |
175 | | virtual InternalIterator* NewIterator() const = 0; |
176 | | |
177 | 0 | virtual const stl_wrappers::KVMap& data() { return data_; } |
178 | | |
179 | 29.1k | virtual bool IsArenaMode() const { return false; } |
180 | | |
181 | 0 | virtual DB* db() const { return nullptr; } // Overridden in DBConstructor |
182 | | |
183 | 0 | virtual bool AnywayDeleteIterator() const { return false; } |
184 | | |
185 | | protected: |
186 | | InternalKeyComparatorPtr last_internal_key_; |
187 | | |
188 | | private: |
189 | | stl_wrappers::KVMap data_; |
190 | | }; |
191 | | |
192 | | class BlockConstructor: public Constructor { |
193 | | public: |
194 | | explicit BlockConstructor( |
195 | | const Comparator* cmp) |
196 | | : Constructor(cmp), |
197 | | comparator_(cmp), |
198 | 240 | block_(nullptr) { } |
199 | 240 | ~BlockConstructor() { |
200 | 240 | delete block_; |
201 | 240 | } |
202 | | virtual Status FinishImpl(const Options& options, |
203 | | const ImmutableCFOptions& ioptions, |
204 | | const BlockBasedTableOptions& table_options, |
205 | | const InternalKeyComparatorPtr& internal_comparator, |
206 | 3.07k | const stl_wrappers::KVMap& kv_map) override { |
207 | 3.07k | delete block_; |
208 | 3.07k | block_ = nullptr; |
209 | 3.07k | BlockBuilder builder( |
210 | 3.07k | table_options.block_restart_interval, table_options.data_block_key_value_encoding_format); |
211 | | |
212 | 217k | for (const auto& kv : kv_map) { |
213 | 217k | builder.Add(kv.first, kv.second); |
214 | 217k | } |
215 | | // Open the block |
216 | 3.07k | data_ = builder.Finish().ToString(); |
217 | 3.07k | BlockContents contents; |
218 | 3.07k | contents.data = data_; |
219 | 3.07k | contents.cachable = false; |
220 | 3.07k | block_ = new Block(std::move(contents)); |
221 | 3.07k | key_value_encoding_format_ = table_options.data_block_key_value_encoding_format; |
222 | 3.07k | return Status::OK(); |
223 | 3.07k | } |
224 | 9.21k | InternalIterator* NewIterator() const override { |
225 | 9.21k | return block_->NewIterator(comparator_, key_value_encoding_format_); |
226 | 9.21k | } |
227 | | |
228 | | private: |
229 | | const Comparator* comparator_; |
230 | | KeyValueEncodingFormat key_value_encoding_format_; |
231 | | std::string data_; |
232 | | Block* block_; |
233 | | |
234 | | BlockConstructor(); |
235 | | }; |
236 | | |
237 | | // A helper class that converts internal format keys into user keys |
238 | | class KeyConvertingIterator : public InternalIterator { |
239 | | public: |
240 | | explicit KeyConvertingIterator(InternalIterator* iter, |
241 | | bool arena_mode = false) |
242 | 10.7k | : iter_(iter), arena_mode_(arena_mode) {} |
243 | 10.7k | virtual ~KeyConvertingIterator() { |
244 | 10.7k | if (arena_mode_) { |
245 | 9.21k | iter_->~InternalIterator(); |
246 | 1.53k | } else { |
247 | 1.53k | delete iter_; |
248 | 1.53k | } |
249 | 10.7k | } |
250 | 2.64M | bool Valid() const override { return iter_->Valid(); } |
251 | 172k | void Seek(const Slice& target) override { |
252 | 172k | ParsedInternalKey ikey(target, kMaxSequenceNumber, kTypeValue); |
253 | 172k | std::string encoded; |
254 | 172k | AppendInternalKey(&encoded, ikey); |
255 | 172k | iter_->Seek(encoded); |
256 | 172k | } |
257 | 176k | void SeekToFirst() override { iter_->SeekToFirst(); } |
258 | 127k | void SeekToLast() override { iter_->SeekToLast(); } |
259 | 417k | void Next() override { iter_->Next(); } |
260 | 315k | void Prev() override { iter_->Prev(); } |
261 | | |
262 | 1.12M | Slice key() const override { |
263 | 1.12M | assert(Valid()); |
264 | 1.12M | ParsedInternalKey parsed_key; |
265 | 1.12M | if (!ParseInternalKey(iter_->key(), &parsed_key)) { |
266 | 0 | status_ = STATUS(Corruption, "malformed internal key"); |
267 | 0 | return Slice("corrupted key"); |
268 | 0 | } |
269 | 1.12M | return parsed_key.user_key; |
270 | 1.12M | } |
271 | | |
272 | 1.12M | Slice value() const override { return iter_->value(); } |
273 | 0 | Status status() const override { |
274 | 0 | return status_.ok() ? iter_->status() : status_; |
275 | 0 | } |
276 | | |
277 | | private: |
278 | | mutable Status status_; |
279 | | InternalIterator* iter_; |
280 | | bool arena_mode_; |
281 | | |
282 | | // No copying allowed |
283 | | KeyConvertingIterator(const KeyConvertingIterator&); |
284 | | void operator=(const KeyConvertingIterator&); |
285 | | }; |
286 | | |
287 | | class TableConstructor: public Constructor { |
288 | | public: |
289 | | explicit TableConstructor(const Comparator* cmp, |
290 | | bool convert_to_internal_key = false) |
291 | | : Constructor(cmp), |
292 | 447 | convert_to_internal_key_(convert_to_internal_key) {} |
293 | 447 | ~TableConstructor() { Reset(); } |
294 | | |
295 | | virtual Status FinishImpl(const Options& options, |
296 | | const ImmutableCFOptions& ioptions, |
297 | | const BlockBasedTableOptions& table_options, |
298 | | const InternalKeyComparatorPtr& internal_comparator, |
299 | 3.98k | const stl_wrappers::KVMap& kv_map) override { |
300 | 3.98k | Reset(); |
301 | 3.98k | soptions.use_mmap_reads = ioptions.allow_mmap_reads; |
302 | 3.98k | file_writer_.reset(test::GetWritableFileWriter(new test::StringSink())); |
303 | 3.98k | unique_ptr<TableBuilder> builder; |
304 | 3.98k | IntTblPropCollectorFactories int_tbl_prop_collector_factories; |
305 | 3.98k | builder.reset(ioptions.table_factory->NewTableBuilder( |
306 | 3.98k | TableBuilderOptions(ioptions, |
307 | 3.98k | internal_comparator, |
308 | 3.98k | int_tbl_prop_collector_factories, |
309 | 3.98k | options.compression, |
310 | 3.98k | CompressionOptions(), |
311 | 3.98k | /* skip_filters */ false), |
312 | 3.98k | TablePropertiesCollectorFactory::Context::kUnknownColumnFamily, |
313 | 3.98k | file_writer_.get())); |
314 | 3.98k | if (TEST_skip_writing_key_value_encoding_format) { |
315 | 6 | dynamic_cast<BlockBasedTableBuilder*>(builder.get()) |
316 | 6 | ->TEST_skip_writing_key_value_encoding_format(); |
317 | 6 | } |
318 | | |
319 | 456k | for (const auto& kv : kv_map) { |
320 | 456k | if (convert_to_internal_key_) { |
321 | 53.9k | ParsedInternalKey ikey(kv.first, kMaxSequenceNumber, kTypeValue); |
322 | 53.9k | std::string encoded; |
323 | 53.9k | AppendInternalKey(&encoded, ikey); |
324 | 53.9k | builder->Add(encoded, kv.second); |
325 | 402k | } else { |
326 | 402k | builder->Add(kv.first, kv.second); |
327 | 402k | } |
328 | 456k | EXPECT_TRUE(builder->status().ok()); |
329 | 456k | } |
330 | 3.98k | Status s = builder->Finish(); |
331 | 3.98k | RETURN_NOT_OK(file_writer_->Flush()); |
332 | 7.97k | EXPECT_TRUE(s.ok()) << s.ToString(); |
333 | | |
334 | 3.98k | EXPECT_EQ(GetSink()->contents().size(), builder->TotalFileSize()); |
335 | 3.98k | table_properties_ = builder->GetTableProperties(); |
336 | | |
337 | | // Open the table |
338 | 3.98k | uniq_id_ = cur_uniq_id_++; |
339 | 3.98k | file_reader_.reset(test::GetRandomAccessFileReader(new test::StringSource( |
340 | 3.98k | GetSink()->contents(), uniq_id_, ioptions.allow_mmap_reads))); |
341 | 3.98k | return ioptions.table_factory->NewTableReader( |
342 | 3.98k | TableReaderOptions(ioptions, soptions, internal_comparator), |
343 | 3.98k | std::move(file_reader_), GetSink()->contents().size(), &table_reader_); |
344 | 3.98k | } |
345 | | |
346 | 10.7k | InternalIterator* NewIterator() const override { |
347 | 10.7k | ReadOptions ro; |
348 | 10.7k | InternalIterator* iter = table_reader_->NewIterator(ro); |
349 | 10.7k | if (convert_to_internal_key_) { |
350 | 1.53k | return new KeyConvertingIterator(iter); |
351 | 9.22k | } else { |
352 | 9.22k | return iter; |
353 | 9.22k | } |
354 | 10.7k | } |
355 | | |
356 | 35 | uint64_t ApproximateOffsetOf(const Slice& key) const { |
357 | 35 | return table_reader_->ApproximateOffsetOf(key); |
358 | 35 | } |
359 | | |
360 | 14 | virtual Status Reopen(const ImmutableCFOptions& ioptions) { |
361 | 14 | file_reader_.reset(test::GetRandomAccessFileReader(new test::StringSource( |
362 | 14 | GetSink()->contents(), uniq_id_, ioptions.allow_mmap_reads))); |
363 | 14 | return ioptions.table_factory->NewTableReader( |
364 | 14 | TableReaderOptions(ioptions, soptions, last_internal_key_), |
365 | 14 | std::move(file_reader_), GetSink()->contents().size(), &table_reader_); |
366 | 14 | } |
367 | | |
368 | 159 | virtual TableReader* GetTableReader() { |
369 | 159 | return table_reader_.get(); |
370 | 159 | } |
371 | | |
372 | 0 | bool AnywayDeleteIterator() const override { |
373 | 0 | return convert_to_internal_key_; |
374 | 0 | } |
375 | | |
376 | 5 | TableProperties GetTableProperties() const { |
377 | 5 | return table_properties_; |
378 | 5 | } |
379 | | |
380 | | bool TEST_skip_writing_key_value_encoding_format = false; |
381 | | |
382 | | private: |
383 | 4.43k | void Reset() { |
384 | 4.43k | uniq_id_ = 0; |
385 | 4.43k | table_reader_.reset(); |
386 | 4.43k | file_writer_.reset(); |
387 | 4.43k | file_reader_.reset(); |
388 | 4.43k | } |
389 | | |
390 | 11.9k | test::StringSink* GetSink() { |
391 | 11.9k | return static_cast<test::StringSink*>(file_writer_->writable_file()); |
392 | 11.9k | } |
393 | | |
394 | | uint64_t uniq_id_; |
395 | | unique_ptr<WritableFileWriter> file_writer_; |
396 | | unique_ptr<RandomAccessFileReader> file_reader_; |
397 | | unique_ptr<TableReader> table_reader_; |
398 | | bool convert_to_internal_key_; |
399 | | |
400 | | TableConstructor(); |
401 | | |
402 | | static uint64_t cur_uniq_id_; |
403 | | EnvOptions soptions; |
404 | | TableProperties table_properties_; |
405 | | }; |
406 | | uint64_t TableConstructor::cur_uniq_id_ = 1; |
407 | | |
408 | | class MemTableConstructor: public Constructor { |
409 | | public: |
410 | | explicit MemTableConstructor(const Comparator* cmp, WriteBuffer* wb) |
411 | | : Constructor(cmp), |
412 | | internal_comparator_(cmp), |
413 | | write_buffer_(wb), |
414 | 240 | table_factory_(new SkipListFactory) { |
415 | 240 | options_.memtable_factory = table_factory_; |
416 | 240 | ImmutableCFOptions ioptions(options_); |
417 | 240 | memtable_ = new MemTable(internal_comparator_, ioptions, |
418 | 240 | MutableCFOptions(options_, ioptions), wb, |
419 | 240 | kMaxSequenceNumber); |
420 | 240 | memtable_->Ref(); |
421 | 240 | } |
422 | 240 | ~MemTableConstructor() { |
423 | 240 | delete memtable_->Unref(); |
424 | 240 | } |
425 | | virtual Status FinishImpl(const Options&, const ImmutableCFOptions& ioptions, |
426 | | const BlockBasedTableOptions& table_options, |
427 | | const InternalKeyComparatorPtr& internal_comparator, |
428 | 3.07k | const stl_wrappers::KVMap& kv_map) override { |
429 | 3.07k | delete memtable_->Unref(); |
430 | 3.07k | ImmutableCFOptions mem_ioptions(ioptions); |
431 | 3.07k | memtable_ = new MemTable(internal_comparator_, mem_ioptions, |
432 | 3.07k | MutableCFOptions(options_, mem_ioptions), |
433 | 3.07k | write_buffer_, kMaxSequenceNumber); |
434 | 3.07k | memtable_->Ref(); |
435 | 3.07k | int seq = 1; |
436 | 217k | for (const auto& kv : kv_map) { |
437 | 217k | Slice key(kv.first); |
438 | 217k | Slice value(kv.second); |
439 | 217k | memtable_->Add(seq, kTypeValue, SliceParts(&key, 1), SliceParts(&value, 1)); |
440 | 217k | seq++; |
441 | 217k | } |
442 | 3.07k | return Status::OK(); |
443 | 3.07k | } |
444 | 9.21k | InternalIterator* NewIterator() const override { |
445 | 9.21k | return new KeyConvertingIterator( |
446 | 9.21k | memtable_->NewIterator(ReadOptions(), &arena_), true); |
447 | 9.21k | } |
448 | | |
449 | 9.21k | bool AnywayDeleteIterator() const override { return true; } |
450 | | |
451 | 9.21k | bool IsArenaMode() const override { return true; } |
452 | | |
453 | | private: |
454 | | mutable Arena arena_; |
455 | | InternalKeyComparator internal_comparator_; |
456 | | Options options_; |
457 | | WriteBuffer* write_buffer_; |
458 | | MemTable* memtable_; |
459 | | std::shared_ptr<SkipListFactory> table_factory_; |
460 | | }; |
461 | | |
462 | | class InternalIteratorFromIterator : public InternalIterator { |
463 | | public: |
464 | 9.21k | explicit InternalIteratorFromIterator(Iterator* it) : it_(it) {} |
465 | 1.31M | bool Valid() const override { return it_->Valid(); } |
466 | 121k | void Seek(const Slice& target) override { it_->Seek(target); } |
467 | 124k | void SeekToFirst() override { it_->SeekToFirst(); } |
468 | 127k | void SeekToLast() override { it_->SeekToLast(); } |
469 | 340k | void Next() override { it_->Next(); } |
470 | 341k | void Prev() override { it_->Prev(); } |
471 | 978k | Slice key() const override { return it_->key(); } |
472 | 978k | Slice value() const override { return it_->value(); } |
473 | 0 | Status status() const override { return it_->status(); } |
474 | | |
475 | | private: |
476 | | unique_ptr<Iterator> it_; |
477 | | }; |
478 | | |
479 | | class DBConstructor: public Constructor { |
480 | | public: |
481 | | explicit DBConstructor(const Comparator* cmp) |
482 | | : Constructor(cmp), |
483 | 241 | comparator_(cmp) { |
484 | 241 | db_ = nullptr; |
485 | 241 | NewDB(); |
486 | 241 | } |
487 | 241 | ~DBConstructor() { |
488 | 241 | delete db_; |
489 | 241 | } |
490 | | virtual Status FinishImpl(const Options& options, |
491 | | const ImmutableCFOptions& ioptions, |
492 | | const BlockBasedTableOptions& table_options, |
493 | | const InternalKeyComparatorPtr& internal_comparator, |
494 | 3.07k | const stl_wrappers::KVMap& kv_map) override { |
495 | 3.07k | delete db_; |
496 | 3.07k | db_ = nullptr; |
497 | 3.07k | NewDB(); |
498 | 242k | for (const auto& kv : kv_map) { |
499 | 242k | WriteBatch batch; |
500 | 242k | batch.Put(kv.first, kv.second); |
501 | 242k | EXPECT_TRUE(db_->Write(WriteOptions(), &batch).ok()); |
502 | 242k | } |
503 | 3.07k | return Status::OK(); |
504 | 3.07k | } |
505 | | |
506 | 9.21k | InternalIterator* NewIterator() const override { |
507 | 9.21k | return new InternalIteratorFromIterator(db_->NewIterator(ReadOptions())); |
508 | 9.21k | } |
509 | | |
510 | 15 | DB* db() const override { return db_; } |
511 | | |
512 | | private: |
513 | 3.31k | void NewDB() { |
514 | 3.31k | std::string name = test::TmpDir() + "/table_testdb"; |
515 | | |
516 | 3.31k | Options options; |
517 | 3.31k | options.comparator = comparator_; |
518 | 3.31k | Status status = DestroyDB(name, options); |
519 | 6.62k | ASSERT_TRUE(status.ok()) << status.ToString(); |
520 | | |
521 | 3.31k | options.create_if_missing = true; |
522 | 3.31k | options.error_if_exists = true; |
523 | 3.31k | options.write_buffer_size = 10000; // Something small to force merging |
524 | 3.31k | status = DB::Open(options, name, &db_); |
525 | 6.62k | ASSERT_TRUE(status.ok()) << status.ToString(); |
526 | 3.31k | } |
527 | | |
528 | | const Comparator* comparator_; |
529 | | DB* db_; |
530 | | }; |
531 | | |
532 | | enum TestType { |
533 | | BLOCK_BASED_TABLE_TEST, |
534 | | #ifndef ROCKSDB_LITE |
535 | | PLAIN_TABLE_SEMI_FIXED_PREFIX, |
536 | | PLAIN_TABLE_FULL_STR_PREFIX, |
537 | | PLAIN_TABLE_TOTAL_ORDER, |
538 | | #endif // !ROCKSDB_LITE |
539 | | BLOCK_TEST, |
540 | | MEMTABLE_TEST, |
541 | | DB_TEST |
542 | | }; |
543 | | |
544 | | struct TestArgs { |
545 | | TestType type; |
546 | | bool reverse_compare; |
547 | | int restart_interval; |
548 | | CompressionType compression; |
549 | | uint32_t format_version; |
550 | | bool use_mmap; |
551 | | }; |
552 | | |
553 | 5 | static std::vector<TestArgs> GenerateArgList() { |
554 | 5 | std::vector<TestArgs> test_args; |
555 | 5 | std::vector<TestType> test_types = { |
556 | 5 | BLOCK_BASED_TABLE_TEST, |
557 | 5 | #ifndef ROCKSDB_LITE |
558 | 5 | PLAIN_TABLE_SEMI_FIXED_PREFIX, |
559 | 5 | PLAIN_TABLE_FULL_STR_PREFIX, |
560 | 5 | PLAIN_TABLE_TOTAL_ORDER, |
561 | 5 | #endif // !ROCKSDB_LITE |
562 | 5 | BLOCK_TEST, |
563 | 5 | MEMTABLE_TEST, DB_TEST}; |
564 | 5 | std::vector<bool> reverse_compare_types = {false, true}; |
565 | 5 | std::vector<int> restart_intervals = {16, 1, 1024}; |
566 | | |
567 | | // Only add compression if it is supported |
568 | 5 | std::vector<std::pair<CompressionType, bool>> compression_types; |
569 | 5 | compression_types.emplace_back(kNoCompression, false); |
570 | 5 | if (Snappy_Supported()) { |
571 | 5 | compression_types.emplace_back(kSnappyCompression, false); |
572 | 5 | } |
573 | 5 | if (Zlib_Supported()) { |
574 | 5 | compression_types.emplace_back(kZlibCompression, false); |
575 | 5 | compression_types.emplace_back(kZlibCompression, true); |
576 | 5 | } |
577 | 5 | if (BZip2_Supported()) { |
578 | 0 | compression_types.emplace_back(kBZip2Compression, false); |
579 | 0 | compression_types.emplace_back(kBZip2Compression, true); |
580 | 0 | } |
581 | 5 | if (LZ4_Supported()) { |
582 | 5 | compression_types.emplace_back(kLZ4Compression, false); |
583 | 5 | compression_types.emplace_back(kLZ4Compression, true); |
584 | 5 | compression_types.emplace_back(kLZ4HCCompression, false); |
585 | 5 | compression_types.emplace_back(kLZ4HCCompression, true); |
586 | 5 | } |
587 | 5 | if (ZSTD_Supported()) { |
588 | 0 | compression_types.emplace_back(kZSTDNotFinalCompression, false); |
589 | 0 | compression_types.emplace_back(kZSTDNotFinalCompression, true); |
590 | 0 | } |
591 | | |
592 | 35 | for (auto test_type : test_types) { |
593 | 70 | for (auto reverse_compare : reverse_compare_types) { |
594 | 70 | #ifndef ROCKSDB_LITE |
595 | 70 | if (test_type == PLAIN_TABLE_SEMI_FIXED_PREFIX || |
596 | 60 | test_type == PLAIN_TABLE_FULL_STR_PREFIX || |
597 | 50 | test_type == PLAIN_TABLE_TOTAL_ORDER) { |
598 | | // Plain table doesn't use restart index or compression. |
599 | 30 | TestArgs one_arg; |
600 | 30 | one_arg.type = test_type; |
601 | 30 | one_arg.reverse_compare = reverse_compare; |
602 | 30 | one_arg.restart_interval = restart_intervals[0]; |
603 | 30 | one_arg.compression = compression_types[0].first; |
604 | 30 | one_arg.use_mmap = true; |
605 | 30 | test_args.push_back(one_arg); |
606 | 30 | one_arg.use_mmap = false; |
607 | 30 | test_args.push_back(one_arg); |
608 | 30 | continue; |
609 | 30 | } |
610 | 40 | #endif // !ROCKSDB_LITE |
611 | | |
612 | 120 | for (auto restart_interval : restart_intervals) { |
613 | 960 | for (auto compression_type : compression_types) { |
614 | 960 | TestArgs one_arg; |
615 | 960 | one_arg.type = test_type; |
616 | 960 | one_arg.reverse_compare = reverse_compare; |
617 | 960 | one_arg.restart_interval = restart_interval; |
618 | 960 | one_arg.compression = compression_type.first; |
619 | 600 | one_arg.format_version = compression_type.second ? 2 : 1; |
620 | 960 | one_arg.use_mmap = false; |
621 | 960 | test_args.push_back(one_arg); |
622 | 960 | } |
623 | 120 | } |
624 | 40 | } |
625 | 35 | } |
626 | 5 | return test_args; |
627 | 5 | } |
628 | | |
629 | | // In order to make all tests run for plain table format, including |
630 | | // those operating on empty keys, create a new prefix transformer which |
631 | | // return fixed prefix if the slice is not shorter than the prefix length, |
632 | | // and the full slice if it is shorter. |
633 | | class FixedOrLessPrefixTransform : public SliceTransform { |
634 | | private: |
635 | | const size_t prefix_len_; |
636 | | |
637 | | public: |
638 | | explicit FixedOrLessPrefixTransform(size_t prefix_len) : |
639 | 20 | prefix_len_(prefix_len) { |
640 | 20 | } |
641 | | |
642 | 512 | const char* Name() const override { return "rocksdb.FixedPrefix"; } |
643 | | |
644 | 65.2k | Slice Transform(const Slice& src) const override { |
645 | 65.2k | assert(InDomain(src)); |
646 | 65.2k | if (src.size() < prefix_len_) { |
647 | 11.8k | return src; |
648 | 11.8k | } |
649 | 53.4k | return Slice(src.data(), prefix_len_); |
650 | 53.4k | } |
651 | | |
652 | 65.2k | bool InDomain(const Slice& src) const override { return true; } |
653 | | |
654 | 0 | bool InRange(const Slice& dst) const override { |
655 | 0 | return (dst.size() <= prefix_len_); |
656 | 0 | } |
657 | | }; |
658 | | |
659 | | class HarnessTest : public RocksDBTest { |
660 | | public: |
661 | | HarnessTest() |
662 | | : ioptions_(options_), |
663 | | constructor_(nullptr), |
664 | 7 | write_buffer_(options_.db_write_buffer_size) {} |
665 | | |
666 | 1.02k | void Init(const TestArgs& args) { |
667 | 1.02k | delete constructor_; |
668 | 1.02k | constructor_ = nullptr; |
669 | 1.02k | options_ = Options(); |
670 | 1.02k | options_.compression = args.compression; |
671 | | // Use shorter block size for tests to exercise block boundary |
672 | | // conditions more. |
673 | 1.02k | if (args.reverse_compare) { |
674 | 510 | options_.comparator = &reverse_key_comparator; |
675 | 510 | } |
676 | | |
677 | 1.02k | internal_comparator_.reset( |
678 | 1.02k | new test::PlainInternalKeyComparator(options_.comparator)); |
679 | | |
680 | 1.02k | support_prev_ = true; |
681 | 1.02k | only_support_prefix_seek_ = false; |
682 | 1.02k | options_.allow_mmap_reads = args.use_mmap; |
683 | 1.02k | switch (args.type) { |
684 | 240 | case BLOCK_BASED_TABLE_TEST: |
685 | 240 | table_options_.flush_block_policy_factory.reset( |
686 | 240 | new FlushBlockBySizePolicyFactory()); |
687 | 240 | table_options_.block_size = 256; |
688 | 240 | table_options_.block_restart_interval = args.restart_interval; |
689 | 240 | table_options_.index_block_restart_interval = args.restart_interval; |
690 | 240 | table_options_.format_version = args.format_version; |
691 | 240 | options_.table_factory.reset( |
692 | 240 | new BlockBasedTableFactory(table_options_)); |
693 | 240 | constructor_ = new TableConstructor(options_.comparator); |
694 | 240 | break; |
695 | | // Plain table is not supported in ROCKSDB_LITE |
696 | 0 | #ifndef ROCKSDB_LITE |
697 | 20 | case PLAIN_TABLE_SEMI_FIXED_PREFIX: |
698 | 20 | support_prev_ = false; |
699 | 20 | only_support_prefix_seek_ = true; |
700 | 20 | options_.prefix_extractor.reset(new FixedOrLessPrefixTransform(2)); |
701 | 20 | options_.table_factory.reset(NewPlainTableFactory()); |
702 | 20 | constructor_ = new TableConstructor(options_.comparator, true); |
703 | 20 | internal_comparator_.reset( |
704 | 20 | new InternalKeyComparator(options_.comparator)); |
705 | 20 | break; |
706 | 20 | case PLAIN_TABLE_FULL_STR_PREFIX: |
707 | 20 | support_prev_ = false; |
708 | 20 | only_support_prefix_seek_ = true; |
709 | 20 | options_.prefix_extractor.reset(NewNoopTransform()); |
710 | 20 | options_.table_factory.reset(NewPlainTableFactory()); |
711 | 20 | constructor_ = new TableConstructor(options_.comparator, true); |
712 | 20 | internal_comparator_.reset( |
713 | 20 | new InternalKeyComparator(options_.comparator)); |
714 | 20 | break; |
715 | 20 | case PLAIN_TABLE_TOTAL_ORDER: |
716 | 20 | support_prev_ = false; |
717 | 20 | only_support_prefix_seek_ = false; |
718 | 20 | options_.prefix_extractor = nullptr; |
719 | | |
720 | 20 | { |
721 | 20 | PlainTableOptions plain_table_options; |
722 | 20 | plain_table_options.user_key_len = kPlainTableVariableLength; |
723 | 20 | plain_table_options.bloom_bits_per_key = 0; |
724 | 20 | plain_table_options.hash_table_ratio = 0; |
725 | | |
726 | 20 | options_.table_factory.reset( |
727 | 20 | NewPlainTableFactory(plain_table_options)); |
728 | 20 | } |
729 | 20 | constructor_ = new TableConstructor(options_.comparator, true); |
730 | 20 | internal_comparator_.reset( |
731 | 20 | new InternalKeyComparator(options_.comparator)); |
732 | 20 | break; |
733 | 0 | #endif // !ROCKSDB_LITE |
734 | 240 | case BLOCK_TEST: |
735 | 240 | table_options_.block_size = 256; |
736 | 240 | options_.table_factory.reset( |
737 | 240 | new BlockBasedTableFactory(table_options_)); |
738 | 240 | constructor_ = new BlockConstructor(options_.comparator); |
739 | 240 | break; |
740 | 240 | case MEMTABLE_TEST: |
741 | 240 | table_options_.block_size = 256; |
742 | 240 | options_.table_factory.reset( |
743 | 240 | new BlockBasedTableFactory(table_options_)); |
744 | 240 | constructor_ = new MemTableConstructor(options_.comparator, |
745 | 240 | &write_buffer_); |
746 | 240 | break; |
747 | 241 | case DB_TEST: |
748 | 241 | table_options_.block_size = 256; |
749 | 241 | options_.table_factory.reset( |
750 | 241 | new BlockBasedTableFactory(table_options_)); |
751 | 241 | constructor_ = new DBConstructor(options_.comparator); |
752 | 241 | break; |
753 | 1.02k | } |
754 | 1.02k | ioptions_ = ImmutableCFOptions(options_); |
755 | 1.02k | } |
756 | | |
757 | 7 | ~HarnessTest() { delete constructor_; } |
758 | | |
759 | 2.28M | void Add(const std::string& key, const std::string& value) { |
760 | 2.28M | constructor_->Add(key, value); |
761 | 2.28M | } |
762 | | |
763 | 13.0k | void Test(Random* rnd) { |
764 | 13.0k | std::vector<std::string> keys; |
765 | 13.0k | stl_wrappers::KVMap data; |
766 | 13.0k | constructor_->Finish(options_, ioptions_, table_options_, |
767 | 13.0k | internal_comparator_, &keys, &data); |
768 | | |
769 | 13.0k | TestForwardScan(keys, data); |
770 | 13.0k | if (support_prev_) { |
771 | 12.2k | TestBackwardScan(keys, data); |
772 | 12.2k | } |
773 | 13.0k | TestRandomAccess(rnd, keys, data); |
774 | 13.0k | } |
775 | | |
776 | | void TestForwardScan(const std::vector<std::string>& keys, |
777 | 13.0k | const stl_wrappers::KVMap& data) { |
778 | 13.0k | InternalIterator* iter = constructor_->NewIterator(); |
779 | 13.0k | ASSERT_TRUE(!iter->Valid()); |
780 | 13.0k | iter->SeekToFirst(); |
781 | 13.0k | for (stl_wrappers::KVMap::const_iterator model_iter = data.begin(); |
782 | 960k | model_iter != data.end(); ++model_iter) { |
783 | 947k | ASSERT_EQ(ToString(data, model_iter), ToString(iter)); |
784 | 947k | iter->Next(); |
785 | 947k | } |
786 | 13.0k | ASSERT_TRUE(!iter->Valid()); |
787 | 13.0k | if (constructor_->IsArenaMode() && !constructor_->AnywayDeleteIterator()) { |
788 | 0 | iter->~InternalIterator(); |
789 | 13.0k | } else { |
790 | 13.0k | delete iter; |
791 | 13.0k | } |
792 | 13.0k | } |
793 | | |
794 | | void TestBackwardScan(const std::vector<std::string>& keys, |
795 | 12.2k | const stl_wrappers::KVMap& data) { |
796 | 12.2k | InternalIterator* iter = constructor_->NewIterator(); |
797 | 12.2k | ASSERT_TRUE(!iter->Valid()); |
798 | 12.2k | iter->SeekToLast(); |
799 | 12.2k | for (stl_wrappers::KVMap::const_reverse_iterator model_iter = data.rbegin(); |
800 | 905k | model_iter != data.rend(); ++model_iter) { |
801 | 893k | ASSERT_EQ(ToString(data, model_iter), ToString(iter)); |
802 | 893k | iter->Prev(); |
803 | 893k | } |
804 | 12.2k | ASSERT_TRUE(!iter->Valid()); |
805 | 12.2k | if (constructor_->IsArenaMode() && !constructor_->AnywayDeleteIterator()) { |
806 | 0 | iter->~InternalIterator(); |
807 | 12.2k | } else { |
808 | 12.2k | delete iter; |
809 | 12.2k | } |
810 | 12.2k | } |
811 | | |
812 | | void TestRandomAccess(Random* rnd, const std::vector<std::string>& keys, |
813 | 13.0k | const stl_wrappers::KVMap& data) { |
814 | 13.0k | static const bool kVerbose = false; |
815 | 13.0k | InternalIterator* iter = constructor_->NewIterator(); |
816 | 13.0k | ASSERT_TRUE(!iter->Valid()); |
817 | 13.0k | stl_wrappers::KVMap::const_iterator model_iter = data.begin(); |
818 | 13.0k | if (kVerbose) fprintf(stderr, "---\n"); |
819 | 2.62M | for (int i = 0; i < 200; i++) { |
820 | 2.45M | const int toss = rnd->Uniform(support_prev_ ? 5 : 3); |
821 | 2.61M | switch (toss) { |
822 | 544k | case 0: { |
823 | 544k | if (iter->Valid()) { |
824 | 441k | if (kVerbose) fprintf(stderr, "Next\n"); |
825 | 441k | iter->Next(); |
826 | 441k | ++model_iter; |
827 | 441k | ASSERT_EQ(ToString(data, model_iter), ToString(iter)); |
828 | 441k | } |
829 | 544k | break; |
830 | 544k | } |
831 | | |
832 | 535k | case 1: { |
833 | 535k | if (kVerbose) fprintf(stderr, "SeekToFirst\n"); |
834 | 535k | iter->SeekToFirst(); |
835 | 535k | model_iter = data.begin(); |
836 | 535k | ASSERT_EQ(ToString(data, model_iter), ToString(iter)); |
837 | 535k | break; |
838 | 535k | } |
839 | | |
840 | 537k | case 2: { |
841 | 537k | std::string key = PickRandomKey(rnd, keys); |
842 | 537k | model_iter = data.lower_bound(key); |
843 | 537k | if (kVerbose) fprintf(stderr, "Seek '%s'\n", |
844 | 0 | EscapeString(key).c_str()); |
845 | 537k | iter->Seek(Slice(key)); |
846 | 537k | ASSERT_EQ(ToString(data, model_iter), ToString(iter)); |
847 | 537k | break; |
848 | 537k | } |
849 | | |
850 | 497k | case 3: { |
851 | 497k | if (iter->Valid()) { |
852 | 394k | if (kVerbose) fprintf(stderr, "Prev\n"); |
853 | 394k | iter->Prev(); |
854 | 394k | if (model_iter == data.begin()) { |
855 | 112k | model_iter = data.end(); // Wrap around to invalid value |
856 | 281k | } else { |
857 | 281k | --model_iter; |
858 | 281k | } |
859 | 394k | ASSERT_EQ(ToString(data, model_iter), ToString(iter)); |
860 | 394k | } |
861 | 497k | break; |
862 | 497k | } |
863 | | |
864 | 496k | case 4: { |
865 | 496k | if (kVerbose) fprintf(stderr, "SeekToLast\n"); |
866 | 496k | iter->SeekToLast(); |
867 | 496k | if (keys.empty()) { |
868 | 8.44k | model_iter = data.end(); |
869 | 488k | } else { |
870 | 488k | std::string last = data.rbegin()->first; |
871 | 488k | model_iter = data.lower_bound(last); |
872 | 488k | } |
873 | 496k | ASSERT_EQ(ToString(data, model_iter), ToString(iter)); |
874 | 496k | break; |
875 | 496k | } |
876 | 2.61M | } |
877 | 2.61M | } |
878 | 13.0k | if (constructor_->IsArenaMode() && !constructor_->AnywayDeleteIterator()) { |
879 | 0 | iter->~InternalIterator(); |
880 | 13.0k | } else { |
881 | 13.0k | delete iter; |
882 | 13.0k | } |
883 | 13.0k | } |
884 | | |
885 | | std::string ToString(const stl_wrappers::KVMap& data, |
886 | 3.35M | const stl_wrappers::KVMap::const_iterator& it) { |
887 | 3.35M | if (it == data.end()) { |
888 | 288k | return "END"; |
889 | 3.06M | } else { |
890 | 3.06M | return "'" + it->first + "->" + it->second + "'"; |
891 | 3.06M | } |
892 | 3.35M | } |
893 | | |
894 | | std::string ToString(const stl_wrappers::KVMap& data, |
895 | 893k | const stl_wrappers::KVMap::const_reverse_iterator& it) { |
896 | 893k | if (it == data.rend()) { |
897 | 0 | return "END"; |
898 | 893k | } else { |
899 | 893k | return "'" + it->first + "->" + it->second + "'"; |
900 | 893k | } |
901 | 893k | } |
902 | | |
903 | 4.24M | std::string ToString(const InternalIterator* it) { |
904 | 4.24M | if (!it->Valid()) { |
905 | 288k | return "END"; |
906 | 3.95M | } else { |
907 | 3.95M | return "'" + it->key().ToString() + "->" + it->value().ToString() + "'"; |
908 | 3.95M | } |
909 | 4.24M | } |
910 | | |
911 | 537k | std::string PickRandomKey(Random* rnd, const std::vector<std::string>& keys) { |
912 | 537k | if (keys.empty()) { |
913 | 8.36k | return "foo"; |
914 | 529k | } else { |
915 | 529k | const int index = rnd->Uniform(static_cast<int>(keys.size())); |
916 | 529k | std::string result = keys[index]; |
917 | 479k | switch (rnd->Uniform(support_prev_ ? 3 : 1)) { |
918 | 207k | case 0: |
919 | | // Return an existing key |
920 | 207k | break; |
921 | 163k | case 1: { |
922 | | // Attempt to return something smaller than an existing key |
923 | 163k | if (result.size() > 0 && result[result.size() - 1] > '\0' |
924 | 90.9k | && (!only_support_prefix_seek_ |
925 | 0 | || options_.prefix_extractor->Transform(result).size() |
926 | 90.9k | < result.size())) { |
927 | 90.9k | result[result.size() - 1]--; |
928 | 90.9k | } |
929 | 163k | break; |
930 | 0 | } |
931 | 157k | case 2: { |
932 | | // Return something larger than an existing key |
933 | 157k | Increment(options_.comparator, &result); |
934 | 157k | break; |
935 | 529k | } |
936 | 529k | } |
937 | 529k | return result; |
938 | 529k | } |
939 | 537k | } |
940 | | |
941 | | // Returns nullptr if not running against a DB |
942 | 15 | DB* db() const { return constructor_->db(); } |
943 | | |
944 | | private: |
945 | | Options options_ = Options(); |
946 | | ImmutableCFOptions ioptions_; |
947 | | BlockBasedTableOptions table_options_ = BlockBasedTableOptions(); |
948 | | Constructor* constructor_; |
949 | | WriteBuffer write_buffer_; |
950 | | bool support_prev_; |
951 | | bool only_support_prefix_seek_; |
952 | | InternalKeyComparatorPtr internal_comparator_; |
953 | | }; |
954 | | |
955 | 35 | static bool Between(uint64_t val, uint64_t low, uint64_t high) { |
956 | 35 | bool result = (val >= low) && (val <= high); |
957 | 35 | if (!result) { |
958 | 0 | fprintf(stderr, "Value %" PRIu64 " is not in range [%" PRIu64 ", %" PRIu64 "]\n", |
959 | 0 | val, low, high); |
960 | 0 | } |
961 | 35 | return result; |
962 | 35 | } |
963 | | |
964 | | // Tests against all kinds of tables |
965 | | class TableTest : public RocksDBTest { |
966 | | public: |
967 | | const InternalKeyComparatorPtr& GetPlainInternalComparator( |
968 | 116 | const Comparator* comp) { |
969 | 116 | if (!plain_internal_comparator) { |
970 | 8 | plain_internal_comparator = std::make_shared<test::PlainInternalKeyComparator>(comp); |
971 | 8 | } |
972 | 116 | return plain_internal_comparator; |
973 | 116 | } |
974 | | |
975 | | void TestIndex(BlockBasedTableOptions table_options, int expected_num_index_levels); |
976 | | void TestTotalOrderSeekOnHashIndex( |
977 | | const BlockBasedTableOptions& table_options, const Options& options); |
978 | | |
979 | | private: |
980 | | InternalKeyComparatorPtr plain_internal_comparator; |
981 | | }; |
982 | | |
983 | | class GeneralTableTest : public TableTest {}; |
984 | | class BlockBasedTableTest : public TableTest {}; |
985 | | class PlainTableTest : public TableTest {}; |
986 | | class TablePropertyTest : public RocksDBTest {}; |
987 | | |
988 | | // This test serves as the living tutorial for the prefix scan of user collected |
989 | | // properties. |
990 | 1 | TEST_F(TablePropertyTest, PrefixScanTest) { |
991 | 1 | UserCollectedProperties props{{"num.111.1", "1"}, |
992 | 1 | {"num.111.2", "2"}, |
993 | 1 | {"num.111.3", "3"}, |
994 | 1 | {"num.333.1", "1"}, |
995 | 1 | {"num.333.2", "2"}, |
996 | 1 | {"num.333.3", "3"}, |
997 | 1 | {"num.555.1", "1"}, |
998 | 1 | {"num.555.2", "2"}, |
999 | 1 | {"num.555.3", "3"}, }; |
1000 | | |
1001 | | // prefixes that exist |
1002 | 3 | for (const std::string& prefix : {"num.111", "num.333", "num.555"}) { |
1003 | 3 | int num = 0; |
1004 | 3 | for (auto pos = props.lower_bound(prefix); |
1005 | 12 | pos != props.end() && |
1006 | 11 | pos->first.compare(0, prefix.size(), prefix) == 0; |
1007 | 9 | ++pos) { |
1008 | 9 | ++num; |
1009 | 9 | auto key = prefix + "." + ToString(num); |
1010 | 9 | ASSERT_EQ(key, pos->first); |
1011 | 9 | ASSERT_EQ(ToString(num), pos->second); |
1012 | 9 | } |
1013 | 3 | ASSERT_EQ(3, num); |
1014 | 3 | } |
1015 | | |
1016 | | // prefixes that don't exist |
1017 | 1 | for (const std::string& prefix : |
1018 | 4 | {"num.000", "num.222", "num.444", "num.666"}) { |
1019 | 4 | auto pos = props.lower_bound(prefix); |
1020 | 4 | ASSERT_TRUE(pos == props.end() || |
1021 | 4 | pos->first.compare(0, prefix.size(), prefix) != 0); |
1022 | 4 | } |
1023 | 1 | } |
1024 | | |
1025 | | // This test include all the basic checks except those for index size and block |
1026 | | // size, which will be conducted in separated unit tests. |
1027 | 1 | TEST_F(BlockBasedTableTest, BasicBlockBasedTableProperties) { |
1028 | 1 | TableConstructor c(BytewiseComparator()); |
1029 | | |
1030 | 1 | c.Add("a1", "val1"); |
1031 | 1 | c.Add("b2", "val2"); |
1032 | 1 | c.Add("c3", "val3"); |
1033 | 1 | c.Add("d4", "val4"); |
1034 | 1 | c.Add("e5", "val5"); |
1035 | 1 | c.Add("f6", "val6"); |
1036 | 1 | c.Add("g7", "val7"); |
1037 | 1 | c.Add("h8", "val8"); |
1038 | 1 | c.Add("j9", "val9"); |
1039 | | |
1040 | 1 | std::vector<std::string> keys; |
1041 | 1 | stl_wrappers::KVMap kvmap; |
1042 | 1 | Options options; |
1043 | 1 | options.compression = kNoCompression; |
1044 | 1 | BlockBasedTableOptions table_options; |
1045 | 1 | table_options.block_restart_interval = 1; |
1046 | 1 | options.table_factory.reset(NewBlockBasedTableFactory(table_options)); |
1047 | | |
1048 | 1 | const ImmutableCFOptions ioptions(options); |
1049 | 1 | c.Finish(options, ioptions, table_options, |
1050 | 1 | GetPlainInternalComparator(options.comparator), &keys, &kvmap); |
1051 | | |
1052 | 1 | auto& props = *c.GetTableReader()->GetTableProperties(); |
1053 | 1 | ASSERT_EQ(kvmap.size(), props.num_entries); |
1054 | | |
1055 | 1 | auto raw_key_size = kvmap.size() * 2ul; |
1056 | 1 | auto raw_value_size = kvmap.size() * 4ul; |
1057 | | |
1058 | 1 | ASSERT_EQ(raw_key_size, props.raw_key_size); |
1059 | 1 | ASSERT_EQ(raw_value_size, props.raw_value_size); |
1060 | 1 | ASSERT_EQ(1ul, props.num_data_blocks); |
1061 | 1 | ASSERT_EQ("", props.filter_policy_name); // no filter policy is used |
1062 | | |
1063 | | // Verify data size. |
1064 | 1 | BlockBuilder block_builder(1, table_options.data_block_key_value_encoding_format); |
1065 | 9 | for (const auto& item : kvmap) { |
1066 | 9 | block_builder.Add(item.first, item.second); |
1067 | 9 | } |
1068 | 1 | Slice content = block_builder.Finish(); |
1069 | 1 | ASSERT_EQ(content.size() + kBlockTrailerSize, props.data_size); |
1070 | 1 | } |
1071 | | |
1072 | 1 | TEST_F(BlockBasedTableTest, FilterPolicyNameProperties) { |
1073 | 1 | TableConstructor c(BytewiseComparator(), true); |
1074 | 1 | c.Add("a1", "val1"); |
1075 | 1 | std::vector<std::string> keys; |
1076 | 1 | stl_wrappers::KVMap kvmap; |
1077 | | |
1078 | 1 | BlockBasedTableOptions table_options; |
1079 | 3 | for (int i = 0; i < 2; i++) { |
1080 | 2 | switch (i) { |
1081 | 1 | case 0: |
1082 | 1 | table_options.filter_policy.reset(NewBloomFilterPolicy(10)); |
1083 | 1 | break; |
1084 | 1 | default: |
1085 | 1 | SetFixedSizeFilterPolicy(&table_options); |
1086 | 2 | } |
1087 | 2 | Options options; |
1088 | 2 | options.table_factory.reset(NewBlockBasedTableFactory(table_options)); |
1089 | | |
1090 | 2 | const ImmutableCFOptions ioptions(options); |
1091 | 2 | c.Finish(options, ioptions, table_options, |
1092 | 2 | GetPlainInternalComparator(options.comparator), &keys, &kvmap); |
1093 | 2 | auto& props = *c.GetTableReader()->GetTableProperties(); |
1094 | 2 | switch (i) { |
1095 | 1 | case 0: |
1096 | 1 | ASSERT_EQ("rocksdb.BuiltinBloomFilter", props.filter_policy_name); |
1097 | 1 | break; |
1098 | 1 | default: |
1099 | 1 | ASSERT_EQ("rocksdb.FixedSizeBloomFilter", props.filter_policy_name); |
1100 | 1 | break; |
1101 | 2 | } |
1102 | 2 | } |
1103 | 1 | } |
1104 | | |
1105 | | // |
1106 | | // BlockBasedTableTest::PrefetchTest |
1107 | | // |
1108 | | void AssertKeysInCache(BlockBasedTable* table_reader, |
1109 | | const std::vector<std::string>& keys_in_cache, |
1110 | 10 | const std::vector<std::string>& keys_not_in_cache) { |
1111 | 48 | for (auto key : keys_in_cache) { |
1112 | 48 | ASSERT_TRUE(table_reader->TEST_KeyInCache(ReadOptions(), key)); |
1113 | 48 | } |
1114 | | |
1115 | 15 | for (auto key : keys_not_in_cache) { |
1116 | 15 | ASSERT_TRUE(!table_reader->TEST_KeyInCache(ReadOptions(), key)); |
1117 | 15 | } |
1118 | 10 | } |
1119 | | |
1120 | | void PrefetchRange(TableConstructor* c, Options* opt, |
1121 | | BlockBasedTableOptions* table_options, |
1122 | | const std::vector<std::string>& keys, const char* key_begin, |
1123 | | const char* key_end, |
1124 | | const std::vector<std::string>& keys_in_cache, |
1125 | | const std::vector<std::string>& keys_not_in_cache, |
1126 | 10 | const Status expected_status = Status::OK()) { |
1127 | | // reset the cache and reopen the table |
1128 | 10 | table_options->block_cache = |
1129 | 10 | NewLRUCache((16 * 1024 * 1024) / FLAGS_cache_single_touch_ratio); |
1130 | 10 | opt->table_factory.reset(NewBlockBasedTableFactory(*table_options)); |
1131 | 10 | const ImmutableCFOptions ioptions2(*opt); |
1132 | 10 | ASSERT_OK(c->Reopen(ioptions2)); |
1133 | | |
1134 | | // prefetch |
1135 | 10 | auto* table_reader = dynamic_cast<BlockBasedTable*>(c->GetTableReader()); |
1136 | | // empty string replacement is a trick so we don't crash the test |
1137 | 8 | Slice begin(key_begin ? key_begin : ""); |
1138 | 8 | Slice end(key_end ? key_end : ""); |
1139 | 8 | Status s = table_reader->Prefetch(key_begin ? &begin : nullptr, |
1140 | 8 | key_end ? &end : nullptr); |
1141 | 10 | ASSERT_TRUE(s.code() == expected_status.code()); |
1142 | | |
1143 | | // assert our expectation in cache warmup |
1144 | 10 | AssertKeysInCache(table_reader, keys_in_cache, keys_not_in_cache); |
1145 | 10 | } |
1146 | | |
1147 | 1 | TEST_F(BlockBasedTableTest, PrefetchTest) { |
1148 | | // The purpose of this test is to test the prefetching operation built into |
1149 | | // BlockBasedTable. |
1150 | 1 | Options opt; |
1151 | 1 | auto ikc = std::make_shared<test::PlainInternalKeyComparator>(opt.comparator); |
1152 | 1 | opt.compression = kNoCompression; |
1153 | 1 | BlockBasedTableOptions table_options; |
1154 | 1 | table_options.block_size = 1024; |
1155 | | // big enough so we don't ever lose cached values. |
1156 | 1 | table_options.block_cache = |
1157 | 1 | NewLRUCache((16 * 1024 * 1024) / FLAGS_cache_single_touch_ratio); |
1158 | 1 | opt.table_factory.reset(NewBlockBasedTableFactory(table_options)); |
1159 | | |
1160 | 1 | TableConstructor c(BytewiseComparator()); |
1161 | 1 | c.Add("k01", "hello"); |
1162 | 1 | c.Add("k02", "hello2"); |
1163 | 1 | c.Add("k03", std::string(10000, 'x')); |
1164 | 1 | c.Add("k04", std::string(200000, 'x')); |
1165 | 1 | c.Add("k05", std::string(300000, 'x')); |
1166 | 1 | c.Add("k06", "hello3"); |
1167 | 1 | c.Add("k07", std::string(100000, 'x')); |
1168 | 1 | std::vector<std::string> keys; |
1169 | 1 | stl_wrappers::KVMap kvmap; |
1170 | 1 | const ImmutableCFOptions ioptions(opt); |
1171 | 1 | c.Finish(opt, ioptions, table_options, ikc, &keys, &kvmap); |
1172 | | |
1173 | | // We get the following data spread : |
1174 | | // |
1175 | | // Data block Index |
1176 | | // ======================== |
1177 | | // [ k01 k02 k03 ] k03 |
1178 | | // [ k04 ] k04 |
1179 | | // [ k05 ] k05 |
1180 | | // [ k06 k07 ] k07 |
1181 | | |
1182 | | |
1183 | | // Simple |
1184 | 1 | PrefetchRange(&c, &opt, &table_options, keys, |
1185 | 1 | /*key_range=*/ "k01", "k05", |
1186 | 1 | /*keys_in_cache=*/ {"k01", "k02", "k03", "k04", "k05"}, |
1187 | 1 | /*keys_not_in_cache=*/ {"k06", "k07"}); |
1188 | 1 | PrefetchRange(&c, &opt, &table_options, keys, |
1189 | 1 | "k01", "k01", |
1190 | 1 | {"k01", "k02", "k03"}, |
1191 | 1 | {"k04", "k05", "k06", "k07"}); |
1192 | | // odd |
1193 | 1 | PrefetchRange(&c, &opt, &table_options, keys, |
1194 | 1 | "a", "z", |
1195 | 1 | {"k01", "k02", "k03", "k04", "k05", "k06", "k07"}, |
1196 | 1 | {}); |
1197 | 1 | PrefetchRange(&c, &opt, &table_options, keys, |
1198 | 1 | "k00", "k00", |
1199 | 1 | {"k01", "k02", "k03"}, |
1200 | 1 | {"k04", "k05", "k06", "k07"}); |
1201 | | // Edge cases |
1202 | 1 | PrefetchRange(&c, &opt, &table_options, keys, |
1203 | 1 | "k00", "k06", |
1204 | 1 | {"k01", "k02", "k03", "k04", "k05", "k06", "k07"}, |
1205 | 1 | {}); |
1206 | 1 | PrefetchRange(&c, &opt, &table_options, keys, |
1207 | 1 | "k00", "zzz", |
1208 | 1 | {"k01", "k02", "k03", "k04", "k05", "k06", "k07"}, |
1209 | 1 | {}); |
1210 | | // null keys |
1211 | 1 | PrefetchRange(&c, &opt, &table_options, keys, |
1212 | 1 | nullptr, nullptr, |
1213 | 1 | {"k01", "k02", "k03", "k04", "k05", "k06", "k07"}, |
1214 | 1 | {}); |
1215 | 1 | PrefetchRange(&c, &opt, &table_options, keys, |
1216 | 1 | "k04", nullptr, |
1217 | 1 | {"k04", "k05", "k06", "k07"}, |
1218 | 1 | {"k01", "k02", "k03"}); |
1219 | 1 | PrefetchRange(&c, &opt, &table_options, keys, |
1220 | 1 | nullptr, "k05", |
1221 | 1 | {"k01", "k02", "k03", "k04", "k05"}, |
1222 | 1 | {"k06", "k07"}); |
1223 | | // invalid |
1224 | 1 | PrefetchRange(&c, &opt, &table_options, keys, |
1225 | 1 | "k06", "k00", {}, {}, |
1226 | 1 | STATUS(InvalidArgument, Slice("k06 "), Slice("k07"))); |
1227 | 1 | } |
1228 | | |
1229 | | void TableTest::TestTotalOrderSeekOnHashIndex( |
1230 | 6 | const BlockBasedTableOptions& table_options, const Options& options) { |
1231 | 6 | TableConstructor c(BytewiseComparator(), true); |
1232 | 6 | c.Add("aaaa1", std::string('a', 56)); |
1233 | 6 | c.Add("bbaa1", std::string('a', 56)); |
1234 | 6 | c.Add("cccc1", std::string('a', 56)); |
1235 | 6 | c.Add("bbbb1", std::string('a', 56)); |
1236 | 6 | c.Add("baaa1", std::string('a', 56)); |
1237 | 6 | c.Add("abbb1", std::string('a', 56)); |
1238 | 6 | c.Add("cccc2", std::string('a', 56)); |
1239 | 6 | std::vector<std::string> keys; |
1240 | 6 | stl_wrappers::KVMap kvmap; |
1241 | 6 | const ImmutableCFOptions ioptions(options); |
1242 | 6 | c.Finish(options, ioptions, table_options, |
1243 | 6 | GetPlainInternalComparator(options.comparator), &keys, &kvmap); |
1244 | 6 | auto props = c.GetTableReader()->GetTableProperties(); |
1245 | 6 | ASSERT_EQ(7u, props->num_data_blocks); |
1246 | 6 | auto* reader = c.GetTableReader(); |
1247 | 6 | ReadOptions ro; |
1248 | 6 | ro.total_order_seek = true; |
1249 | 6 | std::unique_ptr<InternalIterator> iter(reader->NewIterator(ro)); |
1250 | | |
1251 | 6 | iter->Seek(InternalKey("b", 0, kTypeValue).Encode()); |
1252 | 6 | ASSERT_OK(iter->status()); |
1253 | 6 | ASSERT_TRUE(iter->Valid()); |
1254 | 6 | ASSERT_EQ("baaa1", ExtractUserKey(iter->key()).ToString()); |
1255 | 6 | iter->Next(); |
1256 | 6 | ASSERT_OK(iter->status()); |
1257 | 6 | ASSERT_TRUE(iter->Valid()); |
1258 | 6 | ASSERT_EQ("bbaa1", ExtractUserKey(iter->key()).ToString()); |
1259 | | |
1260 | 6 | iter->Seek(InternalKey("bb", 0, kTypeValue).Encode()); |
1261 | 6 | ASSERT_OK(iter->status()); |
1262 | 6 | ASSERT_TRUE(iter->Valid()); |
1263 | 6 | ASSERT_EQ("bbaa1", ExtractUserKey(iter->key()).ToString()); |
1264 | 6 | iter->Next(); |
1265 | 6 | ASSERT_OK(iter->status()); |
1266 | 6 | ASSERT_TRUE(iter->Valid()); |
1267 | 6 | ASSERT_EQ("bbbb1", ExtractUserKey(iter->key()).ToString()); |
1268 | | |
1269 | 6 | iter->Seek(InternalKey("bbb", 0, kTypeValue).Encode()); |
1270 | 6 | ASSERT_OK(iter->status()); |
1271 | 6 | ASSERT_TRUE(iter->Valid()); |
1272 | 6 | ASSERT_EQ("bbbb1", ExtractUserKey(iter->key()).ToString()); |
1273 | 6 | iter->Next(); |
1274 | 6 | ASSERT_OK(iter->status()); |
1275 | 6 | ASSERT_TRUE(iter->Valid()); |
1276 | 6 | ASSERT_EQ("cccc1", ExtractUserKey(iter->key()).ToString()); |
1277 | 6 | } |
1278 | | |
1279 | 1 | TEST_F(BlockBasedTableTest, TotalOrderSeekOnHashIndex) { |
1280 | 1 | BlockBasedTableOptions table_options; |
1281 | | // Make each key/value an individual block |
1282 | 1 | table_options.block_size = 64; |
1283 | | |
1284 | | // Binary search index |
1285 | 1 | { |
1286 | 1 | Options options; |
1287 | 1 | table_options.index_type = IndexType::kBinarySearch; |
1288 | 1 | options.table_factory.reset(new BlockBasedTableFactory(table_options)); |
1289 | 1 | TestTotalOrderSeekOnHashIndex(table_options, options); |
1290 | 1 | } |
1291 | | // Hash search index |
1292 | 1 | { |
1293 | 1 | Options options; |
1294 | 1 | table_options.index_type = IndexType::kHashSearch; |
1295 | 1 | options.table_factory.reset(new BlockBasedTableFactory(table_options)); |
1296 | 1 | options.prefix_extractor.reset(NewFixedPrefixTransform(4)); |
1297 | 1 | TestTotalOrderSeekOnHashIndex(table_options, options); |
1298 | 1 | } |
1299 | 1 | { |
1300 | | // Hash search index with hash_index_allow_collision |
1301 | 1 | Options options; |
1302 | 1 | table_options.index_type = IndexType::kHashSearch; |
1303 | 1 | table_options.hash_index_allow_collision = true; |
1304 | 1 | options.table_factory.reset(new BlockBasedTableFactory(table_options)); |
1305 | 1 | options.prefix_extractor.reset(NewFixedPrefixTransform(4)); |
1306 | 1 | TestTotalOrderSeekOnHashIndex(table_options, options); |
1307 | 1 | } |
1308 | 1 | { |
1309 | | // Binary search index with fixed size filter policy |
1310 | 1 | Options options; |
1311 | 1 | table_options.index_type = IndexType::kBinarySearch; |
1312 | 1 | SetFixedSizeFilterPolicy(&table_options); |
1313 | 1 | options.table_factory.reset(new BlockBasedTableFactory(table_options)); |
1314 | 1 | TestTotalOrderSeekOnHashIndex(table_options, options); |
1315 | 1 | } |
1316 | 1 | { |
1317 | | // Hash search index with filter policy |
1318 | 1 | Options options; |
1319 | 1 | table_options.index_type = IndexType::kHashSearch; |
1320 | 1 | table_options.filter_policy.reset(NewBloomFilterPolicy(10)); |
1321 | 1 | options.table_factory.reset(new BlockBasedTableFactory(table_options)); |
1322 | 1 | options.prefix_extractor.reset(NewFixedPrefixTransform(4)); |
1323 | 1 | TestTotalOrderSeekOnHashIndex(table_options, options); |
1324 | 1 | } |
1325 | 1 | { |
1326 | | // Multi level sharded index with fixed size filter policy |
1327 | 1 | Options options; |
1328 | 1 | table_options.index_type = IndexType::kMultiLevelBinarySearch; |
1329 | 1 | SetFixedSizeFilterPolicy(&table_options); |
1330 | 1 | options.table_factory.reset(new BlockBasedTableFactory(table_options)); |
1331 | 1 | TestTotalOrderSeekOnHashIndex(table_options, options); |
1332 | 1 | } |
1333 | 1 | } |
1334 | | |
1335 | 1 | TEST_F(BlockBasedTableTest, NoopTransformSeek) { |
1336 | 1 | BlockBasedTableOptions table_options; |
1337 | 3 | for (int it = 0; it < 2; it++) { |
1338 | 2 | switch (it) { |
1339 | 1 | case 0: |
1340 | 1 | table_options.filter_policy.reset(NewBloomFilterPolicy(10)); |
1341 | 1 | break; |
1342 | 1 | default: |
1343 | 1 | SetFixedSizeFilterPolicy(&table_options); |
1344 | 1 | break; |
1345 | 2 | } |
1346 | | |
1347 | 2 | Options options; |
1348 | 2 | options.comparator = BytewiseComparator(); |
1349 | 2 | options.table_factory.reset(new BlockBasedTableFactory(table_options)); |
1350 | 2 | options.prefix_extractor.reset(NewNoopTransform()); |
1351 | | |
1352 | 2 | TableConstructor c(options.comparator); |
1353 | | // To tickle the PrefixMayMatch bug it is important that the |
1354 | | // user-key is a single byte so that the index key exactly matches |
1355 | | // the user-key. |
1356 | 2 | InternalKey key("a", 1, kTypeValue); |
1357 | 2 | c.Add(key.Encode().ToBuffer(), "b"); |
1358 | 2 | std::vector<std::string> keys; |
1359 | 2 | stl_wrappers::KVMap kvmap; |
1360 | 2 | const ImmutableCFOptions ioptions(options); |
1361 | 2 | auto internal_comparator = std::make_shared<InternalKeyComparator>(options.comparator); |
1362 | 2 | c.Finish(options, ioptions, table_options, internal_comparator, &keys, &kvmap); |
1363 | | |
1364 | 2 | auto* reader = c.GetTableReader(); |
1365 | 6 | for (int i = 0; i < 2; ++i) { |
1366 | 4 | ReadOptions ro; |
1367 | 4 | ro.total_order_seek = (i == 0); |
1368 | 4 | std::unique_ptr<InternalIterator> iter(reader->NewIterator(ro)); |
1369 | | |
1370 | 4 | iter->Seek(key.Encode()); |
1371 | 4 | ASSERT_OK(iter->status()); |
1372 | 4 | ASSERT_TRUE(iter->Valid()); |
1373 | 4 | ASSERT_EQ("a", ExtractUserKey(iter->key()).ToString()); |
1374 | 4 | } |
1375 | 2 | } |
1376 | 1 | } |
1377 | | |
1378 | | void AddInternalKey(TableConstructor* c, const std::string& prefix, |
1379 | 50 | int suffix_len = 800) { |
1380 | 50 | static Random rnd(1023); |
1381 | 50 | InternalKey k(prefix + RandomString(&rnd, 800), 0, kTypeValue); |
1382 | 50 | c->Add(k.Encode().ToString(), "v"); |
1383 | 50 | } |
1384 | | |
1385 | 5 | void TableTest::TestIndex(BlockBasedTableOptions table_options, int expected_num_index_levels) { |
1386 | 5 | TableConstructor c(BytewiseComparator()); |
1387 | | |
1388 | | // keys with prefix length 3, make sure the key/value is big enough to fill |
1389 | | // one block |
1390 | 5 | AddInternalKey(&c, "0015"); |
1391 | 5 | AddInternalKey(&c, "0035"); |
1392 | | |
1393 | 5 | AddInternalKey(&c, "0054"); |
1394 | 5 | AddInternalKey(&c, "0055"); |
1395 | | |
1396 | 5 | AddInternalKey(&c, "0056"); |
1397 | 5 | AddInternalKey(&c, "0057"); |
1398 | | |
1399 | 5 | AddInternalKey(&c, "0058"); |
1400 | 5 | AddInternalKey(&c, "0075"); |
1401 | | |
1402 | 5 | AddInternalKey(&c, "0076"); |
1403 | 5 | AddInternalKey(&c, "0095"); |
1404 | | |
1405 | 5 | std::vector<std::string> keys; |
1406 | 5 | stl_wrappers::KVMap kvmap; |
1407 | 5 | Options options; |
1408 | 5 | options.prefix_extractor.reset(NewFixedPrefixTransform(3)); |
1409 | 5 | table_options.block_size = 1700; |
1410 | 5 | table_options.block_cache = NewLRUCache(1024); |
1411 | 5 | options.table_factory.reset(NewBlockBasedTableFactory(table_options)); |
1412 | | |
1413 | 5 | auto comparator = std::make_shared<InternalKeyComparator>(BytewiseComparator()); |
1414 | 5 | const ImmutableCFOptions ioptions(options); |
1415 | 5 | c.Finish(options, ioptions, table_options, comparator, &keys, &kvmap); |
1416 | 5 | { |
1417 | 5 | auto props = c.GetTableProperties().user_collected_properties; |
1418 | 5 | auto pos = props.find(BlockBasedTablePropertyNames::kNumIndexLevels); |
1419 | 5 | DCHECK(pos != props.end()); |
1420 | 5 | int num_index_levels = DecodeFixed32(pos->second.c_str()); |
1421 | 5 | ASSERT_EQ(expected_num_index_levels, num_index_levels); |
1422 | 5 | } |
1423 | 5 | auto reader = c.GetTableReader(); |
1424 | | |
1425 | 5 | auto props = reader->GetTableProperties(); |
1426 | 5 | ASSERT_EQ(5u, props->num_data_blocks); |
1427 | | |
1428 | 5 | std::unique_ptr<InternalIterator> iter(reader->NewIterator(ReadOptions())); |
1429 | | |
1430 | | // -- Find keys do not exist, but have common prefix. |
1431 | 5 | std::vector<std::string> prefixes = {"001", "003", "005", "007", "009"}; |
1432 | 5 | std::vector<std::string> lower_bound = {keys[0], keys[1], keys[2], |
1433 | 5 | keys[7], keys[9], }; |
1434 | | |
1435 | | // find the lower bound of the prefix |
1436 | 30 | for (size_t i = 0; i < prefixes.size(); ++i) { |
1437 | 25 | iter->Seek(InternalKey(prefixes[i], 0, kTypeValue).Encode()); |
1438 | 25 | ASSERT_OK(iter->status()); |
1439 | 25 | ASSERT_TRUE(iter->Valid()); |
1440 | | |
1441 | | // seek the first element in the block |
1442 | 25 | ASSERT_EQ(lower_bound[i], iter->key().ToString()); |
1443 | 25 | ASSERT_EQ("v", iter->value().ToString()); |
1444 | 25 | } |
1445 | | |
1446 | | // find the upper bound of prefixes |
1447 | 5 | std::vector<std::string> upper_bound = {keys[1], keys[2], keys[7], keys[9], }; |
1448 | | |
1449 | | // find existing keys |
1450 | 50 | for (const auto& item : kvmap) { |
1451 | 50 | auto ukey = ExtractUserKey(item.first).ToString(); |
1452 | 50 | iter->Seek(ukey); |
1453 | | |
1454 | | // ASSERT_OK(regular_iter->status()); |
1455 | 50 | ASSERT_OK(iter->status()); |
1456 | | |
1457 | | // ASSERT_TRUE(regular_iter->Valid()); |
1458 | 50 | ASSERT_TRUE(iter->Valid()); |
1459 | | |
1460 | 50 | ASSERT_EQ(item.first, iter->key().ToString()); |
1461 | 50 | ASSERT_EQ(item.second, iter->value().ToString()); |
1462 | 50 | } |
1463 | | |
1464 | 30 | for (size_t i = 0; i < prefixes.size(); ++i) { |
1465 | | // the key is greater than any existing keys. |
1466 | 25 | auto key = prefixes[i] + "9"; |
1467 | 25 | iter->Seek(InternalKey(key, 0, kTypeValue).Encode()); |
1468 | | |
1469 | 25 | ASSERT_OK(iter->status()); |
1470 | 25 | if (i == prefixes.size() - 1) { |
1471 | | // last key |
1472 | 5 | ASSERT_TRUE(!iter->Valid()); |
1473 | 20 | } else { |
1474 | 20 | ASSERT_TRUE(iter->Valid()); |
1475 | | // seek the first element in the block |
1476 | 20 | ASSERT_EQ(upper_bound[i], iter->key().ToString()); |
1477 | 20 | ASSERT_EQ("v", iter->value().ToString()); |
1478 | 20 | } |
1479 | 25 | } |
1480 | | |
1481 | | // find keys with prefix that don't match any of the existing prefixes. |
1482 | 5 | std::vector<std::string> non_exist_prefixes = {"002", "004", "006", "008"}; |
1483 | 20 | for (const auto& prefix : non_exist_prefixes) { |
1484 | 20 | iter->Seek(InternalKey(prefix, 0, kTypeValue).Encode()); |
1485 | | // regular_iter->Seek(prefix); |
1486 | | |
1487 | 20 | ASSERT_OK(iter->status()); |
1488 | | // Seek to non-existing prefixes should yield either invalid, or a |
1489 | | // key with prefix greater than the target. |
1490 | 20 | if (iter->Valid()) { |
1491 | 18 | Slice ukey = ExtractUserKey(iter->key()); |
1492 | 18 | Slice ukey_prefix = options.prefix_extractor->Transform(ukey); |
1493 | 18 | ASSERT_LT(BytewiseComparator()->Compare(prefix, ukey_prefix), 0); |
1494 | 18 | } |
1495 | 20 | } |
1496 | 5 | } |
1497 | | |
1498 | 1 | TEST_F(TableTest, BinaryIndexTest) { |
1499 | 1 | BlockBasedTableOptions table_options; |
1500 | 1 | table_options.index_type = IndexType::kBinarySearch; |
1501 | 1 | TestIndex(table_options, 1); |
1502 | 1 | } |
1503 | | |
1504 | 1 | TEST_F(TableTest, HashIndexTest) { |
1505 | 1 | BlockBasedTableOptions table_options; |
1506 | 1 | table_options.index_type = IndexType::kHashSearch; |
1507 | 1 | table_options.hash_index_allow_collision = true; |
1508 | 1 | TestIndex(table_options, 1); |
1509 | 1 | } |
1510 | | |
1511 | 1 | TEST_F(TableTest, MultiLevelIndexTest) { |
1512 | 1 | BlockBasedTableOptions table_options; |
1513 | 1 | table_options.index_type = IndexType::kMultiLevelBinarySearch; |
1514 | 1 | constexpr int keys = 5; |
1515 | 4 | for (int entries_per_index_block = 2; entries_per_index_block < keys; ++entries_per_index_block) { |
1516 | 3 | table_options.min_keys_per_index_block = 2; |
1517 | 3 | table_options.index_block_size = entries_per_index_block * 24; |
1518 | 3 | const int expected_index_levels = static_cast<int>( |
1519 | 3 | ceil(std::log(keys) / std::log(entries_per_index_block))); |
1520 | 3 | TestIndex(table_options, expected_index_levels); |
1521 | 3 | } |
1522 | 1 | } |
1523 | | |
1524 | | // It's very hard to figure out the index block size of a block accurately. |
1525 | | // To make sure we get the index size, we just make sure as key number |
1526 | | // grows, the filter block size also grows. |
1527 | 1 | TEST_F(BlockBasedTableTest, IndexSizeStat) { |
1528 | 1 | uint64_t last_index_size = 0; |
1529 | | |
1530 | | // we need to use random keys since the pure human readable texts |
1531 | | // may be well compressed, resulting insignificant change of index |
1532 | | // block size. |
1533 | 1 | Random rnd(test::RandomSeed()); |
1534 | 1 | std::vector<std::string> keys; |
1535 | | |
1536 | 101 | for (int i = 0; i < 100; ++i) { |
1537 | 100 | keys.push_back(RandomString(&rnd, 10000)); |
1538 | 100 | } |
1539 | | |
1540 | | // Each time we load one more key to the table. the table index block |
1541 | | // size is expected to be larger than last time's. |
1542 | 100 | for (size_t i = 1; i < keys.size(); ++i) { |
1543 | 99 | TableConstructor c(BytewiseComparator()); |
1544 | 5.04k | for (size_t j = 0; j < i; ++j) { |
1545 | 4.95k | c.Add(keys[j], "val"); |
1546 | 4.95k | } |
1547 | | |
1548 | 99 | std::vector<std::string> ks; |
1549 | 99 | stl_wrappers::KVMap kvmap; |
1550 | 99 | Options options; |
1551 | 99 | options.compression = kNoCompression; |
1552 | 99 | BlockBasedTableOptions table_options; |
1553 | 99 | table_options.block_restart_interval = 1; |
1554 | 99 | options.table_factory.reset(NewBlockBasedTableFactory(table_options)); |
1555 | | |
1556 | 99 | const ImmutableCFOptions ioptions(options); |
1557 | 99 | c.Finish(options, ioptions, table_options, |
1558 | 99 | GetPlainInternalComparator(options.comparator), &ks, &kvmap); |
1559 | 99 | auto index_size = c.GetTableReader()->GetTableProperties()->data_index_size; |
1560 | 99 | ASSERT_GT(index_size, last_index_size); |
1561 | 99 | last_index_size = index_size; |
1562 | 99 | } |
1563 | 1 | } |
1564 | | |
1565 | 1 | TEST_F(BlockBasedTableTest, NumBlockStat) { |
1566 | 1 | Random rnd(test::RandomSeed()); |
1567 | 1 | TableConstructor c(BytewiseComparator()); |
1568 | 1 | Options options; |
1569 | 1 | options.compression = kNoCompression; |
1570 | 1 | BlockBasedTableOptions table_options; |
1571 | 1 | table_options.block_restart_interval = 1; |
1572 | 1 | table_options.block_size = 1000; |
1573 | 1 | options.table_factory.reset(NewBlockBasedTableFactory(table_options)); |
1574 | | |
1575 | 11 | for (int i = 0; i < 10; ++i) { |
1576 | | // the key/val are slightly smaller than block size, so that each block |
1577 | | // holds roughly one key/value pair. |
1578 | 10 | c.Add(RandomString(&rnd, 900), "val"); |
1579 | 10 | } |
1580 | | |
1581 | 1 | std::vector<std::string> ks; |
1582 | 1 | stl_wrappers::KVMap kvmap; |
1583 | 1 | const ImmutableCFOptions ioptions(options); |
1584 | 1 | c.Finish(options, ioptions, table_options, |
1585 | 1 | GetPlainInternalComparator(options.comparator), &ks, &kvmap); |
1586 | 1 | ASSERT_EQ(kvmap.size(), |
1587 | 1 | c.GetTableReader()->GetTableProperties()->num_data_blocks); |
1588 | 1 | } |
1589 | | |
1590 | | // A simple tool that takes the snapshot of block cache statistics. |
1591 | | class BlockCachePropertiesSnapshot { |
1592 | | public: |
1593 | 10 | explicit BlockCachePropertiesSnapshot(Statistics* statistics) { |
1594 | 10 | block_cache_miss = statistics->getTickerCount(BLOCK_CACHE_MISS); |
1595 | 10 | block_cache_hit = statistics->getTickerCount(BLOCK_CACHE_HIT); |
1596 | 10 | index_block_cache_miss = statistics->getTickerCount(BLOCK_CACHE_INDEX_MISS); |
1597 | 10 | index_block_cache_hit = statistics->getTickerCount(BLOCK_CACHE_INDEX_HIT); |
1598 | 10 | data_block_cache_miss = statistics->getTickerCount(BLOCK_CACHE_DATA_MISS); |
1599 | 10 | data_block_cache_hit = statistics->getTickerCount(BLOCK_CACHE_DATA_HIT); |
1600 | 10 | filter_block_cache_miss = |
1601 | 10 | statistics->getTickerCount(BLOCK_CACHE_FILTER_MISS); |
1602 | 10 | filter_block_cache_hit = statistics->getTickerCount(BLOCK_CACHE_FILTER_HIT); |
1603 | 10 | block_cache_bytes_read = statistics->getTickerCount(BLOCK_CACHE_BYTES_READ); |
1604 | 10 | block_cache_bytes_write = |
1605 | 10 | statistics->getTickerCount(BLOCK_CACHE_BYTES_WRITE); |
1606 | 10 | } |
1607 | | |
1608 | | void AssertIndexBlockStat(int64_t expected_index_block_cache_miss, |
1609 | 2 | int64_t expected_index_block_cache_hit) { |
1610 | 2 | ASSERT_EQ(expected_index_block_cache_miss, index_block_cache_miss); |
1611 | 2 | ASSERT_EQ(expected_index_block_cache_hit, index_block_cache_hit); |
1612 | 2 | } |
1613 | | |
1614 | | void AssertFilterBlockStat(int64_t expected_filter_block_cache_miss, |
1615 | 3 | int64_t expected_filter_block_cache_hit) { |
1616 | 3 | ASSERT_EQ(expected_filter_block_cache_miss, filter_block_cache_miss); |
1617 | 3 | ASSERT_EQ(expected_filter_block_cache_hit, filter_block_cache_hit); |
1618 | 3 | } |
1619 | | |
1620 | | // Check if the fetched props matches the expected ones. |
1621 | | // TODO(kailiu) Use this only when you disabled filter policy! |
1622 | | void AssertEqual(int64_t expected_index_block_cache_miss, |
1623 | | int64_t expected_index_block_cache_hit, |
1624 | | int64_t expected_data_block_cache_miss, |
1625 | 7 | int64_t expected_data_block_cache_hit) const { |
1626 | 7 | ASSERT_EQ(expected_index_block_cache_miss, index_block_cache_miss); |
1627 | 7 | ASSERT_EQ(expected_index_block_cache_hit, index_block_cache_hit); |
1628 | 7 | ASSERT_EQ(expected_data_block_cache_miss, data_block_cache_miss); |
1629 | 7 | ASSERT_EQ(expected_data_block_cache_hit, data_block_cache_hit); |
1630 | 7 | ASSERT_EQ(expected_index_block_cache_miss + expected_data_block_cache_miss, |
1631 | 7 | block_cache_miss); |
1632 | 7 | ASSERT_EQ(expected_index_block_cache_hit + expected_data_block_cache_hit, |
1633 | 7 | block_cache_hit); |
1634 | 7 | } |
1635 | | |
1636 | 11 | int64_t GetCacheBytesRead() { return block_cache_bytes_read; } |
1637 | | |
1638 | 4 | int64_t GetCacheBytesWrite() { return block_cache_bytes_write; } |
1639 | | |
1640 | | private: |
1641 | | int64_t block_cache_miss = 0; |
1642 | | int64_t block_cache_hit = 0; |
1643 | | int64_t index_block_cache_miss = 0; |
1644 | | int64_t index_block_cache_hit = 0; |
1645 | | int64_t data_block_cache_miss = 0; |
1646 | | int64_t data_block_cache_hit = 0; |
1647 | | int64_t filter_block_cache_miss = 0; |
1648 | | int64_t filter_block_cache_hit = 0; |
1649 | | int64_t block_cache_bytes_read = 0; |
1650 | | int64_t block_cache_bytes_write = 0; |
1651 | | }; |
1652 | | |
1653 | | // Make sure, by default, index/filter blocks were pre-loaded (meaning we won't |
1654 | | // use block cache to store them). |
1655 | 1 | TEST_F(BlockBasedTableTest, BlockCacheDisabledTest) { |
1656 | 1 | Options options; |
1657 | 1 | options.create_if_missing = true; |
1658 | 1 | options.statistics = CreateDBStatisticsForTests(); |
1659 | 1 | BlockBasedTableOptions table_options; |
1660 | 1 | table_options.block_cache = NewLRUCache(1024); |
1661 | 1 | table_options.filter_policy.reset(NewBloomFilterPolicy(10)); |
1662 | 1 | options.table_factory.reset(new BlockBasedTableFactory(table_options)); |
1663 | 1 | std::vector<std::string> keys; |
1664 | 1 | stl_wrappers::KVMap kvmap; |
1665 | | |
1666 | 1 | TableConstructor c(BytewiseComparator(), true); |
1667 | 1 | c.Add("key", "value"); |
1668 | 1 | const ImmutableCFOptions ioptions(options); |
1669 | 1 | c.Finish(options, ioptions, table_options, |
1670 | 1 | GetPlainInternalComparator(options.comparator), &keys, &kvmap); |
1671 | | |
1672 | | // preloading is enabled for filter blocks, disabled for index blocks. |
1673 | 1 | auto reader = dynamic_cast<BlockBasedTable*>(c.GetTableReader()); |
1674 | 1 | ASSERT_TRUE(reader->TEST_filter_block_preloaded()); |
1675 | 1 | ASSERT_FALSE(reader->TEST_index_reader_loaded()); |
1676 | | |
1677 | 1 | { |
1678 | | // nothing happens in the beginning |
1679 | 1 | BlockCachePropertiesSnapshot props(options.statistics.get()); |
1680 | 1 | props.AssertIndexBlockStat(0, 0); |
1681 | 1 | props.AssertFilterBlockStat(0, 0); |
1682 | 1 | } |
1683 | | |
1684 | 1 | { |
1685 | 1 | GetContext get_context(options.comparator, nullptr, nullptr, nullptr, |
1686 | 1 | GetContext::kNotFound, Slice(), nullptr, nullptr, |
1687 | 1 | nullptr, nullptr); |
1688 | | // a hack that just to trigger BlockBasedTable::GetFilter. |
1689 | 1 | ASSERT_OK(reader->Get(ReadOptions(), "non-exist-key", &get_context)); |
1690 | 1 | BlockCachePropertiesSnapshot props(options.statistics.get()); |
1691 | 1 | props.AssertIndexBlockStat(0, 0); |
1692 | 1 | props.AssertFilterBlockStat(0, 0); |
1693 | 1 | } |
1694 | | |
1695 | | // Index is loaded after first access. |
1696 | 1 | ASSERT_TRUE(reader->TEST_index_reader_loaded()); |
1697 | 1 | } |
1698 | | |
1699 | | // Due to the difficulities of the intersaction between statistics, this test |
1700 | | // only tests the case when "index block is put to block cache" |
1701 | 1 | TEST_F(BlockBasedTableTest, FilterBlockInBlockCache) { |
1702 | | // -- Table construction |
1703 | 1 | Options options; |
1704 | 1 | options.create_if_missing = true; |
1705 | 1 | options.statistics = CreateDBStatisticsForTests(); |
1706 | | |
1707 | | // Enable the cache for index/filter blocks |
1708 | 1 | BlockBasedTableOptions table_options; |
1709 | 1 | table_options.block_cache = NewLRUCache(1024 / FLAGS_cache_single_touch_ratio); |
1710 | 1 | table_options.cache_index_and_filter_blocks = true; |
1711 | 1 | options.table_factory.reset(new BlockBasedTableFactory(table_options)); |
1712 | 1 | std::vector<std::string> keys; |
1713 | 1 | stl_wrappers::KVMap kvmap; |
1714 | | |
1715 | 1 | TableConstructor c(BytewiseComparator()); |
1716 | 1 | c.Add("key", "value"); |
1717 | 1 | const ImmutableCFOptions ioptions(options); |
1718 | 1 | c.Finish(options, ioptions, table_options, |
1719 | 1 | GetPlainInternalComparator(options.comparator), &keys, &kvmap); |
1720 | | // preloading filter/index blocks is prohibited. |
1721 | 1 | auto* reader = dynamic_cast<BlockBasedTable*>(c.GetTableReader()); |
1722 | 1 | ASSERT_TRUE(!reader->TEST_filter_block_preloaded()); |
1723 | 1 | ASSERT_TRUE(!reader->TEST_index_reader_loaded()); |
1724 | | |
1725 | | // -- PART 1: Open with regular block cache. |
1726 | | // Since block_cache is disabled, no cache activities will be involved. |
1727 | 1 | unique_ptr<InternalIterator> iter; |
1728 | | |
1729 | 1 | int64_t last_cache_bytes_read = 0; |
1730 | | // At first, no block will be accessed. |
1731 | 1 | { |
1732 | 1 | BlockCachePropertiesSnapshot props(options.statistics.get()); |
1733 | | // index won't be added to block cache. |
1734 | 1 | props.AssertEqual(0, // index block miss |
1735 | 1 | 0, 0, 0); |
1736 | 1 | ASSERT_EQ(props.GetCacheBytesRead(), 0); |
1737 | 1 | ASSERT_EQ(props.GetCacheBytesWrite(), |
1738 | 1 | table_options.block_cache->GetUsage()); |
1739 | 1 | last_cache_bytes_read = props.GetCacheBytesRead(); |
1740 | 1 | } |
1741 | | |
1742 | | // Only index block will be accessed |
1743 | 1 | { |
1744 | 1 | iter.reset(c.NewIterator()); |
1745 | 1 | BlockCachePropertiesSnapshot props(options.statistics.get()); |
1746 | 1 | props.AssertEqual(1, // index block miss |
1747 | 1 | 0, 0, 0); |
1748 | | // Cache miss, Bytes read from cache should not change |
1749 | 1 | ASSERT_EQ(props.GetCacheBytesRead(), last_cache_bytes_read); |
1750 | 1 | ASSERT_EQ(props.GetCacheBytesWrite(), |
1751 | 1 | table_options.block_cache->GetUsage()); |
1752 | 1 | last_cache_bytes_read = props.GetCacheBytesRead(); |
1753 | 1 | } |
1754 | | |
1755 | | // Only data block will be accessed |
1756 | 1 | { |
1757 | 1 | iter->SeekToFirst(); |
1758 | 1 | BlockCachePropertiesSnapshot props(options.statistics.get()); |
1759 | | // NOTE: to help better highlight the "detla" of each ticker, I use |
1760 | | // <last_value> + <added_value> to indicate the increment of changed |
1761 | | // value; other numbers remain the same. |
1762 | 1 | props.AssertEqual(1, 0, 0 + 1, // data block miss |
1763 | 1 | 0); |
1764 | | // Cache miss, Bytes read from cache should not change |
1765 | 1 | ASSERT_EQ(props.GetCacheBytesRead(), last_cache_bytes_read); |
1766 | 1 | ASSERT_EQ(props.GetCacheBytesWrite(), |
1767 | 1 | table_options.block_cache->GetUsage()); |
1768 | 1 | last_cache_bytes_read = props.GetCacheBytesRead(); |
1769 | 1 | } |
1770 | | |
1771 | | // Data block will be in cache |
1772 | 1 | { |
1773 | 1 | iter.reset(c.NewIterator()); |
1774 | 1 | iter->SeekToFirst(); |
1775 | 1 | BlockCachePropertiesSnapshot props(options.statistics.get()); |
1776 | 1 | props.AssertEqual(1, 0 + 1, /* index block hit */ |
1777 | 1 | 1, 0 + 1 /* data block hit */); |
1778 | | // Cache hit, bytes read from cache should increase |
1779 | 1 | ASSERT_GT(props.GetCacheBytesRead(), last_cache_bytes_read); |
1780 | 1 | ASSERT_EQ(props.GetCacheBytesWrite(), |
1781 | 1 | table_options.block_cache->GetUsage()); |
1782 | 1 | last_cache_bytes_read = props.GetCacheBytesRead(); |
1783 | 1 | } |
1784 | | // release the iterator so that the block cache can reset correctly. |
1785 | 1 | iter.reset(); |
1786 | | |
1787 | | // -- PART 2: Open with very small block cache |
1788 | | // In this test, no block will ever get hit since the block cache is |
1789 | | // too small to fit even one entry. |
1790 | 1 | table_options.block_cache = NewLRUCache(1); |
1791 | 1 | options.statistics = CreateDBStatisticsForTests(); |
1792 | 1 | options.table_factory.reset(new BlockBasedTableFactory(table_options)); |
1793 | 1 | const ImmutableCFOptions ioptions2(options); |
1794 | 1 | ASSERT_OK(c.Reopen(ioptions2)); |
1795 | 1 | { |
1796 | 1 | BlockCachePropertiesSnapshot props(options.statistics.get()); |
1797 | 1 | props.AssertEqual(0, // index block miss |
1798 | 1 | 0, 0, 0); |
1799 | | // Cache miss, Bytes read from cache should not change |
1800 | 1 | ASSERT_EQ(props.GetCacheBytesRead(), 0); |
1801 | 1 | } |
1802 | | |
1803 | 1 | { |
1804 | | // Both index and data block get accessed. |
1805 | | // It first cache index block then data block. But since the cache size |
1806 | | // is only 1, index block will be purged after data block is inserted. |
1807 | 1 | iter.reset(c.NewIterator()); |
1808 | 1 | BlockCachePropertiesSnapshot props(options.statistics.get()); |
1809 | 1 | props.AssertEqual(0 + 1, // index block miss |
1810 | 1 | 0, 0, // data block miss |
1811 | 1 | 0); |
1812 | | // Cache hit, bytes read from cache should increase |
1813 | 1 | ASSERT_EQ(props.GetCacheBytesRead(), 0); |
1814 | 1 | } |
1815 | | |
1816 | 1 | { |
1817 | | // SeekToFirst() accesses data block. With similar reason, we expect data |
1818 | | // block's cache miss. |
1819 | 1 | iter->SeekToFirst(); |
1820 | 1 | BlockCachePropertiesSnapshot props(options.statistics.get()); |
1821 | 1 | props.AssertEqual(1, 0, 0 + 1, // data block miss |
1822 | 1 | 0); |
1823 | | // Cache miss, Bytes read from cache should not change |
1824 | 1 | ASSERT_EQ(props.GetCacheBytesRead(), 0); |
1825 | 1 | } |
1826 | 1 | iter.reset(); |
1827 | | |
1828 | | // -- PART 3: Open table with bloom filter enabled but not in SST file |
1829 | 1 | table_options.block_cache = NewLRUCache(4096); |
1830 | 1 | table_options.cache_index_and_filter_blocks = false; |
1831 | 1 | options.table_factory.reset(NewBlockBasedTableFactory(table_options)); |
1832 | | |
1833 | 1 | TableConstructor c3(BytewiseComparator()); |
1834 | 1 | std::string user_key = "k01"; |
1835 | 1 | InternalKey internal_key(user_key, 0, kTypeValue); |
1836 | 1 | const std::string encoded_key = internal_key.Encode().ToString(); |
1837 | 1 | c3.Add(encoded_key, "hello"); |
1838 | 1 | ImmutableCFOptions ioptions3(options); |
1839 | | // Generate table without filter policy |
1840 | 1 | c3.Finish(options, ioptions3, table_options, |
1841 | 1 | GetPlainInternalComparator(options.comparator), &keys, &kvmap); |
1842 | | // Open table with filter policy |
1843 | 1 | table_options.filter_policy.reset(NewBloomFilterPolicy(1)); |
1844 | 1 | options.table_factory.reset(new BlockBasedTableFactory(table_options)); |
1845 | 1 | options.statistics = CreateDBStatisticsForTests(); |
1846 | 1 | ImmutableCFOptions ioptions4(options); |
1847 | 1 | ASSERT_OK(c3.Reopen(ioptions4)); |
1848 | 1 | reader = dynamic_cast<BlockBasedTable*>(c3.GetTableReader()); |
1849 | 1 | ASSERT_TRUE(!reader->TEST_filter_block_preloaded()); |
1850 | 1 | std::string value; |
1851 | 1 | GetContext get_context(options.comparator, nullptr, nullptr, nullptr, |
1852 | 1 | GetContext::kNotFound, user_key, &value, nullptr, |
1853 | 1 | nullptr, nullptr); |
1854 | 1 | ASSERT_OK(reader->Get(ReadOptions(), encoded_key, &get_context)); |
1855 | 1 | ASSERT_EQ(value, "hello"); |
1856 | 1 | BlockCachePropertiesSnapshot props(options.statistics.get()); |
1857 | 1 | props.AssertFilterBlockStat(0, 0); |
1858 | 1 | } |
1859 | | |
1860 | 8 | void ValidateBlockSizeDeviation(int value, int expected) { |
1861 | 8 | BlockBasedTableOptions table_options; |
1862 | 8 | table_options.block_size_deviation = value; |
1863 | 8 | BlockBasedTableFactory* factory = new BlockBasedTableFactory(table_options); |
1864 | | |
1865 | 8 | const BlockBasedTableOptions* normalized_table_options = |
1866 | 8 | (const BlockBasedTableOptions*)factory->GetOptions(); |
1867 | 8 | ASSERT_EQ(normalized_table_options->block_size_deviation, expected); |
1868 | | |
1869 | 8 | delete factory; |
1870 | 8 | } |
1871 | | |
1872 | 6 | void ValidateBlockRestartInterval(int value, int expected) { |
1873 | 6 | BlockBasedTableOptions table_options; |
1874 | 6 | table_options.block_restart_interval = value; |
1875 | 6 | BlockBasedTableFactory* factory = new BlockBasedTableFactory(table_options); |
1876 | | |
1877 | 6 | const BlockBasedTableOptions* normalized_table_options = |
1878 | 6 | (const BlockBasedTableOptions*)factory->GetOptions(); |
1879 | 6 | ASSERT_EQ(normalized_table_options->block_restart_interval, expected); |
1880 | | |
1881 | 6 | delete factory; |
1882 | 6 | } |
1883 | | |
1884 | 1 | TEST_F(BlockBasedTableTest, InvalidOptions) { |
1885 | | // invalid values for block_size_deviation (<0 or >100) are silently set to 0 |
1886 | 1 | ValidateBlockSizeDeviation(-10, 0); |
1887 | 1 | ValidateBlockSizeDeviation(-1, 0); |
1888 | 1 | ValidateBlockSizeDeviation(0, 0); |
1889 | 1 | ValidateBlockSizeDeviation(1, 1); |
1890 | 1 | ValidateBlockSizeDeviation(99, 99); |
1891 | 1 | ValidateBlockSizeDeviation(100, 100); |
1892 | 1 | ValidateBlockSizeDeviation(101, 0); |
1893 | 1 | ValidateBlockSizeDeviation(1000, 0); |
1894 | | |
1895 | | // invalid values for block_restart_interval (<1) are silently set to 1 |
1896 | 1 | ValidateBlockRestartInterval(-10, 1); |
1897 | 1 | ValidateBlockRestartInterval(-1, 1); |
1898 | 1 | ValidateBlockRestartInterval(0, 1); |
1899 | 1 | ValidateBlockRestartInterval(1, 1); |
1900 | 1 | ValidateBlockRestartInterval(2, 2); |
1901 | 1 | ValidateBlockRestartInterval(1000, 1000); |
1902 | 1 | } |
1903 | | |
1904 | 1 | TEST_F(BlockBasedTableTest, BlockReadCountTest) { |
1905 | | // bloom_filter_type = 0 -- block-based filter |
1906 | | // bloom_filter_type = 1 -- full filter |
1907 | 3 | for (int bloom_filter_type = 0; bloom_filter_type < 2; ++bloom_filter_type) { |
1908 | 6 | for (int filter_in_cache = 0; filter_in_cache < 2; |
1909 | 4 | ++filter_in_cache) { |
1910 | 4 | Options options; |
1911 | 4 | options.create_if_missing = true; |
1912 | | |
1913 | 4 | BlockBasedTableOptions table_options; |
1914 | 4 | table_options.block_cache = NewLRUCache(1, 0); |
1915 | 4 | table_options.cache_index_and_filter_blocks = filter_in_cache; |
1916 | 4 | table_options.filter_policy.reset( |
1917 | 4 | NewBloomFilterPolicy(10, bloom_filter_type == 0)); |
1918 | 4 | options.table_factory.reset(new BlockBasedTableFactory(table_options)); |
1919 | 4 | std::vector<std::string> keys; |
1920 | 4 | stl_wrappers::KVMap kvmap; |
1921 | | |
1922 | 4 | TableConstructor c(BytewiseComparator()); |
1923 | 4 | std::string user_key = "k04"; |
1924 | 4 | InternalKey internal_key(user_key, 0, kTypeValue); |
1925 | 4 | std::string encoded_key = internal_key.Encode().ToString(); |
1926 | 4 | c.Add(encoded_key, "hello"); |
1927 | 4 | ImmutableCFOptions ioptions(options); |
1928 | 4 | perf_context.Reset(); |
1929 | | // Generate table with filter policy |
1930 | 4 | c.Finish(options, ioptions, table_options, |
1931 | 4 | GetPlainInternalComparator(options.comparator), &keys, &kvmap); |
1932 | 4 | auto reader = c.GetTableReader(); |
1933 | | // Meta, properties and filter blocks. |
1934 | 4 | ASSERT_EQ(perf_context.block_read_count, 3); |
1935 | 4 | std::string value; |
1936 | 4 | GetContext get_context(options.comparator, nullptr, nullptr, nullptr, |
1937 | 4 | GetContext::kNotFound, user_key, &value, nullptr, |
1938 | 4 | nullptr, nullptr); |
1939 | 4 | perf_context.Reset(); |
1940 | 4 | ASSERT_OK(reader->Get(ReadOptions(), encoded_key, &get_context)); |
1941 | 4 | if (filter_in_cache) { |
1942 | | // Data, index and filter block. |
1943 | 2 | ASSERT_EQ(perf_context.block_read_count, 3); |
1944 | 2 | } else { |
1945 | | // Index, data block (filter is preloaded on open). |
1946 | 2 | ASSERT_EQ(perf_context.block_read_count, 2); |
1947 | 2 | } |
1948 | 4 | ASSERT_EQ(get_context.State(), GetContext::kFound); |
1949 | 4 | ASSERT_EQ(value, "hello"); |
1950 | | |
1951 | | // Get non-existing key |
1952 | 4 | user_key = "does-not-exist"; |
1953 | 4 | internal_key = InternalKey(user_key, 0, kTypeValue); |
1954 | 4 | encoded_key = internal_key.Encode().ToString(); |
1955 | | |
1956 | 4 | get_context = GetContext(options.comparator, nullptr, nullptr, nullptr, |
1957 | 4 | GetContext::kNotFound, user_key, &value, nullptr, |
1958 | 4 | nullptr, nullptr); |
1959 | 4 | perf_context.Reset(); |
1960 | 4 | ASSERT_OK(reader->Get(ReadOptions(), encoded_key, &get_context)); |
1961 | 4 | ASSERT_EQ(get_context.State(), GetContext::kNotFound); |
1962 | | |
1963 | 4 | if (filter_in_cache) { |
1964 | 2 | if (bloom_filter_type == 0) { |
1965 | | // with block-based, we read index and then the filter |
1966 | 1 | ASSERT_EQ(perf_context.block_read_count, 2); |
1967 | 1 | } else { |
1968 | | // with full-filter, we read filter first and then we stop |
1969 | 1 | ASSERT_EQ(perf_context.block_read_count, 1); |
1970 | 1 | } |
1971 | 2 | } else { |
1972 | | // filter is already in memory and it figures out that the key doesn't |
1973 | | // exist |
1974 | 2 | ASSERT_EQ(perf_context.block_read_count, 0); |
1975 | 2 | } |
1976 | 4 | } |
1977 | 2 | } |
1978 | 1 | } |
1979 | | |
1980 | 1 | TEST_F(BlockBasedTableTest, BlockCacheLeak) { |
1981 | | // Check that when we reopen a table we don't lose access to blocks already |
1982 | | // in the cache. This test checks whether the Table actually makes use of the |
1983 | | // unique ID from the file. |
1984 | | |
1985 | 1 | Options opt; |
1986 | 1 | auto ikc = std::make_shared<test::PlainInternalKeyComparator>(opt.comparator); |
1987 | 1 | opt.compression = kNoCompression; |
1988 | 1 | BlockBasedTableOptions table_options; |
1989 | 1 | table_options.block_size = 1024; |
1990 | | // big enough so we don't ever lose cached values. |
1991 | 1 | table_options.block_cache = NewLRUCache((16 * 1024 * 1024) / FLAGS_cache_single_touch_ratio); |
1992 | 1 | opt.table_factory.reset(NewBlockBasedTableFactory(table_options)); |
1993 | | |
1994 | 1 | TableConstructor c(BytewiseComparator()); |
1995 | 1 | c.Add("k01", "hello"); |
1996 | 1 | c.Add("k02", "hello2"); |
1997 | 1 | c.Add("k03", std::string(10000, 'x')); |
1998 | 1 | c.Add("k04", std::string(200000, 'x')); |
1999 | 1 | c.Add("k05", std::string(300000, 'x')); |
2000 | 1 | c.Add("k06", "hello3"); |
2001 | 1 | c.Add("k07", std::string(100000, 'x')); |
2002 | 1 | std::vector<std::string> keys; |
2003 | 1 | stl_wrappers::KVMap kvmap; |
2004 | 1 | const ImmutableCFOptions ioptions(opt); |
2005 | 1 | c.Finish(opt, ioptions, table_options, ikc, &keys, &kvmap); |
2006 | | |
2007 | 1 | { |
2008 | | // Put iterator into dedicated block, so it doesn't survive block_cache destruction. |
2009 | 1 | unique_ptr<InternalIterator> iter(c.NewIterator()); |
2010 | 1 | iter->SeekToFirst(); |
2011 | 8 | while (iter->Valid()) { |
2012 | 7 | iter->key(); |
2013 | 7 | iter->value(); |
2014 | 7 | iter->Next(); |
2015 | 7 | } |
2016 | 1 | ASSERT_OK(iter->status()); |
2017 | 1 | } |
2018 | | |
2019 | 1 | const ImmutableCFOptions ioptions1(opt); |
2020 | 1 | ASSERT_OK(c.Reopen(ioptions1)); |
2021 | 1 | auto table_reader = dynamic_cast<BlockBasedTable*>(c.GetTableReader()); |
2022 | 7 | for (const std::string& key : keys) { |
2023 | 7 | ASSERT_TRUE(table_reader->TEST_KeyInCache(ReadOptions(), key)); |
2024 | 7 | } |
2025 | | |
2026 | | // rerun with different block cache |
2027 | 1 | table_options.block_cache = |
2028 | 1 | NewLRUCache((16 * 1024 * 1024) / FLAGS_cache_single_touch_ratio); |
2029 | 1 | opt.table_factory.reset(NewBlockBasedTableFactory(table_options)); |
2030 | 1 | const ImmutableCFOptions ioptions2(opt); |
2031 | 1 | ASSERT_OK(c.Reopen(ioptions2)); |
2032 | 1 | table_reader = dynamic_cast<BlockBasedTable*>(c.GetTableReader()); |
2033 | 7 | for (const std::string& key : keys) { |
2034 | 7 | ASSERT_TRUE(!table_reader->TEST_KeyInCache(ReadOptions(), key)); |
2035 | 7 | } |
2036 | 1 | } |
2037 | | |
2038 | | // Plain table is not supported in ROCKSDB_LITE |
2039 | | #ifndef ROCKSDB_LITE |
2040 | 1 | TEST_F(PlainTableTest, BasicPlainTableProperties) { |
2041 | 1 | PlainTableOptions plain_table_options; |
2042 | 1 | plain_table_options.user_key_len = 8; |
2043 | 1 | plain_table_options.bloom_bits_per_key = 8; |
2044 | 1 | plain_table_options.hash_table_ratio = 0; |
2045 | | |
2046 | 1 | PlainTableFactory factory(plain_table_options); |
2047 | 1 | test::StringSink sink; |
2048 | 1 | unique_ptr<WritableFileWriter> file_writer( |
2049 | 1 | test::GetWritableFileWriter(new test::StringSink())); |
2050 | 1 | Options options; |
2051 | 1 | const ImmutableCFOptions ioptions(options); |
2052 | 1 | auto ikc = std::make_shared<InternalKeyComparator>(options.comparator); |
2053 | 1 | IntTblPropCollectorFactories int_tbl_prop_collector_factories; |
2054 | 1 | std::unique_ptr<TableBuilder> builder(factory.NewTableBuilder( |
2055 | 1 | TableBuilderOptions(ioptions, |
2056 | 1 | ikc, |
2057 | 1 | int_tbl_prop_collector_factories, |
2058 | 1 | kNoCompression, |
2059 | 1 | CompressionOptions(), |
2060 | 1 | /* skip_filters */ false), |
2061 | 1 | TablePropertiesCollectorFactory::Context::kUnknownColumnFamily, |
2062 | 1 | file_writer.get())); |
2063 | | |
2064 | 27 | for (char c = 'a'; c <= 'z'; ++c) { |
2065 | 26 | std::string key(8, c); |
2066 | 26 | key.append("\1 "); // PlainTable expects internal key structure |
2067 | 26 | std::string value(28, c + 42); |
2068 | 26 | builder->Add(key, value); |
2069 | 26 | } |
2070 | 1 | ASSERT_OK(builder->Finish()); |
2071 | 1 | ASSERT_OK(file_writer->Flush()); |
2072 | | |
2073 | 1 | test::StringSink* ss = |
2074 | 1 | static_cast<test::StringSink*>(file_writer->writable_file()); |
2075 | 1 | unique_ptr<RandomAccessFileReader> file_reader( |
2076 | 1 | test::GetRandomAccessFileReader( |
2077 | 1 | new test::StringSource(ss->contents(), 72242, true))); |
2078 | | |
2079 | 1 | TableProperties* props = nullptr; |
2080 | 1 | auto s = ReadTableProperties(file_reader.get(), ss->contents().size(), |
2081 | 1 | kPlainTableMagicNumber, Env::Default(), nullptr, |
2082 | 1 | &props); |
2083 | 1 | std::unique_ptr<TableProperties> props_guard(props); |
2084 | 1 | ASSERT_OK(s); |
2085 | | |
2086 | 1 | ASSERT_EQ(0ul, props->data_index_size); |
2087 | 1 | ASSERT_EQ(0ul, props->filter_size); |
2088 | 1 | ASSERT_EQ(16ul * 26, props->raw_key_size); |
2089 | 1 | ASSERT_EQ(28ul * 26, props->raw_value_size); |
2090 | 1 | ASSERT_EQ(26ul, props->num_entries); |
2091 | 1 | ASSERT_EQ(1ul, props->num_data_blocks); |
2092 | 1 | } |
2093 | | #endif // !ROCKSDB_LITE |
2094 | | |
2095 | 1 | TEST_F(GeneralTableTest, ApproximateOffsetOfPlain) { |
2096 | 1 | TableConstructor c(BytewiseComparator()); |
2097 | 1 | c.Add("k01", "hello"); |
2098 | 1 | c.Add("k02", "hello2"); |
2099 | 1 | c.Add("k03", std::string(10000, 'x')); |
2100 | 1 | c.Add("k04", std::string(200000, 'x')); |
2101 | 1 | c.Add("k05", std::string(300000, 'x')); |
2102 | 1 | c.Add("k06", "hello3"); |
2103 | 1 | c.Add("k07", std::string(100000, 'x')); |
2104 | 1 | std::vector<std::string> keys; |
2105 | 1 | stl_wrappers::KVMap kvmap; |
2106 | 1 | Options options; |
2107 | 1 | auto internal_comparator = std::make_shared<test::PlainInternalKeyComparator>(options.comparator); |
2108 | 1 | options.compression = kNoCompression; |
2109 | 1 | BlockBasedTableOptions table_options; |
2110 | 1 | table_options.block_size = 1024; |
2111 | 1 | const ImmutableCFOptions ioptions(options); |
2112 | 1 | c.Finish(options, ioptions, table_options, internal_comparator, |
2113 | 1 | &keys, &kvmap); |
2114 | | |
2115 | 1 | ASSERT_TRUE(Between(c.ApproximateOffsetOf("abc"), 0, 0)); |
2116 | 1 | ASSERT_TRUE(Between(c.ApproximateOffsetOf("k01"), 0, 0)); |
2117 | 1 | ASSERT_TRUE(Between(c.ApproximateOffsetOf("k01a"), 0, 0)); |
2118 | 1 | ASSERT_TRUE(Between(c.ApproximateOffsetOf("k02"), 0, 0)); |
2119 | 1 | ASSERT_TRUE(Between(c.ApproximateOffsetOf("k03"), 0, 0)); |
2120 | 1 | ASSERT_TRUE(Between(c.ApproximateOffsetOf("k04"), 10000, 11000)); |
2121 | 1 | ASSERT_TRUE(Between(c.ApproximateOffsetOf("k04a"), 210000, 211000)); |
2122 | 1 | ASSERT_TRUE(Between(c.ApproximateOffsetOf("k05"), 210000, 211000)); |
2123 | 1 | ASSERT_TRUE(Between(c.ApproximateOffsetOf("k06"), 510000, 511000)); |
2124 | 1 | ASSERT_TRUE(Between(c.ApproximateOffsetOf("k07"), 510000, 511000)); |
2125 | 1 | ASSERT_TRUE(Between(c.ApproximateOffsetOf("xyz"), 610000, 612000)); |
2126 | 1 | } |
2127 | | |
2128 | 4 | static void DoCompressionTest(CompressionType comp) { |
2129 | 4 | Random rnd(301); |
2130 | 4 | TableConstructor c(BytewiseComparator()); |
2131 | 4 | std::string tmp; |
2132 | 4 | c.Add("k01", "hello"); |
2133 | 4 | c.Add("k02", CompressibleString(&rnd, 0.25, 10000, &tmp)); |
2134 | 4 | c.Add("k03", "hello3"); |
2135 | 4 | c.Add("k04", CompressibleString(&rnd, 0.25, 10000, &tmp)); |
2136 | 4 | std::vector<std::string> keys; |
2137 | 4 | stl_wrappers::KVMap kvmap; |
2138 | 4 | Options options; |
2139 | 4 | auto ikc = std::make_shared<test::PlainInternalKeyComparator>(options.comparator); |
2140 | 4 | options.compression = comp; |
2141 | 4 | BlockBasedTableOptions table_options; |
2142 | 4 | table_options.block_size = 1024; |
2143 | 4 | const ImmutableCFOptions ioptions(options); |
2144 | 4 | c.Finish(options, ioptions, table_options, ikc, &keys, &kvmap); |
2145 | | |
2146 | 4 | ASSERT_TRUE(Between(c.ApproximateOffsetOf("abc"), 0, 0)); |
2147 | 4 | ASSERT_TRUE(Between(c.ApproximateOffsetOf("k01"), 0, 0)); |
2148 | 4 | ASSERT_TRUE(Between(c.ApproximateOffsetOf("k02"), 0, 0)); |
2149 | 4 | ASSERT_TRUE(Between(c.ApproximateOffsetOf("k03"), 2000, 3000)); |
2150 | 4 | ASSERT_TRUE(Between(c.ApproximateOffsetOf("k04"), 2000, 3000)); |
2151 | 4 | ASSERT_TRUE(Between(c.ApproximateOffsetOf("xyz"), 4000, 6100)); |
2152 | 4 | } |
2153 | | |
2154 | 1 | TEST_F(GeneralTableTest, ApproximateOffsetOfCompressed) { |
2155 | 1 | std::vector<CompressionType> compression_state; |
2156 | 1 | if (!Snappy_Supported()) { |
2157 | 0 | fprintf(stderr, "skipping snappy compression tests\n"); |
2158 | 1 | } else { |
2159 | 1 | compression_state.push_back(kSnappyCompression); |
2160 | 1 | } |
2161 | | |
2162 | 1 | if (!Zlib_Supported()) { |
2163 | 0 | fprintf(stderr, "skipping zlib compression tests\n"); |
2164 | 1 | } else { |
2165 | 1 | compression_state.push_back(kZlibCompression); |
2166 | 1 | } |
2167 | | |
2168 | | // TODO(kailiu) DoCompressionTest() doesn't work with BZip2. |
2169 | | /* |
2170 | | if (!BZip2_Supported()) { |
2171 | | fprintf(stderr, "skipping bzip2 compression tests\n"); |
2172 | | } else { |
2173 | | compression_state.push_back(kBZip2Compression); |
2174 | | } |
2175 | | */ |
2176 | | |
2177 | 1 | if (!LZ4_Supported()) { |
2178 | 0 | fprintf(stderr, "skipping lz4 and lz4hc compression tests\n"); |
2179 | 1 | } else { |
2180 | 1 | compression_state.push_back(kLZ4Compression); |
2181 | 1 | compression_state.push_back(kLZ4HCCompression); |
2182 | 1 | } |
2183 | | |
2184 | 4 | for (auto state : compression_state) { |
2185 | 4 | DoCompressionTest(state); |
2186 | 4 | } |
2187 | 1 | } |
2188 | | |
2189 | 1 | TEST_F(HarnessTest, Randomized) { |
2190 | | #if defined(THREAD_SANITIZER) |
2191 | | static constexpr int kMaxNumEntries = 200; |
2192 | | #else |
2193 | 1 | static constexpr int kMaxNumEntries = 2000; |
2194 | 1 | #endif |
2195 | 1 | std::vector<TestArgs> args = GenerateArgList(); |
2196 | 205 | for (unsigned int i = 0; i < args.size(); i++) { |
2197 | 204 | Init(args[i]); |
2198 | 204 | Random rnd(test::RandomSeed() + 5); |
2199 | 12.4k | for (int num_entries = 0; num_entries < kMaxNumEntries; |
2200 | 12.2k | num_entries += (num_entries < 50 ? 1 : 200)) { |
2201 | 12.2k | if ((num_entries % 10) == 0) { |
2202 | 3.06k | fprintf(stderr, "case %d of %d: num_entries = %d\n", (i + 1), |
2203 | 3.06k | static_cast<int>(args.size()), num_entries); |
2204 | 3.06k | } |
2205 | 2.20M | for (int e = 0; e < num_entries; e++) { |
2206 | 2.18M | std::string v; |
2207 | 2.18M | Add(test::RandomKey(&rnd, rnd.Skewed(4)), |
2208 | 2.18M | RandomString(&rnd, rnd.Skewed(5), &v).ToString()); |
2209 | 2.18M | } |
2210 | 12.2k | Test(&rnd); |
2211 | 12.2k | } |
2212 | 204 | } |
2213 | 1 | } |
2214 | | |
2215 | | #ifndef ROCKSDB_LITE |
2216 | 1 | TEST_F(HarnessTest, RandomizedLongDB) { |
2217 | 1 | Random rnd(test::RandomSeed()); |
2218 | 1 | TestArgs args = {DB_TEST, false, 16, kNoCompression, 0, false}; |
2219 | 1 | Init(args); |
2220 | 1 | int num_entries = 100000; |
2221 | 100k | for (int e = 0; e < num_entries; e++) { |
2222 | 100k | std::string v; |
2223 | 100k | Add(test::RandomKey(&rnd, rnd.Skewed(4)), |
2224 | 100k | RandomString(&rnd, rnd.Skewed(5), &v).ToString()); |
2225 | 100k | } |
2226 | 1 | Test(&rnd); |
2227 | | |
2228 | | // We must have created enough data to force merging |
2229 | 1 | int files = 0; |
2230 | 8 | for (int level = 0; level < db()->NumberLevels(); level++) { |
2231 | 7 | std::string value; |
2232 | 7 | char name[100]; |
2233 | 7 | snprintf(name, sizeof(name), "rocksdb.num-files-at-level%d", level); |
2234 | 7 | ASSERT_TRUE(db()->GetProperty(name, &value)); |
2235 | 7 | files += atoi(value.c_str()); |
2236 | 7 | } |
2237 | 1 | ASSERT_GT(files, 0); |
2238 | 1 | } |
2239 | | #endif // ROCKSDB_LITE |
2240 | | |
2241 | | class MemTableTest : public RocksDBTest {}; |
2242 | | |
2243 | 1 | TEST_F(MemTableTest, Simple) { |
2244 | 1 | InternalKeyComparator cmp(BytewiseComparator()); |
2245 | 1 | auto table_factory = std::make_shared<SkipListFactory>(); |
2246 | 1 | Options options; |
2247 | 1 | options.memtable_factory = table_factory; |
2248 | 1 | ImmutableCFOptions ioptions(options); |
2249 | 1 | WriteBuffer wb(options.db_write_buffer_size); |
2250 | 1 | MemTable* memtable = |
2251 | 1 | new MemTable(cmp, ioptions, MutableCFOptions(options, ioptions), &wb, |
2252 | 1 | kMaxSequenceNumber); |
2253 | 1 | memtable->Ref(); |
2254 | 1 | WriteBatch batch; |
2255 | 1 | WriteBatchInternal::SetSequence(&batch, 100); |
2256 | 1 | batch.Put(std::string("k1"), std::string("v1")); |
2257 | 1 | batch.Put(std::string("k2"), std::string("v2")); |
2258 | 1 | batch.Put(std::string("k3"), std::string("v3")); |
2259 | 1 | batch.Put(std::string("largekey"), std::string("vlarge")); |
2260 | 1 | ColumnFamilyMemTablesDefault cf_mems_default(memtable); |
2261 | 1 | ASSERT_TRUE( |
2262 | 1 | WriteBatchInternal::InsertInto(&batch, &cf_mems_default, nullptr).ok()); |
2263 | | |
2264 | 1 | Arena arena; |
2265 | 1 | ScopedArenaIterator iter(memtable->NewIterator(ReadOptions(), &arena)); |
2266 | 1 | iter->SeekToFirst(); |
2267 | 5 | while (iter->Valid()) { |
2268 | 4 | fprintf(stderr, "key: '%s' -> '%s'\n", |
2269 | 4 | iter->key().ToString().c_str(), |
2270 | 4 | iter->value().ToString().c_str()); |
2271 | 4 | iter->Next(); |
2272 | 4 | } |
2273 | | |
2274 | 1 | delete memtable->Unref(); |
2275 | 1 | } |
2276 | | |
2277 | | // Test the empty key |
2278 | 1 | TEST_F(HarnessTest, SimpleEmptyKey) { |
2279 | 1 | auto args = GenerateArgList(); |
2280 | 204 | for (const auto& arg : args) { |
2281 | 204 | Init(arg); |
2282 | 204 | Random rnd(test::RandomSeed() + 1); |
2283 | 204 | Add("", "v"); |
2284 | 204 | Test(&rnd); |
2285 | 204 | } |
2286 | 1 | } |
2287 | | |
2288 | 1 | TEST_F(HarnessTest, SimpleSingle) { |
2289 | 1 | auto args = GenerateArgList(); |
2290 | 204 | for (const auto& arg : args) { |
2291 | 204 | Init(arg); |
2292 | 204 | Random rnd(test::RandomSeed() + 2); |
2293 | 204 | Add("abc", "v"); |
2294 | 204 | Test(&rnd); |
2295 | 204 | } |
2296 | 1 | } |
2297 | | |
2298 | 1 | TEST_F(HarnessTest, SimpleMulti) { |
2299 | 1 | auto args = GenerateArgList(); |
2300 | 204 | for (const auto& arg : args) { |
2301 | 204 | Init(arg); |
2302 | 204 | Random rnd(test::RandomSeed() + 3); |
2303 | 204 | Add("abc", "v"); |
2304 | 204 | Add("abcd", "v"); |
2305 | 204 | Add("ac", "v2"); |
2306 | 204 | Test(&rnd); |
2307 | 204 | } |
2308 | 1 | } |
2309 | | |
2310 | 1 | TEST_F(HarnessTest, SimpleSpecialKey) { |
2311 | 1 | auto args = GenerateArgList(); |
2312 | 204 | for (const auto& arg : args) { |
2313 | 204 | Init(arg); |
2314 | 204 | Random rnd(test::RandomSeed() + 4); |
2315 | 204 | Add("\xff\xff", "v3"); |
2316 | 204 | Test(&rnd); |
2317 | 204 | } |
2318 | 1 | } |
2319 | | |
2320 | 1 | TEST_F(HarnessTest, FooterTests) { |
2321 | 1 | { |
2322 | | // upconvert legacy block based |
2323 | 1 | std::string encoded; |
2324 | 1 | Footer footer(kLegacyBlockBasedTableMagicNumber, 0); |
2325 | 1 | BlockHandle meta_index(10, 5), index(20, 15); |
2326 | 1 | footer.set_metaindex_handle(meta_index); |
2327 | 1 | footer.set_index_handle(index); |
2328 | 1 | footer.AppendEncodedTo(&encoded); |
2329 | 1 | Footer decoded_footer; |
2330 | 1 | Slice encoded_slice(encoded); |
2331 | 1 | ASSERT_OK(decoded_footer.DecodeFrom(&encoded_slice)); |
2332 | 1 | ASSERT_EQ(decoded_footer.table_magic_number(), kBlockBasedTableMagicNumber); |
2333 | 1 | ASSERT_EQ(decoded_footer.checksum(), kCRC32c); |
2334 | 1 | ASSERT_EQ(decoded_footer.metaindex_handle().offset(), meta_index.offset()); |
2335 | 1 | ASSERT_EQ(decoded_footer.metaindex_handle().size(), meta_index.size()); |
2336 | 1 | ASSERT_EQ(decoded_footer.index_handle().offset(), index.offset()); |
2337 | 1 | ASSERT_EQ(decoded_footer.index_handle().size(), index.size()); |
2338 | 1 | ASSERT_EQ(decoded_footer.version(), 0U); |
2339 | 1 | } |
2340 | 1 | { |
2341 | | // xxhash block based |
2342 | 1 | std::string encoded; |
2343 | 1 | Footer footer(kBlockBasedTableMagicNumber, 1); |
2344 | 1 | BlockHandle meta_index(10, 5), index(20, 15); |
2345 | 1 | footer.set_metaindex_handle(meta_index); |
2346 | 1 | footer.set_index_handle(index); |
2347 | 1 | footer.set_checksum(kxxHash); |
2348 | 1 | footer.AppendEncodedTo(&encoded); |
2349 | 1 | Footer decoded_footer; |
2350 | 1 | Slice encoded_slice(encoded); |
2351 | 1 | ASSERT_OK(decoded_footer.DecodeFrom(&encoded_slice)); |
2352 | 1 | ASSERT_EQ(decoded_footer.table_magic_number(), kBlockBasedTableMagicNumber); |
2353 | 1 | ASSERT_EQ(decoded_footer.checksum(), kxxHash); |
2354 | 1 | ASSERT_EQ(decoded_footer.metaindex_handle().offset(), meta_index.offset()); |
2355 | 1 | ASSERT_EQ(decoded_footer.metaindex_handle().size(), meta_index.size()); |
2356 | 1 | ASSERT_EQ(decoded_footer.index_handle().offset(), index.offset()); |
2357 | 1 | ASSERT_EQ(decoded_footer.index_handle().size(), index.size()); |
2358 | 1 | ASSERT_EQ(decoded_footer.version(), 1U); |
2359 | 1 | } |
2360 | | // Plain table is not supported in ROCKSDB_LITE |
2361 | 1 | #ifndef ROCKSDB_LITE |
2362 | 1 | { |
2363 | | // upconvert legacy plain table |
2364 | 1 | std::string encoded; |
2365 | 1 | Footer footer(kLegacyPlainTableMagicNumber, 0); |
2366 | 1 | BlockHandle meta_index(10, 5), index(20, 15); |
2367 | 1 | footer.set_metaindex_handle(meta_index); |
2368 | 1 | footer.set_index_handle(index); |
2369 | 1 | footer.AppendEncodedTo(&encoded); |
2370 | 1 | Footer decoded_footer; |
2371 | 1 | Slice encoded_slice(encoded); |
2372 | 1 | ASSERT_OK(decoded_footer.DecodeFrom(&encoded_slice)); |
2373 | 1 | ASSERT_EQ(decoded_footer.table_magic_number(), kPlainTableMagicNumber); |
2374 | 1 | ASSERT_EQ(decoded_footer.checksum(), kCRC32c); |
2375 | 1 | ASSERT_EQ(decoded_footer.metaindex_handle().offset(), meta_index.offset()); |
2376 | 1 | ASSERT_EQ(decoded_footer.metaindex_handle().size(), meta_index.size()); |
2377 | 1 | ASSERT_EQ(decoded_footer.index_handle().offset(), index.offset()); |
2378 | 1 | ASSERT_EQ(decoded_footer.index_handle().size(), index.size()); |
2379 | 1 | ASSERT_EQ(decoded_footer.version(), 0U); |
2380 | 1 | } |
2381 | 1 | { |
2382 | | // xxhash block based |
2383 | 1 | std::string encoded; |
2384 | 1 | Footer footer(kPlainTableMagicNumber, 1); |
2385 | 1 | BlockHandle meta_index(10, 5), index(20, 15); |
2386 | 1 | footer.set_metaindex_handle(meta_index); |
2387 | 1 | footer.set_index_handle(index); |
2388 | 1 | footer.set_checksum(kxxHash); |
2389 | 1 | footer.AppendEncodedTo(&encoded); |
2390 | 1 | Footer decoded_footer; |
2391 | 1 | Slice encoded_slice(encoded); |
2392 | 1 | ASSERT_OK(decoded_footer.DecodeFrom(&encoded_slice)); |
2393 | 1 | ASSERT_EQ(decoded_footer.table_magic_number(), kPlainTableMagicNumber); |
2394 | 1 | ASSERT_EQ(decoded_footer.checksum(), kxxHash); |
2395 | 1 | ASSERT_EQ(decoded_footer.metaindex_handle().offset(), meta_index.offset()); |
2396 | 1 | ASSERT_EQ(decoded_footer.metaindex_handle().size(), meta_index.size()); |
2397 | 1 | ASSERT_EQ(decoded_footer.index_handle().offset(), index.offset()); |
2398 | 1 | ASSERT_EQ(decoded_footer.index_handle().size(), index.size()); |
2399 | 1 | ASSERT_EQ(decoded_footer.version(), 1U); |
2400 | 1 | } |
2401 | 1 | #endif // !ROCKSDB_LITE |
2402 | 1 | { |
2403 | | // version == 2 |
2404 | 1 | std::string encoded; |
2405 | 1 | Footer footer(kBlockBasedTableMagicNumber, 2); |
2406 | 1 | BlockHandle meta_index(10, 5), index(20, 15); |
2407 | 1 | footer.set_metaindex_handle(meta_index); |
2408 | 1 | footer.set_index_handle(index); |
2409 | 1 | footer.AppendEncodedTo(&encoded); |
2410 | 1 | Footer decoded_footer; |
2411 | 1 | Slice encoded_slice(encoded); |
2412 | 1 | ASSERT_OK(decoded_footer.DecodeFrom(&encoded_slice)); |
2413 | 1 | ASSERT_EQ(decoded_footer.table_magic_number(), kBlockBasedTableMagicNumber); |
2414 | 1 | ASSERT_EQ(decoded_footer.checksum(), kCRC32c); |
2415 | 1 | ASSERT_EQ(decoded_footer.metaindex_handle().offset(), meta_index.offset()); |
2416 | 1 | ASSERT_EQ(decoded_footer.metaindex_handle().size(), meta_index.size()); |
2417 | 1 | ASSERT_EQ(decoded_footer.index_handle().offset(), index.offset()); |
2418 | 1 | ASSERT_EQ(decoded_footer.index_handle().size(), index.size()); |
2419 | 1 | ASSERT_EQ(decoded_footer.version(), 2U); |
2420 | 1 | } |
2421 | 1 | } |
2422 | | |
2423 | | class IndexBlockRestartIntervalTest |
2424 | | : public BlockBasedTableTest, |
2425 | | public ::testing::WithParamInterface<int> { |
2426 | | public: |
2427 | 34 | static std::vector<int> GetRestartValues() { return {-1, 0, 1, 8, 16, 32}; } |
2428 | | }; |
2429 | | |
2430 | | INSTANTIATE_TEST_CASE_P( |
2431 | | IndexBlockRestartIntervalTest, IndexBlockRestartIntervalTest, |
2432 | | ::testing::ValuesIn(IndexBlockRestartIntervalTest::GetRestartValues())); |
2433 | | |
2434 | 6 | TEST_P(IndexBlockRestartIntervalTest, IndexBlockRestartInterval) { |
2435 | 6 | const int kKeysInTable = 10000; |
2436 | 6 | const int kKeySize = 100; |
2437 | 6 | const int kValSize = 500; |
2438 | | |
2439 | 6 | int index_block_restart_interval = GetParam(); |
2440 | | |
2441 | 6 | std::vector<boost::optional<KeyValueEncodingFormat>> formats_to_test; |
2442 | 12 | for (const auto& format : kKeyValueEncodingFormatList) { |
2443 | 12 | formats_to_test.push_back(format); |
2444 | 12 | } |
2445 | | // Also test backward compatibility with SST files without |
2446 | | // BlockBasedTablePropertyNames::kDataBlockKeyValueEncodingFormat property. |
2447 | 6 | formats_to_test.push_back(boost::none); |
2448 | | |
2449 | 18 | for (const auto& format : formats_to_test) { |
2450 | 18 | Options options; |
2451 | 18 | BlockBasedTableOptions table_options; |
2452 | 18 | table_options.block_size = 64; // small block size to get big index block |
2453 | 18 | table_options.index_block_restart_interval = index_block_restart_interval; |
2454 | | // SST files without BlockBasedTablePropertyNames::kDataBlockKeyValueEncodingFormat only could |
2455 | | // be written with using KeyValueEncodingFormat::kKeyDeltaEncodingSharedPrefix, because there |
2456 | | // were no other formats before we added this property. |
2457 | 18 | table_options.data_block_key_value_encoding_format = |
2458 | 18 | format.get_value_or(KeyValueEncodingFormat::kKeyDeltaEncodingSharedPrefix); |
2459 | 18 | options.table_factory.reset(new BlockBasedTableFactory(table_options)); |
2460 | | |
2461 | 18 | TableConstructor c(BytewiseComparator()); |
2462 | 18 | if (!format.has_value()) { |
2463 | | // Backward compatibility: test that we can read files without |
2464 | | // BlockBasedTablePropertyNames::kDataBlockKeyValueEncodingFormat property. |
2465 | 6 | c.TEST_skip_writing_key_value_encoding_format = true; |
2466 | 6 | } |
2467 | 18 | static Random rnd(301); |
2468 | 180k | for (int i = 0; i < kKeysInTable; i++) { |
2469 | 180k | InternalKey k(RandomString(&rnd, kKeySize), 0, kTypeValue); |
2470 | 180k | c.Add(k.Encode().ToString(), RandomString(&rnd, kValSize)); |
2471 | 180k | } |
2472 | | |
2473 | 18 | std::vector<std::string> keys; |
2474 | 18 | stl_wrappers::KVMap kvmap; |
2475 | 18 | auto comparator = std::make_shared<InternalKeyComparator>(BytewiseComparator()); |
2476 | 18 | const ImmutableCFOptions ioptions(options); |
2477 | 18 | c.Finish(options, ioptions, table_options, comparator, &keys, &kvmap); |
2478 | 18 | auto reader = c.GetTableReader(); |
2479 | | |
2480 | 18 | std::unique_ptr<InternalIterator> db_iter(reader->NewIterator(ReadOptions())); |
2481 | | |
2482 | | // Test point lookup |
2483 | 180k | for (auto& kv : kvmap) { |
2484 | 180k | db_iter->Seek(kv.first); |
2485 | | |
2486 | 180k | ASSERT_TRUE(db_iter->Valid()); |
2487 | 180k | ASSERT_OK(db_iter->status()); |
2488 | 180k | ASSERT_EQ(db_iter->key(), kv.first); |
2489 | 180k | ASSERT_EQ(db_iter->value(), kv.second); |
2490 | 180k | } |
2491 | | |
2492 | | // Test iterating |
2493 | 18 | auto kv_iter = kvmap.begin(); |
2494 | 180k | for (db_iter->SeekToFirst(); db_iter->Valid(); db_iter->Next()) { |
2495 | 180k | ASSERT_EQ(db_iter->key(), kv_iter->first); |
2496 | 180k | ASSERT_EQ(db_iter->value(), kv_iter->second); |
2497 | 180k | kv_iter++; |
2498 | 180k | } |
2499 | 18 | ASSERT_EQ(kv_iter, kvmap.end()); |
2500 | 18 | } |
2501 | 6 | } |
2502 | | |
2503 | | class PrefixTest : public RocksDBTest {}; |
2504 | | |
2505 | | namespace { |
2506 | | // A simple PrefixExtractor that only works for test PrefixAndWholeKeyTest |
2507 | | class TestPrefixExtractor : public rocksdb::SliceTransform { |
2508 | | public: |
2509 | 1 | ~TestPrefixExtractor() override{}; |
2510 | 6 | const char* Name() const override { return "TestPrefixExtractor"; } |
2511 | | |
2512 | 400 | rocksdb::Slice Transform(const rocksdb::Slice& src) const override { |
2513 | 400 | assert(IsValid(src)); |
2514 | 400 | return rocksdb::Slice(src.data(), 3); |
2515 | 400 | } |
2516 | | |
2517 | 400 | bool InDomain(const rocksdb::Slice& src) const override { |
2518 | 400 | assert(IsValid(src)); |
2519 | 400 | return true; |
2520 | 400 | } |
2521 | | |
2522 | 0 | bool InRange(const rocksdb::Slice& dst) const override { return true; } |
2523 | | |
2524 | 800 | bool IsValid(const rocksdb::Slice& src) const { |
2525 | 800 | if (src.size() != 4) { |
2526 | 0 | return false; |
2527 | 0 | } |
2528 | 800 | if (src[0] != '[') { |
2529 | 0 | return false; |
2530 | 0 | } |
2531 | 800 | if (src[1] < '0' || src[1] > '9') { |
2532 | 0 | return false; |
2533 | 0 | } |
2534 | 800 | if (src[2] != ']') { |
2535 | 0 | return false; |
2536 | 0 | } |
2537 | 800 | if (src[3] < '0' || src[3] > '9') { |
2538 | 0 | return false; |
2539 | 0 | } |
2540 | 800 | return true; |
2541 | 800 | } |
2542 | | }; |
2543 | | } // namespace |
2544 | | |
2545 | 1 | TEST_F(PrefixTest, PrefixAndWholeKeyTest) { |
2546 | 1 | rocksdb::BlockBasedTableOptions bbto; |
2547 | 1 | bbto.block_size = 262144; |
2548 | 1 | bbto.whole_key_filtering = true; |
2549 | | |
2550 | 1 | rocksdb::Options options; |
2551 | 1 | options.compaction_style = rocksdb::kCompactionStyleUniversal; |
2552 | 1 | options.num_levels = 20; |
2553 | 1 | options.create_if_missing = true; |
2554 | 1 | options.optimize_filters_for_hits = false; |
2555 | 1 | options.target_file_size_base = 268435456; |
2556 | 1 | options.prefix_extractor = std::make_shared<TestPrefixExtractor>(); |
2557 | | |
2558 | 3 | for (int it = 0; it < 2; it++) { |
2559 | 2 | switch (it) { |
2560 | 1 | case 0: |
2561 | 1 | bbto.filter_policy.reset(rocksdb::NewBloomFilterPolicy(10)); |
2562 | 1 | break; |
2563 | 1 | default: |
2564 | 1 | SetFixedSizeFilterPolicy(&bbto); |
2565 | 1 | break; |
2566 | 2 | } |
2567 | | |
2568 | 2 | const std::string kDBPath = test::TmpDir() + "/prefix_test"; |
2569 | 2 | options.table_factory.reset(NewBlockBasedTableFactory(bbto)); |
2570 | 2 | ASSERT_OK(DestroyDB(kDBPath, options)); |
2571 | 2 | rocksdb::DB* db; |
2572 | 2 | ASSERT_OK(rocksdb::DB::Open(options, kDBPath, &db)); |
2573 | | |
2574 | | // Create a bunch of keys with 10 filters. |
2575 | 22 | for (int i = 0; i < 10; i++) { |
2576 | 20 | std::string prefix = "[" + std::to_string(i) + "]"; |
2577 | 220 | for (int j = 0; j < 10; j++) { |
2578 | 200 | std::string key = prefix + std::to_string(j); |
2579 | 200 | ASSERT_OK(db->Put(rocksdb::WriteOptions(), key, "1")); |
2580 | 200 | } |
2581 | 20 | } |
2582 | | |
2583 | | // Trigger compaction. |
2584 | 2 | ASSERT_OK(db->CompactRange(CompactRangeOptions(), nullptr, nullptr)); |
2585 | 2 | delete db; |
2586 | | // In the second round, turn whole_key_filtering off and expect |
2587 | | // rocksdb still works. |
2588 | 2 | } |
2589 | 1 | } |
2590 | | |
2591 | | } // namespace rocksdb |
2592 | | |
2593 | 13.2k | int main(int argc, char** argv) { |
2594 | 13.2k | ::testing::InitGoogleTest(&argc, argv); |
2595 | 13.2k | return RUN_ALL_TESTS(); |
2596 | 13.2k | } |