Changeset View
Changeset View
Standalone View
Standalone View
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 Lines | bool 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 Lines | Compaction* 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 Lines | void 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 |