23 static const int kTargetFileSize = 2 * 1048576;
27 static const int64_t kMaxGrandParentOverlapBytes = 10 * kTargetFileSize;
32 static const int64_t kExpandedCompactionByteSizeLimit = 25 * kTargetFileSize;
34 static double MaxBytesForLevel(
int level) {
37 double result = 10 * 1048576.0;
45 static uint64_t MaxFileSizeForLevel(
int level) {
46 return kTargetFileSize;
49 static int64_t TotalFileSize(
const std::vector<FileMetaData*>& files) {
51 for (
size_t i = 0; i < files.size(); i++) {
52 sum += files[i]->file_size;
58 std::string IntSetToString(
const std::set<uint64_t>& s) {
59 std::string result =
"{";
60 for (std::set<uint64_t>::const_iterator it = s.begin();
63 result += (result.size() > 1) ?
"," :
"";
79 for (
int level = 0; level < config::kNumLevels; level++) {
80 for (
size_t i = 0; i <
files_[level].size(); i++) {
92 const std::vector<FileMetaData*>& files,
96 while (left < right) {
99 if (icmp.InternalKeyComparator::Compare(f->
largest.
Encode(), key) < 0) {
112 static bool AfterFile(
const Comparator*
ucmp,
113 const Slice*
user_key,
const FileMetaData* f) {
115 return (user_key != NULL &&
116 ucmp->Compare(*user_key, f->largest.user_key()) > 0);
119 static bool BeforeFile(
const Comparator* ucmp,
120 const Slice* user_key,
const FileMetaData* f) {
122 return (user_key != NULL &&
123 ucmp->Compare(*user_key, f->smallest.user_key()) < 0);
128 bool disjoint_sorted_files,
129 const std::vector<FileMetaData*>& files,
130 const Slice* smallest_user_key,
131 const Slice* largest_user_key) {
133 if (!disjoint_sorted_files) {
135 for (
size_t i = 0; i < files.size(); i++) {
137 if (AfterFile(ucmp, smallest_user_key, f) ||
138 BeforeFile(ucmp, largest_user_key, f)) {
149 if (smallest_user_key != NULL) {
151 InternalKey small(*smallest_user_key, kMaxSequenceNumber,kValueTypeForSeek);
155 if (index >= files.size()) {
160 return !BeforeFile(ucmp, largest_user_key, files[index]);
171 const std::vector<FileMetaData*>* flist)
211 const std::vector<FileMetaData*>*
const flist_;
220 const Slice& file_value) {
222 if (file_value.
size() != 16) {
240 std::vector<Iterator*>* iters) {
242 for (
size_t i = 0; i <
files_[0].size(); i++) {
245 options,
files_[0][i]->number,
files_[0][i]->file_size));
251 for (
int level = 1; level < config::kNumLevels; level++) {
252 if (!
files_[level].empty()) {
273 static void SaveValue(
void* arg,
const Slice& ikey,
const Slice& v) {
274 Saver* s =
reinterpret_cast<Saver*
>(
arg);
275 ParsedInternalKey parsed_key;
279 if (s->ucmp->Compare(parsed_key.user_key, s->user_key) == 0) {
280 s->state = (parsed_key.type ==
kTypeValue) ? kFound : kDeleted;
281 if (s->state == kFound) {
282 s->value->assign(v.data(), v.size());
288 static bool NewestFirst(FileMetaData* a, FileMetaData* b) {
289 return a->number > b->number;
299 std::vector<FileMetaData*> tmp;
300 tmp.reserve(
files_[0].size());
309 std::sort(tmp.begin(), tmp.end(), NewestFirst);
310 for (
uint32_t i = 0; i < tmp.size(); i++) {
311 if (!(*
func)(
arg, 0, tmp[i])) {
318 for (
int level = 1; level < config::kNumLevels; level++) {
319 size_t num_files =
files_[level].size();
320 if (num_files == 0)
continue;
324 if (index < num_files) {
349 int last_file_read_level = -1;
354 std::vector<FileMetaData*> tmp;
356 for (
int level = 0; level < config::kNumLevels; level++) {
357 size_t num_files =
files_[level].size();
358 if (num_files == 0)
continue;
365 tmp.reserve(num_files);
366 for (
uint32_t i = 0; i < num_files; i++) {
373 if (tmp.empty())
continue;
375 std::sort(tmp.begin(), tmp.end(), NewestFirst);
377 num_files = tmp.size();
381 if (index >= num_files) {
397 for (
uint32_t i = 0; i < num_files; ++i) {
398 if (last_file_read != NULL && stats->
seek_file == NULL) {
406 last_file_read_level = level;
409 saver.state = kNotFound;
414 ikey, &saver, SaveValue);
418 switch (saver.state) {
459 static bool Match(
void* arg,
int level,
FileMetaData* f) {
462 if (state->matches == 1) {
464 state->stats.seek_file = f;
465 state->stats.seek_file_level = level;
468 return state->matches < 2;
480 if (state.matches >= 2) {
501 const Slice* smallest_user_key,
502 const Slice* largest_user_key) {
504 smallest_user_key, largest_user_key);
508 const Slice& smallest_user_key,
509 const Slice& largest_user_key) {
514 InternalKey start(smallest_user_key, kMaxSequenceNumber, kValueTypeForSeek);
515 InternalKey limit(largest_user_key, 0, static_cast<ValueType>(0));
516 std::vector<FileMetaData*> overlaps;
517 while (level < config::kMaxMemCompactLevel) {
518 if (
OverlapInLevel(level + 1, &smallest_user_key, &largest_user_key)) {
521 if (level + 2 < config::kNumLevels) {
524 const int64_t sum = TotalFileSize(overlaps);
525 if (sum > kMaxGrandParentOverlapBytes) {
540 std::vector<FileMetaData*>* inputs) {
542 assert(level < config::kNumLevels);
544 Slice user_begin, user_end;
552 for (
size_t i = 0; i <
files_[level].size(); ) {
556 if (begin != NULL && user_cmp->
Compare(file_limit, user_begin) < 0) {
558 }
else if (end != NULL && user_cmp->
Compare(file_start, user_end) > 0) {
561 inputs->push_back(f);
565 if (begin != NULL && user_cmp->
Compare(file_start, user_begin) < 0) {
566 user_begin = file_start;
569 }
else if (end != NULL && user_cmp->
Compare(file_limit, user_end) > 0) {
570 user_end = file_limit;
581 for (
int level = 0; level < config::kNumLevels; level++) {
586 r.append(
"--- level ");
589 const std::vector<FileMetaData*>& files =
files_[level];
590 for (
size_t i = 0; i < files.size(); i++) {
596 r.append(files[i]->smallest.DebugString());
598 r.append(files[i]->largest.DebugString());
625 typedef std::set<FileMetaData*, BySmallestKey>
FileSet;
643 for (
int level = 0; level < config::kNumLevels; level++) {
649 for (
int level = 0; level < config::kNumLevels; level++) {
651 std::vector<FileMetaData*> to_unref;
652 to_unref.reserve(added->size());
653 for (FileSet::const_iterator it = added->begin();
654 it != added->end(); ++it) {
655 to_unref.push_back(*it);
658 for (
uint32_t i = 0; i < to_unref.size(); i++) {
680 for (VersionEdit::DeletedFileSet::const_iterator iter = del.begin();
683 const int level = iter->first;
684 const uint64_t number = iter->second;
689 for (
size_t i = 0; i < edit->
new_files_.size(); i++) {
719 for (
int level = 0; level < config::kNumLevels; level++) {
722 const std::vector<FileMetaData*>& base_files = base_->
files_[level];
723 std::vector<FileMetaData*>::const_iterator base_iter = base_files.begin();
724 std::vector<FileMetaData*>::const_iterator base_end = base_files.end();
726 v->
files_[level].reserve(base_files.size() + added->size());
727 for (FileSet::const_iterator added_iter = added->begin();
728 added_iter != added->end();
731 for (std::vector<FileMetaData*>::const_iterator bpos
732 = std::upper_bound(base_iter, base_end, *added_iter, cmp);
742 for (; base_iter != base_end; ++base_iter) {
753 fprintf(stderr,
"overlapping ranges in same level %s vs. %s\n",
765 if (levels_[level].deleted_files.count(f->
number) > 0) {
768 std::vector<FileMetaData*>* files = &v->
files_[level];
769 if (level > 0 && !files->empty()) {
771 assert(vset_->
icmp_.
Compare((*files)[files->size()-1]->largest,
784 :
env_(options->env),
790 manifest_file_number_(0),
794 descriptor_file_(NULL),
795 descriptor_log_(NULL),
796 dummy_versions_(this),
810 assert(v->
refs_ == 0);
850 std::string new_manifest_file;
881 "MANIFEST contains log record despite error; advancing to new "
882 "version to prevent mismatch between in-memory and logged state");
890 if (s.
ok() && !new_manifest_file.empty()) {
906 if (!new_manifest_file.empty()) {
921 virtual void Corruption(
size_t bytes,
const Status& s) {
922 if (this->status->
ok()) *this->status = s;
932 if (current.empty() || current[current.size()-1] !=
'\n') {
935 current.resize(current.size() - 1);
944 bool have_log_number =
false;
945 bool have_prev_log_number =
false;
946 bool have_next_file =
false;
947 bool have_last_sequence =
false;
955 LogReporter reporter;
956 reporter.status = &s;
960 while (reader.
ReadRecord(&record, &scratch) && s.
ok()) {
967 edit.
comparator_ +
" does not match existing comparator ",
973 builder.
Apply(&edit);
978 have_log_number =
true;
983 have_prev_log_number =
true;
988 have_next_file =
true;
993 have_last_sequence =
true;
1001 if (!have_next_file) {
1003 }
else if (!have_log_number) {
1005 }
else if (!have_last_sequence) {
1009 if (!have_prev_log_number) {
1010 prev_log_number = 0;
1041 int best_level = -1;
1042 double best_score = -1;
1044 for (
int level = 0; level < config::kNumLevels-1; level++) {
1058 score = v->
files_[level].size() /
1059 static_cast<double>(config::kL0_CompactionTrigger);
1063 score =
static_cast<double>(level_bytes) / MaxBytesForLevel(level);
1066 if (score > best_score) {
1084 for (
int level = 0; level < config::kNumLevels; level++) {
1093 for (
int level = 0; level < config::kNumLevels; level++) {
1094 const std::vector<FileMetaData*>& files =
current_->
files_[level];
1095 for (
size_t i = 0; i < files.size(); i++) {
1108 assert(level < config::kNumLevels);
1114 assert(config::kNumLevels == 7);
1116 "files[ %d %d %d %d %d %d %d ]",
1139 std::string scratch;
1140 bool result =
false;
1142 if (r ==
Slice(record)) {
1154 for (
int level = 0; level < config::kNumLevels; level++) {
1155 const std::vector<FileMetaData*>& files = v->
files_[level];
1156 for (
size_t i = 0; i < files.size(); i++) {
1159 result += files[i]->file_size;
1160 }
else if (
icmp_.
Compare(files[i]->smallest, ikey) > 0) {
1173 ReadOptions(), files[i]->number, files[i]->file_size, &tableptr);
1174 if (tableptr != NULL) {
1188 for (
int level = 0; level < config::kNumLevels; level++) {
1189 const std::vector<FileMetaData*>& files = v->files_[level];
1190 for (
size_t i = 0; i < files.size(); i++) {
1191 live->insert(files[i]->number);
1199 assert(level < config::kNumLevels);
1205 std::vector<FileMetaData*> overlaps;
1206 for (
int level = 1; level < config::kNumLevels - 1; level++) {
1211 const int64_t sum = TotalFileSize(overlaps);
1226 assert(!inputs.empty());
1229 for (
size_t i = 0; i < inputs.size(); i++) {
1249 const std::vector<FileMetaData*>& inputs2,
1252 std::vector<FileMetaData*> all = inputs1;
1253 all.insert(all.end(), inputs2.begin(), inputs2.end());
1265 const int space = (c->
level() == 0 ? c->
inputs_[0].size() + 1 : 2);
1268 for (
int which = 0; which < 2; which++) {
1269 if (!c->
inputs_[which].empty()) {
1270 if (c->
level() + which == 0) {
1271 const std::vector<FileMetaData*>& files = c->
inputs_[which];
1272 for (
size_t i = 0; i < files.size(); i++) {
1274 options, files[i]->number, files[i]->file_size);
1284 assert(num <= space);
1298 if (size_compaction) {
1301 assert(level+1 < config::kNumLevels);
1317 }
else if (seek_compaction) {
1336 assert(!c->
inputs_[0].empty());
1345 const int level = c->
level();
1358 std::vector<FileMetaData*> expanded0;
1362 const int64_t expanded0_size = TotalFileSize(expanded0);
1363 if (expanded0.size() > c->
inputs_[0].size() &&
1364 inputs1_size + expanded0_size < kExpandedCompactionByteSizeLimit) {
1366 GetRange(expanded0, &new_start, &new_limit);
1367 std::vector<FileMetaData*> expanded1;
1370 if (expanded1.size() == c->
inputs_[1].size()) {
1372 "Expanding@%d %d+%d (%ld+%ld bytes) to %d+%d (%ld+%ld bytes)\n",
1376 long(inputs0_size), long(inputs1_size),
1377 int(expanded0.size()),
1378 int(expanded1.size()),
1379 long(expanded0_size), long(inputs1_size));
1380 smallest = new_start;
1381 largest = new_limit;
1391 if (level + 2 < config::kNumLevels) {
1415 std::vector<FileMetaData*> inputs;
1417 if (inputs.empty()) {
1426 const uint64_t limit = MaxFileSizeForLevel(level);
1428 for (
size_t i = 0; i < inputs.size(); i++) {
1431 if (total >= limit) {
1432 inputs.resize(i + 1);
1448 max_output_file_size_(MaxFileSizeForLevel(level)),
1449 input_version_(NULL),
1450 grandparent_index_(0),
1452 overlapped_bytes_(0) {
1453 for (
int i = 0; i < config::kNumLevels; i++) {
1470 TotalFileSize(
grandparents_) <= kMaxGrandParentOverlapBytes);
1474 for (
int which = 0; which < 2; which++) {
1475 for (
size_t i = 0; i <
inputs_[which].size(); i++) {
1484 for (
int lvl =
level_ + 2; lvl < config::kNumLevels; lvl++) {
uint64_t ApproximateOffsetOf(Version *v, const InternalKey &key)
LevelFileNumIterator(const InternalKeyComparator &icmp, const std::vector< FileMetaData * > *flist)
std::string DebugString() const
bool IsBaseLevelForKey(const Slice &user_key)
void ForEachOverlapping(Slice user_key, Slice internal_key, void *arg, bool(*func)(void *, int, FileMetaData *))
std::string compact_pointer_[config::kNumLevels]
virtual Status DeleteFile(const std::string &fname)=0
void SetCompactPointer(int level, const InternalKey &key)
const std::vector< FileMetaData * > *const flist_
void AddInputDeletions(VersionEdit *edit)
void SetPrevLogNumber(uint64_t num)
int PickLevelForMemTableOutput(const Slice &smallest_user_key, const Slice &largest_user_key)
void GetRange(const std::vector< FileMetaData * > &inputs, InternalKey *smallest, InternalKey *largest)
const std::string dbname_
bool OverlapInLevel(int level, const Slice *smallest_user_key, const Slice *largest_user_key)
void GetOverlappingInputs(int level, const InternalKey *begin, const InternalKey *end, std::vector< FileMetaData * > *inputs)
void DecodeFrom(const Slice &s)
void Apply(VersionEdit *edit)
void SetLogNumber(uint64_t num)
Status WriteSnapshot(log::Writer *log)
uint64_t DecodeFixed64(const char *ptr)
uint64_t ApproximateOffsetOf(const Slice &key) const
VersionSet(const std::string &dbname, const Options *options, TableCache *table_cache, const InternalKeyComparator *)
bool ReadRecord(Slice *record, std::string *scratch)
uint64_t prev_log_number_
const char * data() const
const Options *const options_
uint64_t next_file_number_
const InternalKeyComparator * internal_comparator
Slice internal_key() const
int64_t MaxNextLevelOverlappingBytes()
Compaction * CompactRange(int level, const InternalKey *begin, const InternalKey *end)
static Status Corruption(const Slice &msg, const Slice &msg2=Slice())
uint64_t next_file_number_
std::vector< std::pair< int, InternalKey > > compact_pointers_
void Finalize(Version *v)
const char * LevelSummary(LevelSummaryStorage *scratch) const
void AddFile(int level, uint64_t file, uint64_t file_size, const InternalKey &smallest, const InternalKey &largest)
LevelState levels_[config::kNumLevels]
bool RecordReadSample(Slice key)
Iterator * NewConcatenatingIterator(const ReadOptions &, int level) const
bool IsTrivialMove() const
DeletedFileSet deleted_files_
void Log(Logger *info_log, const char *format,...)
SequenceNumber last_sequence_
Iterator * MakeInputIterator(Compaction *c)
std::vector< std::pair< int, FileMetaData > > new_files_
bool SomeFileOverlapsRange(const InternalKeyComparator &icmp, bool disjoint_sorted_files, const std::vector< FileMetaData * > &files, const Slice *smallest_user_key, const Slice *largest_user_key)
Status AddRecord(const Slice &slice)
bool ParseInternalKey(const Slice &internal_key, ParsedInternalKey *result)
Status LogAndApply(VersionEdit *edit, port::Mutex *mu) EXCLUSIVE_LOCKS_REQUIRED(mu)
std::set< FileMetaData *, BySmallestKey > FileSet
IteratorWrapper * current_
void SetComparatorName(const Slice &name)
Version * current() const
bool ManifestContains(const std::string &record) const
bool UpdateStats(const GetStats &stats)
static Status InvalidArgument(const Slice &msg, const Slice &msg2=Slice())
log::Writer * descriptor_log_
FileMetaData * file_to_compact_
bool operator()(FileMetaData *f1, FileMetaData *f2) const
bool has_next_file_number_
void EncodeFixed64(char *buf, uint64_t value)
int file_to_compact_level_
std::string DescriptorFileName(const std::string &dbname, uint64_t number)
virtual int Compare(const Slice &a, const Slice &b) const
Builder(VersionSet *vset, Version *base)
unsigned long long uint64_t
int64_t overlapped_bytes_
Iterator * NewErrorIterator(const Status &status)
uint64_t prev_log_number_
void AddLiveFiles(std::set< uint64_t > *live)
std::set< std::pair< int, uint64_t > > DeletedFileSet
Status SetCurrentFile(Env *env, const std::string &dbname, uint64_t descriptor_number)
std::string CurrentFileName(const std::string &dbname)
void SetLastSequence(SequenceNumber seq)
const InternalKeyComparator icmp_
int NumLevelFiles(int level) const
virtual void SeekToFirst()
uint64_t manifest_file_number_
virtual Status status() const
static Status NotFound(const Slice &msg, const Slice &msg2=Slice())
std::vector< FileMetaData * > inputs_[2]
TableCache * table_cache_
virtual Status NewSequentialFile(const std::string &fname, SequentialFile **result)=0
void MarkFileNumberUsed(uint64_t number)
std::string const dbname_
const Comparator * user_comparator() const
bool has_prev_log_number_
Status DecodeFrom(const Slice &src)
std::set< uint64_t > deleted_files
std::string DebugString() const
Iterator * NewMergingIterator(const Comparator *cmp, Iterator **list, int n)
void DeleteFile(int level, uint64_t file)
size_t grandparent_index_
int num_input_files(int which) const
virtual const char * Name() const =0
Status Get(const ReadOptions &options, uint64_t file_number, uint64_t file_size, const Slice &k, void *arg, void(*handle_result)(void *, const Slice &, const Slice &))
Iterator * NewTwoLevelIterator(Iterator *index_iter, BlockFunction block_function, void *arg, const ReadOptions &options)
void EncodeTo(std::string *dst) const
std::vector< FileMetaData * > grandparents_
size_t level_ptrs_[config::kNumLevels]
virtual int Compare(const Slice &a, const Slice &b) const =0
Status Get(const ReadOptions &, const LookupKey &key, std::string *val, GetStats *stats)
virtual bool Valid() const
void SetNextFile(uint64_t num)
virtual void SeekToLast()
uint64_t next_file_number_
Iterator * NewIterator(const ReadOptions &options, uint64_t file_number, uint64_t file_size, Table **tableptr=NULL)
WritableFile * descriptor_file_
virtual Status NewWritableFile(const std::string &fname, WritableFile **result)=0
void MaybeAddFile(Version *v, int level, FileMetaData *f)
TableCache *const table_cache_
void SetupOtherInputs(Compaction *c)
void AddIterators(const ReadOptions &, std::vector< Iterator * > *iters)
void AppendVersion(Version *v)
InternalKeyComparator const icmp_
virtual void Seek(const Slice &target)
int FindFile(const InternalKeyComparator &icmp, const std::vector< FileMetaData * > &files, const Slice &key)
std::string ToString() const
void GetRange2(const std::vector< FileMetaData * > &inputs1, const std::vector< FileMetaData * > &inputs2, InternalKey *smallest, InternalKey *largest)
std::string NumberToString(uint64_t num)
const InternalKeyComparator icmp_
bool ShouldStopBefore(const Slice &internal_key)
void AppendNumberTo(std::string *str, uint64_t num)
Compaction * PickCompaction()
Status ReadFileToString(Env *env, const std::string &fname, std::string *data)
std::string ToString() const
std::vector< FileMetaData * > files_[config::kNumLevels]
int64_t NumLevelBytes(int level) const