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 
7 #include <limits>
8 #include <string>
9 #include <utility>
10 #include "db/compaction/compaction.h"
11 #include "db/compaction/compaction_picker_fifo.h"
12 #include "db/compaction/compaction_picker_level.h"
13 #include "db/compaction/compaction_picker_universal.h"
14 
15 #include "test_util/testharness.h"
16 #include "test_util/testutil.h"
17 #include "util/string_util.h"
18 
19 namespace ROCKSDB_NAMESPACE {
20 
21 class CountingLogger : public Logger {
22  public:
23   using Logger::Logv;
Logv(const char *,va_list)24   void Logv(const char* /*format*/, va_list /*ap*/) override { log_count++; }
25   size_t log_count;
26 };
27 
28 class CompactionPickerTest : public testing::Test {
29  public:
30   const Comparator* ucmp_;
31   InternalKeyComparator icmp_;
32   Options options_;
33   ImmutableOptions ioptions_;
34   MutableCFOptions mutable_cf_options_;
35   MutableDBOptions mutable_db_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 
CompactionPickerTest()50   CompactionPickerTest()
51       : ucmp_(BytewiseComparator()),
52         icmp_(ucmp_),
53         ioptions_(options_),
54         mutable_cf_options_(options_),
55         mutable_db_options_(),
56         level_compaction_picker(ioptions_, &icmp_),
57         cf_name_("dummy"),
58         log_buffer_(InfoLogLevel::INFO_LEVEL, &logger_),
59         file_num_(1),
60         vstorage_(nullptr) {
61     mutable_cf_options_.ttl = 0;
62     mutable_cf_options_.periodic_compaction_seconds = 0;
63     // ioptions_.compaction_pri = kMinOverlappingRatio has its own set of
64     // tests to cover.
65     ioptions_.compaction_pri = kByCompensatedSize;
66     fifo_options_.max_table_files_size = 1;
67     mutable_cf_options_.RefreshDerivedOptions(ioptions_);
68     ioptions_.cf_paths.emplace_back("dummy",
69                                     std::numeric_limits<uint64_t>::max());
70   }
71 
~CompactionPickerTest()72   ~CompactionPickerTest() override {}
73 
NewVersionStorage(int num_levels,CompactionStyle style)74   void NewVersionStorage(int num_levels, CompactionStyle style) {
75     DeleteVersionStorage();
76     options_.num_levels = num_levels;
77     vstorage_.reset(new VersionStorageInfo(&icmp_, ucmp_, options_.num_levels,
78                                            style, nullptr, false));
79     vstorage_->CalculateBaseBytes(ioptions_, mutable_cf_options_);
80   }
81 
82   // Create a new VersionStorageInfo object so we can add mode files and then
83   // merge it with the existing VersionStorageInfo
AddVersionStorage()84   void AddVersionStorage() {
85     temp_vstorage_.reset(new VersionStorageInfo(
86         &icmp_, ucmp_, options_.num_levels, ioptions_.compaction_style,
87         vstorage_.get(), false));
88   }
89 
DeleteVersionStorage()90   void DeleteVersionStorage() {
91     vstorage_.reset();
92     temp_vstorage_.reset();
93     files_.clear();
94     file_map_.clear();
95     input_files_.clear();
96   }
97 
Add(int level,uint32_t file_number,const char * smallest,const char * largest,uint64_t file_size=1,uint32_t path_id=0,SequenceNumber smallest_seq=100,SequenceNumber largest_seq=100,size_t compensated_file_size=0,bool marked_for_compact=false)98   void Add(int level, uint32_t file_number, const char* smallest,
99            const char* largest, uint64_t file_size = 1, uint32_t path_id = 0,
100            SequenceNumber smallest_seq = 100, SequenceNumber largest_seq = 100,
101            size_t compensated_file_size = 0, bool marked_for_compact = false) {
102     VersionStorageInfo* vstorage;
103     if (temp_vstorage_) {
104       vstorage = temp_vstorage_.get();
105     } else {
106       vstorage = vstorage_.get();
107     }
108     assert(level < vstorage->num_levels());
109     FileMetaData* f = new FileMetaData(
110         file_number, path_id, file_size,
111         InternalKey(smallest, smallest_seq, kTypeValue),
112         InternalKey(largest, largest_seq, kTypeValue), smallest_seq,
113         largest_seq, marked_for_compact, kInvalidBlobFileNumber,
114         kUnknownOldestAncesterTime, kUnknownFileCreationTime,
115         kUnknownFileChecksum, kUnknownFileChecksumFuncName);
116     f->compensated_file_size =
117         (compensated_file_size != 0) ? compensated_file_size : file_size;
118     vstorage->AddFile(level, f);
119     files_.emplace_back(f);
120     file_map_.insert({file_number, {f, level}});
121   }
122 
SetCompactionInputFilesLevels(int level_count,int start_level)123   void SetCompactionInputFilesLevels(int level_count, int start_level) {
124     input_files_.resize(level_count);
125     for (int i = 0; i < level_count; ++i) {
126       input_files_[i].level = start_level + i;
127     }
128     compaction_level_start_ = start_level;
129   }
130 
AddToCompactionFiles(uint32_t file_number)131   void AddToCompactionFiles(uint32_t file_number) {
132     auto iter = file_map_.find(file_number);
133     assert(iter != file_map_.end());
134     int level = iter->second.second;
135     assert(level < vstorage_->num_levels());
136     input_files_[level - compaction_level_start_].files.emplace_back(
137         iter->second.first);
138   }
139 
UpdateVersionStorageInfo()140   void UpdateVersionStorageInfo() {
141     if (temp_vstorage_) {
142       VersionBuilder builder(FileOptions(), &ioptions_, nullptr,
143                              vstorage_.get(), nullptr);
144       ASSERT_OK(builder.SaveTo(temp_vstorage_.get()));
145       vstorage_ = std::move(temp_vstorage_);
146     }
147     vstorage_->CalculateBaseBytes(ioptions_, mutable_cf_options_);
148     vstorage_->UpdateFilesByCompactionPri(ioptions_.compaction_pri);
149     vstorage_->UpdateNumNonEmptyLevels();
150     vstorage_->GenerateFileIndexer();
151     vstorage_->GenerateLevelFilesBrief();
152     vstorage_->ComputeCompactionScore(ioptions_, mutable_cf_options_);
153     vstorage_->GenerateLevel0NonOverlapping();
154     vstorage_->ComputeFilesMarkedForCompaction();
155     vstorage_->SetFinalized();
156   }
AddFileToVersionStorage(int level,uint32_t file_number,const char * smallest,const char * largest,uint64_t file_size=1,uint32_t path_id=0,SequenceNumber smallest_seq=100,SequenceNumber largest_seq=100,size_t compensated_file_size=0,bool marked_for_compact=false)157   void AddFileToVersionStorage(int level, uint32_t file_number,
158                                const char* smallest, const char* largest,
159                                uint64_t file_size = 1, uint32_t path_id = 0,
160                                SequenceNumber smallest_seq = 100,
161                                SequenceNumber largest_seq = 100,
162                                size_t compensated_file_size = 0,
163                                bool marked_for_compact = false) {
164     VersionStorageInfo* base_vstorage = vstorage_.release();
165     vstorage_.reset(new VersionStorageInfo(&icmp_, ucmp_, options_.num_levels,
166                                            kCompactionStyleUniversal,
167                                            base_vstorage, false));
168     Add(level, file_number, smallest, largest, file_size, path_id, smallest_seq,
169         largest_seq, compensated_file_size, marked_for_compact);
170 
171     VersionBuilder builder(FileOptions(), &ioptions_, nullptr, base_vstorage,
172                            nullptr);
173     builder.SaveTo(vstorage_.get());
174     UpdateVersionStorageInfo();
175   }
176 
177  private:
178   std::unique_ptr<VersionStorageInfo> temp_vstorage_;
179 };
180 
TEST_F(CompactionPickerTest,Empty)181 TEST_F(CompactionPickerTest, Empty) {
182   NewVersionStorage(6, kCompactionStyleLevel);
183   UpdateVersionStorageInfo();
184   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
185       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
186       &log_buffer_));
187   ASSERT_TRUE(compaction.get() == nullptr);
188 }
189 
TEST_F(CompactionPickerTest,Single)190 TEST_F(CompactionPickerTest, Single) {
191   NewVersionStorage(6, kCompactionStyleLevel);
192   mutable_cf_options_.level0_file_num_compaction_trigger = 2;
193   Add(0, 1U, "p", "q");
194   UpdateVersionStorageInfo();
195 
196   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
197       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
198       &log_buffer_));
199   ASSERT_TRUE(compaction.get() == nullptr);
200 }
201 
TEST_F(CompactionPickerTest,Level0Trigger)202 TEST_F(CompactionPickerTest, Level0Trigger) {
203   NewVersionStorage(6, kCompactionStyleLevel);
204   mutable_cf_options_.level0_file_num_compaction_trigger = 2;
205   Add(0, 1U, "150", "200");
206   Add(0, 2U, "200", "250");
207 
208   UpdateVersionStorageInfo();
209 
210   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
211       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
212       &log_buffer_));
213   ASSERT_TRUE(compaction.get() != nullptr);
214   ASSERT_EQ(2U, compaction->num_input_files(0));
215   ASSERT_EQ(1U, compaction->input(0, 0)->fd.GetNumber());
216   ASSERT_EQ(2U, compaction->input(0, 1)->fd.GetNumber());
217 }
218 
TEST_F(CompactionPickerTest,Level1Trigger)219 TEST_F(CompactionPickerTest, Level1Trigger) {
220   NewVersionStorage(6, kCompactionStyleLevel);
221   Add(1, 66U, "150", "200", 1000000000U);
222   UpdateVersionStorageInfo();
223 
224   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
225       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
226       &log_buffer_));
227   ASSERT_TRUE(compaction.get() != nullptr);
228   ASSERT_EQ(1U, compaction->num_input_files(0));
229   ASSERT_EQ(66U, compaction->input(0, 0)->fd.GetNumber());
230 }
231 
TEST_F(CompactionPickerTest,Level1Trigger2)232 TEST_F(CompactionPickerTest, Level1Trigger2) {
233   mutable_cf_options_.target_file_size_base = 10000000000;
234   mutable_cf_options_.RefreshDerivedOptions(ioptions_);
235   NewVersionStorage(6, kCompactionStyleLevel);
236   Add(1, 66U, "150", "200", 1000000001U);
237   Add(1, 88U, "201", "300", 1000000000U);
238   Add(2, 6U, "150", "179", 1000000000U);
239   Add(2, 7U, "180", "220", 1000000000U);
240   Add(2, 8U, "221", "300", 1000000000U);
241   UpdateVersionStorageInfo();
242 
243   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
244       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
245       &log_buffer_));
246   ASSERT_TRUE(compaction.get() != nullptr);
247   ASSERT_EQ(1U, compaction->num_input_files(0));
248   ASSERT_EQ(2U, compaction->num_input_files(1));
249   ASSERT_EQ(66U, compaction->input(0, 0)->fd.GetNumber());
250   ASSERT_EQ(6U, compaction->input(1, 0)->fd.GetNumber());
251   ASSERT_EQ(7U, compaction->input(1, 1)->fd.GetNumber());
252   ASSERT_EQ(uint64_t{1073741824}, compaction->OutputFilePreallocationSize());
253 }
254 
TEST_F(CompactionPickerTest,LevelMaxScore)255 TEST_F(CompactionPickerTest, LevelMaxScore) {
256   NewVersionStorage(6, kCompactionStyleLevel);
257   mutable_cf_options_.target_file_size_base = 10000000;
258   mutable_cf_options_.max_bytes_for_level_base = 10 * 1024 * 1024;
259   mutable_cf_options_.RefreshDerivedOptions(ioptions_);
260   Add(0, 1U, "150", "200", 1000000U);
261   // Level 1 score 1.2
262   Add(1, 66U, "150", "200", 6000000U);
263   Add(1, 88U, "201", "300", 6000000U);
264   // Level 2 score 1.8. File 7 is the largest. Should be picked
265   Add(2, 6U, "150", "179", 60000000U);
266   Add(2, 7U, "180", "220", 60000001U);
267   Add(2, 8U, "221", "300", 60000000U);
268   // Level 3 score slightly larger than 1
269   Add(3, 26U, "150", "170", 260000000U);
270   Add(3, 27U, "171", "179", 260000000U);
271   Add(3, 28U, "191", "220", 260000000U);
272   Add(3, 29U, "221", "300", 260000000U);
273   UpdateVersionStorageInfo();
274 
275   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
276       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
277       &log_buffer_));
278   ASSERT_TRUE(compaction.get() != nullptr);
279   ASSERT_EQ(1U, compaction->num_input_files(0));
280   ASSERT_EQ(7U, compaction->input(0, 0)->fd.GetNumber());
281   ASSERT_EQ(mutable_cf_options_.target_file_size_base +
282                 mutable_cf_options_.target_file_size_base / 10,
283             compaction->OutputFilePreallocationSize());
284 }
285 
TEST_F(CompactionPickerTest,NeedsCompactionLevel)286 TEST_F(CompactionPickerTest, NeedsCompactionLevel) {
287   const int kLevels = 6;
288   const int kFileCount = 20;
289 
290   for (int level = 0; level < kLevels - 1; ++level) {
291     NewVersionStorage(kLevels, kCompactionStyleLevel);
292     uint64_t file_size = vstorage_->MaxBytesForLevel(level) * 2 / kFileCount;
293     for (int file_count = 1; file_count <= kFileCount; ++file_count) {
294       // start a brand new version in each test.
295       NewVersionStorage(kLevels, kCompactionStyleLevel);
296       for (int i = 0; i < file_count; ++i) {
297         Add(level, i, ToString((i + 100) * 1000).c_str(),
298             ToString((i + 100) * 1000 + 999).c_str(),
299             file_size, 0, i * 100, i * 100 + 99);
300       }
301       UpdateVersionStorageInfo();
302       ASSERT_EQ(vstorage_->CompactionScoreLevel(0), level);
303       ASSERT_EQ(level_compaction_picker.NeedsCompaction(vstorage_.get()),
304                 vstorage_->CompactionScore(0) >= 1);
305       // release the version storage
306       DeleteVersionStorage();
307     }
308   }
309 }
310 
TEST_F(CompactionPickerTest,Level0TriggerDynamic)311 TEST_F(CompactionPickerTest, Level0TriggerDynamic) {
312   int num_levels = ioptions_.num_levels;
313   ioptions_.level_compaction_dynamic_level_bytes = true;
314   mutable_cf_options_.level0_file_num_compaction_trigger = 2;
315   mutable_cf_options_.max_bytes_for_level_base = 200;
316   mutable_cf_options_.max_bytes_for_level_multiplier = 10;
317   NewVersionStorage(num_levels, kCompactionStyleLevel);
318   Add(0, 1U, "150", "200");
319   Add(0, 2U, "200", "250");
320 
321   UpdateVersionStorageInfo();
322 
323   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
324       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
325       &log_buffer_));
326   ASSERT_TRUE(compaction.get() != nullptr);
327   ASSERT_EQ(2U, compaction->num_input_files(0));
328   ASSERT_EQ(1U, compaction->input(0, 0)->fd.GetNumber());
329   ASSERT_EQ(2U, compaction->input(0, 1)->fd.GetNumber());
330   ASSERT_EQ(1, static_cast<int>(compaction->num_input_levels()));
331   ASSERT_EQ(num_levels - 1, compaction->output_level());
332 }
333 
TEST_F(CompactionPickerTest,Level0TriggerDynamic2)334 TEST_F(CompactionPickerTest, Level0TriggerDynamic2) {
335   int num_levels = ioptions_.num_levels;
336   ioptions_.level_compaction_dynamic_level_bytes = true;
337   mutable_cf_options_.level0_file_num_compaction_trigger = 2;
338   mutable_cf_options_.max_bytes_for_level_base = 200;
339   mutable_cf_options_.max_bytes_for_level_multiplier = 10;
340   NewVersionStorage(num_levels, kCompactionStyleLevel);
341   Add(0, 1U, "150", "200");
342   Add(0, 2U, "200", "250");
343   Add(num_levels - 1, 3U, "200", "250", 300U);
344 
345   UpdateVersionStorageInfo();
346   ASSERT_EQ(vstorage_->base_level(), num_levels - 2);
347 
348   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
349       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
350       &log_buffer_));
351   ASSERT_TRUE(compaction.get() != nullptr);
352   ASSERT_EQ(2U, compaction->num_input_files(0));
353   ASSERT_EQ(1U, compaction->input(0, 0)->fd.GetNumber());
354   ASSERT_EQ(2U, compaction->input(0, 1)->fd.GetNumber());
355   ASSERT_EQ(1, static_cast<int>(compaction->num_input_levels()));
356   ASSERT_EQ(num_levels - 2, compaction->output_level());
357 }
358 
TEST_F(CompactionPickerTest,Level0TriggerDynamic3)359 TEST_F(CompactionPickerTest, Level0TriggerDynamic3) {
360   int num_levels = ioptions_.num_levels;
361   ioptions_.level_compaction_dynamic_level_bytes = true;
362   mutable_cf_options_.level0_file_num_compaction_trigger = 2;
363   mutable_cf_options_.max_bytes_for_level_base = 200;
364   mutable_cf_options_.max_bytes_for_level_multiplier = 10;
365   NewVersionStorage(num_levels, kCompactionStyleLevel);
366   Add(0, 1U, "150", "200");
367   Add(0, 2U, "200", "250");
368   Add(num_levels - 1, 3U, "200", "250", 300U);
369   Add(num_levels - 1, 4U, "300", "350", 3000U);
370 
371   UpdateVersionStorageInfo();
372   ASSERT_EQ(vstorage_->base_level(), num_levels - 3);
373 
374   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
375       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
376       &log_buffer_));
377   ASSERT_TRUE(compaction.get() != nullptr);
378   ASSERT_EQ(2U, compaction->num_input_files(0));
379   ASSERT_EQ(1U, compaction->input(0, 0)->fd.GetNumber());
380   ASSERT_EQ(2U, compaction->input(0, 1)->fd.GetNumber());
381   ASSERT_EQ(1, static_cast<int>(compaction->num_input_levels()));
382   ASSERT_EQ(num_levels - 3, compaction->output_level());
383 }
384 
TEST_F(CompactionPickerTest,Level0TriggerDynamic4)385 TEST_F(CompactionPickerTest, Level0TriggerDynamic4) {
386   int num_levels = ioptions_.num_levels;
387   ioptions_.level_compaction_dynamic_level_bytes = true;
388   mutable_cf_options_.level0_file_num_compaction_trigger = 2;
389   mutable_cf_options_.max_bytes_for_level_base = 200;
390   mutable_cf_options_.max_bytes_for_level_multiplier = 10;
391 
392   NewVersionStorage(num_levels, kCompactionStyleLevel);
393   Add(0, 1U, "150", "200");
394   Add(0, 2U, "200", "250");
395   Add(num_levels - 1, 3U, "200", "250", 300U);
396   Add(num_levels - 1, 4U, "300", "350", 3000U);
397   Add(num_levels - 3, 5U, "150", "180", 3U);
398   Add(num_levels - 3, 6U, "181", "300", 3U);
399   Add(num_levels - 3, 7U, "400", "450", 3U);
400 
401   UpdateVersionStorageInfo();
402   ASSERT_EQ(vstorage_->base_level(), num_levels - 3);
403 
404   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
405       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
406       &log_buffer_));
407   ASSERT_TRUE(compaction.get() != nullptr);
408   ASSERT_EQ(2U, compaction->num_input_files(0));
409   ASSERT_EQ(1U, compaction->input(0, 0)->fd.GetNumber());
410   ASSERT_EQ(2U, compaction->input(0, 1)->fd.GetNumber());
411   ASSERT_EQ(2U, compaction->num_input_files(1));
412   ASSERT_EQ(num_levels - 3, compaction->level(1));
413   ASSERT_EQ(5U, compaction->input(1, 0)->fd.GetNumber());
414   ASSERT_EQ(6U, compaction->input(1, 1)->fd.GetNumber());
415   ASSERT_EQ(2, static_cast<int>(compaction->num_input_levels()));
416   ASSERT_EQ(num_levels - 3, compaction->output_level());
417 }
418 
TEST_F(CompactionPickerTest,LevelTriggerDynamic4)419 TEST_F(CompactionPickerTest, LevelTriggerDynamic4) {
420   int num_levels = ioptions_.num_levels;
421   ioptions_.level_compaction_dynamic_level_bytes = true;
422   ioptions_.compaction_pri = kMinOverlappingRatio;
423   mutable_cf_options_.level0_file_num_compaction_trigger = 2;
424   mutable_cf_options_.max_bytes_for_level_base = 200;
425   mutable_cf_options_.max_bytes_for_level_multiplier = 10;
426   NewVersionStorage(num_levels, kCompactionStyleLevel);
427   Add(0, 1U, "150", "200");
428   Add(num_levels - 1, 2U, "200", "250", 300U);
429   Add(num_levels - 1, 3U, "300", "350", 3000U);
430   Add(num_levels - 1, 4U, "400", "450", 3U);
431   Add(num_levels - 2, 5U, "150", "180", 300U);
432   Add(num_levels - 2, 6U, "181", "350", 500U);
433   Add(num_levels - 2, 7U, "400", "450", 200U);
434 
435   UpdateVersionStorageInfo();
436 
437   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
438       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
439       &log_buffer_));
440   ASSERT_TRUE(compaction.get() != nullptr);
441   ASSERT_EQ(1U, compaction->num_input_files(0));
442   ASSERT_EQ(5U, compaction->input(0, 0)->fd.GetNumber());
443   ASSERT_EQ(0, compaction->num_input_files(1));
444   ASSERT_EQ(1U, compaction->num_input_levels());
445   ASSERT_EQ(num_levels - 1, compaction->output_level());
446 }
447 
448 // Universal and FIFO Compactions are not supported in ROCKSDB_LITE
449 #ifndef ROCKSDB_LITE
TEST_F(CompactionPickerTest,NeedsCompactionUniversal)450 TEST_F(CompactionPickerTest, NeedsCompactionUniversal) {
451   NewVersionStorage(1, kCompactionStyleUniversal);
452   UniversalCompactionPicker universal_compaction_picker(
453       ioptions_, &icmp_);
454   UpdateVersionStorageInfo();
455   // must return false when there's no files.
456   ASSERT_EQ(universal_compaction_picker.NeedsCompaction(vstorage_.get()),
457             false);
458 
459   // verify the trigger given different number of L0 files.
460   for (int i = 1;
461        i <= mutable_cf_options_.level0_file_num_compaction_trigger * 2; ++i) {
462     NewVersionStorage(1, kCompactionStyleUniversal);
463     Add(0, i, ToString((i + 100) * 1000).c_str(),
464         ToString((i + 100) * 1000 + 999).c_str(), 1000000, 0, i * 100,
465         i * 100 + 99);
466     UpdateVersionStorageInfo();
467     ASSERT_EQ(level_compaction_picker.NeedsCompaction(vstorage_.get()),
468               vstorage_->CompactionScore(0) >= 1);
469   }
470 }
471 
TEST_F(CompactionPickerTest,CompactionUniversalIngestBehindReservedLevel)472 TEST_F(CompactionPickerTest, CompactionUniversalIngestBehindReservedLevel) {
473   const uint64_t kFileSize = 100000;
474   NewVersionStorage(1, kCompactionStyleUniversal);
475   ioptions_.allow_ingest_behind = true;
476   ioptions_.num_levels = 3;
477   UniversalCompactionPicker universal_compaction_picker(ioptions_, &icmp_);
478   UpdateVersionStorageInfo();
479   // must return false when there's no files.
480   ASSERT_EQ(universal_compaction_picker.NeedsCompaction(vstorage_.get()),
481             false);
482 
483   NewVersionStorage(3, kCompactionStyleUniversal);
484 
485   Add(0, 1U, "150", "200", kFileSize, 0, 500, 550);
486   Add(0, 2U, "201", "250", kFileSize, 0, 401, 450);
487   Add(0, 4U, "260", "300", kFileSize, 0, 260, 300);
488   Add(1, 5U, "100", "151", kFileSize, 0, 200, 251);
489   Add(1, 3U, "301", "350", kFileSize, 0, 101, 150);
490   Add(2, 6U, "120", "200", kFileSize, 0, 20, 100);
491 
492   UpdateVersionStorageInfo();
493 
494   std::unique_ptr<Compaction> compaction(
495       universal_compaction_picker.PickCompaction(
496           cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
497           &log_buffer_));
498 
499   // output level should be the one above the bottom-most
500   ASSERT_EQ(1, compaction->output_level());
501 }
502 // Tests if the files can be trivially moved in multi level
503 // universal compaction when allow_trivial_move option is set
504 // In this test as the input files overlaps, they cannot
505 // be trivially moved.
506 
TEST_F(CompactionPickerTest,CannotTrivialMoveUniversal)507 TEST_F(CompactionPickerTest, CannotTrivialMoveUniversal) {
508   const uint64_t kFileSize = 100000;
509 
510   mutable_cf_options_.compaction_options_universal.allow_trivial_move = true;
511   NewVersionStorage(1, kCompactionStyleUniversal);
512   UniversalCompactionPicker universal_compaction_picker(ioptions_, &icmp_);
513   UpdateVersionStorageInfo();
514   // must return false when there's no files.
515   ASSERT_EQ(universal_compaction_picker.NeedsCompaction(vstorage_.get()),
516             false);
517 
518   NewVersionStorage(3, kCompactionStyleUniversal);
519 
520   Add(0, 1U, "150", "200", kFileSize, 0, 500, 550);
521   Add(0, 2U, "201", "250", kFileSize, 0, 401, 450);
522   Add(0, 4U, "260", "300", kFileSize, 0, 260, 300);
523   Add(1, 5U, "100", "151", kFileSize, 0, 200, 251);
524   Add(1, 3U, "301", "350", kFileSize, 0, 101, 150);
525   Add(2, 6U, "120", "200", kFileSize, 0, 20, 100);
526 
527   UpdateVersionStorageInfo();
528 
529   std::unique_ptr<Compaction> compaction(
530       universal_compaction_picker.PickCompaction(
531           cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
532           &log_buffer_));
533 
534   ASSERT_TRUE(!compaction->is_trivial_move());
535 }
536 // Tests if the files can be trivially moved in multi level
537 // universal compaction when allow_trivial_move option is set
538 // In this test as the input files doesn't overlaps, they should
539 // be trivially moved.
TEST_F(CompactionPickerTest,AllowsTrivialMoveUniversal)540 TEST_F(CompactionPickerTest, AllowsTrivialMoveUniversal) {
541   const uint64_t kFileSize = 100000;
542 
543   mutable_cf_options_.compaction_options_universal.allow_trivial_move = true;
544   UniversalCompactionPicker universal_compaction_picker(ioptions_, &icmp_);
545 
546   NewVersionStorage(3, kCompactionStyleUniversal);
547 
548   Add(0, 1U, "150", "200", kFileSize, 0, 500, 550);
549   Add(0, 2U, "201", "250", kFileSize, 0, 401, 450);
550   Add(0, 4U, "260", "300", kFileSize, 0, 260, 300);
551   Add(1, 5U, "010", "080", kFileSize, 0, 200, 251);
552   Add(2, 3U, "301", "350", kFileSize, 0, 101, 150);
553 
554   UpdateVersionStorageInfo();
555 
556   std::unique_ptr<Compaction> compaction(
557       universal_compaction_picker.PickCompaction(
558           cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
559           &log_buffer_));
560 
561   ASSERT_TRUE(compaction->is_trivial_move());
562 }
563 
TEST_F(CompactionPickerTest,UniversalPeriodicCompaction1)564 TEST_F(CompactionPickerTest, UniversalPeriodicCompaction1) {
565   // The case where universal periodic compaction can be picked
566   // with some newer files being compacted.
567   const uint64_t kFileSize = 100000;
568 
569   mutable_cf_options_.periodic_compaction_seconds = 1000;
570   UniversalCompactionPicker universal_compaction_picker(ioptions_, &icmp_);
571 
572   NewVersionStorage(5, kCompactionStyleUniversal);
573 
574   Add(0, 1U, "150", "200", kFileSize, 0, 500, 550);
575   Add(0, 2U, "201", "250", kFileSize, 0, 401, 450);
576   Add(0, 4U, "260", "300", kFileSize, 0, 260, 300);
577   Add(3, 5U, "010", "080", kFileSize, 0, 200, 251);
578   Add(4, 3U, "301", "350", kFileSize, 0, 101, 150);
579   Add(4, 6U, "501", "750", kFileSize, 0, 101, 150);
580 
581   file_map_[2].first->being_compacted = true;
582   UpdateVersionStorageInfo();
583   vstorage_->TEST_AddFileMarkedForPeriodicCompaction(4, file_map_[3].first);
584 
585   std::unique_ptr<Compaction> compaction(
586       universal_compaction_picker.PickCompaction(
587           cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
588           &log_buffer_));
589 
590   ASSERT_TRUE(compaction);
591   ASSERT_EQ(4, compaction->output_level());
592   ASSERT_EQ(0, compaction->start_level());
593   ASSERT_EQ(1U, compaction->num_input_files(0));
594 }
595 
TEST_F(CompactionPickerTest,UniversalPeriodicCompaction2)596 TEST_F(CompactionPickerTest, UniversalPeriodicCompaction2) {
597   // The case where universal periodic compaction does not
598   // pick up only level to compact if it doesn't cover
599   // any file marked as periodic compaction.
600   const uint64_t kFileSize = 100000;
601 
602   mutable_cf_options_.periodic_compaction_seconds = 1000;
603   UniversalCompactionPicker universal_compaction_picker(ioptions_, &icmp_);
604 
605   NewVersionStorage(5, kCompactionStyleUniversal);
606 
607   Add(0, 1U, "150", "200", kFileSize, 0, 500, 550);
608   Add(3, 5U, "010", "080", kFileSize, 0, 200, 251);
609   Add(4, 3U, "301", "350", kFileSize, 0, 101, 150);
610   Add(4, 6U, "501", "750", kFileSize, 0, 101, 150);
611 
612   file_map_[5].first->being_compacted = true;
613   UpdateVersionStorageInfo();
614   vstorage_->TEST_AddFileMarkedForPeriodicCompaction(0, file_map_[1].first);
615 
616   std::unique_ptr<Compaction> compaction(
617       universal_compaction_picker.PickCompaction(
618           cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
619           &log_buffer_));
620 
621   ASSERT_FALSE(compaction);
622 }
623 
TEST_F(CompactionPickerTest,UniversalPeriodicCompaction3)624 TEST_F(CompactionPickerTest, UniversalPeriodicCompaction3) {
625   // The case where universal periodic compaction does not
626   // pick up only the last sorted run which is an L0 file if it isn't
627   // marked as periodic compaction.
628   const uint64_t kFileSize = 100000;
629 
630   mutable_cf_options_.periodic_compaction_seconds = 1000;
631   UniversalCompactionPicker universal_compaction_picker(ioptions_, &icmp_);
632 
633   NewVersionStorage(5, kCompactionStyleUniversal);
634 
635   Add(0, 1U, "150", "200", kFileSize, 0, 500, 550);
636   Add(0, 5U, "010", "080", kFileSize, 0, 200, 251);
637   Add(0, 6U, "501", "750", kFileSize, 0, 101, 150);
638 
639   file_map_[5].first->being_compacted = true;
640   UpdateVersionStorageInfo();
641   vstorage_->TEST_AddFileMarkedForPeriodicCompaction(0, file_map_[1].first);
642 
643   std::unique_ptr<Compaction> compaction(
644       universal_compaction_picker.PickCompaction(
645           cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
646           &log_buffer_));
647 
648   ASSERT_FALSE(compaction);
649 }
650 
TEST_F(CompactionPickerTest,UniversalPeriodicCompaction4)651 TEST_F(CompactionPickerTest, UniversalPeriodicCompaction4) {
652   // The case where universal periodic compaction couldn't form
653   // a compaction that includes any file marked for periodic compaction.
654   // Right now we form the compaction anyway if it is more than one
655   // sorted run. Just put the case here to validate that it doesn't
656   // crash.
657   const uint64_t kFileSize = 100000;
658 
659   mutable_cf_options_.periodic_compaction_seconds = 1000;
660   UniversalCompactionPicker universal_compaction_picker(ioptions_, &icmp_);
661 
662   NewVersionStorage(5, kCompactionStyleUniversal);
663 
664   Add(0, 1U, "150", "200", kFileSize, 0, 500, 550);
665   Add(2, 2U, "010", "080", kFileSize, 0, 200, 251);
666   Add(3, 5U, "010", "080", kFileSize, 0, 200, 251);
667   Add(4, 3U, "301", "350", kFileSize, 0, 101, 150);
668   Add(4, 6U, "501", "750", kFileSize, 0, 101, 150);
669 
670   file_map_[2].first->being_compacted = true;
671   UpdateVersionStorageInfo();
672   vstorage_->TEST_AddFileMarkedForPeriodicCompaction(0, file_map_[2].first);
673 
674   std::unique_ptr<Compaction> compaction(
675       universal_compaction_picker.PickCompaction(
676           cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
677           &log_buffer_));
678   ASSERT_TRUE(!compaction ||
679               compaction->start_level() != compaction->output_level());
680 }
681 
TEST_F(CompactionPickerTest,UniversalPeriodicCompaction5)682 TEST_F(CompactionPickerTest, UniversalPeriodicCompaction5) {
683   // Test single L0 file periodic compaction triggering.
684   const uint64_t kFileSize = 100000;
685 
686   mutable_cf_options_.periodic_compaction_seconds = 1000;
687   UniversalCompactionPicker universal_compaction_picker(ioptions_, &icmp_);
688 
689   NewVersionStorage(5, kCompactionStyleUniversal);
690 
691   Add(0, 6U, "150", "200", kFileSize, 0, 500, 550);
692   UpdateVersionStorageInfo();
693   vstorage_->TEST_AddFileMarkedForPeriodicCompaction(0, file_map_[6].first);
694 
695   std::unique_ptr<Compaction> compaction(
696       universal_compaction_picker.PickCompaction(
697           cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
698           &log_buffer_));
699   ASSERT_TRUE(compaction);
700   ASSERT_EQ(0, compaction->start_level());
701   ASSERT_EQ(1U, compaction->num_input_files(0));
702   ASSERT_EQ(6U, compaction->input(0, 0)->fd.GetNumber());
703   ASSERT_EQ(4, compaction->output_level());
704 }
705 
TEST_F(CompactionPickerTest,UniversalPeriodicCompaction6)706 TEST_F(CompactionPickerTest, UniversalPeriodicCompaction6) {
707   // Test single sorted run non-L0 periodic compaction
708   const uint64_t kFileSize = 100000;
709 
710   mutable_cf_options_.periodic_compaction_seconds = 1000;
711   UniversalCompactionPicker universal_compaction_picker(ioptions_, &icmp_);
712 
713   NewVersionStorage(5, kCompactionStyleUniversal);
714 
715   Add(4, 5U, "150", "200", kFileSize, 0, 500, 550);
716   Add(4, 6U, "350", "400", kFileSize, 0, 500, 550);
717   UpdateVersionStorageInfo();
718   vstorage_->TEST_AddFileMarkedForPeriodicCompaction(4, file_map_[6].first);
719 
720   std::unique_ptr<Compaction> compaction(
721       universal_compaction_picker.PickCompaction(
722           cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
723           &log_buffer_));
724   ASSERT_TRUE(compaction);
725   ASSERT_EQ(4, compaction->start_level());
726   ASSERT_EQ(2U, compaction->num_input_files(0));
727   ASSERT_EQ(5U, compaction->input(0, 0)->fd.GetNumber());
728   ASSERT_EQ(6U, compaction->input(0, 1)->fd.GetNumber());
729   ASSERT_EQ(4, compaction->output_level());
730 }
731 
TEST_F(CompactionPickerTest,NeedsCompactionFIFO)732 TEST_F(CompactionPickerTest, NeedsCompactionFIFO) {
733   NewVersionStorage(1, kCompactionStyleFIFO);
734   const int kFileCount =
735       mutable_cf_options_.level0_file_num_compaction_trigger * 3;
736   const uint64_t kFileSize = 100000;
737   const uint64_t kMaxSize = kFileSize * kFileCount / 2;
738 
739   fifo_options_.max_table_files_size = kMaxSize;
740   mutable_cf_options_.compaction_options_fifo = fifo_options_;
741   FIFOCompactionPicker fifo_compaction_picker(ioptions_, &icmp_);
742   UpdateVersionStorageInfo();
743   // must return false when there's no files.
744   ASSERT_EQ(fifo_compaction_picker.NeedsCompaction(vstorage_.get()), false);
745 
746   // verify whether compaction is needed based on the current
747   // size of L0 files.
748   uint64_t current_size = 0;
749   for (int i = 1; i <= kFileCount; ++i) {
750     NewVersionStorage(1, kCompactionStyleFIFO);
751     Add(0, i, ToString((i + 100) * 1000).c_str(),
752         ToString((i + 100) * 1000 + 999).c_str(),
753         kFileSize, 0, i * 100, i * 100 + 99);
754     current_size += kFileSize;
755     UpdateVersionStorageInfo();
756     ASSERT_EQ(fifo_compaction_picker.NeedsCompaction(vstorage_.get()),
757               vstorage_->CompactionScore(0) >= 1);
758   }
759 }
760 #endif  // ROCKSDB_LITE
761 
TEST_F(CompactionPickerTest,CompactionPriMinOverlapping1)762 TEST_F(CompactionPickerTest, CompactionPriMinOverlapping1) {
763   NewVersionStorage(6, kCompactionStyleLevel);
764   ioptions_.compaction_pri = kMinOverlappingRatio;
765   mutable_cf_options_.target_file_size_base = 100000000000;
766   mutable_cf_options_.target_file_size_multiplier = 10;
767   mutable_cf_options_.max_bytes_for_level_base = 10 * 1024 * 1024;
768   mutable_cf_options_.RefreshDerivedOptions(ioptions_);
769 
770   Add(2, 6U, "150", "179", 50000000U);
771   Add(2, 7U, "180", "220", 50000000U);
772   Add(2, 8U, "321", "400", 50000000U);  // File not overlapping
773   Add(2, 9U, "721", "800", 50000000U);
774 
775   Add(3, 26U, "150", "170", 260000000U);
776   Add(3, 27U, "171", "179", 260000000U);
777   Add(3, 28U, "191", "220", 260000000U);
778   Add(3, 29U, "221", "300", 260000000U);
779   Add(3, 30U, "750", "900", 260000000U);
780   UpdateVersionStorageInfo();
781 
782   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
783       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
784       &log_buffer_));
785   ASSERT_TRUE(compaction.get() != nullptr);
786   ASSERT_EQ(1U, compaction->num_input_files(0));
787   // Pick file 8 because it overlaps with 0 files on level 3.
788   ASSERT_EQ(8U, compaction->input(0, 0)->fd.GetNumber());
789   // Compaction input size * 1.1
790   ASSERT_GE(uint64_t{55000000}, compaction->OutputFilePreallocationSize());
791 }
792 
TEST_F(CompactionPickerTest,CompactionPriMinOverlapping2)793 TEST_F(CompactionPickerTest, CompactionPriMinOverlapping2) {
794   NewVersionStorage(6, kCompactionStyleLevel);
795   ioptions_.compaction_pri = kMinOverlappingRatio;
796   mutable_cf_options_.target_file_size_base = 10000000;
797   mutable_cf_options_.target_file_size_multiplier = 10;
798   mutable_cf_options_.max_bytes_for_level_base = 10 * 1024 * 1024;
799 
800   Add(2, 6U, "150", "175",
801       60000000U);  // Overlaps with file 26, 27, total size 521M
802   Add(2, 7U, "176", "200", 60000000U);  // Overlaps with file 27, 28, total size
803                                         // 520M, the smallest overlapping
804   Add(2, 8U, "201", "300",
805       60000000U);  // Overlaps with file 28, 29, total size 521M
806 
807   Add(3, 25U, "100", "110", 261000000U);
808   Add(3, 26U, "150", "170", 261000000U);
809   Add(3, 27U, "171", "179", 260000000U);
810   Add(3, 28U, "191", "220", 260000000U);
811   Add(3, 29U, "221", "300", 261000000U);
812   Add(3, 30U, "321", "400", 261000000U);
813   UpdateVersionStorageInfo();
814 
815   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
816       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
817       &log_buffer_));
818   ASSERT_TRUE(compaction.get() != nullptr);
819   ASSERT_EQ(1U, compaction->num_input_files(0));
820   // Picking file 7 because overlapping ratio is the biggest.
821   ASSERT_EQ(7U, compaction->input(0, 0)->fd.GetNumber());
822 }
823 
TEST_F(CompactionPickerTest,CompactionPriMinOverlapping3)824 TEST_F(CompactionPickerTest, CompactionPriMinOverlapping3) {
825   NewVersionStorage(6, kCompactionStyleLevel);
826   ioptions_.compaction_pri = kMinOverlappingRatio;
827   mutable_cf_options_.max_bytes_for_level_base = 10000000;
828   mutable_cf_options_.max_bytes_for_level_multiplier = 10;
829 
830   // file 7 and 8 over lap with the same file, but file 8 is smaller so
831   // it will be picked.
832   Add(2, 6U, "150", "167", 60000000U);  // Overlaps with file 26, 27
833   Add(2, 7U, "168", "169", 60000000U);  // Overlaps with file 27
834   Add(2, 8U, "201", "300", 61000000U);  // Overlaps with file 28, but the file
835                                         // itself is larger. Should be picked.
836 
837   Add(3, 26U, "160", "165", 260000000U);
838   Add(3, 27U, "166", "170", 260000000U);
839   Add(3, 28U, "180", "400", 260000000U);
840   Add(3, 29U, "401", "500", 260000000U);
841   UpdateVersionStorageInfo();
842 
843   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
844       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
845       &log_buffer_));
846   ASSERT_TRUE(compaction.get() != nullptr);
847   ASSERT_EQ(1U, compaction->num_input_files(0));
848   // Picking file 8 because overlapping ratio is the biggest.
849   ASSERT_EQ(8U, compaction->input(0, 0)->fd.GetNumber());
850 }
851 
TEST_F(CompactionPickerTest,CompactionPriMinOverlapping4)852 TEST_F(CompactionPickerTest, CompactionPriMinOverlapping4) {
853   NewVersionStorage(6, kCompactionStyleLevel);
854   ioptions_.compaction_pri = kMinOverlappingRatio;
855   mutable_cf_options_.max_bytes_for_level_base = 10000000;
856   mutable_cf_options_.max_bytes_for_level_multiplier = 10;
857 
858   // file 7 and 8 over lap with the same file, but file 8 is smaller so
859   // it will be picked.
860   // Overlaps with file 26, 27. And the file is compensated so will be
861   // picked up.
862   Add(2, 6U, "150", "167", 60000000U, 0, 100, 100, 180000000U);
863   Add(2, 7U, "168", "169", 60000000U);  // Overlaps with file 27
864   Add(2, 8U, "201", "300", 61000000U);  // Overlaps with file 28
865 
866   Add(3, 26U, "160", "165", 60000000U);
867   // Boosted file size in output level is not considered.
868   Add(3, 27U, "166", "170", 60000000U, 0, 100, 100, 260000000U);
869   Add(3, 28U, "180", "400", 60000000U);
870   Add(3, 29U, "401", "500", 60000000U);
871   UpdateVersionStorageInfo();
872 
873   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
874       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
875       &log_buffer_));
876   ASSERT_TRUE(compaction.get() != nullptr);
877   ASSERT_EQ(1U, compaction->num_input_files(0));
878   // Picking file 8 because overlapping ratio is the biggest.
879   ASSERT_EQ(6U, compaction->input(0, 0)->fd.GetNumber());
880 }
881 
882 // This test exhibits the bug where we don't properly reset parent_index in
883 // PickCompaction()
TEST_F(CompactionPickerTest,ParentIndexResetBug)884 TEST_F(CompactionPickerTest, ParentIndexResetBug) {
885   int num_levels = ioptions_.num_levels;
886   mutable_cf_options_.level0_file_num_compaction_trigger = 2;
887   mutable_cf_options_.max_bytes_for_level_base = 200;
888   NewVersionStorage(num_levels, kCompactionStyleLevel);
889   Add(0, 1U, "150", "200");       // <- marked for compaction
890   Add(1, 3U, "400", "500", 600);  // <- this one needs compacting
891   Add(2, 4U, "150", "200");
892   Add(2, 5U, "201", "210");
893   Add(2, 6U, "300", "310");
894   Add(2, 7U, "400", "500");  // <- being compacted
895 
896   vstorage_->LevelFiles(2)[3]->being_compacted = true;
897   vstorage_->LevelFiles(0)[0]->marked_for_compaction = true;
898 
899   UpdateVersionStorageInfo();
900 
901   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
902       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
903       &log_buffer_));
904 }
905 
906 // This test checks ExpandWhileOverlapping() by having overlapping user keys
907 // ranges (with different sequence numbers) in the input files.
TEST_F(CompactionPickerTest,OverlappingUserKeys)908 TEST_F(CompactionPickerTest, OverlappingUserKeys) {
909   NewVersionStorage(6, kCompactionStyleLevel);
910   ioptions_.compaction_pri = kByCompensatedSize;
911 
912   Add(1, 1U, "100", "150", 1U);
913   // Overlapping user keys
914   Add(1, 2U, "200", "400", 1U);
915   Add(1, 3U, "400", "500", 1000000000U, 0, 0);
916   Add(2, 4U, "600", "700", 1U);
917   UpdateVersionStorageInfo();
918 
919   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
920       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
921       &log_buffer_));
922   ASSERT_TRUE(compaction.get() != nullptr);
923   ASSERT_EQ(1U, compaction->num_input_levels());
924   ASSERT_EQ(2U, compaction->num_input_files(0));
925   ASSERT_EQ(2U, compaction->input(0, 0)->fd.GetNumber());
926   ASSERT_EQ(3U, compaction->input(0, 1)->fd.GetNumber());
927 }
928 
TEST_F(CompactionPickerTest,OverlappingUserKeys2)929 TEST_F(CompactionPickerTest, OverlappingUserKeys2) {
930   NewVersionStorage(6, kCompactionStyleLevel);
931   // Overlapping user keys on same level and output level
932   Add(1, 1U, "200", "400", 1000000000U);
933   Add(1, 2U, "400", "500", 1U, 0, 0);
934   Add(2, 3U, "000", "100", 1U);
935   Add(2, 4U, "100", "600", 1U, 0, 0);
936   Add(2, 5U, "600", "700", 1U, 0, 0);
937   UpdateVersionStorageInfo();
938 
939   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
940       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
941       &log_buffer_));
942   ASSERT_TRUE(compaction.get() != nullptr);
943   ASSERT_EQ(2U, compaction->num_input_levels());
944   ASSERT_EQ(2U, compaction->num_input_files(0));
945   ASSERT_EQ(3U, compaction->num_input_files(1));
946   ASSERT_EQ(1U, compaction->input(0, 0)->fd.GetNumber());
947   ASSERT_EQ(2U, compaction->input(0, 1)->fd.GetNumber());
948   ASSERT_EQ(3U, compaction->input(1, 0)->fd.GetNumber());
949   ASSERT_EQ(4U, compaction->input(1, 1)->fd.GetNumber());
950   ASSERT_EQ(5U, compaction->input(1, 2)->fd.GetNumber());
951 }
952 
TEST_F(CompactionPickerTest,OverlappingUserKeys3)953 TEST_F(CompactionPickerTest, OverlappingUserKeys3) {
954   NewVersionStorage(6, kCompactionStyleLevel);
955   // Chain of overlapping user key ranges (forces ExpandWhileOverlapping() to
956   // expand multiple times)
957   Add(1, 1U, "100", "150", 1U);
958   Add(1, 2U, "150", "200", 1U, 0, 0);
959   Add(1, 3U, "200", "250", 1000000000U, 0, 0);
960   Add(1, 4U, "250", "300", 1U, 0, 0);
961   Add(1, 5U, "300", "350", 1U, 0, 0);
962   // Output level overlaps with the beginning and the end of the chain
963   Add(2, 6U, "050", "100", 1U);
964   Add(2, 7U, "350", "400", 1U);
965   UpdateVersionStorageInfo();
966 
967   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
968       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
969       &log_buffer_));
970   ASSERT_TRUE(compaction.get() != nullptr);
971   ASSERT_EQ(2U, compaction->num_input_levels());
972   ASSERT_EQ(5U, compaction->num_input_files(0));
973   ASSERT_EQ(2U, compaction->num_input_files(1));
974   ASSERT_EQ(1U, compaction->input(0, 0)->fd.GetNumber());
975   ASSERT_EQ(2U, compaction->input(0, 1)->fd.GetNumber());
976   ASSERT_EQ(3U, compaction->input(0, 2)->fd.GetNumber());
977   ASSERT_EQ(4U, compaction->input(0, 3)->fd.GetNumber());
978   ASSERT_EQ(5U, compaction->input(0, 4)->fd.GetNumber());
979   ASSERT_EQ(6U, compaction->input(1, 0)->fd.GetNumber());
980   ASSERT_EQ(7U, compaction->input(1, 1)->fd.GetNumber());
981 }
982 
TEST_F(CompactionPickerTest,OverlappingUserKeys4)983 TEST_F(CompactionPickerTest, OverlappingUserKeys4) {
984   NewVersionStorage(6, kCompactionStyleLevel);
985   mutable_cf_options_.max_bytes_for_level_base = 1000000;
986 
987   Add(1, 1U, "100", "150", 1U);
988   Add(1, 2U, "150", "199", 1U, 0, 0);
989   Add(1, 3U, "200", "250", 1100000U, 0, 0);
990   Add(1, 4U, "251", "300", 1U, 0, 0);
991   Add(1, 5U, "300", "350", 1U, 0, 0);
992 
993   Add(2, 6U, "100", "115", 1U);
994   Add(2, 7U, "125", "325", 1U);
995   Add(2, 8U, "350", "400", 1U);
996   UpdateVersionStorageInfo();
997 
998   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
999       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
1000       &log_buffer_));
1001   ASSERT_TRUE(compaction.get() != nullptr);
1002   ASSERT_EQ(2U, compaction->num_input_levels());
1003   ASSERT_EQ(1U, compaction->num_input_files(0));
1004   ASSERT_EQ(1U, compaction->num_input_files(1));
1005   ASSERT_EQ(3U, compaction->input(0, 0)->fd.GetNumber());
1006   ASSERT_EQ(7U, compaction->input(1, 0)->fd.GetNumber());
1007 }
1008 
TEST_F(CompactionPickerTest,OverlappingUserKeys5)1009 TEST_F(CompactionPickerTest, OverlappingUserKeys5) {
1010   NewVersionStorage(6, kCompactionStyleLevel);
1011   // Overlapping user keys on same level and output level
1012   Add(1, 1U, "200", "400", 1000000000U);
1013   Add(1, 2U, "400", "500", 1U, 0, 0);
1014   Add(2, 3U, "000", "100", 1U);
1015   Add(2, 4U, "100", "600", 1U, 0, 0);
1016   Add(2, 5U, "600", "700", 1U, 0, 0);
1017 
1018   vstorage_->LevelFiles(2)[2]->being_compacted = true;
1019 
1020   UpdateVersionStorageInfo();
1021 
1022   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
1023       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
1024       &log_buffer_));
1025   ASSERT_TRUE(compaction.get() == nullptr);
1026 }
1027 
TEST_F(CompactionPickerTest,OverlappingUserKeys6)1028 TEST_F(CompactionPickerTest, OverlappingUserKeys6) {
1029   NewVersionStorage(6, kCompactionStyleLevel);
1030   // Overlapping user keys on same level and output level
1031   Add(1, 1U, "200", "400", 1U, 0, 0);
1032   Add(1, 2U, "401", "500", 1U, 0, 0);
1033   Add(2, 3U, "000", "100", 1U);
1034   Add(2, 4U, "100", "300", 1U, 0, 0);
1035   Add(2, 5U, "305", "450", 1U, 0, 0);
1036   Add(2, 6U, "460", "600", 1U, 0, 0);
1037   Add(2, 7U, "600", "700", 1U, 0, 0);
1038 
1039   vstorage_->LevelFiles(1)[0]->marked_for_compaction = true;
1040   vstorage_->LevelFiles(1)[1]->marked_for_compaction = true;
1041 
1042   UpdateVersionStorageInfo();
1043 
1044   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
1045       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
1046       &log_buffer_));
1047   ASSERT_TRUE(compaction.get() != nullptr);
1048   ASSERT_EQ(2U, compaction->num_input_levels());
1049   ASSERT_EQ(1U, compaction->num_input_files(0));
1050   ASSERT_EQ(3U, compaction->num_input_files(1));
1051 }
1052 
TEST_F(CompactionPickerTest,OverlappingUserKeys7)1053 TEST_F(CompactionPickerTest, OverlappingUserKeys7) {
1054   NewVersionStorage(6, kCompactionStyleLevel);
1055   mutable_cf_options_.max_compaction_bytes = 100000000000u;
1056   // Overlapping user keys on same level and output level
1057   Add(1, 1U, "200", "400", 1U, 0, 0);
1058   Add(1, 2U, "401", "500", 1000000000U, 0, 0);
1059   Add(2, 3U, "100", "250", 1U);
1060   Add(2, 4U, "300", "600", 1U, 0, 0);
1061   Add(2, 5U, "600", "800", 1U, 0, 0);
1062 
1063   UpdateVersionStorageInfo();
1064 
1065   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
1066       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
1067       &log_buffer_));
1068   ASSERT_TRUE(compaction.get() != nullptr);
1069   ASSERT_EQ(2U, compaction->num_input_levels());
1070   ASSERT_GE(1U, compaction->num_input_files(0));
1071   ASSERT_GE(2U, compaction->num_input_files(1));
1072   // File 5 has to be included in the compaction
1073   ASSERT_EQ(5U, compaction->inputs(1)->back()->fd.GetNumber());
1074 }
1075 
TEST_F(CompactionPickerTest,OverlappingUserKeys8)1076 TEST_F(CompactionPickerTest, OverlappingUserKeys8) {
1077   NewVersionStorage(6, kCompactionStyleLevel);
1078   mutable_cf_options_.max_compaction_bytes = 100000000000u;
1079   // grow the number of inputs in "level" without
1080   // changing the number of "level+1" files we pick up
1081   // Expand input level as much as possible
1082   // no overlapping case
1083   Add(1, 1U, "101", "150", 1U);
1084   Add(1, 2U, "151", "200", 1U);
1085   Add(1, 3U, "201", "300", 1000000000U);
1086   Add(1, 4U, "301", "400", 1U);
1087   Add(1, 5U, "401", "500", 1U);
1088   Add(2, 6U, "150", "200", 1U);
1089   Add(2, 7U, "200", "450", 1U, 0, 0);
1090   Add(2, 8U, "500", "600", 1U);
1091 
1092   UpdateVersionStorageInfo();
1093 
1094   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
1095       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
1096       &log_buffer_));
1097   ASSERT_TRUE(compaction.get() != nullptr);
1098   ASSERT_EQ(2U, compaction->num_input_levels());
1099   ASSERT_EQ(3U, compaction->num_input_files(0));
1100   ASSERT_EQ(2U, compaction->num_input_files(1));
1101   ASSERT_EQ(2U, compaction->input(0, 0)->fd.GetNumber());
1102   ASSERT_EQ(3U, compaction->input(0, 1)->fd.GetNumber());
1103   ASSERT_EQ(4U, compaction->input(0, 2)->fd.GetNumber());
1104   ASSERT_EQ(6U, compaction->input(1, 0)->fd.GetNumber());
1105   ASSERT_EQ(7U, compaction->input(1, 1)->fd.GetNumber());
1106 }
1107 
TEST_F(CompactionPickerTest,OverlappingUserKeys9)1108 TEST_F(CompactionPickerTest, OverlappingUserKeys9) {
1109   NewVersionStorage(6, kCompactionStyleLevel);
1110   mutable_cf_options_.max_compaction_bytes = 100000000000u;
1111   // grow the number of inputs in "level" without
1112   // changing the number of "level+1" files we pick up
1113   // Expand input level as much as possible
1114   // overlapping case
1115   Add(1, 1U, "121", "150", 1U);
1116   Add(1, 2U, "151", "200", 1U);
1117   Add(1, 3U, "201", "300", 1000000000U);
1118   Add(1, 4U, "301", "400", 1U);
1119   Add(1, 5U, "401", "500", 1U);
1120   Add(2, 6U, "100", "120", 1U);
1121   Add(2, 7U, "150", "200", 1U);
1122   Add(2, 8U, "200", "450", 1U, 0, 0);
1123   Add(2, 9U, "501", "600", 1U);
1124 
1125   UpdateVersionStorageInfo();
1126 
1127   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
1128       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
1129       &log_buffer_));
1130   ASSERT_TRUE(compaction.get() != nullptr);
1131   ASSERT_EQ(2U, compaction->num_input_levels());
1132   ASSERT_EQ(5U, compaction->num_input_files(0));
1133   ASSERT_EQ(2U, compaction->num_input_files(1));
1134   ASSERT_EQ(1U, compaction->input(0, 0)->fd.GetNumber());
1135   ASSERT_EQ(2U, compaction->input(0, 1)->fd.GetNumber());
1136   ASSERT_EQ(3U, compaction->input(0, 2)->fd.GetNumber());
1137   ASSERT_EQ(4U, compaction->input(0, 3)->fd.GetNumber());
1138   ASSERT_EQ(7U, compaction->input(1, 0)->fd.GetNumber());
1139   ASSERT_EQ(8U, compaction->input(1, 1)->fd.GetNumber());
1140 }
1141 
TEST_F(CompactionPickerTest,OverlappingUserKeys10)1142 TEST_F(CompactionPickerTest, OverlappingUserKeys10) {
1143   // Locked file encountered when pulling in extra input-level files with same
1144   // user keys. Verify we pick the next-best file from the same input level.
1145   NewVersionStorage(6, kCompactionStyleLevel);
1146   mutable_cf_options_.max_compaction_bytes = 100000000000u;
1147 
1148   // file_number 2U is largest and thus first choice. But it overlaps with
1149   // file_number 1U which is being compacted. So instead we pick the next-
1150   // biggest file, 3U, which is eligible for compaction.
1151   Add(1 /* level */, 1U /* file_number */, "100" /* smallest */,
1152       "150" /* largest */, 1U /* file_size */);
1153   file_map_[1U].first->being_compacted = true;
1154   Add(1 /* level */, 2U /* file_number */, "150" /* smallest */,
1155       "200" /* largest */, 1000000000U /* file_size */, 0 /* smallest_seq */,
1156       0 /* largest_seq */);
1157   Add(1 /* level */, 3U /* file_number */, "201" /* smallest */,
1158       "250" /* largest */, 900000000U /* file_size */);
1159   Add(2 /* level */, 4U /* file_number */, "100" /* smallest */,
1160       "150" /* largest */, 1U /* file_size */);
1161   Add(2 /* level */, 5U /* file_number */, "151" /* smallest */,
1162       "200" /* largest */, 1U /* file_size */);
1163   Add(2 /* level */, 6U /* file_number */, "201" /* smallest */,
1164       "250" /* largest */, 1U /* file_size */);
1165 
1166   UpdateVersionStorageInfo();
1167 
1168   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
1169       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
1170       &log_buffer_));
1171   ASSERT_TRUE(compaction.get() != nullptr);
1172   ASSERT_EQ(2U, compaction->num_input_levels());
1173   ASSERT_EQ(1U, compaction->num_input_files(0));
1174   ASSERT_EQ(1U, compaction->num_input_files(1));
1175   ASSERT_EQ(3U, compaction->input(0, 0)->fd.GetNumber());
1176   ASSERT_EQ(6U, compaction->input(1, 0)->fd.GetNumber());
1177 }
1178 
TEST_F(CompactionPickerTest,OverlappingUserKeys11)1179 TEST_F(CompactionPickerTest, OverlappingUserKeys11) {
1180   // Locked file encountered when pulling in extra output-level files with same
1181   // user keys. Expected to skip that compaction and pick the next-best choice.
1182   NewVersionStorage(6, kCompactionStyleLevel);
1183   mutable_cf_options_.max_compaction_bytes = 100000000000u;
1184 
1185   // score(L1) = 3.7
1186   // score(L2) = 1.85
1187   // There is no eligible file in L1 to compact since both candidates pull in
1188   // file_number 5U, which overlaps with a file pending compaction (6U). The
1189   // first eligible compaction is from L2->L3.
1190   Add(1 /* level */, 2U /* file_number */, "151" /* smallest */,
1191       "200" /* largest */, 1000000000U /* file_size */);
1192   Add(1 /* level */, 3U /* file_number */, "201" /* smallest */,
1193       "250" /* largest */, 1U /* file_size */);
1194   Add(2 /* level */, 4U /* file_number */, "100" /* smallest */,
1195       "149" /* largest */, 5000000000U /* file_size */);
1196   Add(2 /* level */, 5U /* file_number */, "150" /* smallest */,
1197       "201" /* largest */, 1U /* file_size */);
1198   Add(2 /* level */, 6U /* file_number */, "201" /* smallest */,
1199       "249" /* largest */, 1U /* file_size */, 0 /* smallest_seq */,
1200       0 /* largest_seq */);
1201   file_map_[6U].first->being_compacted = true;
1202   Add(3 /* level */, 7U /* file_number */, "100" /* smallest */,
1203       "149" /* largest */, 1U /* file_size */);
1204 
1205   UpdateVersionStorageInfo();
1206 
1207   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
1208       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
1209       &log_buffer_));
1210   ASSERT_TRUE(compaction.get() != nullptr);
1211   ASSERT_EQ(2U, compaction->num_input_levels());
1212   ASSERT_EQ(1U, compaction->num_input_files(0));
1213   ASSERT_EQ(1U, compaction->num_input_files(1));
1214   ASSERT_EQ(4U, compaction->input(0, 0)->fd.GetNumber());
1215   ASSERT_EQ(7U, compaction->input(1, 0)->fd.GetNumber());
1216 }
1217 
TEST_F(CompactionPickerTest,NotScheduleL1IfL0WithHigherPri1)1218 TEST_F(CompactionPickerTest, NotScheduleL1IfL0WithHigherPri1) {
1219   NewVersionStorage(6, kCompactionStyleLevel);
1220   mutable_cf_options_.level0_file_num_compaction_trigger = 2;
1221   mutable_cf_options_.max_bytes_for_level_base = 900000000U;
1222 
1223   // 6 L0 files, score 3.
1224   Add(0, 1U, "000", "400", 1U);
1225   Add(0, 2U, "001", "400", 1U, 0, 0);
1226   Add(0, 3U, "001", "400", 1000000000U, 0, 0);
1227   Add(0, 31U, "001", "400", 1000000000U, 0, 0);
1228   Add(0, 32U, "001", "400", 1000000000U, 0, 0);
1229   Add(0, 33U, "001", "400", 1000000000U, 0, 0);
1230 
1231   // L1 total size 2GB, score 2.2. If one file being compacted, score 1.1.
1232   Add(1, 4U, "050", "300", 1000000000U, 0, 0);
1233   file_map_[4u].first->being_compacted = true;
1234   Add(1, 5U, "301", "350", 1000000000U, 0, 0);
1235 
1236   // Output level overlaps with the beginning and the end of the chain
1237   Add(2, 6U, "050", "100", 1U);
1238   Add(2, 7U, "300", "400", 1U);
1239 
1240   // No compaction should be scheduled, if L0 has higher priority than L1
1241   // but L0->L1 compaction is blocked by a file in L1 being compacted.
1242   UpdateVersionStorageInfo();
1243   ASSERT_EQ(0, vstorage_->CompactionScoreLevel(0));
1244   ASSERT_EQ(1, vstorage_->CompactionScoreLevel(1));
1245   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
1246       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
1247       &log_buffer_));
1248   ASSERT_TRUE(compaction.get() == nullptr);
1249 }
1250 
TEST_F(CompactionPickerTest,NotScheduleL1IfL0WithHigherPri2)1251 TEST_F(CompactionPickerTest, NotScheduleL1IfL0WithHigherPri2) {
1252   NewVersionStorage(6, kCompactionStyleLevel);
1253   mutable_cf_options_.level0_file_num_compaction_trigger = 2;
1254   mutable_cf_options_.max_bytes_for_level_base = 900000000U;
1255 
1256   // 6 L0 files, score 3.
1257   Add(0, 1U, "000", "400", 1U);
1258   Add(0, 2U, "001", "400", 1U, 0, 0);
1259   Add(0, 3U, "001", "400", 1000000000U, 0, 0);
1260   Add(0, 31U, "001", "400", 1000000000U, 0, 0);
1261   Add(0, 32U, "001", "400", 1000000000U, 0, 0);
1262   Add(0, 33U, "001", "400", 1000000000U, 0, 0);
1263 
1264   // L1 total size 2GB, score 2.2. If one file being compacted, score 1.1.
1265   Add(1, 4U, "050", "300", 1000000000U, 0, 0);
1266   Add(1, 5U, "301", "350", 1000000000U, 0, 0);
1267 
1268   // Output level overlaps with the beginning and the end of the chain
1269   Add(2, 6U, "050", "100", 1U);
1270   Add(2, 7U, "300", "400", 1U);
1271 
1272   // If no file in L1 being compacted, L0->L1 compaction will be scheduled.
1273   UpdateVersionStorageInfo();  // being_compacted flag is cleared here.
1274   ASSERT_EQ(0, vstorage_->CompactionScoreLevel(0));
1275   ASSERT_EQ(1, vstorage_->CompactionScoreLevel(1));
1276   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
1277       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
1278       &log_buffer_));
1279   ASSERT_TRUE(compaction.get() != nullptr);
1280 }
1281 
TEST_F(CompactionPickerTest,NotScheduleL1IfL0WithHigherPri3)1282 TEST_F(CompactionPickerTest, NotScheduleL1IfL0WithHigherPri3) {
1283   NewVersionStorage(6, kCompactionStyleLevel);
1284   mutable_cf_options_.level0_file_num_compaction_trigger = 2;
1285   mutable_cf_options_.max_bytes_for_level_base = 900000000U;
1286 
1287   // 6 L0 files, score 3.
1288   Add(0, 1U, "000", "400", 1U);
1289   Add(0, 2U, "001", "400", 1U, 0, 0);
1290   Add(0, 3U, "001", "400", 1000000000U, 0, 0);
1291   Add(0, 31U, "001", "400", 1000000000U, 0, 0);
1292   Add(0, 32U, "001", "400", 1000000000U, 0, 0);
1293   Add(0, 33U, "001", "400", 1000000000U, 0, 0);
1294 
1295   // L1 score more than 6.
1296   Add(1, 4U, "050", "300", 1000000000U, 0, 0);
1297   file_map_[4u].first->being_compacted = true;
1298   Add(1, 5U, "301", "350", 1000000000U, 0, 0);
1299   Add(1, 51U, "351", "400", 6000000000U, 0, 0);
1300 
1301   // Output level overlaps with the beginning and the end of the chain
1302   Add(2, 6U, "050", "100", 1U);
1303   Add(2, 7U, "300", "400", 1U);
1304 
1305   // If score in L1 is larger than L0, L1 compaction goes through despite
1306   // there is pending L0 compaction.
1307   UpdateVersionStorageInfo();
1308   ASSERT_EQ(1, vstorage_->CompactionScoreLevel(0));
1309   ASSERT_EQ(0, vstorage_->CompactionScoreLevel(1));
1310   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
1311       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
1312       &log_buffer_));
1313   ASSERT_TRUE(compaction.get() != nullptr);
1314 }
1315 
TEST_F(CompactionPickerTest,EstimateCompactionBytesNeeded1)1316 TEST_F(CompactionPickerTest, EstimateCompactionBytesNeeded1) {
1317   int num_levels = ioptions_.num_levels;
1318   ioptions_.level_compaction_dynamic_level_bytes = false;
1319   mutable_cf_options_.level0_file_num_compaction_trigger = 4;
1320   mutable_cf_options_.max_bytes_for_level_base = 1000;
1321   mutable_cf_options_.max_bytes_for_level_multiplier = 10;
1322   NewVersionStorage(num_levels, kCompactionStyleLevel);
1323   Add(0, 1U, "150", "200", 200);
1324   Add(0, 2U, "150", "200", 200);
1325   Add(0, 3U, "150", "200", 200);
1326   // Level 1 is over target by 200
1327   Add(1, 4U, "400", "500", 600);
1328   Add(1, 5U, "600", "700", 600);
1329   // Level 2 is less than target 10000 even added size of level 1
1330   // Size ratio of L2/L1 is 9600 / 1200 = 8
1331   Add(2, 6U, "150", "200", 2500);
1332   Add(2, 7U, "201", "210", 2000);
1333   Add(2, 8U, "300", "310", 2600);
1334   Add(2, 9U, "400", "500", 2500);
1335   // Level 3 exceeds target 100,000 of 1000
1336   Add(3, 10U, "400", "500", 101000);
1337   // Level 4 exceeds target 1,000,000 by 900 after adding size from level 3
1338   // Size ratio L4/L3 is 9.9
1339   // After merge from L3, L4 size is 1000900
1340   Add(4, 11U, "400", "500", 999900);
1341   Add(5, 12U, "400", "500", 8007200);
1342 
1343   UpdateVersionStorageInfo();
1344 
1345   ASSERT_EQ(200u * 9u + 10900u + 900u * 9,
1346             vstorage_->estimated_compaction_needed_bytes());
1347 }
1348 
TEST_F(CompactionPickerTest,EstimateCompactionBytesNeeded2)1349 TEST_F(CompactionPickerTest, EstimateCompactionBytesNeeded2) {
1350   int num_levels = ioptions_.num_levels;
1351   ioptions_.level_compaction_dynamic_level_bytes = false;
1352   mutable_cf_options_.level0_file_num_compaction_trigger = 3;
1353   mutable_cf_options_.max_bytes_for_level_base = 1000;
1354   mutable_cf_options_.max_bytes_for_level_multiplier = 10;
1355   NewVersionStorage(num_levels, kCompactionStyleLevel);
1356   Add(0, 1U, "150", "200", 200);
1357   Add(0, 2U, "150", "200", 200);
1358   Add(0, 4U, "150", "200", 200);
1359   Add(0, 5U, "150", "200", 200);
1360   Add(0, 6U, "150", "200", 200);
1361   // Level 1 size will be 1400 after merging with L0
1362   Add(1, 7U, "400", "500", 200);
1363   Add(1, 8U, "600", "700", 200);
1364   // Level 2 is less than target 10000 even added size of level 1
1365   Add(2, 9U, "150", "200", 9100);
1366   // Level 3 over the target, but since level 4 is empty, we assume it will be
1367   // a trivial move.
1368   Add(3, 10U, "400", "500", 101000);
1369 
1370   UpdateVersionStorageInfo();
1371 
1372   // estimated L1->L2 merge: 400 * (9100.0 / 1400.0 + 1.0)
1373   ASSERT_EQ(1400u + 3000u, vstorage_->estimated_compaction_needed_bytes());
1374 }
1375 
TEST_F(CompactionPickerTest,EstimateCompactionBytesNeeded3)1376 TEST_F(CompactionPickerTest, EstimateCompactionBytesNeeded3) {
1377   int num_levels = ioptions_.num_levels;
1378   ioptions_.level_compaction_dynamic_level_bytes = false;
1379   mutable_cf_options_.level0_file_num_compaction_trigger = 3;
1380   mutable_cf_options_.max_bytes_for_level_base = 1000;
1381   mutable_cf_options_.max_bytes_for_level_multiplier = 10;
1382   NewVersionStorage(num_levels, kCompactionStyleLevel);
1383   Add(0, 1U, "150", "200", 2000);
1384   Add(0, 2U, "150", "200", 2000);
1385   Add(0, 4U, "150", "200", 2000);
1386   Add(0, 5U, "150", "200", 2000);
1387   Add(0, 6U, "150", "200", 1000);
1388   // Level 1 size will be 10000 after merging with L0
1389   Add(1, 7U, "400", "500", 500);
1390   Add(1, 8U, "600", "700", 500);
1391 
1392   Add(2, 9U, "150", "200", 10000);
1393 
1394   UpdateVersionStorageInfo();
1395 
1396   ASSERT_EQ(10000u + 18000u, vstorage_->estimated_compaction_needed_bytes());
1397 }
1398 
TEST_F(CompactionPickerTest,EstimateCompactionBytesNeededDynamicLevel)1399 TEST_F(CompactionPickerTest, EstimateCompactionBytesNeededDynamicLevel) {
1400   int num_levels = ioptions_.num_levels;
1401   ioptions_.level_compaction_dynamic_level_bytes = true;
1402   mutable_cf_options_.level0_file_num_compaction_trigger = 3;
1403   mutable_cf_options_.max_bytes_for_level_base = 1000;
1404   mutable_cf_options_.max_bytes_for_level_multiplier = 10;
1405   NewVersionStorage(num_levels, kCompactionStyleLevel);
1406 
1407   // Set Last level size 50000
1408   // num_levels - 1 target 5000
1409   // num_levels - 2 is base level with target 1000 (rounded up to
1410   // max_bytes_for_level_base).
1411   Add(num_levels - 1, 10U, "400", "500", 50000);
1412 
1413   Add(0, 1U, "150", "200", 200);
1414   Add(0, 2U, "150", "200", 200);
1415   Add(0, 4U, "150", "200", 200);
1416   Add(0, 5U, "150", "200", 200);
1417   Add(0, 6U, "150", "200", 200);
1418   // num_levels - 3 is over target by 100 + 1000
1419   Add(num_levels - 3, 7U, "400", "500", 550);
1420   Add(num_levels - 3, 8U, "600", "700", 550);
1421   // num_levels - 2 is over target by 1100 + 200
1422   Add(num_levels - 2, 9U, "150", "200", 5200);
1423 
1424   UpdateVersionStorageInfo();
1425 
1426   // Merging to the second last level: (5200 / 2100 + 1) * 1100
1427   // Merging to the last level: (50000 / 6300 + 1) * 1300
1428   ASSERT_EQ(2100u + 3823u + 11617u,
1429             vstorage_->estimated_compaction_needed_bytes());
1430 }
1431 
TEST_F(CompactionPickerTest,IsBottommostLevelTest)1432 TEST_F(CompactionPickerTest, IsBottommostLevelTest) {
1433   // case 1: Higher levels are empty
1434   NewVersionStorage(6, kCompactionStyleLevel);
1435   Add(0, 1U, "a", "m");
1436   Add(0, 2U, "c", "z");
1437   Add(1, 3U, "d", "e");
1438   Add(1, 4U, "l", "p");
1439   Add(2, 5U, "g", "i");
1440   Add(2, 6U, "x", "z");
1441   UpdateVersionStorageInfo();
1442   SetCompactionInputFilesLevels(2, 1);
1443   AddToCompactionFiles(3U);
1444   AddToCompactionFiles(5U);
1445   bool result =
1446       Compaction::TEST_IsBottommostLevel(2, vstorage_.get(), input_files_);
1447   ASSERT_TRUE(result);
1448 
1449   // case 2: Higher levels have no overlap
1450   NewVersionStorage(6, kCompactionStyleLevel);
1451   Add(0, 1U, "a", "m");
1452   Add(0, 2U, "c", "z");
1453   Add(1, 3U, "d", "e");
1454   Add(1, 4U, "l", "p");
1455   Add(2, 5U, "g", "i");
1456   Add(2, 6U, "x", "z");
1457   Add(3, 7U, "k", "p");
1458   Add(3, 8U, "t", "w");
1459   Add(4, 9U, "a", "b");
1460   Add(5, 10U, "c", "cc");
1461   UpdateVersionStorageInfo();
1462   SetCompactionInputFilesLevels(2, 1);
1463   AddToCompactionFiles(3U);
1464   AddToCompactionFiles(5U);
1465   result = Compaction::TEST_IsBottommostLevel(2, vstorage_.get(), input_files_);
1466   ASSERT_TRUE(result);
1467 
1468   // case 3.1: Higher levels (level 3) have overlap
1469   NewVersionStorage(6, kCompactionStyleLevel);
1470   Add(0, 1U, "a", "m");
1471   Add(0, 2U, "c", "z");
1472   Add(1, 3U, "d", "e");
1473   Add(1, 4U, "l", "p");
1474   Add(2, 5U, "g", "i");
1475   Add(2, 6U, "x", "z");
1476   Add(3, 7U, "e", "g");
1477   Add(3, 8U, "h", "k");
1478   Add(4, 9U, "a", "b");
1479   Add(5, 10U, "c", "cc");
1480   UpdateVersionStorageInfo();
1481   SetCompactionInputFilesLevels(2, 1);
1482   AddToCompactionFiles(3U);
1483   AddToCompactionFiles(5U);
1484   result = Compaction::TEST_IsBottommostLevel(2, vstorage_.get(), input_files_);
1485   ASSERT_FALSE(result);
1486 
1487   // case 3.2: Higher levels (level 5) have overlap
1488   DeleteVersionStorage();
1489   NewVersionStorage(6, kCompactionStyleLevel);
1490   Add(0, 1U, "a", "m");
1491   Add(0, 2U, "c", "z");
1492   Add(1, 3U, "d", "e");
1493   Add(1, 4U, "l", "p");
1494   Add(2, 5U, "g", "i");
1495   Add(2, 6U, "x", "z");
1496   Add(3, 7U, "j", "k");
1497   Add(3, 8U, "l", "m");
1498   Add(4, 9U, "a", "b");
1499   Add(5, 10U, "c", "cc");
1500   Add(5, 11U, "h", "k");
1501   Add(5, 12U, "y", "yy");
1502   Add(5, 13U, "z", "zz");
1503   UpdateVersionStorageInfo();
1504   SetCompactionInputFilesLevels(2, 1);
1505   AddToCompactionFiles(3U);
1506   AddToCompactionFiles(5U);
1507   result = Compaction::TEST_IsBottommostLevel(2, vstorage_.get(), input_files_);
1508   ASSERT_FALSE(result);
1509 
1510   // case 3.3: Higher levels (level 5) have overlap, but it's only overlapping
1511   // one key ("d")
1512   NewVersionStorage(6, kCompactionStyleLevel);
1513   Add(0, 1U, "a", "m");
1514   Add(0, 2U, "c", "z");
1515   Add(1, 3U, "d", "e");
1516   Add(1, 4U, "l", "p");
1517   Add(2, 5U, "g", "i");
1518   Add(2, 6U, "x", "z");
1519   Add(3, 7U, "j", "k");
1520   Add(3, 8U, "l", "m");
1521   Add(4, 9U, "a", "b");
1522   Add(5, 10U, "c", "cc");
1523   Add(5, 11U, "ccc", "d");
1524   Add(5, 12U, "y", "yy");
1525   Add(5, 13U, "z", "zz");
1526   UpdateVersionStorageInfo();
1527   SetCompactionInputFilesLevels(2, 1);
1528   AddToCompactionFiles(3U);
1529   AddToCompactionFiles(5U);
1530   result = Compaction::TEST_IsBottommostLevel(2, vstorage_.get(), input_files_);
1531   ASSERT_FALSE(result);
1532 
1533   // Level 0 files overlap
1534   NewVersionStorage(6, kCompactionStyleLevel);
1535   Add(0, 1U, "s", "t");
1536   Add(0, 2U, "a", "m");
1537   Add(0, 3U, "b", "z");
1538   Add(0, 4U, "e", "f");
1539   Add(5, 10U, "y", "z");
1540   UpdateVersionStorageInfo();
1541   SetCompactionInputFilesLevels(1, 0);
1542   AddToCompactionFiles(1U);
1543   AddToCompactionFiles(2U);
1544   AddToCompactionFiles(3U);
1545   AddToCompactionFiles(4U);
1546   result = Compaction::TEST_IsBottommostLevel(2, vstorage_.get(), input_files_);
1547   ASSERT_FALSE(result);
1548 
1549   // Level 0 files don't overlap
1550   NewVersionStorage(6, kCompactionStyleLevel);
1551   Add(0, 1U, "s", "t");
1552   Add(0, 2U, "a", "m");
1553   Add(0, 3U, "b", "k");
1554   Add(0, 4U, "e", "f");
1555   Add(5, 10U, "y", "z");
1556   UpdateVersionStorageInfo();
1557   SetCompactionInputFilesLevels(1, 0);
1558   AddToCompactionFiles(1U);
1559   AddToCompactionFiles(2U);
1560   AddToCompactionFiles(3U);
1561   AddToCompactionFiles(4U);
1562   result = Compaction::TEST_IsBottommostLevel(2, vstorage_.get(), input_files_);
1563   ASSERT_TRUE(result);
1564 
1565   // Level 1 files overlap
1566   NewVersionStorage(6, kCompactionStyleLevel);
1567   Add(0, 1U, "s", "t");
1568   Add(0, 2U, "a", "m");
1569   Add(0, 3U, "b", "k");
1570   Add(0, 4U, "e", "f");
1571   Add(1, 5U, "a", "m");
1572   Add(1, 6U, "n", "o");
1573   Add(1, 7U, "w", "y");
1574   Add(5, 10U, "y", "z");
1575   UpdateVersionStorageInfo();
1576   SetCompactionInputFilesLevels(2, 0);
1577   AddToCompactionFiles(1U);
1578   AddToCompactionFiles(2U);
1579   AddToCompactionFiles(3U);
1580   AddToCompactionFiles(4U);
1581   AddToCompactionFiles(5U);
1582   AddToCompactionFiles(6U);
1583   AddToCompactionFiles(7U);
1584   result = Compaction::TEST_IsBottommostLevel(2, vstorage_.get(), input_files_);
1585   ASSERT_FALSE(result);
1586 
1587   DeleteVersionStorage();
1588 }
1589 
TEST_F(CompactionPickerTest,MaxCompactionBytesHit)1590 TEST_F(CompactionPickerTest, MaxCompactionBytesHit) {
1591   mutable_cf_options_.max_bytes_for_level_base = 1000000u;
1592   mutable_cf_options_.max_compaction_bytes = 800000u;
1593   ioptions_.level_compaction_dynamic_level_bytes = false;
1594   NewVersionStorage(6, kCompactionStyleLevel);
1595   // A compaction should be triggered and pick file 2 and 5.
1596   // It can expand because adding file 1 and 3, the compaction size will
1597   // exceed mutable_cf_options_.max_bytes_for_level_base.
1598   Add(1, 1U, "100", "150", 300000U);
1599   Add(1, 2U, "151", "200", 300001U, 0, 0);
1600   Add(1, 3U, "201", "250", 300000U, 0, 0);
1601   Add(1, 4U, "251", "300", 300000U, 0, 0);
1602   Add(2, 5U, "100", "256", 1U);
1603   UpdateVersionStorageInfo();
1604 
1605   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
1606       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
1607       &log_buffer_));
1608   ASSERT_TRUE(compaction.get() != nullptr);
1609   ASSERT_EQ(2U, compaction->num_input_levels());
1610   ASSERT_EQ(1U, compaction->num_input_files(0));
1611   ASSERT_EQ(1U, compaction->num_input_files(1));
1612   ASSERT_EQ(2U, compaction->input(0, 0)->fd.GetNumber());
1613   ASSERT_EQ(5U, compaction->input(1, 0)->fd.GetNumber());
1614 }
1615 
TEST_F(CompactionPickerTest,MaxCompactionBytesNotHit)1616 TEST_F(CompactionPickerTest, MaxCompactionBytesNotHit) {
1617   mutable_cf_options_.max_bytes_for_level_base = 800000u;
1618   mutable_cf_options_.max_compaction_bytes = 1000000u;
1619   ioptions_.level_compaction_dynamic_level_bytes = false;
1620   NewVersionStorage(6, kCompactionStyleLevel);
1621   // A compaction should be triggered and pick file 2 and 5.
1622   // and it expands to file 1 and 3 too.
1623   Add(1, 1U, "100", "150", 300000U);
1624   Add(1, 2U, "151", "200", 300001U, 0, 0);
1625   Add(1, 3U, "201", "250", 300000U, 0, 0);
1626   Add(1, 4U, "251", "300", 300000U, 0, 0);
1627   Add(2, 5U, "000", "251", 1U);
1628   UpdateVersionStorageInfo();
1629 
1630   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
1631       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
1632       &log_buffer_));
1633   ASSERT_TRUE(compaction.get() != nullptr);
1634   ASSERT_EQ(2U, compaction->num_input_levels());
1635   ASSERT_EQ(3U, compaction->num_input_files(0));
1636   ASSERT_EQ(1U, compaction->num_input_files(1));
1637   ASSERT_EQ(1U, compaction->input(0, 0)->fd.GetNumber());
1638   ASSERT_EQ(2U, compaction->input(0, 1)->fd.GetNumber());
1639   ASSERT_EQ(3U, compaction->input(0, 2)->fd.GetNumber());
1640   ASSERT_EQ(5U, compaction->input(1, 0)->fd.GetNumber());
1641 }
1642 
TEST_F(CompactionPickerTest,IsTrivialMoveOn)1643 TEST_F(CompactionPickerTest, IsTrivialMoveOn) {
1644   mutable_cf_options_.max_bytes_for_level_base = 10000u;
1645   mutable_cf_options_.max_compaction_bytes = 10001u;
1646   ioptions_.level_compaction_dynamic_level_bytes = false;
1647   NewVersionStorage(6, kCompactionStyleLevel);
1648   // A compaction should be triggered and pick file 2
1649   Add(1, 1U, "100", "150", 3000U);
1650   Add(1, 2U, "151", "200", 3001U);
1651   Add(1, 3U, "201", "250", 3000U);
1652   Add(1, 4U, "251", "300", 3000U);
1653 
1654   Add(3, 5U, "120", "130", 7000U);
1655   Add(3, 6U, "170", "180", 7000U);
1656   Add(3, 7U, "220", "230", 7000U);
1657   Add(3, 8U, "270", "280", 7000U);
1658   UpdateVersionStorageInfo();
1659 
1660   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
1661       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
1662       &log_buffer_));
1663   ASSERT_TRUE(compaction.get() != nullptr);
1664   ASSERT_TRUE(compaction->IsTrivialMove());
1665 }
1666 
TEST_F(CompactionPickerTest,IsTrivialMoveOffSstPartitioned)1667 TEST_F(CompactionPickerTest, IsTrivialMoveOffSstPartitioned) {
1668   mutable_cf_options_.max_bytes_for_level_base = 10000u;
1669   mutable_cf_options_.max_compaction_bytes = 10001u;
1670   ioptions_.level_compaction_dynamic_level_bytes = false;
1671   ioptions_.sst_partitioner_factory = NewSstPartitionerFixedPrefixFactory(1);
1672   NewVersionStorage(6, kCompactionStyleLevel);
1673   // A compaction should be triggered and pick file 2
1674   Add(1, 1U, "100", "150", 3000U);
1675   Add(1, 2U, "151", "200", 3001U);
1676   Add(1, 3U, "201", "250", 3000U);
1677   Add(1, 4U, "251", "300", 3000U);
1678 
1679   Add(3, 5U, "120", "130", 7000U);
1680   Add(3, 6U, "170", "180", 7000U);
1681   Add(3, 7U, "220", "230", 7000U);
1682   Add(3, 8U, "270", "280", 7000U);
1683   UpdateVersionStorageInfo();
1684 
1685   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
1686       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
1687       &log_buffer_));
1688   ASSERT_TRUE(compaction.get() != nullptr);
1689   // No trivial move, because partitioning is applied
1690   ASSERT_TRUE(!compaction->IsTrivialMove());
1691 }
1692 
TEST_F(CompactionPickerTest,IsTrivialMoveOff)1693 TEST_F(CompactionPickerTest, IsTrivialMoveOff) {
1694   mutable_cf_options_.max_bytes_for_level_base = 1000000u;
1695   mutable_cf_options_.max_compaction_bytes = 10000u;
1696   ioptions_.level_compaction_dynamic_level_bytes = false;
1697   NewVersionStorage(6, kCompactionStyleLevel);
1698   // A compaction should be triggered and pick all files from level 1
1699   Add(1, 1U, "100", "150", 300000U, 0, 0);
1700   Add(1, 2U, "150", "200", 300000U, 0, 0);
1701   Add(1, 3U, "200", "250", 300000U, 0, 0);
1702   Add(1, 4U, "250", "300", 300000U, 0, 0);
1703 
1704   Add(3, 5U, "120", "130", 6000U);
1705   Add(3, 6U, "140", "150", 6000U);
1706   UpdateVersionStorageInfo();
1707 
1708   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
1709       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
1710       &log_buffer_));
1711   ASSERT_TRUE(compaction.get() != nullptr);
1712   ASSERT_FALSE(compaction->IsTrivialMove());
1713 }
1714 
TEST_F(CompactionPickerTest,CacheNextCompactionIndex)1715 TEST_F(CompactionPickerTest, CacheNextCompactionIndex) {
1716   NewVersionStorage(6, kCompactionStyleLevel);
1717   mutable_cf_options_.max_compaction_bytes = 100000000000u;
1718 
1719   Add(1 /* level */, 1U /* file_number */, "100" /* smallest */,
1720       "149" /* largest */, 1000000000U /* file_size */);
1721   file_map_[1U].first->being_compacted = true;
1722   Add(1 /* level */, 2U /* file_number */, "150" /* smallest */,
1723       "199" /* largest */, 900000000U /* file_size */);
1724   Add(1 /* level */, 3U /* file_number */, "200" /* smallest */,
1725       "249" /* largest */, 800000000U /* file_size */);
1726   Add(1 /* level */, 4U /* file_number */, "250" /* smallest */,
1727       "299" /* largest */, 700000000U /* file_size */);
1728   Add(2 /* level */, 5U /* file_number */, "150" /* smallest */,
1729       "199" /* largest */, 1U /* file_size */);
1730   file_map_[5U].first->being_compacted = true;
1731 
1732   UpdateVersionStorageInfo();
1733 
1734   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
1735       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
1736       &log_buffer_));
1737   ASSERT_TRUE(compaction.get() != nullptr);
1738   ASSERT_EQ(1U, compaction->num_input_levels());
1739   ASSERT_EQ(1U, compaction->num_input_files(0));
1740   ASSERT_EQ(0U, compaction->num_input_files(1));
1741   ASSERT_EQ(3U, compaction->input(0, 0)->fd.GetNumber());
1742   ASSERT_EQ(2, vstorage_->NextCompactionIndex(1 /* level */));
1743 
1744   compaction.reset(level_compaction_picker.PickCompaction(
1745       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
1746       &log_buffer_));
1747   ASSERT_TRUE(compaction.get() != nullptr);
1748   ASSERT_EQ(1U, compaction->num_input_levels());
1749   ASSERT_EQ(1U, compaction->num_input_files(0));
1750   ASSERT_EQ(0U, compaction->num_input_files(1));
1751   ASSERT_EQ(4U, compaction->input(0, 0)->fd.GetNumber());
1752   ASSERT_EQ(3, vstorage_->NextCompactionIndex(1 /* level */));
1753 
1754   compaction.reset(level_compaction_picker.PickCompaction(
1755       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
1756       &log_buffer_));
1757   ASSERT_TRUE(compaction.get() == nullptr);
1758   ASSERT_EQ(4, vstorage_->NextCompactionIndex(1 /* level */));
1759 }
1760 
TEST_F(CompactionPickerTest,IntraL0MaxCompactionBytesNotHit)1761 TEST_F(CompactionPickerTest, IntraL0MaxCompactionBytesNotHit) {
1762   // Intra L0 compaction triggers only if there are at least
1763   // level0_file_num_compaction_trigger + 2 L0 files.
1764   mutable_cf_options_.level0_file_num_compaction_trigger = 3;
1765   mutable_cf_options_.max_compaction_bytes = 1000000u;
1766   NewVersionStorage(6, kCompactionStyleLevel);
1767 
1768   // All 5 L0 files will be picked for intra L0 compaction. The one L1 file
1769   // spans entire L0 key range and is marked as being compacted to avoid
1770   // L0->L1 compaction.
1771   Add(0, 1U, "100", "150", 200000U, 0, 100, 101);
1772   Add(0, 2U, "151", "200", 200000U, 0, 102, 103);
1773   Add(0, 3U, "201", "250", 200000U, 0, 104, 105);
1774   Add(0, 4U, "251", "300", 200000U, 0, 106, 107);
1775   Add(0, 5U, "301", "350", 200000U, 0, 108, 109);
1776   Add(1, 6U, "100", "350", 200000U, 0, 110, 111);
1777   vstorage_->LevelFiles(1)[0]->being_compacted = true;
1778   UpdateVersionStorageInfo();
1779 
1780   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
1781       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
1782       &log_buffer_));
1783   ASSERT_TRUE(compaction.get() != nullptr);
1784   ASSERT_EQ(1U, compaction->num_input_levels());
1785   ASSERT_EQ(5U, compaction->num_input_files(0));
1786   ASSERT_EQ(CompactionReason::kLevelL0FilesNum,
1787             compaction->compaction_reason());
1788   ASSERT_EQ(0, compaction->output_level());
1789 }
1790 
TEST_F(CompactionPickerTest,IntraL0MaxCompactionBytesHit)1791 TEST_F(CompactionPickerTest, IntraL0MaxCompactionBytesHit) {
1792   // Intra L0 compaction triggers only if there are at least
1793   // level0_file_num_compaction_trigger + 2 L0 files.
1794   mutable_cf_options_.level0_file_num_compaction_trigger = 3;
1795   mutable_cf_options_.max_compaction_bytes = 999999u;
1796   NewVersionStorage(6, kCompactionStyleLevel);
1797 
1798   // 4 out of 5 L0 files will be picked for intra L0 compaction due to
1799   // max_compaction_bytes limit (the minimum number of files for triggering
1800   // intra L0 compaction is 4). The one L1 file spans entire L0 key range and
1801   // is marked as being compacted to avoid L0->L1 compaction.
1802   Add(0, 1U, "100", "150", 200000U, 0, 100, 101);
1803   Add(0, 2U, "151", "200", 200000U, 0, 102, 103);
1804   Add(0, 3U, "201", "250", 200000U, 0, 104, 105);
1805   Add(0, 4U, "251", "300", 200000U, 0, 106, 107);
1806   Add(0, 5U, "301", "350", 200000U, 0, 108, 109);
1807   Add(1, 6U, "100", "350", 200000U, 0, 109, 110);
1808   vstorage_->LevelFiles(1)[0]->being_compacted = true;
1809   UpdateVersionStorageInfo();
1810 
1811   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
1812       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
1813       &log_buffer_));
1814   ASSERT_TRUE(compaction.get() != nullptr);
1815   ASSERT_EQ(1U, compaction->num_input_levels());
1816   ASSERT_EQ(4U, compaction->num_input_files(0));
1817   ASSERT_EQ(CompactionReason::kLevelL0FilesNum,
1818             compaction->compaction_reason());
1819   ASSERT_EQ(0, compaction->output_level());
1820 }
1821 
TEST_F(CompactionPickerTest,IntraL0ForEarliestSeqno)1822 TEST_F(CompactionPickerTest, IntraL0ForEarliestSeqno) {
1823   // Intra L0 compaction triggers only if there are at least
1824   // level0_file_num_compaction_trigger + 2 L0 files.
1825   mutable_cf_options_.level0_file_num_compaction_trigger = 3;
1826   mutable_cf_options_.max_compaction_bytes = 999999u;
1827   NewVersionStorage(6, kCompactionStyleLevel);
1828 
1829   // 4 out of 6 L0 files will be picked for intra L0 compaction due to
1830   // being_compact limit. And the latest one L0 will be skipped due to earliest
1831   // seqno. The one L1 file spans entire L0 key range and is marked as being
1832   // compacted to avoid L0->L1 compaction.
1833   Add(1, 1U, "100", "350", 200000U, 0, 110, 111);
1834   Add(0, 2U, "301", "350", 1U, 0, 108, 109);
1835   Add(0, 3U, "251", "300", 1U, 0, 106, 107);
1836   Add(0, 4U, "201", "250", 1U, 0, 104, 105);
1837   Add(0, 5U, "151", "200", 1U, 0, 102, 103);
1838   Add(0, 6U, "100", "150", 1U, 0, 100, 101);
1839   Add(0, 7U, "100", "100", 1U, 0, 99, 100);
1840   vstorage_->LevelFiles(0)[5]->being_compacted = true;
1841   vstorage_->LevelFiles(1)[0]->being_compacted = true;
1842   UpdateVersionStorageInfo();
1843 
1844   std::unique_ptr<Compaction> compaction(level_compaction_picker.PickCompaction(
1845       cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
1846       &log_buffer_, 107));
1847   ASSERT_TRUE(compaction.get() != nullptr);
1848   ASSERT_EQ(1U, compaction->num_input_levels());
1849   ASSERT_EQ(4U, compaction->num_input_files(0));
1850   ASSERT_EQ(CompactionReason::kLevelL0FilesNum,
1851             compaction->compaction_reason());
1852   ASSERT_EQ(0, compaction->output_level());
1853 }
1854 
1855 #ifndef ROCKSDB_LITE
TEST_F(CompactionPickerTest,UniversalMarkedCompactionFullOverlap)1856 TEST_F(CompactionPickerTest, UniversalMarkedCompactionFullOverlap) {
1857   const uint64_t kFileSize = 100000;
1858 
1859   ioptions_.compaction_style = kCompactionStyleUniversal;
1860   UniversalCompactionPicker universal_compaction_picker(ioptions_, &icmp_);
1861 
1862   // This test covers the case where a "regular" universal compaction is
1863   // scheduled first, followed by a delete triggered compaction. The latter
1864   // should fail
1865   NewVersionStorage(5, kCompactionStyleUniversal);
1866 
1867   Add(0, 1U, "150", "200", kFileSize, 0, 500, 550);
1868   Add(0, 2U, "201", "250", 2 * kFileSize, 0, 401, 450);
1869   Add(0, 4U, "260", "300", 4 * kFileSize, 0, 260, 300);
1870   Add(3, 5U, "010", "080", 8 * kFileSize, 0, 200, 251);
1871   Add(4, 3U, "301", "350", 8 * kFileSize, 0, 101, 150);
1872   Add(4, 6U, "501", "750", 8 * kFileSize, 0, 101, 150);
1873 
1874   UpdateVersionStorageInfo();
1875 
1876   std::unique_ptr<Compaction> compaction(
1877       universal_compaction_picker.PickCompaction(
1878           cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
1879           &log_buffer_));
1880 
1881   ASSERT_TRUE(compaction);
1882   // Validate that its a compaction to reduce sorted runs
1883   ASSERT_EQ(CompactionReason::kUniversalSortedRunNum,
1884             compaction->compaction_reason());
1885   ASSERT_EQ(0, compaction->output_level());
1886   ASSERT_EQ(0, compaction->start_level());
1887   ASSERT_EQ(2U, compaction->num_input_files(0));
1888 
1889   AddVersionStorage();
1890   // Simulate a flush and mark the file for compaction
1891   Add(0, 7U, "150", "200", kFileSize, 0, 551, 600, 0, true);
1892   UpdateVersionStorageInfo();
1893 
1894   std::unique_ptr<Compaction> compaction2(
1895       universal_compaction_picker.PickCompaction(
1896           cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
1897           &log_buffer_));
1898   ASSERT_FALSE(compaction2);
1899 }
1900 
TEST_F(CompactionPickerTest,UniversalMarkedCompactionFullOverlap2)1901 TEST_F(CompactionPickerTest, UniversalMarkedCompactionFullOverlap2) {
1902   const uint64_t kFileSize = 100000;
1903 
1904   ioptions_.compaction_style = kCompactionStyleUniversal;
1905   UniversalCompactionPicker universal_compaction_picker(ioptions_, &icmp_);
1906 
1907   // This test covers the case where a delete triggered compaction is
1908   // scheduled first, followed by a "regular" compaction. The latter
1909   // should fail
1910   NewVersionStorage(5, kCompactionStyleUniversal);
1911 
1912   // Mark file number 4 for compaction
1913   Add(0, 4U, "260", "300", 4 * kFileSize, 0, 260, 300, 0, true);
1914   Add(3, 5U, "240", "290", 8 * kFileSize, 0, 201, 250);
1915   Add(4, 3U, "301", "350", 8 * kFileSize, 0, 101, 150);
1916   Add(4, 6U, "501", "750", 8 * kFileSize, 0, 101, 150);
1917   UpdateVersionStorageInfo();
1918 
1919   std::unique_ptr<Compaction> compaction(
1920       universal_compaction_picker.PickCompaction(
1921           cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
1922           &log_buffer_));
1923 
1924   ASSERT_TRUE(compaction);
1925   // Validate that its a delete triggered compaction
1926   ASSERT_EQ(CompactionReason::kFilesMarkedForCompaction,
1927             compaction->compaction_reason());
1928   ASSERT_EQ(3, compaction->output_level());
1929   ASSERT_EQ(0, compaction->start_level());
1930   ASSERT_EQ(1U, compaction->num_input_files(0));
1931   ASSERT_EQ(1U, compaction->num_input_files(1));
1932 
1933   AddVersionStorage();
1934   Add(0, 1U, "150", "200", kFileSize, 0, 500, 550);
1935   Add(0, 2U, "201", "250", 2 * kFileSize, 0, 401, 450);
1936   UpdateVersionStorageInfo();
1937 
1938   std::unique_ptr<Compaction> compaction2(
1939       universal_compaction_picker.PickCompaction(
1940           cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
1941           &log_buffer_));
1942   ASSERT_FALSE(compaction2);
1943 }
1944 
TEST_F(CompactionPickerTest,UniversalMarkedCompactionStartOutputOverlap)1945 TEST_F(CompactionPickerTest, UniversalMarkedCompactionStartOutputOverlap) {
1946   // The case where universal periodic compaction can be picked
1947   // with some newer files being compacted.
1948   const uint64_t kFileSize = 100000;
1949 
1950   ioptions_.compaction_style = kCompactionStyleUniversal;
1951 
1952   bool input_level_overlap = false;
1953   bool output_level_overlap = false;
1954   // Let's mark 2 files in 2 different levels for compaction. The
1955   // compaction picker will randomly pick one, so use the sync point to
1956   // ensure a deterministic order. Loop until both cases are covered
1957   size_t random_index = 0;
1958   SyncPoint::GetInstance()->SetCallBack(
1959       "CompactionPicker::PickFilesMarkedForCompaction", [&](void* arg) {
1960         size_t* index = static_cast<size_t*>(arg);
1961         *index = random_index;
1962       });
1963   SyncPoint::GetInstance()->EnableProcessing();
1964   while (!input_level_overlap || !output_level_overlap) {
1965     // Ensure that the L0 file gets picked first
1966     random_index = !input_level_overlap ? 0 : 1;
1967     UniversalCompactionPicker universal_compaction_picker(ioptions_, &icmp_);
1968     NewVersionStorage(5, kCompactionStyleUniversal);
1969 
1970     Add(0, 1U, "260", "300", 4 * kFileSize, 0, 260, 300, 0, true);
1971     Add(3, 2U, "010", "020", 2 * kFileSize, 0, 201, 248);
1972     Add(3, 3U, "250", "270", 2 * kFileSize, 0, 202, 249);
1973     Add(3, 4U, "290", "310", 2 * kFileSize, 0, 203, 250);
1974     Add(3, 5U, "310", "320", 2 * kFileSize, 0, 204, 251, 0, true);
1975     Add(4, 6U, "301", "350", 8 * kFileSize, 0, 101, 150);
1976     Add(4, 7U, "501", "750", 8 * kFileSize, 0, 101, 150);
1977     UpdateVersionStorageInfo();
1978 
1979     std::unique_ptr<Compaction> compaction(
1980         universal_compaction_picker.PickCompaction(
1981             cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
1982             &log_buffer_));
1983 
1984     ASSERT_TRUE(compaction);
1985     // Validate that its a delete triggered compaction
1986     ASSERT_EQ(CompactionReason::kFilesMarkedForCompaction,
1987               compaction->compaction_reason());
1988     ASSERT_TRUE(compaction->start_level() == 0 ||
1989                 compaction->start_level() == 3);
1990     if (compaction->start_level() == 0) {
1991       // The L0 file was picked. The next compaction will detect an
1992       // overlap on its input level
1993       input_level_overlap = true;
1994       ASSERT_EQ(3, compaction->output_level());
1995       ASSERT_EQ(1U, compaction->num_input_files(0));
1996       ASSERT_EQ(3U, compaction->num_input_files(1));
1997     } else {
1998       // The level 3 file was picked. The next compaction will pick
1999       // the L0 file and will detect overlap when adding output
2000       // level inputs
2001       output_level_overlap = true;
2002       ASSERT_EQ(4, compaction->output_level());
2003       ASSERT_EQ(2U, compaction->num_input_files(0));
2004       ASSERT_EQ(1U, compaction->num_input_files(1));
2005     }
2006 
2007     vstorage_->ComputeCompactionScore(ioptions_, mutable_cf_options_);
2008     // After recomputing the compaction score, only one marked file will remain
2009     random_index = 0;
2010     std::unique_ptr<Compaction> compaction2(
2011         universal_compaction_picker.PickCompaction(
2012             cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
2013             &log_buffer_));
2014     ASSERT_FALSE(compaction2);
2015     DeleteVersionStorage();
2016   }
2017 }
2018 
TEST_F(CompactionPickerTest,UniversalMarkedL0NoOverlap)2019 TEST_F(CompactionPickerTest, UniversalMarkedL0NoOverlap) {
2020   const uint64_t kFileSize = 100000;
2021 
2022   ioptions_.compaction_style = kCompactionStyleUniversal;
2023   UniversalCompactionPicker universal_compaction_picker(ioptions_, &icmp_);
2024 
2025   // This test covers the case where a delete triggered compaction is
2026   // scheduled and should result in a full compaction
2027   NewVersionStorage(1, kCompactionStyleUniversal);
2028 
2029   // Mark file number 4 for compaction
2030   Add(0, 4U, "260", "300", 1 * kFileSize, 0, 260, 300, 0, true);
2031   Add(0, 5U, "240", "290", 2 * kFileSize, 0, 201, 250);
2032   Add(0, 3U, "301", "350", 4 * kFileSize, 0, 101, 150);
2033   Add(0, 6U, "501", "750", 8 * kFileSize, 0, 50, 100);
2034   UpdateVersionStorageInfo();
2035 
2036   std::unique_ptr<Compaction> compaction(
2037       universal_compaction_picker.PickCompaction(
2038           cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
2039           &log_buffer_));
2040 
2041   ASSERT_TRUE(compaction);
2042   // Validate that its a delete triggered compaction
2043   ASSERT_EQ(CompactionReason::kFilesMarkedForCompaction,
2044             compaction->compaction_reason());
2045   ASSERT_EQ(0, compaction->output_level());
2046   ASSERT_EQ(0, compaction->start_level());
2047   ASSERT_EQ(4U, compaction->num_input_files(0));
2048   ASSERT_TRUE(file_map_[4].first->being_compacted);
2049   ASSERT_TRUE(file_map_[5].first->being_compacted);
2050   ASSERT_TRUE(file_map_[3].first->being_compacted);
2051   ASSERT_TRUE(file_map_[6].first->being_compacted);
2052 }
2053 
TEST_F(CompactionPickerTest,UniversalMarkedL0WithOverlap)2054 TEST_F(CompactionPickerTest, UniversalMarkedL0WithOverlap) {
2055   const uint64_t kFileSize = 100000;
2056 
2057   ioptions_.compaction_style = kCompactionStyleUniversal;
2058   UniversalCompactionPicker universal_compaction_picker(ioptions_, &icmp_);
2059 
2060   // This test covers the case where a file is being compacted, and a
2061   // delete triggered compaction is then scheduled. The latter should stop
2062   // at the first file being compacted
2063   NewVersionStorage(1, kCompactionStyleUniversal);
2064 
2065   // Mark file number 4 for compaction
2066   Add(0, 4U, "260", "300", 1 * kFileSize, 0, 260, 300, 0, true);
2067   Add(0, 5U, "240", "290", 2 * kFileSize, 0, 201, 250);
2068   Add(0, 3U, "301", "350", 4 * kFileSize, 0, 101, 150);
2069   Add(0, 6U, "501", "750", 8 * kFileSize, 0, 50, 100);
2070   UpdateVersionStorageInfo();
2071   file_map_[3].first->being_compacted = true;
2072 
2073   std::unique_ptr<Compaction> compaction(
2074       universal_compaction_picker.PickCompaction(
2075           cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
2076           &log_buffer_));
2077 
2078   ASSERT_TRUE(compaction);
2079   // Validate that its a delete triggered compaction
2080   ASSERT_EQ(CompactionReason::kFilesMarkedForCompaction,
2081             compaction->compaction_reason());
2082   ASSERT_EQ(0, compaction->output_level());
2083   ASSERT_EQ(0, compaction->start_level());
2084   ASSERT_EQ(2U, compaction->num_input_files(0));
2085   ASSERT_TRUE(file_map_[4].first->being_compacted);
2086   ASSERT_TRUE(file_map_[5].first->being_compacted);
2087 }
2088 
TEST_F(CompactionPickerTest,UniversalMarkedL0Overlap2)2089 TEST_F(CompactionPickerTest, UniversalMarkedL0Overlap2) {
2090   const uint64_t kFileSize = 100000;
2091 
2092   ioptions_.compaction_style = kCompactionStyleUniversal;
2093   UniversalCompactionPicker universal_compaction_picker(ioptions_, &icmp_);
2094 
2095   // This test covers the case where a delete triggered compaction is
2096   // scheduled first, followed by a "regular" compaction. The latter
2097   // should fail
2098   NewVersionStorage(1, kCompactionStyleUniversal);
2099 
2100   // Mark file number 4 for compaction
2101   Add(0, 4U, "260", "300", 1 * kFileSize, 0, 260, 300);
2102   Add(0, 5U, "240", "290", 2 * kFileSize, 0, 201, 250, 0, true);
2103   Add(0, 3U, "301", "350", 4 * kFileSize, 0, 101, 150);
2104   Add(0, 6U, "501", "750", 8 * kFileSize, 0, 50, 100);
2105   UpdateVersionStorageInfo();
2106 
2107   std::unique_ptr<Compaction> compaction(
2108       universal_compaction_picker.PickCompaction(
2109           cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
2110           &log_buffer_));
2111 
2112   ASSERT_TRUE(compaction);
2113   // Validate that its a delete triggered compaction
2114   ASSERT_EQ(CompactionReason::kFilesMarkedForCompaction,
2115             compaction->compaction_reason());
2116   ASSERT_EQ(0, compaction->output_level());
2117   ASSERT_EQ(0, compaction->start_level());
2118   ASSERT_EQ(3U, compaction->num_input_files(0));
2119   ASSERT_TRUE(file_map_[5].first->being_compacted);
2120   ASSERT_TRUE(file_map_[3].first->being_compacted);
2121   ASSERT_TRUE(file_map_[6].first->being_compacted);
2122 
2123   AddVersionStorage();
2124   Add(0, 1U, "150", "200", kFileSize, 0, 500, 550);
2125   Add(0, 2U, "201", "250", kFileSize, 0, 401, 450);
2126   UpdateVersionStorageInfo();
2127 
2128   std::unique_ptr<Compaction> compaction2(
2129       universal_compaction_picker.PickCompaction(
2130           cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
2131           &log_buffer_));
2132   ASSERT_TRUE(compaction2);
2133   ASSERT_EQ(3U, compaction->num_input_files(0));
2134   ASSERT_TRUE(file_map_[1].first->being_compacted);
2135   ASSERT_TRUE(file_map_[2].first->being_compacted);
2136   ASSERT_TRUE(file_map_[4].first->being_compacted);
2137 }
2138 
TEST_F(CompactionPickerTest,UniversalMarkedManualCompaction)2139 TEST_F(CompactionPickerTest, UniversalMarkedManualCompaction) {
2140   const uint64_t kFileSize = 100000;
2141   const int kNumLevels = 7;
2142 
2143   // This test makes sure the `files_marked_for_compaction_` is updated after
2144   // creating manual compaction.
2145   ioptions_.compaction_style = kCompactionStyleUniversal;
2146   UniversalCompactionPicker universal_compaction_picker(ioptions_, &icmp_);
2147 
2148   NewVersionStorage(kNumLevels, kCompactionStyleUniversal);
2149 
2150   // Add 3 files marked for compaction
2151   Add(0, 3U, "301", "350", 4 * kFileSize, 0, 101, 150, 0, true);
2152   Add(0, 4U, "260", "300", 1 * kFileSize, 0, 260, 300, 0, true);
2153   Add(0, 5U, "240", "290", 2 * kFileSize, 0, 201, 250, 0, true);
2154   UpdateVersionStorageInfo();
2155 
2156   // All 3 files are marked for compaction
2157   ASSERT_EQ(3U, vstorage_->FilesMarkedForCompaction().size());
2158 
2159   bool manual_conflict = false;
2160   InternalKey* manual_end = NULL;
2161   std::unique_ptr<Compaction> compaction(
2162       universal_compaction_picker.CompactRange(
2163           cf_name_, mutable_cf_options_, mutable_db_options_, vstorage_.get(),
2164           ColumnFamilyData::kCompactAllLevels, 6, CompactRangeOptions(), NULL,
2165           NULL, &manual_end, &manual_conflict, port::kMaxUint64));
2166 
2167   ASSERT_TRUE(compaction);
2168 
2169   ASSERT_EQ(CompactionReason::kManualCompaction,
2170             compaction->compaction_reason());
2171   ASSERT_EQ(kNumLevels - 1, compaction->output_level());
2172   ASSERT_EQ(0, compaction->start_level());
2173   ASSERT_EQ(3U, compaction->num_input_files(0));
2174   ASSERT_TRUE(file_map_[3].first->being_compacted);
2175   ASSERT_TRUE(file_map_[4].first->being_compacted);
2176   ASSERT_TRUE(file_map_[5].first->being_compacted);
2177 
2178   // After creating the manual compaction, all files should be cleared from
2179   // `FilesMarkedForCompaction`. So they won't be picked by others.
2180   ASSERT_EQ(0U, vstorage_->FilesMarkedForCompaction().size());
2181 }
2182 
2183 #endif  // ROCKSDB_LITE
2184 
2185 }  // namespace ROCKSDB_NAMESPACE
2186 
main(int argc,char ** argv)2187 int main(int argc, char** argv) {
2188   ::testing::InitGoogleTest(&argc, argv);
2189   return RUN_ALL_TESTS();
2190 }
2191