compaction_picker.cc 37.3 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>
15
#include "db/filename.h"
H
Haobo Xu 已提交
16
#include "util/log_buffer.h"
I
Igor Canadi 已提交
17
#include "util/statistics.h"
I
Igor Canadi 已提交
18 19 20 21

namespace rocksdb {

namespace {
22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
// Determine compression type, based on user options, level of the output
// file and whether compression is disabled.
// If enable_compression is false, then compression is always disabled no
// matter what the values of the other two parameters are.
// Otherwise, the compression type is determined based on options and level.
CompressionType GetCompressionType(const Options& options, int level,
                                   const bool enable_compression = true) {
  if (!enable_compression) {
    // disable compression
    return kNoCompression;
  }
  // If the use has specified a different compression level for each level,
  // then pick the compresison for that level.
  if (!options.compression_per_level.empty()) {
    const int n = options.compression_per_level.size() - 1;
    // It is possible for level_ to be -1; in that case, we use level
    // 0's compression.  This occurs mostly in backwards compatibility
    // situations when the builder doesn't know what level the file
    // belongs to.  Likewise, if level_ is beyond the end of the
    // specified compression levels, use the last value.
    return options.compression_per_level[std::max(0, std::min(level, n))];
  } else {
    return options.compression;
  }
}
I
Igor Canadi 已提交
47

48
uint64_t TotalCompensatedFileSize(const std::vector<FileMetaData*>& files) {
I
Igor Canadi 已提交
49 50
  uint64_t sum = 0;
  for (size_t i = 0; i < files.size() && files[i]; i++) {
51
    sum += files[i]->compensated_file_size;
I
Igor Canadi 已提交
52 53 54 55
  }
  return sum;
}

56 57 58 59 60 61 62 63 64 65 66 67 68 69 70
// 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 已提交
71 72
}  // anonymous namespace

I
Igor Canadi 已提交
73 74
CompactionPicker::CompactionPicker(const Options* options,
                                   const InternalKeyComparator* icmp)
I
Igor Canadi 已提交
75 76 77 78 79 80 81 82 83 84 85 86 87 88
    : 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) {
89 90 91 92 93
      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 已提交
94 95 96 97 98 99 100 101 102 103 104 105 106 107 108
    } 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++) {
109
        total += c->input(0, i)->compensated_file_size;
I
Igor Canadi 已提交
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 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174
      }
    }
    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 已提交
175
bool CompactionPicker::ExpandWhileOverlapping(Compaction* c) {
I
Igor Canadi 已提交
176 177
  // If inputs are empty then there is nothing to expand.
  if (!c || c->inputs_[0].empty()) {
I
Igor Canadi 已提交
178
    return true;
I
Igor Canadi 已提交
179 180 181 182 183
  }

  // 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 已提交
184
    return true;
I
Igor Canadi 已提交
185 186 187 188 189 190 191 192 193 194 195 196
  }

  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();
197
    GetRange(c->inputs_[0].files, &smallest, &largest);
I
Igor Canadi 已提交
198 199
    c->inputs_[0].clear();
    c->input_version_->GetOverlappingInputs(
200 201
        level, &smallest, &largest, &c->inputs_[0].files,
        hint_index, &hint_index);
I
Igor Canadi 已提交
202 203 204
  } while(c->inputs_[0].size() > old_size);

  // Get the new range
205
  GetRange(c->inputs_[0].files, &smallest, &largest);
I
Igor Canadi 已提交
206 207 208 209

  // If, after the expansion, there are files that are already under
  // compaction, then we must drop/cancel this compaction.
  int parent_index = -1;
210 211
  if (c->inputs_[0].empty()) {
    Log(options_->info_log,
I
Igor Canadi 已提交
212 213
        "[%s] ExpandWhileOverlapping() failure because zero input files",
        c->column_family_data()->GetName().c_str());
214
  }
215
  if (c->inputs_[0].empty() || FilesInCompaction(c->inputs_[0].files) ||
I
Igor Canadi 已提交
216 217 218 219 220
      (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 已提交
221
    return false;
I
Igor Canadi 已提交
222
  }
I
Igor Canadi 已提交
223
  return true;
I
Igor Canadi 已提交
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 264 265 266 267 268 269 270
}

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.
271
  GetRange(c->inputs_[0].files, &smallest, &largest);
I
Igor Canadi 已提交
272 273

  // Populate the set of next-level files (inputs_[1]) to include in compaction
