]> git.proxmox.com Git - ceph.git/blob - ceph/src/rocksdb/db/compaction/compaction_picker_test.cc
projects / ceph.git / blob
? search:


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