db_universal_compaction_test.cc

//  Copyright (c) 2011-present, Facebook, Inc.  All rights reserved.
//  This source code is licensed under both the GPLv2 (found in the
//  COPYING file in the root directory) and Apache 2.0 License
//  (found in the LICENSE.Apache file in the root directory).
//
// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file. See the AUTHORS file for names of contributors.

#include <string>

#include "db/db_test_util.h"
#include "port/stack_trace.h"
#include "rocksdb/utilities/table_properties_collectors.h"
#include "test_util/mock_time_env.h"
#include "test_util/sync_point.h"
#include "test_util/testutil.h"
#include "util/random.h"

namespace ROCKSDB_NAMESPACE {

static std::string CompressibleString(Random* rnd, int len) {
  std::string r;
  test::CompressibleString(rnd, 0.8, len, &r);
  return r;
}

class DBTestUniversalCompactionBase
    : public DBTestBase,
      public ::testing::WithParamInterface<std::tuple<int, bool>> {
 public:
  explicit DBTestUniversalCompactionBase(const std::string& path)
      : DBTestBase(path, /*env_do_fsync=*/false) {}
  void SetUp() override {
    num_levels_ = std::get<0>(GetParam());
    exclusive_manual_compaction_ = std::get<1>(GetParam());
  }
  int num_levels_;
  bool exclusive_manual_compaction_;
};

class DBTestUniversalCompaction : public DBTestUniversalCompactionBase {
 public:
  DBTestUniversalCompaction()
      : DBTestUniversalCompactionBase("/db_universal_compaction_test") {}
};

class DBTestUniversalCompaction2 : public DBTestBase {
 public:
  DBTestUniversalCompaction2()
      : DBTestBase("db_universal_compaction_test2", /*env_do_fsync=*/false) {}
};

namespace {
void VerifyCompactionResult(
    const ColumnFamilyMetaData& cf_meta,
    const std::set<std::string>& overlapping_file_numbers) {
#ifndef NDEBUG
  for (auto& level : cf_meta.levels) {
    for (auto& file : level.files) {
      assert(overlapping_file_numbers.find(file.name) ==
             overlapping_file_numbers.end());
    }
  }
#endif
}

class KeepFilter : public CompactionFilter {
 public:
  bool Filter(int /*level*/, const Slice& /*key*/, const Slice& /*value*/,
              std::string* /*new_value*/,
              bool* /*value_changed*/) const override {
    return false;
  }

  const char* Name() const override { return "KeepFilter"; }
};

class KeepFilterFactory : public CompactionFilterFactory {
 public:
  explicit KeepFilterFactory(bool check_context = false)
      : check_context_(check_context) {}

  std::unique_ptr<CompactionFilter> CreateCompactionFilter(
      const CompactionFilter::Context& context) override {
    if (check_context_) {
      EXPECT_EQ(expect_full_compaction_.load(), context.is_full_compaction);
      EXPECT_EQ(expect_manual_compaction_.load(), context.is_manual_compaction);
    }
    return std::unique_ptr<CompactionFilter>(new KeepFilter());
  }