274 275 276 277
  c->input_version_->GetOverlappingInputs(
      level + 1, &smallest, &largest,
      &c->inputs_[1].files, c->parent_index_,
      &c->parent_index_);
I
Igor Canadi 已提交
278 279 280

  // Get entire range covered by compaction
  InternalKey all_start, all_limit;
281
  GetRange(c->inputs_[0].files, c->inputs_[1].files, &all_start, &all_limit);
I
Igor Canadi 已提交
282 283 284 285 286 287 288 289 290 291

  // 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);
292 293
    const uint64_t inputs0_size = TotalCompensatedFileSize(c->inputs_[0].files);
    const uint64_t inputs1_size = TotalCompensatedFileSize(c->inputs_[1].files);
294
    const uint64_t expanded0_size = TotalCompensatedFileSize(expanded0);
I
Igor Canadi 已提交
295 296 297 298 299 300 301 302 303 304 305 306 307
    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 已提交
308
        Log(options_->info_log,
309 310 311 312 313 314
            "[%s] Expanding@%d %zu+%zu (%" PRIu64 "+%" PRIu64
            " bytes) to %zu+%zu (%" PRIu64 "+%" PRIu64 "bytes)\n",
            c->column_family_data()->GetName().c_str(), level,
            c->inputs_[0].size(), c->inputs_[1].size(), inputs0_size,
            inputs1_size, expanded0.size(), expanded1.size(), expanded0_size,
            inputs1_size);
I
Igor Canadi 已提交
315 316
        smallest = new_start;
        largest = new_limit;
317 318 319 320
        c->inputs_[0].files = expanded0;
        c->inputs_[1].files = expanded1;
        GetRange(c->inputs_[0].files, c->inputs_[1].files,
                 &all_start, &all_limit);
I
Igor Canadi 已提交
321 322 323 324 325 326 327 328 329 330 331 332 333 334
      }
    }
  }

  // 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,
335
                                           uint32_t output_path_id,
I
Igor Canadi 已提交
336 337 338
                                           const InternalKey* begin,
                                           const InternalKey* end,
                                           InternalKey** compaction_end) {
I
Igor Canadi 已提交
339 340 341
  // CompactionPickerFIFO has its own implementation of compact range
  assert(options_->compaction_style != kCompactionStyleFIFO);

I
Igor Canadi 已提交
342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364
  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) {
365
      uint64_t s = inputs[i]->compensated_file_size;
I
Igor Canadi 已提交
366 367 368 369 370 371 372 373 374
      total += s;
      if (total >= limit) {
        **compaction_end = inputs[i + 1]->smallest;
        covering_the_whole_range = false;
        inputs.resize(i + 1);
        break;
      }
    }
  }
375 376 377 378 379
  assert(output_path_id < static_cast<uint32_t>(options_->db_paths.size()));
  Compaction* c = new Compaction(
      version, input_level, output_level, MaxFileSizeForLevel(output_level),
      MaxGrandParentOverlapBytes(input_level), output_path_id,
      GetCompressionType(*options_, output_level));
I
Igor Canadi 已提交
380

381
  c->inputs_[0].files = inputs;
I
Igor Canadi 已提交
382 383
  if (ExpandWhileOverlapping(c) == false) {
    delete c;
I
Igor Canadi 已提交
384 385 386
    Log(options_->info_log,
        "[%s] Could not compact due to expansion failure.\n",
        version->cfd_->GetName().c_str());
I
Igor Canadi 已提交
387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402
    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);
403 404 405

  c->is_manual_compaction_ = true;

I
Igor Canadi 已提交
406 407 408
  return c;
}

409 410
Compaction* LevelCompactionPicker::PickCompaction(Version* version,
                                                  LogBuffer* log_buffer) {
I
Igor Canadi 已提交
411 412 413
  Compaction* c = nullptr;
  int level = -1;

414 415 416 417 418 419
  // 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 已提交
420 421 422 423 424 425 426 427 428 429
  // 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 已提交
430 431 432 433
      if (ExpandWhileOverlapping(c) == false) {
        delete c;
        c = nullptr;
      } else {
I
Igor Canadi 已提交
434 435 436 437 438 439 440 441 442 443 444 445 446 447
        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;
448
    GetRange(c->inputs_[0].files, &smallest, &largest);
I
Igor Canadi 已提交
449 450 451 452 453
    // 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,
454
                                            &c->inputs_[0].files);
I
Igor Canadi 已提交
455 456 457 458

    // 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
459
    GetRange(c->inputs_[0].files, &smallest, &largest);
I
Igor Canadi 已提交
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 486 487 488 489 490 491 492 493 494 495 496 497 498
    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),
