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