ceph/src/rocksdb/db/prefix_test.cc

   1 //  Copyright (c) 2011-present, Facebook, Inc.  All rights reserved.
   2 //  This source code is licensed under the BSD-style license found in the
   3 //  LICENSE file in the root directory of this source tree. An additional grant
   4 //  of patent rights can be found in the PATENTS file in the same directory.
   5
   6 #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 <gflags/gflags.h>
  21 #include "db/db_impl.h"
  22 #include "monitoring/histogram.h"
  23 #include "rocksdb/comparator.h"
  24 #include "rocksdb/db.h"
  25 #include "rocksdb/filter_policy.h"
  26 #include "rocksdb/memtablerep.h"
  27 #include "rocksdb/perf_context.h"
  28 #include "rocksdb/slice_transform.h"
  29 #include "rocksdb/table.h"
  30 #include "util/random.h"
  31 #include "util/stop_watch.h"
  32 #include "util/string_util.h"
  33 #include "util/testharness.h"
  34 #include "utilities/merge_operators.h"
  35 #include "util/coding.h"
  36
  37 using GFLAGS::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::TmpDir() + "/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
 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() {
 283     delete options.comparator;
 284   }
 285  protected:
 286   enum OptionConfig {
 287     kBegin,
 288     kHashSkipList,
 289     kHashLinkList,
 290     kHashLinkListHugePageTlb,
 291     kHashLinkListTriggerSkipList,
 292     kEnd
 293   };
 294   int option_config_;
 295   Options options;
 296 };
 297
 298 TEST(SamePrefixTest, InDomainTest) {
 299   DB* db;
 300   Options options;
 301   options.create_if_missing = true;
 302   options.prefix_extractor.reset(new SamePrefixTransform("HHKB"));
 303   BlockBasedTableOptions bbto;
 304   bbto.filter_policy.reset(NewBloomFilterPolicy(10, false));
 305   bbto.whole_key_filtering = false;
 306   options.table_factory.reset(NewBlockBasedTableFactory(bbto));
 307   WriteOptions write_options;
 308   ReadOptions read_options;
 309   {
 310     ASSERT_OK(DestroyDB(kDbName, Options()));
 311     ASSERT_OK(DB::Open(options, kDbName, &db));
 312     ASSERT_OK(db->Put(write_options, "HHKB pro2", "Mar 24, 2006"));
 313     ASSERT_OK(db->Put(write_options, "HHKB pro2 Type-S", "June 29, 2011"));
 314     ASSERT_OK(db->Put(write_options, "Realforce 87u", "idk"));
 315     db->Flush(FlushOptions());
 316     std::string result;
 317     auto db_iter = db->NewIterator(ReadOptions());
 318
 319     db_iter->Seek("Realforce 87u");
 320     ASSERT_TRUE(db_iter->Valid());
 321     ASSERT_OK(db_iter->status());
 322     ASSERT_EQ(db_iter->key(), "Realforce 87u");
 323     ASSERT_EQ(db_iter->value(), "idk");
 324
 325     delete db_iter;
 326     delete db;
 327     ASSERT_OK(DestroyDB(kDbName, Options()));
 328   }
 329
 330   {
 331     ASSERT_OK(DB::Open(options, kDbName, &db));
 332     ASSERT_OK(db->Put(write_options, "pikachu", "1"));
 333     ASSERT_OK(db->Put(write_options, "Meowth", "1"));
 334     ASSERT_OK(db->Put(write_options, "Mewtwo", "idk"));
 335     db->Flush(FlushOptions());
 336     std::string result;
 337     auto db_iter = db->NewIterator(ReadOptions());
 338
 339     db_iter->Seek("Mewtwo");
 340     ASSERT_TRUE(db_iter->Valid());
 341     ASSERT_OK(db_iter->status());
 342     delete db_iter;
 343     delete db;
 344     ASSERT_OK(DestroyDB(kDbName, Options()));
 345   }
 346 }
 347
 348 TEST_F(PrefixTest, TestResult) {
 349   for (int num_buckets = 1; num_buckets <= 2; num_buckets++) {
 350     FirstOption();
 351     while (NextOptions(num_buckets)) {
 352       std::cout << "*** Mem table: " << options.memtable_factory->Name()
 353                 << " number of buckets: " << num_buckets
 354                 << std::endl;
 355       DestroyDB(kDbName, Options());
 356       auto db = OpenDb();
 357       WriteOptions write_options;
 358       ReadOptions read_options;
 359
 360       // 1. Insert one row.
 361       Slice v16("v16");
 362       PutKey(db.get(), write_options, 1, 6, v16);
 363       std::unique_ptr<Iterator> iter(db->NewIterator(read_options));
 364       SeekIterator(iter.get(), 1, 6);
 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());
 370       SeekIterator(iter.get(), 1, 5);
 371       ASSERT_TRUE(iter->Valid());
 372       ASSERT_TRUE(v16 == iter->value());
 373       iter->Next();
 374       ASSERT_TRUE(!iter->Valid());
 375
 376       SeekIterator(iter.get(), 2, 0);
 377       ASSERT_TRUE(!iter->Valid());
 378
 379       ASSERT_EQ(v16.ToString(), Get(db.get(), read_options, 1, 6));
 380       ASSERT_EQ(kNotFoundResult, Get(db.get(), read_options, 1, 5));
 381       ASSERT_EQ(kNotFoundResult, Get(db.get(), read_options, 1, 7));
 382       ASSERT_EQ(kNotFoundResult, Get(db.get(), read_options, 0, 6));
 383       ASSERT_EQ(kNotFoundResult, Get(db.get(), read_options, 2, 6));
 384
 385       // 2. Insert an entry for the same prefix as the last entry in the bucket.
 386       Slice v17("v17");
 387       PutKey(db.get(), write_options, 1, 7, v17);
 388       iter.reset(db->NewIterator(read_options));
 389       SeekIterator(iter.get(), 1, 7);
 390       ASSERT_TRUE(iter->Valid());
 391       ASSERT_TRUE(v17 == iter->value());
 392
 393       SeekIterator(iter.get(), 1, 6);
 394       ASSERT_TRUE(iter->Valid());
 395       ASSERT_TRUE(v16 == iter->value());
 396       iter->Next();
 397       ASSERT_TRUE(iter->Valid());
 398       ASSERT_TRUE(v17 == iter->value());
 399       iter->Next();
 400       ASSERT_TRUE(!iter->Valid());
 401
 402       SeekIterator(iter.get(), 2, 0);
 403       ASSERT_TRUE(!iter->Valid());
 404
 405       // 3. Insert an entry for the same prefix as the head of the bucket.
 406       Slice v15("v15");
 407       PutKey(db.get(), write_options, 1, 5, v15);
 408       iter.reset(db->NewIterator(read_options));
 409
 410       SeekIterator(iter.get(), 1, 7);
 411       ASSERT_TRUE(iter->Valid());
 412       ASSERT_TRUE(v17 == iter->value());
 413
 414       SeekIterator(iter.get(), 1, 5);
 415       ASSERT_TRUE(iter->Valid());
 416       ASSERT_TRUE(v15 == iter->value());
 417       iter->Next();
 418       ASSERT_TRUE(iter->Valid());
 419       ASSERT_TRUE(v16 == iter->value());
 420       iter->Next();
 421       ASSERT_TRUE(iter->Valid());
 422       ASSERT_TRUE(v17 == iter->value());
 423
 424       SeekIterator(iter.get(), 1, 5);
 425       ASSERT_TRUE(iter->Valid());
 426       ASSERT_TRUE(v15 == iter->value());
 427
 428       ASSERT_EQ(v15.ToString(), Get(db.get(), read_options, 1, 5));
 429       ASSERT_EQ(v16.ToString(), Get(db.get(), read_options, 1, 6));
 430       ASSERT_EQ(v17.ToString(), Get(db.get(), read_options, 1, 7));
 431
 432       // 4. Insert an entry with a larger prefix
 433       Slice v22("v22");
 434       PutKey(db.get(), write_options, 2, 2, v22);
 435       iter.reset(db->NewIterator(read_options));
 436
 437       SeekIterator(iter.get(), 2, 2);
 438       ASSERT_TRUE(iter->Valid());
 439       ASSERT_TRUE(v22 == iter->value());
 440       SeekIterator(iter.get(), 2, 0);
 441       ASSERT_TRUE(iter->Valid());
 442       ASSERT_TRUE(v22 == iter->value());
 443
 444       SeekIterator(iter.get(), 1, 5);
 445       ASSERT_TRUE(iter->Valid());
 446       ASSERT_TRUE(v15 == iter->value());
 447
 448       SeekIterator(iter.get(), 1, 7);
 449       ASSERT_TRUE(iter->Valid());
 450       ASSERT_TRUE(v17 == iter->value());
 451
 452       // 5. Insert an entry with a smaller prefix
 453       Slice v02("v02");
 454       PutKey(db.get(), write_options, 0, 2, v02);
 455       iter.reset(db->NewIterator(read_options));
 456
 457       SeekIterator(iter.get(), 0, 2);
 458       ASSERT_TRUE(iter->Valid());
 459       ASSERT_TRUE(v02 == iter->value());
 460       SeekIterator(iter.get(), 0, 0);
 461       ASSERT_TRUE(iter->Valid());
 462       ASSERT_TRUE(v02 == iter->value());
 463
 464       SeekIterator(iter.get(), 2, 0);
 465       ASSERT_TRUE(iter->Valid());
 466       ASSERT_TRUE(v22 == iter->value());
 467
 468       SeekIterator(iter.get(), 1, 5);
 469       ASSERT_TRUE(iter->Valid());
 470       ASSERT_TRUE(v15 == iter->value());
 471
 472       SeekIterator(iter.get(), 1, 7);
 473       ASSERT_TRUE(iter->Valid());
 474       ASSERT_TRUE(v17 == iter->value());
 475
 476       // 6. Insert to the beginning and the end of the first prefix
 477       Slice v13("v13");
 478       Slice v18("v18");
 479       PutKey(db.get(), write_options, 1, 3, v13);
 480       PutKey(db.get(), write_options, 1, 8, v18);
 481       iter.reset(db->NewIterator(read_options));
 482       SeekIterator(iter.get(), 1, 7);
 483       ASSERT_TRUE(iter->Valid());
 484       ASSERT_TRUE(v17 == iter->value());
 485
 486       SeekIterator(iter.get(), 1, 3);
 487       ASSERT_TRUE(iter->Valid());
 488       ASSERT_TRUE(v13 == iter->value());
 489       iter->Next();
 490       ASSERT_TRUE(iter->Valid());
 491       ASSERT_TRUE(v15 == iter->value());
 492       iter->Next();
 493       ASSERT_TRUE(iter->Valid());
 494       ASSERT_TRUE(v16 == iter->value());
 495       iter->Next();
 496       ASSERT_TRUE(iter->Valid());
 497       ASSERT_TRUE(v17 == iter->value());
 498       iter->Next();
 499       ASSERT_TRUE(iter->Valid());
 500       ASSERT_TRUE(v18 == iter->value());
 501
 502       SeekIterator(iter.get(), 0, 0);
 503       ASSERT_TRUE(iter->Valid());
 504       ASSERT_TRUE(v02 == iter->value());
 505
 506       SeekIterator(iter.get(), 2, 0);
 507       ASSERT_TRUE(iter->Valid());
 508       ASSERT_TRUE(v22 == iter->value());
 509
 510       ASSERT_EQ(v22.ToString(), Get(db.get(), read_options, 2, 2));
 511       ASSERT_EQ(v02.ToString(), Get(db.get(), read_options, 0, 2));
 512       ASSERT_EQ(v13.ToString(), Get(db.get(), read_options, 1, 3));
 513       ASSERT_EQ(v15.ToString(), Get(db.get(), read_options, 1, 5));
 514       ASSERT_EQ(v16.ToString(), Get(db.get(), read_options, 1, 6));
 515       ASSERT_EQ(v17.ToString(), Get(db.get(), read_options, 1, 7));
 516       ASSERT_EQ(v18.ToString(), Get(db.get(), read_options, 1, 8));
 517     }
 518   }
 519 }
 520
 521 // Show results in prefix
 522 TEST_F(PrefixTest, PrefixValid) {
 523   for (int num_buckets = 1; num_buckets <= 2; num_buckets++) {
 524     FirstOption();
 525     while (NextOptions(num_buckets)) {
 526       std::cout << "*** Mem table: " << options.memtable_factory->Name()
 527                 << " number of buckets: " << num_buckets << std::endl;
 528       DestroyDB(kDbName, Options());
 529       auto db = OpenDb();
 530       WriteOptions write_options;
 531       ReadOptions read_options;
 532
 533       // Insert keys with common prefix and one key with different
 534       Slice v16("v16");
 535       Slice v17("v17");
 536       Slice v18("v18");
 537       Slice v19("v19");
 538       PutKey(db.get(), write_options, 12345, 6, v16);
 539       PutKey(db.get(), write_options, 12345, 7, v17);
 540       PutKey(db.get(), write_options, 12345, 8, v18);
 541       PutKey(db.get(), write_options, 12345, 9, v19);
 542       PutKey(db.get(), write_options, 12346, 8, v16);
 543       db->Flush(FlushOptions());
 544       TestKey test_key(12346, 8);
 545       std::string s;
 546       db->Delete(write_options, TestKeyToSlice(s, test_key));
 547       db->Flush(FlushOptions());
 548       read_options.prefix_same_as_start = true;
 549       std::unique_ptr<Iterator> iter(db->NewIterator(read_options));
 550       SeekIterator(iter.get(), 12345, 6);
 551       ASSERT_TRUE(iter->Valid());
 552       ASSERT_TRUE(v16 == iter->value());
 553
 554       iter->Next();
 555       ASSERT_TRUE(iter->Valid());
 556       ASSERT_TRUE(v17 == iter->value());
 557
 558       iter->Next();
 559       ASSERT_TRUE(iter->Valid());
 560       ASSERT_TRUE(v18 == iter->value());
 561
 562       iter->Next();
 563       ASSERT_TRUE(iter->Valid());
 564       ASSERT_TRUE(v19 == iter->value());
 565       iter->Next();
 566       ASSERT_FALSE(iter->Valid());
 567       ASSERT_EQ(kNotFoundResult, Get(db.get(), read_options, 12346, 8));
 568
 569       // Verify seeking past the prefix won't return a result.
 570       SeekIterator(iter.get(), 12345, 10);
 571       ASSERT_TRUE(!iter->Valid());
 572     }
 573   }
 574 }
 575
 576 TEST_F(PrefixTest, DynamicPrefixIterator) {
 577   while (NextOptions(FLAGS_bucket_count)) {
 578     std::cout << "*** Mem table: " << options.memtable_factory->Name()
 579         << std::endl;
 580     DestroyDB(kDbName, Options());
 581     auto db = OpenDb();
 582     WriteOptions write_options;
 583     ReadOptions read_options;
 584
 585     std::vector<uint64_t> prefixes;
 586     for (uint64_t i = 0; i < FLAGS_total_prefixes; ++i) {
 587       prefixes.push_back(i);
 588     }
 589
 590     if (FLAGS_random_prefix) {
 591       std::random_shuffle(prefixes.begin(), prefixes.end());
 592     }
 593
 594     HistogramImpl hist_put_time;
 595     HistogramImpl hist_put_comparison;
 596
 597     // insert x random prefix, each with y continuous element.
 598     for (auto prefix : prefixes) {
 599        for (uint64_t sorted = 0; sorted < FLAGS_items_per_prefix; sorted++) {
 600         TestKey test_key(prefix, sorted);
 601
 602         std::string s;
 603         Slice key = TestKeyToSlice(s, test_key);
 604         std::string value(FLAGS_value_size, 0);
 605
 606         perf_context.Reset();
 607         StopWatchNano timer(Env::Default(), true);
 608         ASSERT_OK(db->Put(write_options, key, value));
 609         hist_put_time.Add(timer.ElapsedNanos());
 610         hist_put_comparison.Add(perf_context.user_key_comparison_count);
 611       }
 612     }
 613
 614     std::cout << "Put key comparison: \n" << hist_put_comparison.ToString()
 615               << "Put time: \n" << hist_put_time.ToString();
 616
 617     // test seek existing keys
 618     HistogramImpl hist_seek_time;
 619     HistogramImpl hist_seek_comparison;
 620
 621     std::unique_ptr<Iterator> iter(db->NewIterator(read_options));
 622
 623     for (auto prefix : prefixes) {
 624       TestKey test_key(prefix, FLAGS_items_per_prefix / 2);
 625       std::string s;
 626       Slice key = TestKeyToSlice(s, test_key);
 627       std::string value = "v" + ToString(0);
 628
 629       perf_context.Reset();
 630       StopWatchNano timer(Env::Default(), true);
 631       auto key_prefix = options.prefix_extractor->Transform(key);
 632       uint64_t total_keys = 0;
 633       for (iter->Seek(key);
 634            iter->Valid() && iter->key().starts_with(key_prefix);
 635            iter->Next()) {
 636         if (FLAGS_trigger_deadlock) {
 637           std::cout << "Behold the deadlock!\n";
 638           db->Delete(write_options, iter->key());
 639         }
 640         total_keys++;
 641       }
 642       hist_seek_time.Add(timer.ElapsedNanos());
 643       hist_seek_comparison.Add(perf_context.user_key_comparison_count);
 644       ASSERT_EQ(total_keys, FLAGS_items_per_prefix - FLAGS_items_per_prefix/2);
 645     }
 646
 647     std::cout << "Seek key comparison: \n"
 648               << hist_seek_comparison.ToString()
 649               << "Seek time: \n"
 650               << hist_seek_time.ToString();
 651
 652     // test non-existing keys
 653     HistogramImpl hist_no_seek_time;
 654     HistogramImpl hist_no_seek_comparison;
 655
 656     for (auto prefix = FLAGS_total_prefixes;
 657          prefix < FLAGS_total_prefixes + 10000;
 658          prefix++) {
 659       TestKey test_key(prefix, 0);
 660       std::string s;
 661       Slice key = TestKeyToSlice(s, test_key);
 662
 663       perf_context.Reset();
 664       StopWatchNano timer(Env::Default(), true);
 665       iter->Seek(key);
 666       hist_no_seek_time.Add(timer.ElapsedNanos());
 667       hist_no_seek_comparison.Add(perf_context.user_key_comparison_count);
 668       ASSERT_TRUE(!iter->Valid());
 669     }
 670
 671     std::cout << "non-existing Seek key comparison: \n"
 672               << hist_no_seek_comparison.ToString()
 673               << "non-existing Seek time: \n"
 674               << hist_no_seek_time.ToString();
 675   }
 676 }
 677
 678 TEST_F(PrefixTest, PrefixSeekModePrev) {
 679   // Only for SkipListFactory
 680   options.memtable_factory.reset(new SkipListFactory);
 681   options.merge_operator = MergeOperators::CreatePutOperator();
 682   options.write_buffer_size = 1024 * 1024;
 683   Random rnd(1);
 684   for (size_t m = 1; m < 100; m++) {
 685     std::cout << "[" + std::to_string(m) + "]" + "*** Mem table: "
 686               << options.memtable_factory->Name() << std::endl;
 687     DestroyDB(kDbName, Options());
 688     auto db = OpenDb();
 689     WriteOptions write_options;
 690     ReadOptions read_options;
 691     std::map<TestKey, std::string, TestKeyComparator> entry_maps[3], whole_map;
 692     for (uint64_t i = 0; i < 10; i++) {
 693       int div = i % 3 + 1;
 694       for (uint64_t j = 0; j < 10; j++) {
 695         whole_map[TestKey(i, j)] = entry_maps[rnd.Uniform(div)][TestKey(i, j)] =
 696             'v' + std::to_string(i) + std::to_string(j);
 697       }
 698     }
 699
 700     std::map<TestKey, std::string, TestKeyComparator> type_map;
 701     for (size_t i = 0; i < 3; i++) {
 702       for (auto& kv : entry_maps[i]) {
 703         if (rnd.OneIn(3)) {
 704           PutKey(db.get(), write_options, kv.first, kv.second);
 705           type_map[kv.first] = "value";
 706         } else {
 707           MergeKey(db.get(), write_options, kv.first, kv.second);
 708           type_map[kv.first] = "merge";
 709         }
 710       }
 711       if (i < 2) {
 712         db->Flush(FlushOptions());
 713       }
 714     }
 715
 716     for (size_t i = 0; i < 2; i++) {
 717       for (auto& kv : entry_maps[i]) {
 718         if (rnd.OneIn(10)) {
 719           whole_map.erase(kv.first);
 720           DeleteKey(db.get(), write_options, kv.first);
 721           entry_maps[2][kv.first] = "delete";
 722         }
 723       }
 724     }
 725
 726     if (FLAGS_enable_print) {
 727       for (size_t i = 0; i < 3; i++) {
 728         for (auto& kv : entry_maps[i]) {
 729           std::cout << "[" << i << "]" << kv.first.prefix << kv.first.sorted
 730                     << " " << kv.second + " " + type_map[kv.first] << std::endl;
 731         }
 732       }
 733     }
 734
 735     std::unique_ptr<Iterator> iter(db->NewIterator(read_options));
 736     for (uint64_t prefix = 0; prefix < 10; prefix++) {
 737       uint64_t start_suffix = rnd.Uniform(9);
 738       SeekIterator(iter.get(), prefix, start_suffix);
 739       auto it = whole_map.find(TestKey(prefix, start_suffix));
 740       if (it == whole_map.end()) {
 741         continue;
 742       }
 743       ASSERT_NE(it, whole_map.end());
 744       ASSERT_TRUE(iter->Valid());
 745       if (FLAGS_enable_print) {
 746         std::cout << "round " << prefix
 747                   << " iter: " << SliceToTestKey(iter->key()).prefix
 748                   << SliceToTestKey(iter->key()).sorted
 749                   << " | map: " << it->first.prefix << it->first.sorted << " | "
 750                   << iter->value().ToString() << " " << it->second << std::endl;
 751       }
 752       ASSERT_EQ(iter->value(), it->second);
 753       uint64_t stored_prefix = prefix;
 754       for (size_t k = 0; k < 9; k++) {
 755         if (rnd.OneIn(2) || it == whole_map.begin()) {
 756           iter->Next();
 757           it++;
 758           if (FLAGS_enable_print) {
 759             std::cout << "Next >> ";
 760           }
 761         } else {
 762           iter->Prev();
 763           it--;
 764           if (FLAGS_enable_print) {
 765             std::cout << "Prev >> ";
 766           }
 767         }
 768         if (!iter->Valid() ||
 769             SliceToTestKey(iter->key()).prefix != stored_prefix) {
 770           break;
 771         }
 772         stored_prefix = SliceToTestKey(iter->key()).prefix;
 773         ASSERT_TRUE(iter->Valid());
 774         ASSERT_NE(it, whole_map.end());
 775         ASSERT_EQ(iter->value(), it->second);
 776         if (FLAGS_enable_print) {
 777           std::cout << "iter: " << SliceToTestKey(iter->key()).prefix
 778                     << SliceToTestKey(iter->key()).sorted
 779                     << " | map: " << it->first.prefix << it->first.sorted
 780                     << " | " << iter->value().ToString() << " " << it->second
 781                     << std::endl;
 782         }
 783       }
 784     }
 785   }
 786 }
 787
 788 TEST_F(PrefixTest, PrefixSeekModePrev2) {
 789   // Only for SkipListFactory
 790   // test the case
 791   //        iter1                iter2
 792   // | prefix | suffix |  | prefix | suffix |
 793   // |   1    |   1    |  |   1    |   2    |
 794   // |   1    |   3    |  |   1    |   4    |
 795   // |   2    |   1    |  |   3    |   3    |
 796   // |   2    |   2    |  |   3    |   4    |
 797   // after seek(15), iter1 will be at 21 and iter2 will be 33.
 798   // Then if call Prev() in prefix mode where SeekForPrev(21) gets called,
 799   // iter2 should turn to invalid state because of bloom filter.
 800   options.memtable_factory.reset(new SkipListFactory);
 801   options.write_buffer_size = 1024 * 1024;
 802   std::string v13("v13");
 803   DestroyDB(kDbName, Options());
 804   auto db = OpenDb();
 805   WriteOptions write_options;
 806   ReadOptions read_options;
 807   PutKey(db.get(), write_options, TestKey(1, 2), "v12");
 808   PutKey(db.get(), write_options, TestKey(1, 4), "v14");
 809   PutKey(db.get(), write_options, TestKey(3, 3), "v33");
 810   PutKey(db.get(), write_options, TestKey(3, 4), "v34");
 811   db->Flush(FlushOptions());
 812   reinterpret_cast<DBImpl*>(db.get())->TEST_WaitForFlushMemTable();
 813   PutKey(db.get(), write_options, TestKey(1, 1), "v11");
 814   PutKey(db.get(), write_options, TestKey(1, 3), "v13");
 815   PutKey(db.get(), write_options, TestKey(2, 1), "v21");
 816   PutKey(db.get(), write_options, TestKey(2, 2), "v22");
 817   db->Flush(FlushOptions());
 818   reinterpret_cast<DBImpl*>(db.get())->TEST_WaitForFlushMemTable();
 819   std::unique_ptr<Iterator> iter(db->NewIterator(read_options));
 820   SeekIterator(iter.get(), 1, 5);
 821   iter->Prev();
 822   ASSERT_EQ(iter->value(), v13);
 823 }
 824
 825 TEST_F(PrefixTest, PrefixSeekModePrev3) {
 826   // Only for SkipListFactory
 827   // test SeekToLast() with iterate_upper_bound_ in prefix_seek_mode
 828   options.memtable_factory.reset(new SkipListFactory);
 829   options.write_buffer_size = 1024 * 1024;
 830   std::string v14("v14");
 831   TestKey upper_bound_key = TestKey(1, 5);
 832   std::string s;
 833   Slice upper_bound = TestKeyToSlice(s, upper_bound_key);
 834
 835   {
 836     DestroyDB(kDbName, Options());
 837     auto db = OpenDb();
 838     WriteOptions write_options;
 839     ReadOptions read_options;
 840     read_options.iterate_upper_bound = &upper_bound;
 841     PutKey(db.get(), write_options, TestKey(1, 2), "v12");
 842     PutKey(db.get(), write_options, TestKey(1, 4), "v14");
 843     db->Flush(FlushOptions());
 844     reinterpret_cast<DBImpl*>(db.get())->TEST_WaitForFlushMemTable();
 845     PutKey(db.get(), write_options, TestKey(1, 1), "v11");
 846     PutKey(db.get(), write_options, TestKey(1, 3), "v13");
 847     PutKey(db.get(), write_options, TestKey(2, 1), "v21");
 848     PutKey(db.get(), write_options, TestKey(2, 2), "v22");
 849     db->Flush(FlushOptions());
 850     reinterpret_cast<DBImpl*>(db.get())->TEST_WaitForFlushMemTable();
 851     std::unique_ptr<Iterator> iter(db->NewIterator(read_options));
 852     iter->SeekToLast();
 853     ASSERT_EQ(iter->value(), v14);
 854   }
 855   {
 856     DestroyDB(kDbName, Options());
 857     auto db = OpenDb();
 858     WriteOptions write_options;
 859     ReadOptions read_options;
 860     read_options.iterate_upper_bound = &upper_bound;
 861     PutKey(db.get(), write_options, TestKey(1, 2), "v12");
 862     PutKey(db.get(), write_options, TestKey(1, 4), "v14");
 863     PutKey(db.get(), write_options, TestKey(3, 3), "v33");
 864     PutKey(db.get(), write_options, TestKey(3, 4), "v34");
 865     db->Flush(FlushOptions());
 866     reinterpret_cast<DBImpl*>(db.get())->TEST_WaitForFlushMemTable();
 867     PutKey(db.get(), write_options, TestKey(1, 1), "v11");
 868     PutKey(db.get(), write_options, TestKey(1, 3), "v13");
 869     db->Flush(FlushOptions());
 870     reinterpret_cast<DBImpl*>(db.get())->TEST_WaitForFlushMemTable();
 871     std::unique_ptr<Iterator> iter(db->NewIterator(read_options));
 872     iter->SeekToLast();
 873     ASSERT_EQ(iter->value(), v14);
 874   }
 875 }
 876
 877 }  // end namespace rocksdb
 878
 879 int main(int argc, char** argv) {
 880   ::testing::InitGoogleTest(&argc, argv);
 881   ParseCommandLineFlags(&argc, &argv, true);
 882   std::cout << kDbName << "\n";
 883
 884   return RUN_ALL_TESTS();
 885 }
 886
 887 #endif  // GFLAGS
 888
 889 #else
 890 #include <stdio.h>
 891
 892 int main(int argc, char** argv) {
 893   fprintf(stderr,
 894           "SKIPPED as HashSkipList and HashLinkList are not supported in "
 895           "ROCKSDB_LITE\n");
 896   return 0;
 897 }
 898
 899 #endif  // !ROCKSDB_LITE