1// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file. See the AUTHORS file for names of contributors.
4
5#include "db/version_set.h"
6
7#include <algorithm>
8#include <cstdio>
9
10#include "db/filename.h"
11#include "db/log_reader.h"
12#include "db/log_writer.h"
13#include "db/memtable.h"
14#include "db/table_cache.h"
15#include "leveldb/env.h"
16#include "leveldb/table_builder.h"
17#include "table/merger.h"
18#include "table/two_level_iterator.h"
19#include "util/coding.h"
20#include "util/logging.h"
21
22namespace leveldb {
23
24static size_t TargetFileSize(const Options* options) {
25 return options->max_file_size;
26}
27
28// Maximum bytes of overlaps in grandparent (i.e., level+2) before we
29// stop building a single file in a level->level+1 compaction.
30static int64_t MaxGrandParentOverlapBytes(const Options* options) {
31 return 10 * TargetFileSize(options);
32}
33
34// Maximum number of bytes in all compacted files. We avoid expanding
35// the lower level file set of a compaction if it would make the
36// total compaction cover more than this many bytes.
37static int64_t ExpandedCompactionByteSizeLimit(const Options* options) {
38 return 25 * TargetFileSize(options);
39}
40
41static double MaxBytesForLevel(const Options* options, int level) {
42 // Note: the result for level zero is not really used since we set
43 // the level-0 compaction threshold based on number of files.
44
45 // Result for both level-0 and level-1
46 double result = 10. * 1048576.0;
47 while (level > 1) {
48 result *= 10;
49 level--;
50 }
51 return result;
52}
53
54static uint64_t MaxFileSizeForLevel(const Options* options, int level) {
55 // We could vary per level to reduce number of files?
56 return TargetFileSize(options);
57}
58
59static int64_t TotalFileSize(const std::vector<FileMetaData*>& files) {
60 int64_t sum = 0;
61 for (size_t i = 0; i < files.size(); i++) {
62 sum += files[i]->file_size;
63 }
64 return sum;
65}
66
67Version::~Version() {
68 assert(refs_ == 0);
69
70 // Remove from linked list
71 prev_->next_ = next_;
72 next_->prev_ = prev_;
73
74 // Drop references to files
75 for (int level = 0; level < config::kNumLevels; level++) {
76 for (size_t i = 0; i < files_[level].size(); i++) {
77 FileMetaData* f = files_[level][i];
78 assert(f->refs > 0);
79 f->refs--;
80 if (f->refs <= 0) {
81 delete f;
82 }
83 }
84 }
85}
86
87int FindFile(const InternalKeyComparator& icmp,
88 const std::vector<FileMetaData*>& files, const Slice& key) {
89 uint32_t left = 0;
90 uint32_t right = files.size();
91 while (left < right) {
92 uint32_t mid = (left + right) / 2;
93 const FileMetaData* f = files[mid];
94 if (icmp.InternalKeyComparator::Compare(f->largest.Encode(), key) < 0) {
95 // Key at "mid.largest" is < "target". Therefore all
96 // files at or before "mid" are uninteresting.
97 left = mid + 1;
98 } else {
99 // Key at "mid.largest" is >= "target". Therefore all files
100 // after "mid" are uninteresting.
101 right = mid;
102 }
103 }
104 return right;
105}
106
107static bool AfterFile(const Comparator* ucmp, const Slice* user_key,
108 const FileMetaData* f) {
109 // null user_key occurs before all keys and is therefore never after *f
110 return (user_key != nullptr &&
111 ucmp->Compare(*user_key, f->largest.user_key()) > 0);
112}
113
114static bool BeforeFile(const Comparator* ucmp, const Slice* user_key,
115 const FileMetaData* f) {
116 // null user_key occurs after all keys and is therefore never before *f
117 return (user_key != nullptr &&
118 ucmp->Compare(*user_key, f->smallest.user_key()) < 0);
119}
120
121bool SomeFileOverlapsRange(const InternalKeyComparator& icmp,
122 bool disjoint_sorted_files,
123 const std::vector<FileMetaData*>& files,
124 const Slice* smallest_user_key,
125 const Slice* largest_user_key) {
126 const Comparator* ucmp = icmp.user_comparator();
127 if (!disjoint_sorted_files) {
128 // Need to check against all files
129 for (size_t i = 0; i < files.size(); i++) {
130 const FileMetaData* f = files[i];
131 if (AfterFile(ucmp, smallest_user_key, f) ||
132 BeforeFile(ucmp, largest_user_key, f)) {
133 // No overlap
134 } else {
135 return true; // Overlap
136 }
137 }
138 return false;
139 }
140
141 // Binary search over file list
142 uint32_t index = 0;
143 if (smallest_user_key != nullptr) {
144 // Find the earliest possible internal key for smallest_user_key
145 InternalKey small_key(*smallest_user_key, kMaxSequenceNumber,
146 kValueTypeForSeek);
147 index = FindFile(icmp, files, small_key.Encode());
148 }
149
150 if (index >= files.size()) {
151 // beginning of range is after all files, so no overlap.
152 return false;
153 }
154
155 return !BeforeFile(ucmp, largest_user_key, files[index]);
156}
157
158// An internal iterator. For a given version/level pair, yields
159// information about the files in the level. For a given entry, key()
160// is the largest key that occurs in the file, and value() is an
161// 16-byte value containing the file number and file size, both
162// encoded using EncodeFixed64.
163class Version::LevelFileNumIterator : public Iterator {
164 public:
165 LevelFileNumIterator(const InternalKeyComparator& icmp,
166 const std::vector<FileMetaData*>* flist)
167 : icmp_(icmp), flist_(flist), index_(flist->size()) { // Marks as invalid
168 }
169 bool Valid() const override { return index_ < flist_->size(); }
170 void Seek(const Slice& target) override {
171 index_ = FindFile(icmp_, *flist_, target);
172 }
173 void SeekToFirst() override { index_ = 0; }
174 void SeekToLast() override {
175 index_ = flist_->empty() ? 0 : flist_->size() - 1;
176 }
177 void Next() override {
178 assert(Valid());
179 index_++;
180 }
181 void Prev() override {
182 assert(Valid());
183 if (index_ == 0) {
184 index_ = flist_->size(); // Marks as invalid
185 } else {
186 index_--;
187 }
188 }
189 Slice key() const override {
190 assert(Valid());
191 return (*flist_)[index_]->largest.Encode();
192 }
193 Slice value() const override {
194 assert(Valid());
195 EncodeFixed64(value_buf_, (*flist_)[index_]->number);
196 EncodeFixed64(value_buf_ + 8, (*flist_)[index_]->file_size);
197 return Slice(value_buf_, sizeof(value_buf_));
198 }
199 Status status() const override { return Status::OK(); }
200
201 private:
202 const InternalKeyComparator icmp_;
203 const std::vector<FileMetaData*>* const flist_;
204 uint32_t index_;
205
206 // Backing store for value(). Holds the file number and size.
207 mutable char value_buf_[16];
208};
209
210static Iterator* GetFileIterator(void* arg, const ReadOptions& options,
211 const Slice& file_value) {
212 TableCache* cache = reinterpret_cast<TableCache*>(arg);
213 if (file_value.size() != 16) {
214 return NewErrorIterator(
215 Status::Corruption("FileReader invoked with unexpected value"));
216 } else {
217 return cache->NewIterator(options, DecodeFixed64(file_value.data()),
218 DecodeFixed64(file_value.data() + 8));
219 }
220}
221
222Iterator* Version::NewConcatenatingIterator(const ReadOptions& options,
223 int level) const {
224 return NewTwoLevelIterator(
225 new LevelFileNumIterator(vset_->icmp_, &files_[level]), &GetFileIterator,
226 vset_->table_cache_, options);
227}
228
229void Version::AddIterators(const ReadOptions& options,
230 std::vector<Iterator*>* iters) {
231 // Merge all level zero files together since they may overlap
232 for (size_t i = 0; i < files_[0].size(); i++) {
233 iters->push_back(vset_->table_cache_->NewIterator(
234 options, files_[0][i]->number, files_[0][i]->file_size));
235 }
236
237 // For levels > 0, we can use a concatenating iterator that sequentially
238 // walks through the non-overlapping files in the level, opening them
239 // lazily.
240 for (int level = 1; level < config::kNumLevels; level++) {
241 if (!files_[level].empty()) {
242 iters->push_back(NewConcatenatingIterator(options, level));
243 }
244 }
245}
246
247// Callback from TableCache::Get()
248namespace {
249enum SaverState {
250 kNotFound,
251 kFound,
252 kDeleted,
253 kCorrupt,
254};
255struct Saver {
256 SaverState state;
257 const Comparator* ucmp;
258 Slice user_key;
259 std::string* value;
260};
261} // namespace
262static void SaveValue(void* arg, const Slice& ikey, const Slice& v) {
263 Saver* s = reinterpret_cast<Saver*>(arg);
264 ParsedInternalKey parsed_key;
265 if (!ParseInternalKey(ikey, &parsed_key)) {
266 s->state = kCorrupt;
267 } else {
268 if (s->ucmp->Compare(parsed_key.user_key, s->user_key) == 0) {
269 s->state = (parsed_key.type == kTypeValue) ? kFound : kDeleted;
270 if (s->state == kFound) {
271 s->value->assign(v.data(), v.size());
272 }
273 }
274 }
275}
276
277static bool NewestFirst(FileMetaData* a, FileMetaData* b) {
278 return a->number > b->number;
279}
280
281void Version::ForEachOverlapping(Slice user_key, Slice internal_key, void* arg,
282 bool (*func)(void*, int, FileMetaData*)) {
283 const Comparator* ucmp = vset_->icmp_.user_comparator();
284
285 // Search level-0 in order from newest to oldest.
286 std::vector<FileMetaData*> tmp;
287 tmp.reserve(files_[0].size());
288 for (uint32_t i = 0; i < files_[0].size(); i++) {
289 FileMetaData* f = files_[0][i];
290 if (ucmp->Compare(user_key, f->smallest.user_key()) >= 0 &&
291 ucmp->Compare(user_key, f->largest.user_key()) <= 0) {
292 tmp.push_back(f);
293 }
294 }
295 if (!tmp.empty()) {
296 std::sort(tmp.begin(), tmp.end(), NewestFirst);
297 for (uint32_t i = 0; i < tmp.size(); i++) {
298 if (!(*func)(arg, 0, tmp[i])) {
299 return;
300 }
301 }
302 }
303
304 // Search other levels.
305 for (int level = 1; level < config::kNumLevels; level++) {
306 size_t num_files = files_[level].size();
307 if (num_files == 0) continue;
308
309 // Binary search to find earliest index whose largest key >= internal_key.
310 uint32_t index = FindFile(vset_->icmp_, files_[level], internal_key);
311 if (index < num_files) {
312 FileMetaData* f = files_[level][index];
313 if (ucmp->Compare(user_key, f->smallest.user_key()) < 0) {
314 // All of "f" is past any data for user_key
315 } else {
316 if (!(*func)(arg, level, f)) {
317 return;
318 }
319 }
320 }
321 }
322}
323
324Status Version::Get(const ReadOptions& options, const LookupKey& k,
325 std::string* value, GetStats* stats) {
326 stats->seek_file = nullptr;
327 stats->seek_file_level = -1;
328
329 struct State {
330 Saver saver;
331 GetStats* stats;
332 const ReadOptions* options;
333 Slice ikey;
334 FileMetaData* last_file_read;
335 int last_file_read_level;
336
337 VersionSet* vset;
338 Status s;
339 bool found;
340
341 static bool Match(void* arg, int level, FileMetaData* f) {
342 State* state = reinterpret_cast<State*>(arg);
343
344 if (state->stats->seek_file == nullptr &&
345 state->last_file_read != nullptr) {
346 // We have had more than one seek for this read. Charge the 1st file.
347 state->stats->seek_file = state->last_file_read;
348 state->stats->seek_file_level = state->last_file_read_level;
349 }
350
351 state->last_file_read = f;
352 state->last_file_read_level = level;
353
354 state->s = state->vset->table_cache_->Get(*state->options, f->number,
355 f->file_size, state->ikey,
356 &state->saver, SaveValue);
357 if (!state->s.ok()) {
358 state->found = true;
359 return false;
360 }
361 switch (state->saver.state) {
362 case kNotFound:
363 return true; // Keep searching in other files
364 case kFound:
365 state->found = true;
366 return false;
367 case kDeleted:
368 return false;
369 case kCorrupt:
370 state->s =
371 Status::Corruption("corrupted key for ", state->saver.user_key);
372 state->found = true;
373 return false;
374 }
375
376 // Not reached. Added to avoid false compilation warnings of
377 // "control reaches end of non-void function".
378 return false;
379 }
380 };
381
382 State state;
383 state.found = false;
384 state.stats = stats;
385 state.last_file_read = nullptr;
386 state.last_file_read_level = -1;
387
388 state.options = &options;
389 state.ikey = k.internal_key();
390 state.vset = vset_;
391
392 state.saver.state = kNotFound;
393 state.saver.ucmp = vset_->icmp_.user_comparator();
394 state.saver.user_key = k.user_key();
395 state.saver.value = value;
396
397 ForEachOverlapping(state.saver.user_key, state.ikey, &state, &State::Match);
398
399 return state.found ? state.s : Status::NotFound(Slice());
400}
401
402bool Version::UpdateStats(const GetStats& stats) {
403 FileMetaData* f = stats.seek_file;
404 if (f != nullptr) {
405 f->allowed_seeks--;
406 if (f->allowed_seeks <= 0 && file_to_compact_ == nullptr) {
407 file_to_compact_ = f;
408 file_to_compact_level_ = stats.seek_file_level;
409 return true;
410 }
411 }
412 return false;
413}
414
415bool Version::RecordReadSample(Slice internal_key) {
416 ParsedInternalKey ikey;
417 if (!ParseInternalKey(internal_key, &ikey)) {
418 return false;
419 }
420
421 struct State {
422 GetStats stats; // Holds first matching file
423 int matches;
424
425 static bool Match(void* arg, int level, FileMetaData* f) {
426 State* state = reinterpret_cast<State*>(arg);
427 state->matches++;
428 if (state->matches == 1) {
429 // Remember first match.
430 state->stats.seek_file = f;
431 state->stats.seek_file_level = level;
432 }
433 // We can stop iterating once we have a second match.
434 return state->matches < 2;
435 }
436 };
437
438 State state;
439 state.matches = 0;
440 ForEachOverlapping(ikey.user_key, internal_key, &state, &State::Match);
441
442 // Must have at least two matches since we want to merge across
443 // files. But what if we have a single file that contains many
444 // overwrites and deletions? Should we have another mechanism for
445 // finding such files?
446 if (state.matches >= 2) {
447 // 1MB cost is about 1 seek (see comment in Builder::Apply).
448 return UpdateStats(state.stats);
449 }
450 return false;
451}
452
453void Version::Ref() { ++refs_; }
454
455void Version::Unref() {
456 assert(this != &vset_->dummy_versions_);
457 assert(refs_ >= 1);
458 --refs_;
459 if (refs_ == 0) {
460 delete this;
461 }
462}
463
464bool Version::OverlapInLevel(int level, const Slice* smallest_user_key,
465 const Slice* largest_user_key) {
466 return SomeFileOverlapsRange(vset_->icmp_, (level > 0), files_[level],
467 smallest_user_key, largest_user_key);
468}
469
470int Version::PickLevelForMemTableOutput(const Slice& smallest_user_key,
471 const Slice& largest_user_key) {
472 int level = 0;
473 if (!OverlapInLevel(0, &smallest_user_key, &largest_user_key)) {
474 // Push to next level if there is no overlap in next level,
475 // and the #bytes overlapping in the level after that are limited.
476 InternalKey start(smallest_user_key, kMaxSequenceNumber, kValueTypeForSeek);
477 InternalKey limit(largest_user_key, 0, static_cast<ValueType>(0));
478 std::vector<FileMetaData*> overlaps;
479 while (level < config::kMaxMemCompactLevel) {
480 if (OverlapInLevel(level + 1, &smallest_user_key, &largest_user_key)) {
481 break;
482 }
483 if (level + 2 < config::kNumLevels) {
484 // Check that file does not overlap too many grandparent bytes.
485 GetOverlappingInputs(level + 2, &start, &limit, &overlaps);
486 const int64_t sum = TotalFileSize(overlaps);
487 if (sum > MaxGrandParentOverlapBytes(vset_->options_)) {
488 break;
489 }
490 }
491 level++;
492 }
493 }
494 return level;
495}
496
497// Store in "*inputs" all files in "level" that overlap [begin,end]
498void Version::GetOverlappingInputs(int level, const InternalKey* begin,
499 const InternalKey* end,
500 std::vector<FileMetaData*>* inputs) {
501 assert(level >= 0);
502 assert(level < config::kNumLevels);
503 inputs->clear();
504 Slice user_begin, user_end;
505 if (begin != nullptr) {
506 user_begin = begin->user_key();
507 }
508 if (end != nullptr) {
509 user_end = end->user_key();
510 }
511 const Comparator* user_cmp = vset_->icmp_.user_comparator();
512 for (size_t i = 0; i < files_[level].size();) {
513 FileMetaData* f = files_[level][i++];
514 const Slice file_start = f->smallest.user_key();
515 const Slice file_limit = f->largest.user_key();
516 if (begin != nullptr && user_cmp->Compare(file_limit, user_begin) < 0) {
517 // "f" is completely before specified range; skip it
518 } else if (end != nullptr && user_cmp->Compare(file_start, user_end) > 0) {
519 // "f" is completely after specified range; skip it
520 } else {
521 inputs->push_back(f);
522 if (level == 0) {
523 // Level-0 files may overlap each other. So check if the newly
524 // added file has expanded the range. If so, restart search.
525 if (begin != nullptr && user_cmp->Compare(file_start, user_begin) < 0) {
526 user_begin = file_start;
527 inputs->clear();
528 i = 0;
529 } else if (end != nullptr &&
530 user_cmp->Compare(file_limit, user_end) > 0) {
531 user_end = file_limit;
532 inputs->clear();
533 i = 0;
534 }
535 }
536 }
537 }
538}
539
540std::string Version::DebugString() const {
541 std::string r;
542 for (int level = 0; level < config::kNumLevels; level++) {
543 // E.g.,
544 // --- level 1 ---
545 // 17:123['a' .. 'd']
546 // 20:43['e' .. 'g']
547 r.append("--- level ");
548 AppendNumberTo(&r, level);
549 r.append(" ---\n");
550 const std::vector<FileMetaData*>& files = files_[level];
551 for (size_t i = 0; i < files.size(); i++) {
552 r.push_back(' ');
553 AppendNumberTo(&r, files[i]->number);
554 r.push_back(':');
555 AppendNumberTo(&r, files[i]->file_size);
556 r.append("[");
557 r.append(files[i]->smallest.DebugString());
558 r.append(" .. ");
559 r.append(files[i]->largest.DebugString());
560 r.append("]\n");
561 }
562 }
563 return r;
564}
565
566// A helper class so we can efficiently apply a whole sequence
567// of edits to a particular state without creating intermediate
568// Versions that contain full copies of the intermediate state.
569class VersionSet::Builder {
570 private:
571 // Helper to sort by v->files_[file_number].smallest
572 struct BySmallestKey {
573 const InternalKeyComparator* internal_comparator;
574
575 bool operator()(FileMetaData* f1, FileMetaData* f2) const {
576 int r = internal_comparator->Compare(f1->smallest, f2->smallest);
577 if (r != 0) {
578 return (r < 0);
579 } else {
580 // Break ties by file number
581 return (f1->number < f2->number);
582 }
583 }
584 };
585
586 typedef std::set<FileMetaData*, BySmallestKey> FileSet;
587 struct LevelState {
588 std::set<uint64_t> deleted_files;
589 FileSet* added_files;
590 };
591
592 VersionSet* vset_;
593 Version* base_;
594 LevelState levels_[config::kNumLevels];
595
596 public:
597 // Initialize a builder with the files from *base and other info from *vset
598 Builder(VersionSet* vset, Version* base) : vset_(vset), base_(base) {
599 base_->Ref();
600 BySmallestKey cmp;
601 cmp.internal_comparator = &vset_->icmp_;
602 for (int level = 0; level < config::kNumLevels; level++) {
603 levels_[level].added_files = new FileSet(cmp);
604 }
605 }
606
607 ~Builder() {
608 for (int level = 0; level < config::kNumLevels; level++) {
609 const FileSet* added = levels_[level].added_files;
610 std::vector<FileMetaData*> to_unref;
611 to_unref.reserve(added->size());
612 for (FileSet::const_iterator it = added->begin(); it != added->end();
613 ++it) {
614 to_unref.push_back(*it);
615 }
616 delete added;
617 for (uint32_t i = 0; i < to_unref.size(); i++) {
618 FileMetaData* f = to_unref[i];
619 f->refs--;
620 if (f->refs <= 0) {
621 delete f;
622 }
623 }
624 }
625 base_->Unref();
626 }
627
628 // Apply all of the edits in *edit to the current state.
629 void Apply(const VersionEdit* edit) {
630 // Update compaction pointers
631 for (size_t i = 0; i < edit->compact_pointers_.size(); i++) {
632 const int level = edit->compact_pointers_[i].first;
633 vset_->compact_pointer_[level] =
634 edit->compact_pointers_[i].second.Encode().ToString();
635 }
636
637 // Delete files
638 for (const auto& deleted_file_set_kvp : edit->deleted_files_) {
639 const int level = deleted_file_set_kvp.first;
640 const uint64_t number = deleted_file_set_kvp.second;
641 levels_[level].deleted_files.insert(number);
642 }
643
644 // Add new files
645 for (size_t i = 0; i < edit->new_files_.size(); i++) {
646 const int level = edit->new_files_[i].first;
647 FileMetaData* f = new FileMetaData(edit->new_files_[i].second);
648 f->refs = 1;
649
650 // We arrange to automatically compact this file after
651 // a certain number of seeks. Let's assume:
652 // (1) One seek costs 10ms
653 // (2) Writing or reading 1MB costs 10ms (100MB/s)
654 // (3) A compaction of 1MB does 25MB of IO:
655 // 1MB read from this level
656 // 10-12MB read from next level (boundaries may be misaligned)
657 // 10-12MB written to next level
658 // This implies that 25 seeks cost the same as the compaction
659 // of 1MB of data. I.e., one seek costs approximately the
660 // same as the compaction of 40KB of data. We are a little
661 // conservative and allow approximately one seek for every 16KB
662 // of data before triggering a compaction.
663 f->allowed_seeks = static_cast<int>((f->file_size / 16384U));
664 if (f->allowed_seeks < 100) f->allowed_seeks = 100;
665
666 levels_[level].deleted_files.erase(f->number);
667 levels_[level].added_files->insert(f);
668 }
669 }
670
671 // Save the current state in *v.
672 void SaveTo(Version* v) {
673 BySmallestKey cmp;
674 cmp.internal_comparator = &vset_->icmp_;
675 for (int level = 0; level < config::kNumLevels; level++) {
676 // Merge the set of added files with the set of pre-existing files.
677 // Drop any deleted files. Store the result in *v.
678 const std::vector<FileMetaData*>& base_files = base_->files_[level];
679 std::vector<FileMetaData*>::const_iterator base_iter = base_files.begin();
680 std::vector<FileMetaData*>::const_iterator base_end = base_files.end();
681 const FileSet* added_files = levels_[level].added_files;
682 v->files_[level].reserve(base_files.size() + added_files->size());
683 for (const auto& added_file : *added_files) {
684 // Add all smaller files listed in base_
685 for (std::vector<FileMetaData*>::const_iterator bpos =
686 std::upper_bound(base_iter, base_end, added_file, cmp);
687 base_iter != bpos; ++base_iter) {
688 MaybeAddFile(v, level, *base_iter);
689 }
690
691 MaybeAddFile(v, level, added_file);
692 }
693
694 // Add remaining base files
695 for (; base_iter != base_end; ++base_iter) {
696 MaybeAddFile(v, level, *base_iter);
697 }
698
699#ifndef NDEBUG
700 // Make sure there is no overlap in levels > 0
701 if (level > 0) {
702 for (uint32_t i = 1; i < v->files_[level].size(); i++) {
703 const InternalKey& prev_end = v->files_[level][i - 1]->largest;
704 const InternalKey& this_begin = v->files_[level][i]->smallest;
705 if (vset_->icmp_.Compare(prev_end, this_begin) >= 0) {
706 std::fprintf(stderr, "overlapping ranges in same level %s vs. %s\n",
707 prev_end.DebugString().c_str(),
708 this_begin.DebugString().c_str());
709 std::abort();
710 }
711 }
712 }
713#endif
714 }
715 }
716
717 void MaybeAddFile(Version* v, int level, FileMetaData* f) {
718 if (levels_[level].deleted_files.count(f->number) > 0) {
719 // File is deleted: do nothing
720 } else {
721 std::vector<FileMetaData*>* files = &v->files_[level];
722 if (level > 0 && !files->empty()) {
723 // Must not overlap
724 assert(vset_->icmp_.Compare((*files)[files->size() - 1]->largest,
725 f->smallest) < 0);
726 }
727 f->refs++;
728 files->push_back(f);
729 }
730 }
731};
732
733VersionSet::VersionSet(const std::string& dbname, const Options* options,
734 TableCache* table_cache,
735 const InternalKeyComparator* cmp)
736 : env_(options->env),
737 dbname_(dbname),
738 options_(options),
739 table_cache_(table_cache),
740 icmp_(*cmp),
741 next_file_number_(2),
742 manifest_file_number_(0), // Filled by Recover()
743 last_sequence_(0),
744 log_number_(0),
745 prev_log_number_(0),
746 descriptor_file_(nullptr),
747 descriptor_log_(nullptr),
748 dummy_versions_(this),
749 current_(nullptr) {
750 AppendVersion(new Version(this));
751}
752
753VersionSet::~VersionSet() {
754 current_->Unref();
755 assert(dummy_versions_.next_ == &dummy_versions_); // List must be empty
756 delete descriptor_log_;
757 delete descriptor_file_;
758}
759
760void VersionSet::AppendVersion(Version* v) {
761 // Make "v" current
762 assert(v->refs_ == 0);
763 assert(v != current_);
764 if (current_ != nullptr) {
765 current_->Unref();
766 }
767 current_ = v;
768 v->Ref();
769
770 // Append to linked list
771 v->prev_ = dummy_versions_.prev_;
772 v->next_ = &dummy_versions_;
773 v->prev_->next_ = v;
774 v->next_->prev_ = v;
775}
776
777Status VersionSet::LogAndApply(VersionEdit* edit, port::Mutex* mu) {
778 if (edit->has_log_number_) {
779 assert(edit->log_number_ >= log_number_);
780 assert(edit->log_number_ < next_file_number_);
781 } else {
782 edit->SetLogNumber(log_number_);
783 }
784
785 if (!edit->has_prev_log_number_) {
786 edit->SetPrevLogNumber(prev_log_number_);
787 }
788
789 edit->SetNextFile(next_file_number_);
790 edit->SetLastSequence(last_sequence_);
791
792 Version* v = new Version(this);
793 {
794 Builder builder(this, current_);
795 builder.Apply(edit);
796 builder.SaveTo(v);
797 }
798 Finalize(v);
799
800 // Initialize new descriptor log file if necessary by creating
801 // a temporary file that contains a snapshot of the current version.
802 std::string new_manifest_file;
803 Status s;
804 if (descriptor_log_ == nullptr) {
805 // No reason to unlock *mu here since we only hit this path in the
806 // first call to LogAndApply (when opening the database).
807 assert(descriptor_file_ == nullptr);
808 new_manifest_file = DescriptorFileName(dbname_, manifest_file_number_);
809 s = env_->NewWritableFile(new_manifest_file, &descriptor_file_);
810 if (s.ok()) {
811 descriptor_log_ = new log::Writer(descriptor_file_);
812 s = WriteSnapshot(descriptor_log_);
813 }
814 }
815
816 // Unlock during expensive MANIFEST log write
817 {
818 mu->Unlock();
819
820 // Write new record to MANIFEST log
821 if (s.ok()) {
822 std::string record;
823 edit->EncodeTo(&record);
824 s = descriptor_log_->AddRecord(record);
825 if (s.ok()) {
826 s = descriptor_file_->Sync();
827 }
828 if (!s.ok()) {
829 Log(options_->info_log, "MANIFEST write: %s\n", s.ToString().c_str());
830 }
831 }
832
833 // If we just created a new descriptor file, install it by writing a
834 // new CURRENT file that points to it.
835 if (s.ok() && !new_manifest_file.empty()) {
836 s = SetCurrentFile(env_, dbname_, manifest_file_number_);
837 }
838
839 mu->Lock();
840 }
841
842 // Install the new version
843 if (s.ok()) {
844 AppendVersion(v);
845 log_number_ = edit->log_number_;
846 prev_log_number_ = edit->prev_log_number_;
847 } else {
848 delete v;
849 if (!new_manifest_file.empty()) {
850 delete descriptor_log_;
851 delete descriptor_file_;
852 descriptor_log_ = nullptr;
853 descriptor_file_ = nullptr;
854 env_->RemoveFile(new_manifest_file);
855 }
856 }
857
858 return s;
859}
860
861Status VersionSet::Recover(bool* save_manifest) {
862 struct LogReporter : public log::Reader::Reporter {
863 Status* status;
864 void Corruption(size_t bytes, const Status& s) override {
865 if (this->status->ok()) *this->status = s;
866 }
867 };
868
869 // Read "CURRENT" file, which contains a pointer to the current manifest file
870 std::string current;
871 Status s = ReadFileToString(env_, CurrentFileName(dbname_), &current);
872 if (!s.ok()) {
873 return s;
874 }
875 if (current.empty() || current[current.size() - 1] != '\n') {
876 return Status::Corruption("CURRENT file does not end with newline");
877 }
878 current.resize(current.size() - 1);
879
880 std::string dscname = dbname_ + "/" + current;
881 SequentialFile* file;
882 s = env_->NewSequentialFile(dscname, &file);
883 if (!s.ok()) {
884 if (s.IsNotFound()) {
885 return Status::Corruption("CURRENT points to a non-existent file",
886 s.ToString());
887 }
888 return s;
889 }
890
891 bool have_log_number = false;
892 bool have_prev_log_number = false;
893 bool have_next_file = false;
894 bool have_last_sequence = false;
895 uint64_t next_file = 0;
896 uint64_t last_sequence = 0;
897 uint64_t log_number = 0;
898 uint64_t prev_log_number = 0;
899 Builder builder(this, current_);
900 int read_records = 0;
901
902 {
903 LogReporter reporter;
904 reporter.status = &s;
905 log::Reader reader(file, &reporter, true /*checksum*/,
906 0 /*initial_offset*/);
907 Slice record;
908 std::string scratch;
909 while (reader.ReadRecord(&record, &scratch) && s.ok()) {
910 ++read_records;
911 VersionEdit edit;
912 s = edit.DecodeFrom(record);
913 if (s.ok()) {
914 if (edit.has_comparator_ &&
915 edit.comparator_ != icmp_.user_comparator()->Name()) {
916 s = Status::InvalidArgument(
917 edit.comparator_ + " does not match existing comparator ",
918 icmp_.user_comparator()->Name());
919 }
920 }
921
922 if (s.ok()) {
923 builder.Apply(&edit);
924 }
925
926 if (edit.has_log_number_) {
927 log_number = edit.log_number_;
928 have_log_number = true;
929 }
930
931 if (edit.has_prev_log_number_) {
932 prev_log_number = edit.prev_log_number_;
933 have_prev_log_number = true;
934 }
935
936 if (edit.has_next_file_number_) {
937 next_file = edit.next_file_number_;
938 have_next_file = true;
939 }
940
941 if (edit.has_last_sequence_) {
942 last_sequence = edit.last_sequence_;
943 have_last_sequence = true;
944 }
945 }
946 }
947 delete file;
948 file = nullptr;
949
950 if (s.ok()) {
951 if (!have_next_file) {
952 s = Status::Corruption("no meta-nextfile entry in descriptor");
953 } else if (!have_log_number) {
954 s = Status::Corruption("no meta-lognumber entry in descriptor");
955 } else if (!have_last_sequence) {
956 s = Status::Corruption("no last-sequence-number entry in descriptor");
957 }
958
959 if (!have_prev_log_number) {
960 prev_log_number = 0;
961 }
962
963 MarkFileNumberUsed(prev_log_number);
964 MarkFileNumberUsed(log_number);
965 }
966
967 if (s.ok()) {
968 Version* v = new Version(this);
969 builder.SaveTo(v);
970 // Install recovered version
971 Finalize(v);
972 AppendVersion(v);
973 manifest_file_number_ = next_file;
974 next_file_number_ = next_file + 1;
975 last_sequence_ = last_sequence;
976 log_number_ = log_number;
977 prev_log_number_ = prev_log_number;
978
979 // See if we can reuse the existing MANIFEST file.
980 if (ReuseManifest(dscname, current)) {
981 // No need to save new manifest
982 } else {
983 *save_manifest = true;
984 }
985 } else {
986 std::string error = s.ToString();
987 Log(options_->info_log, "Error recovering version set with %d records: %s",
988 read_records, error.c_str());
989 }
990
991 return s;
992}
993
994bool VersionSet::ReuseManifest(const std::string& dscname,
995 const std::string& dscbase) {
996 if (!options_->reuse_logs) {
997 return false;
998 }
999 FileType manifest_type;
1000 uint64_t manifest_number;
1001 uint64_t manifest_size;
1002 if (!ParseFileName(dscbase, &manifest_number, &manifest_type) ||
1003 manifest_type != kDescriptorFile ||
1004 !env_->GetFileSize(dscname, &manifest_size).ok() ||
1005 // Make new compacted MANIFEST if old one is too big
1006 manifest_size >= TargetFileSize(options_)) {
1007 return false;
1008 }
1009
1010 assert(descriptor_file_ == nullptr);
1011 assert(descriptor_log_ == nullptr);
1012 Status r = env_->NewAppendableFile(dscname, &descriptor_file_);
1013 if (!r.ok()) {
1014 Log(options_->info_log, "Reuse MANIFEST: %s\n", r.ToString().c_str());
1015 assert(descriptor_file_ == nullptr);
1016 return false;
1017 }
1018
1019 Log(options_->info_log, "Reusing MANIFEST %s\n", dscname.c_str());
1020 descriptor_log_ = new log::Writer(descriptor_file_, manifest_size);
1021 manifest_file_number_ = manifest_number;
1022 return true;
1023}
1024
1025void VersionSet::MarkFileNumberUsed(uint64_t number) {
1026 if (next_file_number_ <= number) {
1027 next_file_number_ = number + 1;
1028 }
1029}
1030
1031void VersionSet::Finalize(Version* v) {
1032 // Precomputed best level for next compaction
1033 int best_level = -1;
1034 double best_score = -1;
1035
1036 for (int level = 0; level < config::kNumLevels - 1; level++) {
1037 double score;
1038 if (level == 0) {
1039 // We treat level-0 specially by bounding the number of files
1040 // instead of number of bytes for two reasons:
1041 //
1042 // (1) With larger write-buffer sizes, it is nice not to do too
1043 // many level-0 compactions.
1044 //
1045 // (2) The files in level-0 are merged on every read and
1046 // therefore we wish to avoid too many files when the individual
1047 // file size is small (perhaps because of a small write-buffer
1048 // setting, or very high compression ratios, or lots of
1049 // overwrites/deletions).
1050 score = v->files_[level].size() /
1051 static_cast<double>(config::kL0_CompactionTrigger);
1052 } else {
1053 // Compute the ratio of current size to size limit.
1054 const uint64_t level_bytes = TotalFileSize(v->files_[level]);
1055 score =
1056 static_cast<double>(level_bytes) / MaxBytesForLevel(options_, level);
1057 }
1058
1059 if (score > best_score) {
1060 best_level = level;
1061 best_score = score;
1062 }
1063 }
1064
1065 v->compaction_level_ = best_level;
1066 v->compaction_score_ = best_score;
1067}
1068
1069Status VersionSet::WriteSnapshot(log::Writer* log) {
1070 // TODO: Break up into multiple records to reduce memory usage on recovery?
1071
1072 // Save metadata
1073 VersionEdit edit;
1074 edit.SetComparatorName(icmp_.user_comparator()->Name());
1075
1076 // Save compaction pointers
1077 for (int level = 0; level < config::kNumLevels; level++) {
1078 if (!compact_pointer_[level].empty()) {
1079 InternalKey key;
1080 key.DecodeFrom(compact_pointer_[level]);
1081 edit.SetCompactPointer(level, key);
1082 }
1083 }
1084
1085 // Save files
1086 for (int level = 0; level < config::kNumLevels; level++) {
1087 const std::vector<FileMetaData*>& files = current_->files_[level];
1088 for (size_t i = 0; i < files.size(); i++) {
1089 const FileMetaData* f = files[i];
1090 edit.AddFile(level, f->number, f->file_size, f->smallest, f->largest);
1091 }
1092 }
1093
1094 std::string record;
1095 edit.EncodeTo(&record);
1096 return log->AddRecord(record);
1097}
1098
1099int VersionSet::NumLevelFiles(int level) const {
1100 assert(level >= 0);
1101 assert(level < config::kNumLevels);
1102 return current_->files_[level].size();
1103}
1104
1105const char* VersionSet::LevelSummary(LevelSummaryStorage* scratch) const {
1106 // Update code if kNumLevels changes
1107 static_assert(config::kNumLevels == 7, "");
1108 std::snprintf(
1109 scratch->buffer, sizeof(scratch->buffer), "files[ %d %d %d %d %d %d %d ]",
1110 int(current_->files_[0].size()), int(current_->files_[1].size()),
1111 int(current_->files_[2].size()), int(current_->files_[3].size()),
1112 int(current_->files_[4].size()), int(current_->files_[5].size()),
1113 int(current_->files_[6].size()));
1114 return scratch->buffer;
1115}
1116
1117uint64_t VersionSet::ApproximateOffsetOf(Version* v, const InternalKey& ikey) {
1118 uint64_t result = 0;
1119 for (int level = 0; level < config::kNumLevels; level++) {
1120 const std::vector<FileMetaData*>& files = v->files_[level];
1121 for (size_t i = 0; i < files.size(); i++) {
1122 if (icmp_.Compare(files[i]->largest, ikey) <= 0) {
1123 // Entire file is before "ikey", so just add the file size
1124 result += files[i]->file_size;
1125 } else if (icmp_.Compare(files[i]->smallest, ikey) > 0) {
1126 // Entire file is after "ikey", so ignore
1127 if (level > 0) {
1128 // Files other than level 0 are sorted by meta->smallest, so
1129 // no further files in this level will contain data for
1130 // "ikey".
1131 break;
1132 }
1133 } else {
1134 // "ikey" falls in the range for this table. Add the
1135 // approximate offset of "ikey" within the table.
1136 Table* tableptr;
1137 Iterator* iter = table_cache_->NewIterator(
1138 ReadOptions(), files[i]->number, files[i]->file_size, &tableptr);
1139 if (tableptr != nullptr) {
1140 result += tableptr->ApproximateOffsetOf(ikey.Encode());
1141 }
1142 delete iter;
1143 }
1144 }
1145 }
1146 return result;
1147}
1148
1149void VersionSet::AddLiveFiles(std::set<uint64_t>* live) {
1150 for (Version* v = dummy_versions_.next_; v != &dummy_versions_;
1151 v = v->next_) {
1152 for (int level = 0; level < config::kNumLevels; level++) {
1153 const std::vector<FileMetaData*>& files = v->files_[level];
1154 for (size_t i = 0; i < files.size(); i++) {
1155 live->insert(files[i]->number);
1156 }
1157 }
1158 }
1159}
1160
1161int64_t VersionSet::NumLevelBytes(int level) const {
1162 assert(level >= 0);
1163 assert(level < config::kNumLevels);
1164 return TotalFileSize(current_->files_[level]);
1165}
1166
1167int64_t VersionSet::MaxNextLevelOverlappingBytes() {
1168 int64_t result = 0;
1169 std::vector<FileMetaData*> overlaps;
1170 for (int level = 1; level < config::kNumLevels - 1; level++) {
1171 for (size_t i = 0; i < current_->files_[level].size(); i++) {
1172 const FileMetaData* f = current_->files_[level][i];
1173 current_->GetOverlappingInputs(level + 1, &f->smallest, &f->largest,
1174 &overlaps);
1175 const int64_t sum = TotalFileSize(overlaps);
1176 if (sum > result) {
1177 result = sum;
1178 }
1179 }
1180 }
1181 return result;
1182}
1183
1184// Stores the minimal range that covers all entries in inputs in
1185// *smallest, *largest.
1186// REQUIRES: inputs is not empty
1187void VersionSet::GetRange(const std::vector<FileMetaData*>& inputs,
1188 InternalKey* smallest, InternalKey* largest) {
1189 assert(!inputs.empty());
1190 smallest->Clear();
1191 largest->Clear();
1192 for (size_t i = 0; i < inputs.size(); i++) {
1193 FileMetaData* f = inputs[i];
1194 if (i == 0) {
1195 *smallest = f->smallest;
1196 *largest = f->largest;
1197 } else {
1198 if (icmp_.Compare(f->smallest, *smallest) < 0) {
1199 *smallest = f->smallest;
1200 }
1201 if (icmp_.Compare(f->largest, *largest) > 0) {
1202 *largest = f->largest;
1203 }
1204 }
1205 }
1206}
1207
1208// Stores the minimal range that covers all entries in inputs1 and inputs2
1209// in *smallest, *largest.
1210// REQUIRES: inputs is not empty
1211void VersionSet::GetRange2(const std::vector<FileMetaData*>& inputs1,
1212 const std::vector<FileMetaData*>& inputs2,
1213 InternalKey* smallest, InternalKey* largest) {
1214 std::vector<FileMetaData*> all = inputs1;
1215 all.insert(all.end(), inputs2.begin(), inputs2.end());
1216 GetRange(all, smallest, largest);
1217}
1218
1219Iterator* VersionSet::MakeInputIterator(Compaction* c) {
1220 ReadOptions options;
1221 options.verify_checksums = options_->paranoid_checks;
1222 options.fill_cache = false;
1223
1224 // Level-0 files have to be merged together. For other levels,
1225 // we will make a concatenating iterator per level.
1226 // TODO(opt): use concatenating iterator for level-0 if there is no overlap
1227 const int space = (c->level() == 0 ? c->inputs_[0].size() + 1 : 2);
1228 Iterator** list = new Iterator*[space];
1229 int num = 0;
1230 for (int which = 0; which < 2; which++) {
1231 if (!c->inputs_[which].empty()) {
1232 if (c->level() + which == 0) {
1233 const std::vector<FileMetaData*>& files = c->inputs_[which];
1234 for (size_t i = 0; i < files.size(); i++) {
1235 list[num++] = table_cache_->NewIterator(options, files[i]->number,
1236 files[i]->file_size);
1237 }
1238 } else {
1239 // Create concatenating iterator for the files from this level
1240 list[num++] = NewTwoLevelIterator(
1241 new Version::LevelFileNumIterator(icmp_, &c->inputs_[which]),
1242 &GetFileIterator, table_cache_, options);
1243 }
1244 }
1245 }
1246 assert(num <= space);
1247 Iterator* result = NewMergingIterator(&icmp_, list, num);
1248 delete[] list;
1249 return result;
1250}
1251
1252Compaction* VersionSet::PickCompaction() {
1253 Compaction* c;
1254 int level;
1255
1256 // We prefer compactions triggered by too much data in a level over
1257 // the compactions triggered by seeks.
1258 const bool size_compaction = (current_->compaction_score_ >= 1);
1259 const bool seek_compaction = (current_->file_to_compact_ != nullptr);
1260 if (size_compaction) {
1261 level = current_->compaction_level_;
1262 assert(level >= 0);
1263 assert(level + 1 < config::kNumLevels);
1264 c = new Compaction(options_, level);
1265
1266 // Pick the first file that comes after compact_pointer_[level]
1267 for (size_t i = 0; i < current_->files_[level].size(); i++) {
1268 FileMetaData* f = current_->files_[level][i];
1269 if (compact_pointer_[level].empty() ||
1270 icmp_.Compare(f->largest.Encode(), compact_pointer_[level]) > 0) {
1271 c->inputs_[0].push_back(f);
1272 break;
1273 }
1274 }
1275 if (c->inputs_[0].empty()) {
1276 // Wrap-around to the beginning of the key space
1277 c->inputs_[0].push_back(current_->files_[level][0]);
1278 }
1279 } else if (seek_compaction) {
1280 level = current_->file_to_compact_level_;
1281 c = new Compaction(options_, level);
1282 c->inputs_[0].push_back(current_->file_to_compact_);
1283 } else {
1284 return nullptr;
1285 }
1286
1287 c->input_version_ = current_;
1288 c->input_version_->Ref();
1289
1290 // Files in level 0 may overlap each other, so pick up all overlapping ones
1291 if (level == 0) {
1292 InternalKey smallest, largest;
1293 GetRange(c->inputs_[0], &smallest, &largest);
1294 // Note that the next call will discard the file we placed in
1295 // c->inputs_[0] earlier and replace it with an overlapping set
1296 // which will include the picked file.
1297 current_->GetOverlappingInputs(0, &smallest, &largest, &c->inputs_[0]);
1298 assert(!c->inputs_[0].empty());
1299 }
1300
1301 SetupOtherInputs(c);
1302
1303 return c;
1304}
1305
1306// Finds the largest key in a vector of files. Returns true if files is not
1307// empty.
1308bool FindLargestKey(const InternalKeyComparator& icmp,
1309 const std::vector<FileMetaData*>& files,
1310 InternalKey* largest_key) {
1311 if (files.empty()) {
1312 return false;
1313 }
1314 *largest_key = files[0]->largest;
1315 for (size_t i = 1; i < files.size(); ++i) {
1316 FileMetaData* f = files[i];
1317 if (icmp.Compare(f->largest, *largest_key) > 0) {
1318 *largest_key = f->largest;
1319 }
1320 }
1321 return true;
1322}
1323
1324// Finds minimum file b2=(l2, u2) in level file for which l2 > u1 and
1325// user_key(l2) = user_key(u1)
1326FileMetaData* FindSmallestBoundaryFile(
1327 const InternalKeyComparator& icmp,
1328 const std::vector<FileMetaData*>& level_files,
1329 const InternalKey& largest_key) {
1330 const Comparator* user_cmp = icmp.user_comparator();
1331 FileMetaData* smallest_boundary_file = nullptr;
1332 for (size_t i = 0; i < level_files.size(); ++i) {
1333 FileMetaData* f = level_files[i];
1334 if (icmp.Compare(f->smallest, largest_key) > 0 &&
1335 user_cmp->Compare(f->smallest.user_key(), largest_key.user_key()) ==
1336 0) {
1337 if (smallest_boundary_file == nullptr ||
1338 icmp.Compare(f->smallest, smallest_boundary_file->smallest) < 0) {
1339 smallest_boundary_file = f;
1340 }
1341 }
1342 }
1343 return smallest_boundary_file;
1344}
1345
1346// Extracts the largest file b1 from |compaction_files| and then searches for a
1347// b2 in |level_files| for which user_key(u1) = user_key(l2). If it finds such a
1348// file b2 (known as a boundary file) it adds it to |compaction_files| and then
1349// searches again using this new upper bound.
1350//
1351// If there are two blocks, b1=(l1, u1) and b2=(l2, u2) and
1352// user_key(u1) = user_key(l2), and if we compact b1 but not b2 then a
1353// subsequent get operation will yield an incorrect result because it will
1354// return the record from b2 in level i rather than from b1 because it searches
1355// level by level for records matching the supplied user key.
1356//
1357// parameters:
1358// in level_files: List of files to search for boundary files.
1359// in/out compaction_files: List of files to extend by adding boundary files.
1360void AddBoundaryInputs(const InternalKeyComparator& icmp,
1361 const std::vector<FileMetaData*>& level_files,
1362 std::vector<FileMetaData*>* compaction_files) {
1363 InternalKey largest_key;
1364
1365 // Quick return if compaction_files is empty.
1366 if (!FindLargestKey(icmp, *compaction_files, &largest_key)) {
1367 return;
1368 }
1369
1370 bool continue_searching = true;
1371 while (continue_searching) {
1372 FileMetaData* smallest_boundary_file =
1373 FindSmallestBoundaryFile(icmp, level_files, largest_key);
1374
1375 // If a boundary file was found advance largest_key, otherwise we're done.
1376 if (smallest_boundary_file != NULL) {
1377 compaction_files->push_back(smallest_boundary_file);
1378 largest_key = smallest_boundary_file->largest;
1379 } else {
1380 continue_searching = false;
1381 }
1382 }
1383}
1384
1385void VersionSet::SetupOtherInputs(Compaction* c) {
1386 const int level = c->level();
1387 InternalKey smallest, largest;
1388
1389 AddBoundaryInputs(icmp_, current_->files_[level], &c->inputs_[0]);
1390 GetRange(c->inputs_[0], &smallest, &largest);
1391
1392 current_->GetOverlappingInputs(level + 1, &smallest, &largest,
1393 &c->inputs_[1]);
1394 AddBoundaryInputs(icmp_, current_->files_[level + 1], &c->inputs_[1]);
1395
1396 // Get entire range covered by compaction
1397 InternalKey all_start, all_limit;
1398 GetRange2(c->inputs_[0], c->inputs_[1], &all_start, &all_limit);
1399
1400 // See if we can grow the number of inputs in "level" without
1401 // changing the number of "level+1" files we pick up.
1402 if (!c->inputs_[1].empty()) {
1403 std::vector<FileMetaData*> expanded0;
1404 current_->GetOverlappingInputs(level, &all_start, &all_limit, &expanded0);
1405 AddBoundaryInputs(icmp_, current_->files_[level], &expanded0);
1406 const int64_t inputs0_size = TotalFileSize(c->inputs_[0]);
1407 const int64_t inputs1_size = TotalFileSize(c->inputs_[1]);
1408 const int64_t expanded0_size = TotalFileSize(expanded0);
1409 if (expanded0.size() > c->inputs_[0].size() &&
1410 inputs1_size + expanded0_size <
1411 ExpandedCompactionByteSizeLimit(options_)) {
1412 InternalKey new_start, new_limit;
1413 GetRange(expanded0, &new_start, &new_limit);
1414 std::vector<FileMetaData*> expanded1;
1415 current_->GetOverlappingInputs(level + 1, &new_start, &new_limit,
1416 &expanded1);
1417 AddBoundaryInputs(icmp_, current_->files_[level + 1], &expanded1);
1418 if (expanded1.size() == c->inputs_[1].size()) {
1419 Log(options_->info_log,
1420 "Expanding@%d %d+%d (%ld+%ld bytes) to %d+%d (%ld+%ld bytes)\n",
1421 level, int(c->inputs_[0].size()), int(c->inputs_[1].size()),
1422 long(inputs0_size), long(inputs1_size), int(expanded0.size()),
1423 int(expanded1.size()), long(expanded0_size), long(inputs1_size));
1424 smallest = new_start;
1425 largest = new_limit;
1426 c->inputs_[0] = expanded0;
1427 c->inputs_[1] = expanded1;
1428 GetRange2(c->inputs_[0], c->inputs_[1], &all_start, &all_limit);
1429 }
1430 }
1431 }
1432
1433 // Compute the set of grandparent files that overlap this compaction
1434 // (parent == level+1; grandparent == level+2)
1435 if (level + 2 < config::kNumLevels) {
1436 current_->GetOverlappingInputs(level + 2, &all_start, &all_limit,
1437 &c->grandparents_);
1438 }
1439
1440 // Update the place where we will do the next compaction for this level.
1441 // We update this immediately instead of waiting for the VersionEdit
1442 // to be applied so that if the compaction fails, we will try a different
1443 // key range next time.
1444 compact_pointer_[level] = largest.Encode().ToString();
1445 c->edit_.SetCompactPointer(level, largest);
1446}
1447
1448Compaction* VersionSet::CompactRange(int level, const InternalKey* begin,
1449 const InternalKey* end) {
1450 std::vector<FileMetaData*> inputs;
1451 current_->GetOverlappingInputs(level, begin, end, &inputs);
1452 if (inputs.empty()) {
1453 return nullptr;
1454 }
1455
1456 // Avoid compacting too much in one shot in case the range is large.
1457 // But we cannot do this for level-0 since level-0 files can overlap
1458 // and we must not pick one file and drop another older file if the
1459 // two files overlap.
1460 if (level > 0) {
1461 const uint64_t limit = MaxFileSizeForLevel(options_, level);
1462 uint64_t total = 0;
1463 for (size_t i = 0; i < inputs.size(); i++) {
1464 uint64_t s = inputs[i]->file_size;
1465 total += s;
1466 if (total >= limit) {
1467 inputs.resize(i + 1);
1468 break;
1469 }
1470 }
1471 }
1472
1473 Compaction* c = new Compaction(options_, level);
1474 c->input_version_ = current_;
1475 c->input_version_->Ref();
1476 c->inputs_[0] = inputs;
1477 SetupOtherInputs(c);
1478 return c;
1479}
1480
1481Compaction::Compaction(const Options* options, int level)
1482 : level_(level),
1483 max_output_file_size_(MaxFileSizeForLevel(options, level)),
1484 input_version_(nullptr),
1485 grandparent_index_(0),
1486 seen_key_(false),
1487 overlapped_bytes_(0) {
1488 for (int i = 0; i < config::kNumLevels; i++) {
1489 level_ptrs_[i] = 0;
1490 }
1491}
1492
1493Compaction::~Compaction() {
1494 if (input_version_ != nullptr) {
1495 input_version_->Unref();
1496 }
1497}
1498
1499bool Compaction::IsTrivialMove() const {
1500 const VersionSet* vset = input_version_->vset_;
1501 // Avoid a move if there is lots of overlapping grandparent data.
1502 // Otherwise, the move could create a parent file that will require
1503 // a very expensive merge later on.
1504 return (num_input_files(0) == 1 && num_input_files(1) == 0 &&
1505 TotalFileSize(grandparents_) <=
1506 MaxGrandParentOverlapBytes(vset->options_));
1507}
1508
1509void Compaction::AddInputDeletions(VersionEdit* edit) {
1510 for (int which = 0; which < 2; which++) {
1511 for (size_t i = 0; i < inputs_[which].size(); i++) {
1512 edit->RemoveFile(level_ + which, inputs_[which][i]->number);
1513 }
1514 }
1515}
1516
1517bool Compaction::IsBaseLevelForKey(const Slice& user_key) {
1518 // Maybe use binary search to find right entry instead of linear search?
1519 const Comparator* user_cmp = input_version_->vset_->icmp_.user_comparator();
1520 for (int lvl = level_ + 2; lvl < config::kNumLevels; lvl++) {
1521 const std::vector<FileMetaData*>& files = input_version_->files_[lvl];
1522 while (level_ptrs_[lvl] < files.size()) {
1523 FileMetaData* f = files[level_ptrs_[lvl]];
1524 if (user_cmp->Compare(user_key, f->largest.user_key()) <= 0) {
1525 // We've advanced far enough
1526 if (user_cmp->Compare(user_key, f->smallest.user_key()) >= 0) {
1527 // Key falls in this file's range, so definitely not base level
1528 return false;
1529 }
1530 break;
1531 }
1532 level_ptrs_[lvl]++;
1533 }
1534 }
1535 return true;
1536}
1537
1538bool Compaction::ShouldStopBefore(const Slice& internal_key) {
1539 const VersionSet* vset = input_version_->vset_;
1540 // Scan to find earliest grandparent file that contains key.
1541 const InternalKeyComparator* icmp = &vset->icmp_;
1542 while (grandparent_index_ < grandparents_.size() &&
1543 icmp->Compare(internal_key,
1544 grandparents_[grandparent_index_]->largest.Encode()) >
1545 0) {
1546 if (seen_key_) {
1547 overlapped_bytes_ += grandparents_[grandparent_index_]->file_size;
1548 }
1549 grandparent_index_++;
1550 }
1551 seen_key_ = true;
1552
1553 if (overlapped_bytes_ > MaxGrandParentOverlapBytes(vset->options_)) {
1554 // Too much overlap for current output; start new output
1555 overlapped_bytes_ = 0;
1556 return true;
1557 } else {
1558 return false;
1559 }
1560}
1561
1562void Compaction::ReleaseInputs() {
1563 if (input_version_ != nullptr) {
1564 input_version_->Unref();
1565 input_version_ = nullptr;
1566 }
1567}
1568
1569} // namespace leveldb
1570