ceph/src/rocksdb/db/prefix_test.cc

   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).
   5
   6 #ifndef ROCKSDB_LITE
   7
   8 #ifndef GFLAGS
   9 #include <cstdio>
  10 int main() {
  11   fprintf(stderr, "Please install gflags to run this test... Skipping...\n");
  12   return 0;
  13 }
  14 #else
  15
  16 #include <algorithm>
  17 #include <iostream>
  18 #include <vector>
  19
  20 #include "db/db_impl/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 "test_util/testharness.h"
  30 #include "util/cast_util.h"
  31 #include "util/coding.h"
  32 #include "util/gflags_compat.h"
  33 #include "util/random.h"
  34 #include "util/stop_watch.h"
  35 #include "util/string_util.h"
  36 #include "utilities/merge_operators.h"
  37
  38 using GFLAGS_NAMESPACE::ParseCommandLineFlags;
  39
  40 DEFINE_bool(trigger_deadlock, false,
  41             "issue delete in range scan to trigger PrefixHashMap deadlock");
  42 DEFINE_int32(bucket_count, 100000, "number of buckets");
  43 DEFINE_uint64(num_locks, 10001, "number of locks");
  44 DEFINE_bool(random_prefix, false, "randomize prefix");
  45 DEFINE_uint64(total_prefixes, 100000, "total number of prefixes");
  46 DEFINE_uint64(items_per_prefix, 1, "total number of values per prefix");
  47 DEFINE_int64(write_buffer_size, 33554432, "");
  48 DEFINE_int32(max_write_buffer_number, 2, "");
  49 DEFINE_int32(min_write_buffer_number_to_merge, 1, "");
  50 DEFINE_int32(skiplist_height, 4, "");
  51 DEFINE_double(memtable_prefix_bloom_size_ratio, 0.1, "");
  52 DEFINE_int32(memtable_huge_page_size, 2 * 1024 * 1024, "");
  53 DEFINE_int32(value_size, 40, "");
  54 DEFINE_bool(enable_print, false, "Print options generated to console.");
  55
  56 // Path to the database on file system
  57 const std::string kDbName =
  58     ROCKSDB_NAMESPACE::test::PerThreadDBPath("prefix_test");
  59
  60 namespace ROCKSDB_NAMESPACE {
  61
  62 struct TestKey {
  63   uint64_t prefix;
  64   uint64_t sorted;
  65
  66   TestKey(uint64_t _prefix, uint64_t _sorted)
  67       : prefix(_prefix), sorted(_sorted) {}
  68 };
  69
  70 // return a slice backed by test_key
  71 inline Slice TestKeyToSlice(std::string &s, const TestKey& test_key) {
  72   s.clear();
  73   PutFixed64(&s, test_key.prefix);
  74   PutFixed64(&s, test_key.sorted);
  75   return Slice(s.c_str(), s.size());
  76 }
  77
  78 inline const TestKey SliceToTestKey(const Slice& slice) {
  79   return TestKey(DecodeFixed64(slice.data()),
  80     DecodeFixed64(slice.data() + 8));
  81 }
  82
  83 class TestKeyComparator : public Comparator {
  84  public:
  85
  86   // Compare needs to be aware of the possibility of a and/or b is
  87   // prefix only
  88   int Compare(const Slice& a, const Slice& b) const override {
  89     const TestKey kkey_a = SliceToTestKey(a);
  90     const TestKey kkey_b = SliceToTestKey(b);
  91     const TestKey *key_a = &kkey_a;
  92     const TestKey *key_b = &kkey_b;
  93     if (key_a->prefix != key_b->prefix) {
  94       if (key_a->prefix < key_b->prefix) return -1;
  95       if (key_a->prefix > key_b->prefix) return 1;
  96     } else {
  97       EXPECT_TRUE(key_a->prefix == key_b->prefix);
  98       // note, both a and b could be prefix only
  99       if (a.size() != b.size()) {
 100         // one of them is prefix
 101         EXPECT_TRUE(
 102             (a.size() == sizeof(uint64_t) && b.size() == sizeof(TestKey)) ||
 103             (b.size() == sizeof(uint64_t) && a.size() == sizeof(TestKey)));
 104         if (a.size() < b.size()) return -1;
 105         if (a.size() > b.size()) return 1;
 106       } else {
 107         // both a and b are prefix
 108         if (a.size() == sizeof(uint64_t)) {
 109           return 0;
 110         }
 111
 112         // both a and b are whole key
 113         EXPECT_TRUE(a.size() == sizeof(TestKey) && b.size() == sizeof(TestKey));
 114         if (key_a->sorted < key_b->sorted) return -1;
 115         if (key_a->sorted > key_b->sorted) return 1;
 116         if (key_a->sorted == key_b->sorted) return 0;
 117       }
 118     }
 119     return 0;
 120   }
 121
 122   bool operator()(const TestKey& a, const TestKey& b) const {
 123     std::string sa, sb;
 124     return Compare(TestKeyToSlice(sa, a), TestKeyToSlice(sb, b)) < 0;
 125   }
 126
 127   const char* Name() const override { return "TestKeyComparator"; }
 128
 129   void FindShortestSeparator(std::string* /*start*/,
 130                              const Slice& /*limit*/) const override {}
 131
 132   void FindShortSuccessor(std::string* /*key*/) const override {}
 133 };
 134
 135 namespace {
 136 void PutKey(DB* db, WriteOptions write_options, uint64_t prefix,
 137             uint64_t suffix, const Slice& value) {
 138   TestKey test_key(prefix, suffix);
 139   std::string s;
 140   Slice key = TestKeyToSlice(s, test_key);
 141   ASSERT_OK(db->Put(write_options, key, value));
 142 }
 143
 144 void PutKey(DB* db, WriteOptions write_options, const TestKey& test_key,
 145             const Slice& value) {
 146   std::string s;
 147   Slice key = TestKeyToSlice(s, test_key);
 148   ASSERT_OK(db->Put(write_options, key, value));
 149 }
 150
 151 void MergeKey(DB* db, WriteOptions write_options, const TestKey& test_key,
 152               const Slice& value) {
 153   std::string s;
 154   Slice key = TestKeyToSlice(s, test_key);
 155   ASSERT_OK(db->Merge(write_options, key, value));
 156 }
 157
 158 void DeleteKey(DB* db, WriteOptions write_options, const TestKey& test_key) {
 159   std::string s;
 160   Slice key = TestKeyToSlice(s, test_key);
 161   ASSERT_OK(db->Delete(write_options, key));
 162 }
 163
 164 void SeekIterator(Iterator* iter, uint64_t prefix, uint64_t suffix) {
 165   TestKey test_key(prefix, suffix);
 166   std::string s;
 167   Slice key = TestKeyToSlice(s, test_key);
 168   iter->Seek(key);
 169 }
 170
 171 const std::string kNotFoundResult = "NOT_FOUND";
 172
 173 std::string Get(DB* db, const ReadOptions& read_options, uint64_t prefix,
 174                 uint64_t suffix) {
 175   TestKey test_key(prefix, suffix);
 176   std::string s2;
 177   Slice key = TestKeyToSlice(s2, test_key);
 178
 179   std::string result;
 180   Status s = db->Get(read_options, key, &result);
 181   if (s.IsNotFound()) {
 182     result = kNotFoundResult;
 183   } else if (!s.ok()) {
 184     result = s.ToString();
 185   }
 186   return result;
 187 }
 188
 189 class SamePrefixTransform : public SliceTransform {
 190  private:
 191   const Slice prefix_;
 192   std::string name_;
 193
 194  public:
 195   explicit SamePrefixTransform(const Slice& prefix)
 196       : prefix_(prefix), name_("rocksdb.SamePrefix." + prefix.ToString()) {}
 197
 198   const char* Name() const override { return name_.c_str(); }
 199
 200   Slice Transform(const Slice& src) const override {
 201     assert(InDomain(src));
 202     return prefix_;
 203   }
 204
 205   bool InDomain(const Slice& src) const override {
 206     if (src.size() >= prefix_.size()) {
 207       return Slice(src.data(), prefix_.size()) == prefix_;
 208     }
 209     return false;
 210   }
 211
 212   bool InRange(const Slice& dst) const override { return dst == prefix_; }
 213
 214   bool FullLengthEnabled(size_t* /*len*/) const override { return false; }
 215 };
 216
 217 }  // namespace
 218
 219 class PrefixTest : public testing::Test {
 220  public:
 221   std::shared_ptr<DB> OpenDb() {
 222     DB* db;
 223
 224     options.create_if_missing = true;
 225     options.write_buffer_size = FLAGS_write_buffer_size;
 226     options.max_write_buffer_number = FLAGS_max_write_buffer_number;
 227     options.min_write_buffer_number_to_merge =
 228       FLAGS_min_write_buffer_number_to_merge;
 229
 230     options.memtable_prefix_bloom_size_ratio =
 231         FLAGS_memtable_prefix_bloom_size_ratio;
 232     options.memtable_huge_page_size = FLAGS_memtable_huge_page_size;
 233
 234     options.prefix_extractor.reset(NewFixedPrefixTransform(8));
 235     BlockBasedTableOptions bbto;
 236     bbto.filter_policy.reset(NewBloomFilterPolicy(10, false));
 237     bbto.whole_key_filtering = false;
 238     options.table_factory.reset(NewBlockBasedTableFactory(bbto));
 239     options.allow_concurrent_memtable_write = false;
 240
 241     Status s = DB::Open(options, kDbName,  &db);
 242     EXPECT_OK(s);
 243     return std::shared_ptr<DB>(db);
 244   }
 245
 246   void FirstOption() {
 247     option_config_ = kBegin;
 248   }
 249
 250   bool NextOptions(int bucket_count) {
 251     // skip some options
 252     option_config_++;
 253     if (option_config_ < kEnd) {
 254       options.prefix_extractor.reset(NewFixedPrefixTransform(8));
 255       switch(option_config_) {
 256         case kHashSkipList:
 257           options.memtable_factory.reset(
 258               NewHashSkipListRepFactory(bucket_count, FLAGS_skiplist_height));
 259           return true;
 260         case kHashLinkList:
 261           options.memtable_factory.reset(
 262               NewHashLinkListRepFactory(bucket_count));
 263           return true;
 264         case kHashLinkListHugePageTlb:
 265           options.memtable_factory.reset(
 266               NewHashLinkListRepFactory(bucket_count, 2 * 1024 * 1024));
 267           return true;
 268         case kHashLinkListTriggerSkipList:
 269           options.memtable_factory.reset(
 270               NewHashLinkListRepFactory(bucket_count, 0, 3));
 271           return true;
 272         default:
 273           return false;
 274       }
 275     }
 276     return false;
 277   }
 278
 279   PrefixTest() : option_config_(kBegin) {
 280     options.comparator = new TestKeyComparator();
 281   }
 282   ~PrefixTest() override { delete options.comparator; }
 283
 284  protected:
 285   enum OptionConfig {
 286     kBegin,
 287     kHashSkipList,
 288     kHashLinkList,
 289     kHashLinkListHugePageTlb,
 290     kHashLinkListTriggerSkipList,
 291     kEnd
 292   };
 293   int option_config_;
 294   Options options;
 295 };
 296
 297 TEST(SamePrefixTest, InDomainTest) {
 298   DB* db;
 299   Options options;
 300   options.create_if_missing = true;
 301   options.prefix_extractor.reset(new SamePrefixTransform("HHKB"));
 302   BlockBasedTableOptions bbto;
 303   bbto.filter_policy.reset(NewBloomFilterPolicy(10, false));
 304   bbto.whole_key_filtering = false;
 305   options.table_factory.reset(NewBlockBasedTableFactory(bbto));
 306   WriteOptions write_options;
 307   ReadOptions read_options;
 308   {
 309     ASSERT_OK(DestroyDB(kDbName, Options()));
 310     ASSERT_OK(DB::Open(options, kDbName, &db));
 311     ASSERT_OK(db->Put(write_options, "HHKB pro2", "Mar 24, 2006"));
 312     ASSERT_OK(db->Put(write_options, "HHKB pro2 Type-S", "June 29, 2011"));
 313     ASSERT_OK(db->Put(write_options, "Realforce 87u", "idk"));
 314     db->Flush(FlushOptions());
 315     std::string result;
 316     auto db_iter = db->NewIterator(ReadOptions());
 317
 318     db_iter->Seek("Realforce 87u");
 319     ASSERT_TRUE(db_iter->Valid());
 320     ASSERT_OK(db_iter->status());
 321     ASSERT_EQ(db_iter->key(), "Realforce 87u");
 322     ASSERT_EQ(db_iter->value(), "idk");
 323
 324     delete db_iter;
 325     delete db;
 326     ASSERT_OK(DestroyDB(kDbName, Options()));
 327   }
 328
 329   {
 330     ASSERT_OK(DB::Open(options, kDbName, &db));
 331     ASSERT_OK(db->Put(write_options, "pikachu", "1"));
 332     ASSERT_OK(db->Put(write_options, "Meowth", "1"));
 333     ASSERT_OK(db->Put(write_options, "Mewtwo", "idk"));
 334     db->Flush(FlushOptions());
 335     std::string result;
 336     auto db_iter = db->NewIterator(ReadOptions());
 337
 338     db_iter->Seek("Mewtwo");
 339     ASSERT_TRUE(db_iter->Valid());
 340     ASSERT_OK(db_iter->status());
 341     delete db_iter;
 342     delete db;
 343     ASSERT_OK(DestroyDB(kDbName, Options()));
 344   }
 345 }
 346
 347 TEST_F(PrefixTest, TestResult) {
 348   for (int num_buckets = 1; num_buckets <= 2; num_buckets++) {
 349     FirstOption();
 350     while (NextOptions(num_buckets)) {
 351       std::cout << "*** Mem table: " << options.memtable_factory->Name()
 352                 << " number of buckets: " << num_buckets
 353                 << std::endl;
 354       DestroyDB(kDbName, Options());
 355       auto db = OpenDb();
 356       WriteOptions write_options;
 357       ReadOptions read_options;
 358
 359       // 1. Insert one row.
 360       Slice v16("v16");
 361       PutKey(db.get(), write_options, 1, 6, v16);
 362       std::unique_ptr<Iterator> iter(db->NewIterator(read_options));
 363       SeekIterator(iter.get(), 1, 6);
 364       ASSERT_TRUE(iter->Valid());
 365       ASSERT_TRUE(v16 == iter->value());
 366       SeekIterator(iter.get(), 1, 5);
 367       ASSERT_TRUE(iter->Valid());
 368       ASSERT_TRUE(v16 == iter->value());
 369       SeekIterator(iter.get(), 1, 5);
 370       ASSERT_TRUE(iter->Valid());
 371       ASSERT_TRUE(v16 == iter->value());
 372       iter->Next();
 373       ASSERT_TRUE(!iter->Valid());
 374       ASSERT_OK(iter->status());
 375
 376       SeekIterator(iter.get(), 2, 0);
 377       ASSERT_TRUE(!iter->Valid());
 378       ASSERT_OK(iter->status());
 379
 380       ASSERT_EQ(v16.ToString(), Get(db.get(), read_options, 1, 6));
 381       ASSERT_EQ(kNotFoundResult, Get(db.get(), read_options, 1, 5));
 382       ASSERT_EQ(kNotFoundResult, Get(db.get(), read_options, 1, 7));
 383       ASSERT_EQ(kNotFoundResult, Get(db.get(), read_options, 0, 6));
 384       ASSERT_EQ(kNotFoundResult, Get(db.get(), read_options, 2, 6));
 385
 386       // 2. Insert an entry for the same prefix as the last entry in the bucket.
 387       Slice v17("v17");
 388       PutKey(db.get(), write_options, 1, 7, v17);
 389       iter.reset(db->NewIterator(read_options));
 390       SeekIterator(iter.get(), 1, 7);
 391       ASSERT_TRUE(iter->Valid());
 392       ASSERT_TRUE(v17 == iter->value());
 393
 394       SeekIterator(iter.get(), 1, 6);
 395       ASSERT_TRUE(iter->Valid());
 396       ASSERT_TRUE(v16 == iter->value());
 397       iter->Next();
 398       ASSERT_TRUE(iter->Valid());
 399       ASSERT_TRUE(v17 == iter->value());
 400       iter->Next();
 401       ASSERT_TRUE(!iter->Valid());
 402       ASSERT_OK(iter->status());
 403
 404       SeekIterator(iter.get(), 2, 0);
 405       ASSERT_TRUE(!iter->Valid());
 406       ASSERT_OK(iter->status());
 407
 408       // 3. Insert an entry for the same prefix as the head of the bucket.
 409       Slice v15("v15");
 410       PutKey(db.get(), write_options, 1, 5, v15);
 411       iter.reset(db->NewIterator(read_options));
 412
 413       SeekIterator(iter.get(), 1, 7);
 414       ASSERT_TRUE(iter->Valid());
 415       ASSERT_TRUE(v17 == iter->value());
 416
 417       SeekIterator(iter.get(), 1, 5);
 418       ASSERT_TRUE(iter->Valid());
 419       ASSERT_TRUE(v15 == iter->value());
 420       iter->Next();
 421       ASSERT_TRUE(iter->Valid());
 422       ASSERT_TRUE(v16 == iter->value());
 423       iter->Next();
 424       ASSERT_TRUE(iter->Valid());
 425       ASSERT_TRUE(v17 == iter->value());
 426
 427       SeekIterator(iter.get(), 1, 5);
 428       ASSERT_TRUE(iter->Valid());
 429       ASSERT_TRUE(v15 == iter->value());
 430
 431       ASSERT_EQ(v15.ToString(), Get(db.get(), read_options, 1, 5));
 432       ASSERT_EQ(v16.ToString(), Get(db.get(), read_options, 1, 6));
 433       ASSERT_EQ(v17.ToString(), Get(db.get(), read_options, 1, 7));
 434
 435       // 4. Insert an entry with a larger prefix
 436       Slice v22("v22");
 437       PutKey(db.get(), write_options, 2, 2, v22);
 438       iter.reset(db->NewIterator(read_options));
 439
 440       SeekIterator(iter.get(), 2, 2);
 441       ASSERT_TRUE(iter->Valid());
 442       ASSERT_TRUE(v22 == iter->value());
 443       SeekIterator(iter.get(), 2, 0);
 444       ASSERT_TRUE(iter->Valid());
 445       ASSERT_TRUE(v22 == iter->value());
 446
 447       SeekIterator(iter.get(), 1, 5);
 448       ASSERT_TRUE(iter->Valid());
 449       ASSERT_TRUE(v15 == iter->value());
 450
 451       SeekIterator(iter.get(), 1, 7);
 452       ASSERT_TRUE(iter->Valid());
 453       ASSERT_TRUE(v17 == iter->value());
 454
 455       // 5. Insert an entry with a smaller prefix
 456       Slice v02("v02");
 457       PutKey(db.get(), write_options, 0, 2, v02);
 458       iter.reset(db->NewIterator(read_options));
 459
 460       SeekIterator(iter.get(), 0, 2);
 461       ASSERT_TRUE(iter->Valid());
 462       ASSERT_TRUE(v02 == iter->value());
 463       SeekIterator(iter.get(), 0, 0);
 464       ASSERT_TRUE(iter->Valid());
 465       ASSERT_TRUE(v02 == iter->value());
 466
 467       SeekIterator(iter.get(), 2, 0);
 468       ASSERT_TRUE(iter->Valid());
 469       ASSERT_TRUE(v22 == iter->value());
 470
 471       SeekIterator(iter.get(), 1, 5);
 472       ASSERT_TRUE(iter->Valid());
 473       ASSERT_TRUE(v15 == iter->value());
 474
 475       SeekIterator(iter.get(), 1, 7);
 476       ASSERT_TRUE(iter->Valid());
 477       ASSERT_TRUE(v17 == iter->value());
 478
 479       // 6. Insert to the beginning and the end of the first prefix
 480       Slice v13("v13");
 481       Slice v18("v18");
 482       PutKey(db.get(), write_options, 1, 3, v13);
 483       PutKey(db.get(), write_options, 1, 8, v18);
 484       iter.reset(db->NewIterator(read_options));
 485       SeekIterator(iter.get(), 1, 7);
 486       ASSERT_TRUE(iter->Valid());
 487       ASSERT_TRUE(v17 == iter->value());
 488
 489       SeekIterator(iter.get(), 1, 3);
 490       ASSERT_TRUE(iter->Valid());
 491       ASSERT_TRUE(v13 == iter->value());
 492       iter->Next();
 493       ASSERT_TRUE(iter->Valid());
 494       ASSERT_TRUE(v15 == iter->value());
 495       iter->Next();
 496       ASSERT_TRUE(iter->Valid());
 497       ASSERT_TRUE(v16 == iter->value());
 498       iter->Next();
 499       ASSERT_TRUE(iter->Valid());
 500       ASSERT_TRUE(v17 == iter->value());
 501       iter->Next();
 502       ASSERT_TRUE(iter->Valid());
 503       ASSERT_TRUE(v18 == iter->value());
 504
 505       SeekIterator(iter.get(), 0, 0);
 506       ASSERT_TRUE(iter->Valid());
 507       ASSERT_TRUE(v02 == iter->value());
 508
 509       SeekIterator(iter.get(), 2, 0);
 510       ASSERT_TRUE(iter->Valid());
 511       ASSERT_TRUE(v22 == iter->value());
 512
 513       ASSERT_EQ(v22.ToString(), Get(db.get(), read_options, 2, 2));
 514       ASSERT_EQ(v02.ToString(), Get(db.get(), read_options, 0, 2));
 515       ASSERT_EQ(v13.ToString(), Get(db.get(), read_options, 1, 3));
 516       ASSERT_EQ(v15.ToString(), Get(db.get(), read_options, 1, 5));
 517       ASSERT_EQ(v16.ToString(), Get(db.get(), read_options, 1, 6));
 518       ASSERT_EQ(v17.ToString(), Get(db.get(), read_options, 1, 7));
 519       ASSERT_EQ(v18.ToString(), Get(db.get(), read_options, 1, 8));
 520     }
 521   }
 522 }
 523
 524 // Show results in prefix
 525 TEST_F(PrefixTest, PrefixValid) {
 526   for (int num_buckets = 1; num_buckets <= 2; num_buckets++) {
 527     FirstOption();
 528     while (NextOptions(num_buckets)) {
 529       std::cout << "*** Mem table: " << options.memtable_factory->Name()
 530                 << " number of buckets: " << num_buckets << std::endl;
 531       DestroyDB(kDbName, Options());
 532       auto db = OpenDb();
 533       WriteOptions write_options;
 534       ReadOptions read_options;
 535
 536       // Insert keys with common prefix and one key with different
 537       Slice v16("v16");
 538       Slice v17("v17");
 539       Slice v18("v18");
 540       Slice v19("v19");
 541       PutKey(db.get(), write_options, 12345, 6, v16);
 542       PutKey(db.get(), write_options, 12345, 7, v17);
 543       PutKey(db.get(), write_options, 12345, 8, v18);
 544       PutKey(db.get(), write_options, 12345, 9, v19);
 545       PutKey(db.get(), write_options, 12346, 8, v16);
 546       db->Flush(FlushOptions());
 547       TestKey test_key(12346, 8);
 548       std::string s;
 549       ASSERT_OK(db->Delete(write_options, TestKeyToSlice(s, test_key)));
 550       ASSERT_OK(db->Flush(FlushOptions()));
 551       read_options.prefix_same_as_start = true;
 552       std::unique_ptr<Iterator> iter(db->NewIterator(read_options));
 553       SeekIterator(iter.get(), 12345, 6);
 554       ASSERT_TRUE(iter->Valid());
 555       ASSERT_TRUE(v16 == iter->value());
 556
 557       iter->Next();
 558       ASSERT_TRUE(iter->Valid());
 559       ASSERT_TRUE(v17 == iter->value());
 560
 561       iter->Next();
 562       ASSERT_TRUE(iter->Valid());
 563       ASSERT_TRUE(v18 == iter->value());
 564
 565       iter->Next();
 566       ASSERT_TRUE(iter->Valid());
 567       ASSERT_TRUE(v19 == iter->value());
 568       iter->Next();
 569       ASSERT_FALSE(iter->Valid());
 570       ASSERT_EQ(kNotFoundResult, Get(db.get(), read_options, 12346, 8));
 571
 572       // Verify seeking past the prefix won't return a result.
 573       SeekIterator(iter.get(), 12345, 10);
 574       ASSERT_TRUE(!iter->Valid());
 575       ASSERT_OK(iter->status());
 576     }
 577   }
 578 }
 579
 580 TEST_F(PrefixTest, DynamicPrefixIterator) {
 581   while (NextOptions(FLAGS_bucket_count)) {
 582     std::cout << "*** Mem table: " << options.memtable_factory->Name()
 583         << std::endl;
 584     DestroyDB(kDbName, Options());
 585     auto db = OpenDb();
 586     WriteOptions write_options;
 587     ReadOptions read_options;
 588
 589     std::vector<uint64_t> prefixes;
 590     for (uint64_t i = 0; i < FLAGS_total_prefixes; ++i) {
 591       prefixes.push_back(i);
 592     }
 593
 594     if (FLAGS_random_prefix) {
 595       RandomShuffle(prefixes.begin(), prefixes.end());
 596     }
 597
 598     HistogramImpl hist_put_time;
 599     HistogramImpl hist_put_comparison;
 600
 601     // insert x random prefix, each with y continuous element.
 602     for (auto prefix : prefixes) {
 603        for (uint64_t sorted = 0; sorted < FLAGS_items_per_prefix; sorted++) {
 604         TestKey test_key(prefix, sorted);
 605
 606         std::string s;
 607         Slice key = TestKeyToSlice(s, test_key);
 608         std::string value(FLAGS_value_size, 0);
 609
 610         get_perf_context()->Reset();
 611         StopWatchNano timer(Env::Default(), true);
 612         ASSERT_OK(db->Put(write_options, key, value));
 613         hist_put_time.Add(timer.ElapsedNanos());
 614         hist_put_comparison.Add(get_perf_context()->user_key_comparison_count);
 615       }
 616     }
 617
 618     std::cout << "Put key comparison: \n" << hist_put_comparison.ToString()
 619               << "Put time: \n" << hist_put_time.ToString();
 620
 621     // test seek existing keys
 622     HistogramImpl hist_seek_time;
 623     HistogramImpl hist_seek_comparison;
 624
 625     std::unique_ptr<Iterator> iter(db->NewIterator(read_options));
 626
 627     for (auto prefix : prefixes) {
 628       TestKey test_key(prefix, FLAGS_items_per_prefix / 2);
 629       std::string s;
 630       Slice key = TestKeyToSlice(s, test_key);
 631       std::string value = "v" + ToString(0);
 632
 633       get_perf_context()->Reset();
 634       StopWatchNano timer(Env::Default(), true);
 635       auto key_prefix = options.prefix_extractor->Transform(key);
 636       uint64_t total_keys = 0;
 637       for (iter->Seek(key);
 638            iter->Valid() && iter->key().starts_with(key_prefix);
 639            iter->Next()) {
 640         if (FLAGS_trigger_deadlock) {
 641           std::cout << "Behold the deadlock!\n";
 642           db->Delete(write_options, iter->key());
 643         }
 644         total_keys++;
 645       }
 646       hist_seek_time.Add(timer.ElapsedNanos());
 647       hist_seek_comparison.Add(get_perf_context()->user_key_comparison_count);
 648       ASSERT_EQ(total_keys, FLAGS_items_per_prefix - FLAGS_items_per_prefix/2);
 649     }
 650
 651     std::cout << "Seek key comparison: \n"
 652               << hist_seek_comparison.ToString()
 653               << "Seek time: \n"
 654               << hist_seek_time.ToString();
 655
 656     // test non-existing keys
 657     HistogramImpl hist_no_seek_time;
 658     HistogramImpl hist_no_seek_comparison;
 659
 660     for (auto prefix = FLAGS_total_prefixes;
 661          prefix < FLAGS_total_prefixes + 10000;
 662          prefix++) {
 663       TestKey test_key(prefix, 0);
 664       std::string s;
 665       Slice key = TestKeyToSlice(s, test_key);
 666
 667       get_perf_context()->Reset();
 668       StopWatchNano timer(Env::Default(), true);
 669       iter->Seek(key);
 670       hist_no_seek_time.Add(timer.ElapsedNanos());
 671       hist_no_seek_comparison.Add(get_perf_context()->user_key_comparison_count);
 672       ASSERT_TRUE(!iter->Valid());
 673       ASSERT_OK(iter->status());
 674     }
 675
 676     std::cout << "non-existing Seek key comparison: \n"
 677               << hist_no_seek_comparison.ToString()
 678               << "non-existing Seek time: \n"
 679               << hist_no_seek_time.ToString();
 680   }
 681 }
 682
 683 TEST_F(PrefixTest, PrefixSeekModePrev) {
 684   // Only for SkipListFactory
 685   options.memtable_factory.reset(new SkipListFactory);
 686   options.merge_operator = MergeOperators::CreatePutOperator();
 687   options.write_buffer_size = 1024 * 1024;
 688   Random rnd(1);
 689   for (size_t m = 1; m < 100; m++) {
 690     std::cout << "[" + std::to_string(m) + "]" + "*** Mem table: "
 691               << options.memtable_factory->Name() << std::endl;
 692     DestroyDB(kDbName, Options());
 693     auto db = OpenDb();
 694     WriteOptions write_options;
 695     ReadOptions read_options;
 696     std::map<TestKey, std::string, TestKeyComparator> entry_maps[3], whole_map;
 697     for (uint64_t i = 0; i < 10; i++) {
 698       int div = i % 3 + 1;
 699       for (uint64_t j = 0; j < 10; j++) {
 700         whole_map[TestKey(i, j)] = entry_maps[rnd.Uniform(div)][TestKey(i, j)] =
 701             'v' + std::to_string(i) + std::to_string(j);
 702       }
 703     }
 704
 705     std::map<TestKey, std::string, TestKeyComparator> type_map;
 706     for (size_t i = 0; i < 3; i++) {
 707       for (auto& kv : entry_maps[i]) {
 708         if (rnd.OneIn(3)) {
 709           PutKey(db.get(), write_options, kv.first, kv.second);
 710           type_map[kv.first] = "value";
 711         } else {
 712           MergeKey(db.get(), write_options, kv.first, kv.second);
 713           type_map[kv.first] = "merge";
 714         }
 715       }
 716       if (i < 2) {
 717         db->Flush(FlushOptions());
 718       }
 719     }
 720
 721     for (size_t i = 0; i < 2; i++) {
 722       for (auto& kv : entry_maps[i]) {
 723         if (rnd.OneIn(10)) {
 724           whole_map.erase(kv.first);
 725           DeleteKey(db.get(), write_options, kv.first);
 726           entry_maps[2][kv.first] = "delete";
 727         }
 728       }
 729     }
 730
 731     if (FLAGS_enable_print) {
 732       for (size_t i = 0; i < 3; i++) {
 733         for (auto& kv : entry_maps[i]) {
 734           std::cout << "[" << i << "]" << kv.first.prefix << kv.first.sorted
 735                     << " " << kv.second + " " + type_map[kv.first] << std::endl;
 736         }
 737       }
 738     }
 739
 740     std::unique_ptr<Iterator> iter(db->NewIterator(read_options));
 741     for (uint64_t prefix = 0; prefix < 10; prefix++) {
 742       uint64_t start_suffix = rnd.Uniform(9);
 743       SeekIterator(iter.get(), prefix, start_suffix);
 744       auto it = whole_map.find(TestKey(prefix, start_suffix));
 745       if (it == whole_map.end()) {
 746         continue;
 747       }
 748       ASSERT_NE(it, whole_map.end());
 749       ASSERT_TRUE(iter->Valid());
 750       if (FLAGS_enable_print) {
 751         std::cout << "round " << prefix
 752                   << " iter: " << SliceToTestKey(iter->key()).prefix
 753                   << SliceToTestKey(iter->key()).sorted
 754                   << " | map: " << it->first.prefix << it->first.sorted << " | "
 755                   << iter->value().ToString() << " " << it->second << std::endl;
 756       }
 757       ASSERT_EQ(iter->value(), it->second);
 758       uint64_t stored_prefix = prefix;
 759       for (size_t k = 0; k < 9; k++) {
 760         if (rnd.OneIn(2) || it == whole_map.begin()) {
 761           iter->Next();
 762           ++it;
 763           if (FLAGS_enable_print) {
 764             std::cout << "Next >> ";
 765           }
 766         } else {
 767           iter->Prev();
 768           it--;
 769           if (FLAGS_enable_print) {
 770             std::cout << "Prev >> ";
 771           }
 772         }
 773         if (!iter->Valid() ||
 774             SliceToTestKey(iter->key()).prefix != stored_prefix) {
 775           break;
 776         }
 777         ASSERT_OK(iter->status());
 778         stored_prefix = SliceToTestKey(iter->key()).prefix;
 779         ASSERT_TRUE(iter->Valid());
 780         ASSERT_NE(it, whole_map.end());
 781         ASSERT_EQ(iter->value(), it->second);
 782         if (FLAGS_enable_print) {
 783           std::cout << "iter: " << SliceToTestKey(iter->key()).prefix
 784                     << SliceToTestKey(iter->key()).sorted
 785                     << " | map: " << it->first.prefix << it->first.sorted
 786                     << " | " << iter->value().ToString() << " " << it->second
 787                     << std::endl;
 788         }
 789       }
 790     }
 791   }
 792 }
 793
 794 TEST_F(PrefixTest, PrefixSeekModePrev2) {
 795   // Only for SkipListFactory
 796   // test the case
 797   //        iter1                iter2
 798   // | prefix | suffix |  | prefix | suffix |
 799   // |   1    |   1    |  |   1    |   2    |
 800   // |   1    |   3    |  |   1    |   4    |
 801   // |   2    |   1    |  |   3    |   3    |
 802   // |   2    |   2    |  |   3    |   4    |
 803   // after seek(15), iter1 will be at 21 and iter2 will be 33.
 804   // Then if call Prev() in prefix mode where SeekForPrev(21) gets called,
 805   // iter2 should turn to invalid state because of bloom filter.
 806   options.memtable_factory.reset(new SkipListFactory);
 807   options.write_buffer_size = 1024 * 1024;
 808   std::string v13("v13");
 809   ASSERT_OK(DestroyDB(kDbName, Options()));
 810   auto db = OpenDb();
 811   WriteOptions write_options;
 812   ReadOptions read_options;
 813   PutKey(db.get(), write_options, TestKey(1, 2), "v12");
 814   PutKey(db.get(), write_options, TestKey(1, 4), "v14");
 815   PutKey(db.get(), write_options, TestKey(3, 3), "v33");
 816   PutKey(db.get(), write_options, TestKey(3, 4), "v34");
 817   ASSERT_OK(db->Flush(FlushOptions()));
 818   ASSERT_OK(
 819       static_cast_with_check<DBImpl>(db.get())->TEST_WaitForFlushMemTable());
 820   PutKey(db.get(), write_options, TestKey(1, 1), "v11");
 821   PutKey(db.get(), write_options, TestKey(1, 3), "v13");
 822   PutKey(db.get(), write_options, TestKey(2, 1), "v21");
 823   PutKey(db.get(), write_options, TestKey(2, 2), "v22");
 824   ASSERT_OK(db->Flush(FlushOptions()));
 825   ASSERT_OK(
 826       static_cast_with_check<DBImpl>(db.get())->TEST_WaitForFlushMemTable());
 827   std::unique_ptr<Iterator> iter(db->NewIterator(read_options));
 828   SeekIterator(iter.get(), 1, 5);
 829   iter->Prev();
 830   ASSERT_TRUE(iter->Valid());
 831   ASSERT_EQ(iter->value(), v13);
 832 }
 833
 834 TEST_F(PrefixTest, PrefixSeekModePrev3) {
 835   // Only for SkipListFactory
 836   // test SeekToLast() with iterate_upper_bound_ in prefix_seek_mode
 837   options.memtable_factory.reset(new SkipListFactory);
 838   options.write_buffer_size = 1024 * 1024;
 839   std::string v14("v14");
 840   TestKey upper_bound_key = TestKey(1, 5);
 841   std::string s;
 842   Slice upper_bound = TestKeyToSlice(s, upper_bound_key);
 843
 844   {
 845     ASSERT_OK(DestroyDB(kDbName, Options()));
 846     auto db = OpenDb();
 847     WriteOptions write_options;
 848     ReadOptions read_options;
 849     read_options.iterate_upper_bound = &upper_bound;
 850     PutKey(db.get(), write_options, TestKey(1, 2), "v12");
 851     PutKey(db.get(), write_options, TestKey(1, 4), "v14");
 852     ASSERT_OK(db->Flush(FlushOptions()));
 853     ASSERT_OK(
 854         static_cast_with_check<DBImpl>(db.get())->TEST_WaitForFlushMemTable());
 855     PutKey(db.get(), write_options, TestKey(1, 1), "v11");
 856     PutKey(db.get(), write_options, TestKey(1, 3), "v13");
 857     PutKey(db.get(), write_options, TestKey(2, 1), "v21");
 858     PutKey(db.get(), write_options, TestKey(2, 2), "v22");
 859     ASSERT_OK(db->Flush(FlushOptions()));
 860     ASSERT_OK(
 861         static_cast_with_check<DBImpl>(db.get())->TEST_WaitForFlushMemTable());
 862     std::unique_ptr<Iterator> iter(db->NewIterator(read_options));
 863     iter->SeekToLast();
 864     ASSERT_EQ(iter->value(), v14);
 865   }
 866   {
 867     ASSERT_OK(DestroyDB(kDbName, Options()));
 868     auto db = OpenDb();
 869     WriteOptions write_options;
 870     ReadOptions read_options;
 871     read_options.iterate_upper_bound = &upper_bound;
 872     PutKey(db.get(), write_options, TestKey(1, 2), "v12");
 873     PutKey(db.get(), write_options, TestKey(1, 4), "v14");
 874     PutKey(db.get(), write_options, TestKey(3, 3), "v33");
 875     PutKey(db.get(), write_options, TestKey(3, 4), "v34");
 876     ASSERT_OK(db->Flush(FlushOptions()));
 877     ASSERT_OK(
 878         static_cast_with_check<DBImpl>(db.get())->TEST_WaitForFlushMemTable());
 879     PutKey(db.get(), write_options, TestKey(1, 1), "v11");
 880     PutKey(db.get(), write_options, TestKey(1, 3), "v13");
 881     ASSERT_OK(db->Flush(FlushOptions()));
 882     ASSERT_OK(
 883         static_cast_with_check<DBImpl>(db.get())->TEST_WaitForFlushMemTable());
 884     std::unique_ptr<Iterator> iter(db->NewIterator(read_options));
 885     iter->SeekToLast();
 886     ASSERT_EQ(iter->value(), v14);
 887   }
 888 }
 889
 890 }  // namespace ROCKSDB_NAMESPACE
 891
 892 int main(int argc, char** argv) {
 893   ::testing::InitGoogleTest(&argc, argv);
 894   ParseCommandLineFlags(&argc, &argv, true);
 895   return RUN_ALL_TESTS();
 896 }
 897
 898 #endif  // GFLAGS
 899
 900 #else
 901 #include <stdio.h>
 902
 903 int main(int /*argc*/, char** /*argv*/) {
 904   fprintf(stderr,
 905           "SKIPPED as HashSkipList and HashLinkList are not supported in "
 906           "ROCKSDB_LITE\n");
 907   return 0;
 908 }
 909
 910 #endif  // !ROCKSDB_LITE