  const char* Name() const override { return "KeepFilterFactory"; }
  bool check_context_;
  std::atomic_bool expect_full_compaction_;
  std::atomic_bool expect_manual_compaction_;
};
}  // anonymous namespace

// Make sure we don't trigger a problem if the trigger condtion is given
// to be 0, which is invalid.
TEST_P(DBTestUniversalCompaction, UniversalCompactionSingleSortedRun) {
  Options options = CurrentOptions();

  options.compaction_style = kCompactionStyleUniversal;
  options.num_levels = num_levels_;
  // Config universal compaction to always compact to one single sorted run.
  options.level0_file_num_compaction_trigger = 0;
  options.compaction_options_universal.size_ratio = 10;
  options.compaction_options_universal.min_merge_width = 2;
  options.compaction_options_universal.max_size_amplification_percent = 0;

  options.write_buffer_size = 105 << 10;  // 105KB
  options.arena_block_size = 4 << 10;
  options.target_file_size_base = 32 << 10;  // 32KB
  // trigger compaction if there are >= 4 files
  KeepFilterFactory* filter = new KeepFilterFactory(true);
  filter->expect_manual_compaction_.store(false);
  options.compaction_filter_factory.reset(filter);

  DestroyAndReopen(options);
  ASSERT_EQ(1, db_->GetOptions().level0_file_num_compaction_trigger);

  Random rnd(301);
  int key_idx = 0;

  filter->expect_full_compaction_.store(true);

  for (int num = 0; num < 16; num++) {
    // Write 100KB file. And immediately it should be compacted to one file.
    GenerateNewFile(&rnd, &key_idx);
    ASSERT_OK(dbfull()->TEST_WaitForCompact());
    ASSERT_EQ(NumSortedRuns(0), 1);
  }
  ASSERT_OK(Put(Key(key_idx), ""));
  ASSERT_OK(dbfull()->TEST_WaitForCompact());
  ASSERT_EQ(NumSortedRuns(0), 1);
}

TEST_P(DBTestUniversalCompaction, OptimizeFiltersForHits) {
  Options options = CurrentOptions();
  options.compaction_style = kCompactionStyleUniversal;
  options.compaction_options_universal.size_ratio = 5;
  options.num_levels = num_levels_;
  options.write_buffer_size = 105 << 10;  // 105KB
  options.arena_block_size = 4 << 10;
  options.target_file_size_base = 32 << 10;  // 32KB
  // trigger compaction if there are >= 4 files
  options.level0_file_num_compaction_trigger = 4;
  BlockBasedTableOptions bbto;
  bbto.cache_index_and_filter_blocks = true;
  bbto.filter_policy.reset(NewBloomFilterPolicy(10, false));
  bbto.whole_key_filtering = true;
  options.table_factory.reset(NewBlockBasedTableFactory(bbto));
  options.optimize_filters_for_hits = true;
  options.statistics = ROCKSDB_NAMESPACE::CreateDBStatistics();
  options.memtable_factory.reset(test::NewSpecialSkipListFactory(3));

  DestroyAndReopen(options);

  // block compaction from happening
  env_->SetBackgroundThreads(1, Env::LOW);
  test::SleepingBackgroundTask sleeping_task_low;
  env_->Schedule(&test::SleepingBackgroundTask::DoSleepTask, &sleeping_task_low,
                 Env::Priority::LOW);

  for (int num = 0; num < options.level0_file_num_compaction_trigger; num++) {
    ASSERT_OK(Put(Key(num * 10), "val"));
    if (num) {
      ASSERT_OK(dbfull()->TEST_WaitForFlushMemTable());
    }
    ASSERT_OK(Put(Key(30 + num * 10), "val"));
    ASSERT_OK(Put(Key(60 + num * 10), "val"));
  }
  ASSERT_OK(Put("", ""));
  ASSERT_OK(dbfull()->TEST_WaitForFlushMemTable());

  // Query set of non existing keys
  for (int i = 5; i < 90; i += 10) {
    ASSERT_EQ(Get(Key(i)), "NOT_FOUND");
  }

  // Make sure bloom filter is used at least once.
  ASSERT_GT(TestGetTickerCount(options, BLOOM_FILTER_USEFUL), 0);
  auto prev_counter = TestGetTickerCount(options, BLOOM_FILTER_USEFUL);

  // Make sure bloom filter is used for all but the last L0 file when looking
  // up a non-existent key that's in the range of all L0 files.
  ASSERT_EQ(Get(Key(35)), "NOT_FOUND");
  ASSERT_EQ(prev_counter + NumTableFilesAtLevel(0) - 1,
            TestGetTickerCount(options, BLOOM_FILTER_USEFUL));
  prev_counter = TestGetTickerCount(options, BLOOM_FILTER_USEFUL);

  // Unblock compaction and wait it for happening.
  sleeping_task_low.WakeUp();
  ASSERT_OK(dbfull()->TEST_WaitForCompact());

  // The same queries will not trigger bloom filter
  for (int i = 5; i < 90; i += 10) {
    ASSERT_EQ(Get(Key(i)), "NOT_FOUND");
  }
  ASSERT_EQ(prev_counter, TestGetTickerCount(options, BLOOM_FILTER_USEFUL));
}

// TODO(kailiu) The tests on UniversalCompaction has some issues:
//  1. A lot of magic numbers ("11" or "12").
//  2. Made assumption on the memtable flush conditions, which may change from
//     time to time.
TEST_P(DBTestUniversalCompaction, UniversalCompactionTrigger) {
  Options options;
  options.compaction_style = kCompactionStyleUniversal;
  options.compaction_options_universal.size_ratio = 5;
  options.num_levels = num_levels_;
  options.write_buffer_size = 105 << 10;  // 105KB
  options.arena_block_size = 4 << 10;
  // trigger compaction if there are >= 4 files
  options.level0_file_num_compaction_trigger = 4;
  KeepFilterFactory* filter = new KeepFilterFactory(true);
  filter->expect_manual_compaction_.store(false);
  options.compaction_filter_factory.reset(filter);

  options = CurrentOptions(options);
  DestroyAndReopen(options);
  CreateAndReopenWithCF({"pikachu"}, options);

  ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->SetCallBack(
      "DBTestWritableFile.GetPreallocationStatus", [&](void* arg) {
        ASSERT_TRUE(arg != nullptr);
        size_t preallocation_size = *(static_cast<size_t*>(arg));
        if (num_levels_ > 3) {
          ASSERT_LE(preallocation_size, options.target_file_size_base * 1.1);
        }
      });
  ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->EnableProcessing();

  Random rnd(301);
  int key_idx = 0;

  filter->expect_full_compaction_.store(true);
  // Stage 1:
  //   Generate a set of files at level 0, but don't trigger level-0
  //   compaction.
  for (int num = 0; num < options.level0_file_num_compaction_trigger - 1;
       num++) {
    // Write 100KB
    GenerateNewFile(1, &rnd, &key_idx);
  }

  // Generate one more file at level-0, which should trigger level-0
  // compaction.
  GenerateNewFile(1, &rnd, &key_idx);
  // Suppose each file flushed from mem table has size 1. Now we compact
  // (level0_file_num_compaction_trigger+1)=4 files and should have a big
  // file of size 4.
  ASSERT_EQ(NumSortedRuns(1), 1);

  // Stage 2:
  //   Now we have one file at level 0, with size 4. We also have some data in
  //   mem table. Let's continue generating new files at level 0, but don't
  //   trigger level-0 compaction.
  //   First, clean up memtable before inserting new data. This will generate
  //   a level-0 file, with size around 0.4 (according to previously written
  //   data amount).
  filter->expect_full_compaction_.store(false);
  ASSERT_OK(Flush(1));
  for (int num = 0; num < options.level0_file_num_compaction_trigger - 3;
       num++) {
    GenerateNewFile(1, &rnd, &key_idx);
    ASSERT_EQ(NumSortedRuns(1), num + 3);
  }

  // Generate one more file at level-0, which should trigger level-0
  // compaction.
  GenerateNewFile(1, &rnd, &key_idx);
  // Before compaction, we have 4 files at level 0, with size 4, 0.4, 1, 1.
  // After compaction, we should have 2 files, with size 4, 2.4.
  ASSERT_EQ(NumSortedRuns(1), 2);

  // Stage 3:
  //   Now we have 2 files at level 0, with size 4 and 2.4. Continue
  //   generating new files at level 0.
  for (int num = 0; num < options.level0_file_num_compaction_trigger - 3;
       num++) {
    GenerateNewFile(1, &rnd, &key_idx);
    ASSERT_EQ(NumSortedRuns(1), num + 3);
  }

  // Generate one more file at level-0, which should trigger level-0
  // compaction.
  GenerateNewFile(1, &rnd, &key_idx);
  // Before compaction, we have 4 files at level 0, with size 4, 2.4, 1, 1.
  // After compaction, we should have 3 files, with size 4, 2.4, 2.
  ASSERT_EQ(NumSortedRuns(1), 3);

  // Stage 4:
  //   Now we have 3 files at level 0, with size 4, 2.4, 2. Let's generate a
  //   new file of size 1.
  GenerateNewFile(1, &rnd, &key_idx);
  ASSERT_OK(dbfull()->TEST_WaitForCompact());
  // Level-0 compaction is triggered, but no file will be picked up.
  ASSERT_EQ(NumSortedRuns(1), 4);

  // Stage 5:
  //   Now we have 4 files at level 0, with size 4, 2.4, 2, 1. Let's generate
  //   a new file of size 1.
  filter->expect_full_compaction_.store(true);
  GenerateNewFile(1, &rnd, &key_idx);
  ASSERT_OK(dbfull()->TEST_WaitForCompact());
  // All files at level 0 will be compacted into a single one.
  ASSERT_EQ(NumSortedRuns(1), 1);

  ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->DisableProcessing();
}

TEST_P(DBTestUniversalCompaction, UniversalCompactionSizeAmplification) {
  Options options = CurrentOptions();
  options.compaction_style = kCompactionStyleUniversal;
  options.num_levels = num_levels_;
  options.write_buffer_size = 100 << 10;     // 100KB
  options.target_file_size_base = 32 << 10;  // 32KB
  options.level0_file_num_compaction_trigger = 3;
  DestroyAndReopen(options);
  CreateAndReopenWithCF({"pikachu"}, options);

  // Trigger compaction if size amplification exceeds 110%
  options.compaction_options_universal.max_size_amplification_percent = 110;
  options = CurrentOptions(options);
  ReopenWithColumnFamilies({"default", "pikachu"}, options);

  Random rnd(301);
  int key_idx = 0;

  //   Generate two files in Level 0. Both files are approx the same size.
  for (int num = 0; num < options.level0_file_num_compaction_trigger - 1;
       num++) {
    // Write 110KB (11 values, each 10K)
    for (int i = 0; i < 11; i++) {
      ASSERT_OK(Put(1, Key(key_idx), rnd.RandomString(10000)));
      key_idx++;
    }
    ASSERT_OK(dbfull()->TEST_WaitForFlushMemTable(handles_[1]));
    ASSERT_EQ(NumSortedRuns(1), num + 1);
  }
  ASSERT_EQ(NumSortedRuns(1), 2);

  // Flush whatever is remaining in memtable. This is typically
  // small, which should not trigger size ratio based compaction
  // but will instead trigger size amplification.
  ASSERT_OK(Flush(1));

  ASSERT_OK(dbfull()->TEST_WaitForCompact());

  // Verify that size amplification did occur
  ASSERT_EQ(NumSortedRuns(1), 1);
}

TEST_P(DBTestUniversalCompaction, DynamicUniversalCompactionSizeAmplification) {
  Options options = CurrentOptions();
  options.compaction_style = kCompactionStyleUniversal;
  options.num_levels = 1;
  options.write_buffer_size = 100 << 10;     // 100KB
  options.target_file_size_base = 32 << 10;  // 32KB
  options.level0_file_num_compaction_trigger = 3;
  // Initial setup of compaction_options_universal will prevent universal
  // compaction from happening
  options.compaction_options_universal.size_ratio = 100;
  options.compaction_options_universal.min_merge_width = 100;
  DestroyAndReopen(options);

  int total_picked_compactions = 0;
  int total_size_amp_compactions = 0;
  ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->SetCallBack(
      "UniversalCompactionBuilder::PickCompaction:Return", [&](void* arg) {
        if (arg) {
          total_picked_compactions++;
          Compaction* c = static_cast<Compaction*>(arg);
          if (c->compaction_reason() ==
              CompactionReason::kUniversalSizeAmplification) {
            total_size_amp_compactions++;
          }
        }
      });
  ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->EnableProcessing();

  MutableCFOptions mutable_cf_options;
  CreateAndReopenWithCF({"pikachu"}, options);

  Random rnd(301);
  int key_idx = 0;

  //   Generate two files in Level 0. Both files are approx the same size.
  for (int num = 0; num < options.level0_file_num_compaction_trigger - 1;
       num++) {
    // Write 110KB (11 values, each 10K)
    for (int i = 0; i < 11; i++) {
      ASSERT_OK(Put(1, Key(key_idx), rnd.RandomString(10000)));
      key_idx++;
    }
    ASSERT_OK(dbfull()->TEST_WaitForFlushMemTable(handles_[1]));
    ASSERT_EQ(NumSortedRuns(1), num + 1);
  }
  ASSERT_EQ(NumSortedRuns(1), 2);

  // Flush whatever is remaining in memtable. This is typically
  // small, which should not trigger size ratio based compaction
  // but could instead trigger size amplification if it's set
  // to 110.
  ASSERT_OK(Flush(1));
  ASSERT_OK(dbfull()->TEST_WaitForCompact());
  // Verify compaction did not happen
  ASSERT_EQ(NumSortedRuns(1), 3);

  // Trigger compaction if size amplification exceeds 110% without reopening DB
  ASSERT_EQ(dbfull()
                ->GetOptions(handles_[1])
                .compaction_options_universal.max_size_amplification_percent,
            200U);
  ASSERT_OK(dbfull()->SetOptions(handles_[1],
                                 {{"compaction_options_universal",
                                   "{max_size_amplification_percent=110;}"}}));
  ASSERT_EQ(dbfull()
                ->GetOptions(handles_[1])
                .compaction_options_universal.max_size_amplification_percent,
            110u);
  ASSERT_OK(dbfull()->TEST_GetLatestMutableCFOptions(handles_[1],
                                                     &mutable_cf_options));
  ASSERT_EQ(110u, mutable_cf_options.compaction_options_universal
                      .max_size_amplification_percent);

  ASSERT_OK(dbfull()->TEST_WaitForCompact());
  // Verify that size amplification did happen
  ASSERT_EQ(NumSortedRuns(1), 1);
  ASSERT_EQ(total_picked_compactions, 1);
  ASSERT_EQ(total_size_amp_compactions, 1);
}

TEST_P(DBTestUniversalCompaction, DynamicUniversalCompactionReadAmplification) {
  Options options = CurrentOptions();
  options.compaction_style = kCompactionStyleUniversal;
  options.num_levels = 1;
  options.write_buffer_size = 100 << 10;     // 100KB
  options.target_file_size_base = 32 << 10;  // 32KB
  options.level0_file_num_compaction_trigger = 3;
  // Initial setup of compaction_options_universal will prevent universal
  // compaction from happening
  options.compaction_options_universal.max_size_amplification_percent = 2000;
  options.compaction_options_universal.size_ratio = 0;
  options.compaction_options_universal.min_merge_width = 100;
  DestroyAndReopen(options);

  int total_picked_compactions = 0;
  int total_size_ratio_compactions = 0;
  ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->SetCallBack(
      "UniversalCompactionBuilder::PickCompaction:Return", [&](void* arg) {
        if (arg) {
          total_picked_compactions++;
          Compaction* c = static_cast<Compaction*>(arg);
          if (c->compaction_reason() == CompactionReason::kUniversalSizeRatio) {
            total_size_ratio_compactions++;
          }
        }
      });
  ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->EnableProcessing();

  MutableCFOptions mutable_cf_options;
  CreateAndReopenWithCF({"pikachu"}, options);

  Random rnd(301);
  int key_idx = 0;

  // Generate three files in Level 0. All files are approx the same size.
  for (int num = 0; num < options.level0_file_num_compaction_trigger; num++) {
    // Write 110KB (11 values, each 10K)
    for (int i = 0; i < 11; i++) {
      ASSERT_OK(Put(1, Key(key_idx), rnd.RandomString(10000)));
      key_idx++;
    }
    ASSERT_OK(dbfull()->TEST_WaitForFlushMemTable(handles_[1]));
    ASSERT_EQ(NumSortedRuns(1), num + 1);
  }
  ASSERT_EQ(NumSortedRuns(1), options.level0_file_num_compaction_trigger);

  // Flush whatever is remaining in memtable. This is typically small, about
  // 30KB.
  ASSERT_OK(Flush(1));
  ASSERT_OK(dbfull()->TEST_WaitForCompact());
  // Verify compaction did not happen
  ASSERT_EQ(NumSortedRuns(1), options.level0_file_num_compaction_trigger + 1);
  ASSERT_EQ(total_picked_compactions, 0);

  ASSERT_OK(dbfull()->SetOptions(
      handles_[1],
      {{"compaction_options_universal",
        "{min_merge_width=2;max_merge_width=2;size_ratio=100;}"}}));
  ASSERT_EQ(dbfull()
                ->GetOptions(handles_[1])
                .compaction_options_universal.min_merge_width,
            2u);
  ASSERT_EQ(dbfull()
                ->GetOptions(handles_[1])
                .compaction_options_universal.max_merge_width,
            2u);
  ASSERT_EQ(
      dbfull()->GetOptions(handles_[1]).compaction_options_universal.size_ratio,
      100u);

  ASSERT_OK(dbfull()->TEST_GetLatestMutableCFOptions(handles_[1],
                                                     &mutable_cf_options));
  ASSERT_EQ(mutable_cf_options.compaction_options_universal.size_ratio, 100u);
  ASSERT_EQ(mutable_cf_options.compaction_options_universal.min_merge_width,
            2u);
  ASSERT_EQ(mutable_cf_options.compaction_options_universal.max_merge_width,
            2u);

  ASSERT_OK(dbfull()->TEST_WaitForCompact());

  // Files in L0 are approx: 0.3 (30KB), 1, 1, 1.
  // On compaction: the files are below the size amp threshold, so we
  // fallthrough to checking read amp conditions. The configured size ratio is
  // not big enough to take 0.3 into consideration. So the next files 1 and 1
  // are compacted together first as they satisfy size ratio condition and
  // (min_merge_width, max_merge_width) condition, to give out a file size of 2.
  // Next, the newly generated 2 and the last file 1 are compacted together. So
  // at the end: #sortedRuns = 2, #picked_compactions = 2, and all the picked
  // ones are size ratio based compactions.
  ASSERT_EQ(NumSortedRuns(1), 2);
  // If max_merge_width had not been changed dynamically above, and if it
  // continued to be the default value of UINIT_MAX, total_picked_compactions
  // would have been 1.
  ASSERT_EQ(total_picked_compactions, 2);
  ASSERT_EQ(total_size_ratio_compactions, 2);
}

TEST_P(DBTestUniversalCompaction, CompactFilesOnUniversalCompaction) {
  const int kTestKeySize = 16;
  const int kTestValueSize = 984;
  const int kEntrySize = kTestKeySize + kTestValueSize;
  const int kEntriesPerBuffer = 10;

  ChangeCompactOptions();
  Options options;
  options.create_if_missing = true;
  options.compaction_style = kCompactionStyleLevel;
  options.num_levels = 1;
  options.target_file_size_base = options.write_buffer_size;
  options.compression = kNoCompression;
  options = CurrentOptions(options);
  options.write_buffer_size = kEntrySize * kEntriesPerBuffer;
  CreateAndReopenWithCF({"pikachu"}, options);
  ASSERT_EQ(options.compaction_style, kCompactionStyleUniversal);
  Random rnd(301);
  for (int key = 1024 * kEntriesPerBuffer; key >= 0; --key) {
    ASSERT_OK(Put(1, std::to_string(key), rnd.RandomString(kTestValueSize)));
  }
  ASSERT_OK(dbfull()->TEST_WaitForFlushMemTable(handles_[1]));
  ASSERT_OK(dbfull()->TEST_WaitForCompact());
  ColumnFamilyMetaData cf_meta;
  dbfull()->GetColumnFamilyMetaData(handles_[1], &cf_meta);
  std::vector<std::string> compaction_input_file_names;
  for (const auto& file : cf_meta.levels[0].files) {
    if (rnd.OneIn(2)) {
      compaction_input_file_names.push_back(file.name);
    }
  }

  if (compaction_input_file_names.size() == 0) {
    compaction_input_file_names.push_back(cf_meta.levels[0].files[0].name);
  }

  // expect fail since universal compaction only allow L0 output
  ASSERT_FALSE(dbfull()
                   ->CompactFiles(CompactionOptions(), handles_[1],
                                  compaction_input_file_names, 1)
                   .ok());

  // expect ok and verify the compacted files no longer exist.
  ASSERT_OK(dbfull()->CompactFiles(CompactionOptions(), handles_[1],
                                   compaction_input_file_names, 0));

  dbfull()->GetColumnFamilyMetaData(handles_[1], &cf_meta);
  VerifyCompactionResult(
      cf_meta, std::set<std::string>(compaction_input_file_names.begin(),
                                     compaction_input_file_names.end()));

  compaction_input_file_names.clear();

  // Pick the first and the last file, expect everything is
  // compacted into one single file.
  compaction_input_file_names.push_back(cf_meta.levels[0].files[0].name);
  compaction_input_file_names.push_back(
      cf_meta.levels[0].files[cf_meta.levels[0].files.size() - 1].name);
  ASSERT_OK(dbfull()->CompactFiles(CompactionOptions(), handles_[1],
                                   compaction_input_file_names, 0));

  dbfull()->GetColumnFamilyMetaData(handles_[1], &cf_meta);
  ASSERT_EQ(cf_meta.levels[0].files.size(), 1U);
}

TEST_P(DBTestUniversalCompaction, UniversalCompactionTargetLevel) {
  Options options = CurrentOptions();
  options.compaction_style = kCompactionStyleUniversal;
  options.write_buffer_size = 100 << 10;  // 100KB
  options.num_levels = 7;
  options.disable_auto_compactions = true;
  DestroyAndReopen(options);

  // Generate 3 overlapping files
  Random rnd(301);
  for (int i = 0; i < 210; i++) {
    ASSERT_OK(Put(Key(i), rnd.RandomString(100)));
  }
  ASSERT_OK(Flush());

  for (int i = 200; i < 300; i++) {
    ASSERT_OK(Put(Key(i), rnd.RandomString(100)));
  }
  ASSERT_OK(Flush());

  for (int i = 250; i < 260; i++) {
    ASSERT_OK(Put(Key(i), rnd.RandomString(100)));
  }
  ASSERT_OK(Flush());

  ASSERT_EQ("3", FilesPerLevel(0));
  // Compact all files into 1 file and put it in L4
  CompactRangeOptions compact_options;
  compact_options.change_level = true;
  compact_options.target_level = 4;
  compact_options.exclusive_manual_compaction = exclusive_manual_compaction_;
  ASSERT_OK(db_->CompactRange(compact_options, nullptr, nullptr));
  ASSERT_EQ("0,0,0,0,1", FilesPerLevel(0));
}

#if !defined(ROCKSDB_VALGRIND_RUN) || defined(ROCKSDB_FULL_VALGRIND_RUN)
class DBTestUniversalCompactionMultiLevels
    : public DBTestUniversalCompactionBase {
 public:
  DBTestUniversalCompactionMultiLevels()
      : DBTestUniversalCompactionBase(
            "/db_universal_compaction_multi_levels_test") {}
};

TEST_P(DBTestUniversalCompactionMultiLevels, UniversalCompactionMultiLevels) {
  Options options = CurrentOptions();
  options.compaction_style = kCompactionStyleUniversal;
  options.num_levels = num_levels_;
  options.write_buffer_size = 100 << 10;  // 100KB
  options.level0_file_num_compaction_trigger = 8;
  options.max_background_compactions = 3;
  options.target_file_size_base = 32 * 1024;
  CreateAndReopenWithCF({"pikachu"}, options);

  // Trigger compaction if size amplification exceeds 110%
  options.compaction_options_universal.max_size_amplification_percent = 110;
  options = CurrentOptions(options);
  ReopenWithColumnFamilies({"default", "pikachu"}, options);

  Random rnd(301);
  int num_keys = 100000;
  for (int i = 0; i < num_keys * 2; i++) {
    ASSERT_OK(Put(1, Key(i % num_keys), Key(i)));
  }

  ASSERT_OK(dbfull()->TEST_WaitForCompact());

  for (int i = num_keys; i < num_keys * 2; i++) {
    ASSERT_EQ(Get(1, Key(i % num_keys)), Key(i));
  }
}

// Tests universal compaction with trivial move enabled
TEST_P(DBTestUniversalCompactionMultiLevels, UniversalCompactionTrivialMove) {
  int32_t trivial_move = 0;
  int32_t non_trivial_move = 0;
  ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->SetCallBack(
      "DBImpl::BackgroundCompaction:TrivialMove",
      [&](void* /*arg*/) { trivial_move++; });
  ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->SetCallBack(
      "DBImpl::BackgroundCompaction:NonTrivial", [&](void* arg) {
        non_trivial_move++;
        ASSERT_TRUE(arg != nullptr);
        int output_level = *(static_cast<int*>(arg));
        ASSERT_EQ(output_level, 0);
      });
  ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->EnableProcessing();

  Options options = CurrentOptions();
  options.compaction_style = kCompactionStyleUniversal;
  options.compaction_options_universal.allow_trivial_move = true;
  options.num_levels = 3;
  options.write_buffer_size = 100 << 10;  // 100KB
  options.level0_file_num_compaction_trigger = 3;
  options.max_background_compactions = 2;
  options.target_file_size_base = 32 * 1024;
  DestroyAndReopen(options);
  CreateAndReopenWithCF({"pikachu"}, options);

  // Trigger compaction if size amplification exceeds 110%
  options.compaction_options_universal.max_size_amplification_percent = 110;
  options = CurrentOptions(options);
  ReopenWithColumnFamilies({"default", "pikachu"}, options);

  Random rnd(301);
  int num_keys = 150000;
  for (int i = 0; i < num_keys; i++) {
    ASSERT_OK(Put(1, Key(i), Key(i)));
  }
  std::vector<std::string> values;

  ASSERT_OK(Flush(1));
  ASSERT_OK(dbfull()->TEST_WaitForCompact());

  ASSERT_GT(trivial_move, 0);
  ASSERT_GT(non_trivial_move, 0);

  ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->DisableProcessing();
}

INSTANTIATE_TEST_CASE_P(MultiLevels, DBTestUniversalCompactionMultiLevels,
                        ::testing::Combine(::testing::Values(3, 20),
                                           ::testing::Bool()));

class DBTestUniversalCompactionParallel : public DBTestUniversalCompactionBase {
 public:
  DBTestUniversalCompactionParallel()
      : DBTestUniversalCompactionBase("/db_universal_compaction_prallel_test") {
  }
};

TEST_P(DBTestUniversalCompactionParallel, UniversalCompactionParallel) {
  Options options = CurrentOptions();
  options.compaction_style = kCompactionStyleUniversal;
  options.num_levels = num_levels_;
  options.env = env_;
  options.write_buffer_size = 1 << 10;  // 1KB
  options.level0_file_num_compaction_trigger = 3;
  options.max_background_compactions = 3;
  options.max_background_flushes = 3;
  options.target_file_size_base = 1 * 1024;
  options.compaction_options_universal.max_size_amplification_percent = 110;
  DestroyAndReopen(options);
  CreateAndReopenWithCF({"pikachu"}, options);

  // Delay every compaction so multiple compactions will happen.
  std::atomic<int> num_compactions_running(0);
  std::atomic<bool> has_parallel(false);
  ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->SetCallBack(
      "CompactionJob::Run():Start", [&](void* /*arg*/) {
        if (num_compactions_running.fetch_add(1) > 0) {
          has_parallel.store(true);
          return;
        }
        for (int nwait = 0; nwait < 20000; nwait++) {
          if (has_parallel.load() || num_compactions_running.load() > 1) {
            has_parallel.store(true);
            break;
          }
          env_->SleepForMicroseconds(1000);
        }
      });
  ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->SetCallBack(
      "CompactionJob::Run():End",
      [&](void* /*arg*/) { num_compactions_running.fetch_add(-1); });
  ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->EnableProcessing();

  options = CurrentOptions(options);
  ReopenWithColumnFamilies({"default", "pikachu"}, options);

  Random rnd(301);
  int num_keys = 30000;
  for (int i = 0; i < num_keys * 2; i++) {
    ASSERT_OK(Put(1, Key(i % num_keys), Key(i)));
  }
  ASSERT_OK(dbfull()->TEST_WaitForCompact());

  ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->DisableProcessing();
  ASSERT_EQ(num_compactions_running.load(), 0);
  ASSERT_TRUE(has_parallel.load());

  for (int i = num_keys; i < num_keys * 2; i++) {
    ASSERT_EQ(Get(1, Key(i % num_keys)), Key(i));
  }

  // Reopen and check.
  ReopenWithColumnFamilies({"default", "pikachu"}, options);
  for (int i = num_keys; i < num_keys * 2; i++) {
    ASSERT_EQ(Get(1, Key(i % num_keys)), Key(i));
  }
}

TEST_P(DBTestUniversalCompactionParallel, PickByFileNumberBug) {
  Options options = CurrentOptions();
  options.compaction_style = kCompactionStyleUniversal;
  options.num_levels = num_levels_;
  options.write_buffer_size = 1 * 1024;  // 1KB
  options.level0_file_num_compaction_trigger = 7;
  options.max_background_compactions = 2;
  options.target_file_size_base = 1024 * 1024;  // 1MB

  // Disable size amplifiction compaction
  options.compaction_options_universal.max_size_amplification_percent =
      UINT_MAX;
  DestroyAndReopen(options);

  ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->LoadDependency(
      {{"DBTestUniversalCompactionParallel::PickByFileNumberBug:0",
        "BackgroundCallCompaction:0"},
       {"UniversalCompactionBuilder::PickCompaction:Return",
        "DBTestUniversalCompactionParallel::PickByFileNumberBug:1"},
       {"DBTestUniversalCompactionParallel::PickByFileNumberBug:2",
        "CompactionJob::Run():Start"}});

  int total_picked_compactions = 0;
  ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->SetCallBack(
      "UniversalCompactionBuilder::PickCompaction:Return", [&](void* arg) {
        if (arg) {
          total_picked_compactions++;
        }
      });

  ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->EnableProcessing();

  // Write 7 files to trigger compaction
  int key_idx = 1;
  for (int i = 1; i <= 70; i++) {
    std::string k = Key(key_idx++);
    ASSERT_OK(Put(k, k));
    if (i % 10 == 0) {
      ASSERT_OK(Flush());
    }
  }

  // Wait for the 1st background compaction process to start
  TEST_SYNC_POINT("DBTestUniversalCompactionParallel::PickByFileNumberBug:0");
  TEST_SYNC_POINT("DBTestUniversalCompactionParallel::PickByFileNumberBug:1");
  ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->ClearTrace();

  // Write 3 files while 1st compaction is held
  // These 3 files have different sizes to avoid compacting based on size_ratio
  int num_keys = 1000;
  for (int i = 0; i < 3; i++) {
    for (int j = 1; j <= num_keys; j++) {
      std::string k = Key(key_idx++);
      ASSERT_OK(Put(k, k));
    }
    ASSERT_OK(Flush());
    num_keys -= 100;
  }

  // Hold the 1st compaction from finishing
  TEST_SYNC_POINT("DBTestUniversalCompactionParallel::PickByFileNumberBug:2");
  ASSERT_OK(dbfull()->TEST_WaitForCompact());

  // There should only be one picked compaction as the score drops below one
  // after the first one is picked.
  EXPECT_EQ(total_picked_compactions, 1);
  EXPECT_EQ(TotalTableFiles(), 4);

  // Stop SyncPoint and destroy the DB and reopen it again
  ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->ClearTrace();
  ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->DisableProcessing();
  key_idx = 1;
  total_picked_compactions = 0;
  DestroyAndReopen(options);

  ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->EnableProcessing();

  // Write 7 files to trigger compaction
  for (int i = 1; i <= 70; i++) {
    std::string k = Key(key_idx++);
    ASSERT_OK(Put(k, k));
    if (i % 10 == 0) {
      ASSERT_OK(Flush());
    }
  }

  // Wait for the 1st background compaction process to start
  TEST_SYNC_POINT("DBTestUniversalCompactionParallel::PickByFileNumberBug:0");
  TEST_SYNC_POINT("DBTestUniversalCompactionParallel::PickByFileNumberBug:1");
  ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->ClearTrace();

  // Write 8 files while 1st compaction is held
  // These 8 files have different sizes to avoid compacting based on size_ratio
  num_keys = 1000;
  for (int i = 0; i < 8; i++) {
    for (int j = 1; j <= num_keys; j++) {
      std::string k = Key(key_idx++);
      ASSERT_OK(Put(k, k));
    }
    ASSERT_OK(Flush());
    num_keys -= 100;
  }

  // Wait for the 2nd background compaction process to start
  TEST_SYNC_POINT("DBTestUniversalCompactionParallel::PickByFileNumberBug:0");
  TEST_SYNC_POINT("DBTestUniversalCompactionParallel::PickByFileNumberBug:1");

  // Hold the 1st and 2nd compaction from finishing
  TEST_SYNC_POINT("DBTestUniversalCompactionParallel::PickByFileNumberBug:2");
  ASSERT_OK(dbfull()->TEST_WaitForCompact());

  // This time we will trigger a compaction because of size ratio and
  // another compaction because of number of files that are not compacted
  // greater than 7
  EXPECT_GE(total_picked_compactions, 2);
}

INSTANTIATE_TEST_CASE_P(Parallel, DBTestUniversalCompactionParallel,
                        ::testing::Combine(::testing::Values(1, 10),
                                           ::testing::Values(false)));
#endif  // !defined(ROCKSDB_VALGRIND_RUN) || defined(ROCKSDB_FULL_VALGRIND_RUN)

TEST_P(DBTestUniversalCompaction, UniversalCompactionOptions) {
  Options options = CurrentOptions();
  options.compaction_style = kCompactionStyleUniversal;
  options.write_buffer_size = 105 << 10;     // 105KB
  options.arena_block_size = 4 << 10;        // 4KB
  options.target_file_size_base = 32 << 10;  // 32KB
  options.level0_file_num_compaction_trigger = 4;
  options.num_levels = num_levels_;
  options.compaction_options_universal.compression_size_percent = -1;
  DestroyAndReopen(options);
  CreateAndReopenWithCF({"pikachu"}, options);

  Random rnd(301);
  int key_idx = 0;

  for (int num = 0; num < options.level0_file_num_compaction_trigger; num++) {
    // Write 100KB (100 values, each 1K)
    for (int i = 0; i < 100; i++) {
      ASSERT_OK(Put(1, Key(key_idx), rnd.RandomString(990)));
      key_idx++;
    }
    ASSERT_OK(dbfull()->TEST_WaitForFlushMemTable(handles_[1]));

    if (num < options.level0_file_num_compaction_trigger - 1) {
      ASSERT_EQ(NumSortedRuns(1), num + 1);
    }
  }

  ASSERT_OK(dbfull()->TEST_WaitForCompact());
  ASSERT_EQ(NumSortedRuns(1), 1);
}

TEST_P(DBTestUniversalCompaction, UniversalCompactionStopStyleSimilarSize) {
  Options options = CurrentOptions();
  options.compaction_style = kCompactionStyleUniversal;
  options.write_buffer_size = 105 << 10;     // 105KB
  options.arena_block_size = 4 << 10;        // 4KB
  options.target_file_size_base = 32 << 10;  // 32KB
  // trigger compaction if there are >= 4 files
  options.level0_file_num_compaction_trigger = 4;
  options.compaction_options_universal.size_ratio = 10;
  options.compaction_options_universal.stop_style =
      kCompactionStopStyleSimilarSize;
  options.num_levels = num_levels_;
  DestroyAndReopen(options);

  Random rnd(301);
  int key_idx = 0;

  // Stage 1:
  //   Generate a set of files at level 0, but don't trigger level-0
  //   compaction.
  for (int num = 0; num < options.level0_file_num_compaction_trigger - 1;
       num++) {
    // Write 100KB (100 values, each 1K)
    for (int i = 0; i < 100; i++) {
      ASSERT_OK(Put(Key(key_idx), rnd.RandomString(990)));
      key_idx++;
    }
    ASSERT_OK(dbfull()->TEST_WaitForFlushMemTable());
    ASSERT_EQ(NumSortedRuns(), num + 1);
  }

  // Generate one more file at level-0, which should trigger level-0
  // compaction.
  for (int i = 0; i < 100; i++) {
    ASSERT_OK(Put(Key(key_idx), rnd.RandomString(990)));
    key_idx++;
  }
  ASSERT_OK(dbfull()->TEST_WaitForCompact());
  // Suppose each file flushed from mem table has size 1. Now we compact
  // (level0_file_num_compaction_trigger+1)=4 files and should have a big
  // file of size 4.
  ASSERT_EQ(NumSortedRuns(), 1);

  // Stage 2:
  //   Now we have one file at level 0, with size 4. We also have some data in
  //   mem table. Let's continue generating new files at level 0, but don't
  //   trigger level-0 compaction.
  //   First, clean up memtable before inserting new data. This will generate
  //   a level-0 file, with size around 0.4 (according to previously written
  //   data amount).
  ASSERT_OK(dbfull()->Flush(FlushOptions()));
  for (int num = 0; num < options.level0_file_num_compaction_trigger - 3;
       num++) {
    // Write 110KB (11 values, each 10K)
    for (int i = 0; i < 100; i++) {
      ASSERT_OK(Put(Key(key_idx), rnd.RandomString(990)));