compaction_picker.cc 34.8 KB
Newer Older
I
Igor Canadi 已提交
1 2 3 4 5 6 7 8 9 10
//  Copyright (c) 2013, Facebook, Inc.  All rights reserved.
//  This source code is licensed under the BSD-style license found in the
//  LICENSE file in the root directory of this source tree. An additional grant
//  of patent rights can be found in the PATENTS file in the same directory.
//
// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file. See the AUTHORS file for names of contributors.

#include "db/compaction_picker.h"
11

I
Igor Canadi 已提交
12 13
#define __STDC_FORMAT_MACROS
#include <inttypes.h>
14
#include <limits>
H
Haobo Xu 已提交
15
#include "util/log_buffer.h"
I
Igor Canadi 已提交
16
#include "util/statistics.h"
I
Igor Canadi 已提交
17 18 19 20 21

namespace rocksdb {

namespace {

22
uint64_t TotalCompensatedFileSize(const std::vector<FileMetaData*>& files) {
I
Igor Canadi 已提交
23 24
  uint64_t sum = 0;
  for (size_t i = 0; i < files.size() && files[i]; i++) {
25
    sum += files[i]->compensated_file_size;
I
Igor Canadi 已提交
26 27 28 29
  }
  return sum;
}

30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
// Multiple two operands. If they overflow, return op1.
uint64_t MultiplyCheckOverflow(uint64_t op1, int op2) {
  if (op1 == 0) {
    return 0;
  }
  if (op2 <= 0) {
    return op1;
  }
  uint64_t casted_op2 = (uint64_t) op2;
  if (std::numeric_limits<uint64_t>::max() / op1 < casted_op2) {
    return op1;
  }
  return op1 * casted_op2;
}

I
Igor Canadi 已提交
45 46
}  // anonymous namespace

I
Igor Canadi 已提交
47 48
CompactionPicker::CompactionPicker(const Options* options,
                                   const InternalKeyComparator* icmp)
I
Igor Canadi 已提交
49 50 51 52 53 54 55 56 57 58 59 60 61 62
    : compactions_in_progress_(options->num_levels),
      options_(options),
      num_levels_(options->num_levels),
      icmp_(icmp) {

  max_file_size_.reset(new uint64_t[NumberLevels()]);
  level_max_bytes_.reset(new uint64_t[NumberLevels()]);
  int target_file_size_multiplier = options_->target_file_size_multiplier;
  int max_bytes_multiplier = options_->max_bytes_for_level_multiplier;
  for (int i = 0; i < NumberLevels(); i++) {
    if (i == 0 && options_->compaction_style == kCompactionStyleUniversal) {
      max_file_size_[i] = ULLONG_MAX;
      level_max_bytes_[i] = options_->max_bytes_for_level_base;
    } else if (i > 1) {
63 64 65 66 67
      max_file_size_[i] = MultiplyCheckOverflow(max_file_size_[i - 1],
                                                target_file_size_multiplier);
      level_max_bytes_[i] = MultiplyCheckOverflow(
          MultiplyCheckOverflow(level_max_bytes_[i - 1], max_bytes_multiplier),
          options_->max_bytes_for_level_multiplier_additional[i - 1]);
I
Igor Canadi 已提交
68 69 70 71 72 73 74 75 76 77 78 79 80 81 82
    } else {
      max_file_size_[i] = options_->target_file_size_base;
      level_max_bytes_[i] = options_->max_bytes_for_level_base;
    }
  }
}

CompactionPicker::~CompactionPicker() {}

void CompactionPicker::SizeBeingCompacted(std::vector<uint64_t>& sizes) {
  for (int level = 0; level < NumberLevels() - 1; level++) {
    uint64_t total = 0;
    for (auto c : compactions_in_progress_[level]) {
      assert(c->level() == level);
      for (int i = 0; i < c->num_input_files(0); i++) {
83
        total += c->input(0, i)->compensated_file_size;
I
Igor Canadi 已提交
84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148
      }
    }
    sizes[level] = total;
  }
}

// Clear all files to indicate that they are not being compacted
// Delete this compaction from the list of running compactions.
void CompactionPicker::ReleaseCompactionFiles(Compaction* c, Status status) {
  c->MarkFilesBeingCompacted(false);
  compactions_in_progress_[c->level()].erase(c);
  if (!status.ok()) {
    c->ResetNextCompactionIndex();
  }
}

uint64_t CompactionPicker::MaxFileSizeForLevel(int level) const {
  assert(level >= 0);
  assert(level < NumberLevels());
  return max_file_size_[level];
}

uint64_t CompactionPicker::MaxGrandParentOverlapBytes(int level) {
  uint64_t result = MaxFileSizeForLevel(level);
  result *= options_->max_grandparent_overlap_factor;
  return result;
}

double CompactionPicker::MaxBytesForLevel(int level) {
  // Note: the result for level zero is not really used since we set
  // the level-0 compaction threshold based on number of files.
  assert(level >= 0);
  assert(level < NumberLevels());
  return level_max_bytes_[level];
}

void CompactionPicker::GetRange(const std::vector<FileMetaData*>& inputs,
                                InternalKey* smallest, InternalKey* largest) {
  assert(!inputs.empty());
  smallest->Clear();
  largest->Clear();
  for (size_t i = 0; i < inputs.size(); i++) {
    FileMetaData* f = inputs[i];
    if (i == 0) {
      *smallest = f->smallest;
      *largest = f->largest;
    } else {
      if (icmp_->Compare(f->smallest, *smallest) < 0) {
        *smallest = f->smallest;
      }
      if (icmp_->Compare(f->largest, *largest) > 0) {
        *largest = f->largest;
      }
    }
  }
}

void CompactionPicker::GetRange(const std::vector<FileMetaData*>& inputs1,
                                const std::vector<FileMetaData*>& inputs2,
                                InternalKey* smallest, InternalKey* largest) {
  std::vector<FileMetaData*> all = inputs1;
  all.insert(all.end(), inputs2.begin(), inputs2.end());
  GetRange(all, smallest, largest);
}

I
Igor Canadi 已提交
149
bool CompactionPicker::ExpandWhileOverlapping(Compaction* c) {
I
Igor Canadi 已提交
150 151
  // If inputs are empty then there is nothing to expand.
  if (!c || c->inputs_[0].empty()) {
I
Igor Canadi 已提交
152
    return true;
I
Igor Canadi 已提交
153 154 155 156 157
  }

  // GetOverlappingInputs will always do the right thing for level-0.
  // So we don't need to do any expansion if level == 0.
  if (c->level() == 0) {
I
Igor Canadi 已提交
158
    return true;
I
Igor Canadi 已提交
159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182
  }

  const int level = c->level();
  InternalKey smallest, largest;

  // Keep expanding c->inputs_[0] until we are sure that there is a
  // "clean cut" boundary between the files in input and the surrounding files.
  // This will ensure that no parts of a key are lost during compaction.
  int hint_index = -1;
  size_t old_size;
  do {
    old_size = c->inputs_[0].size();
    GetRange(c->inputs_[0], &smallest, &largest);
    c->inputs_[0].clear();
    c->input_version_->GetOverlappingInputs(
        level, &smallest, &largest, &c->inputs_[0], hint_index, &hint_index);
  } while(c->inputs_[0].size() > old_size);

  // Get the new range
  GetRange(c->inputs_[0], &smallest, &largest);

  // If, after the expansion, there are files that are already under
  // compaction, then we must drop/cancel this compaction.
  int parent_index = -1;
183 184
  if (c->inputs_[0].empty()) {
    Log(options_->info_log,
I
Igor Canadi 已提交
185 186
        "[%s] ExpandWhileOverlapping() failure because zero input files",
        c->column_family_data()->GetName().c_str());
187 188
  }
  if (c->inputs_[0].empty() || FilesInCompaction(c->inputs_[0]) ||
I
Igor Canadi 已提交
189 190 191 192 193
      (c->level() != c->output_level() &&
       ParentRangeInCompaction(c->input_version_, &smallest, &largest, level,
                               &parent_index))) {
    c->inputs_[0].clear();
    c->inputs_[1].clear();
I
Igor Canadi 已提交
194
    return false;
I
Igor Canadi 已提交
195
  }
I
Igor Canadi 已提交
196
  return true;
I
Igor Canadi 已提交
197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263
}

uint64_t CompactionPicker::ExpandedCompactionByteSizeLimit(int level) {
  uint64_t result = MaxFileSizeForLevel(level);
  result *= options_->expanded_compaction_factor;
  return result;
}

// Returns true if any one of specified files are being compacted
bool CompactionPicker::FilesInCompaction(std::vector<FileMetaData*>& files) {
  for (unsigned int i = 0; i < files.size(); i++) {
    if (files[i]->being_compacted) {
      return true;
    }
  }
  return false;
}

// Returns true if any one of the parent files are being compacted
bool CompactionPicker::ParentRangeInCompaction(Version* version,
                                               const InternalKey* smallest,
                                               const InternalKey* largest,
                                               int level, int* parent_index) {
  std::vector<FileMetaData*> inputs;
  assert(level + 1 < NumberLevels());

  version->GetOverlappingInputs(level + 1, smallest, largest, &inputs,
                                *parent_index, parent_index);
  return FilesInCompaction(inputs);
}

// Populates the set of inputs from "level+1" that overlap with "level".
// Will also attempt to expand "level" if that doesn't expand "level+1"
// or cause "level" to include a file for compaction that has an overlapping
// user-key with another file.
void CompactionPicker::SetupOtherInputs(Compaction* c) {
  // If inputs are empty, then there is nothing to expand.
  // If both input and output levels are the same, no need to consider
  // files at level "level+1"
  if (c->inputs_[0].empty() || c->level() == c->output_level()) {
    return;
  }

  const int level = c->level();
  InternalKey smallest, largest;

  // Get the range one last time.
  GetRange(c->inputs_[0], &smallest, &largest);

  // Populate the set of next-level files (inputs_[1]) to include in compaction
  c->input_version_->GetOverlappingInputs(level + 1, &smallest, &largest,
                                          &c->inputs_[1], c->parent_index_,
                                          &c->parent_index_);

  // Get entire range covered by compaction
  InternalKey all_start, all_limit;
  GetRange(c->inputs_[0], c->inputs_[1], &all_start, &all_limit);

  // See if we can further grow the number of inputs in "level" without
  // changing the number of "level+1" files we pick up. We also choose NOT
  // to expand if this would cause "level" to include some entries for some
  // user key, while excluding other entries for the same user key. This
  // can happen when one user key spans multiple files.
  if (!c->inputs_[1].empty()) {
    std::vector<FileMetaData*> expanded0;
    c->input_version_->GetOverlappingInputs(
        level, &all_start, &all_limit, &expanded0, c->base_index_, nullptr);
264 265 266
    const uint64_t inputs0_size = TotalCompensatedFileSize(c->inputs_[0]);
    const uint64_t inputs1_size = TotalCompensatedFileSize(c->inputs_[1]);
    const uint64_t expanded0_size = TotalCompensatedFileSize(expanded0);
I
Igor Canadi 已提交
267 268 269 270 271 272 273 274 275 276 277 278 279
    uint64_t limit = ExpandedCompactionByteSizeLimit(level);
    if (expanded0.size() > c->inputs_[0].size() &&
        inputs1_size + expanded0_size < limit &&
        !FilesInCompaction(expanded0) &&
        !c->input_version_->HasOverlappingUserKey(&expanded0, level)) {
      InternalKey new_start, new_limit;
      GetRange(expanded0, &new_start, &new_limit);
      std::vector<FileMetaData*> expanded1;
      c->input_version_->GetOverlappingInputs(level + 1, &new_start, &new_limit,
                                              &expanded1, c->parent_index_,
                                              &c->parent_index_);
      if (expanded1.size() == c->inputs_[1].size() &&
          !FilesInCompaction(expanded1)) {
I
Igor Canadi 已提交
280
        Log(options_->info_log,
I
Igor Canadi 已提交
281 282 283 284
            "[%s] Expanding@%lu %lu+%lu (%lu+%lu bytes) to %lu+%lu (%lu+%lu "
            "bytes)\n",
            c->column_family_data()->GetName().c_str(), (unsigned long)level,
            (unsigned long)(c->inputs_[0].size()),
285 286 287
            (unsigned long)(c->inputs_[1].size()), (unsigned long)inputs0_size,
            (unsigned long)inputs1_size, (unsigned long)(expanded0.size()),
            (unsigned long)(expanded1.size()), (unsigned long)expanded0_size,
I
Igor Canadi 已提交
288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311
            (unsigned long)inputs1_size);
        smallest = new_start;
        largest = new_limit;
        c->inputs_[0] = expanded0;
        c->inputs_[1] = expanded1;
        GetRange(c->inputs_[0], c->inputs_[1], &all_start, &all_limit);
      }
    }
  }

  // Compute the set of grandparent files that overlap this compaction
  // (parent == level+1; grandparent == level+2)
  if (level + 2 < NumberLevels()) {
    c->input_version_->GetOverlappingInputs(level + 2, &all_start, &all_limit,
                                            &c->grandparents_);
  }
}


Compaction* CompactionPicker::CompactRange(Version* version, int input_level,
                                           int output_level,
                                           const InternalKey* begin,
                                           const InternalKey* end,
                                           InternalKey** compaction_end) {
I
Igor Canadi 已提交
312 313 314
  // CompactionPickerFIFO has its own implementation of compact range
  assert(options_->compaction_style != kCompactionStyleFIFO);

I
Igor Canadi 已提交
315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337
  std::vector<FileMetaData*> inputs;
  bool covering_the_whole_range = true;

  // All files are 'overlapping' in universal style compaction.
  // We have to compact the entire range in one shot.
  if (options_->compaction_style == kCompactionStyleUniversal) {
    begin = nullptr;
    end = nullptr;
  }
  version->GetOverlappingInputs(input_level, begin, end, &inputs);
  if (inputs.empty()) {
    return nullptr;
  }

  // Avoid compacting too much in one shot in case the range is large.
  // But we cannot do this for level-0 since level-0 files can overlap
  // and we must not pick one file and drop another older file if the
  // two files overlap.
  if (input_level > 0) {
    const uint64_t limit =
        MaxFileSizeForLevel(input_level) * options_->source_compaction_factor;
    uint64_t total = 0;
    for (size_t i = 0; i + 1 < inputs.size(); ++i) {
338
      uint64_t s = inputs[i]->compensated_file_size;
I
Igor Canadi 已提交
339 340 341 342 343 344 345 346 347 348 349 350 351 352
      total += s;
      if (total >= limit) {
        **compaction_end = inputs[i + 1]->smallest;
        covering_the_whole_range = false;
        inputs.resize(i + 1);
        break;
      }
    }
  }
  Compaction* c = new Compaction(version, input_level, output_level,
                                 MaxFileSizeForLevel(output_level),
                                 MaxGrandParentOverlapBytes(input_level));

  c->inputs_[0] = inputs;
I
Igor Canadi 已提交
353 354
  if (ExpandWhileOverlapping(c) == false) {
    delete c;
I
Igor Canadi 已提交
355 356 357
    Log(options_->info_log,
        "[%s] Could not compact due to expansion failure.\n",
        version->cfd_->GetName().c_str());
I
Igor Canadi 已提交
358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373
    return nullptr;
  }

  SetupOtherInputs(c);

  if (covering_the_whole_range) {
    *compaction_end = nullptr;
  }

  // These files that are to be manaully compacted do not trample
  // upon other files because manual compactions are processed when
  // the system has a max of 1 background compaction thread.
  c->MarkFilesBeingCompacted(true);

  // Is this compaction creating a file at the bottommost level
  c->SetupBottomMostLevel(true);
374 375 376

  c->is_manual_compaction_ = true;

I
Igor Canadi 已提交
377 378 379
  return c;
}

380 381
Compaction* LevelCompactionPicker::PickCompaction(Version* version,
                                                  LogBuffer* log_buffer) {
I
Igor Canadi 已提交
382 383 384
  Compaction* c = nullptr;
  int level = -1;

385 386 387 388 389 390
  // Compute the compactions needed. It is better to do it here
  // and also in LogAndApply(), otherwise the values could be stale.
  std::vector<uint64_t> size_being_compacted(NumberLevels() - 1);
  SizeBeingCompacted(size_being_compacted);
  version->ComputeCompactionScore(size_being_compacted);

I
Igor Canadi 已提交
391 392 393 394 395 396 397 398 399 400
  // We prefer compactions triggered by too much data in a level over
  // the compactions triggered by seeks.
  //
  // Find the compactions by size on all levels.
  for (int i = 0; i < NumberLevels() - 1; i++) {
    assert(i == 0 ||
           version->compaction_score_[i] <= version->compaction_score_[i - 1]);
    level = version->compaction_level_[i];
    if ((version->compaction_score_[i] >= 1)) {
      c = PickCompactionBySize(version, level, version->compaction_score_[i]);
I
Igor Canadi 已提交
401 402 403 404
      if (ExpandWhileOverlapping(c) == false) {
        delete c;
        c = nullptr;
      } else {
I
Igor Canadi 已提交
405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485
        break;
      }
    }
  }

  if (c == nullptr) {
    return nullptr;
  }

  // Two level 0 compaction won't run at the same time, so don't need to worry
  // about files on level 0 being compacted.
  if (level == 0) {
    assert(compactions_in_progress_[0].empty());
    InternalKey smallest, largest;
    GetRange(c->inputs_[0], &smallest, &largest);
    // Note that the next call will discard the file we placed in
    // c->inputs_[0] earlier and replace it with an overlapping set
    // which will include the picked file.
    c->inputs_[0].clear();
    c->input_version_->GetOverlappingInputs(0, &smallest, &largest,
                                            &c->inputs_[0]);

    // If we include more L0 files in the same compaction run it can
    // cause the 'smallest' and 'largest' key to get extended to a
    // larger range. So, re-invoke GetRange to get the new key range
    GetRange(c->inputs_[0], &smallest, &largest);
    if (ParentRangeInCompaction(c->input_version_, &smallest, &largest, level,
                                &c->parent_index_)) {
      delete c;
      return nullptr;
    }
    assert(!c->inputs_[0].empty());
  }

  // Setup "level+1" files (inputs_[1])
  SetupOtherInputs(c);

  // mark all the files that are being compacted
  c->MarkFilesBeingCompacted(true);

  // Is this compaction creating a file at the bottommost level
  c->SetupBottomMostLevel(false);

  // remember this currently undergoing compaction
  compactions_in_progress_[level].insert(c);

  return c;
}

Compaction* LevelCompactionPicker::PickCompactionBySize(Version* version,
                                                        int level,
                                                        double score) {
  Compaction* c = nullptr;

  // level 0 files are overlapping. So we cannot pick more
  // than one concurrent compactions at this level. This
  // could be made better by looking at key-ranges that are
  // being compacted at level 0.
  if (level == 0 && compactions_in_progress_[level].size() == 1) {
    return nullptr;
  }

  assert(level >= 0);
  assert(level + 1 < NumberLevels());
  c = new Compaction(version, level, level + 1, MaxFileSizeForLevel(level + 1),
                     MaxGrandParentOverlapBytes(level));
  c->score_ = score;

  // Pick the largest file in this level that is not already
  // being compacted
  std::vector<int>& file_size = c->input_version_->files_by_size_[level];

  // record the first file that is not yet compacted
  int nextIndex = -1;

  for (unsigned int i = c->input_version_->next_file_to_compact_by_size_[level];
       i < file_size.size(); i++) {
    int index = file_size[i];
    FileMetaData* f = c->input_version_->files_[level][index];

    // check to verify files are arranged in descending size
486 487 488 489 490
    assert((i == file_size.size() - 1) ||
           (i >= Version::number_of_files_to_sort_ - 1) ||
           (f->compensated_file_size >=
            c->input_version_->files_[level][file_size[i + 1]]->
                compensated_file_size));
I
Igor Canadi 已提交
491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521

    // do not pick a file to compact if it is being compacted
    // from n-1 level.
    if (f->being_compacted) {
      continue;
    }

    // remember the startIndex for the next call to PickCompaction
    if (nextIndex == -1) {
      nextIndex = i;
    }

    // Do not pick this file if its parents at level+1 are being compacted.
    // Maybe we can avoid redoing this work in SetupOtherInputs
    int parent_index = -1;
    if (ParentRangeInCompaction(c->input_version_, &f->smallest, &f->largest,
                                level, &parent_index)) {
      continue;
    }
    c->inputs_[0].push_back(f);
    c->base_index_ = index;
    c->parent_index_ = parent_index;
    break;
  }

  if (c->inputs_[0].empty()) {
    delete c;
    c = nullptr;
  }

  // store where to start the iteration in the next call to PickCompaction
I
Igor Canadi 已提交
522
  version->next_file_to_compact_by_size_[level] = nextIndex;
I
Igor Canadi 已提交
523 524 525 526 527 528 529

  return c;
}

// Universal style of compaction. Pick files that are contiguous in
// time-range to compact.
//
530 531
Compaction* UniversalCompactionPicker::PickCompaction(Version* version,
                                                      LogBuffer* log_buffer) {
I
Igor Canadi 已提交
532 533 534 535 536
  int level = 0;
  double score = version->compaction_score_[0];

  if ((version->files_[level].size() <
       (unsigned int)options_->level0_file_num_compaction_trigger)) {
I
Igor Canadi 已提交
537 538
    LogToBuffer(log_buffer, "[%s] Universal: nothing to do\n",
                version->cfd_->GetName().c_str());
I
Igor Canadi 已提交
539 540 541
    return nullptr;
  }
  Version::FileSummaryStorage tmp;
I
Igor Canadi 已提交
542 543
  LogToBuffer(log_buffer, "[%s] Universal: candidate files(%zu): %s\n",
              version->cfd_->GetName().c_str(), version->files_[level].size(),
544
              version->LevelFileSummary(&tmp, 0));
I
Igor Canadi 已提交
545 546

  // Check for size amplification first.
M
Mike Lin 已提交
547
  Compaction* c;
548 549
  if ((c = PickCompactionUniversalSizeAmp(version, score, log_buffer)) !=
      nullptr) {
I
Igor Canadi 已提交
550 551
    LogToBuffer(log_buffer, "[%s] Universal: compacting for size amp\n",
                version->cfd_->GetName().c_str());
M
Mike Lin 已提交
552
  } else {
I
Igor Canadi 已提交
553 554 555 556
    // Size amplification is within limits. Try reducing read
    // amplification while maintaining file size ratios.
    unsigned int ratio = options_->compaction_options_universal.size_ratio;

557 558
    if ((c = PickCompactionUniversalReadAmp(version, score, ratio, UINT_MAX,
                                            log_buffer)) != nullptr) {
I
Igor Canadi 已提交
559 560
      LogToBuffer(log_buffer, "[%s] Universal: compacting for size ratio\n",
                  version->cfd_->GetName().c_str());
M
Mike Lin 已提交
561 562 563 564 565
    } else {
      // Size amplification and file size ratios are within configured limits.
      // If max read amplification is exceeding configured limits, then force
      // compaction without looking at filesize ratios and try to reduce
      // the number of files to fewer than level0_file_num_compaction_trigger.
I
Igor Canadi 已提交
566 567
      unsigned int num_files = version->files_[level].size() -
                               options_->level0_file_num_compaction_trigger;
568 569
      if ((c = PickCompactionUniversalReadAmp(
               version, score, UINT_MAX, num_files, log_buffer)) != nullptr) {
I
Igor Canadi 已提交
570 571
        LogToBuffer(log_buffer, "[%s] Universal: compacting for file num\n",
                    version->cfd_->GetName().c_str());
M
Mike Lin 已提交
572
      }
I
Igor Canadi 已提交
573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599
    }
  }
  if (c == nullptr) {
    return nullptr;
  }
  assert(c->inputs_[0].size() > 1);

  // validate that all the chosen files are non overlapping in time
  FileMetaData* newerfile __attribute__((unused)) = nullptr;
  for (unsigned int i = 0; i < c->inputs_[0].size(); i++) {
    FileMetaData* f = c->inputs_[0][i];
    assert (f->smallest_seqno <= f->largest_seqno);
    assert(newerfile == nullptr ||
           newerfile->smallest_seqno > f->largest_seqno);
    newerfile = f;
  }

  // The files are sorted from newest first to oldest last.
  std::vector<int>& file_by_time = c->input_version_->files_by_size_[level];

  // Is the earliest file part of this compaction?
  int last_index = file_by_time[file_by_time.size()-1];
  FileMetaData* last_file = c->input_version_->files_[level][last_index];
  if (c->inputs_[0][c->inputs_[0].size()-1] == last_file) {
    c->bottommost_level_ = true;
  }

I
Igor Canadi 已提交
600 601 602 603
  // update statistics
  MeasureTime(options_->statistics.get(), NUM_FILES_IN_SINGLE_COMPACTION,
              c->inputs_[0].size());

I
Igor Canadi 已提交
604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623
  // mark all the files that are being compacted
  c->MarkFilesBeingCompacted(true);

  // remember this currently undergoing compaction
  compactions_in_progress_[level].insert(c);

  // Record whether this compaction includes all sst files.
  // For now, it is only relevant in universal compaction mode.
  c->is_full_compaction_ =
      (c->inputs_[0].size() == c->input_version_->files_[0].size());

  return c;
}

//
// Consider compaction files based on their size differences with
// the next file in time order.
//
Compaction* UniversalCompactionPicker::PickCompactionUniversalReadAmp(
    Version* version, double score, unsigned int ratio,
624
    unsigned int max_number_of_files_to_compact, LogBuffer* log_buffer) {
I
Igor Canadi 已提交
625 626 627 628 629 630 631 632 633 634 635 636
  int level = 0;

  unsigned int min_merge_width =
    options_->compaction_options_universal.min_merge_width;
  unsigned int max_merge_width =
    options_->compaction_options_universal.max_merge_width;

  // The files are sorted from newest first to oldest last.
  std::vector<int>& file_by_time = version->files_by_size_[level];
  FileMetaData* f = nullptr;
  bool done = false;
  int start_index = 0;
I
Igor Canadi 已提交
637
  unsigned int candidate_count = 0;
I
Igor Canadi 已提交
638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658
  assert(file_by_time.size() == version->files_[level].size());

  unsigned int max_files_to_compact = std::min(max_merge_width,
                                       max_number_of_files_to_compact);
  min_merge_width = std::max(min_merge_width, 2U);

  // Considers a candidate file only if it is smaller than the
  // total size accumulated so far.
  for (unsigned int loop = 0; loop < file_by_time.size(); loop++) {

    candidate_count = 0;

    // Skip files that are already being compacted
    for (f = nullptr; loop < file_by_time.size(); loop++) {
      int index = file_by_time[loop];
      f = version->files_[level][index];

      if (!f->being_compacted) {
        candidate_count = 1;
        break;
      }
659 660 661 662
      LogToBuffer(log_buffer,
                  "[%s] Universal: file %lu[%d] being compacted, skipping",
                  version->cfd_->GetName().c_str(),
                  (unsigned long)f->fd.GetNumber(), loop);
I
Igor Canadi 已提交
663 664 665 666 667
      f = nullptr;
    }

    // This file is not being compacted. Consider it as the
    // first candidate to be compacted.
668
    uint64_t candidate_size =  f != nullptr? f->compensated_file_size : 0;
I
Igor Canadi 已提交
669
    if (f != nullptr) {
670 671 672 673
      LogToBuffer(log_buffer,
                  "[%s] Universal: Possible candidate file %lu[%d].",
                  version->cfd_->GetName().c_str(),
                  (unsigned long)f->fd.GetNumber(), loop);
I
Igor Canadi 已提交
674 675 676 677 678 679 680 681 682 683 684
    }

    // Check if the suceeding files need compaction.
    for (unsigned int i = loop+1;
         candidate_count < max_files_to_compact && i < file_by_time.size();
         i++) {
      int index = file_by_time[i];
      FileMetaData* f = version->files_[level][index];
      if (f->being_compacted) {
        break;
      }
685
      // Pick files if the total/last candidate file size (increased by the
I
Igor Canadi 已提交
686
      // specified ratio) is still larger than the next candidate file.
687 688 689 690
      // candidate_size is the total size of files picked so far with the
      // default kCompactionStopStyleTotalSize; with
      // kCompactionStopStyleSimilarSize, it's simply the size of the last
      // picked file.
I
Igor Canadi 已提交
691
      uint64_t sz = (candidate_size * (100L + ratio)) /100;
692
      if (sz < f->fd.GetFileSize()) {
I
Igor Canadi 已提交
693
        break;
694
      }
695 696 697
      if (options_->compaction_options_universal.stop_style == kCompactionStopStyleSimilarSize) {
        // Similar-size stopping rule: also check the last picked file isn't
        // far larger than the next candidate file.
698
        sz = (f->fd.GetFileSize() * (100L + ratio)) / 100;
699 700 701 702 703 704 705
        if (sz < candidate_size) {
          // If the small file we've encountered begins a run of similar-size
          // files, we'll pick them up on a future iteration of the outer
          // loop. If it's some lonely straggler, it'll eventually get picked
          // by the last-resort read amp strategy which disregards size ratios.
          break;
        }
706
        candidate_size = f->compensated_file_size;
707
      } else { // default kCompactionStopStyleTotalSize
708
        candidate_size += f->compensated_file_size;
I
Igor Canadi 已提交
709 710 711 712 713 714 715 716 717 718 719 720 721 722
      }
      candidate_count++;
    }

    // Found a series of consecutive files that need compaction.
    if (candidate_count >= (unsigned int)min_merge_width) {
      start_index = loop;
      done = true;
      break;
    } else {
      for (unsigned int i = loop;
           i < loop + candidate_count && i < file_by_time.size(); i++) {
       int index = file_by_time[i];
       FileMetaData* f = version->files_[level][index];
723
       LogToBuffer(log_buffer,
724 725 726 727
           "[%s] Universal: Skipping file %" PRIu64 "[%d] "
           "with size %" PRIu64 " (compensated size %" PRIu64 ") %d\n",
           version->cfd_->GetName().c_str(), f->fd.GetNumber(),
           i, f->fd.GetFileSize(), f->compensated_file_size, f->being_compacted);
I
Igor Canadi 已提交
728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744
      }
    }
  }
  if (!done || candidate_count <= 1) {
    return nullptr;
  }
  unsigned int first_index_after = start_index + candidate_count;
  // Compression is enabled if files compacted earlier already reached
  // size ratio of compression.
  bool enable_compression = true;
  int ratio_to_compress =
      options_->compaction_options_universal.compression_size_percent;
  if (ratio_to_compress >= 0) {
    uint64_t total_size = version->NumLevelBytes(level);
    uint64_t older_file_size = 0;
    for (unsigned int i = file_by_time.size() - 1; i >= first_index_after;
        i--) {
745 746
      older_file_size +=
          version->files_[level][file_by_time[i]]->fd.GetFileSize();
I
Igor Canadi 已提交
747 748 749 750 751 752 753 754 755 756 757 758 759 760 761
      if (older_file_size * 100L >= total_size * (long) ratio_to_compress) {
        enable_compression = false;
        break;
      }
    }
  }
  Compaction* c =
      new Compaction(version, level, level, MaxFileSizeForLevel(level),
                     LLONG_MAX, false, enable_compression);
  c->score_ = score;

  for (unsigned int i = start_index; i < first_index_after; i++) {
    int index = file_by_time[i];
    FileMetaData* f = c->input_version_->files_[level][index];
    c->inputs_[0].push_back(f);
762 763 764 765 766 767
    LogToBuffer(log_buffer,
                "[%s] Universal: Picking file %" PRIu64 "[%d] "
                "with size %" PRIu64 " (compensated size %" PRIu64 ")\n",
                version->cfd_->GetName().c_str(),
                f->fd.GetNumber(), i,
                f->fd.GetFileSize(), f->compensated_file_size);
I
Igor Canadi 已提交
768 769 770 771 772 773 774 775 776 777 778
  }
  return c;
}

// Look at overall size amplification. If size amplification
// exceeeds the configured value, then do a compaction
// of the candidate files all the way upto the earliest
// base file (overrides configured values of file-size ratios,
// min_merge_width and max_merge_width).
//
Compaction* UniversalCompactionPicker::PickCompactionUniversalSizeAmp(
779
    Version* version, double score, LogBuffer* log_buffer) {
I
Igor Canadi 已提交
780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802
  int level = 0;

  // percentage flexibilty while reducing size amplification
  uint64_t ratio = options_->compaction_options_universal.
                     max_size_amplification_percent;

  // The files are sorted from newest first to oldest last.
  std::vector<int>& file_by_time = version->files_by_size_[level];
  assert(file_by_time.size() == version->files_[level].size());

  unsigned int candidate_count = 0;
  uint64_t candidate_size = 0;
  unsigned int start_index = 0;
  FileMetaData* f = nullptr;

  // Skip files that are already being compacted
  for (unsigned int loop = 0; loop < file_by_time.size() - 1; loop++) {
    int index = file_by_time[loop];
    f = version->files_[level][index];
    if (!f->being_compacted) {
      start_index = loop;         // Consider this as the first candidate.
      break;
    }
803 804 805 806
    LogToBuffer(
        log_buffer, "[%s] Universal: skipping file %lu[%d] compacted %s",
        version->cfd_->GetName().c_str(), (unsigned long)f->fd.GetNumber(),
        loop, " cannot be a candidate to reduce size amp.\n");
I
Igor Canadi 已提交
807 808 809 810 811 812
    f = nullptr;
  }
  if (f == nullptr) {
    return nullptr;             // no candidate files
  }

I
Igor Canadi 已提交
813
  LogToBuffer(log_buffer, "[%s] Universal: First candidate file %lu[%d] %s",
814 815 816
              version->cfd_->GetName().c_str(),
              (unsigned long)f->fd.GetNumber(), start_index,
              " to reduce size amp.\n");
I
Igor Canadi 已提交
817 818 819 820 821 822 823

  // keep adding up all the remaining files
  for (unsigned int loop = start_index; loop < file_by_time.size() - 1;
       loop++) {
    int index = file_by_time[loop];
    f = version->files_[level][index];
    if (f->being_compacted) {
824
      LogToBuffer(
I
Igor Canadi 已提交
825
          log_buffer, "[%s] Universal: Possible candidate file %lu[%d] %s.",
826 827
          version->cfd_->GetName().c_str(), (unsigned long)f->fd.GetNumber(),
          loop,
I
Igor Canadi 已提交
828 829 830
          " is already being compacted. No size amp reduction possible.\n");
      return nullptr;
    }
831
    candidate_size += f->compensated_file_size;
I
Igor Canadi 已提交
832 833 834 835 836 837 838 839
    candidate_count++;
  }
  if (candidate_count == 0) {
    return nullptr;
  }

  // size of earliest file
  int index = file_by_time[file_by_time.size() - 1];
840
  uint64_t earliest_file_size = version->files_[level][index]->fd.GetFileSize();
I
Igor Canadi 已提交
841 842 843

  // size amplification = percentage of additional size
  if (candidate_size * 100 < ratio * earliest_file_size) {
I
Igor Canadi 已提交
844 845 846 847 848 849
    LogToBuffer(
        log_buffer,
        "[%s] Universal: size amp not needed. newer-files-total-size %lu "
        "earliest-file-size %lu",
        version->cfd_->GetName().c_str(), (unsigned long)candidate_size,
        (unsigned long)earliest_file_size);
I
Igor Canadi 已提交
850 851
    return nullptr;
  } else {
852
    LogToBuffer(log_buffer,
I
Igor Canadi 已提交
853
                "[%s] Universal: size amp needed. newer-files-total-size %lu "
854
                "earliest-file-size %lu",
I
Igor Canadi 已提交
855
                version->cfd_->GetName().c_str(), (unsigned long)candidate_size,
856
                (unsigned long)earliest_file_size);
I
Igor Canadi 已提交
857 858 859 860 861 862 863 864 865 866 867 868 869
  }
  assert(start_index >= 0 && start_index < file_by_time.size() - 1);

  // create a compaction request
  // We always compact all the files, so always compress.
  Compaction* c =
      new Compaction(version, level, level, MaxFileSizeForLevel(level),
                     LLONG_MAX, false, true);
  c->score_ = score;
  for (unsigned int loop = start_index; loop < file_by_time.size(); loop++) {
    int index = file_by_time[loop];
    f = c->input_version_->files_[level][index];
    c->inputs_[0].push_back(f);
870
    LogToBuffer(log_buffer,
871 872 873 874 875
        "[%s] Universal: size amp picking file %" PRIu64 "[%d] "
        "with size %" PRIu64 " (compensated size %" PRIu64 ")",
        version->cfd_->GetName().c_str(),
        f->fd.GetNumber(), index,
        f->fd.GetFileSize(), f->compensated_file_size);
I
Igor Canadi 已提交
876 877 878 879
  }
  return c;
}

I
Igor Canadi 已提交
880 881 882 883 884
Compaction* FIFOCompactionPicker::PickCompaction(Version* version,
                                                 LogBuffer* log_buffer) {
  assert(version->NumberLevels() == 1);
  uint64_t total_size = 0;
  for (const auto& file : version->files_[0]) {
885
    total_size += file->compensated_file_size;
I
Igor Canadi 已提交
886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912
  }

  if (total_size <= options_->compaction_options_fifo.max_table_files_size ||
      version->files_[0].size() == 0) {
    // total size not exceeded
    LogToBuffer(log_buffer,
                "[%s] FIFO compaction: nothing to do. Total size %" PRIu64
                ", max size %" PRIu64 "\n",
                version->cfd_->GetName().c_str(), total_size,
                options_->compaction_options_fifo.max_table_files_size);
    return nullptr;
  }

  if (compactions_in_progress_[0].size() > 0) {
    LogToBuffer(log_buffer,
                "[%s] FIFO compaction: Already executing compaction. No need "
                "to run parallel compactions since compactions are very fast",
                version->cfd_->GetName().c_str());
    return nullptr;
  }

  Compaction* c = new Compaction(version, 0, 0, 0, 0, false, false,
                                 true /* is deletion compaction */);
  // delete old files (FIFO)
  for (auto ritr = version->files_[0].rbegin();
       ritr != version->files_[0].rend(); ++ritr) {
    auto f = *ritr;
913
    total_size -= f->compensated_file_size;
I
Igor Canadi 已提交
914 915
    c->inputs_[0].push_back(f);
    char tmp_fsize[16];
916
    AppendHumanBytes(f->fd.GetFileSize(), tmp_fsize, sizeof(tmp_fsize));
I
Igor Canadi 已提交
917 918
    LogToBuffer(log_buffer, "[%s] FIFO compaction: picking file %" PRIu64
                            " with size %s for deletion",
919
                version->cfd_->GetName().c_str(), f->fd.GetNumber(), tmp_fsize);
I
Igor Canadi 已提交
920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945
    if (total_size <= options_->compaction_options_fifo.max_table_files_size) {
      break;
    }
  }

  c->MarkFilesBeingCompacted(true);
  compactions_in_progress_[0].insert(c);

  return c;
}

Compaction* FIFOCompactionPicker::CompactRange(Version* version,
                                               int input_level,
                                               int output_level,
                                               const InternalKey* begin,
                                               const InternalKey* end,
                                               InternalKey** compaction_end) {
  assert(input_level == 0);
  assert(output_level == 0);
  *compaction_end = nullptr;
  LogBuffer log_buffer(InfoLogLevel::INFO_LEVEL, options_->info_log.get());
  auto c = PickCompaction(version, &log_buffer);
  log_buffer.FlushBufferToLog();
  return c;
}

I
Igor Canadi 已提交
946
}  // namespace rocksdb