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.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"
  36
  37 using GFLAGS_NAMESPACE::ParseCommandLineFlags;
  38
  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.");
  54
  55 // Path to the database on file system
  56 const std::string kDbName = rocksdb::test::PerThreadDBPath("prefix_test");
  57
  58 namespace rocksdb {
  59
  60 struct TestKey {
  61   uint64_t prefix;
  62   uint64_t sorted;
  63
  64   TestKey(uint64_t _prefix, uint64_t _sorted)
  65       : prefix(_prefix), sorted(_sorted) {}
  66 };
  67
  68 // return a slice backed by test_key
  69 inline Slice TestKeyToSlice(std::string &s, const TestKey& test_key) {
  70   s.clear();
  71   PutFixed64(&s, test_key.prefix);
  72   PutFixed64(&s, test_key.sorted);
  73   return Slice(s.c_str(), s.size());
  74 }
  75
  76 inline const TestKey SliceToTestKey(const Slice& slice) {
  77   return TestKey(DecodeFixed64(slice.data()),
  78     DecodeFixed64(slice.data() + 8));
  79 }
  80
  81 class TestKeyComparator : public Comparator {
  82  public:
  83
  84   // Compare needs to be aware of the possibility of a and/or b is
  85   // prefix only
  86   virtual 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;
  94     } else {
  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
  99         EXPECT_TRUE(
 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;
 104       } else {
 105         // both a and b are prefix
 106         if (a.size() == sizeof(uint64_t)) {
 107           return 0;
 108         }
 109
 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;
 115       }
 116     }
 117     return 0;
 118   }
 119
 120   bool operator()(const TestKey& a, const TestKey& b) const {
 121     std::string sa, sb;
 122     return Compare(TestKeyToSlice(sa, a), TestKeyToSlice(sb, b)) < 0;
 123   }
 124
 125   virtual const char* Name() const override {
 126     return "TestKeyComparator";
 127   }
 128
 129   virtual void FindShortestSeparator(std::string* /*start*/,
 130                                      const Slice& /*limit*/) const override {}
 131
 132   virtual 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   virtual const char* Name() const override { return name_.c_str(); }
 199
 200   virtual Slice Transform(const Slice& src) const override {
 201     assert(InDomain(src));
 202     return prefix_;
 203   }
 204
 205   virtual 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   virtual bool InRange(const Slice& dst) const override {
 213     return dst == prefix_;
 214   }
 215
 216   virtual bool FullLengthEnabled(size_t* /*len*/) const override {
 217     return false;
 218   }
 219 };
 220
 221 }  // namespace
 222
 223 class PrefixTest : public testing::Test {
 224  public:
 225   std::shared_ptr<DB> OpenDb() {
 226     DB* db;
 227
 228     options.create_if_missing = true;
 229     options.write_buffer_size = FLAGS_write_buffer_size;
 230     options.max_write_buffer_number = FLAGS_max_write_buffer_number;
 231     options.min_write_buffer_number_to_merge =
 232       FLAGS_min_write_buffer_number_to_merge;
 233
 234     options.memtable_prefix_bloom_size_ratio =
 235         FLAGS_memtable_prefix_bloom_size_ratio;
 236     options.memtable_huge_page_size = FLAGS_memtable_huge_page_size;
 237
 238     options.prefix_extractor.reset(NewFixedPrefixTransform(8));
 239     BlockBasedTableOptions bbto;
 240     bbto.filter_policy.reset(NewBloomFilterPolicy(10, false));
 241     bbto.whole_key_filtering = false;
 242     options.table_factory.reset(NewBlockBasedTableFactory(bbto));
 243     options.allow_concurrent_memtable_write = false;
 244
 245     Status s = DB::Open(options, kDbName,  &db);
 246     EXPECT_OK(s);
 247     return std::shared_ptr<DB>(db);
 248   }
 249
 250   void FirstOption() {
 251     option_config_ = kBegin;
 252   }
 253
 254   bool NextOptions(int bucket_count) {
 255     // skip some options
 256     option_config_++;
 257     if (option_config_ < kEnd) {
 258       options.prefix_extractor.reset(NewFixedPrefixTransform(8));
 259       switch(option_config_) {
 260         case kHashSkipList:
 261           options.memtable_factory.reset(
 262               NewHashSkipListRepFactory(bucket_count, FLAGS_skiplist_height));
 263           return true;
 264         case kHashLinkList:
 265           options.memtable_factory.reset(
 266               NewHashLinkListRepFactory(bucket_count));
 267           return true;
 268         case kHashLinkListHugePageTlb:
 269           options.memtable_factory.reset(
 270               NewHashLinkListRepFactory(bucket_count, 2 * 1024 * 1024));
 271           return true;
 272         case kHashLinkListTriggerSkipList:
 273           options.memtable_factory.reset(
 274               NewHashLinkListRepFactory(bucket_count, 0, 3));
 275           return true;
 276         default:
 277           return false;
 278       }
 279     }
 280     return false;
 281   }
 282
 283   PrefixTest() : option_config_(kBegin) {
 284     options.comparator = new TestKeyComparator();
 285   }
 286   ~PrefixTest() {
 287     delete options.comparator;
 288   }
 289  protected:
 290   enum OptionConfig {
 291     kBegin,
 292     kHashSkipList,
 293     kHashLinkList,
 294     kHashLinkListHugePageTlb,
 295     kHashLinkListTriggerSkipList,
 296     kEnd
 297   };
 298   int option_config_;
 299   Options options;
 300 };
 301
 302 TEST(SamePrefixTest, InDomainTest) {
 303   DB* db;
 304   Options options;
 305   options.create_if_missing = true;
 306   options.prefix_extractor.reset(new SamePrefixTransform("HHKB"));
 307   BlockBasedTableOptions bbto;
 308   bbto.filter_policy.reset(NewBloomFilterPolicy(10, false));
 309   bbto.whole_key_filtering = false;
 310   options.table_factory.reset(NewBlockBasedTableFactory(bbto));
 311   WriteOptions write_options;
 312   ReadOptions read_options;
 313   {
 314     ASSERT_OK(DestroyDB(kDbName, Options()));
 315     ASSERT_OK(DB::Open(options, kDbName, &db));
 316     ASSERT_OK(db->Put(write_options, "HHKB pro2", "Mar 24, 2006"));
 317     ASSERT_OK(db->Put(write_options, "HHKB pro2 Type-S", "June 29, 2011"));
 318     ASSERT_OK(db->Put(write_options, "Realforce 87u", "idk"));
 319     db->Flush(FlushOptions());
 320     std::string result;
 321     auto db_iter = db->NewIterator(ReadOptions());
 322
 323     db_iter->Seek("Realforce 87u");
 324     ASSERT_TRUE(db_iter->Valid());
 325     ASSERT_OK(db_iter->status());
 326     ASSERT_EQ(db_iter->key(), "Realforce 87u");
 327     ASSERT_EQ(db_iter->value(), "idk");
 328
 329     delete db_iter;
 330     delete db;
 331     ASSERT_OK(DestroyDB(kDbName, Options()));
 332   }
 333
 334   {
 335     ASSERT_OK(DB::Open(options, kDbName, &db));
 336     ASSERT_OK(db->Put(write_options, "pikachu", "1"));
 337     ASSERT_OK(db->Put(write_options, "Meowth", "1"));
 338     ASSERT_OK(db->Put(write_options, "Mewtwo", "idk"));
 339     db->Flush(FlushOptions());
 340     std::string result;
 341     auto db_iter = db->NewIterator(ReadOptions());
 342
 343     db_iter->Seek("Mewtwo");
 344     ASSERT_TRUE(db_iter->Valid());
 345     ASSERT_OK(db_iter->status());
 346     delete db_iter;
 347     delete db;
 348     ASSERT_OK(DestroyDB(kDbName, Options()));
 349   }
 350 }
 351
 352 TEST_F(PrefixTest, TestResult) {
 353   for (int num_buckets = 1; num_buckets <= 2; num_buckets++) {
 354     FirstOption();
 355     while (NextOptions(num_buckets)) {
 356       std::cout << "*** Mem table: " << options.memtable_factory->Name()
 357                 << " number of buckets: " << num_buckets
 358                 << std::endl;
 359       DestroyDB(kDbName, Options());
 360       auto db = OpenDb();
 361       WriteOptions write_options;
 362       ReadOptions read_options;
 363
 364       // 1. Insert one row.
 365       Slice v16("v16");
 366       PutKey(db.get(), write_options, 1, 6, v16);
 367       std::unique_ptr<Iterator> iter(db->NewIterator(read_options));
 368       SeekIterator(iter.get(), 1, 6);
 369       ASSERT_TRUE(iter->Valid());
 370       ASSERT_TRUE(v16 == iter->value());
 371       SeekIterator(iter.get(), 1, 5);
 372       ASSERT_TRUE(iter->Valid());
 373       ASSERT_TRUE(v16 == iter->value());
 374       SeekIterator(iter.get(), 1, 5);
 375       ASSERT_TRUE(iter->Valid());
 376       ASSERT_TRUE(v16 == iter->value());
 377       iter->Next();
 378       ASSERT_TRUE(!iter->Valid());
 379
 380       SeekIterator(iter.get(), 2, 0);
 381       ASSERT_TRUE(!iter->Valid());
 382
 383       ASSERT_EQ(v16.ToString(), Get(db.get(), read_options, 1, 6));
 384       ASSERT_EQ(kNotFoundResult, Get(db.get(), read_options, 1, 5));
 385       ASSERT_EQ(kNotFoundResult, Get(db.get(), read_options, 1, 7));
 386       ASSERT_EQ(kNotFoundResult, Get(db.get(), read_options, 0, 6));
 387       ASSERT_EQ(kNotFoundResult, Get(db.get(), read_options, 2, 6));
 388
 389       // 2. Insert an entry for the same prefix as the last entry in the bucket.
 390       Slice v17("v17");
 391       PutKey(db.get(), write_options, 1, 7, v17);
 392       iter.reset(db->NewIterator(read_options));
 393       SeekIterator(iter.get(), 1, 7);
 394       ASSERT_TRUE(iter->Valid());
 395       ASSERT_TRUE(v17 == iter->value());
 396
 397       SeekIterator(iter.get(), 1, 6);
 398       ASSERT_TRUE(iter->Valid());
 399       ASSERT_TRUE(v16 == iter->value());
 400       iter->Next();
 401       ASSERT_TRUE(iter->Valid());
 402       ASSERT_TRUE(v17 == iter->value());
 403       iter->Next();
 404       ASSERT_TRUE(!iter->Valid());
 405
 406       SeekIterator(iter.get(), 2, 0);
 407       ASSERT_TRUE(!iter->Valid());
 408
 409       // 3. Insert an entry for the same prefix as the head of the bucket.
 410       Slice v15("v15");
 411       PutKey(db.get(), write_options, 1, 5, v15);
 412       iter.reset(db->NewIterator(read_options));
 413
 414       SeekIterator(iter.get(), 1, 7);
 415       ASSERT_TRUE(iter->Valid());
 416       ASSERT_TRUE(v17 == iter->value());
 417
 418       SeekIterator(iter.get(), 1, 5);
 419       ASSERT_TRUE(iter->Valid());
 420       ASSERT_TRUE(v15 == iter->value());
 421       iter->Next();
 422       ASSERT_TRUE(iter->Valid());
 423       ASSERT_TRUE(v16 == iter->value());
 424       iter->Next();
 425       ASSERT_TRUE(iter->Valid());
 426       ASSERT_TRUE(v17 == iter->value());
 427
 428       SeekIterator(iter.get(), 1, 5);
 429       ASSERT_TRUE(iter->Valid());
 430       ASSERT_TRUE(v15 == iter->value());
 431
 432       ASSERT_EQ(v15.ToString(), Get(db.get(), read_options, 1, 5));
 433       ASSERT_EQ(v16.ToString(), Get(db.get(), read_options, 1, 6));
 434       ASSERT_EQ(v17.ToString(), Get(db.get(), read_options, 1, 7));
 435
 436       // 4. Insert an entry with a larger prefix
 437       Slice v22("v22");
 438       PutKey(db.get(), write_options, 2, 2, v22);
 439       iter.reset(db->NewIterator(read_options));
 440
 441       SeekIterator(iter.get(), 2, 2);
 442       ASSERT_TRUE(iter->Valid());
 443       ASSERT_TRUE(v22 == iter->value());
 444       SeekIterator(iter.get(), 2, 0);
 445       ASSERT_TRUE(iter->Valid());
 446       ASSERT_TRUE(v22 == iter->value());
 447
 448       SeekIterator(iter.get(), 1, 5);
 449       ASSERT_TRUE(iter->Valid());
 450       ASSERT_TRUE(v15 == iter->value());
 451
 452       SeekIterator(iter.get(), 1, 7);
 453       ASSERT_TRUE(iter->Valid());
 454       ASSERT_TRUE(v17 == iter->value());
 455
 456       // 5. Insert an entry with a smaller prefix
 457       Slice v02("v02");
 458       PutKey(db.get(), write_options, 0, 2, v02);
 459       iter.reset(db->NewIterator(read_options));
 460
 461       SeekIterator(iter.get(), 0, 2);
 462       ASSERT_TRUE(iter->Valid());
 463       ASSERT_TRUE(v02 == iter->value());
 464       SeekIterator(iter.get(), 0, 0);
 465       ASSERT_TRUE(iter->Valid());
 466       ASSERT_TRUE(v02 == iter->value());
 467
 468       SeekIterator(iter.get(), 2, 0);
 469       ASSERT_TRUE(iter->Valid());
 470       ASSERT_TRUE(v22 == iter->value());
 471
 472       SeekIterator(iter.get(), 1, 5);
 473       ASSERT_TRUE(iter->Valid());
 474       ASSERT_TRUE(v15 == iter->value());
 475
 476       SeekIterator(iter.get(), 1, 7);
 477       ASSERT_TRUE(iter->Valid());
 478       ASSERT_TRUE(v17 == iter->value());
 479
 480       // 6. Insert to the beginning and the end of the first prefix
 481       Slice v13("v13");
 482       Slice v18("v18");
 483       PutKey(db.get(), write_options, 1, 3, v13);
 484       PutKey(db.get(), write_options, 1, 8, v18);
 485       iter.reset(db->NewIterator(read_options));
 486       SeekIterator(iter.get(), 1, 7);
 487       ASSERT_TRUE(iter->Valid());
 488       ASSERT_TRUE(v17 == iter->value());
 489
 490       SeekIterator(iter.get(), 1, 3);
 491       ASSERT_TRUE(iter->Valid());
 492       ASSERT_TRUE(v13 == iter->value());
 493       iter->Next();
 494       ASSERT_TRUE(iter->Valid());
 495       ASSERT_TRUE(v15 == iter->value());
 496       iter->Next();
 497       ASSERT_TRUE(iter->Valid());
 498       ASSERT_TRUE(v16 == iter->value());
 499       iter->Next();
 500       ASSERT_TRUE(iter->Valid());
 501       ASSERT_TRUE(v17 == iter->value());
 502       iter->Next();
 503       ASSERT_TRUE(iter->Valid());
 504       ASSERT_TRUE(v18 == iter->value());
 505
 506       SeekIterator(iter.get(), 0, 0);
 507       ASSERT_TRUE(iter->Valid());
 508       ASSERT_TRUE(v02 == iter->value());
 509
 510       SeekIterator(iter.get(), 2, 0);
 511       ASSERT_TRUE(iter->Valid());
 512       ASSERT_TRUE(v22 == iter->value());
 513
 514       ASSERT_EQ(v22.ToString(), Get(db.get(), read_options, 2, 2));
 515       ASSERT_EQ(v02.ToString(), Get(db.get(), read_options, 0, 2));
 516       ASSERT_EQ(v13.ToString(), Get(db.get(), read_options, 1, 3));
 517       ASSERT_EQ(v15.ToString(), Get(db.get(), read_options, 1, 5));
 518       ASSERT_EQ(v16.ToString(), Get(db.get(), read_options, 1, 6));
 519       ASSERT_EQ(v17.ToString(), Get(db.get(), read_options, 1, 7));
 520       ASSERT_EQ(v18.ToString(), Get(db.get(), read_options, 1, 8));
 521     }
 522   }
 523 }
 524
 525 // Show results in prefix
 526 TEST_F(PrefixTest, PrefixValid) {
 527   for (int num_buckets = 1; num_buckets <= 2; num_buckets++) {
 528     FirstOption();
 529     while (NextOptions(num_buckets)) {
 530       std::cout << "*** Mem table: " << options.memtable_factory->Name()
 531                 << " number of buckets: " << num_buckets << std::endl;
 532       DestroyDB(kDbName, Options());
 533       auto db = OpenDb();
 534       WriteOptions write_options;
 535       ReadOptions read_options;
 536
 537       // Insert keys with common prefix and one key with different
 538       Slice v16("v16");
 539       Slice v17("v17");
 540       Slice v18("v18");
 541       Slice v19("v19");
 542       PutKey(db.get(), write_options, 12345, 6, v16);
 543       PutKey(db.get(), write_options, 12345, 7, v17);
 544       PutKey(db.get(), write_options, 12345, 8, v18);
 545       PutKey(db.get(), write_options, 12345, 9, v19);
 546       PutKey(db.get(), write_options, 12346, 8, v16);
 547       db->Flush(FlushOptions());
 548       TestKey test_key(12346, 8);
 549       std::string s;
 550       db->Delete(write_options, TestKeyToSlice(s, test_key));
 551       db->Flush(FlushOptions());
 552       read_options.prefix_same_as_start = true;
 553       std::unique_ptr<Iterator> iter(db->NewIterator(read_options));
 554       SeekIterator(iter.get(), 12345, 6);
 555       ASSERT_TRUE(iter->Valid());
 556       ASSERT_TRUE(v16 == iter->value());
 557
 558       iter->Next();
 559       ASSERT_TRUE(iter->Valid());
 560       ASSERT_TRUE(v17 == iter->value());
 561
 562       iter->Next();
 563       ASSERT_TRUE(iter->Valid());
 564       ASSERT_TRUE(v18 == iter->value());
 565
 566       iter->Next();
 567       ASSERT_TRUE(iter->Valid());
 568       ASSERT_TRUE(v19 == iter->value());
 569       iter->Next();
 570       ASSERT_FALSE(iter->Valid());
 571       ASSERT_EQ(kNotFoundResult, Get(db.get(), read_options, 12346, 8));
 572
 573       // Verify seeking past the prefix won't return a result.
 574       SeekIterator(iter.get(), 12345, 10);
 575       ASSERT_TRUE(!iter->Valid());
 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       std::random_shuffle(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     }
 674
 675     std::cout << "non-existing Seek key comparison: \n"
 676               << hist_no_seek_comparison.ToString()
 677               << "non-existing Seek time: \n"
 678               << hist_no_seek_time.ToString();
 679   }
 680 }
 681
 682 TEST_F(PrefixTest, PrefixSeekModePrev) {
 683   // Only for SkipListFactory
 684   options.memtable_factory.reset(new SkipListFactory);
 685   options.merge_operator = MergeOperators::CreatePutOperator();
 686   options.write_buffer_size = 1024 * 1024;
 687   Random rnd(1);
 688   for (size_t m = 1; m < 100; m++) {
 689     std::cout << "[" + std::to_string(m) + "]" + "*** Mem table: "
 690               << options.memtable_factory->Name() << std::endl;
 691     DestroyDB(kDbName, Options());
 692     auto db = OpenDb();
 693     WriteOptions write_options;
 694     ReadOptions read_options;
 695     std::map<TestKey, std::string, TestKeyComparator> entry_maps[3], whole_map;
 696     for (uint64_t i = 0; i < 10; i++) {
 697       int div = i % 3 + 1;
 698       for (uint64_t j = 0; j < 10; j++) {
 699         whole_map[TestKey(i, j)] = entry_maps[rnd.Uniform(div)][TestKey(i, j)] =
 700             'v' + std::to_string(i) + std::to_string(j);
 701       }
 702     }
 703
 704     std::map<TestKey, std::string, TestKeyComparator> type_map;
 705     for (size_t i = 0; i < 3; i++) {
 706       for (auto& kv : entry_maps[i]) {
 707         if (rnd.OneIn(3)) {
 708           PutKey(db.get(), write_options, kv.first, kv.second);
 709           type_map[kv.first] = "value";
 710         } else {
 711           MergeKey(db.get(), write_options, kv.first, kv.second);
 712           type_map[kv.first] = "merge";
 713         }
 714       }
 715       if (i < 2) {
 716         db->Flush(FlushOptions());
 717       }
 718     }
 719
 720     for (size_t i = 0; i < 2; i++) {
 721       for (auto& kv : entry_maps[i]) {
 722         if (rnd.OneIn(10)) {
 723           whole_map.erase(kv.first);
 724           DeleteKey(db.get(), write_options, kv.first);
 725           entry_maps[2][kv.first] = "delete";
 726         }
 727       }
 728     }
 729
 730     if (FLAGS_enable_print) {
 731       for (size_t i = 0; i < 3; i++) {
 732         for (auto& kv : entry_maps[i]) {
 733           std::cout << "[" << i << "]" << kv.first.prefix << kv.first.sorted
 734                     << " " << kv.second + " " + type_map[kv.first] << std::endl;
 735         }
 736       }
 737     }
 738
 739     std::unique_ptr<Iterator> iter(db->NewIterator(read_options));
 740     for (uint64_t prefix = 0; prefix < 10; prefix++) {
 741       uint64_t start_suffix = rnd.Uniform(9);
 742       SeekIterator(iter.get(), prefix, start_suffix);
 743       auto it = whole_map.find(TestKey(prefix, start_suffix));
 744       if (it == whole_map.end()) {
 745         continue;
 746       }
 747       ASSERT_NE(it, whole_map.end());
 748       ASSERT_TRUE(iter->Valid());
 749       if (FLAGS_enable_print) {
 750         std::cout << "round " << prefix
 751                   << " iter: " << SliceToTestKey(iter->key()).prefix
 752                   << SliceToTestKey(iter->key()).sorted
 753                   << " | map: " << it->first.prefix << it->first.sorted << " | "
 754                   << iter->value().ToString() << " " << it->second << std::endl;
 755       }
 756       ASSERT_EQ(iter->value(), it->second);
 757       uint64_t stored_prefix = prefix;
 758       for (size_t k = 0; k < 9; k++) {
 759         if (rnd.OneIn(2) || it == whole_map.begin()) {
 760           iter->Next();
 761           it++;
 762           if (FLAGS_enable_print) {
 763             std::cout << "Next >> ";
 764           }
 765         } else {
 766           iter->Prev();
 767           it--;
 768           if (FLAGS_enable_print) {
 769             std::cout << "Prev >> ";
 770           }
 771         }
 772         if (!iter->Valid() ||
 773             SliceToTestKey(iter->key()).prefix != stored_prefix) {
 774           break;
 775         }
 776         stored_prefix = SliceToTestKey(iter->key()).prefix;
 777         ASSERT_TRUE(iter->Valid());
 778         ASSERT_NE(it, whole_map.end());
 779         ASSERT_EQ(iter->value(), it->second);
 780         if (FLAGS_enable_print) {
 781           std::cout << "iter: " << SliceToTestKey(iter->key()).prefix
 782                     << SliceToTestKey(iter->key()).sorted
 783                     << " | map: " << it->first.prefix << it->first.sorted
 784                     << " | " << iter->value().ToString() << " " << it->second
 785                     << std::endl;
 786         }
 787       }
 788     }
 789   }
 790 }
 791
 792 TEST_F(PrefixTest, PrefixSeekModePrev2) {
 793   // Only for SkipListFactory
 794   // test the case
 795   //        iter1                iter2
 796   // | prefix | suffix |  | prefix | suffix |
 797   // |   1    |   1    |  |   1    |   2    |
 798   // |   1    |   3    |  |   1    |   4    |
 799   // |   2    |   1    |  |   3    |   3    |
 800   // |   2    |   2    |  |   3    |   4    |
 801   // after seek(15), iter1 will be at 21 and iter2 will be 33.
 802   // Then if call Prev() in prefix mode where SeekForPrev(21) gets called,
 803   // iter2 should turn to invalid state because of bloom filter.
 804   options.memtable_factory.reset(new SkipListFactory);
 805   options.write_buffer_size = 1024 * 1024;
 806   std::string v13("v13");
 807   DestroyDB(kDbName, Options());
 808   auto db = OpenDb();
 809   WriteOptions write_options;
 810   ReadOptions read_options;
 811   PutKey(db.get(), write_options, TestKey(1, 2), "v12");
 812   PutKey(db.get(), write_options, TestKey(1, 4), "v14");
 813   PutKey(db.get(), write_options, TestKey(3, 3), "v33");
 814   PutKey(db.get(), write_options, TestKey(3, 4), "v34");
 815   db->Flush(FlushOptions());
 816   reinterpret_cast<DBImpl*>(db.get())->TEST_WaitForFlushMemTable();
 817   PutKey(db.get(), write_options, TestKey(1, 1), "v11");
 818   PutKey(db.get(), write_options, TestKey(1, 3), "v13");
 819   PutKey(db.get(), write_options, TestKey(2, 1), "v21");
 820   PutKey(db.get(), write_options, TestKey(2, 2), "v22");
 821   db->Flush(FlushOptions());
 822   reinterpret_cast<DBImpl*>(db.get())->TEST_WaitForFlushMemTable();
 823   std::unique_ptr<Iterator> iter(db->NewIterator(read_options));
 824   SeekIterator(iter.get(), 1, 5);
 825   iter->Prev();
 826   ASSERT_EQ(iter->value(), v13);
 827 }
 828
 829 TEST_F(PrefixTest, PrefixSeekModePrev3) {
 830   // Only for SkipListFactory
 831   // test SeekToLast() with iterate_upper_bound_ in prefix_seek_mode
 832   options.memtable_factory.reset(new SkipListFactory);
 833   options.write_buffer_size = 1024 * 1024;
 834   std::string v14("v14");
 835   TestKey upper_bound_key = TestKey(1, 5);
 836   std::string s;
 837   Slice upper_bound = TestKeyToSlice(s, upper_bound_key);
 838
 839   {
 840     DestroyDB(kDbName, Options());
 841     auto db = OpenDb();
 842     WriteOptions write_options;
 843     ReadOptions read_options;
 844     read_options.iterate_upper_bound = &upper_bound;
 845     PutKey(db.get(), write_options, TestKey(1, 2), "v12");
 846     PutKey(db.get(), write_options, TestKey(1, 4), "v14");
 847     db->Flush(FlushOptions());
 848     reinterpret_cast<DBImpl*>(db.get())->TEST_WaitForFlushMemTable();
 849     PutKey(db.get(), write_options, TestKey(1, 1), "v11");
 850     PutKey(db.get(), write_options, TestKey(1, 3), "v13");
 851     PutKey(db.get(), write_options, TestKey(2, 1), "v21");
 852     PutKey(db.get(), write_options, TestKey(2, 2), "v22");
 853     db->Flush(FlushOptions());
 854     reinterpret_cast<DBImpl*>(db.get())->TEST_WaitForFlushMemTable();
 855     std::unique_ptr<Iterator> iter(db->NewIterator(read_options));
 856     iter->SeekToLast();
 857     ASSERT_EQ(iter->value(), v14);
 858   }
 859   {
 860     DestroyDB(kDbName, Options());
 861     auto db = OpenDb();
 862     WriteOptions write_options;
 863     ReadOptions read_options;
 864     read_options.iterate_upper_bound = &upper_bound;
 865     PutKey(db.get(), write_options, TestKey(1, 2), "v12");
 866     PutKey(db.get(), write_options, TestKey(1, 4), "v14");
 867     PutKey(db.get(), write_options, TestKey(3, 3), "v33");
 868     PutKey(db.get(), write_options, TestKey(3, 4), "v34");
 869     db->Flush(FlushOptions());
 870     reinterpret_cast<DBImpl*>(db.get())->TEST_WaitForFlushMemTable();
 871     PutKey(db.get(), write_options, TestKey(1, 1), "v11");
 872     PutKey(db.get(), write_options, TestKey(1, 3), "v13");
 873     db->Flush(FlushOptions());
 874     reinterpret_cast<DBImpl*>(db.get())->TEST_WaitForFlushMemTable();
 875     std::unique_ptr<Iterator> iter(db->NewIterator(read_options));
 876     iter->SeekToLast();
 877     ASSERT_EQ(iter->value(), v14);
 878   }
 879 }
 880
 881 }  // end namespace rocksdb
 882
 883 int main(int argc, char** argv) {
 884   ::testing::InitGoogleTest(&argc, argv);
 885   ParseCommandLineFlags(&argc, &argv, true);
 886   return RUN_ALL_TESTS();
 887 }
 888
 889 #endif  // GFLAGS
 890
 891 #else
 892 #include <stdio.h>
 893
 894 int main(int /*argc*/, char** /*argv*/) {
 895   fprintf(stderr,
 896           "SKIPPED as HashSkipList and HashLinkList are not supported in "
 897           "ROCKSDB_LITE\n");
 898   return 0;
 899 }
 900
 901 #endif  // !ROCKSDB_LITE