ceph/src/rocksdb/db/compaction_picker_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 #include "db/compaction_picker.h"
   7 #include <limits>
   8 #include <string>
   9 #include <utility>
  10 #include "db/compaction.h"
  11 #include "db/compaction_picker_universal.h"
  12
  13 #include "util/logging.h"
  14 #include "util/string_util.h"
  15 #include "util/testharness.h"
  16 #include "util/testutil.h"
  17
  18 namespace rocksdb {
  19
  20 class CountingLogger : public Logger {
  21  public:
  22   using Logger::Logv;
  23   virtual void Logv(const char* /*format*/, va_list /*ap*/) override {
  24     log_count++;
  25   }
  26   size_t log_count;
  27 };
  28
  29 class CompactionPickerTest : public testing::Test {
  30  public:
  31   const Comparator* ucmp_;
  32   InternalKeyComparator icmp_;
  33   Options options_;
  34   ImmutableCFOptions ioptions_;
  35   MutableCFOptions mutable_cf_options_;
  36   LevelCompactionPicker level_compaction_picker;
  37   std::string cf_name_;
  38   CountingLogger logger_;
  39   LogBuffer log_buffer_;
  40   uint32_t file_num_;
  41   CompactionOptionsFIFO fifo_options_;
  42   std::unique_ptr<VersionStorageInfo> vstorage_;
  43   std::vector<std::unique_ptr<FileMetaData>> files_;
  44   // does not own FileMetaData
  45   std::unordered_map<uint32_t, std::pair<FileMetaData*, int>> file_map_;
  46   // input files to compaction process.
  47   std::vector<CompactionInputFiles> input_files_;
  48   int compaction_level_start_;
  49
  50   CompactionPickerTest()
  51       : ucmp_(BytewiseComparator()),
  52         icmp_(ucmp_),
  53         ioptions_(options_),
  54         mutable_cf_options_(options_),
  55         level_compaction_picker(ioptions_, &icmp_),
  56         cf_name_("dummy"),
  57         log_buffer_(InfoLogLevel::INFO_LEVEL, &logger_),
  58         file_num_(1),
  59         vstorage_(nullptr) {
  60     fifo_options_.max_table_files_size = 1;
  61     mutable_cf_options_.RefreshDerivedOptions(ioptions_);
  62     ioptions_.cf_paths.emplace_back("dummy",
  63                                     std::numeric_limits<uint64_t>::max());
  64   }
  65
  66   ~CompactionPickerTest() {
  67   }
  68
  69   void NewVersionStorage(int num_levels, CompactionStyle style) {
  70     DeleteVersionStorage();
  71     options_.num_levels = num_levels;
  72     vstorage_.reset(new VersionStorageInfo(&icmp_, ucmp_, options_.num_levels,
  73                                            style, nullptr, false));
  74     vstorage_->CalculateBaseBytes(ioptions_, mutable_cf_options_);
  75   }
  76
  77   void DeleteVersionStorage() {
  78     vstorage_.reset();
  79     files_.clear();
  80     file_map_.clear();
  81     input_files_.clear();
  82   }
  83
  84   void Add(int level, uint32_t file_number, const char* smallest,
  85            const char* largest, uint64_t file_size = 1, uint32_t path_id = 0,
  86            SequenceNumber smallest_seq = 100,
  87            SequenceNumber largest_seq = 100) {
  88     assert(level < vstorage_->num_levels());
  89     FileMetaData* f = new FileMetaData;
  90     f->fd = FileDescriptor(file_number, path_id, file_size);
  91     f->smallest = InternalKey(smallest, smallest_seq, kTypeValue);
  92     f->largest = InternalKey(largest, largest_seq, kTypeValue);
  93     f->fd.smallest_seqno = smallest_seq;
  94     f->fd.largest_seqno = largest_seq;
  95     f->compensated_file_size = file_size;
  96     f->refs = 0;
  97     vstorage_->AddFile(level, f);
  98     files_.emplace_back(f);
  99     file_map_.insert({file_number, {f, level}});
 100   }
 101
 102   void SetCompactionInputFilesLevels(int level_count, int start_level) {
 103     input_files_.resize(level_count);
 104     for (int i = 0; i < level_count; ++i) {
 105       input_files_[i].level = start_level + i;
 106     }
 107     compaction_level_start_ = start_level;
 108   }
 109
 110   void AddToCompactionFiles(uint32_t file_number) {
 111     auto iter = file_map_.find(file_number);
 112     assert(iter != file_map_.end());
 113     int level = iter->second.second;
 114     assert(level < vstorage_->num_levels());
 115     input_files_[level - compaction_level_start_].files.emplace_back(
 116         iter->second.first);
 117   }
 118
 119   void UpdateVersionStorageInfo() {
 120     vstorage_->CalculateBaseBytes(ioptions_, mutable_cf_options_);
 121     vstorage_->UpdateFilesByCompactionPri(ioptions_.compaction_pri);
 122     vstorage_->UpdateNumNonEmptyLevels();
 123     vstorage_->GenerateFileIndexer();
 124     vstorage_->GenerateLevelFilesBrief();
 125     vstorage_->ComputeCompactionScore(ioptions_, mutable_cf_options_);
 126     vstorage_->GenerateLevel0NonOverlapping();
 127     vstorage_->ComputeFilesMarkedForCompaction();
 128     vstorage_->SetFinalized();
 129   }
 130 };
 131
 132 TEST_F(CompactionPickerTest, Empty) {
 133   NewVersionStorage(6, kCompactionStyleLevel);
 134   UpdateVersionStorageInfo();
 135   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
 136       cf_name_, mutable_cf_options_, vstorage_.get(), &log_buffer_));
 137   ASSERT_TRUE(compaction.get() == nullptr);
 138 }
 139
 140 TEST_F(CompactionPickerTest, Single) {
 141   NewVersionStorage(6, kCompactionStyleLevel);
 142   mutable_cf_options_.level0_file_num_compaction_trigger = 2;
 143   Add(0, 1U, "p", "q");
 144   UpdateVersionStorageInfo();
 145
 146   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
 147       cf_name_, mutable_cf_options_, vstorage_.get(), &log_buffer_));
 148   ASSERT_TRUE(compaction.get() == nullptr);
 149 }
 150
 151 TEST_F(CompactionPickerTest, Level0Trigger) {
 152   NewVersionStorage(6, kCompactionStyleLevel);
 153   mutable_cf_options_.level0_file_num_compaction_trigger = 2;
 154   Add(0, 1U, "150", "200");
 155   Add(0, 2U, "200", "250");
 156
 157   UpdateVersionStorageInfo();
 158
 159   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
 160       cf_name_, mutable_cf_options_, vstorage_.get(), &log_buffer_));
 161   ASSERT_TRUE(compaction.get() != nullptr);
 162   ASSERT_EQ(2U, compaction->num_input_files(0));
 163   ASSERT_EQ(1U, compaction->input(0, 0)->fd.GetNumber());
 164   ASSERT_EQ(2U, compaction->input(0, 1)->fd.GetNumber());
 165 }
 166
 167 TEST_F(CompactionPickerTest, Level1Trigger) {
 168   NewVersionStorage(6, kCompactionStyleLevel);
 169   Add(1, 66U, "150", "200", 1000000000U);
 170   UpdateVersionStorageInfo();
 171
 172   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
 173       cf_name_, mutable_cf_options_, vstorage_.get(), &log_buffer_));
 174   ASSERT_TRUE(compaction.get() != nullptr);
 175   ASSERT_EQ(1U, compaction->num_input_files(0));
 176   ASSERT_EQ(66U, compaction->input(0, 0)->fd.GetNumber());
 177 }
 178
 179 TEST_F(CompactionPickerTest, Level1Trigger2) {
 180   mutable_cf_options_.target_file_size_base = 10000000000;
 181   mutable_cf_options_.RefreshDerivedOptions(ioptions_);
 182   NewVersionStorage(6, kCompactionStyleLevel);
 183   Add(1, 66U, "150", "200", 1000000001U);
 184   Add(1, 88U, "201", "300", 1000000000U);
 185   Add(2, 6U, "150", "179", 1000000000U);
 186   Add(2, 7U, "180", "220", 1000000000U);
 187   Add(2, 8U, "221", "300", 1000000000U);
 188   UpdateVersionStorageInfo();
 189
 190   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
 191       cf_name_, mutable_cf_options_, vstorage_.get(), &log_buffer_));
 192   ASSERT_TRUE(compaction.get() != nullptr);
 193   ASSERT_EQ(1U, compaction->num_input_files(0));
 194   ASSERT_EQ(2U, compaction->num_input_files(1));
 195   ASSERT_EQ(66U, compaction->input(0, 0)->fd.GetNumber());
 196   ASSERT_EQ(6U, compaction->input(1, 0)->fd.GetNumber());
 197   ASSERT_EQ(7U, compaction->input(1, 1)->fd.GetNumber());
 198   ASSERT_EQ(uint64_t{1073741824}, compaction->OutputFilePreallocationSize());
 199 }
 200
 201 TEST_F(CompactionPickerTest, LevelMaxScore) {
 202   NewVersionStorage(6, kCompactionStyleLevel);
 203   mutable_cf_options_.target_file_size_base = 10000000;
 204   mutable_cf_options_.max_bytes_for_level_base = 10 * 1024 * 1024;
 205   mutable_cf_options_.RefreshDerivedOptions(ioptions_);
 206   Add(0, 1U, "150", "200", 1000000U);
 207   // Level 1 score 1.2
 208   Add(1, 66U, "150", "200", 6000000U);
 209   Add(1, 88U, "201", "300", 6000000U);
 210   // Level 2 score 1.8. File 7 is the largest. Should be picked
 211   Add(2, 6U, "150", "179", 60000000U);
 212   Add(2, 7U, "180", "220", 60000001U);
 213   Add(2, 8U, "221", "300", 60000000U);
 214   // Level 3 score slightly larger than 1
 215   Add(3, 26U, "150", "170", 260000000U);
 216   Add(3, 27U, "171", "179", 260000000U);
 217   Add(3, 28U, "191", "220", 260000000U);
 218   Add(3, 29U, "221", "300", 260000000U);
 219   UpdateVersionStorageInfo();
 220
 221   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
 222       cf_name_, mutable_cf_options_, vstorage_.get(), &log_buffer_));
 223   ASSERT_TRUE(compaction.get() != nullptr);
 224   ASSERT_EQ(1U, compaction->num_input_files(0));
 225   ASSERT_EQ(7U, compaction->input(0, 0)->fd.GetNumber());
 226   ASSERT_EQ(mutable_cf_options_.target_file_size_base +
 227                 mutable_cf_options_.target_file_size_base / 10,
 228             compaction->OutputFilePreallocationSize());
 229 }
 230
 231 TEST_F(CompactionPickerTest, NeedsCompactionLevel) {
 232   const int kLevels = 6;
 233   const int kFileCount = 20;
 234
 235   for (int level = 0; level < kLevels - 1; ++level) {
 236     NewVersionStorage(kLevels, kCompactionStyleLevel);
 237     uint64_t file_size = vstorage_->MaxBytesForLevel(level) * 2 / kFileCount;
 238     for (int file_count = 1; file_count <= kFileCount; ++file_count) {
 239       // start a brand new version in each test.
 240       NewVersionStorage(kLevels, kCompactionStyleLevel);
 241       for (int i = 0; i < file_count; ++i) {
 242         Add(level, i, ToString((i + 100) * 1000).c_str(),
 243             ToString((i + 100) * 1000 + 999).c_str(),
 244             file_size, 0, i * 100, i * 100 + 99);
 245       }
 246       UpdateVersionStorageInfo();
 247       ASSERT_EQ(vstorage_->CompactionScoreLevel(0), level);
 248       ASSERT_EQ(level_compaction_picker.NeedsCompaction(vstorage_.get()),
 249                 vstorage_->CompactionScore(0) >= 1);
 250       // release the version storage
 251       DeleteVersionStorage();
 252     }
 253   }
 254 }
 255
 256 TEST_F(CompactionPickerTest, Level0TriggerDynamic) {
 257   int num_levels = ioptions_.num_levels;
 258   ioptions_.level_compaction_dynamic_level_bytes = true;
 259   mutable_cf_options_.level0_file_num_compaction_trigger = 2;
 260   mutable_cf_options_.max_bytes_for_level_base = 200;
 261   mutable_cf_options_.max_bytes_for_level_multiplier = 10;
 262   NewVersionStorage(num_levels, kCompactionStyleLevel);
 263   Add(0, 1U, "150", "200");
 264   Add(0, 2U, "200", "250");
 265
 266   UpdateVersionStorageInfo();
 267
 268   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
 269       cf_name_, mutable_cf_options_, vstorage_.get(), &log_buffer_));
 270   ASSERT_TRUE(compaction.get() != nullptr);
 271   ASSERT_EQ(2U, compaction->num_input_files(0));
 272   ASSERT_EQ(1U, compaction->input(0, 0)->fd.GetNumber());
 273   ASSERT_EQ(2U, compaction->input(0, 1)->fd.GetNumber());
 274   ASSERT_EQ(1, static_cast<int>(compaction->num_input_levels()));
 275   ASSERT_EQ(num_levels - 1, compaction->output_level());
 276 }
 277
 278 TEST_F(CompactionPickerTest, Level0TriggerDynamic2) {
 279   int num_levels = ioptions_.num_levels;
 280   ioptions_.level_compaction_dynamic_level_bytes = true;
 281   mutable_cf_options_.level0_file_num_compaction_trigger = 2;
 282   mutable_cf_options_.max_bytes_for_level_base = 200;
 283   mutable_cf_options_.max_bytes_for_level_multiplier = 10;
 284   NewVersionStorage(num_levels, kCompactionStyleLevel);
 285   Add(0, 1U, "150", "200");
 286   Add(0, 2U, "200", "250");
 287   Add(num_levels - 1, 3U, "200", "250", 300U);
 288
 289   UpdateVersionStorageInfo();
 290   ASSERT_EQ(vstorage_->base_level(), num_levels - 2);
 291
 292   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
 293       cf_name_, mutable_cf_options_, vstorage_.get(), &log_buffer_));
 294   ASSERT_TRUE(compaction.get() != nullptr);
 295   ASSERT_EQ(2U, compaction->num_input_files(0));
 296   ASSERT_EQ(1U, compaction->input(0, 0)->fd.GetNumber());
 297   ASSERT_EQ(2U, compaction->input(0, 1)->fd.GetNumber());
 298   ASSERT_EQ(1, static_cast<int>(compaction->num_input_levels()));
 299   ASSERT_EQ(num_levels - 2, compaction->output_level());
 300 }
 301
 302 TEST_F(CompactionPickerTest, Level0TriggerDynamic3) {
 303   int num_levels = ioptions_.num_levels;
 304   ioptions_.level_compaction_dynamic_level_bytes = true;
 305   mutable_cf_options_.level0_file_num_compaction_trigger = 2;
 306   mutable_cf_options_.max_bytes_for_level_base = 200;
 307   mutable_cf_options_.max_bytes_for_level_multiplier = 10;
 308   NewVersionStorage(num_levels, kCompactionStyleLevel);
 309   Add(0, 1U, "150", "200");
 310   Add(0, 2U, "200", "250");
 311   Add(num_levels - 1, 3U, "200", "250", 300U);
 312   Add(num_levels - 1, 4U, "300", "350", 3000U);
 313
 314   UpdateVersionStorageInfo();
 315   ASSERT_EQ(vstorage_->base_level(), num_levels - 3);
 316
 317   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
 318       cf_name_, mutable_cf_options_, vstorage_.get(), &log_buffer_));
 319   ASSERT_TRUE(compaction.get() != nullptr);
 320   ASSERT_EQ(2U, compaction->num_input_files(0));
 321   ASSERT_EQ(1U, compaction->input(0, 0)->fd.GetNumber());
 322   ASSERT_EQ(2U, compaction->input(0, 1)->fd.GetNumber());
 323   ASSERT_EQ(1, static_cast<int>(compaction->num_input_levels()));
 324   ASSERT_EQ(num_levels - 3, compaction->output_level());
 325 }
 326
 327 TEST_F(CompactionPickerTest, Level0TriggerDynamic4) {
 328   int num_levels = ioptions_.num_levels;
 329   ioptions_.level_compaction_dynamic_level_bytes = true;
 330   mutable_cf_options_.level0_file_num_compaction_trigger = 2;
 331   mutable_cf_options_.max_bytes_for_level_base = 200;
 332   mutable_cf_options_.max_bytes_for_level_multiplier = 10;
 333
 334   NewVersionStorage(num_levels, kCompactionStyleLevel);
 335   Add(0, 1U, "150", "200");
 336   Add(0, 2U, "200", "250");
 337   Add(num_levels - 1, 3U, "200", "250", 300U);
 338   Add(num_levels - 1, 4U, "300", "350", 3000U);
 339   Add(num_levels - 3, 5U, "150", "180", 3U);
 340   Add(num_levels - 3, 6U, "181", "300", 3U);
 341   Add(num_levels - 3, 7U, "400", "450", 3U);
 342
 343   UpdateVersionStorageInfo();
 344   ASSERT_EQ(vstorage_->base_level(), num_levels - 3);
 345
 346   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
 347       cf_name_, mutable_cf_options_, vstorage_.get(), &log_buffer_));
 348   ASSERT_TRUE(compaction.get() != nullptr);
 349   ASSERT_EQ(2U, compaction->num_input_files(0));
 350   ASSERT_EQ(1U, compaction->input(0, 0)->fd.GetNumber());
 351   ASSERT_EQ(2U, compaction->input(0, 1)->fd.GetNumber());
 352   ASSERT_EQ(2U, compaction->num_input_files(1));
 353   ASSERT_EQ(num_levels - 3, compaction->level(1));
 354   ASSERT_EQ(5U, compaction->input(1, 0)->fd.GetNumber());
 355   ASSERT_EQ(6U, compaction->input(1, 1)->fd.GetNumber());
 356   ASSERT_EQ(2, static_cast<int>(compaction->num_input_levels()));
 357   ASSERT_EQ(num_levels - 3, compaction->output_level());
 358 }
 359
 360 TEST_F(CompactionPickerTest, LevelTriggerDynamic4) {
 361   int num_levels = ioptions_.num_levels;
 362   ioptions_.level_compaction_dynamic_level_bytes = true;
 363   ioptions_.compaction_pri = kMinOverlappingRatio;
 364   mutable_cf_options_.level0_file_num_compaction_trigger = 2;
 365   mutable_cf_options_.max_bytes_for_level_base = 200;
 366   mutable_cf_options_.max_bytes_for_level_multiplier = 10;
 367   NewVersionStorage(num_levels, kCompactionStyleLevel);
 368   Add(0, 1U, "150", "200");
 369   Add(num_levels - 1, 3U, "200", "250", 300U);
 370   Add(num_levels - 1, 4U, "300", "350", 3000U);
 371   Add(num_levels - 1, 4U, "400", "450", 3U);
 372   Add(num_levels - 2, 5U, "150", "180", 300U);
 373   Add(num_levels - 2, 6U, "181", "350", 500U);
 374   Add(num_levels - 2, 7U, "400", "450", 200U);
 375
 376   UpdateVersionStorageInfo();
 377
 378   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
 379       cf_name_, mutable_cf_options_, vstorage_.get(), &log_buffer_));
 380   ASSERT_TRUE(compaction.get() != nullptr);
 381   ASSERT_EQ(1U, compaction->num_input_files(0));
 382   ASSERT_EQ(5U, compaction->input(0, 0)->fd.GetNumber());
 383   ASSERT_EQ(0, compaction->num_input_files(1));
 384   ASSERT_EQ(1U, compaction->num_input_levels());
 385   ASSERT_EQ(num_levels - 1, compaction->output_level());
 386 }
 387
 388 // Universal and FIFO Compactions are not supported in ROCKSDB_LITE
 389 #ifndef ROCKSDB_LITE
 390 TEST_F(CompactionPickerTest, NeedsCompactionUniversal) {
 391   NewVersionStorage(1, kCompactionStyleUniversal);
 392   UniversalCompactionPicker universal_compaction_picker(
 393       ioptions_, &icmp_);
 394   UpdateVersionStorageInfo();
 395   // must return false when there's no files.
 396   ASSERT_EQ(universal_compaction_picker.NeedsCompaction(vstorage_.get()),
 397             false);
 398
 399   // verify the trigger given different number of L0 files.
 400   for (int i = 1;
 401        i <= mutable_cf_options_.level0_file_num_compaction_trigger * 2; ++i) {
 402     NewVersionStorage(1, kCompactionStyleUniversal);
 403     Add(0, i, ToString((i + 100) * 1000).c_str(),
 404         ToString((i + 100) * 1000 + 999).c_str(), 1000000, 0, i * 100,
 405         i * 100 + 99);
 406     UpdateVersionStorageInfo();
 407     ASSERT_EQ(level_compaction_picker.NeedsCompaction(vstorage_.get()),
 408               vstorage_->CompactionScore(0) >= 1);
 409   }
 410 }
 411
 412 TEST_F(CompactionPickerTest, CompactionUniversalIngestBehindReservedLevel) {
 413   const uint64_t kFileSize = 100000;
 414   NewVersionStorage(1, kCompactionStyleUniversal);
 415   ioptions_.allow_ingest_behind = true;
 416   ioptions_.num_levels = 3;
 417   UniversalCompactionPicker universal_compaction_picker(ioptions_, &icmp_);
 418   UpdateVersionStorageInfo();
 419   // must return false when there's no files.
 420   ASSERT_EQ(universal_compaction_picker.NeedsCompaction(vstorage_.get()),
 421             false);
 422
 423   NewVersionStorage(3, kCompactionStyleUniversal);
 424
 425   Add(0, 1U, "150", "200", kFileSize, 0, 500, 550);
 426   Add(0, 2U, "201", "250", kFileSize, 0, 401, 450);
 427   Add(0, 4U, "260", "300", kFileSize, 0, 260, 300);
 428   Add(1, 5U, "100", "151", kFileSize, 0, 200, 251);
 429   Add(1, 3U, "301", "350", kFileSize, 0, 101, 150);
 430   Add(2, 6U, "120", "200", kFileSize, 0, 20, 100);
 431
 432   UpdateVersionStorageInfo();
 433
 434   std::unique_ptr<Compaction> compaction(
 435       universal_compaction_picker.PickCompaction(
 436           cf_name_, mutable_cf_options_, vstorage_.get(), &log_buffer_));
 437
 438   // output level should be the one above the bottom-most
 439   ASSERT_EQ(1, compaction->output_level());
 440 }
 441 // Tests if the files can be trivially moved in multi level
 442 // universal compaction when allow_trivial_move option is set
 443 // In this test as the input files overlaps, they cannot
 444 // be trivially moved.
 445
 446 TEST_F(CompactionPickerTest, CannotTrivialMoveUniversal) {
 447   const uint64_t kFileSize = 100000;
 448
 449   mutable_cf_options_.compaction_options_universal.allow_trivial_move = true;
 450   NewVersionStorage(1, kCompactionStyleUniversal);
 451   UniversalCompactionPicker universal_compaction_picker(ioptions_, &icmp_);
 452   UpdateVersionStorageInfo();
 453   // must return false when there's no files.
 454   ASSERT_EQ(universal_compaction_picker.NeedsCompaction(vstorage_.get()),
 455             false);
 456
 457   NewVersionStorage(3, kCompactionStyleUniversal);
 458
 459   Add(0, 1U, "150", "200", kFileSize, 0, 500, 550);
 460   Add(0, 2U, "201", "250", kFileSize, 0, 401, 450);
 461   Add(0, 4U, "260", "300", kFileSize, 0, 260, 300);
 462   Add(1, 5U, "100", "151", kFileSize, 0, 200, 251);
 463   Add(1, 3U, "301", "350", kFileSize, 0, 101, 150);
 464   Add(2, 6U, "120", "200", kFileSize, 0, 20, 100);
 465
 466   UpdateVersionStorageInfo();
 467
 468   std::unique_ptr<Compaction> compaction(
 469       universal_compaction_picker.PickCompaction(
 470           cf_name_, mutable_cf_options_, vstorage_.get(), &log_buffer_));
 471
 472   ASSERT_TRUE(!compaction->is_trivial_move());
 473 }
 474 // Tests if the files can be trivially moved in multi level
 475 // universal compaction when allow_trivial_move option is set
 476 // In this test as the input files doesn't overlaps, they should
 477 // be trivially moved.
 478 TEST_F(CompactionPickerTest, AllowsTrivialMoveUniversal) {
 479   const uint64_t kFileSize = 100000;
 480
 481   mutable_cf_options_.compaction_options_universal.allow_trivial_move = true;
 482   UniversalCompactionPicker universal_compaction_picker(ioptions_, &icmp_);
 483
 484   NewVersionStorage(3, kCompactionStyleUniversal);
 485
 486   Add(0, 1U, "150", "200", kFileSize, 0, 500, 550);
 487   Add(0, 2U, "201", "250", kFileSize, 0, 401, 450);
 488   Add(0, 4U, "260", "300", kFileSize, 0, 260, 300);
 489   Add(1, 5U, "010", "080", kFileSize, 0, 200, 251);
 490   Add(2, 3U, "301", "350", kFileSize, 0, 101, 150);
 491
 492   UpdateVersionStorageInfo();
 493
 494   std::unique_ptr<Compaction> compaction(
 495       universal_compaction_picker.PickCompaction(
 496           cf_name_, mutable_cf_options_, vstorage_.get(), &log_buffer_));
 497
 498   ASSERT_TRUE(compaction->is_trivial_move());
 499 }
 500
 501 TEST_F(CompactionPickerTest, NeedsCompactionFIFO) {
 502   NewVersionStorage(1, kCompactionStyleFIFO);
 503   const int kFileCount =
 504       mutable_cf_options_.level0_file_num_compaction_trigger * 3;
 505   const uint64_t kFileSize = 100000;
 506   const uint64_t kMaxSize = kFileSize * kFileCount / 2;
 507
 508   fifo_options_.max_table_files_size = kMaxSize;
 509   mutable_cf_options_.compaction_options_fifo = fifo_options_;
 510   FIFOCompactionPicker fifo_compaction_picker(ioptions_, &icmp_);
 511   UpdateVersionStorageInfo();
 512   // must return false when there's no files.
 513   ASSERT_EQ(fifo_compaction_picker.NeedsCompaction(vstorage_.get()), false);
 514
 515   // verify whether compaction is needed based on the current
 516   // size of L0 files.
 517   uint64_t current_size = 0;
 518   for (int i = 1; i <= kFileCount; ++i) {
 519     NewVersionStorage(1, kCompactionStyleFIFO);
 520     Add(0, i, ToString((i + 100) * 1000).c_str(),
 521         ToString((i + 100) * 1000 + 999).c_str(),
 522         kFileSize, 0, i * 100, i * 100 + 99);
 523     current_size += kFileSize;
 524     UpdateVersionStorageInfo();
 525     ASSERT_EQ(fifo_compaction_picker.NeedsCompaction(vstorage_.get()),
 526               vstorage_->CompactionScore(0) >= 1);
 527   }
 528 }
 529 #endif  // ROCKSDB_LITE
 530
 531 TEST_F(CompactionPickerTest, CompactionPriMinOverlapping1) {
 532   NewVersionStorage(6, kCompactionStyleLevel);
 533   ioptions_.compaction_pri = kMinOverlappingRatio;
 534   mutable_cf_options_.target_file_size_base = 100000000000;
 535   mutable_cf_options_.target_file_size_multiplier = 10;
 536   mutable_cf_options_.max_bytes_for_level_base = 10 * 1024 * 1024;
 537   mutable_cf_options_.RefreshDerivedOptions(ioptions_);
 538
 539   Add(2, 6U, "150", "179", 50000000U);
 540   Add(2, 7U, "180", "220", 50000000U);
 541   Add(2, 8U, "321", "400", 50000000U);  // File not overlapping
 542   Add(2, 9U, "721", "800", 50000000U);
 543
 544   Add(3, 26U, "150", "170", 260000000U);
 545   Add(3, 27U, "171", "179", 260000000U);
 546   Add(3, 28U, "191", "220", 260000000U);
 547   Add(3, 29U, "221", "300", 260000000U);
 548   Add(3, 30U, "750", "900", 260000000U);
 549   UpdateVersionStorageInfo();
 550
 551   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
 552       cf_name_, mutable_cf_options_, vstorage_.get(), &log_buffer_));
 553   ASSERT_TRUE(compaction.get() != nullptr);
 554   ASSERT_EQ(1U, compaction->num_input_files(0));
 555   // Pick file 8 because it overlaps with 0 files on level 3.
 556   ASSERT_EQ(8U, compaction->input(0, 0)->fd.GetNumber());
 557   // Compaction input size * 1.1
 558   ASSERT_GE(uint64_t{55000000}, compaction->OutputFilePreallocationSize());
 559 }
 560
 561 TEST_F(CompactionPickerTest, CompactionPriMinOverlapping2) {
 562   NewVersionStorage(6, kCompactionStyleLevel);
 563   ioptions_.compaction_pri = kMinOverlappingRatio;
 564   mutable_cf_options_.target_file_size_base = 10000000;
 565   mutable_cf_options_.target_file_size_multiplier = 10;
 566   mutable_cf_options_.max_bytes_for_level_base = 10 * 1024 * 1024;
 567
 568   Add(2, 6U, "150", "175",
 569       60000000U);  // Overlaps with file 26, 27, total size 521M
 570   Add(2, 7U, "176", "200", 60000000U);  // Overlaps with file 27, 28, total size
 571                                         // 520M, the smalelst overlapping
 572   Add(2, 8U, "201", "300",
 573       60000000U);  // Overlaps with file 28, 29, total size 521M
 574
 575   Add(3, 26U, "100", "110", 261000000U);
 576   Add(3, 26U, "150", "170", 261000000U);
 577   Add(3, 27U, "171", "179", 260000000U);
 578   Add(3, 28U, "191", "220", 260000000U);
 579   Add(3, 29U, "221", "300", 261000000U);
 580   Add(3, 30U, "321", "400", 261000000U);
 581   UpdateVersionStorageInfo();
 582
 583   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
 584       cf_name_, mutable_cf_options_, vstorage_.get(), &log_buffer_));
 585   ASSERT_TRUE(compaction.get() != nullptr);
 586   ASSERT_EQ(1U, compaction->num_input_files(0));
 587   // Picking file 7 because overlapping ratio is the biggest.
 588   ASSERT_EQ(7U, compaction->input(0, 0)->fd.GetNumber());
 589 }
 590
 591 TEST_F(CompactionPickerTest, CompactionPriMinOverlapping3) {
 592   NewVersionStorage(6, kCompactionStyleLevel);
 593   ioptions_.compaction_pri = kMinOverlappingRatio;
 594   mutable_cf_options_.max_bytes_for_level_base = 10000000;
 595   mutable_cf_options_.max_bytes_for_level_multiplier = 10;
 596
 597   // file 7 and 8 over lap with the same file, but file 8 is smaller so
 598   // it will be picked.
 599   Add(2, 6U, "150", "167", 60000000U);  // Overlaps with file 26, 27
 600   Add(2, 7U, "168", "169", 60000000U);  // Overlaps with file 27
 601   Add(2, 8U, "201", "300", 61000000U);  // Overlaps with file 28, but the file
 602                                         // itself is larger. Should be picked.
 603
 604   Add(3, 26U, "160", "165", 260000000U);
 605   Add(3, 27U, "166", "170", 260000000U);
 606   Add(3, 28U, "180", "400", 260000000U);
 607   Add(3, 29U, "401", "500", 260000000U);
 608   UpdateVersionStorageInfo();
 609
 610   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
 611       cf_name_, mutable_cf_options_, vstorage_.get(), &log_buffer_));
 612   ASSERT_TRUE(compaction.get() != nullptr);
 613   ASSERT_EQ(1U, compaction->num_input_files(0));
 614   // Picking file 8 because overlapping ratio is the biggest.
 615   ASSERT_EQ(8U, compaction->input(0, 0)->fd.GetNumber());
 616 }
 617
 618 // This test exhibits the bug where we don't properly reset parent_index in
 619 // PickCompaction()
 620 TEST_F(CompactionPickerTest, ParentIndexResetBug) {
 621   int num_levels = ioptions_.num_levels;
 622   mutable_cf_options_.level0_file_num_compaction_trigger = 2;
 623   mutable_cf_options_.max_bytes_for_level_base = 200;
 624   NewVersionStorage(num_levels, kCompactionStyleLevel);
 625   Add(0, 1U, "150", "200");       // <- marked for compaction
 626   Add(1, 3U, "400", "500", 600);  // <- this one needs compacting
 627   Add(2, 4U, "150", "200");
 628   Add(2, 5U, "201", "210");
 629   Add(2, 6U, "300", "310");
 630   Add(2, 7U, "400", "500");  // <- being compacted
 631
 632   vstorage_->LevelFiles(2)[3]->being_compacted = true;
 633   vstorage_->LevelFiles(0)[0]->marked_for_compaction = true;
 634
 635   UpdateVersionStorageInfo();
 636
 637   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
 638       cf_name_, mutable_cf_options_, vstorage_.get(), &log_buffer_));
 639 }
 640
 641 // This test checks ExpandWhileOverlapping() by having overlapping user keys
 642 // ranges (with different sequence numbers) in the input files.
 643 TEST_F(CompactionPickerTest, OverlappingUserKeys) {
 644   NewVersionStorage(6, kCompactionStyleLevel);
 645   ioptions_.compaction_pri = kByCompensatedSize;
 646
 647   Add(1, 1U, "100", "150", 1U);
 648   // Overlapping user keys
 649   Add(1, 2U, "200", "400", 1U);
 650   Add(1, 3U, "400", "500", 1000000000U, 0, 0);
 651   Add(2, 4U, "600", "700", 1U);
 652   UpdateVersionStorageInfo();
 653
 654   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
 655               cf_name_, mutable_cf_options_, vstorage_.get(), &log_buffer_));
 656   ASSERT_TRUE(compaction.get() != nullptr);
 657   ASSERT_EQ(1U, compaction->num_input_levels());
 658   ASSERT_EQ(2U, compaction->num_input_files(0));
 659   ASSERT_EQ(2U, compaction->input(0, 0)->fd.GetNumber());
 660   ASSERT_EQ(3U, compaction->input(0, 1)->fd.GetNumber());
 661 }
 662
 663 TEST_F(CompactionPickerTest, OverlappingUserKeys2) {
 664   NewVersionStorage(6, kCompactionStyleLevel);
 665   // Overlapping user keys on same level and output level
 666   Add(1, 1U, "200", "400", 1000000000U);
 667   Add(1, 2U, "400", "500", 1U, 0, 0);
 668   Add(2, 3U, "000", "100", 1U);
 669   Add(2, 4U, "100", "600", 1U, 0, 0);
 670   Add(2, 5U, "600", "700", 1U, 0, 0);
 671   UpdateVersionStorageInfo();
 672
 673   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
 674               cf_name_, mutable_cf_options_, vstorage_.get(), &log_buffer_));
 675   ASSERT_TRUE(compaction.get() != nullptr);
 676   ASSERT_EQ(2U, compaction->num_input_levels());
 677   ASSERT_EQ(2U, compaction->num_input_files(0));
 678   ASSERT_EQ(3U, compaction->num_input_files(1));
 679   ASSERT_EQ(1U, compaction->input(0, 0)->fd.GetNumber());
 680   ASSERT_EQ(2U, compaction->input(0, 1)->fd.GetNumber());
 681   ASSERT_EQ(3U, compaction->input(1, 0)->fd.GetNumber());
 682   ASSERT_EQ(4U, compaction->input(1, 1)->fd.GetNumber());
 683   ASSERT_EQ(5U, compaction->input(1, 2)->fd.GetNumber());
 684 }
 685
 686 TEST_F(CompactionPickerTest, OverlappingUserKeys3) {
 687   NewVersionStorage(6, kCompactionStyleLevel);
 688   // Chain of overlapping user key ranges (forces ExpandWhileOverlapping() to
 689   // expand multiple times)
 690   Add(1, 1U, "100", "150", 1U);
 691   Add(1, 2U, "150", "200", 1U, 0, 0);
 692   Add(1, 3U, "200", "250", 1000000000U, 0, 0);
 693   Add(1, 4U, "250", "300", 1U, 0, 0);
 694   Add(1, 5U, "300", "350", 1U, 0, 0);
 695   // Output level overlaps with the beginning and the end of the chain
 696   Add(2, 6U, "050", "100", 1U);
 697   Add(2, 7U, "350", "400", 1U);
 698   UpdateVersionStorageInfo();
 699
 700   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
 701               cf_name_, mutable_cf_options_, vstorage_.get(), &log_buffer_));
 702   ASSERT_TRUE(compaction.get() != nullptr);
 703   ASSERT_EQ(2U, compaction->num_input_levels());
 704   ASSERT_EQ(5U, compaction->num_input_files(0));
 705   ASSERT_EQ(2U, compaction->num_input_files(1));
 706   ASSERT_EQ(1U, compaction->input(0, 0)->fd.GetNumber());
 707   ASSERT_EQ(2U, compaction->input(0, 1)->fd.GetNumber());
 708   ASSERT_EQ(3U, compaction->input(0, 2)->fd.GetNumber());
 709   ASSERT_EQ(4U, compaction->input(0, 3)->fd.GetNumber());
 710   ASSERT_EQ(5U, compaction->input(0, 4)->fd.GetNumber());
 711   ASSERT_EQ(6U, compaction->input(1, 0)->fd.GetNumber());
 712   ASSERT_EQ(7U, compaction->input(1, 1)->fd.GetNumber());
 713 }
 714
 715 TEST_F(CompactionPickerTest, OverlappingUserKeys4) {
 716   NewVersionStorage(6, kCompactionStyleLevel);
 717   mutable_cf_options_.max_bytes_for_level_base = 1000000;
 718
 719   Add(1, 1U, "100", "150", 1U);
 720   Add(1, 2U, "150", "199", 1U, 0, 0);
 721   Add(1, 3U, "200", "250", 1100000U, 0, 0);
 722   Add(1, 4U, "251", "300", 1U, 0, 0);
 723   Add(1, 5U, "300", "350", 1U, 0, 0);
 724
 725   Add(2, 6U, "100", "115", 1U);
 726   Add(2, 7U, "125", "325", 1U);
 727   Add(2, 8U, "350", "400", 1U);
 728   UpdateVersionStorageInfo();
 729
 730   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
 731       cf_name_, mutable_cf_options_, vstorage_.get(), &log_buffer_));
 732   ASSERT_TRUE(compaction.get() != nullptr);
 733   ASSERT_EQ(2U, compaction->num_input_levels());
 734   ASSERT_EQ(1U, compaction->num_input_files(0));
 735   ASSERT_EQ(1U, compaction->num_input_files(1));
 736   ASSERT_EQ(3U, compaction->input(0, 0)->fd.GetNumber());
 737   ASSERT_EQ(7U, compaction->input(1, 0)->fd.GetNumber());
 738 }
 739
 740 TEST_F(CompactionPickerTest, OverlappingUserKeys5) {
 741   NewVersionStorage(6, kCompactionStyleLevel);
 742   // Overlapping user keys on same level and output level
 743   Add(1, 1U, "200", "400", 1000000000U);
 744   Add(1, 2U, "400", "500", 1U, 0, 0);
 745   Add(2, 3U, "000", "100", 1U);
 746   Add(2, 4U, "100", "600", 1U, 0, 0);
 747   Add(2, 5U, "600", "700", 1U, 0, 0);
 748
 749   vstorage_->LevelFiles(2)[2]->being_compacted = true;
 750
 751   UpdateVersionStorageInfo();
 752
 753   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
 754       cf_name_, mutable_cf_options_, vstorage_.get(), &log_buffer_));
 755   ASSERT_TRUE(compaction.get() == nullptr);
 756 }
 757
 758 TEST_F(CompactionPickerTest, OverlappingUserKeys6) {
 759   NewVersionStorage(6, kCompactionStyleLevel);
 760   // Overlapping user keys on same level and output level
 761   Add(1, 1U, "200", "400", 1U, 0, 0);
 762   Add(1, 2U, "401", "500", 1U, 0, 0);
 763   Add(2, 3U, "000", "100", 1U);
 764   Add(2, 4U, "100", "300", 1U, 0, 0);
 765   Add(2, 5U, "305", "450", 1U, 0, 0);
 766   Add(2, 6U, "460", "600", 1U, 0, 0);
 767   Add(2, 7U, "600", "700", 1U, 0, 0);
 768
 769   vstorage_->LevelFiles(1)[0]->marked_for_compaction = true;
 770   vstorage_->LevelFiles(1)[1]->marked_for_compaction = true;
 771
 772   UpdateVersionStorageInfo();
 773
 774   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
 775       cf_name_, mutable_cf_options_, vstorage_.get(), &log_buffer_));
 776   ASSERT_TRUE(compaction.get() != nullptr);
 777   ASSERT_EQ(2U, compaction->num_input_levels());
 778   ASSERT_EQ(1U, compaction->num_input_files(0));
 779   ASSERT_EQ(3U, compaction->num_input_files(1));
 780 }
 781
 782 TEST_F(CompactionPickerTest, OverlappingUserKeys7) {
 783   NewVersionStorage(6, kCompactionStyleLevel);
 784   mutable_cf_options_.max_compaction_bytes = 100000000000u;
 785   // Overlapping user keys on same level and output level
 786   Add(1, 1U, "200", "400", 1U, 0, 0);
 787   Add(1, 2U, "401", "500", 1000000000U, 0, 0);
 788   Add(2, 3U, "100", "250", 1U);
 789   Add(2, 4U, "300", "600", 1U, 0, 0);
 790   Add(2, 5U, "600", "800", 1U, 0, 0);
 791
 792   UpdateVersionStorageInfo();
 793
 794   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
 795       cf_name_, mutable_cf_options_, vstorage_.get(), &log_buffer_));
 796   ASSERT_TRUE(compaction.get() != nullptr);
 797   ASSERT_EQ(2U, compaction->num_input_levels());
 798   ASSERT_GE(1U, compaction->num_input_files(0));
 799   ASSERT_GE(2U, compaction->num_input_files(1));
 800   // File 5 has to be included in the compaction
 801   ASSERT_EQ(5U, compaction->inputs(1)->back()->fd.GetNumber());
 802 }
 803
 804 TEST_F(CompactionPickerTest, OverlappingUserKeys8) {
 805   NewVersionStorage(6, kCompactionStyleLevel);
 806   mutable_cf_options_.max_compaction_bytes = 100000000000u;
 807   // grow the number of inputs in "level" without
 808   // changing the number of "level+1" files we pick up
 809   // Expand input level as much as possible
 810   // no overlapping case
 811   Add(1, 1U, "101", "150", 1U);
 812   Add(1, 2U, "151", "200", 1U);
 813   Add(1, 3U, "201", "300", 1000000000U);
 814   Add(1, 4U, "301", "400", 1U);
 815   Add(1, 5U, "401", "500", 1U);
 816   Add(2, 6U, "150", "200", 1U);
 817   Add(2, 7U, "200", "450", 1U, 0, 0);
 818   Add(2, 8U, "500", "600", 1U);
 819
 820   UpdateVersionStorageInfo();
 821
 822   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
 823       cf_name_, mutable_cf_options_, vstorage_.get(), &log_buffer_));
 824   ASSERT_TRUE(compaction.get() != nullptr);
 825   ASSERT_EQ(2U, compaction->num_input_levels());
 826   ASSERT_EQ(3U, compaction->num_input_files(0));
 827   ASSERT_EQ(2U, compaction->num_input_files(1));
 828   ASSERT_EQ(2U, compaction->input(0, 0)->fd.GetNumber());
 829   ASSERT_EQ(3U, compaction->input(0, 1)->fd.GetNumber());
 830   ASSERT_EQ(4U, compaction->input(0, 2)->fd.GetNumber());
 831   ASSERT_EQ(6U, compaction->input(1, 0)->fd.GetNumber());
 832   ASSERT_EQ(7U, compaction->input(1, 1)->fd.GetNumber());
 833 }
 834
 835 TEST_F(CompactionPickerTest, OverlappingUserKeys9) {
 836   NewVersionStorage(6, kCompactionStyleLevel);
 837   mutable_cf_options_.max_compaction_bytes = 100000000000u;
 838   // grow the number of inputs in "level" without
 839   // changing the number of "level+1" files we pick up
 840   // Expand input level as much as possible
 841   // overlapping case
 842   Add(1, 1U, "121", "150", 1U);
 843   Add(1, 2U, "151", "200", 1U);
 844   Add(1, 3U, "201", "300", 1000000000U);
 845   Add(1, 4U, "301", "400", 1U);
 846   Add(1, 5U, "401", "500", 1U);
 847   Add(2, 6U, "100", "120", 1U);
 848   Add(2, 7U, "150", "200", 1U);
 849   Add(2, 8U, "200", "450", 1U, 0, 0);
 850   Add(2, 9U, "501", "600", 1U);
 851
 852   UpdateVersionStorageInfo();
 853
 854   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
 855       cf_name_, mutable_cf_options_, vstorage_.get(), &log_buffer_));
 856   ASSERT_TRUE(compaction.get() != nullptr);
 857   ASSERT_EQ(2U, compaction->num_input_levels());
 858   ASSERT_EQ(5U, compaction->num_input_files(0));
 859   ASSERT_EQ(2U, compaction->num_input_files(1));
 860   ASSERT_EQ(1U, compaction->input(0, 0)->fd.GetNumber());
 861   ASSERT_EQ(2U, compaction->input(0, 1)->fd.GetNumber());
 862   ASSERT_EQ(3U, compaction->input(0, 2)->fd.GetNumber());
 863   ASSERT_EQ(4U, compaction->input(0, 3)->fd.GetNumber());
 864   ASSERT_EQ(7U, compaction->input(1, 0)->fd.GetNumber());
 865   ASSERT_EQ(8U, compaction->input(1, 1)->fd.GetNumber());
 866 }
 867
 868 TEST_F(CompactionPickerTest, OverlappingUserKeys10) {
 869   // Locked file encountered when pulling in extra input-level files with same
 870   // user keys. Verify we pick the next-best file from the same input level.
 871   NewVersionStorage(6, kCompactionStyleLevel);
 872   mutable_cf_options_.max_compaction_bytes = 100000000000u;
 873
 874   // file_number 2U is largest and thus first choice. But it overlaps with
 875   // file_number 1U which is being compacted. So instead we pick the next-
 876   // biggest file, 3U, which is eligible for compaction.
 877   Add(1 /* level */, 1U /* file_number */, "100" /* smallest */,
 878       "150" /* largest */, 1U /* file_size */);
 879   file_map_[1U].first->being_compacted = true;
 880   Add(1 /* level */, 2U /* file_number */, "150" /* smallest */,
 881       "200" /* largest */, 1000000000U /* file_size */, 0 /* smallest_seq */,
 882       0 /* largest_seq */);
 883   Add(1 /* level */, 3U /* file_number */, "201" /* smallest */,
 884       "250" /* largest */, 900000000U /* file_size */);
 885   Add(2 /* level */, 4U /* file_number */, "100" /* smallest */,
 886       "150" /* largest */, 1U /* file_size */);
 887   Add(2 /* level */, 5U /* file_number */, "151" /* smallest */,
 888       "200" /* largest */, 1U /* file_size */);
 889   Add(2 /* level */, 6U /* file_number */, "201" /* smallest */,
 890       "250" /* largest */, 1U /* file_size */);
 891
 892   UpdateVersionStorageInfo();
 893
 894   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
 895       cf_name_, mutable_cf_options_, vstorage_.get(), &log_buffer_));
 896   ASSERT_TRUE(compaction.get() != nullptr);
 897   ASSERT_EQ(2U, compaction->num_input_levels());
 898   ASSERT_EQ(1U, compaction->num_input_files(0));
 899   ASSERT_EQ(1U, compaction->num_input_files(1));
 900   ASSERT_EQ(3U, compaction->input(0, 0)->fd.GetNumber());
 901   ASSERT_EQ(6U, compaction->input(1, 0)->fd.GetNumber());
 902 }
 903
 904 TEST_F(CompactionPickerTest, OverlappingUserKeys11) {
 905   // Locked file encountered when pulling in extra output-level files with same
 906   // user keys. Expected to skip that compaction and pick the next-best choice.
 907   NewVersionStorage(6, kCompactionStyleLevel);
 908   mutable_cf_options_.max_compaction_bytes = 100000000000u;
 909
 910   // score(L1) = 3.7
 911   // score(L2) = 1.85
 912   // There is no eligible file in L1 to compact since both candidates pull in
 913   // file_number 5U, which overlaps with a file pending compaction (6U). The
 914   // first eligible compaction is from L2->L3.
 915   Add(1 /* level */, 2U /* file_number */, "151" /* smallest */,
 916       "200" /* largest */, 1000000000U /* file_size */);
 917   Add(1 /* level */, 3U /* file_number */, "201" /* smallest */,
 918       "250" /* largest */, 1U /* file_size */);
 919   Add(2 /* level */, 4U /* file_number */, "100" /* smallest */,
 920       "149" /* largest */, 5000000000U /* file_size */);
 921   Add(2 /* level */, 5U /* file_number */, "150" /* smallest */,
 922       "201" /* largest */, 1U /* file_size */);
 923   Add(2 /* level */, 6U /* file_number */, "201" /* smallest */,
 924       "249" /* largest */, 1U /* file_size */, 0 /* smallest_seq */,
 925       0 /* largest_seq */);
 926   file_map_[6U].first->being_compacted = true;
 927   Add(3 /* level */, 7U /* file_number */, "100" /* smallest */,
 928       "149" /* largest */, 1U /* file_size */);
 929
 930   UpdateVersionStorageInfo();
 931
 932   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
 933       cf_name_, mutable_cf_options_, vstorage_.get(), &log_buffer_));
 934   ASSERT_TRUE(compaction.get() != nullptr);
 935   ASSERT_EQ(2U, compaction->num_input_levels());
 936   ASSERT_EQ(1U, compaction->num_input_files(0));
 937   ASSERT_EQ(1U, compaction->num_input_files(1));
 938   ASSERT_EQ(4U, compaction->input(0, 0)->fd.GetNumber());
 939   ASSERT_EQ(7U, compaction->input(1, 0)->fd.GetNumber());
 940 }
 941
 942 TEST_F(CompactionPickerTest, NotScheduleL1IfL0WithHigherPri1) {
 943   NewVersionStorage(6, kCompactionStyleLevel);
 944   mutable_cf_options_.level0_file_num_compaction_trigger = 2;
 945   mutable_cf_options_.max_bytes_for_level_base = 900000000U;
 946
 947   // 6 L0 files, score 3.
 948   Add(0, 1U, "000", "400", 1U);
 949   Add(0, 2U, "001", "400", 1U, 0, 0);
 950   Add(0, 3U, "001", "400", 1000000000U, 0, 0);
 951   Add(0, 31U, "001", "400", 1000000000U, 0, 0);
 952   Add(0, 32U, "001", "400", 1000000000U, 0, 0);
 953   Add(0, 33U, "001", "400", 1000000000U, 0, 0);
 954
 955   // L1 total size 2GB, score 2.2. If one file being comapcted, score 1.1.
 956   Add(1, 4U, "050", "300", 1000000000U, 0, 0);
 957   file_map_[4u].first->being_compacted = true;
 958   Add(1, 5U, "301", "350", 1000000000U, 0, 0);
 959
 960   // Output level overlaps with the beginning and the end of the chain
 961   Add(2, 6U, "050", "100", 1U);
 962   Add(2, 7U, "300", "400", 1U);
 963
 964   // No compaction should be scheduled, if L0 has higher priority than L1
 965   // but L0->L1 compaction is blocked by a file in L1 being compacted.
 966   UpdateVersionStorageInfo();
 967   ASSERT_EQ(0, vstorage_->CompactionScoreLevel(0));
 968   ASSERT_EQ(1, vstorage_->CompactionScoreLevel(1));
 969   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
 970       cf_name_, mutable_cf_options_, vstorage_.get(), &log_buffer_));
 971   ASSERT_TRUE(compaction.get() == nullptr);
 972 }
 973
 974 TEST_F(CompactionPickerTest, NotScheduleL1IfL0WithHigherPri2) {
 975   NewVersionStorage(6, kCompactionStyleLevel);
 976   mutable_cf_options_.level0_file_num_compaction_trigger = 2;
 977   mutable_cf_options_.max_bytes_for_level_base = 900000000U;
 978
 979   // 6 L0 files, score 3.
 980   Add(0, 1U, "000", "400", 1U);
 981   Add(0, 2U, "001", "400", 1U, 0, 0);
 982   Add(0, 3U, "001", "400", 1000000000U, 0, 0);
 983   Add(0, 31U, "001", "400", 1000000000U, 0, 0);
 984   Add(0, 32U, "001", "400", 1000000000U, 0, 0);
 985   Add(0, 33U, "001", "400", 1000000000U, 0, 0);
 986
 987   // L1 total size 2GB, score 2.2. If one file being comapcted, score 1.1.
 988   Add(1, 4U, "050", "300", 1000000000U, 0, 0);
 989   Add(1, 5U, "301", "350", 1000000000U, 0, 0);
 990
 991   // Output level overlaps with the beginning and the end of the chain
 992   Add(2, 6U, "050", "100", 1U);
 993   Add(2, 7U, "300", "400", 1U);
 994
 995   // If no file in L1 being compacted, L0->L1 compaction will be scheduled.
 996   UpdateVersionStorageInfo();  // being_compacted flag is cleared here.
 997   ASSERT_EQ(0, vstorage_->CompactionScoreLevel(0));
 998   ASSERT_EQ(1, vstorage_->CompactionScoreLevel(1));
 999   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
1000       cf_name_, mutable_cf_options_, vstorage_.get(), &log_buffer_));
1001   ASSERT_TRUE(compaction.get() != nullptr);
1002 }
1003
1004 TEST_F(CompactionPickerTest, NotScheduleL1IfL0WithHigherPri3) {
1005   NewVersionStorage(6, kCompactionStyleLevel);
1006   mutable_cf_options_.level0_file_num_compaction_trigger = 2;
1007   mutable_cf_options_.max_bytes_for_level_base = 900000000U;
1008
1009   // 6 L0 files, score 3.
1010   Add(0, 1U, "000", "400", 1U);
1011   Add(0, 2U, "001", "400", 1U, 0, 0);
1012   Add(0, 3U, "001", "400", 1000000000U, 0, 0);
1013   Add(0, 31U, "001", "400", 1000000000U, 0, 0);
1014   Add(0, 32U, "001", "400", 1000000000U, 0, 0);
1015   Add(0, 33U, "001", "400", 1000000000U, 0, 0);
1016
1017   // L1 score more than 6.
1018   Add(1, 4U, "050", "300", 1000000000U, 0, 0);
1019   file_map_[4u].first->being_compacted = true;
1020   Add(1, 5U, "301", "350", 1000000000U, 0, 0);
1021   Add(1, 51U, "351", "400", 6000000000U, 0, 0);
1022
1023   // Output level overlaps with the beginning and the end of the chain
1024   Add(2, 6U, "050", "100", 1U);
1025   Add(2, 7U, "300", "400", 1U);
1026
1027   // If score in L1 is larger than L0, L1 compaction goes through despite
1028   // there is pending L0 compaction.
1029   UpdateVersionStorageInfo();
1030   ASSERT_EQ(1, vstorage_->CompactionScoreLevel(0));
1031   ASSERT_EQ(0, vstorage_->CompactionScoreLevel(1));
1032   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
1033       cf_name_, mutable_cf_options_, vstorage_.get(), &log_buffer_));
1034   ASSERT_TRUE(compaction.get() != nullptr);
1035 }
1036
1037 TEST_F(CompactionPickerTest, EstimateCompactionBytesNeeded1) {
1038   int num_levels = ioptions_.num_levels;
1039   ioptions_.level_compaction_dynamic_level_bytes = false;
1040   mutable_cf_options_.level0_file_num_compaction_trigger = 4;
1041   mutable_cf_options_.max_bytes_for_level_base = 1000;
1042   mutable_cf_options_.max_bytes_for_level_multiplier = 10;
1043   NewVersionStorage(num_levels, kCompactionStyleLevel);
1044   Add(0, 1U, "150", "200", 200);
1045   Add(0, 2U, "150", "200", 200);
1046   Add(0, 3U, "150", "200", 200);
1047   // Level 1 is over target by 200
1048   Add(1, 4U, "400", "500", 600);
1049   Add(1, 5U, "600", "700", 600);
1050   // Level 2 is less than target 10000 even added size of level 1
1051   // Size ratio of L2/L1 is 9600 / 1200 = 8
1052   Add(2, 6U, "150", "200", 2500);
1053   Add(2, 7U, "201", "210", 2000);
1054   Add(2, 8U, "300", "310", 2600);
1055   Add(2, 9U, "400", "500", 2500);
1056   // Level 3 exceeds target 100,000 of 1000
1057   Add(3, 10U, "400", "500", 101000);
1058   // Level 4 exceeds target 1,000,000 by 900 after adding size from level 3
1059   // Size ratio L4/L3 is 9.9
1060   // After merge from L3, L4 size is 1000900
1061   Add(4, 11U, "400", "500", 999900);
1062   Add(5, 11U, "400", "500", 8007200);
1063
1064   UpdateVersionStorageInfo();
1065
1066   ASSERT_EQ(200u * 9u + 10900u + 900u * 9,
1067             vstorage_->estimated_compaction_needed_bytes());
1068 }
1069
1070 TEST_F(CompactionPickerTest, EstimateCompactionBytesNeeded2) {
1071   int num_levels = ioptions_.num_levels;
1072   ioptions_.level_compaction_dynamic_level_bytes = false;
1073   mutable_cf_options_.level0_file_num_compaction_trigger = 3;
1074   mutable_cf_options_.max_bytes_for_level_base = 1000;
1075   mutable_cf_options_.max_bytes_for_level_multiplier = 10;
1076   NewVersionStorage(num_levels, kCompactionStyleLevel);
1077   Add(0, 1U, "150", "200", 200);
1078   Add(0, 2U, "150", "200", 200);
1079   Add(0, 4U, "150", "200", 200);
1080   Add(0, 5U, "150", "200", 200);
1081   Add(0, 6U, "150", "200", 200);
1082   // Level 1 size will be 1400 after merging with L0
1083   Add(1, 7U, "400", "500", 200);
1084   Add(1, 8U, "600", "700", 200);
1085   // Level 2 is less than target 10000 even added size of level 1
1086   Add(2, 9U, "150", "200", 9100);
1087   // Level 3 over the target, but since level 4 is empty, we assume it will be
1088   // a trivial move.
1089   Add(3, 10U, "400", "500", 101000);
1090
1091   UpdateVersionStorageInfo();
1092
1093   // estimated L1->L2 merge: 400 * (9100.0 / 1400.0 + 1.0)
1094   ASSERT_EQ(1400u + 3000u, vstorage_->estimated_compaction_needed_bytes());
1095 }
1096
1097 TEST_F(CompactionPickerTest, EstimateCompactionBytesNeeded3) {
1098   int num_levels = ioptions_.num_levels;
1099   ioptions_.level_compaction_dynamic_level_bytes = false;
1100   mutable_cf_options_.level0_file_num_compaction_trigger = 3;
1101   mutable_cf_options_.max_bytes_for_level_base = 1000;
1102   mutable_cf_options_.max_bytes_for_level_multiplier = 10;
1103   NewVersionStorage(num_levels, kCompactionStyleLevel);
1104   Add(0, 1U, "150", "200", 2000);
1105   Add(0, 2U, "150", "200", 2000);
1106   Add(0, 4U, "150", "200", 2000);
1107   Add(0, 5U, "150", "200", 2000);
1108   Add(0, 6U, "150", "200", 1000);
1109   // Level 1 size will be 10000 after merging with L0
1110   Add(1, 7U, "400", "500", 500);
1111   Add(1, 8U, "600", "700", 500);
1112
1113   Add(2, 9U, "150", "200", 10000);
1114
1115   UpdateVersionStorageInfo();
1116
1117   ASSERT_EQ(10000u + 18000u, vstorage_->estimated_compaction_needed_bytes());
1118 }
1119
1120 TEST_F(CompactionPickerTest, EstimateCompactionBytesNeededDynamicLevel) {
1121   int num_levels = ioptions_.num_levels;
1122   ioptions_.level_compaction_dynamic_level_bytes = true;
1123   mutable_cf_options_.level0_file_num_compaction_trigger = 3;
1124   mutable_cf_options_.max_bytes_for_level_base = 1000;
1125   mutable_cf_options_.max_bytes_for_level_multiplier = 10;
1126   NewVersionStorage(num_levels, kCompactionStyleLevel);
1127
1128   // Set Last level size 50000
1129   // num_levels - 1 target 5000
1130   // num_levels - 2 is base level with target 1000 (rounded up to
1131   // max_bytes_for_level_base).
1132   Add(num_levels - 1, 10U, "400", "500", 50000);
1133
1134   Add(0, 1U, "150", "200", 200);
1135   Add(0, 2U, "150", "200", 200);
1136   Add(0, 4U, "150", "200", 200);
1137   Add(0, 5U, "150", "200", 200);
1138   Add(0, 6U, "150", "200", 200);
1139   // num_levels - 3 is over target by 100 + 1000
1140   Add(num_levels - 3, 7U, "400", "500", 550);
1141   Add(num_levels - 3, 8U, "600", "700", 550);
1142   // num_levels - 2 is over target by 1100 + 200
1143   Add(num_levels - 2, 9U, "150", "200", 5200);
1144
1145   UpdateVersionStorageInfo();
1146
1147   // Merging to the second last level: (5200 / 2100 + 1) * 1100
1148   // Merging to the last level: (50000 / 6300 + 1) * 1300
1149   ASSERT_EQ(2100u + 3823u + 11617u,
1150             vstorage_->estimated_compaction_needed_bytes());
1151 }
1152
1153 TEST_F(CompactionPickerTest, IsBottommostLevelTest) {
1154   // case 1: Higher levels are empty
1155   NewVersionStorage(6, kCompactionStyleLevel);
1156   Add(0, 1U, "a", "m");
1157   Add(0, 2U, "c", "z");
1158   Add(1, 3U, "d", "e");
1159   Add(1, 4U, "l", "p");
1160   Add(2, 5U, "g", "i");
1161   Add(2, 6U, "x", "z");
1162   UpdateVersionStorageInfo();
1163   SetCompactionInputFilesLevels(2, 1);
1164   AddToCompactionFiles(3U);
1165   AddToCompactionFiles(5U);
1166   bool result =
1167       Compaction::TEST_IsBottommostLevel(2, vstorage_.get(), input_files_);
1168   ASSERT_TRUE(result);
1169
1170   // case 2: Higher levels have no overlap
1171   NewVersionStorage(6, kCompactionStyleLevel);
1172   Add(0, 1U, "a", "m");
1173   Add(0, 2U, "c", "z");
1174   Add(1, 3U, "d", "e");
1175   Add(1, 4U, "l", "p");
1176   Add(2, 5U, "g", "i");
1177   Add(2, 6U, "x", "z");
1178   Add(3, 7U, "k", "p");
1179   Add(3, 8U, "t", "w");
1180   Add(4, 9U, "a", "b");
1181   Add(5, 10U, "c", "cc");
1182   UpdateVersionStorageInfo();
1183   SetCompactionInputFilesLevels(2, 1);
1184   AddToCompactionFiles(3U);
1185   AddToCompactionFiles(5U);
1186   result = Compaction::TEST_IsBottommostLevel(2, vstorage_.get(), input_files_);
1187   ASSERT_TRUE(result);
1188
1189   // case 3.1: Higher levels (level 3) have overlap
1190   NewVersionStorage(6, kCompactionStyleLevel);
1191   Add(0, 1U, "a", "m");
1192   Add(0, 2U, "c", "z");
1193   Add(1, 3U, "d", "e");
1194   Add(1, 4U, "l", "p");
1195   Add(2, 5U, "g", "i");
1196   Add(2, 6U, "x", "z");
1197   Add(3, 7U, "e", "g");
1198   Add(3, 8U, "h", "k");
1199   Add(4, 9U, "a", "b");
1200   Add(5, 10U, "c", "cc");
1201   UpdateVersionStorageInfo();
1202   SetCompactionInputFilesLevels(2, 1);
1203   AddToCompactionFiles(3U);
1204   AddToCompactionFiles(5U);
1205   result = Compaction::TEST_IsBottommostLevel(2, vstorage_.get(), input_files_);
1206   ASSERT_FALSE(result);
1207
1208   // case 3.2: Higher levels (level 5) have overlap
1209   DeleteVersionStorage();
1210   NewVersionStorage(6, kCompactionStyleLevel);
1211   Add(0, 1U, "a", "m");
1212   Add(0, 2U, "c", "z");
1213   Add(1, 3U, "d", "e");
1214   Add(1, 4U, "l", "p");
1215   Add(2, 5U, "g", "i");
1216   Add(2, 6U, "x", "z");
1217   Add(3, 7U, "j", "k");
1218   Add(3, 8U, "l", "m");
1219   Add(4, 9U, "a", "b");
1220   Add(5, 10U, "c", "cc");
1221   Add(5, 11U, "h", "k");
1222   Add(5, 12U, "y", "yy");
1223   Add(5, 13U, "z", "zz");
1224   UpdateVersionStorageInfo();
1225   SetCompactionInputFilesLevels(2, 1);
1226   AddToCompactionFiles(3U);
1227   AddToCompactionFiles(5U);
1228   result = Compaction::TEST_IsBottommostLevel(2, vstorage_.get(), input_files_);
1229   ASSERT_FALSE(result);
1230
1231   // case 3.3: Higher levels (level 5) have overlap, but it's only overlapping
1232   // one key ("d")
1233   NewVersionStorage(6, kCompactionStyleLevel);
1234   Add(0, 1U, "a", "m");
1235   Add(0, 2U, "c", "z");
1236   Add(1, 3U, "d", "e");
1237   Add(1, 4U, "l", "p");
1238   Add(2, 5U, "g", "i");
1239   Add(2, 6U, "x", "z");
1240   Add(3, 7U, "j", "k");
1241   Add(3, 8U, "l", "m");
1242   Add(4, 9U, "a", "b");
1243   Add(5, 10U, "c", "cc");
1244   Add(5, 11U, "ccc", "d");
1245   Add(5, 12U, "y", "yy");
1246   Add(5, 13U, "z", "zz");
1247   UpdateVersionStorageInfo();
1248   SetCompactionInputFilesLevels(2, 1);
1249   AddToCompactionFiles(3U);
1250   AddToCompactionFiles(5U);
1251   result = Compaction::TEST_IsBottommostLevel(2, vstorage_.get(), input_files_);
1252   ASSERT_FALSE(result);
1253
1254   // Level 0 files overlap
1255   NewVersionStorage(6, kCompactionStyleLevel);
1256   Add(0, 1U, "s", "t");
1257   Add(0, 2U, "a", "m");
1258   Add(0, 3U, "b", "z");
1259   Add(0, 4U, "e", "f");
1260   Add(5, 10U, "y", "z");
1261   UpdateVersionStorageInfo();
1262   SetCompactionInputFilesLevels(1, 0);
1263   AddToCompactionFiles(1U);
1264   AddToCompactionFiles(2U);
1265   AddToCompactionFiles(3U);
1266   AddToCompactionFiles(4U);
1267   result = Compaction::TEST_IsBottommostLevel(2, vstorage_.get(), input_files_);
1268   ASSERT_FALSE(result);
1269
1270   // Level 0 files don't overlap
1271   NewVersionStorage(6, kCompactionStyleLevel);
1272   Add(0, 1U, "s", "t");
1273   Add(0, 2U, "a", "m");
1274   Add(0, 3U, "b", "k");
1275   Add(0, 4U, "e", "f");
1276   Add(5, 10U, "y", "z");
1277   UpdateVersionStorageInfo();
1278   SetCompactionInputFilesLevels(1, 0);
1279   AddToCompactionFiles(1U);
1280   AddToCompactionFiles(2U);
1281   AddToCompactionFiles(3U);
1282   AddToCompactionFiles(4U);
1283   result = Compaction::TEST_IsBottommostLevel(2, vstorage_.get(), input_files_);
1284   ASSERT_TRUE(result);
1285
1286   // Level 1 files overlap
1287   NewVersionStorage(6, kCompactionStyleLevel);
1288   Add(0, 1U, "s", "t");
1289   Add(0, 2U, "a", "m");
1290   Add(0, 3U, "b", "k");
1291   Add(0, 4U, "e", "f");
1292   Add(1, 5U, "a", "m");
1293   Add(1, 6U, "n", "o");
1294   Add(1, 7U, "w", "y");
1295   Add(5, 10U, "y", "z");
1296   UpdateVersionStorageInfo();
1297   SetCompactionInputFilesLevels(2, 0);
1298   AddToCompactionFiles(1U);
1299   AddToCompactionFiles(2U);
1300   AddToCompactionFiles(3U);
1301   AddToCompactionFiles(4U);
1302   AddToCompactionFiles(5U);
1303   AddToCompactionFiles(6U);
1304   AddToCompactionFiles(7U);
1305   result = Compaction::TEST_IsBottommostLevel(2, vstorage_.get(), input_files_);
1306   ASSERT_FALSE(result);
1307
1308   DeleteVersionStorage();
1309 }
1310
1311 TEST_F(CompactionPickerTest, MaxCompactionBytesHit) {
1312   mutable_cf_options_.max_bytes_for_level_base = 1000000u;
1313   mutable_cf_options_.max_compaction_bytes = 800000u;
1314   ioptions_.level_compaction_dynamic_level_bytes = false;
1315   NewVersionStorage(6, kCompactionStyleLevel);
1316   // A compaction should be triggered and pick file 2 and 5.
1317   // It can expand because adding file 1 and 3, the compaction size will
1318   // exceed mutable_cf_options_.max_bytes_for_level_base.
1319   Add(1, 1U, "100", "150", 300000U);
1320   Add(1, 2U, "151", "200", 300001U, 0, 0);
1321   Add(1, 3U, "201", "250", 300000U, 0, 0);
1322   Add(1, 4U, "251", "300", 300000U, 0, 0);
1323   Add(2, 5U, "100", "256", 1U);
1324   UpdateVersionStorageInfo();
1325
1326   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
1327       cf_name_, mutable_cf_options_, vstorage_.get(), &log_buffer_));
1328   ASSERT_TRUE(compaction.get() != nullptr);
1329   ASSERT_EQ(2U, compaction->num_input_levels());
1330   ASSERT_EQ(1U, compaction->num_input_files(0));
1331   ASSERT_EQ(1U, compaction->num_input_files(1));
1332   ASSERT_EQ(2U, compaction->input(0, 0)->fd.GetNumber());
1333   ASSERT_EQ(5U, compaction->input(1, 0)->fd.GetNumber());
1334 }
1335
1336 TEST_F(CompactionPickerTest, MaxCompactionBytesNotHit) {
1337   mutable_cf_options_.max_bytes_for_level_base = 800000u;
1338   mutable_cf_options_.max_compaction_bytes = 1000000u;
1339   ioptions_.level_compaction_dynamic_level_bytes = false;
1340   NewVersionStorage(6, kCompactionStyleLevel);
1341   // A compaction should be triggered and pick file 2 and 5.
1342   // and it expands to file 1 and 3 too.
1343   Add(1, 1U, "100", "150", 300000U);
1344   Add(1, 2U, "151", "200", 300001U, 0, 0);
1345   Add(1, 3U, "201", "250", 300000U, 0, 0);
1346   Add(1, 4U, "251", "300", 300000U, 0, 0);
1347   Add(2, 5U, "000", "251", 1U);
1348   UpdateVersionStorageInfo();
1349
1350   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
1351       cf_name_, mutable_cf_options_, vstorage_.get(), &log_buffer_));
1352   ASSERT_TRUE(compaction.get() != nullptr);
1353   ASSERT_EQ(2U, compaction->num_input_levels());
1354   ASSERT_EQ(3U, compaction->num_input_files(0));
1355   ASSERT_EQ(1U, compaction->num_input_files(1));
1356   ASSERT_EQ(1U, compaction->input(0, 0)->fd.GetNumber());
1357   ASSERT_EQ(2U, compaction->input(0, 1)->fd.GetNumber());
1358   ASSERT_EQ(3U, compaction->input(0, 2)->fd.GetNumber());
1359   ASSERT_EQ(5U, compaction->input(1, 0)->fd.GetNumber());
1360 }
1361
1362 TEST_F(CompactionPickerTest, IsTrivialMoveOn) {
1363   mutable_cf_options_.max_bytes_for_level_base = 10000u;
1364   mutable_cf_options_.max_compaction_bytes = 10001u;
1365   ioptions_.level_compaction_dynamic_level_bytes = false;
1366   NewVersionStorage(6, kCompactionStyleLevel);
1367   // A compaction should be triggered and pick file 2
1368   Add(1, 1U, "100", "150", 3000U);
1369   Add(1, 2U, "151", "200", 3001U);
1370   Add(1, 3U, "201", "250", 3000U);
1371   Add(1, 4U, "251", "300", 3000U);
1372
1373   Add(3, 5U, "120", "130", 7000U);
1374   Add(3, 6U, "170", "180", 7000U);
1375   Add(3, 5U, "220", "230", 7000U);
1376   Add(3, 5U, "270", "280", 7000U);
1377   UpdateVersionStorageInfo();
1378
1379   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
1380     cf_name_, mutable_cf_options_, vstorage_.get(), &log_buffer_));
1381   ASSERT_TRUE(compaction.get() != nullptr);
1382   ASSERT_TRUE(compaction->IsTrivialMove());
1383 }
1384
1385 TEST_F(CompactionPickerTest, IsTrivialMoveOff) {
1386   mutable_cf_options_.max_bytes_for_level_base = 1000000u;
1387   mutable_cf_options_.max_compaction_bytes = 10000u;
1388   ioptions_.level_compaction_dynamic_level_bytes = false;
1389   NewVersionStorage(6, kCompactionStyleLevel);
1390   // A compaction should be triggered and pick all files from level 1
1391   Add(1, 1U, "100", "150", 300000U, 0, 0);
1392   Add(1, 2U, "150", "200", 300000U, 0, 0);
1393   Add(1, 3U, "200", "250", 300000U, 0, 0);
1394   Add(1, 4U, "250", "300", 300000U, 0, 0);
1395
1396   Add(3, 5U, "120", "130", 6000U);
1397   Add(3, 6U, "140", "150", 6000U);
1398   UpdateVersionStorageInfo();
1399
1400   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
1401     cf_name_, mutable_cf_options_, vstorage_.get(), &log_buffer_));
1402   ASSERT_TRUE(compaction.get() != nullptr);
1403   ASSERT_FALSE(compaction->IsTrivialMove());
1404 }
1405
1406 TEST_F(CompactionPickerTest, CacheNextCompactionIndex) {
1407   NewVersionStorage(6, kCompactionStyleLevel);
1408   mutable_cf_options_.max_compaction_bytes = 100000000000u;
1409
1410   Add(1 /* level */, 1U /* file_number */, "100" /* smallest */,
1411       "149" /* largest */, 1000000000U /* file_size */);
1412   file_map_[1U].first->being_compacted = true;
1413   Add(1 /* level */, 2U /* file_number */, "150" /* smallest */,
1414       "199" /* largest */, 900000000U /* file_size */);
1415   Add(1 /* level */, 3U /* file_number */, "200" /* smallest */,
1416       "249" /* largest */, 800000000U /* file_size */);
1417   Add(1 /* level */, 4U /* file_number */, "250" /* smallest */,
1418       "299" /* largest */, 700000000U /* file_size */);
1419   Add(2 /* level */, 5U /* file_number */, "150" /* smallest */,
1420       "199" /* largest */, 1U /* file_size */);
1421   file_map_[5U].first->being_compacted = true;
1422
1423   UpdateVersionStorageInfo();
1424
1425   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
1426       cf_name_, mutable_cf_options_, vstorage_.get(), &log_buffer_));
1427   ASSERT_TRUE(compaction.get() != nullptr);
1428   ASSERT_EQ(1U, compaction->num_input_levels());
1429   ASSERT_EQ(1U, compaction->num_input_files(0));
1430   ASSERT_EQ(0U, compaction->num_input_files(1));
1431   ASSERT_EQ(3U, compaction->input(0, 0)->fd.GetNumber());
1432   ASSERT_EQ(2, vstorage_->NextCompactionIndex(1 /* level */));
1433
1434   compaction.reset(level_compaction_picker.PickCompaction(
1435       cf_name_, mutable_cf_options_, vstorage_.get(), &log_buffer_));
1436   ASSERT_TRUE(compaction.get() != nullptr);
1437   ASSERT_EQ(1U, compaction->num_input_levels());
1438   ASSERT_EQ(1U, compaction->num_input_files(0));
1439   ASSERT_EQ(0U, compaction->num_input_files(1));
1440   ASSERT_EQ(4U, compaction->input(0, 0)->fd.GetNumber());
1441   ASSERT_EQ(3, vstorage_->NextCompactionIndex(1 /* level */));
1442
1443   compaction.reset(level_compaction_picker.PickCompaction(
1444       cf_name_, mutable_cf_options_, vstorage_.get(), &log_buffer_));
1445   ASSERT_TRUE(compaction.get() == nullptr);
1446   ASSERT_EQ(4, vstorage_->NextCompactionIndex(1 /* level */));
1447 }
1448
1449 }  // namespace rocksdb
1450
1451 int main(int argc, char** argv) {
1452   ::testing::InitGoogleTest(&argc, argv);
1453   return RUN_ALL_TESTS();
1454 }