ceph/src/rocksdb/db/plain_table_db_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 // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
   7 // Use of this source code is governed by a BSD-style license that can be
   8 // found in the LICENSE file. See the AUTHORS file for names of contributors.
   9
  10 #ifndef ROCKSDB_LITE
  11
  12 #include <algorithm>
  13 #include <set>
  14
  15 #include "db/db_impl/db_impl.h"
  16 #include "db/version_set.h"
  17 #include "db/write_batch_internal.h"
  18 #include "file/filename.h"
  19 #include "rocksdb/cache.h"
  20 #include "rocksdb/compaction_filter.h"
  21 #include "rocksdb/db.h"
  22 #include "rocksdb/env.h"
  23 #include "rocksdb/filter_policy.h"
  24 #include "rocksdb/slice_transform.h"
  25 #include "rocksdb/table.h"
  26 #include "table/meta_blocks.h"
  27 #include "table/plain/plain_table_bloom.h"
  28 #include "table/plain/plain_table_factory.h"
  29 #include "table/plain/plain_table_key_coding.h"
  30 #include "table/plain/plain_table_reader.h"
  31 #include "table/table_builder.h"
  32 #include "test_util/testharness.h"
  33 #include "test_util/testutil.h"
  34 #include "util/cast_util.h"
  35 #include "util/hash.h"
  36 #include "util/mutexlock.h"
  37 #include "util/random.h"
  38 #include "util/string_util.h"
  39 #include "utilities/merge_operators.h"
  40
  41 namespace ROCKSDB_NAMESPACE {
  42 class PlainTableKeyDecoderTest : public testing::Test {};
  43
  44 TEST_F(PlainTableKeyDecoderTest, ReadNonMmap) {
  45   Random rnd(301);
  46   const uint32_t kLength = 2222;
  47   std::string tmp = rnd.RandomString(kLength);
  48   Slice contents(tmp);
  49   test::StringSource* string_source =
  50       new test::StringSource(contents, 0, false);
  51   std::unique_ptr<FSRandomAccessFile> holder(string_source);
  52   std::unique_ptr<RandomAccessFileReader> file_reader(
  53       new RandomAccessFileReader(std::move(holder), "test"));
  54   std::unique_ptr<PlainTableReaderFileInfo> file_info(
  55       new PlainTableReaderFileInfo(std::move(file_reader), EnvOptions(),
  56                                    kLength));
  57
  58   {
  59     PlainTableFileReader reader(file_info.get());
  60
  61     const uint32_t kReadSize = 77;
  62     for (uint32_t pos = 0; pos < kLength; pos += kReadSize) {
  63       uint32_t read_size = std::min(kLength - pos, kReadSize);
  64       Slice out;
  65       ASSERT_TRUE(reader.Read(pos, read_size, &out));
  66       ASSERT_EQ(0, out.compare(tmp.substr(pos, read_size)));
  67     }
  68
  69     ASSERT_LT(uint32_t(string_source->total_reads()), kLength / kReadSize / 2);
  70   }
  71
  72   std::vector<std::vector<std::pair<uint32_t, uint32_t>>> reads = {
  73       {{600, 30}, {590, 30}, {600, 20}, {600, 40}},
  74       {{800, 20}, {100, 20}, {500, 20}, {1500, 20}, {100, 20}, {80, 20}},
  75       {{1000, 20}, {500, 20}, {1000, 50}},
  76       {{1000, 20}, {500, 20}, {500, 20}},
  77       {{1000, 20}, {500, 20}, {200, 20}, {500, 20}},
  78       {{1000, 20}, {500, 20}, {200, 20}, {1000, 50}},
  79       {{600, 500}, {610, 20}, {100, 20}},
  80       {{500, 100}, {490, 100}, {550, 50}},
  81   };
  82
  83   std::vector<int> num_file_reads = {2, 6, 2, 2, 4, 3, 2, 2};
  84
  85   for (size_t i = 0; i < reads.size(); i++) {
  86     string_source->set_total_reads(0);
  87     PlainTableFileReader reader(file_info.get());
  88     for (auto p : reads[i]) {
  89       Slice out;
  90       ASSERT_TRUE(reader.Read(p.first, p.second, &out));
  91       ASSERT_EQ(0, out.compare(tmp.substr(p.first, p.second)));
  92     }
  93     ASSERT_EQ(num_file_reads[i], string_source->total_reads());
  94   }
  95 }
  96
  97 class PlainTableDBTest : public testing::Test,
  98                          public testing::WithParamInterface<bool> {
  99  protected:
 100  private:
 101   std::string dbname_;
 102   Env* env_;
 103   DB* db_;
 104
 105   bool mmap_mode_;
 106   Options last_options_;
 107
 108  public:
 109   PlainTableDBTest() : env_(Env::Default()) {}
 110
 111   ~PlainTableDBTest() override {
 112     delete db_;
 113     EXPECT_OK(DestroyDB(dbname_, Options()));
 114   }
 115
 116   void SetUp() override {
 117     mmap_mode_ = GetParam();
 118     dbname_ = test::PerThreadDBPath("plain_table_db_test");
 119     EXPECT_OK(DestroyDB(dbname_, Options()));
 120     db_ = nullptr;
 121     Reopen();
 122   }
 123
 124   // Return the current option configuration.
 125   Options CurrentOptions() {
 126     Options options;
 127
 128     PlainTableOptions plain_table_options;
 129     plain_table_options.user_key_len = 0;
 130     plain_table_options.bloom_bits_per_key = 2;
 131     plain_table_options.hash_table_ratio = 0.8;
 132     plain_table_options.index_sparseness = 3;
 133     plain_table_options.huge_page_tlb_size = 0;
 134     plain_table_options.encoding_type = kPrefix;
 135     plain_table_options.full_scan_mode = false;
 136     plain_table_options.store_index_in_file = false;
 137
 138     options.table_factory.reset(NewPlainTableFactory(plain_table_options));
 139     options.memtable_factory.reset(NewHashLinkListRepFactory(4, 0, 3, true));
 140
 141     options.prefix_extractor.reset(NewFixedPrefixTransform(8));
 142     options.allow_mmap_reads = mmap_mode_;
 143     options.allow_concurrent_memtable_write = false;
 144     options.unordered_write = false;
 145     return options;
 146   }
 147
 148   DBImpl* dbfull() { return static_cast_with_check<DBImpl>(db_); }
 149
 150   void Reopen(Options* options = nullptr) { ASSERT_OK(TryReopen(options)); }
 151
 152   void Close() {
 153     delete db_;
 154     db_ = nullptr;
 155   }
 156
 157   bool mmap_mode() const { return mmap_mode_; }
 158
 159   void DestroyAndReopen(Options* options = nullptr) {
 160     // Destroy using last options
 161     Destroy(&last_options_);
 162     ASSERT_OK(TryReopen(options));
 163   }
 164
 165   void Destroy(Options* options) {
 166     delete db_;
 167     db_ = nullptr;
 168     ASSERT_OK(DestroyDB(dbname_, *options));
 169   }
 170
 171   Status PureReopen(Options* options, DB** db) {
 172     return DB::Open(*options, dbname_, db);
 173   }
 174
 175   Status ReopenForReadOnly(Options* options) {
 176     delete db_;
 177     db_ = nullptr;
 178     return DB::OpenForReadOnly(*options, dbname_, &db_);
 179   }
 180
 181   Status TryReopen(Options* options = nullptr) {
 182     delete db_;
 183     db_ = nullptr;
 184     Options opts;
 185     if (options != nullptr) {
 186       opts = *options;
 187     } else {
 188       opts = CurrentOptions();
 189       opts.create_if_missing = true;
 190     }
 191     last_options_ = opts;
 192
 193     return DB::Open(opts, dbname_, &db_);
 194   }
 195
 196   Status Put(const Slice& k, const Slice& v) {
 197     return db_->Put(WriteOptions(), k, v);
 198   }
 199
 200   Status Delete(const std::string& k) { return db_->Delete(WriteOptions(), k); }
 201
 202   std::string Get(const std::string& k, const Snapshot* snapshot = nullptr) {
 203     ReadOptions options;
 204     options.snapshot = snapshot;
 205     std::string result;
 206     Status s = db_->Get(options, k, &result);
 207     if (s.IsNotFound()) {
 208       result = "NOT_FOUND";
 209     } else if (!s.ok()) {
 210       result = s.ToString();
 211     }
 212     return result;
 213   }
 214
 215   int NumTableFilesAtLevel(int level) {
 216     std::string property;
 217     EXPECT_TRUE(db_->GetProperty(
 218         "rocksdb.num-files-at-level" + std::to_string(level), &property));
 219     return atoi(property.c_str());
 220   }
 221
 222   // Return spread of files per level
 223   std::string FilesPerLevel() {
 224     std::string result;
 225     size_t last_non_zero_offset = 0;
 226     for (int level = 0; level < db_->NumberLevels(); level++) {
 227       int f = NumTableFilesAtLevel(level);
 228       char buf[100];
 229       snprintf(buf, sizeof(buf), "%s%d", (level ? "," : ""), f);
 230       result += buf;
 231       if (f > 0) {
 232         last_non_zero_offset = result.size();
 233       }
 234     }
 235     result.resize(last_non_zero_offset);
 236     return result;
 237   }
 238
 239   std::string IterStatus(Iterator* iter) {
 240     std::string result;
 241     if (iter->Valid()) {
 242       result = iter->key().ToString() + "->" + iter->value().ToString();
 243     } else {
 244       result = "(invalid)";
 245     }
 246     return result;
 247   }
 248 };
 249
 250 TEST_P(PlainTableDBTest, Empty) {
 251   ASSERT_TRUE(dbfull() != nullptr);
 252   ASSERT_EQ("NOT_FOUND", Get("0000000000000foo"));
 253 }
 254
 255 extern const uint64_t kPlainTableMagicNumber;
 256
 257 class TestPlainTableReader : public PlainTableReader {
 258  public:
 259   TestPlainTableReader(
 260       const EnvOptions& env_options, const InternalKeyComparator& icomparator,
 261       EncodingType encoding_type, uint64_t file_size, int bloom_bits_per_key,
 262       double hash_table_ratio, size_t index_sparseness,
 263       std::unique_ptr<TableProperties>&& props,
 264       std::unique_ptr<RandomAccessFileReader>&& file,
 265       const ImmutableOptions& ioptions, const SliceTransform* prefix_extractor,
 266       bool* expect_bloom_not_match, bool store_index_in_file,
 267       uint32_t column_family_id, const std::string& column_family_name)
 268       : PlainTableReader(ioptions, std::move(file), env_options, icomparator,
 269                          encoding_type, file_size, props.get(),
 270                          prefix_extractor),
 271         expect_bloom_not_match_(expect_bloom_not_match) {
 272     Status s = MmapDataIfNeeded();
 273     EXPECT_TRUE(s.ok());
 274
 275     s = PopulateIndex(props.get(), bloom_bits_per_key, hash_table_ratio,
 276                       index_sparseness, 2 * 1024 * 1024);
 277     EXPECT_TRUE(s.ok());
 278
 279     EXPECT_EQ(column_family_id, static_cast<uint32_t>(props->column_family_id));
 280     EXPECT_EQ(column_family_name, props->column_family_name);
 281     if (store_index_in_file) {
 282       auto bloom_version_ptr = props->user_collected_properties.find(
 283           PlainTablePropertyNames::kBloomVersion);
 284       EXPECT_TRUE(bloom_version_ptr != props->user_collected_properties.end());
 285       EXPECT_EQ(bloom_version_ptr->second, std::string("1"));
 286       if (ioptions.bloom_locality > 0) {
 287         auto num_blocks_ptr = props->user_collected_properties.find(
 288             PlainTablePropertyNames::kNumBloomBlocks);
 289         EXPECT_TRUE(num_blocks_ptr != props->user_collected_properties.end());
 290       }
 291     }
 292     table_properties_ = std::move(props);
 293   }
 294
 295   ~TestPlainTableReader() override {}
 296
 297  private:
 298   bool MatchBloom(uint32_t hash) const override {
 299     bool ret = PlainTableReader::MatchBloom(hash);
 300     if (*expect_bloom_not_match_) {
 301       EXPECT_TRUE(!ret);
 302     } else {
 303       EXPECT_TRUE(ret);
 304     }
 305     return ret;
 306   }
 307   bool* expect_bloom_not_match_;
 308 };
 309
 310 extern const uint64_t kPlainTableMagicNumber;
 311 class TestPlainTableFactory : public PlainTableFactory {
 312  public:
 313   explicit TestPlainTableFactory(bool* expect_bloom_not_match,
 314                                  const PlainTableOptions& options,
 315                                  uint32_t column_family_id,
 316                                  std::string column_family_name)
 317       : PlainTableFactory(options),
 318         bloom_bits_per_key_(options.bloom_bits_per_key),
 319         hash_table_ratio_(options.hash_table_ratio),
 320         index_sparseness_(options.index_sparseness),
 321         store_index_in_file_(options.store_index_in_file),
 322         expect_bloom_not_match_(expect_bloom_not_match),
 323         column_family_id_(column_family_id),
 324         column_family_name_(std::move(column_family_name)) {}
 325
 326   using PlainTableFactory::NewTableReader;
 327   Status NewTableReader(
 328       const ReadOptions& /*ro*/, const TableReaderOptions& table_reader_options,
 329       std::unique_ptr<RandomAccessFileReader>&& file, uint64_t file_size,
 330       std::unique_ptr<TableReader>* table,
 331       bool /*prefetch_index_and_filter_in_cache*/) const override {
 332     std::unique_ptr<TableProperties> props;
 333     auto s = ReadTableProperties(file.get(), file_size, kPlainTableMagicNumber,
 334                                  table_reader_options.ioptions, &props);
 335     EXPECT_TRUE(s.ok());
 336
 337     if (store_index_in_file_) {
 338       BlockHandle bloom_block_handle;
 339       s = FindMetaBlockInFile(file.get(), file_size, kPlainTableMagicNumber,
 340                               table_reader_options.ioptions,
 341                               BloomBlockBuilder::kBloomBlock,
 342                               &bloom_block_handle);
 343       EXPECT_TRUE(s.ok());
 344
 345       BlockHandle index_block_handle;
 346       s = FindMetaBlockInFile(file.get(), file_size, kPlainTableMagicNumber,
 347                               table_reader_options.ioptions,
 348                               PlainTableIndexBuilder::kPlainTableIndexBlock,
 349                               &index_block_handle);
 350       EXPECT_TRUE(s.ok());
 351     }
 352
 353     auto& user_props = props->user_collected_properties;
 354     auto encoding_type_prop =
 355         user_props.find(PlainTablePropertyNames::kEncodingType);
 356     assert(encoding_type_prop != user_props.end());
 357     EncodingType encoding_type = static_cast<EncodingType>(
 358         DecodeFixed32(encoding_type_prop->second.c_str()));
 359
 360     std::unique_ptr<PlainTableReader> new_reader(new TestPlainTableReader(
 361         table_reader_options.env_options,
 362         table_reader_options.internal_comparator, encoding_type, file_size,
 363         bloom_bits_per_key_, hash_table_ratio_, index_sparseness_,
 364         std::move(props), std::move(file), table_reader_options.ioptions,
 365         table_reader_options.prefix_extractor.get(), expect_bloom_not_match_,
 366         store_index_in_file_, column_family_id_, column_family_name_));
 367
 368     *table = std::move(new_reader);
 369     return s;
 370   }
 371
 372  private:
 373   int bloom_bits_per_key_;
 374   double hash_table_ratio_;
 375   size_t index_sparseness_;
 376   bool store_index_in_file_;
 377   bool* expect_bloom_not_match_;
 378   const uint32_t column_family_id_;
 379   const std::string column_family_name_;
 380 };
 381
 382 TEST_P(PlainTableDBTest, BadOptions1) {
 383   // Build with a prefix extractor
 384   ASSERT_OK(Put("1000000000000foo", "v1"));
 385   ASSERT_OK(dbfull()->TEST_FlushMemTable());
 386
 387   // Bad attempt to re-open without a prefix extractor
 388   Options options = CurrentOptions();
 389   options.prefix_extractor.reset();
 390   ASSERT_EQ(
 391       "Invalid argument: Prefix extractor is missing when opening a PlainTable "
 392       "built using a prefix extractor",
 393       TryReopen(&options).ToString());
 394
 395   // Bad attempt to re-open with different prefix extractor
 396   options.prefix_extractor.reset(NewFixedPrefixTransform(6));
 397   ASSERT_EQ(
 398       "Invalid argument: Prefix extractor given doesn't match the one used to "
 399       "build PlainTable",
 400       TryReopen(&options).ToString());
 401
 402   // Correct prefix extractor
 403   options.prefix_extractor.reset(NewFixedPrefixTransform(8));
 404   Reopen(&options);
 405   ASSERT_EQ("v1", Get("1000000000000foo"));
 406 }
 407
 408 TEST_P(PlainTableDBTest, BadOptions2) {
 409   Options options = CurrentOptions();
 410   options.prefix_extractor.reset();
 411   options.create_if_missing = true;
 412   DestroyAndReopen(&options);
 413   // Build without a prefix extractor
 414   // (apparently works even if hash_table_ratio > 0)
 415   ASSERT_OK(Put("1000000000000foo", "v1"));
 416   // Build without a prefix extractor, this call will fail and returns the
 417   // status for this bad attempt.
 418   ASSERT_NOK(dbfull()->TEST_FlushMemTable());
 419
 420   // Bad attempt to re-open with hash_table_ratio > 0 and no prefix extractor
 421   Status s = TryReopen(&options);
 422   ASSERT_EQ(
 423       "Not implemented: PlainTable requires a prefix extractor enable prefix "
 424       "hash mode.",
 425       s.ToString());
 426
 427   // OK to open with hash_table_ratio == 0 and no prefix extractor
 428   PlainTableOptions plain_table_options;
 429   plain_table_options.hash_table_ratio = 0;
 430   options.table_factory.reset(NewPlainTableFactory(plain_table_options));
 431   Reopen(&options);
 432   ASSERT_EQ("v1", Get("1000000000000foo"));
 433
 434   // OK to open newly with a prefix_extractor and hash table; builds index
 435   // in memory.
 436   options = CurrentOptions();
 437   Reopen(&options);
 438   ASSERT_EQ("v1", Get("1000000000000foo"));
 439 }
 440
 441 TEST_P(PlainTableDBTest, Flush) {
 442   for (size_t huge_page_tlb_size = 0; huge_page_tlb_size <= 2 * 1024 * 1024;
 443        huge_page_tlb_size += 2 * 1024 * 1024) {
 444     for (EncodingType encoding_type : {kPlain, kPrefix}) {
 445       for (int bloom = -1; bloom <= 117; bloom += 117) {
 446         const int bloom_bits = std::max(bloom, 0);
 447         const bool full_scan_mode = bloom < 0;
 448         for (int total_order = 0; total_order <= 1; total_order++) {
 449           for (int store_index_in_file = 0; store_index_in_file <= 1;
 450                ++store_index_in_file) {
 451             Options options = CurrentOptions();
 452             options.create_if_missing = true;
 453             // Set only one bucket to force bucket conflict.
 454             // Test index interval for the same prefix to be 1, 2 and 4
 455             if (total_order) {
 456               options.prefix_extractor.reset();
 457
 458               PlainTableOptions plain_table_options;
 459               plain_table_options.user_key_len = 0;
 460               plain_table_options.bloom_bits_per_key = bloom_bits;
 461               plain_table_options.hash_table_ratio = 0;
 462               plain_table_options.index_sparseness = 2;
 463               plain_table_options.huge_page_tlb_size = huge_page_tlb_size;
 464               plain_table_options.encoding_type = encoding_type;
 465               plain_table_options.full_scan_mode = full_scan_mode;
 466               plain_table_options.store_index_in_file = store_index_in_file;
 467
 468               options.table_factory.reset(
 469                   NewPlainTableFactory(plain_table_options));
 470             } else {
 471               PlainTableOptions plain_table_options;
 472               plain_table_options.user_key_len = 0;
 473               plain_table_options.bloom_bits_per_key = bloom_bits;
 474               plain_table_options.hash_table_ratio = 0.75;
 475               plain_table_options.index_sparseness = 16;
 476               plain_table_options.huge_page_tlb_size = huge_page_tlb_size;
 477               plain_table_options.encoding_type = encoding_type;
 478               plain_table_options.full_scan_mode = full_scan_mode;
 479               plain_table_options.store_index_in_file = store_index_in_file;
 480
 481               options.table_factory.reset(
 482                   NewPlainTableFactory(plain_table_options));
 483             }
 484             DestroyAndReopen(&options);
 485             uint64_t int_num;
 486             ASSERT_TRUE(dbfull()->GetIntProperty(
 487                 "rocksdb.estimate-table-readers-mem", &int_num));
 488             ASSERT_EQ(int_num, 0U);
 489
 490             ASSERT_OK(Put("1000000000000foo", "v1"));
 491             ASSERT_OK(Put("0000000000000bar", "v2"));
 492             ASSERT_OK(Put("1000000000000foo", "v3"));
 493             ASSERT_OK(dbfull()->TEST_FlushMemTable());
 494
 495             ASSERT_TRUE(dbfull()->GetIntProperty(
 496                 "rocksdb.estimate-table-readers-mem", &int_num));
 497             ASSERT_GT(int_num, 0U);
 498
 499             TablePropertiesCollection ptc;
 500             ASSERT_OK(reinterpret_cast<DB*>(dbfull())->GetPropertiesOfAllTables(
 501                 &ptc));
 502             ASSERT_EQ(1U, ptc.size());
 503             auto row = ptc.begin();
 504             auto tp = row->second;
 505
 506             if (full_scan_mode) {
 507               // Does not support Get/Seek
 508               std::unique_ptr<Iterator> iter(
 509                   dbfull()->NewIterator(ReadOptions()));
 510               iter->SeekToFirst();
 511               ASSERT_TRUE(iter->Valid());
 512               ASSERT_EQ("0000000000000bar", iter->key().ToString());
 513               ASSERT_EQ("v2", iter->value().ToString());
 514               iter->Next();
 515               ASSERT_TRUE(iter->Valid());
 516               ASSERT_EQ("1000000000000foo", iter->key().ToString());
 517               ASSERT_EQ("v3", iter->value().ToString());
 518               iter->Next();
 519               ASSERT_TRUE(!iter->Valid());
 520               ASSERT_TRUE(iter->status().ok());
 521             } else {
 522               if (!store_index_in_file) {
 523                 ASSERT_EQ(total_order ? "4" : "12",
 524                           (tp->user_collected_properties)
 525                               .at("plain_table_hash_table_size"));
 526                 ASSERT_EQ("0", (tp->user_collected_properties)
 527                                    .at("plain_table_sub_index_size"));
 528               } else {
 529                 ASSERT_EQ("0", (tp->user_collected_properties)
 530                                    .at("plain_table_hash_table_size"));
 531                 ASSERT_EQ("0", (tp->user_collected_properties)
 532                                    .at("plain_table_sub_index_size"));
 533               }
 534               ASSERT_EQ("v3", Get("1000000000000foo"));
 535               ASSERT_EQ("v2", Get("0000000000000bar"));
 536             }
 537           }
 538         }
 539       }
 540     }
 541   }
 542 }
 543
 544 TEST_P(PlainTableDBTest, Flush2) {
 545   for (size_t huge_page_tlb_size = 0; huge_page_tlb_size <= 2 * 1024 * 1024;
 546        huge_page_tlb_size += 2 * 1024 * 1024) {
 547     for (EncodingType encoding_type : {kPlain, kPrefix}) {
 548       for (int bloom_bits = 0; bloom_bits <= 117; bloom_bits += 117) {
 549         for (int total_order = 0; total_order <= 1; total_order++) {
 550           for (int store_index_in_file = 0; store_index_in_file <= 1;
 551                ++store_index_in_file) {
 552             if (encoding_type == kPrefix && total_order) {
 553               continue;
 554             }
 555             if (!bloom_bits && store_index_in_file) {
 556               continue;
 557             }
 558             if (total_order && store_index_in_file) {
 559               continue;
 560             }
 561             bool expect_bloom_not_match = false;
 562             Options options = CurrentOptions();
 563             options.create_if_missing = true;
 564             // Set only one bucket to force bucket conflict.
 565             // Test index interval for the same prefix to be 1, 2 and 4
 566             PlainTableOptions plain_table_options;
 567             if (total_order) {
 568               options.prefix_extractor = nullptr;
 569               plain_table_options.hash_table_ratio = 0;
 570               plain_table_options.index_sparseness = 2;
 571             } else {
 572               plain_table_options.hash_table_ratio = 0.75;
 573               plain_table_options.index_sparseness = 16;
 574             }
 575             plain_table_options.user_key_len = kPlainTableVariableLength;
 576             plain_table_options.bloom_bits_per_key = bloom_bits;
 577             plain_table_options.huge_page_tlb_size = huge_page_tlb_size;
 578             plain_table_options.encoding_type = encoding_type;
 579             plain_table_options.store_index_in_file = store_index_in_file;
 580             options.table_factory.reset(new TestPlainTableFactory(
 581                 &expect_bloom_not_match, plain_table_options,
 582                 0 /* column_family_id */, kDefaultColumnFamilyName));
 583
 584             DestroyAndReopen(&options);
 585             ASSERT_OK(Put("0000000000000bar", "b"));
 586             ASSERT_OK(Put("1000000000000foo", "v1"));
 587             ASSERT_OK(dbfull()->TEST_FlushMemTable());
 588
 589             ASSERT_OK(Put("1000000000000foo", "v2"));
 590             ASSERT_OK(dbfull()->TEST_FlushMemTable());
 591             ASSERT_EQ("v2", Get("1000000000000foo"));
 592
 593             ASSERT_OK(Put("0000000000000eee", "v3"));
 594             ASSERT_OK(dbfull()->TEST_FlushMemTable());
 595             ASSERT_EQ("v3", Get("0000000000000eee"));
 596
 597             ASSERT_OK(Delete("0000000000000bar"));
 598             ASSERT_OK(dbfull()->TEST_FlushMemTable());
 599             ASSERT_EQ("NOT_FOUND", Get("0000000000000bar"));
 600
 601             ASSERT_OK(Put("0000000000000eee", "v5"));
 602             ASSERT_OK(Put("9000000000000eee", "v5"));
 603             ASSERT_OK(dbfull()->TEST_FlushMemTable());
 604             ASSERT_EQ("v5", Get("0000000000000eee"));
 605
 606             // Test Bloom Filter
 607             if (bloom_bits > 0) {
 608               // Neither key nor value should exist.
 609               expect_bloom_not_match = true;
 610               ASSERT_EQ("NOT_FOUND", Get("5_not00000000bar"));
 611               // Key doesn't exist any more but prefix exists.
 612               if (total_order) {
 613                 ASSERT_EQ("NOT_FOUND", Get("1000000000000not"));
 614                 ASSERT_EQ("NOT_FOUND", Get("0000000000000not"));
 615               }
 616               expect_bloom_not_match = false;
 617             }
 618           }
 619         }
 620       }
 621     }
 622   }
 623 }
 624
 625 TEST_P(PlainTableDBTest, Immortal) {
 626   for (EncodingType encoding_type : {kPlain, kPrefix}) {
 627     Options options = CurrentOptions();
 628     options.create_if_missing = true;
 629     options.max_open_files = -1;
 630     // Set only one bucket to force bucket conflict.
 631     // Test index interval for the same prefix to be 1, 2 and 4
 632     PlainTableOptions plain_table_options;
 633     plain_table_options.hash_table_ratio = 0.75;
 634     plain_table_options.index_sparseness = 16;
 635     plain_table_options.user_key_len = kPlainTableVariableLength;
 636     plain_table_options.bloom_bits_per_key = 10;
 637     plain_table_options.encoding_type = encoding_type;
 638     options.table_factory.reset(NewPlainTableFactory(plain_table_options));
 639
 640     DestroyAndReopen(&options);
 641     ASSERT_OK(Put("0000000000000bar", "b"));
 642     ASSERT_OK(Put("1000000000000foo", "v1"));
 643     ASSERT_OK(dbfull()->TEST_FlushMemTable());
 644
 645     int copied = 0;
 646     ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->SetCallBack(
 647         "GetContext::SaveValue::PinSelf", [&](void* /*arg*/) { copied++; });
 648     ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->EnableProcessing();
 649     ASSERT_EQ("b", Get("0000000000000bar"));
 650     ASSERT_EQ("v1", Get("1000000000000foo"));
 651     ASSERT_EQ(2, copied);
 652     copied = 0;
 653
 654     Close();
 655     ASSERT_OK(ReopenForReadOnly(&options));
 656
 657     ASSERT_EQ("b", Get("0000000000000bar"));
 658     ASSERT_EQ("v1", Get("1000000000000foo"));
 659     ASSERT_EQ("NOT_FOUND", Get("1000000000000bar"));
 660     if (mmap_mode()) {
 661       ASSERT_EQ(0, copied);
 662     } else {
 663       ASSERT_EQ(2, copied);
 664     }
 665     ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->DisableProcessing();
 666   }
 667 }
 668
 669 TEST_P(PlainTableDBTest, Iterator) {
 670   for (size_t huge_page_tlb_size = 0; huge_page_tlb_size <= 2 * 1024 * 1024;
 671        huge_page_tlb_size += 2 * 1024 * 1024) {
 672     for (EncodingType encoding_type : {kPlain, kPrefix}) {
 673       for (int bloom_bits = 0; bloom_bits <= 117; bloom_bits += 117) {
 674         for (int total_order = 0; total_order <= 1; total_order++) {
 675           if (encoding_type == kPrefix && total_order == 1) {
 676             continue;
 677           }
 678           bool expect_bloom_not_match = false;
 679           Options options = CurrentOptions();
 680           options.create_if_missing = true;
 681           // Set only one bucket to force bucket conflict.
 682           // Test index interval for the same prefix to be 1, 2 and 4
 683           if (total_order) {
 684             options.prefix_extractor = nullptr;
 685
 686             PlainTableOptions plain_table_options;
 687             plain_table_options.user_key_len = 16;
 688             plain_table_options.bloom_bits_per_key = bloom_bits;
 689             plain_table_options.hash_table_ratio = 0;
 690             plain_table_options.index_sparseness = 2;
 691             plain_table_options.huge_page_tlb_size = huge_page_tlb_size;
 692             plain_table_options.encoding_type = encoding_type;
 693
 694             options.table_factory.reset(new TestPlainTableFactory(
 695                 &expect_bloom_not_match, plain_table_options,
 696                 0 /* column_family_id */, kDefaultColumnFamilyName));
 697           } else {
 698             PlainTableOptions plain_table_options;
 699             plain_table_options.user_key_len = 16;
 700             plain_table_options.bloom_bits_per_key = bloom_bits;
 701             plain_table_options.hash_table_ratio = 0.75;
 702             plain_table_options.index_sparseness = 16;
 703             plain_table_options.huge_page_tlb_size = huge_page_tlb_size;
 704             plain_table_options.encoding_type = encoding_type;
 705
 706             options.table_factory.reset(new TestPlainTableFactory(
 707                 &expect_bloom_not_match, plain_table_options,
 708                 0 /* column_family_id */, kDefaultColumnFamilyName));
 709           }
 710           DestroyAndReopen(&options);
 711
 712           ASSERT_OK(Put("1000000000foo002", "v_2"));
 713           ASSERT_OK(Put("0000000000000bar", "random"));
 714           ASSERT_OK(Put("1000000000foo001", "v1"));
 715           ASSERT_OK(Put("3000000000000bar", "bar_v"));
 716           ASSERT_OK(Put("1000000000foo003", "v__3"));
 717           ASSERT_OK(Put("1000000000foo004", "v__4"));
 718           ASSERT_OK(Put("1000000000foo005", "v__5"));
 719           ASSERT_OK(Put("1000000000foo007", "v__7"));
 720           ASSERT_OK(Put("1000000000foo008", "v__8"));
 721           ASSERT_OK(dbfull()->TEST_FlushMemTable());
 722           ASSERT_EQ("v1", Get("1000000000foo001"));
 723           ASSERT_EQ("v__3", Get("1000000000foo003"));
 724           Iterator* iter = dbfull()->NewIterator(ReadOptions());
 725           iter->Seek("1000000000foo000");
 726           ASSERT_TRUE(iter->Valid());
 727           ASSERT_EQ("1000000000foo001", iter->key().ToString());
 728           ASSERT_EQ("v1", iter->value().ToString());
 729
 730           iter->Next();
 731           ASSERT_TRUE(iter->Valid());
 732           ASSERT_EQ("1000000000foo002", iter->key().ToString());
 733           ASSERT_EQ("v_2", iter->value().ToString());
 734
 735           iter->Next();
 736           ASSERT_TRUE(iter->Valid());
 737           ASSERT_EQ("1000000000foo003", iter->key().ToString());
 738           ASSERT_EQ("v__3", iter->value().ToString());
 739
 740           iter->Next();
 741           ASSERT_TRUE(iter->Valid());
 742           ASSERT_EQ("1000000000foo004", iter->key().ToString());
 743           ASSERT_EQ("v__4", iter->value().ToString());
 744
 745           iter->Seek("3000000000000bar");
 746           ASSERT_TRUE(iter->Valid());
 747           ASSERT_EQ("3000000000000bar", iter->key().ToString());
 748           ASSERT_EQ("bar_v", iter->value().ToString());
 749
 750           iter->Seek("1000000000foo000");
 751           ASSERT_TRUE(iter->Valid());
 752           ASSERT_EQ("1000000000foo001", iter->key().ToString());
 753           ASSERT_EQ("v1", iter->value().ToString());
 754
 755           iter->Seek("1000000000foo005");
 756           ASSERT_TRUE(iter->Valid());
 757           ASSERT_EQ("1000000000foo005", iter->key().ToString());
 758           ASSERT_EQ("v__5", iter->value().ToString());
 759
 760           iter->Seek("1000000000foo006");
 761           ASSERT_TRUE(iter->Valid());
 762           ASSERT_EQ("1000000000foo007", iter->key().ToString());
 763           ASSERT_EQ("v__7", iter->value().ToString());
 764
 765           iter->Seek("1000000000foo008");
 766           ASSERT_TRUE(iter->Valid());
 767           ASSERT_EQ("1000000000foo008", iter->key().ToString());
 768           ASSERT_EQ("v__8", iter->value().ToString());
 769
 770           if (total_order == 0) {
 771             iter->Seek("1000000000foo009");
 772             ASSERT_TRUE(iter->Valid());
 773             ASSERT_EQ("3000000000000bar", iter->key().ToString());
 774           }
 775
 776           // Test Bloom Filter
 777           if (bloom_bits > 0) {
 778             if (!total_order) {
 779               // Neither key nor value should exist.
 780               expect_bloom_not_match = true;
 781               iter->Seek("2not000000000bar");
 782               ASSERT_TRUE(!iter->Valid());
 783               ASSERT_EQ("NOT_FOUND", Get("2not000000000bar"));
 784               expect_bloom_not_match = false;
 785             } else {
 786               expect_bloom_not_match = true;
 787               ASSERT_EQ("NOT_FOUND", Get("2not000000000bar"));
 788               expect_bloom_not_match = false;
 789             }
 790           }
 791           ASSERT_OK(iter->status());
 792           delete iter;
 793         }
 794       }
 795     }
 796   }
 797 }
 798
 799 namespace {
 800 std::string NthKey(size_t n, char filler) {
 801   std::string rv(16, filler);
 802   rv[0] = n % 10;
 803   rv[1] = (n / 10) % 10;
 804   rv[2] = (n / 100) % 10;
 805   rv[3] = (n / 1000) % 10;
 806   return rv;
 807 }
 808 }  // anonymous namespace
 809
 810 TEST_P(PlainTableDBTest, BloomSchema) {
 811   Options options = CurrentOptions();
 812   options.create_if_missing = true;
 813   for (int bloom_locality = 0; bloom_locality <= 1; bloom_locality++) {
 814     options.bloom_locality = bloom_locality;
 815     PlainTableOptions plain_table_options;
 816     plain_table_options.user_key_len = 16;
 817     plain_table_options.bloom_bits_per_key = 3;  // high FP rate for test
 818     plain_table_options.hash_table_ratio = 0.75;
 819     plain_table_options.index_sparseness = 16;
 820     plain_table_options.huge_page_tlb_size = 0;
 821     plain_table_options.encoding_type = kPlain;
 822
 823     bool expect_bloom_not_match = false;
 824     options.table_factory.reset(new TestPlainTableFactory(
 825         &expect_bloom_not_match, plain_table_options, 0 /* column_family_id */,
 826         kDefaultColumnFamilyName));
 827     DestroyAndReopen(&options);
 828
 829     for (unsigned i = 0; i < 2345; ++i) {
 830       ASSERT_OK(Put(NthKey(i, 'y'), "added"));
 831     }
 832     ASSERT_OK(dbfull()->TEST_FlushMemTable());
 833     ASSERT_EQ("added", Get(NthKey(42, 'y')));
 834
 835     for (unsigned i = 0; i < 32; ++i) {
 836       // Known pattern of Bloom filter false positives can detect schema change
 837       // with high probability. Known FPs stuffed into bits:
 838       uint32_t pattern;
 839       if (!bloom_locality) {
 840         pattern = 1785868347UL;
 841       } else if (CACHE_LINE_SIZE == 64U) {
 842         pattern = 2421694657UL;
 843       } else if (CACHE_LINE_SIZE == 128U) {
 844         pattern = 788710956UL;
 845       } else {
 846         ASSERT_EQ(CACHE_LINE_SIZE, 256U);
 847         pattern = 163905UL;
 848       }
 849       bool expect_fp = pattern & (1UL << i);
 850       // fprintf(stderr, "expect_fp@%u: %d\n", i, (int)expect_fp);
 851       expect_bloom_not_match = !expect_fp;
 852       ASSERT_EQ("NOT_FOUND", Get(NthKey(i, 'n')));
 853     }
 854   }
 855 }
 856
 857 namespace {
 858 std::string MakeLongKey(size_t length, char c) {
 859   return std::string(length, c);
 860 }
 861 }  // anonymous namespace
 862
 863 TEST_P(PlainTableDBTest, IteratorLargeKeys) {
 864   Options options = CurrentOptions();
 865
 866   PlainTableOptions plain_table_options;
 867   plain_table_options.user_key_len = 0;
 868   plain_table_options.bloom_bits_per_key = 0;
 869   plain_table_options.hash_table_ratio = 0;
 870
 871   options.table_factory.reset(NewPlainTableFactory(plain_table_options));
 872   options.create_if_missing = true;
 873   options.prefix_extractor.reset();
 874   DestroyAndReopen(&options);
 875
 876   std::string key_list[] = {MakeLongKey(30, '0'), MakeLongKey(16, '1'),
 877                             MakeLongKey(32, '2'), MakeLongKey(60, '3'),
 878                             MakeLongKey(90, '4'), MakeLongKey(50, '5'),
 879                             MakeLongKey(26, '6')};
 880
 881   for (size_t i = 0; i < 7; i++) {
 882     ASSERT_OK(Put(key_list[i], std::to_string(i)));
 883   }
 884
 885   ASSERT_OK(dbfull()->TEST_FlushMemTable());
 886
 887   Iterator* iter = dbfull()->NewIterator(ReadOptions());
 888   iter->Seek(key_list[0]);
 889
 890   for (size_t i = 0; i < 7; i++) {
 891     ASSERT_TRUE(iter->Valid());
 892     ASSERT_EQ(key_list[i], iter->key().ToString());
 893     ASSERT_EQ(std::to_string(i), iter->value().ToString());
 894     iter->Next();
 895   }
 896
 897   ASSERT_TRUE(!iter->Valid());
 898
 899   delete iter;
 900 }
 901
 902 namespace {
 903 std::string MakeLongKeyWithPrefix(size_t length, char c) {
 904   return "00000000" + std::string(length - 8, c);
 905 }
 906 }  // anonymous namespace
 907
 908 TEST_P(PlainTableDBTest, IteratorLargeKeysWithPrefix) {
 909   Options options = CurrentOptions();
 910
 911   PlainTableOptions plain_table_options;
 912   plain_table_options.user_key_len = 16;
 913   plain_table_options.bloom_bits_per_key = 0;
 914   plain_table_options.hash_table_ratio = 0.8;
 915   plain_table_options.index_sparseness = 3;
 916   plain_table_options.huge_page_tlb_size = 0;
 917   plain_table_options.encoding_type = kPrefix;
 918
 919   options.table_factory.reset(NewPlainTableFactory(plain_table_options));
 920   options.create_if_missing = true;
 921   DestroyAndReopen(&options);
 922
 923   std::string key_list[] = {
 924       MakeLongKeyWithPrefix(30, '0'), MakeLongKeyWithPrefix(16, '1'),
 925       MakeLongKeyWithPrefix(32, '2'), MakeLongKeyWithPrefix(60, '3'),
 926       MakeLongKeyWithPrefix(90, '4'), MakeLongKeyWithPrefix(50, '5'),
 927       MakeLongKeyWithPrefix(26, '6')};
 928
 929   for (size_t i = 0; i < 7; i++) {
 930     ASSERT_OK(Put(key_list[i], std::to_string(i)));
 931   }
 932
 933   ASSERT_OK(dbfull()->TEST_FlushMemTable());
 934
 935   Iterator* iter = dbfull()->NewIterator(ReadOptions());
 936   iter->Seek(key_list[0]);
 937
 938   for (size_t i = 0; i < 7; i++) {
 939     ASSERT_TRUE(iter->Valid());
 940     ASSERT_EQ(key_list[i], iter->key().ToString());
 941     ASSERT_EQ(std::to_string(i), iter->value().ToString());
 942     iter->Next();
 943   }
 944
 945   ASSERT_TRUE(!iter->Valid());
 946
 947   delete iter;
 948 }
 949
 950 TEST_P(PlainTableDBTest, IteratorReverseSuffixComparator) {
 951   Options options = CurrentOptions();
 952   options.create_if_missing = true;
 953   // Set only one bucket to force bucket conflict.
 954   // Test index interval for the same prefix to be 1, 2 and 4
 955   test::SimpleSuffixReverseComparator comp;
 956   options.comparator = &comp;
 957   DestroyAndReopen(&options);
 958
 959   ASSERT_OK(Put("1000000000foo002", "v_2"));
 960   ASSERT_OK(Put("0000000000000bar", "random"));
 961   ASSERT_OK(Put("1000000000foo001", "v1"));
 962   ASSERT_OK(Put("3000000000000bar", "bar_v"));
 963   ASSERT_OK(Put("1000000000foo003", "v__3"));
 964   ASSERT_OK(Put("1000000000foo004", "v__4"));
 965   ASSERT_OK(Put("1000000000foo005", "v__5"));
 966   ASSERT_OK(Put("1000000000foo007", "v__7"));
 967   ASSERT_OK(Put("1000000000foo008", "v__8"));
 968   ASSERT_OK(dbfull()->TEST_FlushMemTable());
 969   ASSERT_EQ("v1", Get("1000000000foo001"));
 970   ASSERT_EQ("v__3", Get("1000000000foo003"));
 971   Iterator* iter = dbfull()->NewIterator(ReadOptions());
 972   iter->Seek("1000000000foo009");
 973   ASSERT_TRUE(iter->Valid());
 974   ASSERT_EQ("1000000000foo008", iter->key().ToString());
 975   ASSERT_EQ("v__8", iter->value().ToString());
 976
 977   iter->Next();
 978   ASSERT_TRUE(iter->Valid());
 979   ASSERT_EQ("1000000000foo007", iter->key().ToString());
 980   ASSERT_EQ("v__7", iter->value().ToString());
 981
 982   iter->Next();
 983   ASSERT_TRUE(iter->Valid());
 984   ASSERT_EQ("1000000000foo005", iter->key().ToString());
 985   ASSERT_EQ("v__5", iter->value().ToString());
 986
 987   iter->Next();
 988   ASSERT_TRUE(iter->Valid());
 989   ASSERT_EQ("1000000000foo004", iter->key().ToString());
 990   ASSERT_EQ("v__4", iter->value().ToString());
 991
 992   iter->Seek("3000000000000bar");
 993   ASSERT_TRUE(iter->Valid());
 994   ASSERT_EQ("3000000000000bar", iter->key().ToString());
 995   ASSERT_EQ("bar_v", iter->value().ToString());
 996
 997   iter->Seek("1000000000foo005");
 998   ASSERT_TRUE(iter->Valid());
 999   ASSERT_EQ("1000000000foo005", iter->key().ToString());
1000   ASSERT_EQ("v__5", iter->value().ToString());
1001
1002   iter->Seek("1000000000foo006");
1003   ASSERT_TRUE(iter->Valid());
1004   ASSERT_EQ("1000000000foo005", iter->key().ToString());
1005   ASSERT_EQ("v__5", iter->value().ToString());
1006
1007   iter->Seek("1000000000foo008");
1008   ASSERT_TRUE(iter->Valid());
1009   ASSERT_EQ("1000000000foo008", iter->key().ToString());
1010   ASSERT_EQ("v__8", iter->value().ToString());
1011
1012   iter->Seek("1000000000foo000");
1013   ASSERT_TRUE(iter->Valid());
1014   ASSERT_EQ("3000000000000bar", iter->key().ToString());
1015
1016   delete iter;
1017 }
1018
1019 TEST_P(PlainTableDBTest, HashBucketConflict) {
1020   for (size_t huge_page_tlb_size = 0; huge_page_tlb_size <= 2 * 1024 * 1024;
1021        huge_page_tlb_size += 2 * 1024 * 1024) {
1022     for (unsigned char i = 1; i <= 3; i++) {
1023       Options options = CurrentOptions();
1024       options.create_if_missing = true;
1025       // Set only one bucket to force bucket conflict.
1026       // Test index interval for the same prefix to be 1, 2 and 4
1027
1028       PlainTableOptions plain_table_options;
1029       plain_table_options.user_key_len = 16;
1030       plain_table_options.bloom_bits_per_key = 0;
1031       plain_table_options.hash_table_ratio = 0;
1032       plain_table_options.index_sparseness = 2 ^ i;
1033       plain_table_options.huge_page_tlb_size = huge_page_tlb_size;
1034
1035       options.table_factory.reset(NewPlainTableFactory(plain_table_options));
1036
1037       DestroyAndReopen(&options);
1038       ASSERT_OK(Put("5000000000000fo0", "v1"));
1039       ASSERT_OK(Put("5000000000000fo1", "v2"));
1040       ASSERT_OK(Put("5000000000000fo2", "v"));
1041       ASSERT_OK(Put("2000000000000fo0", "v3"));
1042       ASSERT_OK(Put("2000000000000fo1", "v4"));
1043       ASSERT_OK(Put("2000000000000fo2", "v"));
1044       ASSERT_OK(Put("2000000000000fo3", "v"));
1045
1046       ASSERT_OK(dbfull()->TEST_FlushMemTable());
1047
1048       ASSERT_EQ("v1", Get("5000000000000fo0"));
1049       ASSERT_EQ("v2", Get("5000000000000fo1"));
1050       ASSERT_EQ("v3", Get("2000000000000fo0"));
1051       ASSERT_EQ("v4", Get("2000000000000fo1"));
1052
1053       ASSERT_EQ("NOT_FOUND", Get("5000000000000bar"));
1054       ASSERT_EQ("NOT_FOUND", Get("2000000000000bar"));
1055       ASSERT_EQ("NOT_FOUND", Get("5000000000000fo8"));
1056       ASSERT_EQ("NOT_FOUND", Get("2000000000000fo8"));
1057
1058       ReadOptions ro;
1059       Iterator* iter = dbfull()->NewIterator(ro);
1060
1061       iter->Seek("5000000000000fo0");
1062       ASSERT_TRUE(iter->Valid());
1063       ASSERT_EQ("5000000000000fo0", iter->key().ToString());
1064       iter->Next();
1065       ASSERT_TRUE(iter->Valid());
1066       ASSERT_EQ("5000000000000fo1", iter->key().ToString());
1067
1068       iter->Seek("5000000000000fo1");
1069       ASSERT_TRUE(iter->Valid());
1070       ASSERT_EQ("5000000000000fo1", iter->key().ToString());
1071
1072       iter->Seek("2000000000000fo0");
1073       ASSERT_TRUE(iter->Valid());
1074       ASSERT_EQ("2000000000000fo0", iter->key().ToString());
1075       iter->Next();
1076       ASSERT_TRUE(iter->Valid());
1077       ASSERT_EQ("2000000000000fo1", iter->key().ToString());
1078
1079       iter->Seek("2000000000000fo1");
1080       ASSERT_TRUE(iter->Valid());
1081       ASSERT_EQ("2000000000000fo1", iter->key().ToString());
1082
1083       iter->Seek("2000000000000bar");
1084       ASSERT_TRUE(iter->Valid());
1085       ASSERT_EQ("2000000000000fo0", iter->key().ToString());
1086
1087       iter->Seek("5000000000000bar");
1088       ASSERT_TRUE(iter->Valid());
1089       ASSERT_EQ("5000000000000fo0", iter->key().ToString());
1090
1091       iter->Seek("2000000000000fo8");
1092       ASSERT_TRUE(!iter->Valid() ||
1093                   options.comparator->Compare(iter->key(), "20000001") > 0);
1094
1095       iter->Seek("5000000000000fo8");
1096       ASSERT_TRUE(!iter->Valid());
1097
1098       iter->Seek("1000000000000fo2");
1099       ASSERT_TRUE(!iter->Valid());
1100
1101       iter->Seek("3000000000000fo2");
1102       ASSERT_TRUE(!iter->Valid());
1103
1104       iter->Seek("8000000000000fo2");
1105       ASSERT_TRUE(!iter->Valid());
1106
1107       ASSERT_OK(iter->status());
1108       delete iter;
1109     }
1110   }
1111 }
1112
1113 TEST_P(PlainTableDBTest, HashBucketConflictReverseSuffixComparator) {
1114   for (size_t huge_page_tlb_size = 0; huge_page_tlb_size <= 2 * 1024 * 1024;
1115        huge_page_tlb_size += 2 * 1024 * 1024) {
1116     for (unsigned char i = 1; i <= 3; i++) {
1117       Options options = CurrentOptions();
1118       options.create_if_missing = true;
1119       test::SimpleSuffixReverseComparator comp;
1120       options.comparator = &comp;
1121       // Set only one bucket to force bucket conflict.
1122       // Test index interval for the same prefix to be 1, 2 and 4
1123
1124       PlainTableOptions plain_table_options;
1125       plain_table_options.user_key_len = 16;
1126       plain_table_options.bloom_bits_per_key = 0;
1127       plain_table_options.hash_table_ratio = 0;
1128       plain_table_options.index_sparseness = 2 ^ i;
1129       plain_table_options.huge_page_tlb_size = huge_page_tlb_size;
1130
1131       options.table_factory.reset(NewPlainTableFactory(plain_table_options));
1132       DestroyAndReopen(&options);
1133       ASSERT_OK(Put("5000000000000fo0", "v1"));
1134       ASSERT_OK(Put("5000000000000fo1", "v2"));
1135       ASSERT_OK(Put("5000000000000fo2", "v"));
1136       ASSERT_OK(Put("2000000000000fo0", "v3"));
1137       ASSERT_OK(Put("2000000000000fo1", "v4"));
1138       ASSERT_OK(Put("2000000000000fo2", "v"));
1139       ASSERT_OK(Put("2000000000000fo3", "v"));
1140
1141       ASSERT_OK(dbfull()->TEST_FlushMemTable());
1142
1143       ASSERT_EQ("v1", Get("5000000000000fo0"));
1144       ASSERT_EQ("v2", Get("5000000000000fo1"));
1145       ASSERT_EQ("v3", Get("2000000000000fo0"));
1146       ASSERT_EQ("v4", Get("2000000000000fo1"));
1147
1148       ASSERT_EQ("NOT_FOUND", Get("5000000000000bar"));
1149       ASSERT_EQ("NOT_FOUND", Get("2000000000000bar"));
1150       ASSERT_EQ("NOT_FOUND", Get("5000000000000fo8"));
1151       ASSERT_EQ("NOT_FOUND", Get("2000000000000fo8"));
1152
1153       ReadOptions ro;
1154       Iterator* iter = dbfull()->NewIterator(ro);
1155
1156       iter->Seek("5000000000000fo1");
1157       ASSERT_TRUE(iter->Valid());
1158       ASSERT_EQ("5000000000000fo1", iter->key().ToString());
1159       iter->Next();
1160       ASSERT_TRUE(iter->Valid());
1161       ASSERT_EQ("5000000000000fo0", iter->key().ToString());
1162
1163       iter->Seek("5000000000000fo1");
1164       ASSERT_TRUE(iter->Valid());
1165       ASSERT_EQ("5000000000000fo1", iter->key().ToString());
1166
1167       iter->Seek("2000000000000fo1");
1168       ASSERT_TRUE(iter->Valid());
1169       ASSERT_EQ("2000000000000fo1", iter->key().ToString());
1170       iter->Next();
1171       ASSERT_TRUE(iter->Valid());
1172       ASSERT_EQ("2000000000000fo0", iter->key().ToString());
1173
1174       iter->Seek("2000000000000fo1");
1175       ASSERT_TRUE(iter->Valid());
1176       ASSERT_EQ("2000000000000fo1", iter->key().ToString());
1177
1178       iter->Seek("2000000000000var");
1179       ASSERT_TRUE(iter->Valid());
1180       ASSERT_EQ("2000000000000fo3", iter->key().ToString());
1181
1182       iter->Seek("5000000000000var");
1183       ASSERT_TRUE(iter->Valid());
1184       ASSERT_EQ("5000000000000fo2", iter->key().ToString());
1185
1186       std::string seek_key = "2000000000000bar";
1187       iter->Seek(seek_key);
1188       ASSERT_TRUE(!iter->Valid() ||
1189                   options.prefix_extractor->Transform(iter->key()) !=
1190                       options.prefix_extractor->Transform(seek_key));
1191
1192       iter->Seek("1000000000000fo2");
1193       ASSERT_TRUE(!iter->Valid());
1194
1195       iter->Seek("3000000000000fo2");
1196       ASSERT_TRUE(!iter->Valid());
1197
1198       iter->Seek("8000000000000fo2");
1199       ASSERT_TRUE(!iter->Valid());
1200
1201       ASSERT_OK(iter->status());
1202       delete iter;
1203     }
1204   }
1205 }
1206
1207 TEST_P(PlainTableDBTest, NonExistingKeyToNonEmptyBucket) {
1208   Options options = CurrentOptions();
1209   options.create_if_missing = true;
1210   // Set only one bucket to force bucket conflict.
1211   // Test index interval for the same prefix to be 1, 2 and 4
1212   PlainTableOptions plain_table_options;
1213   plain_table_options.user_key_len = 16;
1214   plain_table_options.bloom_bits_per_key = 0;
1215   plain_table_options.hash_table_ratio = 0;
1216   plain_table_options.index_sparseness = 5;
1217
1218   options.table_factory.reset(NewPlainTableFactory(plain_table_options));
1219   DestroyAndReopen(&options);
1220   ASSERT_OK(Put("5000000000000fo0", "v1"));
1221   ASSERT_OK(Put("5000000000000fo1", "v2"));
1222   ASSERT_OK(Put("5000000000000fo2", "v3"));
1223
1224   ASSERT_OK(dbfull()->TEST_FlushMemTable());
1225
1226   ASSERT_EQ("v1", Get("5000000000000fo0"));
1227   ASSERT_EQ("v2", Get("5000000000000fo1"));
1228   ASSERT_EQ("v3", Get("5000000000000fo2"));
1229
1230   ASSERT_EQ("NOT_FOUND", Get("8000000000000bar"));
1231   ASSERT_EQ("NOT_FOUND", Get("1000000000000bar"));
1232
1233   Iterator* iter = dbfull()->NewIterator(ReadOptions());
1234
1235   iter->Seek("5000000000000bar");
1236   ASSERT_TRUE(iter->Valid());
1237   ASSERT_EQ("5000000000000fo0", iter->key().ToString());
1238
1239   iter->Seek("5000000000000fo8");
1240   ASSERT_TRUE(!iter->Valid());
1241
1242   iter->Seek("1000000000000fo2");
1243   ASSERT_TRUE(!iter->Valid());
1244
1245   iter->Seek("8000000000000fo2");
1246   ASSERT_TRUE(!iter->Valid());
1247
1248   ASSERT_OK(iter->status());
1249   delete iter;
1250 }
1251
1252 static std::string Key(int i) {
1253   char buf[100];
1254   snprintf(buf, sizeof(buf), "key_______%06d", i);
1255   return std::string(buf);
1256 }
1257
1258 TEST_P(PlainTableDBTest, CompactionTrigger) {
1259   Options options = CurrentOptions();
1260   options.write_buffer_size = 120 << 10;  // 120KB
1261   options.num_levels = 3;
1262   options.level0_file_num_compaction_trigger = 3;
1263   Reopen(&options);
1264
1265   Random rnd(301);
1266
1267   for (int num = 0; num < options.level0_file_num_compaction_trigger - 1;
1268        num++) {
1269     std::vector<std::string> values;
1270     // Write 120KB (10 values, each 12K)
1271     for (int i = 0; i < 10; i++) {
1272       values.push_back(rnd.RandomString(12 << 10));
1273       ASSERT_OK(Put(Key(i), values[i]));
1274     }
1275     ASSERT_OK(Put(Key(999), ""));
1276     ASSERT_OK(dbfull()->TEST_WaitForFlushMemTable());
1277     ASSERT_EQ(NumTableFilesAtLevel(0), num + 1);
1278   }
1279
1280   // generate one more file in level-0, and should trigger level-0 compaction
1281   std::vector<std::string> values;
1282   for (int i = 0; i < 12; i++) {
1283     values.push_back(rnd.RandomString(10000));
1284     ASSERT_OK(Put(Key(i), values[i]));
1285   }
1286   ASSERT_OK(Put(Key(999), ""));
1287   ASSERT_OK(dbfull()->TEST_WaitForCompact());
1288
1289   ASSERT_EQ(NumTableFilesAtLevel(0), 0);
1290   ASSERT_EQ(NumTableFilesAtLevel(1), 1);
1291 }
1292
1293 TEST_P(PlainTableDBTest, AdaptiveTable) {
1294   Options options = CurrentOptions();
1295   options.create_if_missing = true;
1296
1297   options.table_factory.reset(NewPlainTableFactory());
1298   DestroyAndReopen(&options);
1299
1300   ASSERT_OK(Put("1000000000000foo", "v1"));
1301   ASSERT_OK(Put("0000000000000bar", "v2"));
1302   ASSERT_OK(Put("1000000000000foo", "v3"));
1303   ASSERT_OK(dbfull()->TEST_FlushMemTable());
1304
1305   options.create_if_missing = false;
1306   std::shared_ptr<TableFactory> block_based_factory(
1307       NewBlockBasedTableFactory());
1308   std::shared_ptr<TableFactory> plain_table_factory(NewPlainTableFactory());
1309   std::shared_ptr<TableFactory> dummy_factory;
1310   options.table_factory.reset(NewAdaptiveTableFactory(
1311       block_based_factory, block_based_factory, plain_table_factory));
1312   Reopen(&options);
1313   ASSERT_EQ("v3", Get("1000000000000foo"));
1314   ASSERT_EQ("v2", Get("0000000000000bar"));
1315
1316   ASSERT_OK(Put("2000000000000foo", "v4"));
1317   ASSERT_OK(Put("3000000000000bar", "v5"));
1318   ASSERT_OK(dbfull()->TEST_FlushMemTable());
1319   ASSERT_EQ("v4", Get("2000000000000foo"));
1320   ASSERT_EQ("v5", Get("3000000000000bar"));
1321
1322   Reopen(&options);
1323   ASSERT_EQ("v3", Get("1000000000000foo"));
1324   ASSERT_EQ("v2", Get("0000000000000bar"));
1325   ASSERT_EQ("v4", Get("2000000000000foo"));
1326   ASSERT_EQ("v5", Get("3000000000000bar"));
1327
1328   options.paranoid_checks = false;
1329   options.table_factory.reset(NewBlockBasedTableFactory());
1330   Reopen(&options);
1331   ASSERT_NE("v3", Get("1000000000000foo"));
1332
1333   options.paranoid_checks = false;
1334   options.table_factory.reset(NewPlainTableFactory());
1335   Reopen(&options);
1336   ASSERT_NE("v5", Get("3000000000000bar"));
1337 }
1338
1339 INSTANTIATE_TEST_CASE_P(PlainTableDBTest, PlainTableDBTest, ::testing::Bool());
1340
1341 }  // namespace ROCKSDB_NAMESPACE
1342
1343 int main(int argc, char** argv) {
1344   ROCKSDB_NAMESPACE::port::InstallStackTraceHandler();
1345   ::testing::InitGoogleTest(&argc, argv);
1346   return RUN_ALL_TESTS();
1347 }
1348
1349 #else
1350 #include <stdio.h>
1351
1352 int main(int /*argc*/, char** /*argv*/) {
1353   fprintf(stderr, "SKIPPED as plain table is not supported in ROCKSDB_LITE\n");
1354   return 0;
1355 }
1356
1357 #endif  // !ROCKSDB_LITE