]>
Commit | Line | Data |
---|---|---|
7c673cae | 1 | // Copyright (c) 2011-present, Facebook, Inc. All rights reserved. |
11fdf7f2 TL |
2 | // This source code is licensed under both the GPLv2 (found in the |
3 | // COPYING file in the root directory) and Apache 2.0 License | |
4 | // (found in the LICENSE.Apache file in the root directory). | |
7c673cae FG |
5 | // |
6 | // Copyright (c) 2011 The LevelDB Authors. All rights reserved. | |
7 | // Use of this source code is governed by a BSD-style license that can be | |
8 | // found in the LICENSE file. See the AUTHORS file for names of contributors. | |
9 | ||
7c673cae | 10 | #include <stdio.h> |
7c673cae FG |
11 | #include <algorithm> |
12 | #include <iostream> | |
13 | #include <map> | |
14 | #include <memory> | |
15 | #include <string> | |
16 | #include <vector> | |
17 | ||
f67539c2 | 18 | #include "block_fetcher.h" |
11fdf7f2 | 19 | #include "cache/lru_cache.h" |
7c673cae FG |
20 | #include "db/dbformat.h" |
21 | #include "db/memtable.h" | |
22 | #include "db/write_batch_internal.h" | |
23 | #include "memtable/stl_wrappers.h" | |
f67539c2 | 24 | #include "meta_blocks.h" |
7c673cae FG |
25 | #include "monitoring/statistics.h" |
26 | #include "port/port.h" | |
27 | #include "rocksdb/cache.h" | |
28 | #include "rocksdb/db.h" | |
29 | #include "rocksdb/env.h" | |
f67539c2 TL |
30 | #include "rocksdb/file_checksum.h" |
31 | #include "rocksdb/file_system.h" | |
7c673cae FG |
32 | #include "rocksdb/iterator.h" |
33 | #include "rocksdb/memtablerep.h" | |
34 | #include "rocksdb/perf_context.h" | |
35 | #include "rocksdb/slice_transform.h" | |
36 | #include "rocksdb/statistics.h" | |
37 | #include "rocksdb/write_buffer_manager.h" | |
f67539c2 TL |
38 | #include "table/block_based/block.h" |
39 | #include "table/block_based/block_based_table_builder.h" | |
40 | #include "table/block_based/block_based_table_factory.h" | |
41 | #include "table/block_based/block_based_table_reader.h" | |
42 | #include "table/block_based/block_builder.h" | |
43 | #include "table/block_based/flush_block_policy.h" | |
7c673cae FG |
44 | #include "table/format.h" |
45 | #include "table/get_context.h" | |
46 | #include "table/internal_iterator.h" | |
f67539c2 | 47 | #include "table/plain/plain_table_factory.h" |
7c673cae FG |
48 | #include "table/scoped_arena_iterator.h" |
49 | #include "table/sst_file_writer_collectors.h" | |
f67539c2 TL |
50 | #include "test_util/sync_point.h" |
51 | #include "test_util/testharness.h" | |
52 | #include "test_util/testutil.h" | |
7c673cae | 53 | #include "util/compression.h" |
f67539c2 | 54 | #include "util/file_checksum_helper.h" |
7c673cae FG |
55 | #include "util/random.h" |
56 | #include "util/string_util.h" | |
7c673cae FG |
57 | #include "utilities/merge_operators.h" |
58 | ||
f67539c2 | 59 | namespace ROCKSDB_NAMESPACE { |
7c673cae FG |
60 | |
61 | extern const uint64_t kLegacyBlockBasedTableMagicNumber; | |
62 | extern const uint64_t kLegacyPlainTableMagicNumber; | |
63 | extern const uint64_t kBlockBasedTableMagicNumber; | |
64 | extern const uint64_t kPlainTableMagicNumber; | |
65 | ||
66 | namespace { | |
67 | ||
f67539c2 TL |
68 | const std::string kDummyValue(10000, 'o'); |
69 | ||
7c673cae FG |
70 | // DummyPropertiesCollector used to test BlockBasedTableProperties |
71 | class DummyPropertiesCollector : public TablePropertiesCollector { | |
72 | public: | |
494da23a | 73 | const char* Name() const override { return ""; } |
7c673cae | 74 | |
494da23a | 75 | Status Finish(UserCollectedProperties* /*properties*/) override { |
11fdf7f2 TL |
76 | return Status::OK(); |
77 | } | |
7c673cae | 78 | |
494da23a | 79 | Status Add(const Slice& /*user_key*/, const Slice& /*value*/) override { |
11fdf7f2 TL |
80 | return Status::OK(); |
81 | } | |
7c673cae | 82 | |
494da23a | 83 | UserCollectedProperties GetReadableProperties() const override { |
7c673cae FG |
84 | return UserCollectedProperties{}; |
85 | } | |
86 | }; | |
87 | ||
88 | class DummyPropertiesCollectorFactory1 | |
89 | : public TablePropertiesCollectorFactory { | |
90 | public: | |
494da23a TL |
91 | TablePropertiesCollector* CreateTablePropertiesCollector( |
92 | TablePropertiesCollectorFactory::Context /*context*/) override { | |
7c673cae FG |
93 | return new DummyPropertiesCollector(); |
94 | } | |
494da23a | 95 | const char* Name() const override { return "DummyPropertiesCollector1"; } |
7c673cae FG |
96 | }; |
97 | ||
98 | class DummyPropertiesCollectorFactory2 | |
99 | : public TablePropertiesCollectorFactory { | |
100 | public: | |
494da23a TL |
101 | TablePropertiesCollector* CreateTablePropertiesCollector( |
102 | TablePropertiesCollectorFactory::Context /*context*/) override { | |
7c673cae FG |
103 | return new DummyPropertiesCollector(); |
104 | } | |
494da23a | 105 | const char* Name() const override { return "DummyPropertiesCollector2"; } |
7c673cae FG |
106 | }; |
107 | ||
108 | // Return reverse of "key". | |
109 | // Used to test non-lexicographic comparators. | |
110 | std::string Reverse(const Slice& key) { | |
111 | auto rev = key.ToString(); | |
112 | std::reverse(rev.begin(), rev.end()); | |
113 | return rev; | |
114 | } | |
115 | ||
116 | class ReverseKeyComparator : public Comparator { | |
117 | public: | |
494da23a | 118 | const char* Name() const override { |
7c673cae FG |
119 | return "rocksdb.ReverseBytewiseComparator"; |
120 | } | |
121 | ||
494da23a | 122 | int Compare(const Slice& a, const Slice& b) const override { |
7c673cae FG |
123 | return BytewiseComparator()->Compare(Reverse(a), Reverse(b)); |
124 | } | |
125 | ||
494da23a TL |
126 | void FindShortestSeparator(std::string* start, |
127 | const Slice& limit) const override { | |
7c673cae FG |
128 | std::string s = Reverse(*start); |
129 | std::string l = Reverse(limit); | |
130 | BytewiseComparator()->FindShortestSeparator(&s, l); | |
131 | *start = Reverse(s); | |
132 | } | |
133 | ||
494da23a | 134 | void FindShortSuccessor(std::string* key) const override { |
7c673cae FG |
135 | std::string s = Reverse(*key); |
136 | BytewiseComparator()->FindShortSuccessor(&s); | |
137 | *key = Reverse(s); | |
138 | } | |
139 | }; | |
140 | ||
141 | ReverseKeyComparator reverse_key_comparator; | |
142 | ||
143 | void Increment(const Comparator* cmp, std::string* key) { | |
144 | if (cmp == BytewiseComparator()) { | |
145 | key->push_back('\0'); | |
146 | } else { | |
147 | assert(cmp == &reverse_key_comparator); | |
148 | std::string rev = Reverse(*key); | |
149 | rev.push_back('\0'); | |
150 | *key = Reverse(rev); | |
151 | } | |
152 | } | |
153 | ||
154 | } // namespace | |
155 | ||
156 | // Helper class for tests to unify the interface between | |
157 | // BlockBuilder/TableBuilder and Block/Table. | |
158 | class Constructor { | |
159 | public: | |
160 | explicit Constructor(const Comparator* cmp) | |
161 | : data_(stl_wrappers::LessOfComparator(cmp)) {} | |
162 | virtual ~Constructor() { } | |
163 | ||
164 | void Add(const std::string& key, const Slice& value) { | |
165 | data_[key] = value.ToString(); | |
166 | } | |
167 | ||
168 | // Finish constructing the data structure with all the keys that have | |
169 | // been added so far. Returns the keys in sorted order in "*keys" | |
170 | // and stores the key/value pairs in "*kvmap" | |
171 | void Finish(const Options& options, const ImmutableCFOptions& ioptions, | |
11fdf7f2 | 172 | const MutableCFOptions& moptions, |
7c673cae FG |
173 | const BlockBasedTableOptions& table_options, |
174 | const InternalKeyComparator& internal_comparator, | |
175 | std::vector<std::string>* keys, stl_wrappers::KVMap* kvmap) { | |
176 | last_internal_key_ = &internal_comparator; | |
177 | *kvmap = data_; | |
178 | keys->clear(); | |
179 | for (const auto& kv : data_) { | |
180 | keys->push_back(kv.first); | |
181 | } | |
182 | data_.clear(); | |
11fdf7f2 | 183 | Status s = FinishImpl(options, ioptions, moptions, table_options, |
7c673cae FG |
184 | internal_comparator, *kvmap); |
185 | ASSERT_TRUE(s.ok()) << s.ToString(); | |
186 | } | |
187 | ||
188 | // Construct the data structure from the data in "data" | |
189 | virtual Status FinishImpl(const Options& options, | |
190 | const ImmutableCFOptions& ioptions, | |
11fdf7f2 | 191 | const MutableCFOptions& moptions, |
7c673cae FG |
192 | const BlockBasedTableOptions& table_options, |
193 | const InternalKeyComparator& internal_comparator, | |
194 | const stl_wrappers::KVMap& data) = 0; | |
195 | ||
11fdf7f2 TL |
196 | virtual InternalIterator* NewIterator( |
197 | const SliceTransform* prefix_extractor = nullptr) const = 0; | |
7c673cae FG |
198 | |
199 | virtual const stl_wrappers::KVMap& data() { return data_; } | |
200 | ||
201 | virtual bool IsArenaMode() const { return false; } | |
202 | ||
203 | virtual DB* db() const { return nullptr; } // Overridden in DBConstructor | |
204 | ||
205 | virtual bool AnywayDeleteIterator() const { return false; } | |
206 | ||
207 | protected: | |
208 | const InternalKeyComparator* last_internal_key_; | |
209 | ||
210 | private: | |
211 | stl_wrappers::KVMap data_; | |
212 | }; | |
213 | ||
214 | class BlockConstructor: public Constructor { | |
215 | public: | |
216 | explicit BlockConstructor(const Comparator* cmp) | |
217 | : Constructor(cmp), | |
218 | comparator_(cmp), | |
219 | block_(nullptr) { } | |
494da23a TL |
220 | ~BlockConstructor() override { delete block_; } |
221 | Status FinishImpl(const Options& /*options*/, | |
222 | const ImmutableCFOptions& /*ioptions*/, | |
223 | const MutableCFOptions& /*moptions*/, | |
224 | const BlockBasedTableOptions& table_options, | |
225 | const InternalKeyComparator& /*internal_comparator*/, | |
226 | const stl_wrappers::KVMap& kv_map) override { | |
7c673cae FG |
227 | delete block_; |
228 | block_ = nullptr; | |
229 | BlockBuilder builder(table_options.block_restart_interval); | |
230 | ||
231 | for (const auto kv : kv_map) { | |
232 | builder.Add(kv.first, kv.second); | |
233 | } | |
234 | // Open the block | |
235 | data_ = builder.Finish().ToString(); | |
236 | BlockContents contents; | |
237 | contents.data = data_; | |
7c673cae FG |
238 | block_ = new Block(std::move(contents), kDisableGlobalSequenceNumber); |
239 | return Status::OK(); | |
240 | } | |
494da23a | 241 | InternalIterator* NewIterator( |
11fdf7f2 | 242 | const SliceTransform* /*prefix_extractor*/) const override { |
f67539c2 | 243 | return block_->NewDataIterator(comparator_, comparator_); |
7c673cae FG |
244 | } |
245 | ||
246 | private: | |
247 | const Comparator* comparator_; | |
248 | std::string data_; | |
249 | Block* block_; | |
250 | ||
251 | BlockConstructor(); | |
252 | }; | |
253 | ||
254 | // A helper class that converts internal format keys into user keys | |
255 | class KeyConvertingIterator : public InternalIterator { | |
256 | public: | |
257 | explicit KeyConvertingIterator(InternalIterator* iter, | |
258 | bool arena_mode = false) | |
259 | : iter_(iter), arena_mode_(arena_mode) {} | |
494da23a | 260 | ~KeyConvertingIterator() override { |
7c673cae FG |
261 | if (arena_mode_) { |
262 | iter_->~InternalIterator(); | |
263 | } else { | |
264 | delete iter_; | |
265 | } | |
266 | } | |
494da23a TL |
267 | bool Valid() const override { return iter_->Valid() && status_.ok(); } |
268 | void Seek(const Slice& target) override { | |
7c673cae FG |
269 | ParsedInternalKey ikey(target, kMaxSequenceNumber, kTypeValue); |
270 | std::string encoded; | |
271 | AppendInternalKey(&encoded, ikey); | |
272 | iter_->Seek(encoded); | |
273 | } | |
494da23a | 274 | void SeekForPrev(const Slice& target) override { |
7c673cae FG |
275 | ParsedInternalKey ikey(target, kMaxSequenceNumber, kTypeValue); |
276 | std::string encoded; | |
277 | AppendInternalKey(&encoded, ikey); | |
278 | iter_->SeekForPrev(encoded); | |
279 | } | |
494da23a TL |
280 | void SeekToFirst() override { iter_->SeekToFirst(); } |
281 | void SeekToLast() override { iter_->SeekToLast(); } | |
282 | void Next() override { iter_->Next(); } | |
283 | void Prev() override { iter_->Prev(); } | |
f67539c2 | 284 | bool IsOutOfBound() override { return iter_->IsOutOfBound(); } |
7c673cae | 285 | |
494da23a | 286 | Slice key() const override { |
7c673cae FG |
287 | assert(Valid()); |
288 | ParsedInternalKey parsed_key; | |
289 | if (!ParseInternalKey(iter_->key(), &parsed_key)) { | |
290 | status_ = Status::Corruption("malformed internal key"); | |
291 | return Slice("corrupted key"); | |
292 | } | |
293 | return parsed_key.user_key; | |
294 | } | |
295 | ||
494da23a TL |
296 | Slice value() const override { return iter_->value(); } |
297 | Status status() const override { | |
7c673cae FG |
298 | return status_.ok() ? iter_->status() : status_; |
299 | } | |
300 | ||
301 | private: | |
302 | mutable Status status_; | |
303 | InternalIterator* iter_; | |
304 | bool arena_mode_; | |
305 | ||
306 | // No copying allowed | |
307 | KeyConvertingIterator(const KeyConvertingIterator&); | |
308 | void operator=(const KeyConvertingIterator&); | |
309 | }; | |
310 | ||
311 | class TableConstructor: public Constructor { | |
312 | public: | |
313 | explicit TableConstructor(const Comparator* cmp, | |
11fdf7f2 | 314 | bool convert_to_internal_key = false, |
f67539c2 | 315 | int level = -1, SequenceNumber largest_seqno = 0) |
7c673cae | 316 | : Constructor(cmp), |
f67539c2 | 317 | largest_seqno_(largest_seqno), |
11fdf7f2 | 318 | convert_to_internal_key_(convert_to_internal_key), |
f67539c2 TL |
319 | level_(level) { |
320 | env_ = ROCKSDB_NAMESPACE::Env::Default(); | |
321 | } | |
494da23a | 322 | ~TableConstructor() override { Reset(); } |
7c673cae | 323 | |
494da23a TL |
324 | Status FinishImpl(const Options& options, const ImmutableCFOptions& ioptions, |
325 | const MutableCFOptions& moptions, | |
326 | const BlockBasedTableOptions& /*table_options*/, | |
327 | const InternalKeyComparator& internal_comparator, | |
328 | const stl_wrappers::KVMap& kv_map) override { | |
7c673cae FG |
329 | Reset(); |
330 | soptions.use_mmap_reads = ioptions.allow_mmap_reads; | |
11fdf7f2 TL |
331 | file_writer_.reset(test::GetWritableFileWriter(new test::StringSink(), |
332 | "" /* don't care */)); | |
494da23a | 333 | std::unique_ptr<TableBuilder> builder; |
7c673cae FG |
334 | std::vector<std::unique_ptr<IntTblPropCollectorFactory>> |
335 | int_tbl_prop_collector_factories; | |
f67539c2 TL |
336 | |
337 | if (largest_seqno_ != 0) { | |
338 | // Pretend that it's an external file written by SstFileWriter. | |
339 | int_tbl_prop_collector_factories.emplace_back( | |
340 | new SstFileWriterPropertiesCollectorFactory(2 /* version */, | |
341 | 0 /* global_seqno*/)); | |
342 | } | |
343 | ||
7c673cae | 344 | std::string column_family_name; |
7c673cae | 345 | builder.reset(ioptions.table_factory->NewTableBuilder( |
494da23a TL |
346 | TableBuilderOptions(ioptions, moptions, internal_comparator, |
347 | &int_tbl_prop_collector_factories, | |
348 | options.compression, options.sample_for_compression, | |
349 | options.compression_opts, false /* skip_filters */, | |
350 | column_family_name, level_), | |
7c673cae FG |
351 | TablePropertiesCollectorFactory::Context::kUnknownColumnFamily, |
352 | file_writer_.get())); | |
353 | ||
354 | for (const auto kv : kv_map) { | |
355 | if (convert_to_internal_key_) { | |
356 | ParsedInternalKey ikey(kv.first, kMaxSequenceNumber, kTypeValue); | |
357 | std::string encoded; | |
358 | AppendInternalKey(&encoded, ikey); | |
359 | builder->Add(encoded, kv.second); | |
360 | } else { | |
361 | builder->Add(kv.first, kv.second); | |
362 | } | |
363 | EXPECT_TRUE(builder->status().ok()); | |
364 | } | |
365 | Status s = builder->Finish(); | |
366 | file_writer_->Flush(); | |
367 | EXPECT_TRUE(s.ok()) << s.ToString(); | |
368 | ||
11fdf7f2 | 369 | EXPECT_EQ(TEST_GetSink()->contents().size(), builder->FileSize()); |
7c673cae FG |
370 | |
371 | // Open the table | |
372 | uniq_id_ = cur_uniq_id_++; | |
373 | file_reader_.reset(test::GetRandomAccessFileReader(new test::StringSource( | |
11fdf7f2 TL |
374 | TEST_GetSink()->contents(), uniq_id_, ioptions.allow_mmap_reads))); |
375 | const bool kSkipFilters = true; | |
376 | const bool kImmortal = true; | |
7c673cae | 377 | return ioptions.table_factory->NewTableReader( |
11fdf7f2 TL |
378 | TableReaderOptions(ioptions, moptions.prefix_extractor.get(), soptions, |
379 | internal_comparator, !kSkipFilters, !kImmortal, | |
f67539c2 | 380 | level_, largest_seqno_, &block_cache_tracer_), |
11fdf7f2 TL |
381 | std::move(file_reader_), TEST_GetSink()->contents().size(), |
382 | &table_reader_); | |
7c673cae FG |
383 | } |
384 | ||
494da23a | 385 | InternalIterator* NewIterator( |
11fdf7f2 | 386 | const SliceTransform* prefix_extractor) const override { |
7c673cae | 387 | ReadOptions ro; |
f67539c2 TL |
388 | InternalIterator* iter = table_reader_->NewIterator( |
389 | ro, prefix_extractor, /*arena=*/nullptr, /*skip_filters=*/false, | |
390 | TableReaderCaller::kUncategorized); | |
7c673cae FG |
391 | if (convert_to_internal_key_) { |
392 | return new KeyConvertingIterator(iter); | |
393 | } else { | |
394 | return iter; | |
395 | } | |
396 | } | |
397 | ||
398 | uint64_t ApproximateOffsetOf(const Slice& key) const { | |
399 | if (convert_to_internal_key_) { | |
400 | InternalKey ikey(key, kMaxSequenceNumber, kTypeValue); | |
401 | const Slice skey = ikey.Encode(); | |
f67539c2 TL |
402 | return table_reader_->ApproximateOffsetOf( |
403 | skey, TableReaderCaller::kUncategorized); | |
7c673cae | 404 | } |
f67539c2 TL |
405 | return table_reader_->ApproximateOffsetOf( |
406 | key, TableReaderCaller::kUncategorized); | |
7c673cae FG |
407 | } |
408 | ||
11fdf7f2 TL |
409 | virtual Status Reopen(const ImmutableCFOptions& ioptions, |
410 | const MutableCFOptions& moptions) { | |
7c673cae | 411 | file_reader_.reset(test::GetRandomAccessFileReader(new test::StringSource( |
11fdf7f2 | 412 | TEST_GetSink()->contents(), uniq_id_, ioptions.allow_mmap_reads))); |
7c673cae | 413 | return ioptions.table_factory->NewTableReader( |
11fdf7f2 TL |
414 | TableReaderOptions(ioptions, moptions.prefix_extractor.get(), soptions, |
415 | *last_internal_key_), | |
416 | std::move(file_reader_), TEST_GetSink()->contents().size(), | |
417 | &table_reader_); | |
7c673cae FG |
418 | } |
419 | ||
11fdf7f2 | 420 | virtual TableReader* GetTableReader() { return table_reader_.get(); } |
7c673cae | 421 | |
494da23a | 422 | bool AnywayDeleteIterator() const override { |
7c673cae FG |
423 | return convert_to_internal_key_; |
424 | } | |
425 | ||
426 | void ResetTableReader() { table_reader_.reset(); } | |
427 | ||
428 | bool ConvertToInternalKey() { return convert_to_internal_key_; } | |
429 | ||
11fdf7f2 | 430 | test::StringSink* TEST_GetSink() { |
f67539c2 TL |
431 | return ROCKSDB_NAMESPACE::test::GetStringSinkFromLegacyWriter( |
432 | file_writer_.get()); | |
11fdf7f2 TL |
433 | } |
434 | ||
f67539c2 TL |
435 | BlockCacheTracer block_cache_tracer_; |
436 | ||
7c673cae FG |
437 | private: |
438 | void Reset() { | |
439 | uniq_id_ = 0; | |
440 | table_reader_.reset(); | |
441 | file_writer_.reset(); | |
442 | file_reader_.reset(); | |
443 | } | |
444 | ||
7c673cae | 445 | uint64_t uniq_id_; |
494da23a TL |
446 | std::unique_ptr<WritableFileWriter> file_writer_; |
447 | std::unique_ptr<RandomAccessFileReader> file_reader_; | |
448 | std::unique_ptr<TableReader> table_reader_; | |
f67539c2 | 449 | SequenceNumber largest_seqno_; |
7c673cae | 450 | bool convert_to_internal_key_; |
11fdf7f2 | 451 | int level_; |
7c673cae FG |
452 | |
453 | TableConstructor(); | |
454 | ||
455 | static uint64_t cur_uniq_id_; | |
456 | EnvOptions soptions; | |
f67539c2 | 457 | Env* env_; |
7c673cae FG |
458 | }; |
459 | uint64_t TableConstructor::cur_uniq_id_ = 1; | |
460 | ||
461 | class MemTableConstructor: public Constructor { | |
462 | public: | |
463 | explicit MemTableConstructor(const Comparator* cmp, WriteBufferManager* wb) | |
464 | : Constructor(cmp), | |
465 | internal_comparator_(cmp), | |
466 | write_buffer_manager_(wb), | |
467 | table_factory_(new SkipListFactory) { | |
468 | options_.memtable_factory = table_factory_; | |
469 | ImmutableCFOptions ioptions(options_); | |
470 | memtable_ = | |
471 | new MemTable(internal_comparator_, ioptions, MutableCFOptions(options_), | |
11fdf7f2 | 472 | wb, kMaxSequenceNumber, 0 /* column_family_id */); |
7c673cae FG |
473 | memtable_->Ref(); |
474 | } | |
494da23a TL |
475 | ~MemTableConstructor() override { delete memtable_->Unref(); } |
476 | Status FinishImpl(const Options&, const ImmutableCFOptions& ioptions, | |
477 | const MutableCFOptions& /*moptions*/, | |
478 | const BlockBasedTableOptions& /*table_options*/, | |
479 | const InternalKeyComparator& /*internal_comparator*/, | |
480 | const stl_wrappers::KVMap& kv_map) override { | |
7c673cae FG |
481 | delete memtable_->Unref(); |
482 | ImmutableCFOptions mem_ioptions(ioptions); | |
483 | memtable_ = new MemTable(internal_comparator_, mem_ioptions, | |
484 | MutableCFOptions(options_), write_buffer_manager_, | |
11fdf7f2 | 485 | kMaxSequenceNumber, 0 /* column_family_id */); |
7c673cae FG |
486 | memtable_->Ref(); |
487 | int seq = 1; | |
488 | for (const auto kv : kv_map) { | |
489 | memtable_->Add(seq, kTypeValue, kv.first, kv.second); | |
490 | seq++; | |
491 | } | |
492 | return Status::OK(); | |
493 | } | |
494da23a | 494 | InternalIterator* NewIterator( |
11fdf7f2 | 495 | const SliceTransform* /*prefix_extractor*/) const override { |
7c673cae FG |
496 | return new KeyConvertingIterator( |
497 | memtable_->NewIterator(ReadOptions(), &arena_), true); | |
498 | } | |
499 | ||
494da23a | 500 | bool AnywayDeleteIterator() const override { return true; } |
7c673cae | 501 | |
494da23a | 502 | bool IsArenaMode() const override { return true; } |
7c673cae FG |
503 | |
504 | private: | |
505 | mutable Arena arena_; | |
506 | InternalKeyComparator internal_comparator_; | |
507 | Options options_; | |
508 | WriteBufferManager* write_buffer_manager_; | |
509 | MemTable* memtable_; | |
510 | std::shared_ptr<SkipListFactory> table_factory_; | |
511 | }; | |
512 | ||
513 | class InternalIteratorFromIterator : public InternalIterator { | |
514 | public: | |
515 | explicit InternalIteratorFromIterator(Iterator* it) : it_(it) {} | |
494da23a TL |
516 | bool Valid() const override { return it_->Valid(); } |
517 | void Seek(const Slice& target) override { it_->Seek(target); } | |
518 | void SeekForPrev(const Slice& target) override { it_->SeekForPrev(target); } | |
519 | void SeekToFirst() override { it_->SeekToFirst(); } | |
520 | void SeekToLast() override { it_->SeekToLast(); } | |
521 | void Next() override { it_->Next(); } | |
522 | void Prev() override { it_->Prev(); } | |
7c673cae FG |
523 | Slice key() const override { return it_->key(); } |
524 | Slice value() const override { return it_->value(); } | |
494da23a | 525 | Status status() const override { return it_->status(); } |
7c673cae FG |
526 | |
527 | private: | |
494da23a | 528 | std::unique_ptr<Iterator> it_; |
7c673cae FG |
529 | }; |
530 | ||
531 | class DBConstructor: public Constructor { | |
532 | public: | |
533 | explicit DBConstructor(const Comparator* cmp) | |
534 | : Constructor(cmp), | |
535 | comparator_(cmp) { | |
536 | db_ = nullptr; | |
537 | NewDB(); | |
538 | } | |
494da23a TL |
539 | ~DBConstructor() override { delete db_; } |
540 | Status FinishImpl(const Options& /*options*/, | |
541 | const ImmutableCFOptions& /*ioptions*/, | |
542 | const MutableCFOptions& /*moptions*/, | |
543 | const BlockBasedTableOptions& /*table_options*/, | |
544 | const InternalKeyComparator& /*internal_comparator*/, | |
545 | const stl_wrappers::KVMap& kv_map) override { | |
7c673cae FG |
546 | delete db_; |
547 | db_ = nullptr; | |
548 | NewDB(); | |
549 | for (const auto kv : kv_map) { | |
550 | WriteBatch batch; | |
551 | batch.Put(kv.first, kv.second); | |
552 | EXPECT_TRUE(db_->Write(WriteOptions(), &batch).ok()); | |
553 | } | |
554 | return Status::OK(); | |
555 | } | |
556 | ||
494da23a | 557 | InternalIterator* NewIterator( |
11fdf7f2 | 558 | const SliceTransform* /*prefix_extractor*/) const override { |
7c673cae FG |
559 | return new InternalIteratorFromIterator(db_->NewIterator(ReadOptions())); |
560 | } | |
561 | ||
494da23a | 562 | DB* db() const override { return db_; } |
7c673cae FG |
563 | |
564 | private: | |
565 | void NewDB() { | |
11fdf7f2 | 566 | std::string name = test::PerThreadDBPath("table_testdb"); |
7c673cae FG |
567 | |
568 | Options options; | |
569 | options.comparator = comparator_; | |
570 | Status status = DestroyDB(name, options); | |
571 | ASSERT_TRUE(status.ok()) << status.ToString(); | |
572 | ||
573 | options.create_if_missing = true; | |
574 | options.error_if_exists = true; | |
575 | options.write_buffer_size = 10000; // Something small to force merging | |
576 | status = DB::Open(options, name, &db_); | |
577 | ASSERT_TRUE(status.ok()) << status.ToString(); | |
578 | } | |
579 | ||
580 | const Comparator* comparator_; | |
581 | DB* db_; | |
582 | }; | |
583 | ||
584 | enum TestType { | |
585 | BLOCK_BASED_TABLE_TEST, | |
586 | #ifndef ROCKSDB_LITE | |
587 | PLAIN_TABLE_SEMI_FIXED_PREFIX, | |
588 | PLAIN_TABLE_FULL_STR_PREFIX, | |
589 | PLAIN_TABLE_TOTAL_ORDER, | |
590 | #endif // !ROCKSDB_LITE | |
591 | BLOCK_TEST, | |
592 | MEMTABLE_TEST, | |
593 | DB_TEST | |
594 | }; | |
595 | ||
596 | struct TestArgs { | |
597 | TestType type; | |
598 | bool reverse_compare; | |
599 | int restart_interval; | |
600 | CompressionType compression; | |
601 | uint32_t format_version; | |
602 | bool use_mmap; | |
603 | }; | |
604 | ||
605 | static std::vector<TestArgs> GenerateArgList() { | |
606 | std::vector<TestArgs> test_args; | |
607 | std::vector<TestType> test_types = { | |
608 | BLOCK_BASED_TABLE_TEST, | |
609 | #ifndef ROCKSDB_LITE | |
610 | PLAIN_TABLE_SEMI_FIXED_PREFIX, | |
611 | PLAIN_TABLE_FULL_STR_PREFIX, | |
612 | PLAIN_TABLE_TOTAL_ORDER, | |
613 | #endif // !ROCKSDB_LITE | |
614 | BLOCK_TEST, | |
615 | MEMTABLE_TEST, DB_TEST}; | |
616 | std::vector<bool> reverse_compare_types = {false, true}; | |
617 | std::vector<int> restart_intervals = {16, 1, 1024}; | |
618 | ||
619 | // Only add compression if it is supported | |
620 | std::vector<std::pair<CompressionType, bool>> compression_types; | |
621 | compression_types.emplace_back(kNoCompression, false); | |
622 | if (Snappy_Supported()) { | |
623 | compression_types.emplace_back(kSnappyCompression, false); | |
624 | } | |
625 | if (Zlib_Supported()) { | |
626 | compression_types.emplace_back(kZlibCompression, false); | |
627 | compression_types.emplace_back(kZlibCompression, true); | |
628 | } | |
629 | if (BZip2_Supported()) { | |
630 | compression_types.emplace_back(kBZip2Compression, false); | |
631 | compression_types.emplace_back(kBZip2Compression, true); | |
632 | } | |
633 | if (LZ4_Supported()) { | |
634 | compression_types.emplace_back(kLZ4Compression, false); | |
635 | compression_types.emplace_back(kLZ4Compression, true); | |
636 | compression_types.emplace_back(kLZ4HCCompression, false); | |
637 | compression_types.emplace_back(kLZ4HCCompression, true); | |
638 | } | |
639 | if (XPRESS_Supported()) { | |
640 | compression_types.emplace_back(kXpressCompression, false); | |
641 | compression_types.emplace_back(kXpressCompression, true); | |
642 | } | |
643 | if (ZSTD_Supported()) { | |
644 | compression_types.emplace_back(kZSTD, false); | |
645 | compression_types.emplace_back(kZSTD, true); | |
646 | } | |
647 | ||
648 | for (auto test_type : test_types) { | |
649 | for (auto reverse_compare : reverse_compare_types) { | |
650 | #ifndef ROCKSDB_LITE | |
651 | if (test_type == PLAIN_TABLE_SEMI_FIXED_PREFIX || | |
652 | test_type == PLAIN_TABLE_FULL_STR_PREFIX || | |
653 | test_type == PLAIN_TABLE_TOTAL_ORDER) { | |
654 | // Plain table doesn't use restart index or compression. | |
655 | TestArgs one_arg; | |
656 | one_arg.type = test_type; | |
657 | one_arg.reverse_compare = reverse_compare; | |
658 | one_arg.restart_interval = restart_intervals[0]; | |
659 | one_arg.compression = compression_types[0].first; | |
660 | one_arg.use_mmap = true; | |
661 | test_args.push_back(one_arg); | |
662 | one_arg.use_mmap = false; | |
663 | test_args.push_back(one_arg); | |
664 | continue; | |
665 | } | |
666 | #endif // !ROCKSDB_LITE | |
667 | ||
668 | for (auto restart_interval : restart_intervals) { | |
669 | for (auto compression_type : compression_types) { | |
670 | TestArgs one_arg; | |
671 | one_arg.type = test_type; | |
672 | one_arg.reverse_compare = reverse_compare; | |
673 | one_arg.restart_interval = restart_interval; | |
674 | one_arg.compression = compression_type.first; | |
675 | one_arg.format_version = compression_type.second ? 2 : 1; | |
676 | one_arg.use_mmap = false; | |
677 | test_args.push_back(one_arg); | |
678 | } | |
679 | } | |
680 | } | |
681 | } | |
682 | return test_args; | |
683 | } | |
684 | ||
685 | // In order to make all tests run for plain table format, including | |
686 | // those operating on empty keys, create a new prefix transformer which | |
687 | // return fixed prefix if the slice is not shorter than the prefix length, | |
688 | // and the full slice if it is shorter. | |
689 | class FixedOrLessPrefixTransform : public SliceTransform { | |
690 | private: | |
691 | const size_t prefix_len_; | |
692 | ||
693 | public: | |
694 | explicit FixedOrLessPrefixTransform(size_t prefix_len) : | |
695 | prefix_len_(prefix_len) { | |
696 | } | |
697 | ||
494da23a | 698 | const char* Name() const override { return "rocksdb.FixedPrefix"; } |
7c673cae | 699 | |
494da23a | 700 | Slice Transform(const Slice& src) const override { |
7c673cae FG |
701 | assert(InDomain(src)); |
702 | if (src.size() < prefix_len_) { | |
703 | return src; | |
704 | } | |
705 | return Slice(src.data(), prefix_len_); | |
706 | } | |
707 | ||
494da23a | 708 | bool InDomain(const Slice& /*src*/) const override { return true; } |
7c673cae | 709 | |
494da23a | 710 | bool InRange(const Slice& dst) const override { |
7c673cae FG |
711 | return (dst.size() <= prefix_len_); |
712 | } | |
494da23a | 713 | bool FullLengthEnabled(size_t* /*len*/) const override { return false; } |
7c673cae FG |
714 | }; |
715 | ||
716 | class HarnessTest : public testing::Test { | |
717 | public: | |
718 | HarnessTest() | |
719 | : ioptions_(options_), | |
11fdf7f2 | 720 | moptions_(options_), |
7c673cae FG |
721 | constructor_(nullptr), |
722 | write_buffer_(options_.db_write_buffer_size) {} | |
723 | ||
724 | void Init(const TestArgs& args) { | |
725 | delete constructor_; | |
726 | constructor_ = nullptr; | |
727 | options_ = Options(); | |
728 | options_.compression = args.compression; | |
729 | // Use shorter block size for tests to exercise block boundary | |
730 | // conditions more. | |
731 | if (args.reverse_compare) { | |
732 | options_.comparator = &reverse_key_comparator; | |
733 | } | |
734 | ||
735 | internal_comparator_.reset( | |
736 | new test::PlainInternalKeyComparator(options_.comparator)); | |
737 | ||
738 | support_prev_ = true; | |
739 | only_support_prefix_seek_ = false; | |
740 | options_.allow_mmap_reads = args.use_mmap; | |
741 | switch (args.type) { | |
742 | case BLOCK_BASED_TABLE_TEST: | |
743 | table_options_.flush_block_policy_factory.reset( | |
744 | new FlushBlockBySizePolicyFactory()); | |
745 | table_options_.block_size = 256; | |
746 | table_options_.block_restart_interval = args.restart_interval; | |
747 | table_options_.index_block_restart_interval = args.restart_interval; | |
748 | table_options_.format_version = args.format_version; | |
749 | options_.table_factory.reset( | |
750 | new BlockBasedTableFactory(table_options_)); | |
751 | constructor_ = new TableConstructor( | |
752 | options_.comparator, true /* convert_to_internal_key_ */); | |
753 | internal_comparator_.reset( | |
754 | new InternalKeyComparator(options_.comparator)); | |
755 | break; | |
756 | // Plain table is not supported in ROCKSDB_LITE | |
757 | #ifndef ROCKSDB_LITE | |
758 | case PLAIN_TABLE_SEMI_FIXED_PREFIX: | |
759 | support_prev_ = false; | |
760 | only_support_prefix_seek_ = true; | |
761 | options_.prefix_extractor.reset(new FixedOrLessPrefixTransform(2)); | |
762 | options_.table_factory.reset(NewPlainTableFactory()); | |
763 | constructor_ = new TableConstructor( | |
764 | options_.comparator, true /* convert_to_internal_key_ */); | |
765 | internal_comparator_.reset( | |
766 | new InternalKeyComparator(options_.comparator)); | |
767 | break; | |
768 | case PLAIN_TABLE_FULL_STR_PREFIX: | |
769 | support_prev_ = false; | |
770 | only_support_prefix_seek_ = true; | |
771 | options_.prefix_extractor.reset(NewNoopTransform()); | |
772 | options_.table_factory.reset(NewPlainTableFactory()); | |
773 | constructor_ = new TableConstructor( | |
774 | options_.comparator, true /* convert_to_internal_key_ */); | |
775 | internal_comparator_.reset( | |
776 | new InternalKeyComparator(options_.comparator)); | |
777 | break; | |
778 | case PLAIN_TABLE_TOTAL_ORDER: | |
779 | support_prev_ = false; | |
780 | only_support_prefix_seek_ = false; | |
781 | options_.prefix_extractor = nullptr; | |
782 | ||
783 | { | |
784 | PlainTableOptions plain_table_options; | |
785 | plain_table_options.user_key_len = kPlainTableVariableLength; | |
786 | plain_table_options.bloom_bits_per_key = 0; | |
787 | plain_table_options.hash_table_ratio = 0; | |
788 | ||
789 | options_.table_factory.reset( | |
790 | NewPlainTableFactory(plain_table_options)); | |
791 | } | |
792 | constructor_ = new TableConstructor( | |
793 | options_.comparator, true /* convert_to_internal_key_ */); | |
794 | internal_comparator_.reset( | |
795 | new InternalKeyComparator(options_.comparator)); | |
796 | break; | |
797 | #endif // !ROCKSDB_LITE | |
798 | case BLOCK_TEST: | |
799 | table_options_.block_size = 256; | |
800 | options_.table_factory.reset( | |
801 | new BlockBasedTableFactory(table_options_)); | |
802 | constructor_ = new BlockConstructor(options_.comparator); | |
803 | break; | |
804 | case MEMTABLE_TEST: | |
805 | table_options_.block_size = 256; | |
806 | options_.table_factory.reset( | |
807 | new BlockBasedTableFactory(table_options_)); | |
808 | constructor_ = new MemTableConstructor(options_.comparator, | |
809 | &write_buffer_); | |
810 | break; | |
811 | case DB_TEST: | |
812 | table_options_.block_size = 256; | |
813 | options_.table_factory.reset( | |
814 | new BlockBasedTableFactory(table_options_)); | |
815 | constructor_ = new DBConstructor(options_.comparator); | |
816 | break; | |
817 | } | |
818 | ioptions_ = ImmutableCFOptions(options_); | |
11fdf7f2 | 819 | moptions_ = MutableCFOptions(options_); |
7c673cae FG |
820 | } |
821 | ||
494da23a | 822 | ~HarnessTest() override { delete constructor_; } |
7c673cae FG |
823 | |
824 | void Add(const std::string& key, const std::string& value) { | |
825 | constructor_->Add(key, value); | |
826 | } | |
827 | ||
828 | void Test(Random* rnd) { | |
829 | std::vector<std::string> keys; | |
830 | stl_wrappers::KVMap data; | |
11fdf7f2 | 831 | constructor_->Finish(options_, ioptions_, moptions_, table_options_, |
7c673cae FG |
832 | *internal_comparator_, &keys, &data); |
833 | ||
834 | TestForwardScan(keys, data); | |
835 | if (support_prev_) { | |
836 | TestBackwardScan(keys, data); | |
837 | } | |
838 | TestRandomAccess(rnd, keys, data); | |
839 | } | |
840 | ||
11fdf7f2 | 841 | void TestForwardScan(const std::vector<std::string>& /*keys*/, |
7c673cae FG |
842 | const stl_wrappers::KVMap& data) { |
843 | InternalIterator* iter = constructor_->NewIterator(); | |
844 | ASSERT_TRUE(!iter->Valid()); | |
845 | iter->SeekToFirst(); | |
846 | for (stl_wrappers::KVMap::const_iterator model_iter = data.begin(); | |
847 | model_iter != data.end(); ++model_iter) { | |
848 | ASSERT_EQ(ToString(data, model_iter), ToString(iter)); | |
849 | iter->Next(); | |
850 | } | |
851 | ASSERT_TRUE(!iter->Valid()); | |
852 | if (constructor_->IsArenaMode() && !constructor_->AnywayDeleteIterator()) { | |
853 | iter->~InternalIterator(); | |
854 | } else { | |
855 | delete iter; | |
856 | } | |
857 | } | |
858 | ||
11fdf7f2 | 859 | void TestBackwardScan(const std::vector<std::string>& /*keys*/, |
7c673cae FG |
860 | const stl_wrappers::KVMap& data) { |
861 | InternalIterator* iter = constructor_->NewIterator(); | |
862 | ASSERT_TRUE(!iter->Valid()); | |
863 | iter->SeekToLast(); | |
864 | for (stl_wrappers::KVMap::const_reverse_iterator model_iter = data.rbegin(); | |
865 | model_iter != data.rend(); ++model_iter) { | |
866 | ASSERT_EQ(ToString(data, model_iter), ToString(iter)); | |
867 | iter->Prev(); | |
868 | } | |
869 | ASSERT_TRUE(!iter->Valid()); | |
870 | if (constructor_->IsArenaMode() && !constructor_->AnywayDeleteIterator()) { | |
871 | iter->~InternalIterator(); | |
872 | } else { | |
873 | delete iter; | |
874 | } | |
875 | } | |
876 | ||
877 | void TestRandomAccess(Random* rnd, const std::vector<std::string>& keys, | |
878 | const stl_wrappers::KVMap& data) { | |
879 | static const bool kVerbose = false; | |
880 | InternalIterator* iter = constructor_->NewIterator(); | |
881 | ASSERT_TRUE(!iter->Valid()); | |
882 | stl_wrappers::KVMap::const_iterator model_iter = data.begin(); | |
883 | if (kVerbose) fprintf(stderr, "---\n"); | |
884 | for (int i = 0; i < 200; i++) { | |
885 | const int toss = rnd->Uniform(support_prev_ ? 5 : 3); | |
886 | switch (toss) { | |
887 | case 0: { | |
888 | if (iter->Valid()) { | |
889 | if (kVerbose) fprintf(stderr, "Next\n"); | |
890 | iter->Next(); | |
891 | ++model_iter; | |
892 | ASSERT_EQ(ToString(data, model_iter), ToString(iter)); | |
893 | } | |
894 | break; | |
895 | } | |
896 | ||
897 | case 1: { | |
898 | if (kVerbose) fprintf(stderr, "SeekToFirst\n"); | |
899 | iter->SeekToFirst(); | |
900 | model_iter = data.begin(); | |
901 | ASSERT_EQ(ToString(data, model_iter), ToString(iter)); | |
902 | break; | |
903 | } | |
904 | ||
905 | case 2: { | |
906 | std::string key = PickRandomKey(rnd, keys); | |
907 | model_iter = data.lower_bound(key); | |
908 | if (kVerbose) fprintf(stderr, "Seek '%s'\n", | |
909 | EscapeString(key).c_str()); | |
910 | iter->Seek(Slice(key)); | |
911 | ASSERT_EQ(ToString(data, model_iter), ToString(iter)); | |
912 | break; | |
913 | } | |
914 | ||
915 | case 3: { | |
916 | if (iter->Valid()) { | |
917 | if (kVerbose) fprintf(stderr, "Prev\n"); | |
918 | iter->Prev(); | |
919 | if (model_iter == data.begin()) { | |
920 | model_iter = data.end(); // Wrap around to invalid value | |
921 | } else { | |
922 | --model_iter; | |
923 | } | |
924 | ASSERT_EQ(ToString(data, model_iter), ToString(iter)); | |
925 | } | |
926 | break; | |
927 | } | |
928 | ||
929 | case 4: { | |
930 | if (kVerbose) fprintf(stderr, "SeekToLast\n"); | |
931 | iter->SeekToLast(); | |
932 | if (keys.empty()) { | |
933 | model_iter = data.end(); | |
934 | } else { | |
935 | std::string last = data.rbegin()->first; | |
936 | model_iter = data.lower_bound(last); | |
937 | } | |
938 | ASSERT_EQ(ToString(data, model_iter), ToString(iter)); | |
939 | break; | |
940 | } | |
941 | } | |
942 | } | |
943 | if (constructor_->IsArenaMode() && !constructor_->AnywayDeleteIterator()) { | |
944 | iter->~InternalIterator(); | |
945 | } else { | |
946 | delete iter; | |
947 | } | |
948 | } | |
949 | ||
950 | std::string ToString(const stl_wrappers::KVMap& data, | |
951 | const stl_wrappers::KVMap::const_iterator& it) { | |
952 | if (it == data.end()) { | |
953 | return "END"; | |
954 | } else { | |
955 | return "'" + it->first + "->" + it->second + "'"; | |
956 | } | |
957 | } | |
958 | ||
959 | std::string ToString(const stl_wrappers::KVMap& data, | |
960 | const stl_wrappers::KVMap::const_reverse_iterator& it) { | |
961 | if (it == data.rend()) { | |
962 | return "END"; | |
963 | } else { | |
964 | return "'" + it->first + "->" + it->second + "'"; | |
965 | } | |
966 | } | |
967 | ||
968 | std::string ToString(const InternalIterator* it) { | |
969 | if (!it->Valid()) { | |
970 | return "END"; | |
971 | } else { | |
972 | return "'" + it->key().ToString() + "->" + it->value().ToString() + "'"; | |
973 | } | |
974 | } | |
975 | ||
976 | std::string PickRandomKey(Random* rnd, const std::vector<std::string>& keys) { | |
977 | if (keys.empty()) { | |
978 | return "foo"; | |
979 | } else { | |
980 | const int index = rnd->Uniform(static_cast<int>(keys.size())); | |
981 | std::string result = keys[index]; | |
982 | switch (rnd->Uniform(support_prev_ ? 3 : 1)) { | |
983 | case 0: | |
984 | // Return an existing key | |
985 | break; | |
986 | case 1: { | |
987 | // Attempt to return something smaller than an existing key | |
988 | if (result.size() > 0 && result[result.size() - 1] > '\0' | |
989 | && (!only_support_prefix_seek_ | |
990 | || options_.prefix_extractor->Transform(result).size() | |
991 | < result.size())) { | |
992 | result[result.size() - 1]--; | |
993 | } | |
994 | break; | |
995 | } | |
996 | case 2: { | |
997 | // Return something larger than an existing key | |
998 | Increment(options_.comparator, &result); | |
999 | break; | |
1000 | } | |
1001 | } | |
1002 | return result; | |
1003 | } | |
1004 | } | |
1005 | ||
1006 | // Returns nullptr if not running against a DB | |
1007 | DB* db() const { return constructor_->db(); } | |
1008 | ||
11fdf7f2 TL |
1009 | void RandomizedHarnessTest(size_t part, size_t total) { |
1010 | std::vector<TestArgs> args = GenerateArgList(); | |
1011 | assert(part); | |
1012 | assert(part <= total); | |
1013 | for (size_t i = 0; i < args.size(); i++) { | |
1014 | if ((i % total) + 1 != part) { | |
1015 | continue; | |
1016 | } | |
1017 | Init(args[i]); | |
1018 | Random rnd(test::RandomSeed() + 5); | |
1019 | for (int num_entries = 0; num_entries < 2000; | |
1020 | num_entries += (num_entries < 50 ? 1 : 200)) { | |
1021 | for (int e = 0; e < num_entries; e++) { | |
1022 | std::string v; | |
1023 | Add(test::RandomKey(&rnd, rnd.Skewed(4)), | |
1024 | test::RandomString(&rnd, rnd.Skewed(5), &v).ToString()); | |
1025 | } | |
1026 | Test(&rnd); | |
1027 | } | |
1028 | } | |
1029 | } | |
1030 | ||
7c673cae FG |
1031 | private: |
1032 | Options options_ = Options(); | |
1033 | ImmutableCFOptions ioptions_; | |
11fdf7f2 | 1034 | MutableCFOptions moptions_; |
7c673cae FG |
1035 | BlockBasedTableOptions table_options_ = BlockBasedTableOptions(); |
1036 | Constructor* constructor_; | |
1037 | WriteBufferManager write_buffer_; | |
1038 | bool support_prev_; | |
1039 | bool only_support_prefix_seek_; | |
494da23a | 1040 | std::shared_ptr<InternalKeyComparator> internal_comparator_; |
7c673cae FG |
1041 | }; |
1042 | ||
1043 | static bool Between(uint64_t val, uint64_t low, uint64_t high) { | |
1044 | bool result = (val >= low) && (val <= high); | |
1045 | if (!result) { | |
1046 | fprintf(stderr, "Value %llu is not in range [%llu, %llu]\n", | |
1047 | (unsigned long long)(val), | |
1048 | (unsigned long long)(low), | |
1049 | (unsigned long long)(high)); | |
1050 | } | |
1051 | return result; | |
1052 | } | |
1053 | ||
1054 | // Tests against all kinds of tables | |
1055 | class TableTest : public testing::Test { | |
1056 | public: | |
1057 | const InternalKeyComparator& GetPlainInternalComparator( | |
1058 | const Comparator* comp) { | |
1059 | if (!plain_internal_comparator) { | |
1060 | plain_internal_comparator.reset( | |
1061 | new test::PlainInternalKeyComparator(comp)); | |
1062 | } | |
1063 | return *plain_internal_comparator; | |
1064 | } | |
1065 | void IndexTest(BlockBasedTableOptions table_options); | |
1066 | ||
1067 | private: | |
1068 | std::unique_ptr<InternalKeyComparator> plain_internal_comparator; | |
1069 | }; | |
1070 | ||
1071 | class GeneralTableTest : public TableTest {}; | |
11fdf7f2 TL |
1072 | class BlockBasedTableTest |
1073 | : public TableTest, | |
1074 | virtual public ::testing::WithParamInterface<uint32_t> { | |
1075 | public: | |
f67539c2 TL |
1076 | BlockBasedTableTest() : format_(GetParam()) { |
1077 | env_ = ROCKSDB_NAMESPACE::Env::Default(); | |
1078 | } | |
11fdf7f2 TL |
1079 | |
1080 | BlockBasedTableOptions GetBlockBasedTableOptions() { | |
1081 | BlockBasedTableOptions options; | |
1082 | options.format_version = format_; | |
1083 | return options; | |
1084 | } | |
1085 | ||
f67539c2 TL |
1086 | void SetupTracingTest(TableConstructor* c) { |
1087 | test_path_ = test::PerThreadDBPath("block_based_table_tracing_test"); | |
1088 | EXPECT_OK(env_->CreateDir(test_path_)); | |
1089 | trace_file_path_ = test_path_ + "/block_cache_trace_file"; | |
1090 | TraceOptions trace_opt; | |
1091 | std::unique_ptr<TraceWriter> trace_writer; | |
1092 | EXPECT_OK(NewFileTraceWriter(env_, EnvOptions(), trace_file_path_, | |
1093 | &trace_writer)); | |
1094 | c->block_cache_tracer_.StartTrace(env_, trace_opt, std::move(trace_writer)); | |
1095 | { | |
1096 | std::string user_key = "k01"; | |
1097 | InternalKey internal_key(user_key, 0, kTypeValue); | |
1098 | std::string encoded_key = internal_key.Encode().ToString(); | |
1099 | c->Add(encoded_key, kDummyValue); | |
1100 | } | |
1101 | { | |
1102 | std::string user_key = "k02"; | |
1103 | InternalKey internal_key(user_key, 0, kTypeValue); | |
1104 | std::string encoded_key = internal_key.Encode().ToString(); | |
1105 | c->Add(encoded_key, kDummyValue); | |
1106 | } | |
1107 | } | |
1108 | ||
1109 | void VerifyBlockAccessTrace( | |
1110 | TableConstructor* c, | |
1111 | const std::vector<BlockCacheTraceRecord>& expected_records) { | |
1112 | c->block_cache_tracer_.EndTrace(); | |
1113 | ||
1114 | std::unique_ptr<TraceReader> trace_reader; | |
1115 | Status s = | |
1116 | NewFileTraceReader(env_, EnvOptions(), trace_file_path_, &trace_reader); | |
1117 | EXPECT_OK(s); | |
1118 | BlockCacheTraceReader reader(std::move(trace_reader)); | |
1119 | BlockCacheTraceHeader header; | |
1120 | EXPECT_OK(reader.ReadHeader(&header)); | |
1121 | uint32_t index = 0; | |
1122 | while (s.ok()) { | |
1123 | BlockCacheTraceRecord access; | |
1124 | s = reader.ReadAccess(&access); | |
1125 | if (!s.ok()) { | |
1126 | break; | |
1127 | } | |
1128 | ASSERT_LT(index, expected_records.size()); | |
1129 | EXPECT_NE("", access.block_key); | |
1130 | EXPECT_EQ(access.block_type, expected_records[index].block_type); | |
1131 | EXPECT_GT(access.block_size, 0); | |
1132 | EXPECT_EQ(access.caller, expected_records[index].caller); | |
1133 | EXPECT_EQ(access.no_insert, expected_records[index].no_insert); | |
1134 | EXPECT_EQ(access.is_cache_hit, expected_records[index].is_cache_hit); | |
1135 | // Get | |
1136 | if (access.caller == TableReaderCaller::kUserGet) { | |
1137 | EXPECT_EQ(access.referenced_key, | |
1138 | expected_records[index].referenced_key); | |
1139 | EXPECT_EQ(access.get_id, expected_records[index].get_id); | |
1140 | EXPECT_EQ(access.get_from_user_specified_snapshot, | |
1141 | expected_records[index].get_from_user_specified_snapshot); | |
1142 | if (access.block_type == TraceType::kBlockTraceDataBlock) { | |
1143 | EXPECT_GT(access.referenced_data_size, 0); | |
1144 | EXPECT_GT(access.num_keys_in_block, 0); | |
1145 | EXPECT_EQ(access.referenced_key_exist_in_block, | |
1146 | expected_records[index].referenced_key_exist_in_block); | |
1147 | } | |
1148 | } else { | |
1149 | EXPECT_EQ(access.referenced_key, ""); | |
1150 | EXPECT_EQ(access.get_id, 0); | |
1151 | EXPECT_TRUE(access.get_from_user_specified_snapshot == Boolean::kFalse); | |
1152 | EXPECT_EQ(access.referenced_data_size, 0); | |
1153 | EXPECT_EQ(access.num_keys_in_block, 0); | |
1154 | EXPECT_TRUE(access.referenced_key_exist_in_block == Boolean::kFalse); | |
1155 | } | |
1156 | index++; | |
1157 | } | |
1158 | EXPECT_EQ(index, expected_records.size()); | |
1159 | EXPECT_OK(env_->DeleteFile(trace_file_path_)); | |
1160 | EXPECT_OK(env_->DeleteDir(test_path_)); | |
1161 | } | |
1162 | ||
11fdf7f2 TL |
1163 | protected: |
1164 | uint64_t IndexUncompressedHelper(bool indexCompress); | |
1165 | ||
1166 | private: | |
1167 | uint32_t format_; | |
f67539c2 TL |
1168 | Env* env_; |
1169 | std::string trace_file_path_; | |
1170 | std::string test_path_; | |
11fdf7f2 | 1171 | }; |
7c673cae FG |
1172 | class PlainTableTest : public TableTest {}; |
1173 | class TablePropertyTest : public testing::Test {}; | |
11fdf7f2 TL |
1174 | class BBTTailPrefetchTest : public TableTest {}; |
1175 | ||
f67539c2 TL |
1176 | // The helper class to test the file checksum |
1177 | class FileChecksumTestHelper { | |
1178 | public: | |
1179 | FileChecksumTestHelper(bool convert_to_internal_key = false) | |
1180 | : convert_to_internal_key_(convert_to_internal_key) { | |
1181 | sink_ = new test::StringSink(); | |
1182 | } | |
1183 | ~FileChecksumTestHelper() {} | |
1184 | ||
1185 | void CreateWriteableFile() { | |
1186 | file_writer_.reset(test::GetWritableFileWriter(sink_, "" /* don't care */)); | |
1187 | } | |
1188 | ||
1189 | void SetFileChecksumFunc(FileChecksumFunc* checksum_func) { | |
1190 | if (file_writer_ != nullptr) { | |
1191 | file_writer_->TEST_SetFileChecksumFunc(checksum_func); | |
1192 | } | |
1193 | } | |
1194 | ||
1195 | WritableFileWriter* GetFileWriter() { return file_writer_.get(); } | |
1196 | ||
1197 | Status ResetTableBuilder(std::unique_ptr<TableBuilder>&& builder) { | |
1198 | assert(builder != nullptr); | |
1199 | table_builder_ = std::move(builder); | |
1200 | return Status::OK(); | |
1201 | } | |
1202 | ||
1203 | void AddKVtoKVMap(int num_entries) { | |
1204 | Random rnd(test::RandomSeed()); | |
1205 | for (int i = 0; i < num_entries; i++) { | |
1206 | std::string v; | |
1207 | test::RandomString(&rnd, 100, &v); | |
1208 | kv_map_[test::RandomKey(&rnd, 20)] = v; | |
1209 | } | |
1210 | } | |
1211 | ||
1212 | Status WriteKVAndFlushTable() { | |
1213 | for (const auto kv : kv_map_) { | |
1214 | if (convert_to_internal_key_) { | |
1215 | ParsedInternalKey ikey(kv.first, kMaxSequenceNumber, kTypeValue); | |
1216 | std::string encoded; | |
1217 | AppendInternalKey(&encoded, ikey); | |
1218 | table_builder_->Add(encoded, kv.second); | |
1219 | } else { | |
1220 | table_builder_->Add(kv.first, kv.second); | |
1221 | } | |
1222 | EXPECT_TRUE(table_builder_->status().ok()); | |
1223 | } | |
1224 | Status s = table_builder_->Finish(); | |
1225 | file_writer_->Flush(); | |
1226 | EXPECT_TRUE(s.ok()); | |
1227 | ||
1228 | EXPECT_EQ(sink_->contents().size(), table_builder_->FileSize()); | |
1229 | return s; | |
1230 | } | |
1231 | ||
1232 | std::string GetFileChecksum() { return table_builder_->GetFileChecksum(); } | |
1233 | ||
1234 | const char* GetFileChecksumFuncName() { | |
1235 | return table_builder_->GetFileChecksumFuncName(); | |
1236 | } | |
1237 | ||
1238 | Status CalculateFileChecksum(FileChecksumFunc* file_checksum_func, | |
1239 | std::string* checksum) { | |
1240 | assert(file_checksum_func != nullptr); | |
1241 | cur_uniq_id_ = checksum_uniq_id_++; | |
1242 | test::StringSink* ss_rw = | |
1243 | ROCKSDB_NAMESPACE::test::GetStringSinkFromLegacyWriter( | |
1244 | file_writer_.get()); | |
1245 | file_reader_.reset(test::GetRandomAccessFileReader( | |
1246 | new test::StringSource(ss_rw->contents()))); | |
1247 | std::unique_ptr<char[]> scratch(new char[2048]); | |
1248 | Slice result; | |
1249 | uint64_t offset = 0; | |
1250 | std::string tmp_checksum; | |
1251 | bool first_read = true; | |
1252 | Status s; | |
1253 | s = file_reader_->Read(offset, 2048, &result, scratch.get(), false); | |
1254 | if (!s.ok()) { | |
1255 | return s; | |
1256 | } | |
1257 | while (result.size() != 0) { | |
1258 | if (first_read) { | |
1259 | first_read = false; | |
1260 | tmp_checksum = file_checksum_func->Value(scratch.get(), result.size()); | |
1261 | } else { | |
1262 | tmp_checksum = file_checksum_func->Extend(tmp_checksum, scratch.get(), | |
1263 | result.size()); | |
1264 | } | |
1265 | offset += static_cast<uint64_t>(result.size()); | |
1266 | s = file_reader_->Read(offset, 2048, &result, scratch.get(), false); | |
1267 | if (!s.ok()) { | |
1268 | return s; | |
1269 | } | |
1270 | } | |
1271 | EXPECT_EQ(offset, static_cast<uint64_t>(table_builder_->FileSize())); | |
1272 | *checksum = tmp_checksum; | |
1273 | return Status::OK(); | |
1274 | } | |
1275 | ||
1276 | private: | |
1277 | bool convert_to_internal_key_; | |
1278 | uint64_t cur_uniq_id_; | |
1279 | std::unique_ptr<WritableFileWriter> file_writer_; | |
1280 | std::unique_ptr<RandomAccessFileReader> file_reader_; | |
1281 | std::unique_ptr<TableBuilder> table_builder_; | |
1282 | stl_wrappers::KVMap kv_map_; | |
1283 | test::StringSink* sink_; | |
1284 | ||
1285 | static uint64_t checksum_uniq_id_; | |
1286 | }; | |
1287 | ||
1288 | uint64_t FileChecksumTestHelper::checksum_uniq_id_ = 1; | |
1289 | ||
11fdf7f2 TL |
1290 | INSTANTIATE_TEST_CASE_P(FormatDef, BlockBasedTableTest, |
1291 | testing::Values(test::kDefaultFormatVersion)); | |
1292 | INSTANTIATE_TEST_CASE_P(FormatLatest, BlockBasedTableTest, | |
1293 | testing::Values(test::kLatestFormatVersion)); | |
7c673cae FG |
1294 | |
1295 | // This test serves as the living tutorial for the prefix scan of user collected | |
1296 | // properties. | |
1297 | TEST_F(TablePropertyTest, PrefixScanTest) { | |
1298 | UserCollectedProperties props{{"num.111.1", "1"}, | |
1299 | {"num.111.2", "2"}, | |
1300 | {"num.111.3", "3"}, | |
1301 | {"num.333.1", "1"}, | |
1302 | {"num.333.2", "2"}, | |
1303 | {"num.333.3", "3"}, | |
1304 | {"num.555.1", "1"}, | |
1305 | {"num.555.2", "2"}, | |
1306 | {"num.555.3", "3"}, }; | |
1307 | ||
1308 | // prefixes that exist | |
1309 | for (const std::string& prefix : {"num.111", "num.333", "num.555"}) { | |
1310 | int num = 0; | |
1311 | for (auto pos = props.lower_bound(prefix); | |
1312 | pos != props.end() && | |
1313 | pos->first.compare(0, prefix.size(), prefix) == 0; | |
1314 | ++pos) { | |
1315 | ++num; | |
1316 | auto key = prefix + "." + ToString(num); | |
1317 | ASSERT_EQ(key, pos->first); | |
1318 | ASSERT_EQ(ToString(num), pos->second); | |
1319 | } | |
1320 | ASSERT_EQ(3, num); | |
1321 | } | |
1322 | ||
1323 | // prefixes that don't exist | |
1324 | for (const std::string& prefix : | |
1325 | {"num.000", "num.222", "num.444", "num.666"}) { | |
1326 | auto pos = props.lower_bound(prefix); | |
1327 | ASSERT_TRUE(pos == props.end() || | |
1328 | pos->first.compare(0, prefix.size(), prefix) != 0); | |
1329 | } | |
1330 | } | |
1331 | ||
1332 | // This test include all the basic checks except those for index size and block | |
1333 | // size, which will be conducted in separated unit tests. | |
11fdf7f2 | 1334 | TEST_P(BlockBasedTableTest, BasicBlockBasedTableProperties) { |
7c673cae FG |
1335 | TableConstructor c(BytewiseComparator(), true /* convert_to_internal_key_ */); |
1336 | ||
1337 | c.Add("a1", "val1"); | |
1338 | c.Add("b2", "val2"); | |
1339 | c.Add("c3", "val3"); | |
1340 | c.Add("d4", "val4"); | |
1341 | c.Add("e5", "val5"); | |
1342 | c.Add("f6", "val6"); | |
1343 | c.Add("g7", "val7"); | |
1344 | c.Add("h8", "val8"); | |
1345 | c.Add("j9", "val9"); | |
1346 | uint64_t diff_internal_user_bytes = 9 * 8; // 8 is seq size, 9 k-v totally | |
1347 | ||
1348 | std::vector<std::string> keys; | |
1349 | stl_wrappers::KVMap kvmap; | |
1350 | Options options; | |
1351 | options.compression = kNoCompression; | |
11fdf7f2 | 1352 | options.statistics = CreateDBStatistics(); |
494da23a | 1353 | options.statistics->set_stats_level(StatsLevel::kAll); |
11fdf7f2 | 1354 | BlockBasedTableOptions table_options = GetBlockBasedTableOptions(); |
7c673cae FG |
1355 | table_options.block_restart_interval = 1; |
1356 | options.table_factory.reset(NewBlockBasedTableFactory(table_options)); | |
1357 | ||
11fdf7f2 TL |
1358 | ImmutableCFOptions ioptions(options); |
1359 | MutableCFOptions moptions(options); | |
1360 | ioptions.statistics = options.statistics.get(); | |
1361 | c.Finish(options, ioptions, moptions, table_options, | |
7c673cae | 1362 | GetPlainInternalComparator(options.comparator), &keys, &kvmap); |
11fdf7f2 | 1363 | ASSERT_EQ(options.statistics->getTickerCount(NUMBER_BLOCK_NOT_COMPRESSED), 0); |
7c673cae FG |
1364 | |
1365 | auto& props = *c.GetTableReader()->GetTableProperties(); | |
1366 | ASSERT_EQ(kvmap.size(), props.num_entries); | |
1367 | ||
1368 | auto raw_key_size = kvmap.size() * 2ul; | |
1369 | auto raw_value_size = kvmap.size() * 4ul; | |
1370 | ||
1371 | ASSERT_EQ(raw_key_size + diff_internal_user_bytes, props.raw_key_size); | |
1372 | ASSERT_EQ(raw_value_size, props.raw_value_size); | |
1373 | ASSERT_EQ(1ul, props.num_data_blocks); | |
1374 | ASSERT_EQ("", props.filter_policy_name); // no filter policy is used | |
1375 | ||
1376 | // Verify data size. | |
1377 | BlockBuilder block_builder(1); | |
1378 | for (const auto& item : kvmap) { | |
1379 | block_builder.Add(item.first, item.second); | |
1380 | } | |
1381 | Slice content = block_builder.Finish(); | |
1382 | ASSERT_EQ(content.size() + kBlockTrailerSize + diff_internal_user_bytes, | |
1383 | props.data_size); | |
1384 | c.ResetTableReader(); | |
1385 | } | |
1386 | ||
11fdf7f2 TL |
1387 | #ifdef SNAPPY |
1388 | uint64_t BlockBasedTableTest::IndexUncompressedHelper(bool compressed) { | |
1389 | TableConstructor c(BytewiseComparator(), true /* convert_to_internal_key_ */); | |
1390 | constexpr size_t kNumKeys = 10000; | |
1391 | ||
1392 | for (size_t k = 0; k < kNumKeys; ++k) { | |
1393 | c.Add("key" + ToString(k), "val" + ToString(k)); | |
1394 | } | |
1395 | ||
1396 | std::vector<std::string> keys; | |
1397 | stl_wrappers::KVMap kvmap; | |
1398 | Options options; | |
1399 | options.compression = kSnappyCompression; | |
1400 | options.statistics = CreateDBStatistics(); | |
494da23a | 1401 | options.statistics->set_stats_level(StatsLevel::kAll); |
11fdf7f2 TL |
1402 | BlockBasedTableOptions table_options = GetBlockBasedTableOptions(); |
1403 | table_options.block_restart_interval = 1; | |
1404 | table_options.enable_index_compression = compressed; | |
1405 | options.table_factory.reset(NewBlockBasedTableFactory(table_options)); | |
1406 | ||
1407 | ImmutableCFOptions ioptions(options); | |
1408 | MutableCFOptions moptions(options); | |
1409 | ioptions.statistics = options.statistics.get(); | |
1410 | c.Finish(options, ioptions, moptions, table_options, | |
1411 | GetPlainInternalComparator(options.comparator), &keys, &kvmap); | |
1412 | c.ResetTableReader(); | |
1413 | return options.statistics->getTickerCount(NUMBER_BLOCK_COMPRESSED); | |
1414 | } | |
1415 | TEST_P(BlockBasedTableTest, IndexUncompressed) { | |
1416 | uint64_t tbl1_compressed_cnt = IndexUncompressedHelper(true); | |
1417 | uint64_t tbl2_compressed_cnt = IndexUncompressedHelper(false); | |
1418 | // tbl1_compressed_cnt should include 1 index block | |
1419 | EXPECT_EQ(tbl2_compressed_cnt + 1, tbl1_compressed_cnt); | |
1420 | } | |
1421 | #endif // SNAPPY | |
1422 | ||
1423 | TEST_P(BlockBasedTableTest, BlockBasedTableProperties2) { | |
7c673cae FG |
1424 | TableConstructor c(&reverse_key_comparator); |
1425 | std::vector<std::string> keys; | |
1426 | stl_wrappers::KVMap kvmap; | |
1427 | ||
1428 | { | |
1429 | Options options; | |
1430 | options.compression = CompressionType::kNoCompression; | |
11fdf7f2 | 1431 | BlockBasedTableOptions table_options = GetBlockBasedTableOptions(); |
7c673cae FG |
1432 | options.table_factory.reset(NewBlockBasedTableFactory(table_options)); |
1433 | ||
1434 | const ImmutableCFOptions ioptions(options); | |
11fdf7f2 TL |
1435 | const MutableCFOptions moptions(options); |
1436 | c.Finish(options, ioptions, moptions, table_options, | |
7c673cae FG |
1437 | GetPlainInternalComparator(options.comparator), &keys, &kvmap); |
1438 | ||
1439 | auto& props = *c.GetTableReader()->GetTableProperties(); | |
1440 | ||
1441 | // Default comparator | |
1442 | ASSERT_EQ("leveldb.BytewiseComparator", props.comparator_name); | |
1443 | // No merge operator | |
1444 | ASSERT_EQ("nullptr", props.merge_operator_name); | |
1445 | // No prefix extractor | |
1446 | ASSERT_EQ("nullptr", props.prefix_extractor_name); | |
1447 | // No property collectors | |
1448 | ASSERT_EQ("[]", props.property_collectors_names); | |
1449 | // No filter policy is used | |
1450 | ASSERT_EQ("", props.filter_policy_name); | |
1451 | // Compression type == that set: | |
1452 | ASSERT_EQ("NoCompression", props.compression_name); | |
1453 | c.ResetTableReader(); | |
1454 | } | |
1455 | ||
1456 | { | |
1457 | Options options; | |
11fdf7f2 | 1458 | BlockBasedTableOptions table_options = GetBlockBasedTableOptions(); |
7c673cae FG |
1459 | options.table_factory.reset(NewBlockBasedTableFactory(table_options)); |
1460 | options.comparator = &reverse_key_comparator; | |
1461 | options.merge_operator = MergeOperators::CreateUInt64AddOperator(); | |
1462 | options.prefix_extractor.reset(NewNoopTransform()); | |
1463 | options.table_properties_collector_factories.emplace_back( | |
1464 | new DummyPropertiesCollectorFactory1()); | |
1465 | options.table_properties_collector_factories.emplace_back( | |
1466 | new DummyPropertiesCollectorFactory2()); | |
1467 | ||
1468 | const ImmutableCFOptions ioptions(options); | |
11fdf7f2 TL |
1469 | const MutableCFOptions moptions(options); |
1470 | c.Finish(options, ioptions, moptions, table_options, | |
7c673cae FG |
1471 | GetPlainInternalComparator(options.comparator), &keys, &kvmap); |
1472 | ||
1473 | auto& props = *c.GetTableReader()->GetTableProperties(); | |
1474 | ||
1475 | ASSERT_EQ("rocksdb.ReverseBytewiseComparator", props.comparator_name); | |
1476 | ASSERT_EQ("UInt64AddOperator", props.merge_operator_name); | |
1477 | ASSERT_EQ("rocksdb.Noop", props.prefix_extractor_name); | |
1478 | ASSERT_EQ("[DummyPropertiesCollector1,DummyPropertiesCollector2]", | |
1479 | props.property_collectors_names); | |
1480 | ASSERT_EQ("", props.filter_policy_name); // no filter policy is used | |
1481 | c.ResetTableReader(); | |
1482 | } | |
1483 | } | |
1484 | ||
11fdf7f2 | 1485 | TEST_P(BlockBasedTableTest, RangeDelBlock) { |
7c673cae FG |
1486 | TableConstructor c(BytewiseComparator()); |
1487 | std::vector<std::string> keys = {"1pika", "2chu"}; | |
1488 | std::vector<std::string> vals = {"p", "c"}; | |
1489 | ||
494da23a TL |
1490 | std::vector<RangeTombstone> expected_tombstones = { |
1491 | {"1pika", "2chu", 0}, | |
1492 | {"2chu", "c", 1}, | |
1493 | {"2chu", "c", 0}, | |
1494 | {"c", "p", 0}, | |
1495 | }; | |
1496 | ||
7c673cae FG |
1497 | for (int i = 0; i < 2; i++) { |
1498 | RangeTombstone t(keys[i], vals[i], i); | |
1499 | std::pair<InternalKey, Slice> p = t.Serialize(); | |
1500 | c.Add(p.first.Encode().ToString(), p.second); | |
1501 | } | |
1502 | ||
1503 | std::vector<std::string> sorted_keys; | |
1504 | stl_wrappers::KVMap kvmap; | |
1505 | Options options; | |
1506 | options.compression = kNoCompression; | |
11fdf7f2 | 1507 | BlockBasedTableOptions table_options = GetBlockBasedTableOptions(); |
7c673cae FG |
1508 | table_options.block_restart_interval = 1; |
1509 | options.table_factory.reset(NewBlockBasedTableFactory(table_options)); | |
1510 | ||
1511 | const ImmutableCFOptions ioptions(options); | |
11fdf7f2 | 1512 | const MutableCFOptions moptions(options); |
7c673cae FG |
1513 | std::unique_ptr<InternalKeyComparator> internal_cmp( |
1514 | new InternalKeyComparator(options.comparator)); | |
11fdf7f2 TL |
1515 | c.Finish(options, ioptions, moptions, table_options, *internal_cmp, |
1516 | &sorted_keys, &kvmap); | |
7c673cae FG |
1517 | |
1518 | for (int j = 0; j < 2; ++j) { | |
1519 | std::unique_ptr<InternalIterator> iter( | |
1520 | c.GetTableReader()->NewRangeTombstoneIterator(ReadOptions())); | |
1521 | if (j > 0) { | |
1522 | // For second iteration, delete the table reader object and verify the | |
1523 | // iterator can still access its metablock's range tombstones. | |
1524 | c.ResetTableReader(); | |
1525 | } | |
1526 | ASSERT_FALSE(iter->Valid()); | |
1527 | iter->SeekToFirst(); | |
1528 | ASSERT_TRUE(iter->Valid()); | |
494da23a | 1529 | for (size_t i = 0; i < expected_tombstones.size(); i++) { |
7c673cae FG |
1530 | ASSERT_TRUE(iter->Valid()); |
1531 | ParsedInternalKey parsed_key; | |
1532 | ASSERT_TRUE(ParseInternalKey(iter->key(), &parsed_key)); | |
1533 | RangeTombstone t(parsed_key, iter->value()); | |
494da23a TL |
1534 | const auto& expected_t = expected_tombstones[i]; |
1535 | ASSERT_EQ(t.start_key_, expected_t.start_key_); | |
1536 | ASSERT_EQ(t.end_key_, expected_t.end_key_); | |
1537 | ASSERT_EQ(t.seq_, expected_t.seq_); | |
7c673cae FG |
1538 | iter->Next(); |
1539 | } | |
1540 | ASSERT_TRUE(!iter->Valid()); | |
1541 | } | |
1542 | } | |
1543 | ||
11fdf7f2 | 1544 | TEST_P(BlockBasedTableTest, FilterPolicyNameProperties) { |
7c673cae FG |
1545 | TableConstructor c(BytewiseComparator(), true /* convert_to_internal_key_ */); |
1546 | c.Add("a1", "val1"); | |
1547 | std::vector<std::string> keys; | |
1548 | stl_wrappers::KVMap kvmap; | |
11fdf7f2 | 1549 | BlockBasedTableOptions table_options = GetBlockBasedTableOptions(); |
7c673cae FG |
1550 | table_options.filter_policy.reset(NewBloomFilterPolicy(10)); |
1551 | Options options; | |
1552 | options.table_factory.reset(NewBlockBasedTableFactory(table_options)); | |
1553 | ||
1554 | const ImmutableCFOptions ioptions(options); | |
11fdf7f2 TL |
1555 | const MutableCFOptions moptions(options); |
1556 | c.Finish(options, ioptions, moptions, table_options, | |
7c673cae FG |
1557 | GetPlainInternalComparator(options.comparator), &keys, &kvmap); |
1558 | auto& props = *c.GetTableReader()->GetTableProperties(); | |
1559 | ASSERT_EQ("rocksdb.BuiltinBloomFilter", props.filter_policy_name); | |
1560 | c.ResetTableReader(); | |
1561 | } | |
1562 | ||
1563 | // | |
1564 | // BlockBasedTableTest::PrefetchTest | |
1565 | // | |
1566 | void AssertKeysInCache(BlockBasedTable* table_reader, | |
1567 | const std::vector<std::string>& keys_in_cache, | |
1568 | const std::vector<std::string>& keys_not_in_cache, | |
1569 | bool convert = false) { | |
1570 | if (convert) { | |
1571 | for (auto key : keys_in_cache) { | |
1572 | InternalKey ikey(key, kMaxSequenceNumber, kTypeValue); | |
1573 | ASSERT_TRUE(table_reader->TEST_KeyInCache(ReadOptions(), ikey.Encode())); | |
1574 | } | |
1575 | for (auto key : keys_not_in_cache) { | |
1576 | InternalKey ikey(key, kMaxSequenceNumber, kTypeValue); | |
1577 | ASSERT_TRUE(!table_reader->TEST_KeyInCache(ReadOptions(), ikey.Encode())); | |
1578 | } | |
1579 | } else { | |
1580 | for (auto key : keys_in_cache) { | |
1581 | ASSERT_TRUE(table_reader->TEST_KeyInCache(ReadOptions(), key)); | |
1582 | } | |
1583 | for (auto key : keys_not_in_cache) { | |
1584 | ASSERT_TRUE(!table_reader->TEST_KeyInCache(ReadOptions(), key)); | |
1585 | } | |
1586 | } | |
1587 | } | |
1588 | ||
1589 | void PrefetchRange(TableConstructor* c, Options* opt, | |
1590 | BlockBasedTableOptions* table_options, const char* key_begin, | |
1591 | const char* key_end, | |
1592 | const std::vector<std::string>& keys_in_cache, | |
1593 | const std::vector<std::string>& keys_not_in_cache, | |
1594 | const Status expected_status = Status::OK()) { | |
1595 | // reset the cache and reopen the table | |
1596 | table_options->block_cache = NewLRUCache(16 * 1024 * 1024, 4); | |
1597 | opt->table_factory.reset(NewBlockBasedTableFactory(*table_options)); | |
1598 | const ImmutableCFOptions ioptions2(*opt); | |
11fdf7f2 TL |
1599 | const MutableCFOptions moptions(*opt); |
1600 | ASSERT_OK(c->Reopen(ioptions2, moptions)); | |
7c673cae FG |
1601 | |
1602 | // prefetch | |
1603 | auto* table_reader = dynamic_cast<BlockBasedTable*>(c->GetTableReader()); | |
1604 | Status s; | |
494da23a TL |
1605 | std::unique_ptr<Slice> begin, end; |
1606 | std::unique_ptr<InternalKey> i_begin, i_end; | |
7c673cae FG |
1607 | if (key_begin != nullptr) { |
1608 | if (c->ConvertToInternalKey()) { | |
1609 | i_begin.reset(new InternalKey(key_begin, kMaxSequenceNumber, kTypeValue)); | |
1610 | begin.reset(new Slice(i_begin->Encode())); | |
1611 | } else { | |
1612 | begin.reset(new Slice(key_begin)); | |
1613 | } | |
1614 | } | |
1615 | if (key_end != nullptr) { | |
1616 | if (c->ConvertToInternalKey()) { | |
1617 | i_end.reset(new InternalKey(key_end, kMaxSequenceNumber, kTypeValue)); | |
1618 | end.reset(new Slice(i_end->Encode())); | |
1619 | } else { | |
1620 | end.reset(new Slice(key_end)); | |
1621 | } | |
1622 | } | |
1623 | s = table_reader->Prefetch(begin.get(), end.get()); | |
1624 | ||
1625 | ASSERT_TRUE(s.code() == expected_status.code()); | |
1626 | ||
1627 | // assert our expectation in cache warmup | |
1628 | AssertKeysInCache(table_reader, keys_in_cache, keys_not_in_cache, | |
1629 | c->ConvertToInternalKey()); | |
1630 | c->ResetTableReader(); | |
1631 | } | |
1632 | ||
11fdf7f2 | 1633 | TEST_P(BlockBasedTableTest, PrefetchTest) { |
7c673cae FG |
1634 | // The purpose of this test is to test the prefetching operation built into |
1635 | // BlockBasedTable. | |
1636 | Options opt; | |
494da23a | 1637 | std::unique_ptr<InternalKeyComparator> ikc; |
7c673cae FG |
1638 | ikc.reset(new test::PlainInternalKeyComparator(opt.comparator)); |
1639 | opt.compression = kNoCompression; | |
11fdf7f2 | 1640 | BlockBasedTableOptions table_options = GetBlockBasedTableOptions(); |
7c673cae FG |
1641 | table_options.block_size = 1024; |
1642 | // big enough so we don't ever lose cached values. | |
1643 | table_options.block_cache = NewLRUCache(16 * 1024 * 1024, 4); | |
1644 | opt.table_factory.reset(NewBlockBasedTableFactory(table_options)); | |
1645 | ||
1646 | TableConstructor c(BytewiseComparator(), true /* convert_to_internal_key_ */); | |
1647 | c.Add("k01", "hello"); | |
1648 | c.Add("k02", "hello2"); | |
1649 | c.Add("k03", std::string(10000, 'x')); | |
1650 | c.Add("k04", std::string(200000, 'x')); | |
1651 | c.Add("k05", std::string(300000, 'x')); | |
1652 | c.Add("k06", "hello3"); | |
1653 | c.Add("k07", std::string(100000, 'x')); | |
1654 | std::vector<std::string> keys; | |
1655 | stl_wrappers::KVMap kvmap; | |
1656 | const ImmutableCFOptions ioptions(opt); | |
11fdf7f2 TL |
1657 | const MutableCFOptions moptions(opt); |
1658 | c.Finish(opt, ioptions, moptions, table_options, *ikc, &keys, &kvmap); | |
7c673cae FG |
1659 | c.ResetTableReader(); |
1660 | ||
1661 | // We get the following data spread : | |
1662 | // | |
1663 | // Data block Index | |
1664 | // ======================== | |
1665 | // [ k01 k02 k03 ] k03 | |
1666 | // [ k04 ] k04 | |
1667 | // [ k05 ] k05 | |
1668 | // [ k06 k07 ] k07 | |
1669 | ||
1670 | ||
1671 | // Simple | |
1672 | PrefetchRange(&c, &opt, &table_options, | |
1673 | /*key_range=*/"k01", "k05", | |
1674 | /*keys_in_cache=*/{"k01", "k02", "k03", "k04", "k05"}, | |
1675 | /*keys_not_in_cache=*/{"k06", "k07"}); | |
1676 | PrefetchRange(&c, &opt, &table_options, "k01", "k01", {"k01", "k02", "k03"}, | |
1677 | {"k04", "k05", "k06", "k07"}); | |
1678 | // odd | |
1679 | PrefetchRange(&c, &opt, &table_options, "a", "z", | |
1680 | {"k01", "k02", "k03", "k04", "k05", "k06", "k07"}, {}); | |
1681 | PrefetchRange(&c, &opt, &table_options, "k00", "k00", {"k01", "k02", "k03"}, | |
1682 | {"k04", "k05", "k06", "k07"}); | |
1683 | // Edge cases | |
1684 | PrefetchRange(&c, &opt, &table_options, "k00", "k06", | |
1685 | {"k01", "k02", "k03", "k04", "k05", "k06", "k07"}, {}); | |
1686 | PrefetchRange(&c, &opt, &table_options, "k00", "zzz", | |
1687 | {"k01", "k02", "k03", "k04", "k05", "k06", "k07"}, {}); | |
1688 | // null keys | |
1689 | PrefetchRange(&c, &opt, &table_options, nullptr, nullptr, | |
1690 | {"k01", "k02", "k03", "k04", "k05", "k06", "k07"}, {}); | |
1691 | PrefetchRange(&c, &opt, &table_options, "k04", nullptr, | |
1692 | {"k04", "k05", "k06", "k07"}, {"k01", "k02", "k03"}); | |
1693 | PrefetchRange(&c, &opt, &table_options, nullptr, "k05", | |
1694 | {"k01", "k02", "k03", "k04", "k05"}, {"k06", "k07"}); | |
1695 | // invalid | |
1696 | PrefetchRange(&c, &opt, &table_options, "k06", "k00", {}, {}, | |
1697 | Status::InvalidArgument(Slice("k06 "), Slice("k07"))); | |
1698 | c.ResetTableReader(); | |
1699 | } | |
1700 | ||
11fdf7f2 TL |
1701 | TEST_P(BlockBasedTableTest, TotalOrderSeekOnHashIndex) { |
1702 | BlockBasedTableOptions table_options = GetBlockBasedTableOptions(); | |
f67539c2 | 1703 | for (int i = 0; i <= 5; ++i) { |
7c673cae FG |
1704 | Options options; |
1705 | // Make each key/value an individual block | |
1706 | table_options.block_size = 64; | |
1707 | switch (i) { | |
1708 | case 0: | |
1709 | // Binary search index | |
1710 | table_options.index_type = BlockBasedTableOptions::kBinarySearch; | |
1711 | options.table_factory.reset(new BlockBasedTableFactory(table_options)); | |
1712 | break; | |
1713 | case 1: | |
1714 | // Hash search index | |
1715 | table_options.index_type = BlockBasedTableOptions::kHashSearch; | |
1716 | options.table_factory.reset(new BlockBasedTableFactory(table_options)); | |
1717 | options.prefix_extractor.reset(NewFixedPrefixTransform(4)); | |
1718 | break; | |
1719 | case 2: | |
1720 | // Hash search index with hash_index_allow_collision | |
1721 | table_options.index_type = BlockBasedTableOptions::kHashSearch; | |
1722 | table_options.hash_index_allow_collision = true; | |
1723 | options.table_factory.reset(new BlockBasedTableFactory(table_options)); | |
1724 | options.prefix_extractor.reset(NewFixedPrefixTransform(4)); | |
1725 | break; | |
1726 | case 3: | |
1727 | // Hash search index with filter policy | |
1728 | table_options.index_type = BlockBasedTableOptions::kHashSearch; | |
1729 | table_options.filter_policy.reset(NewBloomFilterPolicy(10)); | |
1730 | options.table_factory.reset(new BlockBasedTableFactory(table_options)); | |
1731 | options.prefix_extractor.reset(NewFixedPrefixTransform(4)); | |
1732 | break; | |
1733 | case 4: | |
f67539c2 | 1734 | // Two-level index |
7c673cae FG |
1735 | table_options.index_type = BlockBasedTableOptions::kTwoLevelIndexSearch; |
1736 | options.table_factory.reset(new BlockBasedTableFactory(table_options)); | |
1737 | break; | |
f67539c2 TL |
1738 | case 5: |
1739 | // Binary search with first key | |
1740 | table_options.index_type = | |
1741 | BlockBasedTableOptions::kBinarySearchWithFirstKey; | |
1742 | options.table_factory.reset(new BlockBasedTableFactory(table_options)); | |
1743 | break; | |
7c673cae FG |
1744 | } |
1745 | ||
1746 | TableConstructor c(BytewiseComparator(), | |
1747 | true /* convert_to_internal_key_ */); | |
1748 | c.Add("aaaa1", std::string('a', 56)); | |
1749 | c.Add("bbaa1", std::string('a', 56)); | |
1750 | c.Add("cccc1", std::string('a', 56)); | |
1751 | c.Add("bbbb1", std::string('a', 56)); | |
1752 | c.Add("baaa1", std::string('a', 56)); | |
1753 | c.Add("abbb1", std::string('a', 56)); | |
1754 | c.Add("cccc2", std::string('a', 56)); | |
1755 | std::vector<std::string> keys; | |
1756 | stl_wrappers::KVMap kvmap; | |
1757 | const ImmutableCFOptions ioptions(options); | |
11fdf7f2 TL |
1758 | const MutableCFOptions moptions(options); |
1759 | c.Finish(options, ioptions, moptions, table_options, | |
7c673cae FG |
1760 | GetPlainInternalComparator(options.comparator), &keys, &kvmap); |
1761 | auto props = c.GetTableReader()->GetTableProperties(); | |
1762 | ASSERT_EQ(7u, props->num_data_blocks); | |
1763 | auto* reader = c.GetTableReader(); | |
1764 | ReadOptions ro; | |
1765 | ro.total_order_seek = true; | |
f67539c2 TL |
1766 | std::unique_ptr<InternalIterator> iter(reader->NewIterator( |
1767 | ro, moptions.prefix_extractor.get(), /*arena=*/nullptr, | |
1768 | /*skip_filters=*/false, TableReaderCaller::kUncategorized)); | |
7c673cae FG |
1769 | |
1770 | iter->Seek(InternalKey("b", 0, kTypeValue).Encode()); | |
1771 | ASSERT_OK(iter->status()); | |
1772 | ASSERT_TRUE(iter->Valid()); | |
1773 | ASSERT_EQ("baaa1", ExtractUserKey(iter->key()).ToString()); | |
1774 | iter->Next(); | |
1775 | ASSERT_OK(iter->status()); | |
1776 | ASSERT_TRUE(iter->Valid()); | |
1777 | ASSERT_EQ("bbaa1", ExtractUserKey(iter->key()).ToString()); | |
1778 | ||
1779 | iter->Seek(InternalKey("bb", 0, kTypeValue).Encode()); | |
1780 | ASSERT_OK(iter->status()); | |
1781 | ASSERT_TRUE(iter->Valid()); | |
1782 | ASSERT_EQ("bbaa1", ExtractUserKey(iter->key()).ToString()); | |
1783 | iter->Next(); | |
1784 | ASSERT_OK(iter->status()); | |
1785 | ASSERT_TRUE(iter->Valid()); | |
1786 | ASSERT_EQ("bbbb1", ExtractUserKey(iter->key()).ToString()); | |
1787 | ||
1788 | iter->Seek(InternalKey("bbb", 0, kTypeValue).Encode()); | |
1789 | ASSERT_OK(iter->status()); | |
1790 | ASSERT_TRUE(iter->Valid()); | |
1791 | ASSERT_EQ("bbbb1", ExtractUserKey(iter->key()).ToString()); | |
1792 | iter->Next(); | |
1793 | ASSERT_OK(iter->status()); | |
1794 | ASSERT_TRUE(iter->Valid()); | |
1795 | ASSERT_EQ("cccc1", ExtractUserKey(iter->key()).ToString()); | |
1796 | } | |
1797 | } | |
1798 | ||
11fdf7f2 TL |
1799 | TEST_P(BlockBasedTableTest, NoopTransformSeek) { |
1800 | BlockBasedTableOptions table_options = GetBlockBasedTableOptions(); | |
7c673cae FG |
1801 | table_options.filter_policy.reset(NewBloomFilterPolicy(10)); |
1802 | ||
1803 | Options options; | |
1804 | options.comparator = BytewiseComparator(); | |
1805 | options.table_factory.reset(new BlockBasedTableFactory(table_options)); | |
1806 | options.prefix_extractor.reset(NewNoopTransform()); | |
1807 | ||
1808 | TableConstructor c(options.comparator); | |
1809 | // To tickle the PrefixMayMatch bug it is important that the | |
1810 | // user-key is a single byte so that the index key exactly matches | |
1811 | // the user-key. | |
1812 | InternalKey key("a", 1, kTypeValue); | |
1813 | c.Add(key.Encode().ToString(), "b"); | |
1814 | std::vector<std::string> keys; | |
1815 | stl_wrappers::KVMap kvmap; | |
1816 | const ImmutableCFOptions ioptions(options); | |
11fdf7f2 | 1817 | const MutableCFOptions moptions(options); |
7c673cae | 1818 | const InternalKeyComparator internal_comparator(options.comparator); |
11fdf7f2 TL |
1819 | c.Finish(options, ioptions, moptions, table_options, internal_comparator, |
1820 | &keys, &kvmap); | |
7c673cae FG |
1821 | |
1822 | auto* reader = c.GetTableReader(); | |
1823 | for (int i = 0; i < 2; ++i) { | |
1824 | ReadOptions ro; | |
1825 | ro.total_order_seek = (i == 0); | |
f67539c2 TL |
1826 | std::unique_ptr<InternalIterator> iter(reader->NewIterator( |
1827 | ro, moptions.prefix_extractor.get(), /*arena=*/nullptr, | |
1828 | /*skip_filters=*/false, TableReaderCaller::kUncategorized)); | |
7c673cae FG |
1829 | |
1830 | iter->Seek(key.Encode()); | |
1831 | ASSERT_OK(iter->status()); | |
1832 | ASSERT_TRUE(iter->Valid()); | |
1833 | ASSERT_EQ("a", ExtractUserKey(iter->key()).ToString()); | |
1834 | } | |
1835 | } | |
1836 | ||
11fdf7f2 | 1837 | TEST_P(BlockBasedTableTest, SkipPrefixBloomFilter) { |
7c673cae FG |
1838 | // if DB is opened with a prefix extractor of a different name, |
1839 | // prefix bloom is skipped when read the file | |
11fdf7f2 | 1840 | BlockBasedTableOptions table_options = GetBlockBasedTableOptions(); |
7c673cae FG |
1841 | table_options.filter_policy.reset(NewBloomFilterPolicy(2)); |
1842 | table_options.whole_key_filtering = false; | |
1843 | ||
1844 | Options options; | |
1845 | options.comparator = BytewiseComparator(); | |
1846 | options.table_factory.reset(new BlockBasedTableFactory(table_options)); | |
1847 | options.prefix_extractor.reset(NewFixedPrefixTransform(1)); | |
1848 | ||
1849 | TableConstructor c(options.comparator); | |
1850 | InternalKey key("abcdefghijk", 1, kTypeValue); | |
1851 | c.Add(key.Encode().ToString(), "test"); | |
1852 | std::vector<std::string> keys; | |
1853 | stl_wrappers::KVMap kvmap; | |
1854 | const ImmutableCFOptions ioptions(options); | |
11fdf7f2 | 1855 | const MutableCFOptions moptions(options); |
7c673cae | 1856 | const InternalKeyComparator internal_comparator(options.comparator); |
11fdf7f2 TL |
1857 | c.Finish(options, ioptions, moptions, table_options, internal_comparator, |
1858 | &keys, &kvmap); | |
1859 | // TODO(Zhongyi): update test to use MutableCFOptions | |
7c673cae FG |
1860 | options.prefix_extractor.reset(NewFixedPrefixTransform(9)); |
1861 | const ImmutableCFOptions new_ioptions(options); | |
11fdf7f2 TL |
1862 | const MutableCFOptions new_moptions(options); |
1863 | c.Reopen(new_ioptions, new_moptions); | |
7c673cae | 1864 | auto reader = c.GetTableReader(); |
f67539c2 TL |
1865 | std::unique_ptr<InternalIterator> db_iter(reader->NewIterator( |
1866 | ReadOptions(), new_moptions.prefix_extractor.get(), /*arena=*/nullptr, | |
1867 | /*skip_filters=*/false, TableReaderCaller::kUncategorized)); | |
7c673cae FG |
1868 | |
1869 | // Test point lookup | |
1870 | // only one kv | |
1871 | for (auto& kv : kvmap) { | |
1872 | db_iter->Seek(kv.first); | |
1873 | ASSERT_TRUE(db_iter->Valid()); | |
1874 | ASSERT_OK(db_iter->status()); | |
1875 | ASSERT_EQ(db_iter->key(), kv.first); | |
1876 | ASSERT_EQ(db_iter->value(), kv.second); | |
1877 | } | |
1878 | } | |
1879 | ||
1880 | static std::string RandomString(Random* rnd, int len) { | |
1881 | std::string r; | |
1882 | test::RandomString(rnd, len, &r); | |
1883 | return r; | |
1884 | } | |
1885 | ||
1886 | void AddInternalKey(TableConstructor* c, const std::string& prefix, | |
f67539c2 | 1887 | std::string value = "v", int /*suffix_len*/ = 800) { |
7c673cae FG |
1888 | static Random rnd(1023); |
1889 | InternalKey k(prefix + RandomString(&rnd, 800), 0, kTypeValue); | |
f67539c2 | 1890 | c->Add(k.Encode().ToString(), value); |
7c673cae FG |
1891 | } |
1892 | ||
1893 | void TableTest::IndexTest(BlockBasedTableOptions table_options) { | |
1894 | TableConstructor c(BytewiseComparator()); | |
1895 | ||
1896 | // keys with prefix length 3, make sure the key/value is big enough to fill | |
1897 | // one block | |
1898 | AddInternalKey(&c, "0015"); | |
1899 | AddInternalKey(&c, "0035"); | |
1900 | ||
1901 | AddInternalKey(&c, "0054"); | |
1902 | AddInternalKey(&c, "0055"); | |
1903 | ||
1904 | AddInternalKey(&c, "0056"); | |
1905 | AddInternalKey(&c, "0057"); | |
1906 | ||
1907 | AddInternalKey(&c, "0058"); | |
1908 | AddInternalKey(&c, "0075"); | |
1909 | ||
1910 | AddInternalKey(&c, "0076"); | |
1911 | AddInternalKey(&c, "0095"); | |
1912 | ||
1913 | std::vector<std::string> keys; | |
1914 | stl_wrappers::KVMap kvmap; | |
1915 | Options options; | |
1916 | options.prefix_extractor.reset(NewFixedPrefixTransform(3)); | |
1917 | table_options.block_size = 1700; | |
1918 | table_options.block_cache = NewLRUCache(1024, 4); | |
1919 | options.table_factory.reset(NewBlockBasedTableFactory(table_options)); | |
1920 | ||
1921 | std::unique_ptr<InternalKeyComparator> comparator( | |
1922 | new InternalKeyComparator(BytewiseComparator())); | |
1923 | const ImmutableCFOptions ioptions(options); | |
11fdf7f2 TL |
1924 | const MutableCFOptions moptions(options); |
1925 | c.Finish(options, ioptions, moptions, table_options, *comparator, &keys, | |
1926 | &kvmap); | |
7c673cae FG |
1927 | auto reader = c.GetTableReader(); |
1928 | ||
1929 | auto props = reader->GetTableProperties(); | |
1930 | ASSERT_EQ(5u, props->num_data_blocks); | |
1931 | ||
11fdf7f2 | 1932 | // TODO(Zhongyi): update test to use MutableCFOptions |
f67539c2 TL |
1933 | std::unique_ptr<InternalIterator> index_iter(reader->NewIterator( |
1934 | ReadOptions(), moptions.prefix_extractor.get(), /*arena=*/nullptr, | |
1935 | /*skip_filters=*/false, TableReaderCaller::kUncategorized)); | |
7c673cae FG |
1936 | |
1937 | // -- Find keys do not exist, but have common prefix. | |
1938 | std::vector<std::string> prefixes = {"001", "003", "005", "007", "009"}; | |
1939 | std::vector<std::string> lower_bound = {keys[0], keys[1], keys[2], | |
1940 | keys[7], keys[9], }; | |
1941 | ||
1942 | // find the lower bound of the prefix | |
1943 | for (size_t i = 0; i < prefixes.size(); ++i) { | |
1944 | index_iter->Seek(InternalKey(prefixes[i], 0, kTypeValue).Encode()); | |
1945 | ASSERT_OK(index_iter->status()); | |
1946 | ASSERT_TRUE(index_iter->Valid()); | |
1947 | ||
1948 | // seek the first element in the block | |
1949 | ASSERT_EQ(lower_bound[i], index_iter->key().ToString()); | |
1950 | ASSERT_EQ("v", index_iter->value().ToString()); | |
1951 | } | |
1952 | ||
1953 | // find the upper bound of prefixes | |
1954 | std::vector<std::string> upper_bound = {keys[1], keys[2], keys[7], keys[9], }; | |
1955 | ||
1956 | // find existing keys | |
1957 | for (const auto& item : kvmap) { | |
1958 | auto ukey = ExtractUserKey(item.first).ToString(); | |
1959 | index_iter->Seek(ukey); | |
1960 | ||
1961 | // ASSERT_OK(regular_iter->status()); | |
1962 | ASSERT_OK(index_iter->status()); | |
1963 | ||
1964 | // ASSERT_TRUE(regular_iter->Valid()); | |
1965 | ASSERT_TRUE(index_iter->Valid()); | |
1966 | ||
1967 | ASSERT_EQ(item.first, index_iter->key().ToString()); | |
1968 | ASSERT_EQ(item.second, index_iter->value().ToString()); | |
1969 | } | |
1970 | ||
1971 | for (size_t i = 0; i < prefixes.size(); ++i) { | |
1972 | // the key is greater than any existing keys. | |
1973 | auto key = prefixes[i] + "9"; | |
1974 | index_iter->Seek(InternalKey(key, 0, kTypeValue).Encode()); | |
1975 | ||
f67539c2 TL |
1976 | ASSERT_TRUE(index_iter->status().ok() || index_iter->status().IsNotFound()); |
1977 | ASSERT_TRUE(!index_iter->status().IsNotFound() || !index_iter->Valid()); | |
7c673cae FG |
1978 | if (i == prefixes.size() - 1) { |
1979 | // last key | |
1980 | ASSERT_TRUE(!index_iter->Valid()); | |
1981 | } else { | |
1982 | ASSERT_TRUE(index_iter->Valid()); | |
1983 | // seek the first element in the block | |
1984 | ASSERT_EQ(upper_bound[i], index_iter->key().ToString()); | |
1985 | ASSERT_EQ("v", index_iter->value().ToString()); | |
1986 | } | |
1987 | } | |
1988 | ||
1989 | // find keys with prefix that don't match any of the existing prefixes. | |
1990 | std::vector<std::string> non_exist_prefixes = {"002", "004", "006", "008"}; | |
1991 | for (const auto& prefix : non_exist_prefixes) { | |
1992 | index_iter->Seek(InternalKey(prefix, 0, kTypeValue).Encode()); | |
1993 | // regular_iter->Seek(prefix); | |
1994 | ||
1995 | ASSERT_OK(index_iter->status()); | |
1996 | // Seek to non-existing prefixes should yield either invalid, or a | |
1997 | // key with prefix greater than the target. | |
1998 | if (index_iter->Valid()) { | |
1999 | Slice ukey = ExtractUserKey(index_iter->key()); | |
2000 | Slice ukey_prefix = options.prefix_extractor->Transform(ukey); | |
2001 | ASSERT_TRUE(BytewiseComparator()->Compare(prefix, ukey_prefix) < 0); | |
2002 | } | |
2003 | } | |
f67539c2 TL |
2004 | for (const auto& prefix : non_exist_prefixes) { |
2005 | index_iter->SeekForPrev(InternalKey(prefix, 0, kTypeValue).Encode()); | |
2006 | // regular_iter->Seek(prefix); | |
2007 | ||
2008 | ASSERT_OK(index_iter->status()); | |
2009 | // Seek to non-existing prefixes should yield either invalid, or a | |
2010 | // key with prefix greater than the target. | |
2011 | if (index_iter->Valid()) { | |
2012 | Slice ukey = ExtractUserKey(index_iter->key()); | |
2013 | Slice ukey_prefix = options.prefix_extractor->Transform(ukey); | |
2014 | ASSERT_TRUE(BytewiseComparator()->Compare(prefix, ukey_prefix) > 0); | |
2015 | } | |
2016 | } | |
7c673cae FG |
2017 | c.ResetTableReader(); |
2018 | } | |
2019 | ||
11fdf7f2 TL |
2020 | TEST_P(BlockBasedTableTest, BinaryIndexTest) { |
2021 | BlockBasedTableOptions table_options = GetBlockBasedTableOptions(); | |
7c673cae FG |
2022 | table_options.index_type = BlockBasedTableOptions::kBinarySearch; |
2023 | IndexTest(table_options); | |
2024 | } | |
2025 | ||
11fdf7f2 TL |
2026 | TEST_P(BlockBasedTableTest, HashIndexTest) { |
2027 | BlockBasedTableOptions table_options = GetBlockBasedTableOptions(); | |
7c673cae FG |
2028 | table_options.index_type = BlockBasedTableOptions::kHashSearch; |
2029 | IndexTest(table_options); | |
2030 | } | |
2031 | ||
11fdf7f2 | 2032 | TEST_P(BlockBasedTableTest, PartitionIndexTest) { |
7c673cae FG |
2033 | const int max_index_keys = 5; |
2034 | const int est_max_index_key_value_size = 32; | |
2035 | const int est_max_index_size = max_index_keys * est_max_index_key_value_size; | |
2036 | for (int i = 1; i <= est_max_index_size + 1; i++) { | |
11fdf7f2 | 2037 | BlockBasedTableOptions table_options = GetBlockBasedTableOptions(); |
7c673cae FG |
2038 | table_options.index_type = BlockBasedTableOptions::kTwoLevelIndexSearch; |
2039 | table_options.metadata_block_size = i; | |
2040 | IndexTest(table_options); | |
2041 | } | |
2042 | } | |
2043 | ||
f67539c2 TL |
2044 | TEST_P(BlockBasedTableTest, IndexSeekOptimizationIncomplete) { |
2045 | std::unique_ptr<InternalKeyComparator> comparator( | |
2046 | new InternalKeyComparator(BytewiseComparator())); | |
2047 | BlockBasedTableOptions table_options = GetBlockBasedTableOptions(); | |
2048 | Options options; | |
2049 | options.table_factory.reset(NewBlockBasedTableFactory(table_options)); | |
2050 | const ImmutableCFOptions ioptions(options); | |
2051 | const MutableCFOptions moptions(options); | |
2052 | ||
2053 | TableConstructor c(BytewiseComparator()); | |
2054 | AddInternalKey(&c, "pika"); | |
2055 | ||
2056 | std::vector<std::string> keys; | |
2057 | stl_wrappers::KVMap kvmap; | |
2058 | c.Finish(options, ioptions, moptions, table_options, *comparator, &keys, | |
2059 | &kvmap); | |
2060 | ASSERT_EQ(1, keys.size()); | |
2061 | ||
2062 | auto reader = c.GetTableReader(); | |
2063 | ReadOptions ropt; | |
2064 | ropt.read_tier = ReadTier::kBlockCacheTier; | |
2065 | std::unique_ptr<InternalIterator> iter(reader->NewIterator( | |
2066 | ropt, /*prefix_extractor=*/nullptr, /*arena=*/nullptr, | |
2067 | /*skip_filters=*/false, TableReaderCaller::kUncategorized)); | |
2068 | ||
2069 | auto ikey = [](Slice user_key) { | |
2070 | return InternalKey(user_key, 0, kTypeValue).Encode().ToString(); | |
2071 | }; | |
2072 | ||
2073 | iter->Seek(ikey("pika")); | |
2074 | ASSERT_FALSE(iter->Valid()); | |
2075 | ASSERT_TRUE(iter->status().IsIncomplete()); | |
2076 | ||
2077 | // This used to crash at some point. | |
2078 | iter->Seek(ikey("pika")); | |
2079 | ASSERT_FALSE(iter->Valid()); | |
2080 | ASSERT_TRUE(iter->status().IsIncomplete()); | |
2081 | } | |
2082 | ||
2083 | TEST_P(BlockBasedTableTest, BinaryIndexWithFirstKey1) { | |
2084 | BlockBasedTableOptions table_options = GetBlockBasedTableOptions(); | |
2085 | table_options.index_type = BlockBasedTableOptions::kBinarySearchWithFirstKey; | |
2086 | IndexTest(table_options); | |
2087 | } | |
2088 | ||
2089 | class CustomFlushBlockPolicy : public FlushBlockPolicyFactory, | |
2090 | public FlushBlockPolicy { | |
2091 | public: | |
2092 | explicit CustomFlushBlockPolicy(std::vector<int> keys_per_block) | |
2093 | : keys_per_block_(keys_per_block) {} | |
2094 | ||
2095 | const char* Name() const override { return "table_test"; } | |
2096 | FlushBlockPolicy* NewFlushBlockPolicy(const BlockBasedTableOptions&, | |
2097 | const BlockBuilder&) const override { | |
2098 | return new CustomFlushBlockPolicy(keys_per_block_); | |
2099 | } | |
2100 | ||
2101 | bool Update(const Slice&, const Slice&) override { | |
2102 | if (keys_in_current_block_ >= keys_per_block_.at(current_block_idx_)) { | |
2103 | ++current_block_idx_; | |
2104 | keys_in_current_block_ = 1; | |
2105 | return true; | |
2106 | } | |
2107 | ||
2108 | ++keys_in_current_block_; | |
2109 | return false; | |
2110 | } | |
2111 | ||
2112 | std::vector<int> keys_per_block_; | |
2113 | ||
2114 | int current_block_idx_ = 0; | |
2115 | int keys_in_current_block_ = 0; | |
2116 | }; | |
2117 | ||
2118 | TEST_P(BlockBasedTableTest, BinaryIndexWithFirstKey2) { | |
2119 | for (int use_first_key = 0; use_first_key < 2; ++use_first_key) { | |
2120 | SCOPED_TRACE("use_first_key = " + std::to_string(use_first_key)); | |
2121 | BlockBasedTableOptions table_options = GetBlockBasedTableOptions(); | |
2122 | table_options.index_type = | |
2123 | use_first_key ? BlockBasedTableOptions::kBinarySearchWithFirstKey | |
2124 | : BlockBasedTableOptions::kBinarySearch; | |
2125 | table_options.block_cache = NewLRUCache(10000); // fits all blocks | |
2126 | table_options.index_shortening = | |
2127 | BlockBasedTableOptions::IndexShorteningMode::kNoShortening; | |
2128 | table_options.flush_block_policy_factory = | |
2129 | std::make_shared<CustomFlushBlockPolicy>(std::vector<int>{2, 1, 3, 2}); | |
2130 | Options options; | |
2131 | options.table_factory.reset(NewBlockBasedTableFactory(table_options)); | |
2132 | options.statistics = CreateDBStatistics(); | |
2133 | Statistics* stats = options.statistics.get(); | |
2134 | std::unique_ptr<InternalKeyComparator> comparator( | |
2135 | new InternalKeyComparator(BytewiseComparator())); | |
2136 | const ImmutableCFOptions ioptions(options); | |
2137 | const MutableCFOptions moptions(options); | |
2138 | ||
2139 | TableConstructor c(BytewiseComparator()); | |
2140 | ||
2141 | // Block 0. | |
2142 | AddInternalKey(&c, "aaaa", "v0"); | |
2143 | AddInternalKey(&c, "aaac", "v1"); | |
2144 | ||
2145 | // Block 1. | |
2146 | AddInternalKey(&c, "aaca", "v2"); | |
2147 | ||
2148 | // Block 2. | |
2149 | AddInternalKey(&c, "caaa", "v3"); | |
2150 | AddInternalKey(&c, "caac", "v4"); | |
2151 | AddInternalKey(&c, "caae", "v5"); | |
2152 | ||
2153 | // Block 3. | |
2154 | AddInternalKey(&c, "ccaa", "v6"); | |
2155 | AddInternalKey(&c, "ccac", "v7"); | |
2156 | ||
2157 | // Write the file. | |
2158 | std::vector<std::string> keys; | |
2159 | stl_wrappers::KVMap kvmap; | |
2160 | c.Finish(options, ioptions, moptions, table_options, *comparator, &keys, | |
2161 | &kvmap); | |
2162 | ASSERT_EQ(8, keys.size()); | |
2163 | ||
2164 | auto reader = c.GetTableReader(); | |
2165 | auto props = reader->GetTableProperties(); | |
2166 | ASSERT_EQ(4u, props->num_data_blocks); | |
2167 | std::unique_ptr<InternalIterator> iter(reader->NewIterator( | |
2168 | ReadOptions(), /*prefix_extractor=*/nullptr, /*arena=*/nullptr, | |
2169 | /*skip_filters=*/false, TableReaderCaller::kUncategorized)); | |
2170 | ||
2171 | // Shouldn't have read data blocks before iterator is seeked. | |
2172 | EXPECT_EQ(0, stats->getTickerCount(BLOCK_CACHE_DATA_MISS)); | |
2173 | EXPECT_EQ(0, stats->getTickerCount(BLOCK_CACHE_DATA_HIT)); | |
2174 | ||
2175 | auto ikey = [](Slice user_key) { | |
2176 | return InternalKey(user_key, 0, kTypeValue).Encode().ToString(); | |
2177 | }; | |
2178 | ||
2179 | // Seek to a key between blocks. If index contains first key, we shouldn't | |
2180 | // read any data blocks until value is requested. | |
2181 | iter->Seek(ikey("aaba")); | |
2182 | ASSERT_TRUE(iter->Valid()); | |
2183 | EXPECT_EQ(keys[2], iter->key().ToString()); | |
2184 | EXPECT_EQ(use_first_key ? 0 : 1, | |
2185 | stats->getTickerCount(BLOCK_CACHE_DATA_MISS)); | |
2186 | EXPECT_EQ("v2", iter->value().ToString()); | |
2187 | EXPECT_EQ(1, stats->getTickerCount(BLOCK_CACHE_DATA_MISS)); | |
2188 | EXPECT_EQ(0, stats->getTickerCount(BLOCK_CACHE_DATA_HIT)); | |
2189 | ||
2190 | // Seek to the middle of a block. The block should be read right away. | |
2191 | iter->Seek(ikey("caab")); | |
2192 | ASSERT_TRUE(iter->Valid()); | |
2193 | EXPECT_EQ(keys[4], iter->key().ToString()); | |
2194 | EXPECT_EQ(2, stats->getTickerCount(BLOCK_CACHE_DATA_MISS)); | |
2195 | EXPECT_EQ(0, stats->getTickerCount(BLOCK_CACHE_DATA_HIT)); | |
2196 | EXPECT_EQ("v4", iter->value().ToString()); | |
2197 | EXPECT_EQ(0, stats->getTickerCount(BLOCK_CACHE_DATA_HIT)); | |
2198 | ||
2199 | // Seek to just before the same block and don't access value. | |
2200 | // The iterator should keep pinning the block contents. | |
2201 | iter->Seek(ikey("baaa")); | |
2202 | ASSERT_TRUE(iter->Valid()); | |
2203 | EXPECT_EQ(keys[3], iter->key().ToString()); | |
2204 | EXPECT_EQ(0, stats->getTickerCount(BLOCK_CACHE_DATA_HIT)); | |
2205 | ||
2206 | // Seek to the same block again to check that the block is still pinned. | |
2207 | iter->Seek(ikey("caae")); | |
2208 | ASSERT_TRUE(iter->Valid()); | |
2209 | EXPECT_EQ(keys[5], iter->key().ToString()); | |
2210 | EXPECT_EQ(0, stats->getTickerCount(BLOCK_CACHE_DATA_HIT)); | |
2211 | EXPECT_EQ("v5", iter->value().ToString()); | |
2212 | EXPECT_EQ(2, stats->getTickerCount(BLOCK_CACHE_DATA_MISS)); | |
2213 | EXPECT_EQ(0, stats->getTickerCount(BLOCK_CACHE_DATA_HIT)); | |
2214 | ||
2215 | // Step forward and fall through to the next block. Don't access value. | |
2216 | iter->Next(); | |
2217 | ASSERT_TRUE(iter->Valid()); | |
2218 | EXPECT_EQ(keys[6], iter->key().ToString()); | |
2219 | EXPECT_EQ(use_first_key ? 2 : 3, | |
2220 | stats->getTickerCount(BLOCK_CACHE_DATA_MISS)); | |
2221 | EXPECT_EQ(0, stats->getTickerCount(BLOCK_CACHE_DATA_HIT)); | |
2222 | ||
2223 | // Step forward again. Block should be read. | |
2224 | iter->Next(); | |
2225 | ASSERT_TRUE(iter->Valid()); | |
2226 | EXPECT_EQ(keys[7], iter->key().ToString()); | |
2227 | EXPECT_EQ(3, stats->getTickerCount(BLOCK_CACHE_DATA_MISS)); | |
2228 | EXPECT_EQ("v7", iter->value().ToString()); | |
2229 | EXPECT_EQ(0, stats->getTickerCount(BLOCK_CACHE_DATA_HIT)); | |
2230 | ||
2231 | // Step forward and reach the end. | |
2232 | iter->Next(); | |
2233 | EXPECT_FALSE(iter->Valid()); | |
2234 | EXPECT_EQ(3, stats->getTickerCount(BLOCK_CACHE_DATA_MISS)); | |
2235 | EXPECT_EQ(0, stats->getTickerCount(BLOCK_CACHE_DATA_HIT)); | |
2236 | ||
2237 | // Seek to a single-key block and step forward without accessing value. | |
2238 | iter->Seek(ikey("aaca")); | |
2239 | ASSERT_TRUE(iter->Valid()); | |
2240 | EXPECT_EQ(keys[2], iter->key().ToString()); | |
2241 | EXPECT_EQ(use_first_key ? 0 : 1, | |
2242 | stats->getTickerCount(BLOCK_CACHE_DATA_HIT)); | |
2243 | ||
2244 | iter->Next(); | |
2245 | ASSERT_TRUE(iter->Valid()); | |
2246 | EXPECT_EQ(keys[3], iter->key().ToString()); | |
2247 | EXPECT_EQ(use_first_key ? 1 : 2, | |
2248 | stats->getTickerCount(BLOCK_CACHE_DATA_HIT)); | |
2249 | EXPECT_EQ("v3", iter->value().ToString()); | |
2250 | EXPECT_EQ(2, stats->getTickerCount(BLOCK_CACHE_DATA_HIT)); | |
2251 | EXPECT_EQ(3, stats->getTickerCount(BLOCK_CACHE_DATA_MISS)); | |
2252 | ||
2253 | // Seek between blocks and step back without accessing value. | |
2254 | iter->Seek(ikey("aaca")); | |
2255 | ASSERT_TRUE(iter->Valid()); | |
2256 | EXPECT_EQ(keys[2], iter->key().ToString()); | |
2257 | EXPECT_EQ(use_first_key ? 2 : 3, | |
2258 | stats->getTickerCount(BLOCK_CACHE_DATA_HIT)); | |
2259 | EXPECT_EQ(3, stats->getTickerCount(BLOCK_CACHE_DATA_MISS)); | |
2260 | ||
2261 | iter->Prev(); | |
2262 | ASSERT_TRUE(iter->Valid()); | |
2263 | EXPECT_EQ(keys[1], iter->key().ToString()); | |
2264 | EXPECT_EQ(use_first_key ? 2 : 3, | |
2265 | stats->getTickerCount(BLOCK_CACHE_DATA_HIT)); | |
2266 | // All blocks are in cache now, there'll be no more misses ever. | |
2267 | EXPECT_EQ(4, stats->getTickerCount(BLOCK_CACHE_DATA_MISS)); | |
2268 | EXPECT_EQ("v1", iter->value().ToString()); | |
2269 | ||
2270 | // Next into the next block again. | |
2271 | iter->Next(); | |
2272 | ASSERT_TRUE(iter->Valid()); | |
2273 | EXPECT_EQ(keys[2], iter->key().ToString()); | |
2274 | EXPECT_EQ(use_first_key ? 2 : 4, | |
2275 | stats->getTickerCount(BLOCK_CACHE_DATA_HIT)); | |
2276 | ||
2277 | // Seek to first and step back without accessing value. | |
2278 | iter->SeekToFirst(); | |
2279 | ASSERT_TRUE(iter->Valid()); | |
2280 | EXPECT_EQ(keys[0], iter->key().ToString()); | |
2281 | EXPECT_EQ(use_first_key ? 2 : 5, | |
2282 | stats->getTickerCount(BLOCK_CACHE_DATA_HIT)); | |
2283 | ||
2284 | iter->Prev(); | |
2285 | EXPECT_FALSE(iter->Valid()); | |
2286 | EXPECT_EQ(use_first_key ? 2 : 5, | |
2287 | stats->getTickerCount(BLOCK_CACHE_DATA_HIT)); | |
2288 | ||
2289 | // Do some SeekForPrev() and SeekToLast() just to cover all methods. | |
2290 | iter->SeekForPrev(ikey("caad")); | |
2291 | ASSERT_TRUE(iter->Valid()); | |
2292 | EXPECT_EQ(keys[4], iter->key().ToString()); | |
2293 | EXPECT_EQ(use_first_key ? 3 : 6, | |
2294 | stats->getTickerCount(BLOCK_CACHE_DATA_HIT)); | |
2295 | EXPECT_EQ("v4", iter->value().ToString()); | |
2296 | EXPECT_EQ(use_first_key ? 3 : 6, | |
2297 | stats->getTickerCount(BLOCK_CACHE_DATA_HIT)); | |
2298 | ||
2299 | iter->SeekToLast(); | |
2300 | ASSERT_TRUE(iter->Valid()); | |
2301 | EXPECT_EQ(keys[7], iter->key().ToString()); | |
2302 | EXPECT_EQ(use_first_key ? 4 : 7, | |
2303 | stats->getTickerCount(BLOCK_CACHE_DATA_HIT)); | |
2304 | EXPECT_EQ("v7", iter->value().ToString()); | |
2305 | EXPECT_EQ(use_first_key ? 4 : 7, | |
2306 | stats->getTickerCount(BLOCK_CACHE_DATA_HIT)); | |
2307 | ||
2308 | EXPECT_EQ(4, stats->getTickerCount(BLOCK_CACHE_DATA_MISS)); | |
2309 | ||
2310 | c.ResetTableReader(); | |
2311 | } | |
2312 | } | |
2313 | ||
2314 | TEST_P(BlockBasedTableTest, BinaryIndexWithFirstKeyGlobalSeqno) { | |
2315 | BlockBasedTableOptions table_options = GetBlockBasedTableOptions(); | |
2316 | table_options.index_type = BlockBasedTableOptions::kBinarySearchWithFirstKey; | |
2317 | table_options.block_cache = NewLRUCache(10000); | |
2318 | Options options; | |
2319 | options.statistics = CreateDBStatistics(); | |
2320 | Statistics* stats = options.statistics.get(); | |
2321 | options.table_factory.reset(NewBlockBasedTableFactory(table_options)); | |
2322 | std::unique_ptr<InternalKeyComparator> comparator( | |
2323 | new InternalKeyComparator(BytewiseComparator())); | |
2324 | const ImmutableCFOptions ioptions(options); | |
2325 | const MutableCFOptions moptions(options); | |
2326 | ||
2327 | TableConstructor c(BytewiseComparator(), /* convert_to_internal_key */ false, | |
2328 | /* level */ -1, /* largest_seqno */ 42); | |
2329 | ||
2330 | c.Add(InternalKey("b", 0, kTypeValue).Encode().ToString(), "x"); | |
2331 | c.Add(InternalKey("c", 0, kTypeValue).Encode().ToString(), "y"); | |
2332 | ||
2333 | std::vector<std::string> keys; | |
2334 | stl_wrappers::KVMap kvmap; | |
2335 | c.Finish(options, ioptions, moptions, table_options, *comparator, &keys, | |
2336 | &kvmap); | |
2337 | ASSERT_EQ(2, keys.size()); | |
2338 | ||
2339 | auto reader = c.GetTableReader(); | |
2340 | auto props = reader->GetTableProperties(); | |
2341 | ASSERT_EQ(1u, props->num_data_blocks); | |
2342 | std::unique_ptr<InternalIterator> iter(reader->NewIterator( | |
2343 | ReadOptions(), /*prefix_extractor=*/nullptr, /*arena=*/nullptr, | |
2344 | /*skip_filters=*/false, TableReaderCaller::kUncategorized)); | |
2345 | ||
2346 | iter->Seek(InternalKey("a", 0, kTypeValue).Encode().ToString()); | |
2347 | ASSERT_TRUE(iter->Valid()); | |
2348 | EXPECT_EQ(InternalKey("b", 42, kTypeValue).Encode().ToString(), | |
2349 | iter->key().ToString()); | |
2350 | EXPECT_NE(keys[0], iter->key().ToString()); | |
2351 | // Key should have been served from index, without reading data blocks. | |
2352 | EXPECT_EQ(0, stats->getTickerCount(BLOCK_CACHE_DATA_MISS)); | |
2353 | ||
2354 | EXPECT_EQ("x", iter->value().ToString()); | |
2355 | EXPECT_EQ(1, stats->getTickerCount(BLOCK_CACHE_DATA_MISS)); | |
2356 | EXPECT_EQ(0, stats->getTickerCount(BLOCK_CACHE_DATA_HIT)); | |
2357 | EXPECT_EQ(InternalKey("b", 42, kTypeValue).Encode().ToString(), | |
2358 | iter->key().ToString()); | |
2359 | ||
2360 | c.ResetTableReader(); | |
2361 | } | |
2362 | ||
7c673cae FG |
2363 | // It's very hard to figure out the index block size of a block accurately. |
2364 | // To make sure we get the index size, we just make sure as key number | |
2365 | // grows, the filter block size also grows. | |
11fdf7f2 | 2366 | TEST_P(BlockBasedTableTest, IndexSizeStat) { |
7c673cae FG |
2367 | uint64_t last_index_size = 0; |
2368 | ||
2369 | // we need to use random keys since the pure human readable texts | |
2370 | // may be well compressed, resulting insignifcant change of index | |
2371 | // block size. | |
2372 | Random rnd(test::RandomSeed()); | |
2373 | std::vector<std::string> keys; | |
2374 | ||
2375 | for (int i = 0; i < 100; ++i) { | |
2376 | keys.push_back(RandomString(&rnd, 10000)); | |
2377 | } | |
2378 | ||
2379 | // Each time we load one more key to the table. the table index block | |
2380 | // size is expected to be larger than last time's. | |
2381 | for (size_t i = 1; i < keys.size(); ++i) { | |
2382 | TableConstructor c(BytewiseComparator(), | |
2383 | true /* convert_to_internal_key_ */); | |
2384 | for (size_t j = 0; j < i; ++j) { | |
2385 | c.Add(keys[j], "val"); | |
2386 | } | |
2387 | ||
2388 | std::vector<std::string> ks; | |
2389 | stl_wrappers::KVMap kvmap; | |
2390 | Options options; | |
2391 | options.compression = kNoCompression; | |
11fdf7f2 | 2392 | BlockBasedTableOptions table_options = GetBlockBasedTableOptions(); |
7c673cae FG |
2393 | table_options.block_restart_interval = 1; |
2394 | options.table_factory.reset(NewBlockBasedTableFactory(table_options)); | |
2395 | ||
2396 | const ImmutableCFOptions ioptions(options); | |
11fdf7f2 TL |
2397 | const MutableCFOptions moptions(options); |
2398 | c.Finish(options, ioptions, moptions, table_options, | |
7c673cae FG |
2399 | GetPlainInternalComparator(options.comparator), &ks, &kvmap); |
2400 | auto index_size = c.GetTableReader()->GetTableProperties()->index_size; | |
2401 | ASSERT_GT(index_size, last_index_size); | |
2402 | last_index_size = index_size; | |
2403 | c.ResetTableReader(); | |
2404 | } | |
2405 | } | |
2406 | ||
11fdf7f2 | 2407 | TEST_P(BlockBasedTableTest, NumBlockStat) { |
7c673cae FG |
2408 | Random rnd(test::RandomSeed()); |
2409 | TableConstructor c(BytewiseComparator(), true /* convert_to_internal_key_ */); | |
2410 | Options options; | |
2411 | options.compression = kNoCompression; | |
11fdf7f2 | 2412 | BlockBasedTableOptions table_options = GetBlockBasedTableOptions(); |
7c673cae FG |
2413 | table_options.block_restart_interval = 1; |
2414 | table_options.block_size = 1000; | |
2415 | options.table_factory.reset(NewBlockBasedTableFactory(table_options)); | |
2416 | ||
2417 | for (int i = 0; i < 10; ++i) { | |
2418 | // the key/val are slightly smaller than block size, so that each block | |
2419 | // holds roughly one key/value pair. | |
2420 | c.Add(RandomString(&rnd, 900), "val"); | |
2421 | } | |
2422 | ||
2423 | std::vector<std::string> ks; | |
2424 | stl_wrappers::KVMap kvmap; | |
2425 | const ImmutableCFOptions ioptions(options); | |
11fdf7f2 TL |
2426 | const MutableCFOptions moptions(options); |
2427 | c.Finish(options, ioptions, moptions, table_options, | |
7c673cae FG |
2428 | GetPlainInternalComparator(options.comparator), &ks, &kvmap); |
2429 | ASSERT_EQ(kvmap.size(), | |
2430 | c.GetTableReader()->GetTableProperties()->num_data_blocks); | |
2431 | c.ResetTableReader(); | |
2432 | } | |
2433 | ||
f67539c2 TL |
2434 | TEST_P(BlockBasedTableTest, TracingGetTest) { |
2435 | TableConstructor c(BytewiseComparator()); | |
2436 | Options options; | |
2437 | BlockBasedTableOptions table_options = GetBlockBasedTableOptions(); | |
2438 | options.create_if_missing = true; | |
2439 | table_options.block_cache = NewLRUCache(1024 * 1024, 0); | |
2440 | table_options.cache_index_and_filter_blocks = true; | |
2441 | table_options.filter_policy.reset(NewBloomFilterPolicy(10, true)); | |
2442 | options.table_factory.reset(new BlockBasedTableFactory(table_options)); | |
2443 | SetupTracingTest(&c); | |
2444 | std::vector<std::string> keys; | |
2445 | stl_wrappers::KVMap kvmap; | |
2446 | ImmutableCFOptions ioptions(options); | |
2447 | MutableCFOptions moptions(options); | |
2448 | c.Finish(options, ioptions, moptions, table_options, | |
2449 | GetPlainInternalComparator(options.comparator), &keys, &kvmap); | |
2450 | std::string user_key = "k01"; | |
2451 | InternalKey internal_key(user_key, 0, kTypeValue); | |
2452 | std::string encoded_key = internal_key.Encode().ToString(); | |
2453 | for (uint32_t i = 1; i <= 2; i++) { | |
2454 | PinnableSlice value; | |
2455 | GetContext get_context(options.comparator, nullptr, nullptr, nullptr, | |
2456 | GetContext::kNotFound, user_key, &value, nullptr, | |
2457 | nullptr, true, nullptr, nullptr, nullptr, nullptr, | |
2458 | nullptr, nullptr, /*tracing_get_id=*/i); | |
2459 | get_perf_context()->Reset(); | |
2460 | ASSERT_OK(c.GetTableReader()->Get(ReadOptions(), encoded_key, &get_context, | |
2461 | moptions.prefix_extractor.get())); | |
2462 | ASSERT_EQ(get_context.State(), GetContext::kFound); | |
2463 | ASSERT_EQ(value.ToString(), kDummyValue); | |
2464 | } | |
2465 | ||
2466 | // Verify traces. | |
2467 | std::vector<BlockCacheTraceRecord> expected_records; | |
2468 | // The first two records should be prefetching index and filter blocks. | |
2469 | BlockCacheTraceRecord record; | |
2470 | record.block_type = TraceType::kBlockTraceIndexBlock; | |
2471 | record.caller = TableReaderCaller::kPrefetch; | |
2472 | record.is_cache_hit = Boolean::kFalse; | |
2473 | record.no_insert = Boolean::kFalse; | |
2474 | expected_records.push_back(record); | |
2475 | record.block_type = TraceType::kBlockTraceFilterBlock; | |
2476 | expected_records.push_back(record); | |
2477 | // Then we should have three records for one index, one filter, and one data | |
2478 | // block access. | |
2479 | record.get_id = 1; | |
2480 | record.block_type = TraceType::kBlockTraceIndexBlock; | |
2481 | record.caller = TableReaderCaller::kUserGet; | |
2482 | record.get_from_user_specified_snapshot = Boolean::kFalse; | |
2483 | record.referenced_key = encoded_key; | |
2484 | record.referenced_key_exist_in_block = Boolean::kTrue; | |
2485 | record.is_cache_hit = Boolean::kTrue; | |
2486 | expected_records.push_back(record); | |
2487 | record.block_type = TraceType::kBlockTraceFilterBlock; | |
2488 | expected_records.push_back(record); | |
2489 | record.is_cache_hit = Boolean::kFalse; | |
2490 | record.block_type = TraceType::kBlockTraceDataBlock; | |
2491 | expected_records.push_back(record); | |
2492 | // The second get should all observe cache hits. | |
2493 | record.is_cache_hit = Boolean::kTrue; | |
2494 | record.get_id = 2; | |
2495 | record.block_type = TraceType::kBlockTraceIndexBlock; | |
2496 | record.caller = TableReaderCaller::kUserGet; | |
2497 | record.get_from_user_specified_snapshot = Boolean::kFalse; | |
2498 | record.referenced_key = encoded_key; | |
2499 | expected_records.push_back(record); | |
2500 | record.block_type = TraceType::kBlockTraceFilterBlock; | |
2501 | expected_records.push_back(record); | |
2502 | record.block_type = TraceType::kBlockTraceDataBlock; | |
2503 | expected_records.push_back(record); | |
2504 | VerifyBlockAccessTrace(&c, expected_records); | |
2505 | c.ResetTableReader(); | |
2506 | } | |
2507 | ||
2508 | TEST_P(BlockBasedTableTest, TracingApproximateOffsetOfTest) { | |
2509 | TableConstructor c(BytewiseComparator()); | |
2510 | Options options; | |
2511 | BlockBasedTableOptions table_options = GetBlockBasedTableOptions(); | |
2512 | options.create_if_missing = true; | |
2513 | table_options.block_cache = NewLRUCache(1024 * 1024, 0); | |
2514 | table_options.cache_index_and_filter_blocks = true; | |
2515 | table_options.filter_policy.reset(NewBloomFilterPolicy(10, true)); | |
2516 | options.table_factory.reset(new BlockBasedTableFactory(table_options)); | |
2517 | SetupTracingTest(&c); | |
2518 | std::vector<std::string> keys; | |
2519 | stl_wrappers::KVMap kvmap; | |
2520 | ImmutableCFOptions ioptions(options); | |
2521 | MutableCFOptions moptions(options); | |
2522 | c.Finish(options, ioptions, moptions, table_options, | |
2523 | GetPlainInternalComparator(options.comparator), &keys, &kvmap); | |
2524 | for (uint32_t i = 1; i <= 2; i++) { | |
2525 | std::string user_key = "k01"; | |
2526 | InternalKey internal_key(user_key, 0, kTypeValue); | |
2527 | std::string encoded_key = internal_key.Encode().ToString(); | |
2528 | c.GetTableReader()->ApproximateOffsetOf( | |
2529 | encoded_key, TableReaderCaller::kUserApproximateSize); | |
2530 | } | |
2531 | // Verify traces. | |
2532 | std::vector<BlockCacheTraceRecord> expected_records; | |
2533 | // The first two records should be prefetching index and filter blocks. | |
2534 | BlockCacheTraceRecord record; | |
2535 | record.block_type = TraceType::kBlockTraceIndexBlock; | |
2536 | record.caller = TableReaderCaller::kPrefetch; | |
2537 | record.is_cache_hit = Boolean::kFalse; | |
2538 | record.no_insert = Boolean::kFalse; | |
2539 | expected_records.push_back(record); | |
2540 | record.block_type = TraceType::kBlockTraceFilterBlock; | |
2541 | expected_records.push_back(record); | |
2542 | // Then we should have two records for only index blocks. | |
2543 | record.block_type = TraceType::kBlockTraceIndexBlock; | |
2544 | record.caller = TableReaderCaller::kUserApproximateSize; | |
2545 | record.is_cache_hit = Boolean::kTrue; | |
2546 | expected_records.push_back(record); | |
2547 | expected_records.push_back(record); | |
2548 | VerifyBlockAccessTrace(&c, expected_records); | |
2549 | c.ResetTableReader(); | |
2550 | } | |
2551 | ||
2552 | TEST_P(BlockBasedTableTest, TracingIterator) { | |
2553 | TableConstructor c(BytewiseComparator()); | |
2554 | Options options; | |
2555 | BlockBasedTableOptions table_options = GetBlockBasedTableOptions(); | |
2556 | options.create_if_missing = true; | |
2557 | table_options.block_cache = NewLRUCache(1024 * 1024, 0); | |
2558 | table_options.cache_index_and_filter_blocks = true; | |
2559 | table_options.filter_policy.reset(NewBloomFilterPolicy(10, true)); | |
2560 | options.table_factory.reset(new BlockBasedTableFactory(table_options)); | |
2561 | SetupTracingTest(&c); | |
2562 | std::vector<std::string> keys; | |
2563 | stl_wrappers::KVMap kvmap; | |
2564 | ImmutableCFOptions ioptions(options); | |
2565 | MutableCFOptions moptions(options); | |
2566 | c.Finish(options, ioptions, moptions, table_options, | |
2567 | GetPlainInternalComparator(options.comparator), &keys, &kvmap); | |
2568 | ||
2569 | for (uint32_t i = 1; i <= 2; i++) { | |
2570 | std::unique_ptr<InternalIterator> iter(c.GetTableReader()->NewIterator( | |
2571 | ReadOptions(), moptions.prefix_extractor.get(), /*arena=*/nullptr, | |
2572 | /*skip_filters=*/false, TableReaderCaller::kUserIterator)); | |
2573 | iter->SeekToFirst(); | |
2574 | while (iter->Valid()) { | |
2575 | iter->key(); | |
2576 | iter->value(); | |
2577 | iter->Next(); | |
2578 | } | |
2579 | ASSERT_OK(iter->status()); | |
2580 | iter.reset(); | |
2581 | } | |
2582 | ||
2583 | // Verify traces. | |
2584 | std::vector<BlockCacheTraceRecord> expected_records; | |
2585 | // The first two records should be prefetching index and filter blocks. | |
2586 | BlockCacheTraceRecord record; | |
2587 | record.block_type = TraceType::kBlockTraceIndexBlock; | |
2588 | record.caller = TableReaderCaller::kPrefetch; | |
2589 | record.is_cache_hit = Boolean::kFalse; | |
2590 | record.no_insert = Boolean::kFalse; | |
2591 | expected_records.push_back(record); | |
2592 | record.block_type = TraceType::kBlockTraceFilterBlock; | |
2593 | expected_records.push_back(record); | |
2594 | // Then we should have three records for index and two data block access. | |
2595 | record.block_type = TraceType::kBlockTraceIndexBlock; | |
2596 | record.caller = TableReaderCaller::kUserIterator; | |
2597 | record.is_cache_hit = Boolean::kTrue; | |
2598 | expected_records.push_back(record); | |
2599 | record.block_type = TraceType::kBlockTraceDataBlock; | |
2600 | record.is_cache_hit = Boolean::kFalse; | |
2601 | expected_records.push_back(record); | |
2602 | expected_records.push_back(record); | |
2603 | // When we iterate this file for the second time, we should observe all cache | |
2604 | // hits. | |
2605 | record.block_type = TraceType::kBlockTraceIndexBlock; | |
2606 | record.is_cache_hit = Boolean::kTrue; | |
2607 | expected_records.push_back(record); | |
2608 | record.block_type = TraceType::kBlockTraceDataBlock; | |
2609 | expected_records.push_back(record); | |
2610 | expected_records.push_back(record); | |
2611 | VerifyBlockAccessTrace(&c, expected_records); | |
2612 | c.ResetTableReader(); | |
2613 | } | |
2614 | ||
7c673cae FG |
2615 | // A simple tool that takes the snapshot of block cache statistics. |
2616 | class BlockCachePropertiesSnapshot { | |
2617 | public: | |
2618 | explicit BlockCachePropertiesSnapshot(Statistics* statistics) { | |
2619 | block_cache_miss = statistics->getTickerCount(BLOCK_CACHE_MISS); | |
2620 | block_cache_hit = statistics->getTickerCount(BLOCK_CACHE_HIT); | |
2621 | index_block_cache_miss = statistics->getTickerCount(BLOCK_CACHE_INDEX_MISS); | |
2622 | index_block_cache_hit = statistics->getTickerCount(BLOCK_CACHE_INDEX_HIT); | |
2623 | data_block_cache_miss = statistics->getTickerCount(BLOCK_CACHE_DATA_MISS); | |
2624 | data_block_cache_hit = statistics->getTickerCount(BLOCK_CACHE_DATA_HIT); | |
2625 | filter_block_cache_miss = | |
2626 | statistics->getTickerCount(BLOCK_CACHE_FILTER_MISS); | |
2627 | filter_block_cache_hit = statistics->getTickerCount(BLOCK_CACHE_FILTER_HIT); | |
2628 | block_cache_bytes_read = statistics->getTickerCount(BLOCK_CACHE_BYTES_READ); | |
2629 | block_cache_bytes_write = | |
2630 | statistics->getTickerCount(BLOCK_CACHE_BYTES_WRITE); | |
2631 | } | |
2632 | ||
2633 | void AssertIndexBlockStat(int64_t expected_index_block_cache_miss, | |
2634 | int64_t expected_index_block_cache_hit) { | |
2635 | ASSERT_EQ(expected_index_block_cache_miss, index_block_cache_miss); | |
2636 | ASSERT_EQ(expected_index_block_cache_hit, index_block_cache_hit); | |
2637 | } | |
2638 | ||
2639 | void AssertFilterBlockStat(int64_t expected_filter_block_cache_miss, | |
2640 | int64_t expected_filter_block_cache_hit) { | |
2641 | ASSERT_EQ(expected_filter_block_cache_miss, filter_block_cache_miss); | |
2642 | ASSERT_EQ(expected_filter_block_cache_hit, filter_block_cache_hit); | |
2643 | } | |
2644 | ||
2645 | // Check if the fetched props matches the expected ones. | |
2646 | // TODO(kailiu) Use this only when you disabled filter policy! | |
2647 | void AssertEqual(int64_t expected_index_block_cache_miss, | |
2648 | int64_t expected_index_block_cache_hit, | |
2649 | int64_t expected_data_block_cache_miss, | |
2650 | int64_t expected_data_block_cache_hit) const { | |
2651 | ASSERT_EQ(expected_index_block_cache_miss, index_block_cache_miss); | |
2652 | ASSERT_EQ(expected_index_block_cache_hit, index_block_cache_hit); | |
2653 | ASSERT_EQ(expected_data_block_cache_miss, data_block_cache_miss); | |
2654 | ASSERT_EQ(expected_data_block_cache_hit, data_block_cache_hit); | |
2655 | ASSERT_EQ(expected_index_block_cache_miss + expected_data_block_cache_miss, | |
2656 | block_cache_miss); | |
2657 | ASSERT_EQ(expected_index_block_cache_hit + expected_data_block_cache_hit, | |
2658 | block_cache_hit); | |
2659 | } | |
2660 | ||
2661 | int64_t GetCacheBytesRead() { return block_cache_bytes_read; } | |
2662 | ||
2663 | int64_t GetCacheBytesWrite() { return block_cache_bytes_write; } | |
2664 | ||
2665 | private: | |
2666 | int64_t block_cache_miss = 0; | |
2667 | int64_t block_cache_hit = 0; | |
2668 | int64_t index_block_cache_miss = 0; | |
2669 | int64_t index_block_cache_hit = 0; | |
2670 | int64_t data_block_cache_miss = 0; | |
2671 | int64_t data_block_cache_hit = 0; | |
2672 | int64_t filter_block_cache_miss = 0; | |
2673 | int64_t filter_block_cache_hit = 0; | |
2674 | int64_t block_cache_bytes_read = 0; | |
2675 | int64_t block_cache_bytes_write = 0; | |
2676 | }; | |
2677 | ||
2678 | // Make sure, by default, index/filter blocks were pre-loaded (meaning we won't | |
2679 | // use block cache to store them). | |
11fdf7f2 | 2680 | TEST_P(BlockBasedTableTest, BlockCacheDisabledTest) { |
7c673cae FG |
2681 | Options options; |
2682 | options.create_if_missing = true; | |
2683 | options.statistics = CreateDBStatistics(); | |
11fdf7f2 | 2684 | BlockBasedTableOptions table_options = GetBlockBasedTableOptions(); |
7c673cae FG |
2685 | table_options.block_cache = NewLRUCache(1024, 4); |
2686 | table_options.filter_policy.reset(NewBloomFilterPolicy(10)); | |
2687 | options.table_factory.reset(new BlockBasedTableFactory(table_options)); | |
2688 | std::vector<std::string> keys; | |
2689 | stl_wrappers::KVMap kvmap; | |
2690 | ||
2691 | TableConstructor c(BytewiseComparator(), true /* convert_to_internal_key_ */); | |
2692 | c.Add("key", "value"); | |
2693 | const ImmutableCFOptions ioptions(options); | |
11fdf7f2 TL |
2694 | const MutableCFOptions moptions(options); |
2695 | c.Finish(options, ioptions, moptions, table_options, | |
7c673cae FG |
2696 | GetPlainInternalComparator(options.comparator), &keys, &kvmap); |
2697 | ||
2698 | // preloading filter/index blocks is enabled. | |
2699 | auto reader = dynamic_cast<BlockBasedTable*>(c.GetTableReader()); | |
f67539c2 TL |
2700 | ASSERT_FALSE(reader->TEST_FilterBlockInCache()); |
2701 | ASSERT_FALSE(reader->TEST_IndexBlockInCache()); | |
7c673cae FG |
2702 | |
2703 | { | |
2704 | // nothing happens in the beginning | |
2705 | BlockCachePropertiesSnapshot props(options.statistics.get()); | |
2706 | props.AssertIndexBlockStat(0, 0); | |
2707 | props.AssertFilterBlockStat(0, 0); | |
2708 | } | |
2709 | ||
2710 | { | |
2711 | GetContext get_context(options.comparator, nullptr, nullptr, nullptr, | |
2712 | GetContext::kNotFound, Slice(), nullptr, nullptr, | |
f67539c2 | 2713 | nullptr, true, nullptr, nullptr); |
7c673cae | 2714 | // a hack that just to trigger BlockBasedTable::GetFilter. |
11fdf7f2 TL |
2715 | reader->Get(ReadOptions(), "non-exist-key", &get_context, |
2716 | moptions.prefix_extractor.get()); | |
7c673cae FG |
2717 | BlockCachePropertiesSnapshot props(options.statistics.get()); |
2718 | props.AssertIndexBlockStat(0, 0); | |
2719 | props.AssertFilterBlockStat(0, 0); | |
2720 | } | |
2721 | } | |
2722 | ||
2723 | // Due to the difficulities of the intersaction between statistics, this test | |
2724 | // only tests the case when "index block is put to block cache" | |
11fdf7f2 | 2725 | TEST_P(BlockBasedTableTest, FilterBlockInBlockCache) { |
7c673cae FG |
2726 | // -- Table construction |
2727 | Options options; | |
2728 | options.create_if_missing = true; | |
2729 | options.statistics = CreateDBStatistics(); | |
2730 | ||
2731 | // Enable the cache for index/filter blocks | |
11fdf7f2 | 2732 | BlockBasedTableOptions table_options = GetBlockBasedTableOptions(); |
f67539c2 TL |
2733 | LRUCacheOptions co; |
2734 | co.capacity = 2048; | |
2735 | co.num_shard_bits = 2; | |
2736 | co.metadata_charge_policy = kDontChargeCacheMetadata; | |
2737 | table_options.block_cache = NewLRUCache(co); | |
7c673cae FG |
2738 | table_options.cache_index_and_filter_blocks = true; |
2739 | options.table_factory.reset(new BlockBasedTableFactory(table_options)); | |
2740 | std::vector<std::string> keys; | |
2741 | stl_wrappers::KVMap kvmap; | |
2742 | ||
2743 | TableConstructor c(BytewiseComparator(), true /* convert_to_internal_key_ */); | |
2744 | c.Add("key", "value"); | |
2745 | const ImmutableCFOptions ioptions(options); | |
11fdf7f2 TL |
2746 | const MutableCFOptions moptions(options); |
2747 | c.Finish(options, ioptions, moptions, table_options, | |
7c673cae FG |
2748 | GetPlainInternalComparator(options.comparator), &keys, &kvmap); |
2749 | // preloading filter/index blocks is prohibited. | |
2750 | auto* reader = dynamic_cast<BlockBasedTable*>(c.GetTableReader()); | |
f67539c2 TL |
2751 | ASSERT_FALSE(reader->TEST_FilterBlockInCache()); |
2752 | ASSERT_TRUE(reader->TEST_IndexBlockInCache()); | |
7c673cae FG |
2753 | |
2754 | // -- PART 1: Open with regular block cache. | |
2755 | // Since block_cache is disabled, no cache activities will be involved. | |
494da23a | 2756 | std::unique_ptr<InternalIterator> iter; |
7c673cae FG |
2757 | |
2758 | int64_t last_cache_bytes_read = 0; | |
2759 | // At first, no block will be accessed. | |
2760 | { | |
2761 | BlockCachePropertiesSnapshot props(options.statistics.get()); | |
2762 | // index will be added to block cache. | |
2763 | props.AssertEqual(1, // index block miss | |
2764 | 0, 0, 0); | |
2765 | ASSERT_EQ(props.GetCacheBytesRead(), 0); | |
2766 | ASSERT_EQ(props.GetCacheBytesWrite(), | |
f67539c2 | 2767 | static_cast<int64_t>(table_options.block_cache->GetUsage())); |
7c673cae FG |
2768 | last_cache_bytes_read = props.GetCacheBytesRead(); |
2769 | } | |
2770 | ||
2771 | // Only index block will be accessed | |
2772 | { | |
11fdf7f2 | 2773 | iter.reset(c.NewIterator(moptions.prefix_extractor.get())); |
7c673cae FG |
2774 | BlockCachePropertiesSnapshot props(options.statistics.get()); |
2775 | // NOTE: to help better highlight the "detla" of each ticker, I use | |
2776 | // <last_value> + <added_value> to indicate the increment of changed | |
2777 | // value; other numbers remain the same. | |
2778 | props.AssertEqual(1, 0 + 1, // index block hit | |
2779 | 0, 0); | |
2780 | // Cache hit, bytes read from cache should increase | |
2781 | ASSERT_GT(props.GetCacheBytesRead(), last_cache_bytes_read); | |
2782 | ASSERT_EQ(props.GetCacheBytesWrite(), | |
f67539c2 | 2783 | static_cast<int64_t>(table_options.block_cache->GetUsage())); |
7c673cae FG |
2784 | last_cache_bytes_read = props.GetCacheBytesRead(); |
2785 | } | |
2786 | ||
2787 | // Only data block will be accessed | |
2788 | { | |
2789 | iter->SeekToFirst(); | |
2790 | BlockCachePropertiesSnapshot props(options.statistics.get()); | |
2791 | props.AssertEqual(1, 1, 0 + 1, // data block miss | |
2792 | 0); | |
2793 | // Cache miss, Bytes read from cache should not change | |
2794 | ASSERT_EQ(props.GetCacheBytesRead(), last_cache_bytes_read); | |
2795 | ASSERT_EQ(props.GetCacheBytesWrite(), | |
f67539c2 | 2796 | static_cast<int64_t>(table_options.block_cache->GetUsage())); |
7c673cae FG |
2797 | last_cache_bytes_read = props.GetCacheBytesRead(); |
2798 | } | |
2799 | ||
2800 | // Data block will be in cache | |
2801 | { | |
11fdf7f2 | 2802 | iter.reset(c.NewIterator(moptions.prefix_extractor.get())); |
7c673cae FG |
2803 | iter->SeekToFirst(); |
2804 | BlockCachePropertiesSnapshot props(options.statistics.get()); | |
2805 | props.AssertEqual(1, 1 + 1, /* index block hit */ | |
2806 | 1, 0 + 1 /* data block hit */); | |
2807 | // Cache hit, bytes read from cache should increase | |
2808 | ASSERT_GT(props.GetCacheBytesRead(), last_cache_bytes_read); | |
2809 | ASSERT_EQ(props.GetCacheBytesWrite(), | |
f67539c2 | 2810 | static_cast<int64_t>(table_options.block_cache->GetUsage())); |
7c673cae FG |
2811 | } |
2812 | // release the iterator so that the block cache can reset correctly. | |
2813 | iter.reset(); | |
2814 | ||
2815 | c.ResetTableReader(); | |
2816 | ||
2817 | // -- PART 2: Open with very small block cache | |
2818 | // In this test, no block will ever get hit since the block cache is | |
2819 | // too small to fit even one entry. | |
2820 | table_options.block_cache = NewLRUCache(1, 4); | |
2821 | options.statistics = CreateDBStatistics(); | |
2822 | options.table_factory.reset(new BlockBasedTableFactory(table_options)); | |
2823 | const ImmutableCFOptions ioptions2(options); | |
11fdf7f2 TL |
2824 | const MutableCFOptions moptions2(options); |
2825 | c.Reopen(ioptions2, moptions2); | |
7c673cae FG |
2826 | { |
2827 | BlockCachePropertiesSnapshot props(options.statistics.get()); | |
2828 | props.AssertEqual(1, // index block miss | |
2829 | 0, 0, 0); | |
2830 | // Cache miss, Bytes read from cache should not change | |
2831 | ASSERT_EQ(props.GetCacheBytesRead(), 0); | |
2832 | } | |
2833 | ||
2834 | { | |
2835 | // Both index and data block get accessed. | |
2836 | // It first cache index block then data block. But since the cache size | |
2837 | // is only 1, index block will be purged after data block is inserted. | |
11fdf7f2 | 2838 | iter.reset(c.NewIterator(moptions2.prefix_extractor.get())); |
7c673cae FG |
2839 | BlockCachePropertiesSnapshot props(options.statistics.get()); |
2840 | props.AssertEqual(1 + 1, // index block miss | |
2841 | 0, 0, // data block miss | |
2842 | 0); | |
2843 | // Cache hit, bytes read from cache should increase | |
2844 | ASSERT_EQ(props.GetCacheBytesRead(), 0); | |
2845 | } | |
2846 | ||
2847 | { | |
2848 | // SeekToFirst() accesses data block. With similar reason, we expect data | |
2849 | // block's cache miss. | |
2850 | iter->SeekToFirst(); | |
2851 | BlockCachePropertiesSnapshot props(options.statistics.get()); | |
2852 | props.AssertEqual(2, 0, 0 + 1, // data block miss | |
2853 | 0); | |
2854 | // Cache miss, Bytes read from cache should not change | |
2855 | ASSERT_EQ(props.GetCacheBytesRead(), 0); | |
2856 | } | |
2857 | iter.reset(); | |
2858 | c.ResetTableReader(); | |
2859 | ||
2860 | // -- PART 3: Open table with bloom filter enabled but not in SST file | |
2861 | table_options.block_cache = NewLRUCache(4096, 4); | |
2862 | table_options.cache_index_and_filter_blocks = false; | |
2863 | options.table_factory.reset(NewBlockBasedTableFactory(table_options)); | |
2864 | ||
2865 | TableConstructor c3(BytewiseComparator()); | |
2866 | std::string user_key = "k01"; | |
2867 | InternalKey internal_key(user_key, 0, kTypeValue); | |
2868 | c3.Add(internal_key.Encode().ToString(), "hello"); | |
2869 | ImmutableCFOptions ioptions3(options); | |
11fdf7f2 | 2870 | MutableCFOptions moptions3(options); |
7c673cae | 2871 | // Generate table without filter policy |
11fdf7f2 | 2872 | c3.Finish(options, ioptions3, moptions3, table_options, |
7c673cae FG |
2873 | GetPlainInternalComparator(options.comparator), &keys, &kvmap); |
2874 | c3.ResetTableReader(); | |
2875 | ||
2876 | // Open table with filter policy | |
2877 | table_options.filter_policy.reset(NewBloomFilterPolicy(1)); | |
2878 | options.table_factory.reset(new BlockBasedTableFactory(table_options)); | |
2879 | options.statistics = CreateDBStatistics(); | |
2880 | ImmutableCFOptions ioptions4(options); | |
11fdf7f2 TL |
2881 | MutableCFOptions moptions4(options); |
2882 | ASSERT_OK(c3.Reopen(ioptions4, moptions4)); | |
7c673cae | 2883 | reader = dynamic_cast<BlockBasedTable*>(c3.GetTableReader()); |
f67539c2 | 2884 | ASSERT_FALSE(reader->TEST_FilterBlockInCache()); |
7c673cae FG |
2885 | PinnableSlice value; |
2886 | GetContext get_context(options.comparator, nullptr, nullptr, nullptr, | |
2887 | GetContext::kNotFound, user_key, &value, nullptr, | |
f67539c2 | 2888 | nullptr, true, nullptr, nullptr); |
11fdf7f2 TL |
2889 | ASSERT_OK(reader->Get(ReadOptions(), internal_key.Encode(), &get_context, |
2890 | moptions4.prefix_extractor.get())); | |
7c673cae FG |
2891 | ASSERT_STREQ(value.data(), "hello"); |
2892 | BlockCachePropertiesSnapshot props(options.statistics.get()); | |
2893 | props.AssertFilterBlockStat(0, 0); | |
2894 | c3.ResetTableReader(); | |
2895 | } | |
2896 | ||
2897 | void ValidateBlockSizeDeviation(int value, int expected) { | |
2898 | BlockBasedTableOptions table_options; | |
2899 | table_options.block_size_deviation = value; | |
2900 | BlockBasedTableFactory* factory = new BlockBasedTableFactory(table_options); | |
2901 | ||
2902 | const BlockBasedTableOptions* normalized_table_options = | |
2903 | (const BlockBasedTableOptions*)factory->GetOptions(); | |
2904 | ASSERT_EQ(normalized_table_options->block_size_deviation, expected); | |
2905 | ||
2906 | delete factory; | |
2907 | } | |
2908 | ||
2909 | void ValidateBlockRestartInterval(int value, int expected) { | |
2910 | BlockBasedTableOptions table_options; | |
2911 | table_options.block_restart_interval = value; | |
2912 | BlockBasedTableFactory* factory = new BlockBasedTableFactory(table_options); | |
2913 | ||
2914 | const BlockBasedTableOptions* normalized_table_options = | |
2915 | (const BlockBasedTableOptions*)factory->GetOptions(); | |
2916 | ASSERT_EQ(normalized_table_options->block_restart_interval, expected); | |
2917 | ||
2918 | delete factory; | |
2919 | } | |
2920 | ||
11fdf7f2 | 2921 | TEST_P(BlockBasedTableTest, InvalidOptions) { |
7c673cae FG |
2922 | // invalid values for block_size_deviation (<0 or >100) are silently set to 0 |
2923 | ValidateBlockSizeDeviation(-10, 0); | |
2924 | ValidateBlockSizeDeviation(-1, 0); | |
2925 | ValidateBlockSizeDeviation(0, 0); | |
2926 | ValidateBlockSizeDeviation(1, 1); | |
2927 | ValidateBlockSizeDeviation(99, 99); | |
2928 | ValidateBlockSizeDeviation(100, 100); | |
2929 | ValidateBlockSizeDeviation(101, 0); | |
2930 | ValidateBlockSizeDeviation(1000, 0); | |
2931 | ||
2932 | // invalid values for block_restart_interval (<1) are silently set to 1 | |
2933 | ValidateBlockRestartInterval(-10, 1); | |
2934 | ValidateBlockRestartInterval(-1, 1); | |
2935 | ValidateBlockRestartInterval(0, 1); | |
2936 | ValidateBlockRestartInterval(1, 1); | |
2937 | ValidateBlockRestartInterval(2, 2); | |
2938 | ValidateBlockRestartInterval(1000, 1000); | |
2939 | } | |
2940 | ||
11fdf7f2 | 2941 | TEST_P(BlockBasedTableTest, BlockReadCountTest) { |
7c673cae FG |
2942 | // bloom_filter_type = 0 -- block-based filter |
2943 | // bloom_filter_type = 0 -- full filter | |
2944 | for (int bloom_filter_type = 0; bloom_filter_type < 2; ++bloom_filter_type) { | |
2945 | for (int index_and_filter_in_cache = 0; index_and_filter_in_cache < 2; | |
2946 | ++index_and_filter_in_cache) { | |
2947 | Options options; | |
2948 | options.create_if_missing = true; | |
2949 | ||
11fdf7f2 | 2950 | BlockBasedTableOptions table_options = GetBlockBasedTableOptions(); |
7c673cae FG |
2951 | table_options.block_cache = NewLRUCache(1, 0); |
2952 | table_options.cache_index_and_filter_blocks = index_and_filter_in_cache; | |
2953 | table_options.filter_policy.reset( | |
2954 | NewBloomFilterPolicy(10, bloom_filter_type == 0)); | |
2955 | options.table_factory.reset(new BlockBasedTableFactory(table_options)); | |
2956 | std::vector<std::string> keys; | |
2957 | stl_wrappers::KVMap kvmap; | |
2958 | ||
2959 | TableConstructor c(BytewiseComparator()); | |
2960 | std::string user_key = "k04"; | |
2961 | InternalKey internal_key(user_key, 0, kTypeValue); | |
2962 | std::string encoded_key = internal_key.Encode().ToString(); | |
2963 | c.Add(encoded_key, "hello"); | |
2964 | ImmutableCFOptions ioptions(options); | |
11fdf7f2 | 2965 | MutableCFOptions moptions(options); |
7c673cae | 2966 | // Generate table with filter policy |
11fdf7f2 | 2967 | c.Finish(options, ioptions, moptions, table_options, |
7c673cae FG |
2968 | GetPlainInternalComparator(options.comparator), &keys, &kvmap); |
2969 | auto reader = c.GetTableReader(); | |
2970 | PinnableSlice value; | |
f67539c2 TL |
2971 | { |
2972 | GetContext get_context(options.comparator, nullptr, nullptr, nullptr, | |
2973 | GetContext::kNotFound, user_key, &value, nullptr, | |
2974 | nullptr, true, nullptr, nullptr); | |
2975 | get_perf_context()->Reset(); | |
2976 | ASSERT_OK(reader->Get(ReadOptions(), encoded_key, &get_context, | |
2977 | moptions.prefix_extractor.get())); | |
2978 | if (index_and_filter_in_cache) { | |
2979 | // data, index and filter block | |
2980 | ASSERT_EQ(get_perf_context()->block_read_count, 3); | |
2981 | ASSERT_EQ(get_perf_context()->index_block_read_count, 1); | |
2982 | ASSERT_EQ(get_perf_context()->filter_block_read_count, 1); | |
2983 | } else { | |
2984 | // just the data block | |
2985 | ASSERT_EQ(get_perf_context()->block_read_count, 1); | |
2986 | } | |
2987 | ASSERT_EQ(get_context.State(), GetContext::kFound); | |
2988 | ASSERT_STREQ(value.data(), "hello"); | |
7c673cae | 2989 | } |
7c673cae FG |
2990 | |
2991 | // Get non-existing key | |
2992 | user_key = "does-not-exist"; | |
2993 | internal_key = InternalKey(user_key, 0, kTypeValue); | |
2994 | encoded_key = internal_key.Encode().ToString(); | |
2995 | ||
2996 | value.Reset(); | |
f67539c2 TL |
2997 | { |
2998 | GetContext get_context(options.comparator, nullptr, nullptr, nullptr, | |
7c673cae | 2999 | GetContext::kNotFound, user_key, &value, nullptr, |
f67539c2 TL |
3000 | nullptr, true, nullptr, nullptr); |
3001 | get_perf_context()->Reset(); | |
3002 | ASSERT_OK(reader->Get(ReadOptions(), encoded_key, &get_context, | |
3003 | moptions.prefix_extractor.get())); | |
3004 | ASSERT_EQ(get_context.State(), GetContext::kNotFound); | |
3005 | } | |
7c673cae FG |
3006 | |
3007 | if (index_and_filter_in_cache) { | |
3008 | if (bloom_filter_type == 0) { | |
3009 | // with block-based, we read index and then the filter | |
11fdf7f2 | 3010 | ASSERT_EQ(get_perf_context()->block_read_count, 2); |
f67539c2 TL |
3011 | ASSERT_EQ(get_perf_context()->index_block_read_count, 1); |
3012 | ASSERT_EQ(get_perf_context()->filter_block_read_count, 1); | |
7c673cae FG |
3013 | } else { |
3014 | // with full-filter, we read filter first and then we stop | |
11fdf7f2 | 3015 | ASSERT_EQ(get_perf_context()->block_read_count, 1); |
f67539c2 | 3016 | ASSERT_EQ(get_perf_context()->filter_block_read_count, 1); |
7c673cae FG |
3017 | } |
3018 | } else { | |
3019 | // filter is already in memory and it figures out that the key doesn't | |
3020 | // exist | |
11fdf7f2 | 3021 | ASSERT_EQ(get_perf_context()->block_read_count, 0); |
7c673cae FG |
3022 | } |
3023 | } | |
3024 | } | |
3025 | } | |
3026 | ||
11fdf7f2 | 3027 | TEST_P(BlockBasedTableTest, BlockCacheLeak) { |
7c673cae FG |
3028 | // Check that when we reopen a table we don't lose access to blocks already |
3029 | // in the cache. This test checks whether the Table actually makes use of the | |
3030 | // unique ID from the file. | |
3031 | ||
3032 | Options opt; | |
494da23a | 3033 | std::unique_ptr<InternalKeyComparator> ikc; |
7c673cae FG |
3034 | ikc.reset(new test::PlainInternalKeyComparator(opt.comparator)); |
3035 | opt.compression = kNoCompression; | |
11fdf7f2 | 3036 | BlockBasedTableOptions table_options = GetBlockBasedTableOptions(); |
7c673cae FG |
3037 | table_options.block_size = 1024; |
3038 | // big enough so we don't ever lose cached values. | |
3039 | table_options.block_cache = NewLRUCache(16 * 1024 * 1024, 4); | |
3040 | opt.table_factory.reset(NewBlockBasedTableFactory(table_options)); | |
3041 | ||
3042 | TableConstructor c(BytewiseComparator(), true /* convert_to_internal_key_ */); | |
3043 | c.Add("k01", "hello"); | |
3044 | c.Add("k02", "hello2"); | |
3045 | c.Add("k03", std::string(10000, 'x')); | |
3046 | c.Add("k04", std::string(200000, 'x')); | |
3047 | c.Add("k05", std::string(300000, 'x')); | |
3048 | c.Add("k06", "hello3"); | |
3049 | c.Add("k07", std::string(100000, 'x')); | |
3050 | std::vector<std::string> keys; | |
3051 | stl_wrappers::KVMap kvmap; | |
3052 | const ImmutableCFOptions ioptions(opt); | |
11fdf7f2 TL |
3053 | const MutableCFOptions moptions(opt); |
3054 | c.Finish(opt, ioptions, moptions, table_options, *ikc, &keys, &kvmap); | |
7c673cae | 3055 | |
494da23a | 3056 | std::unique_ptr<InternalIterator> iter( |
11fdf7f2 | 3057 | c.NewIterator(moptions.prefix_extractor.get())); |
7c673cae FG |
3058 | iter->SeekToFirst(); |
3059 | while (iter->Valid()) { | |
3060 | iter->key(); | |
3061 | iter->value(); | |
3062 | iter->Next(); | |
3063 | } | |
3064 | ASSERT_OK(iter->status()); | |
11fdf7f2 | 3065 | iter.reset(); |
7c673cae FG |
3066 | |
3067 | const ImmutableCFOptions ioptions1(opt); | |
11fdf7f2 TL |
3068 | const MutableCFOptions moptions1(opt); |
3069 | ASSERT_OK(c.Reopen(ioptions1, moptions1)); | |
7c673cae FG |
3070 | auto table_reader = dynamic_cast<BlockBasedTable*>(c.GetTableReader()); |
3071 | for (const std::string& key : keys) { | |
11fdf7f2 TL |
3072 | InternalKey ikey(key, kMaxSequenceNumber, kTypeValue); |
3073 | ASSERT_TRUE(table_reader->TEST_KeyInCache(ReadOptions(), ikey.Encode())); | |
7c673cae FG |
3074 | } |
3075 | c.ResetTableReader(); | |
3076 | ||
3077 | // rerun with different block cache | |
3078 | table_options.block_cache = NewLRUCache(16 * 1024 * 1024, 4); | |
3079 | opt.table_factory.reset(NewBlockBasedTableFactory(table_options)); | |
3080 | const ImmutableCFOptions ioptions2(opt); | |
11fdf7f2 TL |
3081 | const MutableCFOptions moptions2(opt); |
3082 | ASSERT_OK(c.Reopen(ioptions2, moptions2)); | |
7c673cae FG |
3083 | table_reader = dynamic_cast<BlockBasedTable*>(c.GetTableReader()); |
3084 | for (const std::string& key : keys) { | |
11fdf7f2 TL |
3085 | InternalKey ikey(key, kMaxSequenceNumber, kTypeValue); |
3086 | ASSERT_TRUE(!table_reader->TEST_KeyInCache(ReadOptions(), ikey.Encode())); | |
7c673cae FG |
3087 | } |
3088 | c.ResetTableReader(); | |
3089 | } | |
3090 | ||
494da23a TL |
3091 | namespace { |
3092 | class CustomMemoryAllocator : public MemoryAllocator { | |
3093 | public: | |
3094 | const char* Name() const override { return "CustomMemoryAllocator"; } | |
3095 | ||
3096 | void* Allocate(size_t size) override { | |
3097 | ++numAllocations; | |
3098 | auto ptr = new char[size + 16]; | |
3099 | memcpy(ptr, "memory_allocator_", 16); // mangle first 16 bytes | |
3100 | return reinterpret_cast<void*>(ptr + 16); | |
3101 | } | |
3102 | void Deallocate(void* p) override { | |
3103 | ++numDeallocations; | |
3104 | char* ptr = reinterpret_cast<char*>(p) - 16; | |
3105 | delete[] ptr; | |
3106 | } | |
3107 | ||
3108 | std::atomic<int> numAllocations; | |
3109 | std::atomic<int> numDeallocations; | |
3110 | }; | |
3111 | } // namespace | |
3112 | ||
3113 | TEST_P(BlockBasedTableTest, MemoryAllocator) { | |
3114 | auto custom_memory_allocator = std::make_shared<CustomMemoryAllocator>(); | |
3115 | { | |
3116 | Options opt; | |
3117 | std::unique_ptr<InternalKeyComparator> ikc; | |
3118 | ikc.reset(new test::PlainInternalKeyComparator(opt.comparator)); | |
3119 | opt.compression = kNoCompression; | |
3120 | BlockBasedTableOptions table_options; | |
3121 | table_options.block_size = 1024; | |
3122 | LRUCacheOptions lruOptions; | |
3123 | lruOptions.memory_allocator = custom_memory_allocator; | |
3124 | lruOptions.capacity = 16 * 1024 * 1024; | |
3125 | lruOptions.num_shard_bits = 4; | |
3126 | table_options.block_cache = NewLRUCache(std::move(lruOptions)); | |
3127 | opt.table_factory.reset(NewBlockBasedTableFactory(table_options)); | |
3128 | ||
3129 | TableConstructor c(BytewiseComparator(), | |
3130 | true /* convert_to_internal_key_ */); | |
3131 | c.Add("k01", "hello"); | |
3132 | c.Add("k02", "hello2"); | |
3133 | c.Add("k03", std::string(10000, 'x')); | |
3134 | c.Add("k04", std::string(200000, 'x')); | |
3135 | c.Add("k05", std::string(300000, 'x')); | |
3136 | c.Add("k06", "hello3"); | |
3137 | c.Add("k07", std::string(100000, 'x')); | |
3138 | std::vector<std::string> keys; | |
3139 | stl_wrappers::KVMap kvmap; | |
3140 | const ImmutableCFOptions ioptions(opt); | |
3141 | const MutableCFOptions moptions(opt); | |
3142 | c.Finish(opt, ioptions, moptions, table_options, *ikc, &keys, &kvmap); | |
3143 | ||
3144 | std::unique_ptr<InternalIterator> iter( | |
3145 | c.NewIterator(moptions.prefix_extractor.get())); | |
3146 | iter->SeekToFirst(); | |
3147 | while (iter->Valid()) { | |
3148 | iter->key(); | |
3149 | iter->value(); | |
3150 | iter->Next(); | |
3151 | } | |
3152 | ASSERT_OK(iter->status()); | |
3153 | } | |
3154 | ||
3155 | // out of scope, block cache should have been deleted, all allocations | |
3156 | // deallocated | |
3157 | EXPECT_EQ(custom_memory_allocator->numAllocations.load(), | |
3158 | custom_memory_allocator->numDeallocations.load()); | |
3159 | // make sure that allocations actually happened through the cache allocator | |
3160 | EXPECT_GT(custom_memory_allocator->numAllocations.load(), 0); | |
3161 | } | |
3162 | ||
f67539c2 TL |
3163 | // Test the file checksum of block based table |
3164 | TEST_P(BlockBasedTableTest, NoFileChecksum) { | |
7c673cae | 3165 | Options options; |
f67539c2 TL |
3166 | ImmutableCFOptions ioptions(options); |
3167 | MutableCFOptions moptions(options); | |
11fdf7f2 | 3168 | BlockBasedTableOptions table_options = GetBlockBasedTableOptions(); |
f67539c2 TL |
3169 | std::unique_ptr<InternalKeyComparator> comparator( |
3170 | new InternalKeyComparator(BytewiseComparator())); | |
3171 | SequenceNumber largest_seqno = 0; | |
3172 | int level = 0; | |
3173 | std::vector<std::unique_ptr<IntTblPropCollectorFactory>> | |
3174 | int_tbl_prop_collector_factories; | |
7c673cae | 3175 | |
f67539c2 TL |
3176 | if (largest_seqno != 0) { |
3177 | // Pretend that it's an external file written by SstFileWriter. | |
3178 | int_tbl_prop_collector_factories.emplace_back( | |
3179 | new SstFileWriterPropertiesCollectorFactory(2 /* version */, | |
3180 | 0 /* global_seqno*/)); | |
3181 | } | |
3182 | std::string column_family_name; | |
7c673cae | 3183 | |
f67539c2 TL |
3184 | FileChecksumTestHelper f(true); |
3185 | f.CreateWriteableFile(); | |
3186 | std::unique_ptr<TableBuilder> builder; | |
3187 | builder.reset(ioptions.table_factory->NewTableBuilder( | |
3188 | TableBuilderOptions(ioptions, moptions, *comparator, | |
3189 | &int_tbl_prop_collector_factories, | |
3190 | options.compression, options.sample_for_compression, | |
3191 | options.compression_opts, false /* skip_filters */, | |
3192 | column_family_name, level), | |
3193 | TablePropertiesCollectorFactory::Context::kUnknownColumnFamily, | |
3194 | f.GetFileWriter())); | |
3195 | f.ResetTableBuilder(std::move(builder)); | |
3196 | f.AddKVtoKVMap(1000); | |
3197 | f.WriteKVAndFlushTable(); | |
3198 | ASSERT_STREQ(f.GetFileChecksumFuncName(), | |
3199 | kUnknownFileChecksumFuncName.c_str()); | |
3200 | ASSERT_STREQ(f.GetFileChecksum().c_str(), kUnknownFileChecksum.c_str()); | |
3201 | } | |
7c673cae | 3202 | |
f67539c2 TL |
3203 | TEST_P(BlockBasedTableTest, Crc32FileChecksum) { |
3204 | Options options; | |
3205 | options.sst_file_checksum_func = | |
3206 | std::shared_ptr<FileChecksumFunc>(CreateFileChecksumFuncCrc32c()); | |
3207 | ImmutableCFOptions ioptions(options); | |
3208 | MutableCFOptions moptions(options); | |
3209 | BlockBasedTableOptions table_options = GetBlockBasedTableOptions(); | |
3210 | std::unique_ptr<InternalKeyComparator> comparator( | |
3211 | new InternalKeyComparator(BytewiseComparator())); | |
3212 | SequenceNumber largest_seqno = 0; | |
3213 | int level = 0; | |
3214 | std::vector<std::unique_ptr<IntTblPropCollectorFactory>> | |
3215 | int_tbl_prop_collector_factories; | |
7c673cae | 3216 | |
f67539c2 TL |
3217 | if (largest_seqno != 0) { |
3218 | // Pretend that it's an external file written by SstFileWriter. | |
3219 | int_tbl_prop_collector_factories.emplace_back( | |
3220 | new SstFileWriterPropertiesCollectorFactory(2 /* version */, | |
3221 | 0 /* global_seqno*/)); | |
3222 | } | |
3223 | std::string column_family_name; | |
3224 | ||
3225 | FileChecksumTestHelper f(true); | |
3226 | f.CreateWriteableFile(); | |
3227 | f.SetFileChecksumFunc(options.sst_file_checksum_func.get()); | |
3228 | std::unique_ptr<TableBuilder> builder; | |
3229 | builder.reset(ioptions.table_factory->NewTableBuilder( | |
3230 | TableBuilderOptions(ioptions, moptions, *comparator, | |
3231 | &int_tbl_prop_collector_factories, | |
3232 | options.compression, options.sample_for_compression, | |
3233 | options.compression_opts, false /* skip_filters */, | |
3234 | column_family_name, level), | |
3235 | TablePropertiesCollectorFactory::Context::kUnknownColumnFamily, | |
3236 | f.GetFileWriter())); | |
3237 | f.ResetTableBuilder(std::move(builder)); | |
3238 | f.AddKVtoKVMap(1000); | |
3239 | f.WriteKVAndFlushTable(); | |
3240 | ASSERT_STREQ(f.GetFileChecksumFuncName(), "FileChecksumCrc32c"); | |
3241 | std::string checksum; | |
3242 | ASSERT_OK( | |
3243 | f.CalculateFileChecksum(options.sst_file_checksum_func.get(), &checksum)); | |
3244 | ASSERT_STREQ(f.GetFileChecksum().c_str(), checksum.c_str()); | |
7c673cae FG |
3245 | } |
3246 | ||
3247 | // Plain table is not supported in ROCKSDB_LITE | |
3248 | #ifndef ROCKSDB_LITE | |
3249 | TEST_F(PlainTableTest, BasicPlainTableProperties) { | |
3250 | PlainTableOptions plain_table_options; | |
3251 | plain_table_options.user_key_len = 8; | |
3252 | plain_table_options.bloom_bits_per_key = 8; | |
3253 | plain_table_options.hash_table_ratio = 0; | |
3254 | ||
3255 | PlainTableFactory factory(plain_table_options); | |
3256 | test::StringSink sink; | |
494da23a | 3257 | std::unique_ptr<WritableFileWriter> file_writer( |
11fdf7f2 | 3258 | test::GetWritableFileWriter(new test::StringSink(), "" /* don't care */)); |
7c673cae FG |
3259 | Options options; |
3260 | const ImmutableCFOptions ioptions(options); | |
11fdf7f2 | 3261 | const MutableCFOptions moptions(options); |
7c673cae FG |
3262 | InternalKeyComparator ikc(options.comparator); |
3263 | std::vector<std::unique_ptr<IntTblPropCollectorFactory>> | |
3264 | int_tbl_prop_collector_factories; | |
3265 | std::string column_family_name; | |
3266 | int unknown_level = -1; | |
3267 | std::unique_ptr<TableBuilder> builder(factory.NewTableBuilder( | |
11fdf7f2 TL |
3268 | TableBuilderOptions( |
3269 | ioptions, moptions, ikc, &int_tbl_prop_collector_factories, | |
494da23a | 3270 | kNoCompression, 0 /* sample_for_compression */, CompressionOptions(), |
11fdf7f2 | 3271 | false /* skip_filters */, column_family_name, unknown_level), |
7c673cae FG |
3272 | TablePropertiesCollectorFactory::Context::kUnknownColumnFamily, |
3273 | file_writer.get())); | |
3274 | ||
3275 | for (char c = 'a'; c <= 'z'; ++c) { | |
3276 | std::string key(8, c); | |
3277 | key.append("\1 "); // PlainTable expects internal key structure | |
3278 | std::string value(28, c + 42); | |
3279 | builder->Add(key, value); | |
3280 | } | |
3281 | ASSERT_OK(builder->Finish()); | |
3282 | file_writer->Flush(); | |
3283 | ||
3284 | test::StringSink* ss = | |
f67539c2 | 3285 | ROCKSDB_NAMESPACE::test::GetStringSinkFromLegacyWriter(file_writer.get()); |
494da23a | 3286 | std::unique_ptr<RandomAccessFileReader> file_reader( |
7c673cae FG |
3287 | test::GetRandomAccessFileReader( |
3288 | new test::StringSource(ss->contents(), 72242, true))); | |
3289 | ||
3290 | TableProperties* props = nullptr; | |
3291 | auto s = ReadTableProperties(file_reader.get(), ss->contents().size(), | |
3292 | kPlainTableMagicNumber, ioptions, | |
11fdf7f2 | 3293 | &props, true /* compression_type_missing */); |
7c673cae FG |
3294 | std::unique_ptr<TableProperties> props_guard(props); |
3295 | ASSERT_OK(s); | |
3296 | ||
3297 | ASSERT_EQ(0ul, props->index_size); | |
3298 | ASSERT_EQ(0ul, props->filter_size); | |
3299 | ASSERT_EQ(16ul * 26, props->raw_key_size); | |
3300 | ASSERT_EQ(28ul * 26, props->raw_value_size); | |
3301 | ASSERT_EQ(26ul, props->num_entries); | |
3302 | ASSERT_EQ(1ul, props->num_data_blocks); | |
3303 | } | |
f67539c2 TL |
3304 | |
3305 | TEST_F(PlainTableTest, NoFileChecksum) { | |
3306 | PlainTableOptions plain_table_options; | |
3307 | plain_table_options.user_key_len = 20; | |
3308 | plain_table_options.bloom_bits_per_key = 8; | |
3309 | plain_table_options.hash_table_ratio = 0; | |
3310 | PlainTableFactory factory(plain_table_options); | |
3311 | ||
3312 | Options options; | |
3313 | const ImmutableCFOptions ioptions(options); | |
3314 | const MutableCFOptions moptions(options); | |
3315 | InternalKeyComparator ikc(options.comparator); | |
3316 | std::vector<std::unique_ptr<IntTblPropCollectorFactory>> | |
3317 | int_tbl_prop_collector_factories; | |
3318 | std::string column_family_name; | |
3319 | int unknown_level = -1; | |
3320 | FileChecksumTestHelper f(true); | |
3321 | f.CreateWriteableFile(); | |
3322 | ||
3323 | std::unique_ptr<TableBuilder> builder(factory.NewTableBuilder( | |
3324 | TableBuilderOptions( | |
3325 | ioptions, moptions, ikc, &int_tbl_prop_collector_factories, | |
3326 | kNoCompression, 0 /* sample_for_compression */, CompressionOptions(), | |
3327 | false /* skip_filters */, column_family_name, unknown_level), | |
3328 | TablePropertiesCollectorFactory::Context::kUnknownColumnFamily, | |
3329 | f.GetFileWriter())); | |
3330 | f.ResetTableBuilder(std::move(builder)); | |
3331 | f.AddKVtoKVMap(1000); | |
3332 | f.WriteKVAndFlushTable(); | |
3333 | ASSERT_STREQ(f.GetFileChecksumFuncName(), | |
3334 | kUnknownFileChecksumFuncName.c_str()); | |
3335 | EXPECT_EQ(f.GetFileChecksum(), kUnknownFileChecksum.c_str()); | |
3336 | } | |
3337 | ||
3338 | TEST_F(PlainTableTest, Crc32FileChecksum) { | |
3339 | PlainTableOptions plain_table_options; | |
3340 | plain_table_options.user_key_len = 20; | |
3341 | plain_table_options.bloom_bits_per_key = 8; | |
3342 | plain_table_options.hash_table_ratio = 0; | |
3343 | PlainTableFactory factory(plain_table_options); | |
3344 | ||
3345 | Options options; | |
3346 | options.sst_file_checksum_func = | |
3347 | std::shared_ptr<FileChecksumFunc>(CreateFileChecksumFuncCrc32c()); | |
3348 | const ImmutableCFOptions ioptions(options); | |
3349 | const MutableCFOptions moptions(options); | |
3350 | InternalKeyComparator ikc(options.comparator); | |
3351 | std::vector<std::unique_ptr<IntTblPropCollectorFactory>> | |
3352 | int_tbl_prop_collector_factories; | |
3353 | std::string column_family_name; | |
3354 | int unknown_level = -1; | |
3355 | FileChecksumTestHelper f(true); | |
3356 | f.CreateWriteableFile(); | |
3357 | f.SetFileChecksumFunc(options.sst_file_checksum_func.get()); | |
3358 | ||
3359 | std::unique_ptr<TableBuilder> builder(factory.NewTableBuilder( | |
3360 | TableBuilderOptions( | |
3361 | ioptions, moptions, ikc, &int_tbl_prop_collector_factories, | |
3362 | kNoCompression, 0 /* sample_for_compression */, CompressionOptions(), | |
3363 | false /* skip_filters */, column_family_name, unknown_level), | |
3364 | TablePropertiesCollectorFactory::Context::kUnknownColumnFamily, | |
3365 | f.GetFileWriter())); | |
3366 | f.ResetTableBuilder(std::move(builder)); | |
3367 | f.AddKVtoKVMap(1000); | |
3368 | f.WriteKVAndFlushTable(); | |
3369 | ASSERT_STREQ(f.GetFileChecksumFuncName(), "FileChecksumCrc32c"); | |
3370 | std::string checksum; | |
3371 | ASSERT_OK( | |
3372 | f.CalculateFileChecksum(options.sst_file_checksum_func.get(), &checksum)); | |
3373 | EXPECT_STREQ(f.GetFileChecksum().c_str(), checksum.c_str()); | |
3374 | } | |
3375 | ||
7c673cae FG |
3376 | #endif // !ROCKSDB_LITE |
3377 | ||
3378 | TEST_F(GeneralTableTest, ApproximateOffsetOfPlain) { | |
3379 | TableConstructor c(BytewiseComparator(), true /* convert_to_internal_key_ */); | |
3380 | c.Add("k01", "hello"); | |
3381 | c.Add("k02", "hello2"); | |
3382 | c.Add("k03", std::string(10000, 'x')); | |
3383 | c.Add("k04", std::string(200000, 'x')); | |
3384 | c.Add("k05", std::string(300000, 'x')); | |
3385 | c.Add("k06", "hello3"); | |
3386 | c.Add("k07", std::string(100000, 'x')); | |
3387 | std::vector<std::string> keys; | |
3388 | stl_wrappers::KVMap kvmap; | |
3389 | Options options; | |
3390 | test::PlainInternalKeyComparator internal_comparator(options.comparator); | |
3391 | options.compression = kNoCompression; | |
3392 | BlockBasedTableOptions table_options; | |
3393 | table_options.block_size = 1024; | |
3394 | const ImmutableCFOptions ioptions(options); | |
11fdf7f2 TL |
3395 | const MutableCFOptions moptions(options); |
3396 | c.Finish(options, ioptions, moptions, table_options, internal_comparator, | |
7c673cae FG |
3397 | &keys, &kvmap); |
3398 | ||
3399 | ASSERT_TRUE(Between(c.ApproximateOffsetOf("abc"), 0, 0)); | |
3400 | ASSERT_TRUE(Between(c.ApproximateOffsetOf("k01"), 0, 0)); | |
3401 | ASSERT_TRUE(Between(c.ApproximateOffsetOf("k01a"), 0, 0)); | |
3402 | ASSERT_TRUE(Between(c.ApproximateOffsetOf("k02"), 0, 0)); | |
3403 | ASSERT_TRUE(Between(c.ApproximateOffsetOf("k03"), 0, 0)); | |
3404 | ASSERT_TRUE(Between(c.ApproximateOffsetOf("k04"), 10000, 11000)); | |
3405 | // k04 and k05 will be in two consecutive blocks, the index is | |
3406 | // an arbitrary slice between k04 and k05, either before or after k04a | |
3407 | ASSERT_TRUE(Between(c.ApproximateOffsetOf("k04a"), 10000, 211000)); | |
3408 | ASSERT_TRUE(Between(c.ApproximateOffsetOf("k05"), 210000, 211000)); | |
3409 | ASSERT_TRUE(Between(c.ApproximateOffsetOf("k06"), 510000, 511000)); | |
3410 | ASSERT_TRUE(Between(c.ApproximateOffsetOf("k07"), 510000, 511000)); | |
3411 | ASSERT_TRUE(Between(c.ApproximateOffsetOf("xyz"), 610000, 612000)); | |
3412 | c.ResetTableReader(); | |
3413 | } | |
3414 | ||
3415 | static void DoCompressionTest(CompressionType comp) { | |
3416 | Random rnd(301); | |
3417 | TableConstructor c(BytewiseComparator(), true /* convert_to_internal_key_ */); | |
3418 | std::string tmp; | |
3419 | c.Add("k01", "hello"); | |
3420 | c.Add("k02", test::CompressibleString(&rnd, 0.25, 10000, &tmp)); | |
3421 | c.Add("k03", "hello3"); | |
3422 | c.Add("k04", test::CompressibleString(&rnd, 0.25, 10000, &tmp)); | |
3423 | std::vector<std::string> keys; | |
3424 | stl_wrappers::KVMap kvmap; | |
3425 | Options options; | |
3426 | test::PlainInternalKeyComparator ikc(options.comparator); | |
3427 | options.compression = comp; | |
3428 | BlockBasedTableOptions table_options; | |
3429 | table_options.block_size = 1024; | |
3430 | const ImmutableCFOptions ioptions(options); | |
11fdf7f2 TL |
3431 | const MutableCFOptions moptions(options); |
3432 | c.Finish(options, ioptions, moptions, table_options, ikc, &keys, &kvmap); | |
7c673cae FG |
3433 | |
3434 | ASSERT_TRUE(Between(c.ApproximateOffsetOf("abc"), 0, 0)); | |
3435 | ASSERT_TRUE(Between(c.ApproximateOffsetOf("k01"), 0, 0)); | |
3436 | ASSERT_TRUE(Between(c.ApproximateOffsetOf("k02"), 0, 0)); | |
494da23a TL |
3437 | ASSERT_TRUE(Between(c.ApproximateOffsetOf("k03"), 2000, 3500)); |
3438 | ASSERT_TRUE(Between(c.ApproximateOffsetOf("k04"), 2000, 3500)); | |
3439 | ASSERT_TRUE(Between(c.ApproximateOffsetOf("xyz"), 4000, 6500)); | |
7c673cae FG |
3440 | c.ResetTableReader(); |
3441 | } | |
3442 | ||
3443 | TEST_F(GeneralTableTest, ApproximateOffsetOfCompressed) { | |
3444 | std::vector<CompressionType> compression_state; | |
3445 | if (!Snappy_Supported()) { | |
3446 | fprintf(stderr, "skipping snappy compression tests\n"); | |
3447 | } else { | |
3448 | compression_state.push_back(kSnappyCompression); | |
3449 | } | |
3450 | ||
3451 | if (!Zlib_Supported()) { | |
3452 | fprintf(stderr, "skipping zlib compression tests\n"); | |
3453 | } else { | |
3454 | compression_state.push_back(kZlibCompression); | |
3455 | } | |
3456 | ||
3457 | // TODO(kailiu) DoCompressionTest() doesn't work with BZip2. | |
3458 | /* | |
3459 | if (!BZip2_Supported()) { | |
3460 | fprintf(stderr, "skipping bzip2 compression tests\n"); | |
3461 | } else { | |
3462 | compression_state.push_back(kBZip2Compression); | |
3463 | } | |
3464 | */ | |
3465 | ||
3466 | if (!LZ4_Supported()) { | |
3467 | fprintf(stderr, "skipping lz4 and lz4hc compression tests\n"); | |
3468 | } else { | |
3469 | compression_state.push_back(kLZ4Compression); | |
3470 | compression_state.push_back(kLZ4HCCompression); | |
3471 | } | |
3472 | ||
3473 | if (!XPRESS_Supported()) { | |
3474 | fprintf(stderr, "skipping xpress and xpress compression tests\n"); | |
3475 | } | |
3476 | else { | |
3477 | compression_state.push_back(kXpressCompression); | |
3478 | } | |
3479 | ||
3480 | for (auto state : compression_state) { | |
3481 | DoCompressionTest(state); | |
3482 | } | |
3483 | } | |
3484 | ||
494da23a | 3485 | #ifndef ROCKSDB_VALGRIND_RUN |
11fdf7f2 TL |
3486 | // RandomizedHarnessTest is very slow for certain combination of arguments |
3487 | // Split into 8 pieces to reduce the time individual tests take. | |
3488 | TEST_F(HarnessTest, Randomized1) { | |
3489 | // part 1 out of 8 | |
3490 | const size_t part = 1; | |
3491 | const size_t total = 8; | |
3492 | RandomizedHarnessTest(part, total); | |
3493 | } | |
3494 | ||
3495 | TEST_F(HarnessTest, Randomized2) { | |
3496 | // part 2 out of 8 | |
3497 | const size_t part = 2; | |
3498 | const size_t total = 8; | |
3499 | RandomizedHarnessTest(part, total); | |
3500 | } | |
3501 | ||
3502 | TEST_F(HarnessTest, Randomized3) { | |
3503 | // part 3 out of 8 | |
3504 | const size_t part = 3; | |
3505 | const size_t total = 8; | |
3506 | RandomizedHarnessTest(part, total); | |
3507 | } | |
3508 | ||
3509 | TEST_F(HarnessTest, Randomized4) { | |
3510 | // part 4 out of 8 | |
3511 | const size_t part = 4; | |
3512 | const size_t total = 8; | |
3513 | RandomizedHarnessTest(part, total); | |
3514 | } | |
3515 | ||
3516 | TEST_F(HarnessTest, Randomized5) { | |
3517 | // part 5 out of 8 | |
3518 | const size_t part = 5; | |
3519 | const size_t total = 8; | |
3520 | RandomizedHarnessTest(part, total); | |
3521 | } | |
3522 | ||
3523 | TEST_F(HarnessTest, Randomized6) { | |
3524 | // part 6 out of 8 | |
3525 | const size_t part = 6; | |
3526 | const size_t total = 8; | |
3527 | RandomizedHarnessTest(part, total); | |
3528 | } | |
3529 | ||
3530 | TEST_F(HarnessTest, Randomized7) { | |
3531 | // part 7 out of 8 | |
3532 | const size_t part = 7; | |
3533 | const size_t total = 8; | |
3534 | RandomizedHarnessTest(part, total); | |
3535 | } | |
3536 | ||
3537 | TEST_F(HarnessTest, Randomized8) { | |
3538 | // part 8 out of 8 | |
3539 | const size_t part = 8; | |
3540 | const size_t total = 8; | |
3541 | RandomizedHarnessTest(part, total); | |
7c673cae FG |
3542 | } |
3543 | ||
3544 | #ifndef ROCKSDB_LITE | |
3545 | TEST_F(HarnessTest, RandomizedLongDB) { | |
3546 | Random rnd(test::RandomSeed()); | |
3547 | TestArgs args = {DB_TEST, false, 16, kNoCompression, 0, false}; | |
3548 | Init(args); | |
3549 | int num_entries = 100000; | |
3550 | for (int e = 0; e < num_entries; e++) { | |
3551 | std::string v; | |
3552 | Add(test::RandomKey(&rnd, rnd.Skewed(4)), | |
3553 | test::RandomString(&rnd, rnd.Skewed(5), &v).ToString()); | |
3554 | } | |
3555 | Test(&rnd); | |
3556 | ||
3557 | // We must have created enough data to force merging | |
3558 | int files = 0; | |
3559 | for (int level = 0; level < db()->NumberLevels(); level++) { | |
3560 | std::string value; | |
3561 | char name[100]; | |
3562 | snprintf(name, sizeof(name), "rocksdb.num-files-at-level%d", level); | |
3563 | ASSERT_TRUE(db()->GetProperty(name, &value)); | |
3564 | files += atoi(value.c_str()); | |
3565 | } | |
3566 | ASSERT_GT(files, 0); | |
3567 | } | |
3568 | #endif // ROCKSDB_LITE | |
494da23a | 3569 | #endif // ROCKSDB_VALGRIND_RUN |
7c673cae FG |
3570 | |
3571 | class MemTableTest : public testing::Test {}; | |
3572 | ||
3573 | TEST_F(MemTableTest, Simple) { | |
3574 | InternalKeyComparator cmp(BytewiseComparator()); | |
3575 | auto table_factory = std::make_shared<SkipListFactory>(); | |
3576 | Options options; | |
3577 | options.memtable_factory = table_factory; | |
3578 | ImmutableCFOptions ioptions(options); | |
3579 | WriteBufferManager wb(options.db_write_buffer_size); | |
11fdf7f2 TL |
3580 | MemTable* memtable = |
3581 | new MemTable(cmp, ioptions, MutableCFOptions(options), &wb, | |
3582 | kMaxSequenceNumber, 0 /* column_family_id */); | |
7c673cae FG |
3583 | memtable->Ref(); |
3584 | WriteBatch batch; | |
3585 | WriteBatchInternal::SetSequence(&batch, 100); | |
3586 | batch.Put(std::string("k1"), std::string("v1")); | |
3587 | batch.Put(std::string("k2"), std::string("v2")); | |
3588 | batch.Put(std::string("k3"), std::string("v3")); | |
3589 | batch.Put(std::string("largekey"), std::string("vlarge")); | |
3590 | batch.DeleteRange(std::string("chi"), std::string("xigua")); | |
3591 | batch.DeleteRange(std::string("begin"), std::string("end")); | |
3592 | ColumnFamilyMemTablesDefault cf_mems_default(memtable); | |
3593 | ASSERT_TRUE( | |
f67539c2 TL |
3594 | WriteBatchInternal::InsertInto(&batch, &cf_mems_default, nullptr, nullptr) |
3595 | .ok()); | |
7c673cae FG |
3596 | |
3597 | for (int i = 0; i < 2; ++i) { | |
3598 | Arena arena; | |
3599 | ScopedArenaIterator arena_iter_guard; | |
3600 | std::unique_ptr<InternalIterator> iter_guard; | |
3601 | InternalIterator* iter; | |
3602 | if (i == 0) { | |
3603 | iter = memtable->NewIterator(ReadOptions(), &arena); | |
3604 | arena_iter_guard.set(iter); | |
3605 | } else { | |
494da23a TL |
3606 | iter = memtable->NewRangeTombstoneIterator( |
3607 | ReadOptions(), kMaxSequenceNumber /* read_seq */); | |
7c673cae FG |
3608 | iter_guard.reset(iter); |
3609 | } | |
3610 | if (iter == nullptr) { | |
3611 | continue; | |
3612 | } | |
3613 | iter->SeekToFirst(); | |
3614 | while (iter->Valid()) { | |
3615 | fprintf(stderr, "key: '%s' -> '%s'\n", iter->key().ToString().c_str(), | |
3616 | iter->value().ToString().c_str()); | |
3617 | iter->Next(); | |
3618 | } | |
3619 | } | |
3620 | ||
3621 | delete memtable->Unref(); | |
3622 | } | |
3623 | ||
3624 | // Test the empty key | |
3625 | TEST_F(HarnessTest, SimpleEmptyKey) { | |
3626 | auto args = GenerateArgList(); | |
3627 | for (const auto& arg : args) { | |
3628 | Init(arg); | |
3629 | Random rnd(test::RandomSeed() + 1); | |
3630 | Add("", "v"); | |
3631 | Test(&rnd); | |
3632 | } | |
3633 | } | |
3634 | ||
3635 | TEST_F(HarnessTest, SimpleSingle) { | |
3636 | auto args = GenerateArgList(); | |
3637 | for (const auto& arg : args) { | |
3638 | Init(arg); | |
3639 | Random rnd(test::RandomSeed() + 2); | |
3640 | Add("abc", "v"); | |
3641 | Test(&rnd); | |
3642 | } | |
3643 | } | |
3644 | ||
3645 | TEST_F(HarnessTest, SimpleMulti) { | |
3646 | auto args = GenerateArgList(); | |
3647 | for (const auto& arg : args) { | |
3648 | Init(arg); | |
3649 | Random rnd(test::RandomSeed() + 3); | |
3650 | Add("abc", "v"); | |
3651 | Add("abcd", "v"); | |
3652 | Add("ac", "v2"); | |
3653 | Test(&rnd); | |
3654 | } | |
3655 | } | |
3656 | ||
3657 | TEST_F(HarnessTest, SimpleSpecialKey) { | |
3658 | auto args = GenerateArgList(); | |
3659 | for (const auto& arg : args) { | |
3660 | Init(arg); | |
3661 | Random rnd(test::RandomSeed() + 4); | |
3662 | Add("\xff\xff", "v3"); | |
3663 | Test(&rnd); | |
3664 | } | |
3665 | } | |
3666 | ||
3667 | TEST_F(HarnessTest, FooterTests) { | |
3668 | { | |
3669 | // upconvert legacy block based | |
3670 | std::string encoded; | |
3671 | Footer footer(kLegacyBlockBasedTableMagicNumber, 0); | |
3672 | BlockHandle meta_index(10, 5), index(20, 15); | |
3673 | footer.set_metaindex_handle(meta_index); | |
3674 | footer.set_index_handle(index); | |
3675 | footer.EncodeTo(&encoded); | |
3676 | Footer decoded_footer; | |
3677 | Slice encoded_slice(encoded); | |
3678 | decoded_footer.DecodeFrom(&encoded_slice); | |
3679 | ASSERT_EQ(decoded_footer.table_magic_number(), kBlockBasedTableMagicNumber); | |
3680 | ASSERT_EQ(decoded_footer.checksum(), kCRC32c); | |
3681 | ASSERT_EQ(decoded_footer.metaindex_handle().offset(), meta_index.offset()); | |
3682 | ASSERT_EQ(decoded_footer.metaindex_handle().size(), meta_index.size()); | |
3683 | ASSERT_EQ(decoded_footer.index_handle().offset(), index.offset()); | |
3684 | ASSERT_EQ(decoded_footer.index_handle().size(), index.size()); | |
3685 | ASSERT_EQ(decoded_footer.version(), 0U); | |
3686 | } | |
3687 | { | |
3688 | // xxhash block based | |
3689 | std::string encoded; | |
3690 | Footer footer(kBlockBasedTableMagicNumber, 1); | |
3691 | BlockHandle meta_index(10, 5), index(20, 15); | |
3692 | footer.set_metaindex_handle(meta_index); | |
3693 | footer.set_index_handle(index); | |
3694 | footer.set_checksum(kxxHash); | |
3695 | footer.EncodeTo(&encoded); | |
3696 | Footer decoded_footer; | |
3697 | Slice encoded_slice(encoded); | |
3698 | decoded_footer.DecodeFrom(&encoded_slice); | |
3699 | ASSERT_EQ(decoded_footer.table_magic_number(), kBlockBasedTableMagicNumber); | |
3700 | ASSERT_EQ(decoded_footer.checksum(), kxxHash); | |
3701 | ASSERT_EQ(decoded_footer.metaindex_handle().offset(), meta_index.offset()); | |
3702 | ASSERT_EQ(decoded_footer.metaindex_handle().size(), meta_index.size()); | |
3703 | ASSERT_EQ(decoded_footer.index_handle().offset(), index.offset()); | |
3704 | ASSERT_EQ(decoded_footer.index_handle().size(), index.size()); | |
3705 | ASSERT_EQ(decoded_footer.version(), 1U); | |
3706 | } | |
494da23a TL |
3707 | { |
3708 | // xxhash64 block based | |
3709 | std::string encoded; | |
3710 | Footer footer(kBlockBasedTableMagicNumber, 1); | |
3711 | BlockHandle meta_index(10, 5), index(20, 15); | |
3712 | footer.set_metaindex_handle(meta_index); | |
3713 | footer.set_index_handle(index); | |
3714 | footer.set_checksum(kxxHash64); | |
3715 | footer.EncodeTo(&encoded); | |
3716 | Footer decoded_footer; | |
3717 | Slice encoded_slice(encoded); | |
3718 | decoded_footer.DecodeFrom(&encoded_slice); | |
3719 | ASSERT_EQ(decoded_footer.table_magic_number(), kBlockBasedTableMagicNumber); | |
3720 | ASSERT_EQ(decoded_footer.checksum(), kxxHash64); | |
3721 | ASSERT_EQ(decoded_footer.metaindex_handle().offset(), meta_index.offset()); | |
3722 | ASSERT_EQ(decoded_footer.metaindex_handle().size(), meta_index.size()); | |
3723 | ASSERT_EQ(decoded_footer.index_handle().offset(), index.offset()); | |
3724 | ASSERT_EQ(decoded_footer.index_handle().size(), index.size()); | |
3725 | ASSERT_EQ(decoded_footer.version(), 1U); | |
3726 | } | |
7c673cae FG |
3727 | // Plain table is not supported in ROCKSDB_LITE |
3728 | #ifndef ROCKSDB_LITE | |
3729 | { | |
3730 | // upconvert legacy plain table | |
3731 | std::string encoded; | |
3732 | Footer footer(kLegacyPlainTableMagicNumber, 0); | |
3733 | BlockHandle meta_index(10, 5), index(20, 15); | |
3734 | footer.set_metaindex_handle(meta_index); | |
3735 | footer.set_index_handle(index); | |
3736 | footer.EncodeTo(&encoded); | |
3737 | Footer decoded_footer; | |
3738 | Slice encoded_slice(encoded); | |
3739 | decoded_footer.DecodeFrom(&encoded_slice); | |
3740 | ASSERT_EQ(decoded_footer.table_magic_number(), kPlainTableMagicNumber); | |
3741 | ASSERT_EQ(decoded_footer.checksum(), kCRC32c); | |
3742 | ASSERT_EQ(decoded_footer.metaindex_handle().offset(), meta_index.offset()); | |
3743 | ASSERT_EQ(decoded_footer.metaindex_handle().size(), meta_index.size()); | |
3744 | ASSERT_EQ(decoded_footer.index_handle().offset(), index.offset()); | |
3745 | ASSERT_EQ(decoded_footer.index_handle().size(), index.size()); | |
3746 | ASSERT_EQ(decoded_footer.version(), 0U); | |
3747 | } | |
3748 | { | |
3749 | // xxhash block based | |
3750 | std::string encoded; | |
3751 | Footer footer(kPlainTableMagicNumber, 1); | |
3752 | BlockHandle meta_index(10, 5), index(20, 15); | |
3753 | footer.set_metaindex_handle(meta_index); | |
3754 | footer.set_index_handle(index); | |
3755 | footer.set_checksum(kxxHash); | |
3756 | footer.EncodeTo(&encoded); | |
3757 | Footer decoded_footer; | |
3758 | Slice encoded_slice(encoded); | |
3759 | decoded_footer.DecodeFrom(&encoded_slice); | |
3760 | ASSERT_EQ(decoded_footer.table_magic_number(), kPlainTableMagicNumber); | |
3761 | ASSERT_EQ(decoded_footer.checksum(), kxxHash); | |
3762 | ASSERT_EQ(decoded_footer.metaindex_handle().offset(), meta_index.offset()); | |
3763 | ASSERT_EQ(decoded_footer.metaindex_handle().size(), meta_index.size()); | |
3764 | ASSERT_EQ(decoded_footer.index_handle().offset(), index.offset()); | |
3765 | ASSERT_EQ(decoded_footer.index_handle().size(), index.size()); | |
3766 | ASSERT_EQ(decoded_footer.version(), 1U); | |
3767 | } | |
3768 | #endif // !ROCKSDB_LITE | |
3769 | { | |
3770 | // version == 2 | |
3771 | std::string encoded; | |
3772 | Footer footer(kBlockBasedTableMagicNumber, 2); | |
3773 | BlockHandle meta_index(10, 5), index(20, 15); | |
3774 | footer.set_metaindex_handle(meta_index); | |
3775 | footer.set_index_handle(index); | |
3776 | footer.EncodeTo(&encoded); | |
3777 | Footer decoded_footer; | |
3778 | Slice encoded_slice(encoded); | |
3779 | decoded_footer.DecodeFrom(&encoded_slice); | |
3780 | ASSERT_EQ(decoded_footer.table_magic_number(), kBlockBasedTableMagicNumber); | |
3781 | ASSERT_EQ(decoded_footer.checksum(), kCRC32c); | |
3782 | ASSERT_EQ(decoded_footer.metaindex_handle().offset(), meta_index.offset()); | |
3783 | ASSERT_EQ(decoded_footer.metaindex_handle().size(), meta_index.size()); | |
3784 | ASSERT_EQ(decoded_footer.index_handle().offset(), index.offset()); | |
3785 | ASSERT_EQ(decoded_footer.index_handle().size(), index.size()); | |
3786 | ASSERT_EQ(decoded_footer.version(), 2U); | |
3787 | } | |
3788 | } | |
3789 | ||
3790 | class IndexBlockRestartIntervalTest | |
11fdf7f2 TL |
3791 | : public TableTest, |
3792 | public ::testing::WithParamInterface<std::pair<int, bool>> { | |
7c673cae | 3793 | public: |
11fdf7f2 TL |
3794 | static std::vector<std::pair<int, bool>> GetRestartValues() { |
3795 | return {{-1, false}, {0, false}, {1, false}, {8, false}, | |
3796 | {16, false}, {32, false}, {-1, true}, {0, true}, | |
3797 | {1, true}, {8, true}, {16, true}, {32, true}}; | |
3798 | } | |
7c673cae FG |
3799 | }; |
3800 | ||
3801 | INSTANTIATE_TEST_CASE_P( | |
3802 | IndexBlockRestartIntervalTest, IndexBlockRestartIntervalTest, | |
3803 | ::testing::ValuesIn(IndexBlockRestartIntervalTest::GetRestartValues())); | |
3804 | ||
3805 | TEST_P(IndexBlockRestartIntervalTest, IndexBlockRestartInterval) { | |
3806 | const int kKeysInTable = 10000; | |
3807 | const int kKeySize = 100; | |
3808 | const int kValSize = 500; | |
3809 | ||
11fdf7f2 TL |
3810 | const int index_block_restart_interval = std::get<0>(GetParam()); |
3811 | const bool value_delta_encoding = std::get<1>(GetParam()); | |
7c673cae FG |
3812 | |
3813 | Options options; | |
3814 | BlockBasedTableOptions table_options; | |
3815 | table_options.block_size = 64; // small block size to get big index block | |
3816 | table_options.index_block_restart_interval = index_block_restart_interval; | |
11fdf7f2 TL |
3817 | if (value_delta_encoding) { |
3818 | table_options.format_version = 4; | |
3819 | } | |
7c673cae FG |
3820 | options.table_factory.reset(new BlockBasedTableFactory(table_options)); |
3821 | ||
3822 | TableConstructor c(BytewiseComparator()); | |
3823 | static Random rnd(301); | |
3824 | for (int i = 0; i < kKeysInTable; i++) { | |
3825 | InternalKey k(RandomString(&rnd, kKeySize), 0, kTypeValue); | |
3826 | c.Add(k.Encode().ToString(), RandomString(&rnd, kValSize)); | |
3827 | } | |
3828 | ||
3829 | std::vector<std::string> keys; | |
3830 | stl_wrappers::KVMap kvmap; | |
3831 | std::unique_ptr<InternalKeyComparator> comparator( | |
3832 | new InternalKeyComparator(BytewiseComparator())); | |
3833 | const ImmutableCFOptions ioptions(options); | |
11fdf7f2 TL |
3834 | const MutableCFOptions moptions(options); |
3835 | c.Finish(options, ioptions, moptions, table_options, *comparator, &keys, | |
3836 | &kvmap); | |
7c673cae FG |
3837 | auto reader = c.GetTableReader(); |
3838 | ||
f67539c2 TL |
3839 | std::unique_ptr<InternalIterator> db_iter(reader->NewIterator( |
3840 | ReadOptions(), moptions.prefix_extractor.get(), /*arena=*/nullptr, | |
3841 | /*skip_filters=*/false, TableReaderCaller::kUncategorized)); | |
7c673cae FG |
3842 | |
3843 | // Test point lookup | |
3844 | for (auto& kv : kvmap) { | |
3845 | db_iter->Seek(kv.first); | |
3846 | ||
3847 | ASSERT_TRUE(db_iter->Valid()); | |
3848 | ASSERT_OK(db_iter->status()); | |
3849 | ASSERT_EQ(db_iter->key(), kv.first); | |
3850 | ASSERT_EQ(db_iter->value(), kv.second); | |
3851 | } | |
3852 | ||
3853 | // Test iterating | |
3854 | auto kv_iter = kvmap.begin(); | |
3855 | for (db_iter->SeekToFirst(); db_iter->Valid(); db_iter->Next()) { | |
3856 | ASSERT_EQ(db_iter->key(), kv_iter->first); | |
3857 | ASSERT_EQ(db_iter->value(), kv_iter->second); | |
3858 | kv_iter++; | |
3859 | } | |
3860 | ASSERT_EQ(kv_iter, kvmap.end()); | |
3861 | c.ResetTableReader(); | |
3862 | } | |
3863 | ||
3864 | class PrefixTest : public testing::Test { | |
3865 | public: | |
3866 | PrefixTest() : testing::Test() {} | |
494da23a | 3867 | ~PrefixTest() override {} |
7c673cae FG |
3868 | }; |
3869 | ||
3870 | namespace { | |
3871 | // A simple PrefixExtractor that only works for test PrefixAndWholeKeyTest | |
f67539c2 | 3872 | class TestPrefixExtractor : public ROCKSDB_NAMESPACE::SliceTransform { |
7c673cae FG |
3873 | public: |
3874 | ~TestPrefixExtractor() override{}; | |
3875 | const char* Name() const override { return "TestPrefixExtractor"; } | |
3876 | ||
f67539c2 TL |
3877 | ROCKSDB_NAMESPACE::Slice Transform( |
3878 | const ROCKSDB_NAMESPACE::Slice& src) const override { | |
7c673cae | 3879 | assert(IsValid(src)); |
f67539c2 | 3880 | return ROCKSDB_NAMESPACE::Slice(src.data(), 3); |
7c673cae FG |
3881 | } |
3882 | ||
f67539c2 | 3883 | bool InDomain(const ROCKSDB_NAMESPACE::Slice& src) const override { |
7c673cae FG |
3884 | assert(IsValid(src)); |
3885 | return true; | |
3886 | } | |
3887 | ||
f67539c2 TL |
3888 | bool InRange(const ROCKSDB_NAMESPACE::Slice& /*dst*/) const override { |
3889 | return true; | |
3890 | } | |
7c673cae | 3891 | |
f67539c2 | 3892 | bool IsValid(const ROCKSDB_NAMESPACE::Slice& src) const { |
7c673cae FG |
3893 | if (src.size() != 4) { |
3894 | return false; | |
3895 | } | |
3896 | if (src[0] != '[') { | |
3897 | return false; | |
3898 | } | |
3899 | if (src[1] < '0' || src[1] > '9') { | |
3900 | return false; | |
3901 | } | |
3902 | if (src[2] != ']') { | |
3903 | return false; | |
3904 | } | |
3905 | if (src[3] < '0' || src[3] > '9') { | |
3906 | return false; | |
3907 | } | |
3908 | return true; | |
3909 | } | |
3910 | }; | |
3911 | } // namespace | |
3912 | ||
3913 | TEST_F(PrefixTest, PrefixAndWholeKeyTest) { | |
f67539c2 TL |
3914 | ROCKSDB_NAMESPACE::Options options; |
3915 | options.compaction_style = ROCKSDB_NAMESPACE::kCompactionStyleUniversal; | |
7c673cae FG |
3916 | options.num_levels = 20; |
3917 | options.create_if_missing = true; | |
3918 | options.optimize_filters_for_hits = false; | |
3919 | options.target_file_size_base = 268435456; | |
3920 | options.prefix_extractor = std::make_shared<TestPrefixExtractor>(); | |
f67539c2 TL |
3921 | ROCKSDB_NAMESPACE::BlockBasedTableOptions bbto; |
3922 | bbto.filter_policy.reset(ROCKSDB_NAMESPACE::NewBloomFilterPolicy(10)); | |
7c673cae FG |
3923 | bbto.block_size = 262144; |
3924 | bbto.whole_key_filtering = true; | |
3925 | ||
11fdf7f2 | 3926 | const std::string kDBPath = test::PerThreadDBPath("table_prefix_test"); |
7c673cae FG |
3927 | options.table_factory.reset(NewBlockBasedTableFactory(bbto)); |
3928 | DestroyDB(kDBPath, options); | |
f67539c2 TL |
3929 | ROCKSDB_NAMESPACE::DB* db; |
3930 | ASSERT_OK(ROCKSDB_NAMESPACE::DB::Open(options, kDBPath, &db)); | |
7c673cae FG |
3931 | |
3932 | // Create a bunch of keys with 10 filters. | |
3933 | for (int i = 0; i < 10; i++) { | |
3934 | std::string prefix = "[" + std::to_string(i) + "]"; | |
3935 | for (int j = 0; j < 10; j++) { | |
3936 | std::string key = prefix + std::to_string(j); | |
f67539c2 | 3937 | db->Put(ROCKSDB_NAMESPACE::WriteOptions(), key, "1"); |
7c673cae FG |
3938 | } |
3939 | } | |
3940 | ||
3941 | // Trigger compaction. | |
3942 | db->CompactRange(CompactRangeOptions(), nullptr, nullptr); | |
3943 | delete db; | |
3944 | // In the second round, turn whole_key_filtering off and expect | |
3945 | // rocksdb still works. | |
3946 | } | |
3947 | ||
11fdf7f2 TL |
3948 | /* |
3949 | * Disable TableWithGlobalSeqno since RocksDB does not store global_seqno in | |
3950 | * the SST file any more. Instead, RocksDB deduces global_seqno from the | |
3951 | * MANIFEST while reading from an SST. Therefore, it's not possible to test the | |
3952 | * functionality of global_seqno in a single, isolated unit test without the | |
3953 | * involvement of Version, VersionSet, etc. | |
3954 | */ | |
3955 | TEST_P(BlockBasedTableTest, DISABLED_TableWithGlobalSeqno) { | |
3956 | BlockBasedTableOptions bbto = GetBlockBasedTableOptions(); | |
7c673cae | 3957 | test::StringSink* sink = new test::StringSink(); |
494da23a | 3958 | std::unique_ptr<WritableFileWriter> file_writer( |
11fdf7f2 | 3959 | test::GetWritableFileWriter(sink, "" /* don't care */)); |
7c673cae FG |
3960 | Options options; |
3961 | options.table_factory.reset(NewBlockBasedTableFactory(bbto)); | |
3962 | const ImmutableCFOptions ioptions(options); | |
11fdf7f2 | 3963 | const MutableCFOptions moptions(options); |
7c673cae FG |
3964 | InternalKeyComparator ikc(options.comparator); |
3965 | std::vector<std::unique_ptr<IntTblPropCollectorFactory>> | |
3966 | int_tbl_prop_collector_factories; | |
3967 | int_tbl_prop_collector_factories.emplace_back( | |
3968 | new SstFileWriterPropertiesCollectorFactory(2 /* version */, | |
3969 | 0 /* global_seqno*/)); | |
3970 | std::string column_family_name; | |
3971 | std::unique_ptr<TableBuilder> builder(options.table_factory->NewTableBuilder( | |
11fdf7f2 TL |
3972 | TableBuilderOptions(ioptions, moptions, ikc, |
3973 | &int_tbl_prop_collector_factories, kNoCompression, | |
494da23a | 3974 | 0 /* sample_for_compression */, CompressionOptions(), |
7c673cae FG |
3975 | false /* skip_filters */, column_family_name, -1), |
3976 | TablePropertiesCollectorFactory::Context::kUnknownColumnFamily, | |
3977 | file_writer.get())); | |
3978 | ||
3979 | for (char c = 'a'; c <= 'z'; ++c) { | |
3980 | std::string key(8, c); | |
3981 | std::string value = key; | |
3982 | InternalKey ik(key, 0, kTypeValue); | |
3983 | ||
3984 | builder->Add(ik.Encode(), value); | |
3985 | } | |
3986 | ASSERT_OK(builder->Finish()); | |
3987 | file_writer->Flush(); | |
3988 | ||
3989 | test::RandomRWStringSink ss_rw(sink); | |
3990 | uint32_t version; | |
3991 | uint64_t global_seqno; | |
3992 | uint64_t global_seqno_offset; | |
3993 | ||
3994 | // Helper function to get version, global_seqno, global_seqno_offset | |
3995 | std::function<void()> GetVersionAndGlobalSeqno = [&]() { | |
494da23a | 3996 | std::unique_ptr<RandomAccessFileReader> file_reader( |
7c673cae FG |
3997 | test::GetRandomAccessFileReader( |
3998 | new test::StringSource(ss_rw.contents(), 73342, true))); | |
3999 | ||
4000 | TableProperties* props = nullptr; | |
4001 | ASSERT_OK(ReadTableProperties(file_reader.get(), ss_rw.contents().size(), | |
4002 | kBlockBasedTableMagicNumber, ioptions, | |
11fdf7f2 | 4003 | &props, true /* compression_type_missing */)); |
7c673cae FG |
4004 | |
4005 | UserCollectedProperties user_props = props->user_collected_properties; | |
4006 | version = DecodeFixed32( | |
4007 | user_props[ExternalSstFilePropertyNames::kVersion].c_str()); | |
4008 | global_seqno = DecodeFixed64( | |
4009 | user_props[ExternalSstFilePropertyNames::kGlobalSeqno].c_str()); | |
4010 | global_seqno_offset = | |
4011 | props->properties_offsets[ExternalSstFilePropertyNames::kGlobalSeqno]; | |
4012 | ||
4013 | delete props; | |
4014 | }; | |
4015 | ||
4016 | // Helper function to update the value of the global seqno in the file | |
4017 | std::function<void(uint64_t)> SetGlobalSeqno = [&](uint64_t val) { | |
4018 | std::string new_global_seqno; | |
4019 | PutFixed64(&new_global_seqno, val); | |
4020 | ||
4021 | ASSERT_OK(ss_rw.Write(global_seqno_offset, new_global_seqno)); | |
4022 | }; | |
4023 | ||
4024 | // Helper function to get the contents of the table InternalIterator | |
494da23a | 4025 | std::unique_ptr<TableReader> table_reader; |
7c673cae | 4026 | std::function<InternalIterator*()> GetTableInternalIter = [&]() { |
494da23a | 4027 | std::unique_ptr<RandomAccessFileReader> file_reader( |
7c673cae FG |
4028 | test::GetRandomAccessFileReader( |
4029 | new test::StringSource(ss_rw.contents(), 73342, true))); | |
4030 | ||
4031 | options.table_factory->NewTableReader( | |
11fdf7f2 TL |
4032 | TableReaderOptions(ioptions, moptions.prefix_extractor.get(), |
4033 | EnvOptions(), ikc), | |
4034 | std::move(file_reader), ss_rw.contents().size(), &table_reader); | |
7c673cae | 4035 | |
f67539c2 TL |
4036 | return table_reader->NewIterator( |
4037 | ReadOptions(), moptions.prefix_extractor.get(), /*arena=*/nullptr, | |
4038 | /*skip_filters=*/false, TableReaderCaller::kUncategorized); | |
7c673cae FG |
4039 | }; |
4040 | ||
4041 | GetVersionAndGlobalSeqno(); | |
f67539c2 TL |
4042 | ASSERT_EQ(2u, version); |
4043 | ASSERT_EQ(0u, global_seqno); | |
7c673cae FG |
4044 | |
4045 | InternalIterator* iter = GetTableInternalIter(); | |
4046 | char current_c = 'a'; | |
4047 | for (iter->SeekToFirst(); iter->Valid(); iter->Next()) { | |
4048 | ParsedInternalKey pik; | |
4049 | ASSERT_TRUE(ParseInternalKey(iter->key(), &pik)); | |
4050 | ||
4051 | ASSERT_EQ(pik.type, ValueType::kTypeValue); | |
4052 | ASSERT_EQ(pik.sequence, 0); | |
4053 | ASSERT_EQ(pik.user_key, iter->value()); | |
4054 | ASSERT_EQ(pik.user_key.ToString(), std::string(8, current_c)); | |
4055 | current_c++; | |
4056 | } | |
4057 | ASSERT_EQ(current_c, 'z' + 1); | |
4058 | delete iter; | |
4059 | ||
4060 | // Update global sequence number to 10 | |
4061 | SetGlobalSeqno(10); | |
4062 | GetVersionAndGlobalSeqno(); | |
f67539c2 TL |
4063 | ASSERT_EQ(2u, version); |
4064 | ASSERT_EQ(10u, global_seqno); | |
7c673cae FG |
4065 | |
4066 | iter = GetTableInternalIter(); | |
4067 | current_c = 'a'; | |
4068 | for (iter->SeekToFirst(); iter->Valid(); iter->Next()) { | |
4069 | ParsedInternalKey pik; | |
4070 | ASSERT_TRUE(ParseInternalKey(iter->key(), &pik)); | |
4071 | ||
4072 | ASSERT_EQ(pik.type, ValueType::kTypeValue); | |
4073 | ASSERT_EQ(pik.sequence, 10); | |
4074 | ASSERT_EQ(pik.user_key, iter->value()); | |
4075 | ASSERT_EQ(pik.user_key.ToString(), std::string(8, current_c)); | |
4076 | current_c++; | |
4077 | } | |
4078 | ASSERT_EQ(current_c, 'z' + 1); | |
4079 | ||
4080 | // Verify Seek | |
4081 | for (char c = 'a'; c <= 'z'; c++) { | |
4082 | std::string k = std::string(8, c); | |
4083 | InternalKey ik(k, 10, kValueTypeForSeek); | |
4084 | iter->Seek(ik.Encode()); | |
4085 | ASSERT_TRUE(iter->Valid()); | |
4086 | ||
4087 | ParsedInternalKey pik; | |
4088 | ASSERT_TRUE(ParseInternalKey(iter->key(), &pik)); | |
4089 | ||
4090 | ASSERT_EQ(pik.type, ValueType::kTypeValue); | |
4091 | ASSERT_EQ(pik.sequence, 10); | |
4092 | ASSERT_EQ(pik.user_key.ToString(), k); | |
4093 | ASSERT_EQ(iter->value().ToString(), k); | |
4094 | } | |
4095 | delete iter; | |
4096 | ||
4097 | // Update global sequence number to 3 | |
4098 | SetGlobalSeqno(3); | |
4099 | GetVersionAndGlobalSeqno(); | |
f67539c2 TL |
4100 | ASSERT_EQ(2u, version); |
4101 | ASSERT_EQ(3u, global_seqno); | |
7c673cae FG |
4102 | |
4103 | iter = GetTableInternalIter(); | |
4104 | current_c = 'a'; | |
4105 | for (iter->SeekToFirst(); iter->Valid(); iter->Next()) { | |
4106 | ParsedInternalKey pik; | |
4107 | ASSERT_TRUE(ParseInternalKey(iter->key(), &pik)); | |
4108 | ||
4109 | ASSERT_EQ(pik.type, ValueType::kTypeValue); | |
4110 | ASSERT_EQ(pik.sequence, 3); | |
4111 | ASSERT_EQ(pik.user_key, iter->value()); | |
4112 | ASSERT_EQ(pik.user_key.ToString(), std::string(8, current_c)); | |
4113 | current_c++; | |
4114 | } | |
4115 | ASSERT_EQ(current_c, 'z' + 1); | |
4116 | ||
4117 | // Verify Seek | |
4118 | for (char c = 'a'; c <= 'z'; c++) { | |
4119 | std::string k = std::string(8, c); | |
4120 | // seqno=4 is less than 3 so we still should get our key | |
4121 | InternalKey ik(k, 4, kValueTypeForSeek); | |
4122 | iter->Seek(ik.Encode()); | |
4123 | ASSERT_TRUE(iter->Valid()); | |
4124 | ||
4125 | ParsedInternalKey pik; | |
4126 | ASSERT_TRUE(ParseInternalKey(iter->key(), &pik)); | |
4127 | ||
4128 | ASSERT_EQ(pik.type, ValueType::kTypeValue); | |
4129 | ASSERT_EQ(pik.sequence, 3); | |
4130 | ASSERT_EQ(pik.user_key.ToString(), k); | |
4131 | ASSERT_EQ(iter->value().ToString(), k); | |
4132 | } | |
4133 | ||
4134 | delete iter; | |
4135 | } | |
4136 | ||
11fdf7f2 TL |
4137 | TEST_P(BlockBasedTableTest, BlockAlignTest) { |
4138 | BlockBasedTableOptions bbto = GetBlockBasedTableOptions(); | |
4139 | bbto.block_align = true; | |
4140 | test::StringSink* sink = new test::StringSink(); | |
494da23a | 4141 | std::unique_ptr<WritableFileWriter> file_writer( |
11fdf7f2 TL |
4142 | test::GetWritableFileWriter(sink, "" /* don't care */)); |
4143 | Options options; | |
4144 | options.compression = kNoCompression; | |
4145 | options.table_factory.reset(NewBlockBasedTableFactory(bbto)); | |
4146 | const ImmutableCFOptions ioptions(options); | |
4147 | const MutableCFOptions moptions(options); | |
4148 | InternalKeyComparator ikc(options.comparator); | |
4149 | std::vector<std::unique_ptr<IntTblPropCollectorFactory>> | |
4150 | int_tbl_prop_collector_factories; | |
4151 | std::string column_family_name; | |
4152 | std::unique_ptr<TableBuilder> builder(options.table_factory->NewTableBuilder( | |
4153 | TableBuilderOptions(ioptions, moptions, ikc, | |
4154 | &int_tbl_prop_collector_factories, kNoCompression, | |
494da23a | 4155 | 0 /* sample_for_compression */, CompressionOptions(), |
11fdf7f2 TL |
4156 | false /* skip_filters */, column_family_name, -1), |
4157 | TablePropertiesCollectorFactory::Context::kUnknownColumnFamily, | |
4158 | file_writer.get())); | |
4159 | ||
4160 | for (int i = 1; i <= 10000; ++i) { | |
4161 | std::ostringstream ostr; | |
4162 | ostr << std::setfill('0') << std::setw(5) << i; | |
4163 | std::string key = ostr.str(); | |
4164 | std::string value = "val"; | |
4165 | InternalKey ik(key, 0, kTypeValue); | |
4166 | ||
4167 | builder->Add(ik.Encode(), value); | |
4168 | } | |
4169 | ASSERT_OK(builder->Finish()); | |
4170 | file_writer->Flush(); | |
4171 | ||
4172 | test::RandomRWStringSink ss_rw(sink); | |
494da23a | 4173 | std::unique_ptr<RandomAccessFileReader> file_reader( |
11fdf7f2 TL |
4174 | test::GetRandomAccessFileReader( |
4175 | new test::StringSource(ss_rw.contents(), 73342, true))); | |
4176 | ||
4177 | // Helper function to get version, global_seqno, global_seqno_offset | |
4178 | std::function<void()> VerifyBlockAlignment = [&]() { | |
4179 | TableProperties* props = nullptr; | |
4180 | ASSERT_OK(ReadTableProperties(file_reader.get(), ss_rw.contents().size(), | |
4181 | kBlockBasedTableMagicNumber, ioptions, | |
4182 | &props, true /* compression_type_missing */)); | |
4183 | ||
4184 | uint64_t data_block_size = props->data_size / props->num_data_blocks; | |
4185 | ASSERT_EQ(data_block_size, 4096); | |
4186 | ASSERT_EQ(props->data_size, data_block_size * props->num_data_blocks); | |
4187 | delete props; | |
4188 | }; | |
4189 | ||
4190 | VerifyBlockAlignment(); | |
4191 | ||
4192 | // The below block of code verifies that we can read back the keys. Set | |
4193 | // block_align to false when creating the reader to ensure we can flip between | |
4194 | // the two modes without any issues | |
4195 | std::unique_ptr<TableReader> table_reader; | |
4196 | bbto.block_align = false; | |
4197 | Options options2; | |
4198 | options2.table_factory.reset(NewBlockBasedTableFactory(bbto)); | |
4199 | ImmutableCFOptions ioptions2(options2); | |
4200 | const MutableCFOptions moptions2(options2); | |
4201 | ||
4202 | ASSERT_OK(ioptions.table_factory->NewTableReader( | |
4203 | TableReaderOptions(ioptions2, moptions2.prefix_extractor.get(), | |
4204 | EnvOptions(), | |
4205 | GetPlainInternalComparator(options2.comparator)), | |
4206 | std::move(file_reader), ss_rw.contents().size(), &table_reader)); | |
4207 | ||
4208 | std::unique_ptr<InternalIterator> db_iter(table_reader->NewIterator( | |
f67539c2 TL |
4209 | ReadOptions(), moptions2.prefix_extractor.get(), /*arena=*/nullptr, |
4210 | /*skip_filters=*/false, TableReaderCaller::kUncategorized)); | |
11fdf7f2 TL |
4211 | |
4212 | int expected_key = 1; | |
4213 | for (db_iter->SeekToFirst(); db_iter->Valid(); db_iter->Next()) { | |
4214 | std::ostringstream ostr; | |
4215 | ostr << std::setfill('0') << std::setw(5) << expected_key++; | |
4216 | std::string key = ostr.str(); | |
4217 | std::string value = "val"; | |
4218 | ||
4219 | ASSERT_OK(db_iter->status()); | |
4220 | ASSERT_EQ(ExtractUserKey(db_iter->key()).ToString(), key); | |
4221 | ASSERT_EQ(db_iter->value().ToString(), value); | |
4222 | } | |
4223 | expected_key--; | |
4224 | ASSERT_EQ(expected_key, 10000); | |
4225 | table_reader.reset(); | |
4226 | } | |
4227 | ||
4228 | TEST_P(BlockBasedTableTest, PropertiesBlockRestartPointTest) { | |
4229 | BlockBasedTableOptions bbto = GetBlockBasedTableOptions(); | |
4230 | bbto.block_align = true; | |
4231 | test::StringSink* sink = new test::StringSink(); | |
494da23a | 4232 | std::unique_ptr<WritableFileWriter> file_writer( |
11fdf7f2 TL |
4233 | test::GetWritableFileWriter(sink, "" /* don't care */)); |
4234 | ||
4235 | Options options; | |
4236 | options.compression = kNoCompression; | |
4237 | options.table_factory.reset(NewBlockBasedTableFactory(bbto)); | |
4238 | ||
4239 | const ImmutableCFOptions ioptions(options); | |
4240 | const MutableCFOptions moptions(options); | |
4241 | InternalKeyComparator ikc(options.comparator); | |
4242 | std::vector<std::unique_ptr<IntTblPropCollectorFactory>> | |
4243 | int_tbl_prop_collector_factories; | |
4244 | std::string column_family_name; | |
4245 | ||
4246 | std::unique_ptr<TableBuilder> builder(options.table_factory->NewTableBuilder( | |
4247 | TableBuilderOptions(ioptions, moptions, ikc, | |
4248 | &int_tbl_prop_collector_factories, kNoCompression, | |
494da23a | 4249 | 0 /* sample_for_compression */, CompressionOptions(), |
11fdf7f2 TL |
4250 | false /* skip_filters */, column_family_name, -1), |
4251 | TablePropertiesCollectorFactory::Context::kUnknownColumnFamily, | |
4252 | file_writer.get())); | |
4253 | ||
4254 | for (int i = 1; i <= 10000; ++i) { | |
4255 | std::ostringstream ostr; | |
4256 | ostr << std::setfill('0') << std::setw(5) << i; | |
4257 | std::string key = ostr.str(); | |
4258 | std::string value = "val"; | |
4259 | InternalKey ik(key, 0, kTypeValue); | |
4260 | ||
4261 | builder->Add(ik.Encode(), value); | |
4262 | } | |
4263 | ASSERT_OK(builder->Finish()); | |
4264 | file_writer->Flush(); | |
4265 | ||
4266 | test::RandomRWStringSink ss_rw(sink); | |
494da23a | 4267 | std::unique_ptr<RandomAccessFileReader> file_reader( |
11fdf7f2 TL |
4268 | test::GetRandomAccessFileReader( |
4269 | new test::StringSource(ss_rw.contents(), 73342, true))); | |
4270 | ||
4271 | { | |
4272 | RandomAccessFileReader* file = file_reader.get(); | |
4273 | uint64_t file_size = ss_rw.contents().size(); | |
4274 | ||
4275 | Footer footer; | |
4276 | ASSERT_OK(ReadFooterFromFile(file, nullptr /* prefetch_buffer */, file_size, | |
4277 | &footer, kBlockBasedTableMagicNumber)); | |
4278 | ||
f67539c2 | 4279 | auto BlockFetchHelper = [&](const BlockHandle& handle, BlockType block_type, |
11fdf7f2 TL |
4280 | BlockContents* contents) { |
4281 | ReadOptions read_options; | |
4282 | read_options.verify_checksums = false; | |
11fdf7f2 TL |
4283 | PersistentCacheOptions cache_options; |
4284 | ||
494da23a TL |
4285 | BlockFetcher block_fetcher( |
4286 | file, nullptr /* prefetch_buffer */, footer, read_options, handle, | |
4287 | contents, ioptions, false /* decompress */, | |
f67539c2 TL |
4288 | false /*maybe_compressed*/, block_type, |
4289 | UncompressionDict::GetEmptyDict(), cache_options); | |
11fdf7f2 TL |
4290 | |
4291 | ASSERT_OK(block_fetcher.ReadBlockContents()); | |
4292 | }; | |
4293 | ||
4294 | // -- Read metaindex block | |
4295 | auto metaindex_handle = footer.metaindex_handle(); | |
4296 | BlockContents metaindex_contents; | |
4297 | ||
f67539c2 TL |
4298 | BlockFetchHelper(metaindex_handle, BlockType::kMetaIndex, |
4299 | &metaindex_contents); | |
11fdf7f2 TL |
4300 | Block metaindex_block(std::move(metaindex_contents), |
4301 | kDisableGlobalSequenceNumber); | |
4302 | ||
f67539c2 TL |
4303 | std::unique_ptr<InternalIterator> meta_iter(metaindex_block.NewDataIterator( |
4304 | BytewiseComparator(), BytewiseComparator())); | |
11fdf7f2 TL |
4305 | bool found_properties_block = true; |
4306 | ASSERT_OK(SeekToPropertiesBlock(meta_iter.get(), &found_properties_block)); | |
4307 | ASSERT_TRUE(found_properties_block); | |
4308 | ||
4309 | // -- Read properties block | |
4310 | Slice v = meta_iter->value(); | |
4311 | BlockHandle properties_handle; | |
4312 | ASSERT_OK(properties_handle.DecodeFrom(&v)); | |
4313 | BlockContents properties_contents; | |
4314 | ||
f67539c2 TL |
4315 | BlockFetchHelper(properties_handle, BlockType::kProperties, |
4316 | &properties_contents); | |
11fdf7f2 TL |
4317 | Block properties_block(std::move(properties_contents), |
4318 | kDisableGlobalSequenceNumber); | |
4319 | ||
f67539c2 | 4320 | ASSERT_EQ(properties_block.NumRestarts(), 1u); |
11fdf7f2 TL |
4321 | } |
4322 | } | |
4323 | ||
4324 | TEST_P(BlockBasedTableTest, PropertiesMetaBlockLast) { | |
4325 | // The properties meta-block should come at the end since we always need to | |
4326 | // read it when opening a file, unlike index/filter/other meta-blocks, which | |
4327 | // are sometimes read depending on the user's configuration. This ordering | |
4328 | // allows us to do a small readahead on the end of the file to read properties | |
4329 | // and meta-index blocks with one I/O. | |
4330 | TableConstructor c(BytewiseComparator(), true /* convert_to_internal_key_ */); | |
4331 | c.Add("a1", "val1"); | |
4332 | c.Add("b2", "val2"); | |
4333 | c.Add("c3", "val3"); | |
4334 | c.Add("d4", "val4"); | |
4335 | c.Add("e5", "val5"); | |
4336 | c.Add("f6", "val6"); | |
4337 | c.Add("g7", "val7"); | |
4338 | c.Add("h8", "val8"); | |
4339 | c.Add("j9", "val9"); | |
4340 | ||
4341 | // write an SST file | |
4342 | Options options; | |
4343 | BlockBasedTableOptions table_options = GetBlockBasedTableOptions(); | |
4344 | table_options.filter_policy.reset(NewBloomFilterPolicy( | |
4345 | 8 /* bits_per_key */, false /* use_block_based_filter */)); | |
4346 | options.table_factory.reset(NewBlockBasedTableFactory(table_options)); | |
4347 | ImmutableCFOptions ioptions(options); | |
4348 | MutableCFOptions moptions(options); | |
4349 | std::vector<std::string> keys; | |
4350 | stl_wrappers::KVMap kvmap; | |
4351 | c.Finish(options, ioptions, moptions, table_options, | |
4352 | GetPlainInternalComparator(options.comparator), &keys, &kvmap); | |
4353 | ||
4354 | // get file reader | |
4355 | test::StringSink* table_sink = c.TEST_GetSink(); | |
4356 | std::unique_ptr<RandomAccessFileReader> table_reader{ | |
4357 | test::GetRandomAccessFileReader( | |
4358 | new test::StringSource(table_sink->contents(), 0 /* unique_id */, | |
4359 | false /* allow_mmap_reads */))}; | |
4360 | size_t table_size = table_sink->contents().size(); | |
4361 | ||
4362 | // read footer | |
4363 | Footer footer; | |
4364 | ASSERT_OK(ReadFooterFromFile(table_reader.get(), | |
4365 | nullptr /* prefetch_buffer */, table_size, | |
4366 | &footer, kBlockBasedTableMagicNumber)); | |
4367 | ||
4368 | // read metaindex | |
4369 | auto metaindex_handle = footer.metaindex_handle(); | |
4370 | BlockContents metaindex_contents; | |
11fdf7f2 TL |
4371 | PersistentCacheOptions pcache_opts; |
4372 | BlockFetcher block_fetcher( | |
4373 | table_reader.get(), nullptr /* prefetch_buffer */, footer, ReadOptions(), | |
4374 | metaindex_handle, &metaindex_contents, ioptions, false /* decompress */, | |
f67539c2 TL |
4375 | false /*maybe_compressed*/, BlockType::kMetaIndex, |
4376 | UncompressionDict::GetEmptyDict(), pcache_opts, | |
4377 | nullptr /*memory_allocator*/); | |
11fdf7f2 TL |
4378 | ASSERT_OK(block_fetcher.ReadBlockContents()); |
4379 | Block metaindex_block(std::move(metaindex_contents), | |
4380 | kDisableGlobalSequenceNumber); | |
4381 | ||
4382 | // verify properties block comes last | |
4383 | std::unique_ptr<InternalIterator> metaindex_iter{ | |
f67539c2 | 4384 | metaindex_block.NewDataIterator(options.comparator, options.comparator)}; |
11fdf7f2 TL |
4385 | uint64_t max_offset = 0; |
4386 | std::string key_at_max_offset; | |
4387 | for (metaindex_iter->SeekToFirst(); metaindex_iter->Valid(); | |
4388 | metaindex_iter->Next()) { | |
4389 | BlockHandle handle; | |
4390 | Slice value = metaindex_iter->value(); | |
4391 | ASSERT_OK(handle.DecodeFrom(&value)); | |
4392 | if (handle.offset() > max_offset) { | |
4393 | max_offset = handle.offset(); | |
4394 | key_at_max_offset = metaindex_iter->key().ToString(); | |
4395 | } | |
4396 | } | |
4397 | ASSERT_EQ(kPropertiesBlock, key_at_max_offset); | |
4398 | // index handle is stored in footer rather than metaindex block, so need | |
4399 | // separate logic to verify it comes before properties block. | |
4400 | ASSERT_GT(max_offset, footer.index_handle().offset()); | |
4401 | c.ResetTableReader(); | |
4402 | } | |
4403 | ||
4404 | TEST_P(BlockBasedTableTest, BadOptions) { | |
f67539c2 | 4405 | ROCKSDB_NAMESPACE::Options options; |
11fdf7f2 TL |
4406 | options.compression = kNoCompression; |
4407 | BlockBasedTableOptions bbto = GetBlockBasedTableOptions(); | |
4408 | bbto.block_size = 4000; | |
4409 | bbto.block_align = true; | |
4410 | ||
4411 | const std::string kDBPath = | |
4412 | test::PerThreadDBPath("block_based_table_bad_options_test"); | |
4413 | options.table_factory.reset(NewBlockBasedTableFactory(bbto)); | |
4414 | DestroyDB(kDBPath, options); | |
f67539c2 TL |
4415 | ROCKSDB_NAMESPACE::DB* db; |
4416 | ASSERT_NOK(ROCKSDB_NAMESPACE::DB::Open(options, kDBPath, &db)); | |
11fdf7f2 TL |
4417 | |
4418 | bbto.block_size = 4096; | |
4419 | options.compression = kSnappyCompression; | |
4420 | options.table_factory.reset(NewBlockBasedTableFactory(bbto)); | |
f67539c2 | 4421 | ASSERT_NOK(ROCKSDB_NAMESPACE::DB::Open(options, kDBPath, &db)); |
11fdf7f2 TL |
4422 | } |
4423 | ||
4424 | TEST_F(BBTTailPrefetchTest, TestTailPrefetchStats) { | |
4425 | TailPrefetchStats tpstats; | |
4426 | ASSERT_EQ(0, tpstats.GetSuggestedPrefetchSize()); | |
4427 | tpstats.RecordEffectiveSize(size_t{1000}); | |
4428 | tpstats.RecordEffectiveSize(size_t{1005}); | |
4429 | tpstats.RecordEffectiveSize(size_t{1002}); | |
4430 | ASSERT_EQ(1005, tpstats.GetSuggestedPrefetchSize()); | |
4431 | ||
4432 | // One single super large value shouldn't influence much | |
4433 | tpstats.RecordEffectiveSize(size_t{1002000}); | |
4434 | tpstats.RecordEffectiveSize(size_t{999}); | |
4435 | ASSERT_LE(1005, tpstats.GetSuggestedPrefetchSize()); | |
4436 | ASSERT_GT(1200, tpstats.GetSuggestedPrefetchSize()); | |
4437 | ||
4438 | // Only history of 32 is kept | |
4439 | for (int i = 0; i < 32; i++) { | |
4440 | tpstats.RecordEffectiveSize(size_t{100}); | |
4441 | } | |
4442 | ASSERT_EQ(100, tpstats.GetSuggestedPrefetchSize()); | |
4443 | ||
4444 | // 16 large values and 16 small values. The result should be closer | |
4445 | // to the small value as the algorithm. | |
4446 | for (int i = 0; i < 16; i++) { | |
4447 | tpstats.RecordEffectiveSize(size_t{1000}); | |
4448 | } | |
4449 | tpstats.RecordEffectiveSize(size_t{10}); | |
4450 | tpstats.RecordEffectiveSize(size_t{20}); | |
4451 | for (int i = 0; i < 6; i++) { | |
4452 | tpstats.RecordEffectiveSize(size_t{100}); | |
4453 | } | |
4454 | ASSERT_LE(80, tpstats.GetSuggestedPrefetchSize()); | |
4455 | ASSERT_GT(200, tpstats.GetSuggestedPrefetchSize()); | |
4456 | } | |
4457 | ||
4458 | TEST_F(BBTTailPrefetchTest, FilePrefetchBufferMinOffset) { | |
4459 | TailPrefetchStats tpstats; | |
4460 | FilePrefetchBuffer buffer(nullptr, 0, 0, false, true); | |
4461 | buffer.TryReadFromCache(500, 10, nullptr); | |
4462 | buffer.TryReadFromCache(480, 10, nullptr); | |
4463 | buffer.TryReadFromCache(490, 10, nullptr); | |
4464 | ASSERT_EQ(480, buffer.min_offset_read()); | |
4465 | } | |
4466 | ||
4467 | TEST_P(BlockBasedTableTest, DataBlockHashIndex) { | |
4468 | const int kNumKeys = 500; | |
4469 | const int kKeySize = 8; | |
4470 | const int kValSize = 40; | |
4471 | ||
4472 | BlockBasedTableOptions table_options = GetBlockBasedTableOptions(); | |
4473 | table_options.data_block_index_type = | |
4474 | BlockBasedTableOptions::kDataBlockBinaryAndHash; | |
4475 | ||
4476 | Options options; | |
4477 | options.comparator = BytewiseComparator(); | |
4478 | ||
4479 | options.table_factory.reset(new BlockBasedTableFactory(table_options)); | |
4480 | ||
4481 | TableConstructor c(options.comparator); | |
4482 | ||
4483 | static Random rnd(1048); | |
4484 | for (int i = 0; i < kNumKeys; i++) { | |
4485 | // padding one "0" to mark existent keys. | |
4486 | std::string random_key(RandomString(&rnd, kKeySize - 1) + "1"); | |
4487 | InternalKey k(random_key, 0, kTypeValue); | |
4488 | c.Add(k.Encode().ToString(), RandomString(&rnd, kValSize)); | |
4489 | } | |
4490 | ||
4491 | std::vector<std::string> keys; | |
4492 | stl_wrappers::KVMap kvmap; | |
4493 | const ImmutableCFOptions ioptions(options); | |
4494 | const MutableCFOptions moptions(options); | |
4495 | const InternalKeyComparator internal_comparator(options.comparator); | |
4496 | c.Finish(options, ioptions, moptions, table_options, internal_comparator, | |
4497 | &keys, &kvmap); | |
4498 | ||
4499 | auto reader = c.GetTableReader(); | |
4500 | ||
4501 | std::unique_ptr<InternalIterator> seek_iter; | |
f67539c2 TL |
4502 | seek_iter.reset(reader->NewIterator( |
4503 | ReadOptions(), moptions.prefix_extractor.get(), /*arena=*/nullptr, | |
4504 | /*skip_filters=*/false, TableReaderCaller::kUncategorized)); | |
11fdf7f2 TL |
4505 | for (int i = 0; i < 2; ++i) { |
4506 | ReadOptions ro; | |
4507 | // for every kv, we seek using two method: Get() and Seek() | |
4508 | // Get() will use the SuffixIndexHash in Block. For non-existent key it | |
4509 | // will invalidate the iterator | |
4510 | // Seek() will use the default BinarySeek() in Block. So for non-existent | |
4511 | // key it will land at the closest key that is large than target. | |
4512 | ||
4513 | // Search for existent keys | |
4514 | for (auto& kv : kvmap) { | |
4515 | if (i == 0) { | |
4516 | // Search using Seek() | |
4517 | seek_iter->Seek(kv.first); | |
4518 | ASSERT_OK(seek_iter->status()); | |
4519 | ASSERT_TRUE(seek_iter->Valid()); | |
4520 | ASSERT_EQ(seek_iter->key(), kv.first); | |
4521 | ASSERT_EQ(seek_iter->value(), kv.second); | |
4522 | } else { | |
4523 | // Search using Get() | |
4524 | PinnableSlice value; | |
4525 | std::string user_key = ExtractUserKey(kv.first).ToString(); | |
4526 | GetContext get_context(options.comparator, nullptr, nullptr, nullptr, | |
4527 | GetContext::kNotFound, user_key, &value, nullptr, | |
f67539c2 | 4528 | nullptr, true, nullptr, nullptr); |
11fdf7f2 TL |
4529 | ASSERT_OK(reader->Get(ro, kv.first, &get_context, |
4530 | moptions.prefix_extractor.get())); | |
4531 | ASSERT_EQ(get_context.State(), GetContext::kFound); | |
4532 | ASSERT_EQ(value, Slice(kv.second)); | |
4533 | value.Reset(); | |
4534 | } | |
4535 | } | |
4536 | ||
4537 | // Search for non-existent keys | |
4538 | for (auto& kv : kvmap) { | |
4539 | std::string user_key = ExtractUserKey(kv.first).ToString(); | |
4540 | user_key.back() = '0'; // make it non-existent key | |
4541 | InternalKey internal_key(user_key, 0, kTypeValue); | |
4542 | std::string encoded_key = internal_key.Encode().ToString(); | |
4543 | if (i == 0) { // Search using Seek() | |
4544 | seek_iter->Seek(encoded_key); | |
4545 | ASSERT_OK(seek_iter->status()); | |
4546 | if (seek_iter->Valid()) { | |
4547 | ASSERT_TRUE(BytewiseComparator()->Compare( | |
4548 | user_key, ExtractUserKey(seek_iter->key())) < 0); | |
4549 | } | |
4550 | } else { // Search using Get() | |
4551 | PinnableSlice value; | |
4552 | GetContext get_context(options.comparator, nullptr, nullptr, nullptr, | |
4553 | GetContext::kNotFound, user_key, &value, nullptr, | |
f67539c2 | 4554 | nullptr, true, nullptr, nullptr); |
11fdf7f2 TL |
4555 | ASSERT_OK(reader->Get(ro, encoded_key, &get_context, |
4556 | moptions.prefix_extractor.get())); | |
4557 | ASSERT_EQ(get_context.State(), GetContext::kNotFound); | |
4558 | value.Reset(); | |
4559 | } | |
4560 | } | |
4561 | } | |
4562 | } | |
4563 | ||
f67539c2 TL |
4564 | // BlockBasedTableIterator should invalidate itself and return |
4565 | // OutOfBound()=true immediately after Seek(), to allow LevelIterator | |
4566 | // filter out corresponding level. | |
4567 | TEST_P(BlockBasedTableTest, OutOfBoundOnSeek) { | |
4568 | TableConstructor c(BytewiseComparator(), true /*convert_to_internal_key*/); | |
4569 | c.Add("foo", "v1"); | |
4570 | std::vector<std::string> keys; | |
4571 | stl_wrappers::KVMap kvmap; | |
4572 | Options options; | |
4573 | BlockBasedTableOptions table_opt(GetBlockBasedTableOptions()); | |
4574 | options.table_factory.reset(NewBlockBasedTableFactory(table_opt)); | |
4575 | const ImmutableCFOptions ioptions(options); | |
4576 | const MutableCFOptions moptions(options); | |
4577 | c.Finish(options, ioptions, moptions, table_opt, | |
4578 | GetPlainInternalComparator(BytewiseComparator()), &keys, &kvmap); | |
4579 | auto* reader = c.GetTableReader(); | |
4580 | ReadOptions read_opt; | |
4581 | std::string upper_bound = "bar"; | |
4582 | Slice upper_bound_slice(upper_bound); | |
4583 | read_opt.iterate_upper_bound = &upper_bound_slice; | |
4584 | std::unique_ptr<InternalIterator> iter; | |
4585 | iter.reset(new KeyConvertingIterator(reader->NewIterator( | |
4586 | read_opt, /*prefix_extractor=*/nullptr, /*arena=*/nullptr, | |
4587 | /*skip_filters=*/false, TableReaderCaller::kUncategorized))); | |
4588 | iter->SeekToFirst(); | |
4589 | ASSERT_FALSE(iter->Valid()); | |
4590 | ASSERT_TRUE(iter->IsOutOfBound()); | |
4591 | iter.reset(new KeyConvertingIterator(reader->NewIterator( | |
4592 | read_opt, /*prefix_extractor=*/nullptr, /*arena=*/nullptr, | |
4593 | /*skip_filters=*/false, TableReaderCaller::kUncategorized))); | |
4594 | iter->Seek("foo"); | |
4595 | ASSERT_FALSE(iter->Valid()); | |
4596 | ASSERT_TRUE(iter->IsOutOfBound()); | |
4597 | } | |
4598 | ||
4599 | // BlockBasedTableIterator should invalidate itself and return | |
4600 | // OutOfBound()=true after Next(), if it finds current index key is no smaller | |
4601 | // than upper bound, unless it is pointing to the last data block. | |
4602 | TEST_P(BlockBasedTableTest, OutOfBoundOnNext) { | |
4603 | TableConstructor c(BytewiseComparator(), true /*convert_to_internal_key*/); | |
4604 | c.Add("bar", "v"); | |
4605 | c.Add("foo", "v"); | |
4606 | std::vector<std::string> keys; | |
4607 | stl_wrappers::KVMap kvmap; | |
4608 | Options options; | |
4609 | BlockBasedTableOptions table_opt(GetBlockBasedTableOptions()); | |
4610 | table_opt.flush_block_policy_factory = | |
4611 | std::make_shared<FlushBlockEveryKeyPolicyFactory>(); | |
4612 | options.table_factory.reset(NewBlockBasedTableFactory(table_opt)); | |
4613 | const ImmutableCFOptions ioptions(options); | |
4614 | const MutableCFOptions moptions(options); | |
4615 | c.Finish(options, ioptions, moptions, table_opt, | |
4616 | GetPlainInternalComparator(BytewiseComparator()), &keys, &kvmap); | |
4617 | auto* reader = c.GetTableReader(); | |
4618 | ReadOptions read_opt; | |
4619 | std::string ub1 = "bar_after"; | |
4620 | Slice ub_slice1(ub1); | |
4621 | read_opt.iterate_upper_bound = &ub_slice1; | |
4622 | std::unique_ptr<InternalIterator> iter; | |
4623 | iter.reset(new KeyConvertingIterator(reader->NewIterator( | |
4624 | read_opt, /*prefix_extractor=*/nullptr, /*arena=*/nullptr, | |
4625 | /*skip_filters=*/false, TableReaderCaller::kUncategorized))); | |
4626 | iter->Seek("bar"); | |
4627 | ASSERT_TRUE(iter->Valid()); | |
4628 | ASSERT_EQ("bar", iter->key()); | |
4629 | iter->Next(); | |
4630 | ASSERT_FALSE(iter->Valid()); | |
4631 | ASSERT_TRUE(iter->IsOutOfBound()); | |
4632 | std::string ub2 = "foo_after"; | |
4633 | Slice ub_slice2(ub2); | |
4634 | read_opt.iterate_upper_bound = &ub_slice2; | |
4635 | iter.reset(new KeyConvertingIterator(reader->NewIterator( | |
4636 | read_opt, /*prefix_extractor=*/nullptr, /*arena=*/nullptr, | |
4637 | /*skip_filters=*/false, TableReaderCaller::kUncategorized))); | |
4638 | iter->Seek("foo"); | |
4639 | ASSERT_TRUE(iter->Valid()); | |
4640 | ASSERT_EQ("foo", iter->key()); | |
4641 | iter->Next(); | |
4642 | ASSERT_FALSE(iter->Valid()); | |
4643 | ASSERT_FALSE(iter->IsOutOfBound()); | |
4644 | } | |
4645 | ||
4646 | } // namespace ROCKSDB_NAMESPACE | |
7c673cae FG |
4647 | |
4648 | int main(int argc, char** argv) { | |
4649 | ::testing::InitGoogleTest(&argc, argv); | |
4650 | return RUN_ALL_TESTS(); | |
4651 | } |