Page MenuHomePhabricator
Differential D580 Diff 1484 src/leveldb/db/version_set.cc

Changeset View

Standalone View

View Options

src/leveldb/db/version_set.cc

Show All 14 Lines
#include "leveldb/table_builder.h" #include "leveldb/table_builder.h"
#include "table/merger.h" #include "table/merger.h"
#include "table/two_level_iterator.h" #include "table/two_level_iterator.h"
#include "util/coding.h" #include "util/coding.h"
#include "util/logging.h" #include "util/logging.h"
namespace leveldb { namespace leveldb {
static const int kTargetFileSize = 2 * 1048576; static int TargetFileSize(const Options* options) {
return options->max_file_size;
}
// Maximum bytes of overlaps in grandparent (i.e., level+2) before we // Maximum bytes of overlaps in grandparent (i.e., level+2) before we
// stop building a single file in a level->level+1 compaction. // stop building a single file in a level->level+1 compaction.
static const int64_t kMaxGrandParentOverlapBytes = 10 * kTargetFileSize; static int64_t MaxGrandParentOverlapBytes(const Options* options) {
return 10 * TargetFileSize(options);
}
// Maximum number of bytes in all compacted files. We avoid expanding // Maximum number of bytes in all compacted files. We avoid expanding
// the lower level file set of a compaction if it would make the // the lower level file set of a compaction if it would make the
// total compaction cover more than this many bytes. // total compaction cover more than this many bytes.
static const int64_t kExpandedCompactionByteSizeLimit = 25 * kTargetFileSize; static int64_t ExpandedCompactionByteSizeLimit(const Options* options) {
return 25 * TargetFileSize(options);
}
static double MaxBytesForLevel(int level) { static double MaxBytesForLevel(const Options* options, int level) {
// Note: the result for level zero is not really used since we set // Note: the result for level zero is not really used since we set
// the level-0 compaction threshold based on number of files. // the level-0 compaction threshold based on number of files.
double result = 10 * 1048576.0; // Result for both level-0 and level-1
// Result for both level-0 and level-1
double result = 10. * 1048576.0;
while (level > 1) { while (level > 1) {
result *= 10; result *= 10;
level--; level--;
} }
return result; return result;
} }
static uint64_t MaxFileSizeForLevel(int level) { static uint64_t MaxFileSizeForLevel(const Options* options, int level) {
return kTargetFileSize; // We could vary per level to reduce number of files? // We could vary per level to reduce number of files?
return TargetFileSize(options);
} }
static int64_t TotalFileSize(const std::vector<FileMetaData*>& files) { static int64_t TotalFileSize(const std::vector<FileMetaData*>& files) {
int64_t sum = 0; int64_t sum = 0;
for (size_t i = 0; i < files.size(); i++) { for (size_t i = 0; i < files.size(); i++) {
sum += files[i]->file_size; sum += files[i]->file_size;
} }
return sum; return sum;
▲ Show 20 Lines • Show All 448 Lines • ▼ Show 20 Lines if (!OverlapInLevel(0, &smallest_user_key, &largest_user_key)) {
while (level < config::kMaxMemCompactLevel) { while (level < config::kMaxMemCompactLevel) {
if (OverlapInLevel(level + 1, &smallest_user_key, &largest_user_key)) { if (OverlapInLevel(level + 1, &smallest_user_key, &largest_user_key)) {
break; break;
} }
if (level + 2 < config::kNumLevels) { if (level + 2 < config::kNumLevels) {
// Check that file does not overlap too many grandparent bytes. // Check that file does not overlap too many grandparent bytes.
GetOverlappingInputs(level + 2, &start, &limit, &overlaps); GetOverlappingInputs(level + 2, &start, &limit, &overlaps);
const int64_t sum = TotalFileSize(overlaps); const int64_t sum = TotalFileSize(overlaps);
if (sum > kMaxGrandParentOverlapBytes) { if (sum > MaxGrandParentOverlapBytes(vset_->options_)) {
break; break;
} }
} }
level++; level++;
} }
} }
return level; return level;
} }
▲ Show 20 Lines • Show All 502 Lines • ▼ Show 20 Linesbool VersionSet::ReuseManifest(const std::string& dscname,
} }
FileType manifest_type; FileType manifest_type;
uint64_t manifest_number; uint64_t manifest_number;
uint64_t manifest_size; uint64_t manifest_size;
if (!ParseFileName(dscbase, &manifest_number, &manifest_type) || if (!ParseFileName(dscbase, &manifest_number, &manifest_type) ||
manifest_type != kDescriptorFile || manifest_type != kDescriptorFile ||
!env_->GetFileSize(dscname, &manifest_size).ok() || !env_->GetFileSize(dscname, &manifest_size).ok() ||
// Make new compacted MANIFEST if old one is too big // Make new compacted MANIFEST if old one is too big
manifest_size >= kTargetFileSize) { manifest_size >= TargetFileSize(options_)) {
return false; return false;
} }
assert(descriptor_file_ == NULL); assert(descriptor_file_ == NULL);
assert(descriptor_log_ == NULL); assert(descriptor_log_ == NULL);
Status r = env_->NewAppendableFile(dscname, &descriptor_file_); Status r = env_->NewAppendableFile(dscname, &descriptor_file_);
if (!r.ok()) { if (!r.ok()) {
Log(options_->info_log, "Reuse MANIFEST: %s\n", r.ToString().c_str()); Log(options_->info_log, "Reuse MANIFEST: %s\n", r.ToString().c_str());
Show All 32 Lines if (level == 0) {
// file size is small (perhaps because of a small write-buffer // file size is small (perhaps because of a small write-buffer
// setting, or very high compression ratios, or lots of // setting, or very high compression ratios, or lots of
// overwrites/deletions). // overwrites/deletions).
score = v->files_[level].size() / score = v->files_[level].size() /
static_cast<double>(config::kL0_CompactionTrigger); static_cast<double>(config::kL0_CompactionTrigger);
} else { } else {
// Compute the ratio of current size to size limit. // Compute the ratio of current size to size limit.
const uint64_t level_bytes = TotalFileSize(v->files_[level]); const uint64_t level_bytes = TotalFileSize(v->files_[level]);
score = static_cast<double>(level_bytes) / MaxBytesForLevel(level); score =
static_cast<double>(level_bytes) / MaxBytesForLevel(options_, level);
} }
if (score > best_score) { if (score > best_score) {
best_level = level; best_level = level;
best_score = score; best_score = score;
} }
} }
▲ Show 20 Lines • Show All 197 Lines • ▼ Show 20 LinesCompaction* VersionSet::PickCompaction() {
// We prefer compactions triggered by too much data in a level over // We prefer compactions triggered by too much data in a level over
// the compactions triggered by seeks. // the compactions triggered by seeks.
const bool size_compaction = (current_->compaction_score_ >= 1); const bool size_compaction = (current_->compaction_score_ >= 1);
const bool seek_compaction = (current_->file_to_compact_ != NULL); const bool seek_compaction = (current_->file_to_compact_ != NULL);
if (size_compaction) { if (size_compaction) {
level = current_->compaction_level_; level = current_->compaction_level_;
assert(level >= 0); assert(level >= 0);
assert(level+1 < config::kNumLevels); assert(level+1 < config::kNumLevels);
c = new Compaction(level); c = new Compaction(options_, level);
// Pick the first file that comes after compact_pointer_[level] // Pick the first file that comes after compact_pointer_[level]
for (size_t i = 0; i < current_->files_[level].size(); i++) { for (size_t i = 0; i < current_->files_[level].size(); i++) {
FileMetaData* f = current_->files_[level][i]; FileMetaData* f = current_->files_[level][i];
if (compact_pointer_[level].empty() || if (compact_pointer_[level].empty() ||
icmp_.Compare(f->largest.Encode(), compact_pointer_[level]) > 0) { icmp_.Compare(f->largest.Encode(), compact_pointer_[level]) > 0) {
c->inputs_[0].push_back(f); c->inputs_[0].push_back(f);
break; break;
} }
} }
if (c->inputs_[0].empty()) { if (c->inputs_[0].empty()) {
// Wrap-around to the beginning of the key space // Wrap-around to the beginning of the key space
c->inputs_[0].push_back(current_->files_[level][0]); c->inputs_[0].push_back(current_->files_[level][0]);
} }
} else if (seek_compaction) { } else if (seek_compaction) {
level = current_->file_to_compact_level_; level = current_->file_to_compact_level_;
c = new Compaction(level); c = new Compaction(options_, level);
c->inputs_[0].push_back(current_->file_to_compact_); c->inputs_[0].push_back(current_->file_to_compact_);
} else { } else {
return NULL; return NULL;
} }
c->input_version_ = current_; c->input_version_ = current_;
c->input_version_->Ref(); c->input_version_->Ref();
Show All 28 Linesvoid VersionSet::SetupOtherInputs(Compaction* c) {
// changing the number of "level+1" files we pick up. // changing the number of "level+1" files we pick up.
if (!c->inputs_[1].empty()) { if (!c->inputs_[1].empty()) {
std::vector<FileMetaData*> expanded0; std::vector<FileMetaData*> expanded0;
current_->GetOverlappingInputs(level, &all_start, &all_limit, &expanded0); current_->GetOverlappingInputs(level, &all_start, &all_limit, &expanded0);
const int64_t inputs0_size = TotalFileSize(c->inputs_[0]); const int64_t inputs0_size = TotalFileSize(c->inputs_[0]);
const int64_t inputs1_size = TotalFileSize(c->inputs_[1]); const int64_t inputs1_size = TotalFileSize(c->inputs_[1]);
const int64_t expanded0_size = TotalFileSize(expanded0); const int64_t expanded0_size = TotalFileSize(expanded0);
if (expanded0.size() > c->inputs_[0].size() && if (expanded0.size() > c->inputs_[0].size() &&
inputs1_size + expanded0_size < kExpandedCompactionByteSizeLimit) { inputs1_size + expanded0_size <
ExpandedCompactionByteSizeLimit(options_)) {
InternalKey new_start, new_limit; InternalKey new_start, new_limit;
GetRange(expanded0, &new_start, &new_limit); GetRange(expanded0, &new_start, &new_limit);
std::vector<FileMetaData*> expanded1; std::vector<FileMetaData*> expanded1;
current_->GetOverlappingInputs(level+1, &new_start, &new_limit, current_->GetOverlappingInputs(level+1, &new_start, &new_limit,
&expanded1); &expanded1);
if (expanded1.size() == c->inputs_[1].size()) { if (expanded1.size() == c->inputs_[1].size()) {
Log(options_->info_log, Log(options_->info_log,
"Expanding@%d %d+%d (%ld+%ld bytes) to %d+%d (%ld+%ld bytes)\n", "Expanding@%d %d+%d (%ld+%ld bytes) to %d+%d (%ld+%ld bytes)\n",
▲ Show 20 Lines • Show All 45 Lines • ▼ Show 20 Lines if (inputs.empty()) {
return NULL; return NULL;
} }
// Avoid compacting too much in one shot in case the range is large. // 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 // 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 // and we must not pick one file and drop another older file if the
// two files overlap. // two files overlap.
if (level > 0) { if (level > 0) {
const uint64_t limit = MaxFileSizeForLevel(level); const uint64_t limit = MaxFileSizeForLevel(options_, level);
uint64_t total = 0; uint64_t total = 0;
for (size_t i = 0; i < inputs.size(); i++) { for (size_t i = 0; i < inputs.size(); i++) {
uint64_t s = inputs[i]->file_size; uint64_t s = inputs[i]->file_size;
total += s; total += s;
if (total >= limit) { if (total >= limit) {
inputs.resize(i + 1); inputs.resize(i + 1);
break; break;
} }
} }
} }
Compaction* c = new Compaction(level); Compaction* c = new Compaction(options_, level);
c->input_version_ = current_; c->input_version_ = current_;
c->input_version_->Ref(); c->input_version_->Ref();
c->inputs_[0] = inputs; c->inputs_[0] = inputs;
SetupOtherInputs(c); SetupOtherInputs(c);
return c; return c;
} }
Compaction::Compaction(int level) Compaction::Compaction(const Options* options, int level)
: level_(level), : level_(level),
max_output_file_size_(MaxFileSizeForLevel(level)), max_output_file_size_(MaxFileSizeForLevel(options, level)),
input_version_(NULL), input_version_(NULL),
grandparent_index_(0), grandparent_index_(0),
seen_key_(false), seen_key_(false),
overlapped_bytes_(0) { overlapped_bytes_(0) {
for (int i = 0; i < config::kNumLevels; i++) { for (int i = 0; i < config::kNumLevels; i++) {
level_ptrs_[i] = 0; level_ptrs_[i] = 0;
} }
} }
Compaction::~Compaction() { Compaction::~Compaction() {
if (input_version_ != NULL) { if (input_version_ != NULL) {
input_version_->Unref(); input_version_->Unref();
} }
} }
bool Compaction::IsTrivialMove() const { bool Compaction::IsTrivialMove() const {
const VersionSet* vset = input_version_->vset_;
// Avoid a move if there is lots of overlapping grandparent data. // Avoid a move if there is lots of overlapping grandparent data.
// Otherwise, the move could create a parent file that will require // Otherwise, the move could create a parent file that will require
// a very expensive merge later on. // a very expensive merge later on.
return (num_input_files(0) == 1 && return (num_input_files(0) == 1 && num_input_files(1) == 0 &&
num_input_files(1) == 0 && TotalFileSize(grandparents_) <=
TotalFileSize(grandparents_) <= kMaxGrandParentOverlapBytes); MaxGrandParentOverlapBytes(vset->options_));
} }
void Compaction::AddInputDeletions(VersionEdit* edit) { void Compaction::AddInputDeletions(VersionEdit* edit) {
for (int which = 0; which < 2; which++) { for (int which = 0; which < 2; which++) {
for (size_t i = 0; i < inputs_[which].size(); i++) { for (size_t i = 0; i < inputs_[which].size(); i++) {
edit->DeleteFile(level_ + which, inputs_[which][i]->number); edit->DeleteFile(level_ + which, inputs_[which][i]->number);
} }
} }
Show All 16 Lines for (; level_ptrs_[lvl] < files.size(); ) {
} }
level_ptrs_[lvl]++; level_ptrs_[lvl]++;
} }
} }
return true; return true;
} }
bool Compaction::ShouldStopBefore(const Slice& internal_key) { bool Compaction::ShouldStopBefore(const Slice& internal_key) {
const VersionSet* vset = input_version_->vset_;
// Scan to find earliest grandparent file that contains key. // Scan to find earliest grandparent file that contains key.
const InternalKeyComparator* icmp = &input_version_->vset_->icmp_; const InternalKeyComparator* icmp = &vset->icmp_;
while (grandparent_index_ < grandparents_.size() && while (grandparent_index_ < grandparents_.size() &&
icmp->Compare(internal_key, icmp->Compare(internal_key,
grandparents_[grandparent_index_]->largest.Encode()) > 0) { grandparents_[grandparent_index_]->largest.Encode()) > 0) {
if (seen_key_) { if (seen_key_) {
overlapped_bytes_ += grandparents_[grandparent_index_]->file_size; overlapped_bytes_ += grandparents_[grandparent_index_]->file_size;
} }
grandparent_index_++; grandparent_index_++;
} }
seen_key_ = true; seen_key_ = true;
if (overlapped_bytes_ > kMaxGrandParentOverlapBytes) { if (overlapped_bytes_ > MaxGrandParentOverlapBytes(vset->options_)) {
// Too much overlap for current output; start new output // Too much overlap for current output; start new output
overlapped_bytes_ = 0; overlapped_bytes_ = 0;
return true; return true;
} else { } else {
return false; return false;
} }
} }
void Compaction::ReleaseInputs() { void Compaction::ReleaseInputs() {
if (input_version_ != NULL) { if (input_version_ != NULL) {
input_version_->Unref(); input_version_->Unref();
input_version_ = NULL; input_version_ = NULL;
} }
} }
} // namespace leveldb } // namespace leveldb