499
                     MaxGrandParentOverlapBytes(level), 0,
500
                     GetCompressionType(*options_, level + 1));
I
Igor Canadi 已提交
501 502 503 504 505 506 507 508 509 510 511 512 513 514
  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];

515
    // Check to verify files are arranged in descending compensated size.
516 517 518 519 520
    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 已提交
521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539

    // 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;
    }
540
    c->inputs_[0].files.push_back(f);
I
Igor Canadi 已提交
541 542 543 544 545 546 547 548 549 550 551
    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 已提交
552
  version->next_file_to_compact_by_size_[level] = nextIndex;
I
Igor Canadi 已提交
553 554 555 556 557 558 559

  return c;
}

// Universal style of compaction. Pick files that are contiguous in
// time-range to compact.
//
560 561
Compaction* UniversalCompactionPicker::PickCompaction(Version* version,
                                                      LogBuffer* log_buffer) {
I
Igor Canadi 已提交
562 563 564 565 566
  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 已提交
567 568
    LogToBuffer(log_buffer, "[%s] Universal: nothing to do\n",
                version->cfd_->GetName().c_str());
I
Igor Canadi 已提交
569 570 571
    return nullptr;
  }
  Version::FileSummaryStorage tmp;
I
Igor Canadi 已提交
572 573
  LogToBuffer(log_buffer, "[%s] Universal: candidate files(%zu): %s\n",
              version->cfd_->GetName().c_str(), version->files_[level].size(),
574
              version->LevelFileSummary(&tmp, 0));
I
Igor Canadi 已提交
575 576

  // Check for size amplification first.
M
Mike Lin 已提交
577
  Compaction* c;
578 579
  if ((c = PickCompactionUniversalSizeAmp(version, score, log_buffer)) !=
      nullptr) {
I
Igor Canadi 已提交
580 581
    LogToBuffer(log_buffer, "[%s] Universal: compacting for size amp\n",
                version->cfd_->GetName().c_str());
M
Mike Lin 已提交
582
  } else {
I
Igor Canadi 已提交
583 584 585 586
    // Size amplification is within limits. Try reducing read
    // amplification while maintaining file size ratios.
    unsigned int ratio = options_->compaction_options_universal.size_ratio;

587 588
    if ((c = PickCompactionUniversalReadAmp(version, score, ratio, UINT_MAX,
                                            log_buffer)) != nullptr) {
I
Igor Canadi 已提交
589 590
      LogToBuffer(log_buffer, "[%s] Universal: compacting for size ratio\n",
                  version->cfd_->GetName().c_str());
M
Mike Lin 已提交
591 592 593 594 595
    } 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 已提交
596 597
      unsigned int num_files = version->files_[level].size() -
                               options_->level0_file_num_compaction_trigger;
598 599
      if ((c = PickCompactionUniversalReadAmp(
               version, score, UINT_MAX, num_files, log_buffer)) != nullptr) {
I
Igor Canadi 已提交
600 601
        LogToBuffer(log_buffer, "[%s] Universal: compacting for file num\n",
                    version->cfd_->GetName().c_str());
M
Mike Lin 已提交
602
      }
I
Igor Canadi 已提交
603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620
    }
  }
  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;
  }

  // Is the earliest file part of this compaction?
621
  FileMetaData* last_file = c->input_version_->files_[level].back();
622
  c->bottommost_level_ = c->inputs_[0].files.back() == last_file;
I
Igor Canadi 已提交
623

I
Igor Canadi 已提交
624
  // update statistics
L
Lei Jin 已提交
625 626
  MeasureTime(options_->statistics.get(),
              NUM_FILES_IN_SINGLE_COMPACTION, c->inputs_[0].size());
I
Igor Canadi 已提交
627

I
Igor Canadi 已提交
628 629 630 631 632 633 634 635 636 637 638 639 640 641
  // 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;
}

