1 // Copyright (c) 2011-present, Facebook, Inc. All rights reserved.
2 // This source code is licensed under both the GPLv2 (found in the
3 // COPYING file in the root directory) and Apache 2.0 License
4 // (found in the LICENSE.Apache file in the root directory).
11 fprintf(stderr
, "Please install gflags to run this test... Skipping...\n");
20 #include "db/db_impl.h"
21 #include "monitoring/histogram.h"
22 #include "rocksdb/comparator.h"
23 #include "rocksdb/db.h"
24 #include "rocksdb/filter_policy.h"
25 #include "rocksdb/memtablerep.h"
26 #include "rocksdb/perf_context.h"
27 #include "rocksdb/slice_transform.h"
28 #include "rocksdb/table.h"
29 #include "util/coding.h"
30 #include "util/gflags_compat.h"
31 #include "util/random.h"
32 #include "util/stop_watch.h"
33 #include "util/string_util.h"
34 #include "util/testharness.h"
35 #include "utilities/merge_operators.h"
37 using GFLAGS_NAMESPACE::ParseCommandLineFlags
;
39 DEFINE_bool(trigger_deadlock
, false,
40 "issue delete in range scan to trigger PrefixHashMap deadlock");
41 DEFINE_int32(bucket_count
, 100000, "number of buckets");
42 DEFINE_uint64(num_locks
, 10001, "number of locks");
43 DEFINE_bool(random_prefix
, false, "randomize prefix");
44 DEFINE_uint64(total_prefixes
, 100000, "total number of prefixes");
45 DEFINE_uint64(items_per_prefix
, 1, "total number of values per prefix");
46 DEFINE_int64(write_buffer_size
, 33554432, "");
47 DEFINE_int32(max_write_buffer_number
, 2, "");
48 DEFINE_int32(min_write_buffer_number_to_merge
, 1, "");
49 DEFINE_int32(skiplist_height
, 4, "");
50 DEFINE_double(memtable_prefix_bloom_size_ratio
, 0.1, "");
51 DEFINE_int32(memtable_huge_page_size
, 2 * 1024 * 1024, "");
52 DEFINE_int32(value_size
, 40, "");
53 DEFINE_bool(enable_print
, false, "Print options generated to console.");
55 // Path to the database on file system
56 const std::string kDbName
= rocksdb::test::PerThreadDBPath("prefix_test");
64 TestKey(uint64_t _prefix
, uint64_t _sorted
)
65 : prefix(_prefix
), sorted(_sorted
) {}
68 // return a slice backed by test_key
69 inline Slice
TestKeyToSlice(std::string
&s
, const TestKey
& test_key
) {
71 PutFixed64(&s
, test_key
.prefix
);
72 PutFixed64(&s
, test_key
.sorted
);
73 return Slice(s
.c_str(), s
.size());
76 inline const TestKey
SliceToTestKey(const Slice
& slice
) {
77 return TestKey(DecodeFixed64(slice
.data()),
78 DecodeFixed64(slice
.data() + 8));
81 class TestKeyComparator
: public Comparator
{
84 // Compare needs to be aware of the possibility of a and/or b is
86 int Compare(const Slice
& a
, const Slice
& b
) const override
{
87 const TestKey kkey_a
= SliceToTestKey(a
);
88 const TestKey kkey_b
= SliceToTestKey(b
);
89 const TestKey
*key_a
= &kkey_a
;
90 const TestKey
*key_b
= &kkey_b
;
91 if (key_a
->prefix
!= key_b
->prefix
) {
92 if (key_a
->prefix
< key_b
->prefix
) return -1;
93 if (key_a
->prefix
> key_b
->prefix
) return 1;
95 EXPECT_TRUE(key_a
->prefix
== key_b
->prefix
);
96 // note, both a and b could be prefix only
97 if (a
.size() != b
.size()) {
98 // one of them is prefix
100 (a
.size() == sizeof(uint64_t) && b
.size() == sizeof(TestKey
)) ||
101 (b
.size() == sizeof(uint64_t) && a
.size() == sizeof(TestKey
)));
102 if (a
.size() < b
.size()) return -1;
103 if (a
.size() > b
.size()) return 1;
105 // both a and b are prefix
106 if (a
.size() == sizeof(uint64_t)) {
110 // both a and b are whole key
111 EXPECT_TRUE(a
.size() == sizeof(TestKey
) && b
.size() == sizeof(TestKey
));
112 if (key_a
->sorted
< key_b
->sorted
) return -1;
113 if (key_a
->sorted
> key_b
->sorted
) return 1;
114 if (key_a
->sorted
== key_b
->sorted
) return 0;
120 bool operator()(const TestKey
& a
, const TestKey
& b
) const {
122 return Compare(TestKeyToSlice(sa
, a
), TestKeyToSlice(sb
, b
)) < 0;
125 const char* Name() const override
{ return "TestKeyComparator"; }
127 void FindShortestSeparator(std::string
* /*start*/,
128 const Slice
& /*limit*/) const override
{}
130 void FindShortSuccessor(std::string
* /*key*/) const override
{}
134 void PutKey(DB
* db
, WriteOptions write_options
, uint64_t prefix
,
135 uint64_t suffix
, const Slice
& value
) {
136 TestKey
test_key(prefix
, suffix
);
138 Slice key
= TestKeyToSlice(s
, test_key
);
139 ASSERT_OK(db
->Put(write_options
, key
, value
));
142 void PutKey(DB
* db
, WriteOptions write_options
, const TestKey
& test_key
,
143 const Slice
& value
) {
145 Slice key
= TestKeyToSlice(s
, test_key
);
146 ASSERT_OK(db
->Put(write_options
, key
, value
));
149 void MergeKey(DB
* db
, WriteOptions write_options
, const TestKey
& test_key
,
150 const Slice
& value
) {
152 Slice key
= TestKeyToSlice(s
, test_key
);
153 ASSERT_OK(db
->Merge(write_options
, key
, value
));
156 void DeleteKey(DB
* db
, WriteOptions write_options
, const TestKey
& test_key
) {
158 Slice key
= TestKeyToSlice(s
, test_key
);
159 ASSERT_OK(db
->Delete(write_options
, key
));
162 void SeekIterator(Iterator
* iter
, uint64_t prefix
, uint64_t suffix
) {
163 TestKey
test_key(prefix
, suffix
);
165 Slice key
= TestKeyToSlice(s
, test_key
);
169 const std::string kNotFoundResult
= "NOT_FOUND";
171 std::string
Get(DB
* db
, const ReadOptions
& read_options
, uint64_t prefix
,
173 TestKey
test_key(prefix
, suffix
);
175 Slice key
= TestKeyToSlice(s2
, test_key
);
178 Status s
= db
->Get(read_options
, key
, &result
);
179 if (s
.IsNotFound()) {
180 result
= kNotFoundResult
;
181 } else if (!s
.ok()) {
182 result
= s
.ToString();
187 class SamePrefixTransform
: public SliceTransform
{
193 explicit SamePrefixTransform(const Slice
& prefix
)
194 : prefix_(prefix
), name_("rocksdb.SamePrefix." + prefix
.ToString()) {}
196 const char* Name() const override
{ return name_
.c_str(); }
198 Slice
Transform(const Slice
& src
) const override
{
199 assert(InDomain(src
));
203 bool InDomain(const Slice
& src
) const override
{
204 if (src
.size() >= prefix_
.size()) {
205 return Slice(src
.data(), prefix_
.size()) == prefix_
;
210 bool InRange(const Slice
& dst
) const override
{ return dst
== prefix_
; }
212 bool FullLengthEnabled(size_t* /*len*/) const override
{ return false; }
217 class PrefixTest
: public testing::Test
{
219 std::shared_ptr
<DB
> OpenDb() {
222 options
.create_if_missing
= true;
223 options
.write_buffer_size
= FLAGS_write_buffer_size
;
224 options
.max_write_buffer_number
= FLAGS_max_write_buffer_number
;
225 options
.min_write_buffer_number_to_merge
=
226 FLAGS_min_write_buffer_number_to_merge
;
228 options
.memtable_prefix_bloom_size_ratio
=
229 FLAGS_memtable_prefix_bloom_size_ratio
;
230 options
.memtable_huge_page_size
= FLAGS_memtable_huge_page_size
;
232 options
.prefix_extractor
.reset(NewFixedPrefixTransform(8));
233 BlockBasedTableOptions bbto
;
234 bbto
.filter_policy
.reset(NewBloomFilterPolicy(10, false));
235 bbto
.whole_key_filtering
= false;
236 options
.table_factory
.reset(NewBlockBasedTableFactory(bbto
));
237 options
.allow_concurrent_memtable_write
= false;
239 Status s
= DB::Open(options
, kDbName
, &db
);
241 return std::shared_ptr
<DB
>(db
);
245 option_config_
= kBegin
;
248 bool NextOptions(int bucket_count
) {
251 if (option_config_
< kEnd
) {
252 options
.prefix_extractor
.reset(NewFixedPrefixTransform(8));
253 switch(option_config_
) {
255 options
.memtable_factory
.reset(
256 NewHashSkipListRepFactory(bucket_count
, FLAGS_skiplist_height
));
259 options
.memtable_factory
.reset(
260 NewHashLinkListRepFactory(bucket_count
));
262 case kHashLinkListHugePageTlb
:
263 options
.memtable_factory
.reset(
264 NewHashLinkListRepFactory(bucket_count
, 2 * 1024 * 1024));
266 case kHashLinkListTriggerSkipList
:
267 options
.memtable_factory
.reset(
268 NewHashLinkListRepFactory(bucket_count
, 0, 3));
277 PrefixTest() : option_config_(kBegin
) {
278 options
.comparator
= new TestKeyComparator();
280 ~PrefixTest() override
{ delete options
.comparator
; }
287 kHashLinkListHugePageTlb
,
288 kHashLinkListTriggerSkipList
,
295 TEST(SamePrefixTest
, InDomainTest
) {
298 options
.create_if_missing
= true;
299 options
.prefix_extractor
.reset(new SamePrefixTransform("HHKB"));
300 BlockBasedTableOptions bbto
;
301 bbto
.filter_policy
.reset(NewBloomFilterPolicy(10, false));
302 bbto
.whole_key_filtering
= false;
303 options
.table_factory
.reset(NewBlockBasedTableFactory(bbto
));
304 WriteOptions write_options
;
305 ReadOptions read_options
;
307 ASSERT_OK(DestroyDB(kDbName
, Options()));
308 ASSERT_OK(DB::Open(options
, kDbName
, &db
));
309 ASSERT_OK(db
->Put(write_options
, "HHKB pro2", "Mar 24, 2006"));
310 ASSERT_OK(db
->Put(write_options
, "HHKB pro2 Type-S", "June 29, 2011"));
311 ASSERT_OK(db
->Put(write_options
, "Realforce 87u", "idk"));
312 db
->Flush(FlushOptions());
314 auto db_iter
= db
->NewIterator(ReadOptions());
316 db_iter
->Seek("Realforce 87u");
317 ASSERT_TRUE(db_iter
->Valid());
318 ASSERT_OK(db_iter
->status());
319 ASSERT_EQ(db_iter
->key(), "Realforce 87u");
320 ASSERT_EQ(db_iter
->value(), "idk");
324 ASSERT_OK(DestroyDB(kDbName
, Options()));
328 ASSERT_OK(DB::Open(options
, kDbName
, &db
));
329 ASSERT_OK(db
->Put(write_options
, "pikachu", "1"));
330 ASSERT_OK(db
->Put(write_options
, "Meowth", "1"));
331 ASSERT_OK(db
->Put(write_options
, "Mewtwo", "idk"));
332 db
->Flush(FlushOptions());
334 auto db_iter
= db
->NewIterator(ReadOptions());
336 db_iter
->Seek("Mewtwo");
337 ASSERT_TRUE(db_iter
->Valid());
338 ASSERT_OK(db_iter
->status());
341 ASSERT_OK(DestroyDB(kDbName
, Options()));
345 TEST_F(PrefixTest
, TestResult
) {
346 for (int num_buckets
= 1; num_buckets
<= 2; num_buckets
++) {
348 while (NextOptions(num_buckets
)) {
349 std::cout
<< "*** Mem table: " << options
.memtable_factory
->Name()
350 << " number of buckets: " << num_buckets
352 DestroyDB(kDbName
, Options());
354 WriteOptions write_options
;
355 ReadOptions read_options
;
357 // 1. Insert one row.
359 PutKey(db
.get(), write_options
, 1, 6, v16
);
360 std::unique_ptr
<Iterator
> iter(db
->NewIterator(read_options
));
361 SeekIterator(iter
.get(), 1, 6);
362 ASSERT_TRUE(iter
->Valid());
363 ASSERT_TRUE(v16
== iter
->value());
364 SeekIterator(iter
.get(), 1, 5);
365 ASSERT_TRUE(iter
->Valid());
366 ASSERT_TRUE(v16
== iter
->value());
367 SeekIterator(iter
.get(), 1, 5);
368 ASSERT_TRUE(iter
->Valid());
369 ASSERT_TRUE(v16
== iter
->value());
371 ASSERT_TRUE(!iter
->Valid());
373 SeekIterator(iter
.get(), 2, 0);
374 ASSERT_TRUE(!iter
->Valid());
376 ASSERT_EQ(v16
.ToString(), Get(db
.get(), read_options
, 1, 6));
377 ASSERT_EQ(kNotFoundResult
, Get(db
.get(), read_options
, 1, 5));
378 ASSERT_EQ(kNotFoundResult
, Get(db
.get(), read_options
, 1, 7));
379 ASSERT_EQ(kNotFoundResult
, Get(db
.get(), read_options
, 0, 6));
380 ASSERT_EQ(kNotFoundResult
, Get(db
.get(), read_options
, 2, 6));
382 // 2. Insert an entry for the same prefix as the last entry in the bucket.
384 PutKey(db
.get(), write_options
, 1, 7, v17
);
385 iter
.reset(db
->NewIterator(read_options
));
386 SeekIterator(iter
.get(), 1, 7);
387 ASSERT_TRUE(iter
->Valid());
388 ASSERT_TRUE(v17
== iter
->value());
390 SeekIterator(iter
.get(), 1, 6);
391 ASSERT_TRUE(iter
->Valid());
392 ASSERT_TRUE(v16
== iter
->value());
394 ASSERT_TRUE(iter
->Valid());
395 ASSERT_TRUE(v17
== iter
->value());
397 ASSERT_TRUE(!iter
->Valid());
399 SeekIterator(iter
.get(), 2, 0);
400 ASSERT_TRUE(!iter
->Valid());
402 // 3. Insert an entry for the same prefix as the head of the bucket.
404 PutKey(db
.get(), write_options
, 1, 5, v15
);
405 iter
.reset(db
->NewIterator(read_options
));
407 SeekIterator(iter
.get(), 1, 7);
408 ASSERT_TRUE(iter
->Valid());
409 ASSERT_TRUE(v17
== iter
->value());
411 SeekIterator(iter
.get(), 1, 5);
412 ASSERT_TRUE(iter
->Valid());
413 ASSERT_TRUE(v15
== iter
->value());
415 ASSERT_TRUE(iter
->Valid());
416 ASSERT_TRUE(v16
== iter
->value());
418 ASSERT_TRUE(iter
->Valid());
419 ASSERT_TRUE(v17
== iter
->value());
421 SeekIterator(iter
.get(), 1, 5);
422 ASSERT_TRUE(iter
->Valid());
423 ASSERT_TRUE(v15
== iter
->value());
425 ASSERT_EQ(v15
.ToString(), Get(db
.get(), read_options
, 1, 5));
426 ASSERT_EQ(v16
.ToString(), Get(db
.get(), read_options
, 1, 6));
427 ASSERT_EQ(v17
.ToString(), Get(db
.get(), read_options
, 1, 7));
429 // 4. Insert an entry with a larger prefix
431 PutKey(db
.get(), write_options
, 2, 2, v22
);
432 iter
.reset(db
->NewIterator(read_options
));
434 SeekIterator(iter
.get(), 2, 2);
435 ASSERT_TRUE(iter
->Valid());
436 ASSERT_TRUE(v22
== iter
->value());
437 SeekIterator(iter
.get(), 2, 0);
438 ASSERT_TRUE(iter
->Valid());
439 ASSERT_TRUE(v22
== iter
->value());
441 SeekIterator(iter
.get(), 1, 5);
442 ASSERT_TRUE(iter
->Valid());
443 ASSERT_TRUE(v15
== iter
->value());
445 SeekIterator(iter
.get(), 1, 7);
446 ASSERT_TRUE(iter
->Valid());
447 ASSERT_TRUE(v17
== iter
->value());
449 // 5. Insert an entry with a smaller prefix
451 PutKey(db
.get(), write_options
, 0, 2, v02
);
452 iter
.reset(db
->NewIterator(read_options
));
454 SeekIterator(iter
.get(), 0, 2);
455 ASSERT_TRUE(iter
->Valid());
456 ASSERT_TRUE(v02
== iter
->value());
457 SeekIterator(iter
.get(), 0, 0);
458 ASSERT_TRUE(iter
->Valid());
459 ASSERT_TRUE(v02
== iter
->value());
461 SeekIterator(iter
.get(), 2, 0);
462 ASSERT_TRUE(iter
->Valid());
463 ASSERT_TRUE(v22
== iter
->value());
465 SeekIterator(iter
.get(), 1, 5);
466 ASSERT_TRUE(iter
->Valid());
467 ASSERT_TRUE(v15
== iter
->value());
469 SeekIterator(iter
.get(), 1, 7);
470 ASSERT_TRUE(iter
->Valid());
471 ASSERT_TRUE(v17
== iter
->value());
473 // 6. Insert to the beginning and the end of the first prefix
476 PutKey(db
.get(), write_options
, 1, 3, v13
);
477 PutKey(db
.get(), write_options
, 1, 8, v18
);
478 iter
.reset(db
->NewIterator(read_options
));
479 SeekIterator(iter
.get(), 1, 7);
480 ASSERT_TRUE(iter
->Valid());
481 ASSERT_TRUE(v17
== iter
->value());
483 SeekIterator(iter
.get(), 1, 3);
484 ASSERT_TRUE(iter
->Valid());
485 ASSERT_TRUE(v13
== iter
->value());
487 ASSERT_TRUE(iter
->Valid());
488 ASSERT_TRUE(v15
== iter
->value());
490 ASSERT_TRUE(iter
->Valid());
491 ASSERT_TRUE(v16
== iter
->value());
493 ASSERT_TRUE(iter
->Valid());
494 ASSERT_TRUE(v17
== iter
->value());
496 ASSERT_TRUE(iter
->Valid());
497 ASSERT_TRUE(v18
== iter
->value());
499 SeekIterator(iter
.get(), 0, 0);
500 ASSERT_TRUE(iter
->Valid());
501 ASSERT_TRUE(v02
== iter
->value());
503 SeekIterator(iter
.get(), 2, 0);
504 ASSERT_TRUE(iter
->Valid());
505 ASSERT_TRUE(v22
== iter
->value());
507 ASSERT_EQ(v22
.ToString(), Get(db
.get(), read_options
, 2, 2));
508 ASSERT_EQ(v02
.ToString(), Get(db
.get(), read_options
, 0, 2));
509 ASSERT_EQ(v13
.ToString(), Get(db
.get(), read_options
, 1, 3));
510 ASSERT_EQ(v15
.ToString(), Get(db
.get(), read_options
, 1, 5));
511 ASSERT_EQ(v16
.ToString(), Get(db
.get(), read_options
, 1, 6));
512 ASSERT_EQ(v17
.ToString(), Get(db
.get(), read_options
, 1, 7));
513 ASSERT_EQ(v18
.ToString(), Get(db
.get(), read_options
, 1, 8));
518 // Show results in prefix
519 TEST_F(PrefixTest
, PrefixValid
) {
520 for (int num_buckets
= 1; num_buckets
<= 2; num_buckets
++) {
522 while (NextOptions(num_buckets
)) {
523 std::cout
<< "*** Mem table: " << options
.memtable_factory
->Name()
524 << " number of buckets: " << num_buckets
<< std::endl
;
525 DestroyDB(kDbName
, Options());
527 WriteOptions write_options
;
528 ReadOptions read_options
;
530 // Insert keys with common prefix and one key with different
535 PutKey(db
.get(), write_options
, 12345, 6, v16
);
536 PutKey(db
.get(), write_options
, 12345, 7, v17
);
537 PutKey(db
.get(), write_options
, 12345, 8, v18
);
538 PutKey(db
.get(), write_options
, 12345, 9, v19
);
539 PutKey(db
.get(), write_options
, 12346, 8, v16
);
540 db
->Flush(FlushOptions());
541 TestKey
test_key(12346, 8);
543 db
->Delete(write_options
, TestKeyToSlice(s
, test_key
));
544 db
->Flush(FlushOptions());
545 read_options
.prefix_same_as_start
= true;
546 std::unique_ptr
<Iterator
> iter(db
->NewIterator(read_options
));
547 SeekIterator(iter
.get(), 12345, 6);
548 ASSERT_TRUE(iter
->Valid());
549 ASSERT_TRUE(v16
== iter
->value());
552 ASSERT_TRUE(iter
->Valid());
553 ASSERT_TRUE(v17
== iter
->value());
556 ASSERT_TRUE(iter
->Valid());
557 ASSERT_TRUE(v18
== iter
->value());
560 ASSERT_TRUE(iter
->Valid());
561 ASSERT_TRUE(v19
== iter
->value());
563 ASSERT_FALSE(iter
->Valid());
564 ASSERT_EQ(kNotFoundResult
, Get(db
.get(), read_options
, 12346, 8));
566 // Verify seeking past the prefix won't return a result.
567 SeekIterator(iter
.get(), 12345, 10);
568 ASSERT_TRUE(!iter
->Valid());
573 TEST_F(PrefixTest
, DynamicPrefixIterator
) {
574 while (NextOptions(FLAGS_bucket_count
)) {
575 std::cout
<< "*** Mem table: " << options
.memtable_factory
->Name()
577 DestroyDB(kDbName
, Options());
579 WriteOptions write_options
;
580 ReadOptions read_options
;
582 std::vector
<uint64_t> prefixes
;
583 for (uint64_t i
= 0; i
< FLAGS_total_prefixes
; ++i
) {
584 prefixes
.push_back(i
);
587 if (FLAGS_random_prefix
) {
588 std::random_shuffle(prefixes
.begin(), prefixes
.end());
591 HistogramImpl hist_put_time
;
592 HistogramImpl hist_put_comparison
;
594 // insert x random prefix, each with y continuous element.
595 for (auto prefix
: prefixes
) {
596 for (uint64_t sorted
= 0; sorted
< FLAGS_items_per_prefix
; sorted
++) {
597 TestKey
test_key(prefix
, sorted
);
600 Slice key
= TestKeyToSlice(s
, test_key
);
601 std::string
value(FLAGS_value_size
, 0);
603 get_perf_context()->Reset();
604 StopWatchNano
timer(Env::Default(), true);
605 ASSERT_OK(db
->Put(write_options
, key
, value
));
606 hist_put_time
.Add(timer
.ElapsedNanos());
607 hist_put_comparison
.Add(get_perf_context()->user_key_comparison_count
);
611 std::cout
<< "Put key comparison: \n" << hist_put_comparison
.ToString()
612 << "Put time: \n" << hist_put_time
.ToString();
614 // test seek existing keys
615 HistogramImpl hist_seek_time
;
616 HistogramImpl hist_seek_comparison
;
618 std::unique_ptr
<Iterator
> iter(db
->NewIterator(read_options
));
620 for (auto prefix
: prefixes
) {
621 TestKey
test_key(prefix
, FLAGS_items_per_prefix
/ 2);
623 Slice key
= TestKeyToSlice(s
, test_key
);
624 std::string value
= "v" + ToString(0);
626 get_perf_context()->Reset();
627 StopWatchNano
timer(Env::Default(), true);
628 auto key_prefix
= options
.prefix_extractor
->Transform(key
);
629 uint64_t total_keys
= 0;
630 for (iter
->Seek(key
);
631 iter
->Valid() && iter
->key().starts_with(key_prefix
);
633 if (FLAGS_trigger_deadlock
) {
634 std::cout
<< "Behold the deadlock!\n";
635 db
->Delete(write_options
, iter
->key());
639 hist_seek_time
.Add(timer
.ElapsedNanos());
640 hist_seek_comparison
.Add(get_perf_context()->user_key_comparison_count
);
641 ASSERT_EQ(total_keys
, FLAGS_items_per_prefix
- FLAGS_items_per_prefix
/2);
644 std::cout
<< "Seek key comparison: \n"
645 << hist_seek_comparison
.ToString()
647 << hist_seek_time
.ToString();
649 // test non-existing keys
650 HistogramImpl hist_no_seek_time
;
651 HistogramImpl hist_no_seek_comparison
;
653 for (auto prefix
= FLAGS_total_prefixes
;
654 prefix
< FLAGS_total_prefixes
+ 10000;
656 TestKey
test_key(prefix
, 0);
658 Slice key
= TestKeyToSlice(s
, test_key
);
660 get_perf_context()->Reset();
661 StopWatchNano
timer(Env::Default(), true);
663 hist_no_seek_time
.Add(timer
.ElapsedNanos());
664 hist_no_seek_comparison
.Add(get_perf_context()->user_key_comparison_count
);
665 ASSERT_TRUE(!iter
->Valid());
668 std::cout
<< "non-existing Seek key comparison: \n"
669 << hist_no_seek_comparison
.ToString()
670 << "non-existing Seek time: \n"
671 << hist_no_seek_time
.ToString();
675 TEST_F(PrefixTest
, PrefixSeekModePrev
) {
676 // Only for SkipListFactory
677 options
.memtable_factory
.reset(new SkipListFactory
);
678 options
.merge_operator
= MergeOperators::CreatePutOperator();
679 options
.write_buffer_size
= 1024 * 1024;
681 for (size_t m
= 1; m
< 100; m
++) {
682 std::cout
<< "[" + std::to_string(m
) + "]" + "*** Mem table: "
683 << options
.memtable_factory
->Name() << std::endl
;
684 DestroyDB(kDbName
, Options());
686 WriteOptions write_options
;
687 ReadOptions read_options
;
688 std::map
<TestKey
, std::string
, TestKeyComparator
> entry_maps
[3], whole_map
;
689 for (uint64_t i
= 0; i
< 10; i
++) {
691 for (uint64_t j
= 0; j
< 10; j
++) {
692 whole_map
[TestKey(i
, j
)] = entry_maps
[rnd
.Uniform(div
)][TestKey(i
, j
)] =
693 'v' + std::to_string(i
) + std::to_string(j
);
697 std::map
<TestKey
, std::string
, TestKeyComparator
> type_map
;
698 for (size_t i
= 0; i
< 3; i
++) {
699 for (auto& kv
: entry_maps
[i
]) {
701 PutKey(db
.get(), write_options
, kv
.first
, kv
.second
);
702 type_map
[kv
.first
] = "value";
704 MergeKey(db
.get(), write_options
, kv
.first
, kv
.second
);
705 type_map
[kv
.first
] = "merge";
709 db
->Flush(FlushOptions());
713 for (size_t i
= 0; i
< 2; i
++) {
714 for (auto& kv
: entry_maps
[i
]) {
716 whole_map
.erase(kv
.first
);
717 DeleteKey(db
.get(), write_options
, kv
.first
);
718 entry_maps
[2][kv
.first
] = "delete";
723 if (FLAGS_enable_print
) {
724 for (size_t i
= 0; i
< 3; i
++) {
725 for (auto& kv
: entry_maps
[i
]) {
726 std::cout
<< "[" << i
<< "]" << kv
.first
.prefix
<< kv
.first
.sorted
727 << " " << kv
.second
+ " " + type_map
[kv
.first
] << std::endl
;
732 std::unique_ptr
<Iterator
> iter(db
->NewIterator(read_options
));
733 for (uint64_t prefix
= 0; prefix
< 10; prefix
++) {
734 uint64_t start_suffix
= rnd
.Uniform(9);
735 SeekIterator(iter
.get(), prefix
, start_suffix
);
736 auto it
= whole_map
.find(TestKey(prefix
, start_suffix
));
737 if (it
== whole_map
.end()) {
740 ASSERT_NE(it
, whole_map
.end());
741 ASSERT_TRUE(iter
->Valid());
742 if (FLAGS_enable_print
) {
743 std::cout
<< "round " << prefix
744 << " iter: " << SliceToTestKey(iter
->key()).prefix
745 << SliceToTestKey(iter
->key()).sorted
746 << " | map: " << it
->first
.prefix
<< it
->first
.sorted
<< " | "
747 << iter
->value().ToString() << " " << it
->second
<< std::endl
;
749 ASSERT_EQ(iter
->value(), it
->second
);
750 uint64_t stored_prefix
= prefix
;
751 for (size_t k
= 0; k
< 9; k
++) {
752 if (rnd
.OneIn(2) || it
== whole_map
.begin()) {
755 if (FLAGS_enable_print
) {
756 std::cout
<< "Next >> ";
761 if (FLAGS_enable_print
) {
762 std::cout
<< "Prev >> ";
765 if (!iter
->Valid() ||
766 SliceToTestKey(iter
->key()).prefix
!= stored_prefix
) {
769 stored_prefix
= SliceToTestKey(iter
->key()).prefix
;
770 ASSERT_TRUE(iter
->Valid());
771 ASSERT_NE(it
, whole_map
.end());
772 ASSERT_EQ(iter
->value(), it
->second
);
773 if (FLAGS_enable_print
) {
774 std::cout
<< "iter: " << SliceToTestKey(iter
->key()).prefix
775 << SliceToTestKey(iter
->key()).sorted
776 << " | map: " << it
->first
.prefix
<< it
->first
.sorted
777 << " | " << iter
->value().ToString() << " " << it
->second
785 TEST_F(PrefixTest
, PrefixSeekModePrev2
) {
786 // Only for SkipListFactory
789 // | prefix | suffix | | prefix | suffix |
790 // | 1 | 1 | | 1 | 2 |
791 // | 1 | 3 | | 1 | 4 |
792 // | 2 | 1 | | 3 | 3 |
793 // | 2 | 2 | | 3 | 4 |
794 // after seek(15), iter1 will be at 21 and iter2 will be 33.
795 // Then if call Prev() in prefix mode where SeekForPrev(21) gets called,
796 // iter2 should turn to invalid state because of bloom filter.
797 options
.memtable_factory
.reset(new SkipListFactory
);
798 options
.write_buffer_size
= 1024 * 1024;
799 std::string
v13("v13");
800 DestroyDB(kDbName
, Options());
802 WriteOptions write_options
;
803 ReadOptions read_options
;
804 PutKey(db
.get(), write_options
, TestKey(1, 2), "v12");
805 PutKey(db
.get(), write_options
, TestKey(1, 4), "v14");
806 PutKey(db
.get(), write_options
, TestKey(3, 3), "v33");
807 PutKey(db
.get(), write_options
, TestKey(3, 4), "v34");
808 db
->Flush(FlushOptions());
809 reinterpret_cast<DBImpl
*>(db
.get())->TEST_WaitForFlushMemTable();
810 PutKey(db
.get(), write_options
, TestKey(1, 1), "v11");
811 PutKey(db
.get(), write_options
, TestKey(1, 3), "v13");
812 PutKey(db
.get(), write_options
, TestKey(2, 1), "v21");
813 PutKey(db
.get(), write_options
, TestKey(2, 2), "v22");
814 db
->Flush(FlushOptions());
815 reinterpret_cast<DBImpl
*>(db
.get())->TEST_WaitForFlushMemTable();
816 std::unique_ptr
<Iterator
> iter(db
->NewIterator(read_options
));
817 SeekIterator(iter
.get(), 1, 5);
819 ASSERT_EQ(iter
->value(), v13
);
822 TEST_F(PrefixTest
, PrefixSeekModePrev3
) {
823 // Only for SkipListFactory
824 // test SeekToLast() with iterate_upper_bound_ in prefix_seek_mode
825 options
.memtable_factory
.reset(new SkipListFactory
);
826 options
.write_buffer_size
= 1024 * 1024;
827 std::string
v14("v14");
828 TestKey upper_bound_key
= TestKey(1, 5);
830 Slice upper_bound
= TestKeyToSlice(s
, upper_bound_key
);
833 DestroyDB(kDbName
, Options());
835 WriteOptions write_options
;
836 ReadOptions read_options
;
837 read_options
.iterate_upper_bound
= &upper_bound
;
838 PutKey(db
.get(), write_options
, TestKey(1, 2), "v12");
839 PutKey(db
.get(), write_options
, TestKey(1, 4), "v14");
840 db
->Flush(FlushOptions());
841 reinterpret_cast<DBImpl
*>(db
.get())->TEST_WaitForFlushMemTable();
842 PutKey(db
.get(), write_options
, TestKey(1, 1), "v11");
843 PutKey(db
.get(), write_options
, TestKey(1, 3), "v13");
844 PutKey(db
.get(), write_options
, TestKey(2, 1), "v21");
845 PutKey(db
.get(), write_options
, TestKey(2, 2), "v22");
846 db
->Flush(FlushOptions());
847 reinterpret_cast<DBImpl
*>(db
.get())->TEST_WaitForFlushMemTable();
848 std::unique_ptr
<Iterator
> iter(db
->NewIterator(read_options
));
850 ASSERT_EQ(iter
->value(), v14
);
853 DestroyDB(kDbName
, Options());
855 WriteOptions write_options
;
856 ReadOptions read_options
;
857 read_options
.iterate_upper_bound
= &upper_bound
;
858 PutKey(db
.get(), write_options
, TestKey(1, 2), "v12");
859 PutKey(db
.get(), write_options
, TestKey(1, 4), "v14");
860 PutKey(db
.get(), write_options
, TestKey(3, 3), "v33");
861 PutKey(db
.get(), write_options
, TestKey(3, 4), "v34");
862 db
->Flush(FlushOptions());
863 reinterpret_cast<DBImpl
*>(db
.get())->TEST_WaitForFlushMemTable();
864 PutKey(db
.get(), write_options
, TestKey(1, 1), "v11");
865 PutKey(db
.get(), write_options
, TestKey(1, 3), "v13");
866 db
->Flush(FlushOptions());
867 reinterpret_cast<DBImpl
*>(db
.get())->TEST_WaitForFlushMemTable();
868 std::unique_ptr
<Iterator
> iter(db
->NewIterator(read_options
));
870 ASSERT_EQ(iter
->value(), v14
);
874 } // end namespace rocksdb
876 int main(int argc
, char** argv
) {
877 ::testing::InitGoogleTest(&argc
, argv
);
878 ParseCommandLineFlags(&argc
, &argv
, true);
879 return RUN_ALL_TESTS();
887 int main(int /*argc*/, char** /*argv*/) {
889 "SKIPPED as HashSkipList and HashLinkList are not supported in "
894 #endif // !ROCKSDB_LITE