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 | |
22 | namespace leveldb { |
23 | |
24 | static 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. |
30 | static 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. |
37 | static int64_t ExpandedCompactionByteSizeLimit(const Options* options) { |
38 | return 25 * TargetFileSize(options); |
39 | } |
40 | |
41 | static 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 | |
54 | static 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 | |
59 | static 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 | |
67 | Version::~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 | |
87 | int 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 | |
107 | static 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 | |
114 | static 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 | |
121 | bool 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. |
163 | class 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 | |
210 | static 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 | |
222 | Iterator* 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 | |
229 | void 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() |
248 | namespace { |
249 | enum SaverState { |
250 | kNotFound, |
251 | kFound, |
252 | kDeleted, |
253 | kCorrupt, |
254 | }; |
255 | struct Saver { |
256 | SaverState state; |
257 | const Comparator* ucmp; |
258 | Slice user_key; |
259 | std::string* value; |
260 | }; |
261 | } // namespace |
262 | static 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 | |
277 | static bool NewestFirst(FileMetaData* a, FileMetaData* b) { |
278 | return a->number > b->number; |
279 | } |
280 | |
281 | void 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 | |
324 | Status 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 | |
402 | bool 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 | |
415 | bool 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 | |
453 | void Version::Ref() { ++refs_; } |
454 | |
455 | void Version::Unref() { |
456 | assert(this != &vset_->dummy_versions_); |
457 | assert(refs_ >= 1); |
458 | --refs_; |
459 | if (refs_ == 0) { |
460 | delete this; |
461 | } |
462 | } |
463 | |
464 | bool 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 | |
470 | int 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] |
498 | void 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 | |
540 | std::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. |
569 | class 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 | |
733 | VersionSet::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 | |
753 | VersionSet::~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 | |
760 | void 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 | |
777 | Status 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 | |
861 | Status 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_), ¤t); |
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 | |
994 | bool 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 | |
1025 | void VersionSet::MarkFileNumberUsed(uint64_t number) { |
1026 | if (next_file_number_ <= number) { |
1027 | next_file_number_ = number + 1; |
1028 | } |
1029 | } |
1030 | |
1031 | void 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 | |
1069 | Status 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 | |
1099 | int VersionSet::NumLevelFiles(int level) const { |
1100 | assert(level >= 0); |
1101 | assert(level < config::kNumLevels); |
1102 | return current_->files_[level].size(); |
1103 | } |
1104 | |
1105 | const 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 | |
1117 | uint64_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 | |
1149 | void 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 | |
1161 | int64_t VersionSet::NumLevelBytes(int level) const { |
1162 | assert(level >= 0); |
1163 | assert(level < config::kNumLevels); |
1164 | return TotalFileSize(current_->files_[level]); |
1165 | } |
1166 | |
1167 | int64_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 |
1187 | void 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 |
1211 | void 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 | |
1219 | Iterator* 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 | |
1252 | Compaction* 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. |
1308 | bool 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) |
1326 | FileMetaData* 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. |
1360 | void 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 | |
1385 | void 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 | |
1448 | Compaction* 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 | |
1481 | Compaction::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 | |
1493 | Compaction::~Compaction() { |
1494 | if (input_version_ != nullptr) { |
1495 | input_version_->Unref(); |
1496 | } |
1497 | } |
1498 | |
1499 | bool 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 | |
1509 | void 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 | |
1517 | bool 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 | |
1538 | bool 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 | |
1562 | void Compaction::ReleaseInputs() { |
1563 | if (input_version_ != nullptr) { |
1564 | input_version_->Unref(); |
1565 | input_version_ = nullptr; |
1566 | } |
1567 | } |
1568 | |
1569 | } // namespace leveldb |
1570 | |