642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672
uint32_t UniversalCompactionPicker::GetPathId(const Options& options,
                                              uint64_t file_size) {
  // Two conditions need to be satisfied:
  // (1) the target path needs to be able to hold the file's size
  // (2) Total size left in this and previous paths need to be not
  //     smaller than expected future file size before this new file is
  //     compacted, which is estimated based on size_ratio.
  // For example, if now we are compacting files of size (1, 1, 2, 4, 8),
  // we will make sure the target file, probably with size of 16, will be
  // placed in a path so that eventually when new files are generated and
  // compacted to (1, 1, 2, 4, 8, 16), all those files can be stored in or
  // before the path we chose.
  //
  // TODO(sdong): now the case of multiple column families is not
  // considered in this algorithm. So the target size can be violated in
  // that case. We need to improve it.
  uint64_t accumulated_size = 0;
  uint64_t future_size =
      file_size * (100 - options.compaction_options_universal.size_ratio) / 100;
  uint32_t p = 0;
  for (; p < options.db_paths.size() - 1; p++) {
    uint64_t target_size = options.db_paths[p].target_size;
    if (target_size > file_size &&
        accumulated_size + (target_size - file_size) > future_size) {
      return p;
    }
    accumulated_size += target_size;
  }
  return p;
}

I
Igor Canadi 已提交
673 674 675 676 677 678
//
// 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,
679
    unsigned int max_number_of_files_to_compact, LogBuffer* log_buffer) {
I
Igor Canadi 已提交
680 681 682 683 684 685 686 687
  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.
688 689
  const auto& files = version->files_[level];

I
Igor Canadi 已提交
690 691 692
  FileMetaData* f = nullptr;
  bool done = false;
  int start_index = 0;
I
Igor Canadi 已提交
693
  unsigned int candidate_count = 0;
I
Igor Canadi 已提交
694 695 696 697 698 699 700

  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.
701
  for (unsigned int loop = 0; loop < files.size(); loop++) {
I
Igor Canadi 已提交
702 703 704 705

    candidate_count = 0;

    // Skip files that are already being compacted
706 707
    for (f = nullptr; loop < files.size(); loop++) {
      f = files[loop];
I
Igor Canadi 已提交
708 709 710 711 712

      if (!f->being_compacted) {
        candidate_count = 1;
        break;
      }
713 714 715
      LogToBuffer(log_buffer, "[%s] Universal: file %" PRIu64
                              "[%d] being compacted, skipping",
                  version->cfd_->GetName().c_str(), f->fd.GetNumber(), loop);
I
Igor Canadi 已提交
716 717 718 719 720
      f = nullptr;
    }

    // This file is not being compacted. Consider it as the
    // first candidate to be compacted.
721
    uint64_t candidate_size =  f != nullptr? f->compensated_file_size : 0;
I
Igor Canadi 已提交
722
    if (f != nullptr) {
723 724 725 726
      LogToBuffer(
          log_buffer, "[%s] Universal: Possible candidate file %s[%d].",
          version->cfd_->GetName().c_str(),
          FormatFileNumber(f->fd.GetNumber(), f->fd.GetPathId()).c_str(), loop);
I
Igor Canadi 已提交
727 728 729
    }

    // Check if the suceeding files need compaction.
730 731 732
    for (unsigned int i = loop + 1;
         candidate_count < max_files_to_compact && i < files.size(); i++) {
      FileMetaData* f = files[i];
I
Igor Canadi 已提交
733 734 735
      if (f->being_compacted) {
        break;
      }
736
      // Pick files if the total/last candidate file size (increased by the
I
Igor Canadi 已提交
737
      // specified ratio) is still larger than the next candidate file.
738 739 740 741
      // 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 已提交
742
      uint64_t sz = (candidate_size * (100L + ratio)) /100;
743
      if (sz < f->fd.GetFileSize()) {
I
Igor Canadi 已提交
744
        break;
745
      }
746 747 748
      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.
749
        sz = (f->fd.GetFileSize() * (100L + ratio)) / 100;
750 751 752 753 754 755 756
        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;
        }
757
        candidate_size = f->compensated_file_size;
758
      } else { // default kCompactionStopStyleTotalSize
759
        candidate_size += f->compensated_file_size;
I
Igor Canadi 已提交
760 761 762 763 764 765 766 767 768 769 770
      }
      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;
771 772 773 774 775 776 777 778
           i < loop + candidate_count && i < files.size(); i++) {
        FileMetaData* f = files[i];
        LogToBuffer(log_buffer, "[%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 已提交
779 780 781 782 783 784 785 786 787 788 789 790 791 792 793
      }
    }
  }
  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;
