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