794 795 796
    for (unsigned int i = files.size() - 1;
         i >= first_index_after; i--) {
      older_file_size += files[i]->fd.GetFileSize();
I
Igor Canadi 已提交
797 798 799 800 801 802
      if (older_file_size * 100L >= total_size * (long) ratio_to_compress) {
        enable_compression = false;
        break;
      }
    }
  }
803 804 805 806 807 808 809

  uint64_t estimated_total_size = 0;
  for (unsigned int i = 0; i < first_index_after; i++) {
    estimated_total_size += files[i]->fd.GetFileSize();
  }
  uint32_t path_id = GetPathId(*options_, estimated_total_size);

810
  Compaction* c = new Compaction(
811
      version, level, level, MaxFileSizeForLevel(level), LLONG_MAX, path_id,
812
      GetCompressionType(*options_, level, enable_compression));
I
Igor Canadi 已提交
813 814 815
  c->score_ = score;

  for (unsigned int i = start_index; i < first_index_after; i++) {
816
    FileMetaData* f = c->input_version_->files_[level][i];
817
    c->inputs_[0].files.push_back(f);
818
    LogToBuffer(log_buffer,
819
                "[%s] Universal: Picking file %s[%d] "
820 821
                "with size %" PRIu64 " (compensated size %" PRIu64 ")\n",
                version->cfd_->GetName().c_str(),
822 823
                FormatFileNumber(f->fd.GetNumber(), f->fd.GetPathId()).c_str(),
                i, f->fd.GetFileSize(), f->compensated_file_size);
I
Igor Canadi 已提交
824 825 826 827 828 829 830 831 832 833 834
  }
  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(
835
    Version* version, double score, LogBuffer* log_buffer) {
I
Igor Canadi 已提交
836 837 838 839 840 841 842
  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.
843
  const auto& files = version->files_[level];
I
Igor Canadi 已提交
844 845 846 847 848 849 850

  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
851 852
  for (unsigned int loop = 0; loop < files.size() - 1; loop++) {
    f = files[loop];
I
Igor Canadi 已提交
853 854 855 856
    if (!f->being_compacted) {
      start_index = loop;         // Consider this as the first candidate.
      break;
    }
857 858 859 860
    LogToBuffer(log_buffer, "[%s] Universal: skipping file %s[%d] compacted %s",
                version->cfd_->GetName().c_str(),
                FormatFileNumber(f->fd.GetNumber(), f->fd.GetPathId()).c_str(),
                loop, " cannot be a candidate to reduce size amp.\n");
I
Igor Canadi 已提交
861 862 863 864 865 866
    f = nullptr;
  }
  if (f == nullptr) {
    return nullptr;             // no candidate files
  }

867 868 869 870
  LogToBuffer(log_buffer, "[%s] Universal: First candidate file %s[%d] %s",
              version->cfd_->GetName().c_str(),
              FormatFileNumber(f->fd.GetNumber(), f->fd.GetPathId()).c_str(),
              start_index, " to reduce size amp.\n");
I
Igor Canadi 已提交
871 872

  // keep adding up all the remaining files
873 874
  for (unsigned int loop = start_index; loop < files.size() - 1; loop++) {
    f = files[loop];
I
Igor Canadi 已提交
875
    if (f->being_compacted) {
876
      LogToBuffer(
877 878 879
          log_buffer, "[%s] Universal: Possible candidate file %s[%d] %s.",
          version->cfd_->GetName().c_str(),
          FormatFileNumber(f->fd.GetNumber(), f->fd.GetPathId()).c_str(), loop,
I
Igor Canadi 已提交
880 881 882
          " is already being compacted. No size amp reduction possible.\n");
      return nullptr;
    }
883
    candidate_size += f->compensated_file_size;
I
Igor Canadi 已提交
884 885 886 887 888 889 890
    candidate_count++;
  }
  if (candidate_count == 0) {
    return nullptr;
  }

  // size of earliest file
891
  uint64_t earliest_file_size = files.back()->fd.GetFileSize();
I
Igor Canadi 已提交
892 893 894

  // size amplification = percentage of additional size
  if (candidate_size * 100 < ratio * earliest_file_size) {
I
Igor Canadi 已提交
895 896
    LogToBuffer(
        log_buffer,
897 898 899
        "[%s] Universal: size amp not needed. newer-files-total-size %" PRIu64
        "earliest-file-size %" PRIu64,
        version->cfd_->GetName().c_str(), candidate_size, earliest_file_size);
I
Igor Canadi 已提交
900 901
    return nullptr;
  } else {
902 903 904 905 906
    LogToBuffer(
        log_buffer,
        "[%s] Universal: size amp needed. newer-files-total-size %" PRIu64
        "earliest-file-size %" PRIu64,
        version->cfd_->GetName().c_str(), candidate_size, earliest_file_size);
I
Igor Canadi 已提交
907
  }
908
  assert(start_index >= 0 && start_index < files.size() - 1);
I
Igor Canadi 已提交
909

910 911 912 913 914 915 916
  // Estimate total file size
  uint64_t estimated_total_size = 0;
  for (unsigned int loop = start_index; loop < files.size(); loop++) {
    estimated_total_size += files[loop]->fd.GetFileSize();
  }
  uint32_t path_id = GetPathId(*options_, estimated_total_size);

I
Igor Canadi 已提交
917 918 919 920
  // create a compaction request
  // We always compact all the files, so always compress.
  Compaction* c =
      new Compaction(version, level, level, MaxFileSizeForLevel(level),
921
                     LLONG_MAX, path_id, GetCompressionType(*options_, level));
I
Igor Canadi 已提交
922
  c->score_ = score;
923 924
  for (unsigned int loop = start_index; loop < files.size(); loop++) {
    f = c->input_version_->files_[level][loop];
925
    c->inputs_[0].files.push_back(f);
926
    LogToBuffer(log_buffer,
927 928 929
        "[%s] Universal: size amp picking file %" PRIu64 "[%d] "
        "with size %" PRIu64 " (compensated size %" PRIu64 ")",
        version->cfd_->GetName().c_str(),
I
Igor Canadi 已提交
930
        f->fd.GetNumber(), loop,
931
        f->fd.GetFileSize(), f->compensated_file_size);
I
Igor Canadi 已提交
932 933 934 935
  }
  return c;
}

I
Igor Canadi 已提交
936 937 938 939 940
Compaction* FIFOCompactionPicker::PickCompaction(Version* version,
                                                 LogBuffer* log_buffer) {
  assert(version->NumberLevels() == 1);
  uint64_t total_size = 0;
  for (const auto& file : version->files_[0]) {
941
    total_size += file->compensated_file_size;
I
Igor Canadi 已提交
942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962
  }

  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;
  }

963
  Compaction* c = new Compaction(version, 0, 0, 0, 0, 0, kNoCompression, false,
I
Igor Canadi 已提交
964 965 966 967 968
                                 true /* is deletion compaction */);
  // delete old files (FIFO)
  for (auto ritr = version->files_[0].rbegin();
       ritr != version->files_[0].rend(); ++ritr) {
    auto f = *ritr;
969
    total_size -= f->compensated_file_size;
970
    c->inputs_[0].files.push_back(f);
I
Igor Canadi 已提交
971
    char tmp_fsize[16];
972
    AppendHumanBytes(f->fd.GetFileSize(), tmp_fsize, sizeof(tmp_fsize));
I
Igor Canadi 已提交
973 974
    LogToBuffer(log_buffer, "[%s] FIFO compaction: picking file %" PRIu64
                            " with size %s for deletion",
975
                version->cfd_->GetName().c_str(), f->fd.GetNumber(), tmp_fsize);
I
Igor Canadi 已提交
976 977 978 979 980 981 982 983 984 985 986
    if (total_size <= options_->compaction_options_fifo.max_table_files_size) {
      break;
    }
  }

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

  return c;
}

987 988 989 990
Compaction* FIFOCompactionPicker::CompactRange(
    Version* version, int input_level, int output_level,
    uint32_t output_path_id, const InternalKey* begin, const InternalKey* end,
    InternalKey** compaction_end) {
I
Igor Canadi 已提交
991 992 993 994
  assert(input_level == 0);
  assert(output_level == 0);
  *compaction_end = nullptr;
  LogBuffer log_buffer(InfoLogLevel::INFO_LEVEL, options_->info_log.get());
995 996 997 998 999
  Compaction* c = PickCompaction(version, &log_buffer);
  if (c != nullptr) {
    assert(output_path_id < static_cast<uint32_t>(options_->db_paths.size()));
    c->output_path_id_ = output_path_id;
  }
I
Igor Canadi 已提交
1000 1001 1002 1003
  log_buffer.FlushBufferToLog();
  return c;
}

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